Por que uma mudança pequena de ε altera tanto o número de grupos?

As decisões são por limiar: conta-se o número de pontos numa bola fixa. Um ε um pouco maior pode estender uma ponte entre duas regiões densas e colar os grupos; um menor, romper. Essa falta de suavidade está no próprio modelo de densidade rígido.

Como escolher minPts no plano?

Costuma-se tomar minPts ≈ 2·dim (no plano, 4 como começo) e depois ajustar ao nível de ruído aceitável: minPts maior — exigência mais dura aos núcleos e mais pontos vão ao ruído.

Em que o DBSCAN difere do agrupamento k-médias?

O número de grupos não se fixa de antemão, a forma pode ser qualquer, e os pontos raros são declarados ruído, em vez de serem enfiados à força no grupo mais próximo. O preço são dois limiares ε e minPts no lugar de um só k, e a sensibilidade à escala das distâncias.

DBSCAN

Raio ε e limiar minPts: núcleo, fronteira e ruído. Grupos de forma qualquer, sem k prefixado; em torno dos núcleos pode-se mostrar circunferências de raio ε.

Sobre o modelo

O DBSCAN acha grupos de forma qualquer pela densidade local e não pede que se fixe o número k de grupos. Dois parâmetros: o raio da vizinhança ε e minPts — o número mínimo de pontos na bola (incluindo o próprio ponto) para que o objeto seja núcleo. Os grupos crescem a partir dos núcleos: um ponto ainda não visitado na vizinhança ε de um núcleo entra no mesmo grupo; os não-núcleos alcançados são fronteira; o que não foi absorvido é ruído. Um ε pequeno rompe as «pontes» raras entre os amontoados; um ε grande cola as regiões. Os rótulos são recalculados na hora ao mudar ε e minPts: cor por grupo, ruído cinza com contorno vermelho; opcionalmente, circunferências de raio ε em torno dos núcleos. A demonstração mistura nuvens gaussianas densas com um fundo uniforme, para o ruído aparecer.

Para quem: Aprendizado de máquina e análise espacial: agrupamento por densidade, comparação com as k-médias.

Conceitos-chave

DBSCAN
vizinhança ε
minPts
núcleo
fronteira
ruído
alcançabilidade por densidade
grupo de forma qualquer

Como funciona

Um ponto é núcleo se na bola de raio ε há pelo menos minPts vizinhos. O grupo cresce a partir dos núcleos pela ε-conexidade; os pontos não absorvidos são ruído. Um ε pequeno corta as pontes entre os amontoados; um grande as cola. A demonstração — nuvens densas e um fundo esparso.

Perguntas frequentes

Por que uma mudança pequena de ε altera tanto o número de grupos?: As decisões são por limiar: conta-se o número de pontos numa bola fixa. Um ε um pouco maior pode estender uma ponte entre duas regiões densas e colar os grupos; um menor, romper. Essa falta de suavidade está no próprio modelo de densidade rígido.
Como escolher minPts no plano?: Costuma-se tomar minPts ≈ 2·dim (no plano, 4 como começo) e depois ajustar ao nível de ruído aceitável: minPts maior — exigência mais dura aos núcleos e mais pontos vão ao ruído.
Em que o DBSCAN difere do agrupamento k-médias?: O número de grupos não se fixa de antemão, a forma pode ser qualquer, e os pontos raros são declarados ruído, em vez de serem enfiados à força no grupo mais próximo. O preço são dois limiares ε e minPts no lugar de um só k, e a sensibilidade à escala das distâncias.

Continue com temas próximos desta categoria — ou todos os 85 em «Visualização matemática».

Toda a categoria →

NovoEscola

Agrupamento k-médias

Abrir o simulador

Pontos no plano, número de grupos k e centróides iniciais. Passo de Lloyd: atribuição ao centro mais próximo e deslocamento do centróide ao baricentro. A demonstração é uma mistura de gaussianas; soma dos quadrados intra-grupo.

NovoEscola

Regressão linear: MQO, ridge, lasso e R²

Abrir o simulador

Pontos no plano e o modelo y = β₀ + β₁x: MQO usual, ridge (penalização L₂ na inclinação) ou lasso (penalização L₁). O deslocamento Δy no ponto de maior |x| é um valor atípico de grande alavancagem; comparam-se SSE e R².

NovoUniversidade / pesquisa