DBSCAN

Atualizado 2025-11-05 Leitura 4 min

Resumo

O DBSCAN (Density-Based Spatial Clustering of Applications with Noise) agrupa pontos de acordo com a densidade local, de modo que os clusters podem ter qualquer formato enquanto regiões esparsas se tornam ruído.
Dois hiperparâmetros controlam o modelo: eps, o raio da vizinhança, e min_samples, o número mínimo de vizinhos necessários para que um ponto se torne uma amostra central.
Os pontos são classificados como centrais, de fronteira ou ruído; os clusters são componentes conexas de pontos centrais mais seus vizinhos de fronteira.
Uma receita comum de ajuste é fixar min_samples (≥ dimensionalidade + 1) e varrer eps enquanto se inspeciona a proporção de pontos marcados como ruído.

Intuição #

Este método deve ser interpretado por meio de suas suposições, condições dos dados e como as escolhas de parâmetros afetam a generalização.

Explicação Detalhada #

1. Visão geral #

O DBSCAN não requer o número de clusters antecipadamente. Em vez disso, ele inspeciona cada amostra:

Pontos centrais: pelo menos min_samples vizinhos dentro da distância eps.
Pontos de fronteira: estão dentro da esfera eps de um ponto central, mas não atendem ao critério central por si mesmos.
Pontos de ruído: não pertencem a nenhuma vizinhança central.

Por causa dessa visão baseada em densidade, o DBSCAN é robusto a clusters não convexos, como duas meias-luas ou círculos concêntricos. Sempre normalize os atributos para que eps tenha uma interpretação significativa.

2. Definição formal #

Dado (x_i \in \mathcal{X}), sua (\varepsilon)-vizinhança é

$$ \mathcal{N}_\varepsilon(x_i) = \{ x_j \in \mathcal{X} \mid \lVert x_i - x_j \rVert \le \varepsilon \}. $$

Se (|\mathcal{N}_\varepsilon(x_i)| \ge \texttt{min_samples}|), o ponto é central. O DBSCAN constrói clusters explorando pontos alcançáveis por densidade; qualquer ponto não visitado se torna ruído. Com um índice espacial, a complexidade geral é (O(n \log n)).

3. Exemplo em Python #

O trecho abaixo usa o DBSCAN do scikit-learn em um conjunto de dados de duas meias-luas, colore os pontos centrais/de fronteira de forma diferente e informa quantas amostras são marcadas como ruído.

from __future__ import annotations

import japanize_matplotlib
import matplotlib.pyplot as plt
import numpy as np
from numpy.typing import NDArray
from sklearn.cluster import DBSCAN
from sklearn.datasets import make_moons
from sklearn.preprocessing import StandardScaler

def run_dbscan_demo(
    n_samples: int = 600,
    noise: float = 0.08,
    eps: float = 0.3,
    min_samples: int = 10,
    random_state: int = 0,
) -> dict[str, int]:
    japanize_matplotlib.japanize()
    features, _ = make_moons(
        n_samples=n_samples,
        noise=noise,
        random_state=random_state,
    )
    features = StandardScaler().fit_transform(features)

    model = DBSCAN(eps=eps, min_samples=min_samples)
    labels = model.fit_predict(features)

    unique_labels = sorted(np.unique(labels))
    cluster_ids = [label for label in unique_labels if label != -1]
    noise_count = int(np.sum(labels == -1))

    core_mask = np.zeros(labels.shape[0], dtype=bool)
    if hasattr(model, "core_sample_indices_"):
        core_mask[model.core_sample_indices_] = True

    fig, ax = plt.subplots(figsize=(6.2, 5.2))
    palette = plt.cm.get_cmap("tab10", max(len(cluster_ids), 1))

    for order, cluster_id in enumerate(cluster_ids):
        mask = labels == cluster_id
        color = palette(order)
        ax.scatter(
            features[mask & core_mask, 0],
            features[mask & core_mask, 1],
            c=[color],
            s=36,
            edgecolor="white",
            linewidth=0.2,
            label=f"Cluster {cluster_id} core",
        )
        ax.scatter(
            features[mask & ~core_mask, 0],
            features[mask & ~core_mask, 1],
            c=[color],
            s=24,
            edgecolor="white",
            linewidth=0.2,
            marker="o",
            label=f"Cluster {cluster_id} border",
        )

    if noise_count:
        noise_mask = labels == -1
        ax.scatter(
            features[noise_mask, 0],
            features[noise_mask, 1],
            c="#9ca3af",
            marker="x",
            s=28,
            linewidth=0.8,
            label="Noise",
        )

    ax.set_title("DBSCAN clustering demo")
    ax.set_xlabel("Feature 1")
    ax.set_ylabel("Feature 2")
    ax.grid(alpha=0.2)
    ax.legend(loc="upper right", fontsize=9)
    fig.tight_layout()
    plt.show()

    return {"n_clusters": len(cluster_ids), "n_noise": noise_count}

result = run_dbscan_demo()
print(f"Clusters discovered: {result['n_clusters']}")
print(f"Noise points: {result['n_noise']}")

Resultado do agrupamento DBSCAN

4. Dicas práticas #

Plote as distâncias ordenadas ao k-ésimo vizinho (k = min_samples) para escolher o eps onde a curva apresenta um cotovelo.
Use pipelines para que a normalização e o agrupamento sejam executados juntos; caso contrário, as decisões baseadas em distância perdem o significado.
Para conjuntos de dados muito grandes, considere vizinhos mais próximos aproximados ou mude para o HDBSCAN, que estende o DBSCAN para dados de múltiplas densidades e elimina a necessidade de ajustar o eps.

5. Referências #

Ester, M., Kriegel, H.-P., Sander, J., & Xu, X. (1996). A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. KDD.
Schubert, E., Sander, J., Ester, M., Kriegel, H.-P., & Xu, X. (2017). DBSCAN Revisited, Revisited. ACM Transactions on Database Systems.
scikit-learn developers. (2024). Clustering. https://scikit-learn.org/stable/modules/clustering.html