69  Clustering jerárquico

El clustering jerárquico construye una jerarquía anidada de agrupaciones en vez de producir una única partición. Esta jerarquía se representa como un árbol binario llamado dendrograma, en el que las hojas son las observaciones individuales y la raíz es un único grupo que contiene a todas. El analista puede cortar el dendrograma a cualquier altura para obtener una partición con el número de grupos deseado.

Esta propiedad hace que el clustering jerárquico sea especialmente útil cuando no se conoce de antemano el número de grupos, o cuando se desea explorar estructuras a distintos niveles de granularidad. Además, el dendrograma proporciona una representación visual rica de la estructura de los datos que facilita la interpretación.

Existen dos enfoques principales: el método aglomerativo, que comienza con cada observación como su propio grupo y va fusionando los más similares; y el método divisivo, que parte de un único grupo y lo va partiendo recursivamente. El método aglomerativo es más común en la práctica y está mejor estudiado teóricamente (Hastie et al. 2009; Aggarwal y Reddy 2013).

1 Método aglomerativo

El algoritmo aglomerativo genérico opera sobre la matriz de distancias entre grupos.

Algoritmo aglomerativo.

Entrada: observaciones \(\mathbf{x}_1,\dots,\mathbf{x}_n\), función de enlace \(d\).

1. Inicializar \(n\) grupos \(C_i=\{\mathbf{x}_i\}\) para \(i=1,\dots,n\).
2. Calcular la matriz de distancias \(D\) de tamaño \(n\times n\) con \(D_{ij}=d(\mathbf{x}_i,\mathbf{x}_j)\).
3. Repetir hasta que quede un solo grupo:
   1. Encontrar el par \((i,j)\) con \(D_{ij}\) mínima.
   2. Fusionar \(C_i\) y \(C_j\) en un nuevo grupo \(C_{ij}\).
   3. Actualizar \(D\) con las distancias del nuevo grupo a todos los demás.
4. Registrar la secuencia de fusiones y sus alturas.

Salida: dendrograma con todas las fusiones.

La diferencia entre las variantes del método aglomerativo está en cómo se define la distancia \(d\) entre grupos —el criterio de enlace.

2 Criterios de enlace

El criterio de enlace determina la distancia entre dos grupos como función de las distancias entre sus elementos. Los criterios más usados son los siguientes.

Enlace simple (single linkage). La distancia entre dos grupos es la distancia mínima entre cualquier par de observaciones, una de cada grupo: \[ d_{\text{simple}}(C_i,C_j) = \min_{\mathbf{x}\in C_i,\mathbf{y}\in C_j} d(\mathbf{x},\mathbf{y}). \tag{1}\]

Enlace completo (complete linkage). La distancia entre dos grupos es la distancia máxima entre cualquier par de observaciones, una de cada grupo: \[ d_{\text{completo}}(C_i,C_j) = \max_{\mathbf{x}\in C_i,\mathbf{y}\in C_j} d(\mathbf{x},\mathbf{y}). \tag{2}\]

Enlace promedio (average linkage / UPGMA). La distancia entre dos grupos es el promedio de todas las distancias por pares: \[ d_{\text{prom}}(C_i,C_j) = \frac{1}{|C_i||C_j|}\sum_{\mathbf{x}\in C_i}\sum_{\mathbf{y}\in C_j}d(\mathbf{x},\mathbf{y}). \tag{3}\]

Enlace de Ward. Fusiona los dos grupos cuya unión produce el menor incremento en la suma de cuadrados intra-grupo (Ward 1963): \[ d_{\text{Ward}}(C_i,C_j) = \frac{|C_i||C_j|}{|C_i|+|C_j|}\|\boldsymbol{\mu}_i-\boldsymbol{\mu}_j\|^2, \tag{4}\] donde \(\boldsymbol{\mu}_i\) y \(\boldsymbol{\mu}_j\) son los centroides de \(C_i\) y \(C_j\).

El enlace simple tiende a producir dendrogramas con efecto de encadenamiento: grupos alargados en los que se van añadiendo puntos uno por uno. El enlace completo produce grupos más compactos pero puede ser sensible a outliers. El enlace de Ward minimiza la varianza intra-grupo en cada fusión, por lo que tiende a producir grupos de tamaño parecido y es el más usado en la práctica.

Clustering jerárquico — dendrograma interactivo
Selecciona el criterio de enlace y mueve el umbral de corte para ver los grupos resultantes

Enlace: Ward Completo Simple Promedio Umbral = 1.8

3 El dendrograma

El dendrograma es una representación en árbol de la historia de fusiones. En el eje vertical se grafica la distancia (o altura) a la que se realiza cada fusión; en el eje horizontal se ubican las observaciones individuales. Una línea horizontal a altura \(h\) divide el dendrograma en los grupos que existían en ese momento.

Para extraer un número de grupos específico se corta el dendrograma con una línea horizontal. El número de ramas que esa línea intersecta es el número de grupos resultantes. La altura del corte puede elegirse visualmente buscando el mayor salto vertical en el dendrograma, lo que corresponde a fusiones que unen grupos bien separados.

4 Correlación cofenética

La correlación cofenética mide qué tan fielmente el dendrograma representa las distancias originales. La distancia cofenética entre dos puntos \(\mathbf{x}_i\) y \(\mathbf{x}_j\) es la altura a la que se fusionan por primera vez en el dendrograma.

Definición. La correlación cofenética \(r_c\) es la correlación de Pearson entre la matriz de distancias originales y la matriz de distancias cofenéticas: \[ r_c = \text{corr}(d_{ij}, c_{ij}), \tag{5}\] donde \(d_{ij}\) es la distancia original y \(c_{ij}\) es la distancia cofenética entre \(\mathbf{x}_i\) y \(\mathbf{x}_j\).

Un valor de \(r_c\) cercano a 1 indica que el dendrograma preserva bien la estructura de distancias. El enlace promedio suele producir los mayores valores de correlación cofenética.

import numpy as np
from sklearn.datasets import make_blobs
from scipy.cluster.hierarchy import linkage, dendrogram, cophenet
from scipy.spatial.distance import pdist

X, y_true = make_blobs(n_samples=80, centers=3, cluster_std=0.8, random_state=42)

for method in ["single", "complete", "average", "ward"]:
    Z = linkage(X, method=method)
    c, _ = cophenet(Z, pdist(X))
    print(f"{method:10s}  r_cofenética = {c:.4f}")

single      r_cofenética = 0.9833
complete    r_cofenética = 0.9838
average     r_cofenética = 0.9849
ward        r_cofenética = 0.9842

import matplotlib.pyplot as plt
from scipy.cluster.hierarchy import linkage, dendrogram, fcluster
import numpy as np
from sklearn.datasets import make_blobs

X, _ = make_blobs(n_samples=80, centers=4, cluster_std=0.7, random_state=0)

Z = linkage(X, method="ward")

fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(12, 4))

dendrogram(Z, ax=ax1, truncate_mode="lastp", p=20, leaf_rotation=90,
           color_threshold=0.7 * max(Z[:, 2]))
ax1.set_title("Dendrograma (Ward)")
ax1.set_xlabel("Muestra o grupo")
ax1.set_ylabel("Distancia")

labels = fcluster(Z, t=4, criterion="maxclust")
ax2.scatter(X[:, 0], X[:, 1], c=labels, cmap="tab10", s=30, edgecolors="white", linewidths=0.5)
ax2.set_title("Partición con k=4 grupos")
plt.tight_layout()
plt.show()

5 Complejidad y escalabilidad

El algoritmo aglomerativo ingenuo requiere \(O(n^2)\) espacio para la matriz de distancias y \(O(n^3)\) tiempo para las \(n-1\) fusiones, ya que en cada paso debe recalcular las distancias entre el nuevo grupo y los demás. Para enlace simple y completo existen algoritmos como SLINK y CLINK con complejidad \(O(n^2)\) en tiempo y \(O(n)\) en espacio.

Para conjuntos de datos grandes (\(n > 10\,000\)), el clustering jerárquico estándar se vuelve poco práctico. Algunas alternativas son:

• BIRCH: construye un resumen compacto de los datos (CF-tree) y luego aplica clustering jerárquico sobre los resúmenes.
• Clustering jerárquico aproximado: usando índices de vecinos más cercanos aproximados para reducir el número de comparaciones.
• Mini-batch clustering: submuestrear el conjunto de datos y extrapolar la estructura jerárquica.

from sklearn.datasets import make_blobs
from sklearn.cluster import AgglomerativeClustering
from sklearn.metrics import silhouette_score
import numpy as np

X, y_true = make_blobs(n_samples=300, centers=4, cluster_std=0.8, random_state=0)

for linkage in ["ward", "complete", "average", "single"]:
    model = AgglomerativeClustering(n_clusters=4, linkage=linkage)
    labels = model.fit_predict(X)
    sil = silhouette_score(X, labels)
    print(f"{linkage:10s}  silueta = {sil:.4f}")

ward        silueta = 0.5749
complete    silueta = 0.5780
average     silueta = 0.5646
single      silueta = -0.0659

6 Aplicaciones del clustering jerárquico

El clustering jerárquico se usa extensamente en bioinformática para agrupar genes o muestras en experimentos de expresión génica, donde el dendrograma permite visualizar tanto la agrupación de genes similares como su grado de similitud a distintas escalas. En análisis de texto, se usa para construir taxonomías temáticas. En finanzas, para clasificar activos con comportamientos similares.

Una ventaja clave sobre K-Means es que no requiere especificar el número de grupos de antemano. El dendrograma muestra de forma explícita las estructuras a distintos niveles, lo que facilita la toma de decisiones sobre la granularidad apropiada para el problema.

Aggarwal, Charu C., y Chandan K. Reddy. 2013. Data Clustering: Algorithms and Applications. CRC Press.

Hastie, Trevor, Robert Tibshirani, y Jerome Friedman. 2009. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. 2.ª ed. Springer Series en Statistics. Springer. https://doi.org/10.1007/978-0-387-84858-7.

Ward, Joe H. 1963. «Hierarchical grouping to optimize an objective function». Journal of the American Statistical Association 58 (301): 236-44.