DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

O DBSCAN (agrupamento espacial baseado em densidade com ruído) é um algoritmo de aprendizagem não supervisionada que agrupa pontos muito próximos em clusters e identifica como ruído os pontos em regiões esparsas. Martin Ester, Hans-Peter Kriegel, Jörg Sander e Xiaowei Xu apresentaram-no na conferência KDD em 1996. Não exige definir antecipadamente o número de clusters, deteta clusters de qualquer forma, como anéis, crescentes ou estradas sinuosas, e o rótulo de ruído também funciona como uma forma simples de deteção de anomalias. O algoritmo completo é controlado por dois parâmetros: o raio da vizinhança e o número de pontos necessários para que uma vizinhança seja considerada densa.

Pontos centrais, pontos de fronteira e ruído#

O DBSCAN analisa a vizinhança de cada ponto — o conjunto de pontos a uma distância eps — e contabiliza os seus elementos:

• Ponto central: tem pelo menos min_samples pontos na sua vizinhança, contando consigo próprio na implementação do scikit-learn. Os pontos centrais formam o interior denso de um cluster.
• Ponto de fronteira: tem poucos vizinhos para ser um ponto central, mas fica a uma distância eps de um ponto central. Os pontos de fronteira formam os limites de um cluster.
• Ponto de ruído: não é nenhum dos anteriores, pelo que não pertence a qualquer cluster e recebe o rótulo -1.

Um cluster cresce a partir de qualquer ponto central ainda não visitado. O DBSCAN adiciona todos os pontos da sua vizinhança e, em seguida, repete o processo a partir de cada novo ponto central adicionado até não ser possível alcançar mais pontos; assim, uma cadeia de vizinhanças densas sobrepostas forma um único cluster, independentemente das curvas que faça. Os pontos de fronteira juntam-se a um cluster, mas não o expandem. O resultado é determinístico para uma dada ordem de entrada, mas um ponto de fronteira ao alcance de dois clusters junta-se ao cluster que o alcançar primeiro; por isso, baralhar os dados pode deslocar pontos de fronteira entre clusters.

Escolher eps e min_samples#

O raio eps é o fator mais importante e depende da escala dos dados, razão pela qual normalmente se padronizam primeiro as características. Um raio demasiado pequeno deixa a maioria dos pontos classificados como ruído, enquanto um raio demasiado grande funde clusters vizinhos. A heurística habitual ordena a distância de cada ponto ao seu k-ésimo vizinho mais próximo, sendo k igual a min_samples, e escolhe eps no joelho dessa curva, onde as distâncias começam a aumentar acentuadamente. Valores de min_samples mais altos tornam o agrupamento mais tolerante ao ruído e são comuns em conjuntos de dados grandes ou ruidosos. Em espaços de muitas dimensões, como os embeddings de imagens, as distâncias entre pontos tornam-se semelhantes; por isso, os especialistas aplicam frequentemente uma redução da dimensionalidade, como a análise de componentes principais (PCA), antes de executar o DBSCAN.

DBSCAN, K-Means e HDBSCAN#

O agrupamento K-means exige que se indique antecipadamente o número de clusters, atribui cada ponto ao centroide mais próximo e, por isso, favorece clusters compactos e arredondados, além de incluir os valores atípicos nalgum grupo. O DBSCAN descobre o número de clusters com base na densidade e deixa os valores atípicos de fora. O seu ponto fraco é um único eps global: quando os clusters têm densidades muito diferentes, nenhum raio consegue separar os clusters esparsos do ruído e os clusters densos uns dos outros. O HDBSCAN resolve este problema executando, na prática, o DBSCAN para todos os valores de eps e mantendo os clusters mais estáveis; ambos os algoritmos estão disponíveis no módulo de agrupamento do scikit-learn, juntamente com o algoritmo relacionado OPTICS.

Este exemplo agrupa dois crescentes entrelaçados com 20 valores atípicos aleatórios adicionados e avalia cada resultado em relação aos grupos verdadeiros através do índice de Rand ajustado, em que 1.0 corresponde a uma correspondência perfeita:

import numpy as np
from sklearn.cluster import DBSCAN, KMeans
from sklearn.datasets import make_moons
from sklearn.metrics import adjusted_rand_score

# Two interleaving crescents plus 20 scattered outliers (true label -1)
X, y = make_moons(n_samples=300, noise=0.05, random_state=0)
rng = np.random.default_rng(0)
X = np.vstack([X, rng.uniform(-1.5, 2.5, size=(20, 2))])
y = np.concatenate([y, np.full(20, -1)])

# DBSCAN infers clusters from density; k-means is told there are 2
db_labels = DBSCAN(eps=0.2, min_samples=5).fit_predict(X)
km_labels = KMeans(n_clusters=2, random_state=0).fit_predict(X)

print(f"DBSCAN: {db_labels.max() + 1} clusters, {(db_labels == -1).sum()} noise points")
print(f"ARI: DBSCAN {adjusted_rand_score(y, db_labels):.2f}, k-means {adjusted_rand_score(y, km_labels):.2f}")

O script apresenta 2 clusters e 15 pontos de ruído para o DBSCAN, bem como índices de Rand ajustados de 0.97 para o DBSCAN e 0.20 para o k-means. O DBSCAN acompanha ambos os crescentes e separa os valores atípicos que ficaram afastados deles, enquanto o k-means divide os crescentes com um limite reto, apesar de ter recebido o número correto de clusters.

Aplicações no mundo real#

• Perceção LiDAR: os pipelines de veículos autónomos e de robótica removem os pontos do solo de uma leitura LiDAR e agrupam depois os pontos 3D restantes em obstáculos separados. O agrupamento baseado na densidade é uma escolha comum, porque o número de objetos é desconhecido.
• Pós-processamento de deteções: os centros das caixas das deteções YOLO26, disponíveis como result.boxes.xywh, podem ser agrupados com DBSCAN para encontrar grupos de pessoas numa multidão ou locais recorrentes de defeitos numa linha de produção; as deteções isoladas são então classificadas como ruído.
• Monitoramento de fraudes e sensores: Transações ou leituras rotuladas como -1 ficam longe de todos os grupos densos de comportamento normal e tornam-se candidatas a revisão.
• Análise geoespacial: Empresas de entrega e transporte por aplicativo agrupam pontos de GPS para encontrar paradas frequentes e locais populares de embarque. O DBSCAN do Scikit-learn aceita metric="haversine" para latitude e longitude em radianos; nesse caso, eps é um ângulo na esfera unitária, então um raio de 100 metros passa a ser eps = 0.1 / 6371, usando o raio médio da Terra de 6,371 km.