70  DBSCAN y HDBSCAN

K-Means y el clustering jerárquico asumen implícitamente que los grupos son convexos o al menos compactos en torno a un centroide o medoide. En muchos problemas reales, los grupos tienen formas arbitrarias: anillos concéntricos, espirales, formas irregulares determinadas por procesos físicos o geográficos. Para estos casos, los métodos basados en densidad son más adecuados.

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) fue propuesto por Ester et al. en 1996 (Ester et al. 1996) y se convirtió en uno de los algoritmos de clustering más influyentes, ganando el premio Test of Time en la conferencia KDD 2014. Su idea central es simple: un grupo es una región de alta densidad de puntos, separada de otras regiones de alta densidad por regiones de baja densidad. Los puntos en zonas de baja densidad se clasifican como ruido.

1 Conceptos fundamentales

DBSCAN opera sobre dos parámetros: el radio de vecindad \(\varepsilon\) y el número mínimo de puntos \(\text{minPts}\).

Definición. La \(\varepsilon\)-vecindad de un punto \(\mathbf{x}\) es el conjunto de puntos a distancia menor o igual que \(\varepsilon\): \[ N_\varepsilon(\mathbf{x}) = \{\mathbf{y}\in\mathcal{D} \mid d(\mathbf{x},\mathbf{y})\leq\varepsilon\}. \tag{1}\]

Con estos dos parámetros se clasifican los puntos en tres categorías.

Definición. Un punto \(\mathbf{x}\) es:

• Punto núcleo (core point): si \(|N_\varepsilon(\mathbf{x})|\geq\text{minPts}\).
• Punto borde (border point): si no es punto núcleo pero está en la \(\varepsilon\)-vecindad de algún punto núcleo.
• Punto de ruido (noise point): si no es punto núcleo ni punto borde.

Los puntos núcleo tienen suficientes vecinos cercanos como para considerarse parte del interior de un grupo. Los puntos borde están cerca de un grupo pero no tienen suficientes vecinos propios. Los puntos de ruido son aislados y no pertenecen a ningún grupo.

2 Alcanzabilidad y conectividad por densidad

La noción de grupo en DBSCAN se define mediante la alcanzabilidad por densidad entre puntos.

Definición. Un punto \(\mathbf{y}\) es directamente alcanzable por densidad desde \(\mathbf{x}\) (con parámetros \(\varepsilon\) y \(\text{minPts}\)) si: 1. \(\mathbf{y}\in N_\varepsilon(\mathbf{x})\), y 2. \(|N_\varepsilon(\mathbf{x})|\geq\text{minPts}\) (es decir, \(\mathbf{x}\) es punto núcleo).

Definición. Un punto \(\mathbf{y}\) es alcanzable por densidad desde \(\mathbf{x}\) si existe una cadena \(\mathbf{x}=\mathbf{p}_1,\mathbf{p}_2,\dots,\mathbf{p}_k=\mathbf{y}\) tal que \(\mathbf{p}_{i+1}\) es directamente alcanzable desde \(\mathbf{p}_i\).

Definición. Dos puntos \(\mathbf{x}\) e \(\mathbf{y}\) están conectados por densidad si existe un punto \(\mathbf{z}\) tal que ambos son alcanzables por densidad desde \(\mathbf{z}\).

Un grupo DBSCAN es un conjunto maximal de puntos mutuamente conectados por densidad.

3 Algoritmo DBSCAN

Algoritmo DBSCAN.

Entrada: \(\mathcal{D}=\{\mathbf{x}_1,\dots,\mathbf{x}_n\}\), parámetros \(\varepsilon\) y \(\text{minPts}\).

1. Etiquetar todos los puntos como no visitados.
2. Para cada punto no visitado \(\mathbf{x}\):
   1. Marcar \(\mathbf{x}\) como visitado.
   2. Calcular \(N_\varepsilon(\mathbf{x})\).
   3. Si \(|N_\varepsilon(\mathbf{x})|<\text{minPts}\): etiquetar \(\mathbf{x}\) como ruido (provisionalmente).
   4. Si \(|N_\varepsilon(\mathbf{x})|\geq\text{minPts}\): crear nuevo grupo \(C\) y expandir:
      • Agregar \(\mathbf{x}\) a \(C\).
      • Para cada \(\mathbf{y}\in N_\varepsilon(\mathbf{x})\) no visitado: visitar \(\mathbf{y}\) y, si es punto núcleo, agregar \(N_\varepsilon(\mathbf{y})\) a la cola de expansión.
      • Agregar todos los alcanzables al grupo \(C\).

Salida: etiquetas de grupo para cada punto (o ruido).

La complejidad de DBSCAN es \(O(n^2)\) con búsqueda lineal de vecinos. Con un índice espacial como k-d tree o R-tree, se reduce a \(O(n\log n)\) en promedio para datos de baja dimensión. En alta dimensión, la maldición de la dimensionalidad hace que los índices espaciales pierdan eficiencia.

DBSCAN — explorador de ε-vecindad
Ajusta ε y minPts para ver cómo cambian los puntos núcleo, borde y ruido

ε = 0.9

minPts = 3

4 Selección de parámetros

La elección de \(\varepsilon\) y \(\text{minPts}\) es el principal desafío de DBSCAN. Los valores inadecuados pueden producir un único grupo masivo (ε grande), muchos puntos de ruido (ε pequeño), o fragmentación de grupos naturales.

4.1 Heurística del gráfico k-distancia

Una heurística clásica para elegir \(\varepsilon\) es el gráfico de k-distancia. Para cada punto, se calcula la distancia al k-ésimo vecino más cercano. Estos valores se ordenan de mayor a menor y se grafican. El codo de la curva sugiere un buen valor de \(\varepsilon\).

import numpy as np
from sklearn.neighbors import NearestNeighbors
from sklearn.datasets import make_moons
import matplotlib.pyplot as plt

X, _ = make_moons(n_samples=300, noise=0.05, random_state=42)

k = 5
nbrs = NearestNeighbors(n_neighbors=k).fit(X)
distances, _ = nbrs.kneighbors(X)
k_dist = np.sort(distances[:, -1])[::-1]

plt.figure(figsize=(7, 3))
plt.plot(k_dist, color="#1a3a5c", linewidth=2)
plt.axhline(0.15, color="#f59e0b", linestyle="--", label="ε = 0.15 (sugerido)")
plt.xlabel("Puntos ordenados por k-distancia")
plt.ylabel("k-distancia")
plt.title(f"Gráfico {k}-distancia para seleccionar ε")
plt.legend()
plt.tight_layout()
plt.show()

4.2 Regla general para minPts

Como guía práctica, se recomienda \(\text{minPts}\geq d+1\) donde \(d\) es la dimensión de los datos (Ester et al. 1996). Para datos ruidosos, valores mayores son más robustos. En la práctica se usan frecuentemente \(\text{minPts}\in\{3,4,5,10\}\) y se ajusta \(\varepsilon\) con la heurística k-distancia.

from sklearn.datasets import make_moons
from sklearn.cluster import DBSCAN
from sklearn.metrics import silhouette_score
import numpy as np

X, y_true = make_moons(n_samples=300, noise=0.05, random_state=42)

db = DBSCAN(eps=0.15, min_samples=5)
labels = db.fit_predict(X)

n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
n_noise = np.sum(labels == -1)

print(f"Grupos encontrados: {n_clusters}")
print(f"Puntos de ruido: {n_noise} ({100*n_noise/len(X):.1f}%)")

mask = labels != -1
if mask.sum() > 1 and len(set(labels[mask])) > 1:
    print(f"Silueta (sin ruido): {silhouette_score(X[mask], labels[mask]):.4f}")

Grupos encontrados: 2
Puntos de ruido: 0 (0.0%)
Silueta (sin ruido): 0.3308

5 Ventajas y limitaciones

Ventajas de DBSCAN:

• Detecta grupos de forma arbitraria, no solo convexos.
• Identifica automáticamente puntos de ruido sin necesidad de asignarlos a ningún grupo.
• No requiere especificar el número de grupos de antemano.
• Es relativamente robusto a outliers.

Limitaciones:

• No funciona bien cuando los grupos tienen densidades muy distintas: un \(\varepsilon\) que conecta grupos de baja densidad puede fusionar grupos de alta densidad.
• La selección de \(\varepsilon\) y \(\text{minPts}\) puede ser difícil en datos de alta dimensión donde las distancias colapsan.
• Computacionalmente ineficiente para conjuntos de datos muy grandes sin indexación espacial.

6 HDBSCAN

HDBSCAN (Hierarchical DBSCAN) extiende DBSCAN construyendo una jerarquía de grupos basada en densidad que es más robusta ante variaciones de densidad (Campello et al. 2013). La idea central es transformar las distancias originales en distancias de alcanzabilidad mutua, construir un árbol de expansión mínimo sobre estas distancias, convertirlo en una jerarquía de grupos y extraer los grupos más persistentes.

Definición. La distancia de alcanzabilidad mutua entre dos puntos \(\mathbf{x}\) y \(\mathbf{y}\) es: \[ d_{\text{mreach},k}(\mathbf{x},\mathbf{y}) = \max\{d_k(\mathbf{x}),\; d_k(\mathbf{y}),\; d(\mathbf{x},\mathbf{y})\}, \tag{2}\] donde \(d_k(\mathbf{x})\) es la distancia al k-ésimo vecino más cercano de \(\mathbf{x}\).

Esta transformación suaviza la estructura de densidad y hace que los grupos emerjan de forma más estable. HDBSCAN no requiere especificar \(\varepsilon\) directamente, solo \(\text{minPts}\), y produce grupos de densidad variable.

try:
    import hdbscan
    from sklearn.datasets import make_moons

    X, _ = make_moons(n_samples=300, noise=0.05, random_state=42)

    hdb = hdbscan.HDBSCAN(min_cluster_size=15, min_samples=5)
    labels = hdb.fit_predict(X)

    n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
    n_noise = (labels == -1).sum()
    print(f"HDBSCAN — Grupos: {n_clusters}, Ruido: {n_noise}")
except ImportError:
    print("Instalar hdbscan: pip install hdbscan")
    from sklearn.cluster import HDBSCAN
    from sklearn.datasets import make_moons

    X, _ = make_moons(n_samples=300, noise=0.05, random_state=42)
    hdb = HDBSCAN(min_cluster_size=15, min_samples=5)
    labels = hdb.fit_predict(X)
    n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
    n_noise = (labels == -1).sum()
    print(f"HDBSCAN (sklearn) — Grupos: {n_clusters}, Ruido: {n_noise}")

Instalar hdbscan: pip install hdbscan
HDBSCAN (sklearn) — Grupos: 2, Ruido: 0

7 Aplicaciones

DBSCAN y HDBSCAN son especialmente útiles en:

• Datos geoespaciales: identificar zonas de alta concentración de eventos (crímenes, ventas, accidentes) sin asumir formas de grupos predeterminadas.
• Detección de anomalías: los puntos clasificados como ruido son candidatos naturales a anomalías.
• Análisis de imágenes: segmentar regiones de una imagen con criterios de similitud local.
• Bioinformática: identificar grupos de células con comportamiento similar en datos de citometría de flujo o RNA-seq.
• Redes sociales: detectar comunidades en grafos convertidos en vectores de características.

Campello, Ricardo J. G. B., Davoud Moulavi, y Jörg Sander. 2013. «Density-based clustering based on hierarchical density estimates». Advances in Knowledge Discovery and Data Mining, Lecture Notes en Computer Science, vol. 7819: 160-72.

Ester, Martin, Hans-Peter Kriegel, Jörg Sander, y Xiaowei Xu. 1996. «A density-based algorithm for discovering clusters in large spatial databases with noise». Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, 226-31.