Clustering DBSCAN

O que é DBSCAN?

DBSCAN agrupa pontos densamente empacotados e marca os de baixa densidade como outliers. Não requer especificar K e encontra clusters de forma arbitrária.

Dois parâmetros: epsilon (eps) — distância máxima de vizinhança; minSamples — pontos mínimos para região densa. Pontos: núcleo, borda ou ruído.

Efetivo para densidades variáveis, formas não-convexas e ruído significativo. Limitado quando densidades dos clusters diferem muito.

Formula: Ponto central: |N_eps(p)| ≥ minSamples Ponto de borda: |N_eps(p)| < minSamples, mas dentro de eps de um ponto central Ruído: nem central nem de borda N_eps(p) = {q : dist(p,q) ≤ eps}

Exemplo de cálculo

Pontos: (1,1), (1.1,1.2), (0.9,0.8), (5,5), (5.1,5.2), (4.9,4.8), (10,10). eps=1.0, minSamples=2. Cluster 1: 3 pts, Cluster 2: 3 pts, Ruído: (10,10).

Quando usar esta calculadora

• Um cientista de dados realizando detecção de anomalias em que os outliers precisam ser explicitamente identificados como pontos de ruído separados dos clusters
• Um analista espacial agrupando dados geográficos (p. ex., focos de criminalidade, locais de entrega) em que as formas dos clusters são irregulares e o número de grupos é desconhecido
• Um pesquisador analisando dados com ruído natural em que forçar cada ponto para dentro de um cluster (como faz o K-Means) distorceria a análise
• Um engenheiro agrupando leituras de sensores que formam padrões não esféricos (anéis, crescentes, formas alongadas) que o K-Means não consegue detectar

Erros comuns a evitar

• Definir epsilon grande demais — isso funde clusters distintos em um só; use o gráfico de k-distâncias para encontrar o valor apropriado de eps no joelho da curva
• Definir epsilon pequeno demais — isso classifica a maioria dos pontos como ruído e encontra poucos ou nenhum cluster; se a maior parte dos seus dados é rotulada como ruído, eps provavelmente está pequeno demais
• Não escalonar as variáveis antes do agrupamento — o DBSCAN usa a distância euclidiana, então variáveis com escalas maiores dominam o cálculo da distância; padronize todas as variáveis primeiro
• Usar o DBSCAN quando os clusters têm densidades muito diferentes — um único valor de eps não consegue acomodar simultaneamente clusters densos e esparsos; considere HDBSCAN ou OPTICS em vez disso

Como interpretar os resultados

• Pontos de ruído (rotulados como outliers) são pontos de dados em regiões de baixa densidade — podem representar anomalias genuínas, erros de medição ou dados de transição entre clusters
• O número de clusters é determinado automaticamente pelos dados e parâmetros, não especificado de antemão — esta é uma vantagem fundamental sobre o K-Means
• Se o algoritmo encontra apenas um cluster ou classifica tudo como ruído, tente ajustar eps e minSamples — os parâmetros precisam de ajuste para corresponder à estrutura de densidade dos seus dados

Normas e referências relacionadas

• Ester, Kriegel, Sander & Xu (1996), 'A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise', Proc. KDD-96 — artigo original do DBSCAN
• Schubert, Sander, Ester, Kriegel & Xu (2017), 'DBSCAN Revisited, Revisited', ACM Transactions on Database Systems — orientação moderna sobre a seleção de parâmetros e a heurística da distância k

Perguntas frequentes

Como escolher eps e minSamples?

minSamples: tipicamente 2×dimensões. eps: plotar distância k-vizinhos mais próximos, escolher o 'joelho'.

Quando usar DBSCAN ao invés de K-Means?

Quando não se conhece K, formas irregulares ou ruído significativo. K-Means é mais rápido para clusters esféricos.