Clustering jerárquico

Qué cubre este capítulo

k-means te obligaba a elegir k antes de decirte nada. Le pides tres clusters cuando los datos tienen cinco y aun así te va a entregar tres, partiendo grupos reales con tal de llegar al número que exigiste. Este capítulo te quita esa exigencia de encima. Construimos un clustering que nunca fija k: arma el árbol completo de agrupaciones, desde cada punto por su cuenta en la base hasta un único grupo grande en la cima, y te deja cortarlo donde la estructura te lo indique.

El método es clustering jerárquico aglomerativo, y la idea es casi ofensivamente simple: empiezas con cada punto como su propio cluster, encuentras los dos clusters más cercanos, los fusionas, y repites hasta que queda uno solo. Lo que significa "más cercano" entre dos grupos de puntos es la única decisión real que tomas —la regla de linkage— y lo cambia todo, así que implementamos tres y las hacemos seleccionables. Armamos todo en NumPy, registramos cada merge y la distancia a la que ocurrió, y usamos eso para dibujar un dendrograma: el árbol de merges, que es el verdadero resultado aquí, no un conjunto de etiquetas. Luego cortamos el árbol en k y verificamos que los clusters planos que obtenemos coincidan exactamente con los de scikit-learn.

Los datos son treinta puntos en 2-D repartidos en tres blobs bien portados — pequeños a propósito, porque un dendrograma de treinta hojas se lee y uno de diez mil es una mancha negra. Ese límite de tamaño no es un detalle. Es justo el trade-off del que trata este capítulo.

Un poco de historia

El clustering jerárquico creció en biología, no en ciencias de la computación. Quienes lo necesitaban eran taxónomos que intentaban construir el árbol de la vida a partir de mediciones: si tienes cuarenta escarabajos y una tabla con sus rasgos, ¿cuáles dos se parecen más y qué grupos de escarabajos forman un género? En 1963 Robert Sokal y Peter Sneath publicaron Principles of Numerical Taxonomy, el libro que sostuvo que podías clasificar organismos por algoritmo en lugar de por criterio experto, calculando similitudes a partir de mediciones crudas y dejando que las agrupaciones salieran solas. Los dendrogramas de este capítulo son sus diagramas. Todo el encuadre —fusiona lo más parecido, dibuja el árbol, lee las ramas— viene de ese programa de meterle números a la clasificación.

Ese mismo año, 1963, Joe Ward escribió una regla de linkage distinta desde otro ángulo: en vez de fusionar los clusters más cercanos por distancia, fusiona el par cuya unión aumenta menos la varianza dentro del cluster. El método de Ward es el que más vas a ver como default en la práctica, porque tiende a producir clusters compactos y balanceados, y amarra todo el procedimiento al mismo objetivo de suma de cuadrados que k-means minimiza. La regla de single link con la que abrimos es todavía más vieja en espíritu, y se lee como el instinto del taxónomo: dos grupos están tan cerca como sus dos miembros más cercanos. Sesenta años después, el algoritmo no ha cambiado. Lo que cambió es que dejamos de dibujar los árboles a mano.

La intuición

Olvídate de los centroides. Aquí no hay, ni hay k que adivinar. Pon cada punto en un cluster él solito —treinta puntos, treinta clusters— y luego haz lo único que el algoritmo sabe hacer: encontrar los dos clusters más cercanos y pegarlos en uno. Ahora tienes veintinueve clusters. Hazlo otra vez: veintiocho. Sigue así y los clusters chiquitos se fusionan en unos más grandes, los grandes se fusionan en blobs, y los blobs finalmente se fusionan en un solo cluster que contiene todo. Veintinueve merges para treinta puntos, y ya.

Nada de eso preguntó cuántos grupos hay. El algoritmo no decide: registra. Cada merge ocurrió a cierta distancia, y si anotas esas distancias en orden obtienes una historia: estos dos puntos estaban prácticamente encimados, este par de grumos estaba un poco más separado, y justo al final dos blobs grandes y bien separados fueron arrastrados uno hacia el otro a través de un hueco enorme porque ya no quedaba nada más que fusionar. Esa historia es el dendrograma, y los huecos que tiene son donde vive la estructura real. Un merge a distancia diminuta une cosas que sí van juntas; un merge a través de un salto grande fusiona dos grupos que en realidad no querían ser uno. Eliges tu número de clusters cortando el árbol debajo de los saltos grandes, después de haberlos visto, en vez de adivinar antes de empezar.

Aquí están los datos crudos: treinta puntos, sin etiquetas, en gris, tres blobs que tu ojo encuentra sin ayuda:

Las matemáticas

La única cantidad que el algoritmo necesita es una distancia entre dos clusters, y cada cluster no es más que el conjunto de puntos originales que contiene. Escribe la distancia entre puntos como $\lVert x_a - x_b \rVert$, la distancia euclidiana común y corriente entre los puntos $a$ y $b$. Para dos clusters $A$ y $B$, la regla de linkage dice cómo convertir todas las distancias punto a punto entre ellos en un solo número.

El single linkage toma el par más cercano: la menor distancia entre cualquier punto de $A$ y cualquier punto de $B$:

El complete linkage toma en cambio el par más lejano, así que dos clusters cuentan como cercanos solo si hasta sus miembros más distantes están cerca:

El average linkage parte la diferencia y toma la media sobre todos los pares entre clusters, donde $|A|$ y $|B|$ son el número de puntos en cada cluster:

Esas tres fórmulas son toda la personalidad del algoritmo. El single linkage sigue cadenas de vecinos cercanos y puede ensartar grupos separados a través de un puente de puntos; el complete linkage exige bolitas apretadas y puede partir en dos un cluster alargado; el average queda en medio y suele ser el primer intento seguro, por eso es el que ponemos al frente. Una vez que elegiste una regla, el procedimiento es fijo: en cada paso fusiona el par $(A, B)$ con la menor $d(A, B)$, registra la distancia como la altura del merge, y repite. Aquí no se está minimizando ningún objetivo como k-means minimiza la inercia: el árbol es simplemente la transcripción de una secuencia greedy de merges entre los más cercanos.

En qué es bueno y en qué no

Lo atractivo es que responde una pregunta que k-means ni siquiera puede escuchar: ¿cuántos clusters hay? Tú no se lo dices: construyes el árbol completo una vez y lees la respuesta en las alturas de los merges, cortando debajo del hueco que se vea real. Obtienes toda la estructura anidada de regalo, así que puedes ver que estos dos subgrupos viven dentro de aquel grupo más grande, lo cual importa cuando lo que estás agrupando de verdad tiene una jerarquía: taxonomías, temas de documentos, familias de genes. Es determinista: mismos datos, mismo linkage, mismo árbol, en cada corrida, sin seed que cuidar ni reinicio aleatorio al cual encomendarte. Y con single linkage puede trazar clusters largos, delgados y nada redondos que k-means partiría de tajo, porque solo le importan los vecinos cercanos, no la distancia a un centro.

El problema es que no escala, punto. Necesitas las distancias entre todos los pares de puntos, que es una matriz de $n \times n$ —memoria cuadrática antes de haber fusionado nada— y el algoritmo directo escanea los pares vivos en cada uno de los n−1 pasos, lo que te deja alrededor de $O(n^3)$ en tiempo. Con miles de puntos ya es lento; con millones es inviable, y k-means, lineal en el número de puntos, gana por default. También es greedy y comprometido: un merge, una vez hecho, nunca se revisa, así que una fusión equivocada temprano se propaga hasta la punta del árbol. Y la elección del linkage no es un detalle que puedas saltarte: single, complete y average pueden entregarte tres árboles genuinamente distintos sobre los mismos datos, así que "el clustering jerárquico dice que estos son los grupos" nunca es una oración completa si no nombras la regla.

Los datos

Tres blobs gaussianos del make_blobs de scikit-learn, treinta puntos en 2-D, diez por blob, con una semilla aleatoria fija para que la foto nunca se mueva. Pequeño a propósito: este es el único algoritmo del curso donde la visualización se degrada con el tamaño, porque un dendrograma dibuja una hoja por punto y treinta hojas son exactamente las que alcanzas a leer. Dos features para que todo quepa en una página; tres blobs lo bastante separados como para que el corte correcto le resulte obvio a un humano, que es lo que quieres cuando estás verificando si el árbol está de acuerdo. El generador también devuelve el id verdadero de blob por punto. Esos los guardamos sellados: las coordenadas construyen el árbol, los ids solo salen al final para calificar qué tan bien el corte plano recuperó la estructura que en realidad estaba ahí.

Constrúyelo, una función a la vez

Cuatro funciones. Una calcula distancias, otra convierte una regla de linkage en una distancia entre clusters, otra hace crecer el árbol completo, y otra lo corta. Se apilan en ese orden.

Todo descansa sobre las distancias por pares entre puntos, calculadas una sola vez:

def pairwise(X):
    """Euclidean distance from every point to every other point.

    X is (N, D); the result is an (N, N) matrix where entry (i, j) is
    ||x_i - x_j||. This is computed once, up front — every linkage rule below
    is just a way of reducing a block of this matrix down to one number.
    """
    diff = X[:, None, :] - X[None, :, :]      # (N, N, D)
    return np.sqrt((diff ** 2).sum(axis=2))   # (N, N)

Esa matriz (N, N) es la materia prima. Cada regla de linkage es una forma de reducir un bloque rectangular de ella —las distancias entre los puntos de un cluster y los puntos de otro— a un solo número:

def cluster_distance(members_a, members_b, D, linkage):
    """Distance between two clusters, reduced from the point distance matrix D.

    A cluster is just a list of the original point indices it contains. Pull
    the block of D between the two member sets and collapse it to a single
    number the way the chosen linkage says to:

      single   = the closest pair of points across the two clusters (min)
      complete = the farthest pair (max)
      average  = the mean over all cross-cluster pairs

    That one choice is the whole personality of the algorithm.
    """
    block = D[np.ix_(members_a, members_b)]
    if linkage == "single":
        return float(block.min())
    if linkage == "complete":
        return float(block.max())
    if linkage == "average":
        return float(block.mean())
    raise ValueError(f"unknown linkage: {linkage}")

Single toma el mínimo del bloque, complete su máximo, average su media. Tres líneas, tres clusterings completamente distintos; al resto del código le da igual cuál elijas. Ahora el loop que hace crecer el árbol. Empieza con cada punto en su propio cluster, y luego n−1 veces escanea todos los pares de clusters vivos, encuentra el más cercano según la regla de linkage, y los fusiona:

def agglomerate(X, linkage="average"):
    """Grow the merge tree: fuse the two nearest clusters, N-1 times.

    Clusters are held in a dict id -> list of member point indices. Every point
    starts as its own cluster with id 0..N-1. At each step we scan all pairs of
    live clusters, find the closest under the linkage rule, merge them into a
    new cluster (given the next fresh id, scipy-style: N, N+1, ...), and record
    the merge.

    Returns a scipy-compatible linkage matrix Z with one row per merge —
    [id_a, id_b, height, size] — plus a `history` list, one entry per merge,
    that the chapter replays frame by frame to animate the agglomeration.
    """
    D = pairwise(X)
    n = len(X)
    clusters = {i: [i] for i in range(n)}     # id -> member point indices
    next_id = n
    Z = []
    history = []

    for _ in range(n - 1):
        # find the closest pair of live clusters under the linkage rule
        ids = list(clusters)
        best = None
        for a_pos in range(len(ids)):
            for b_pos in range(a_pos + 1, len(ids)):
                ia, ib = ids[a_pos], ids[b_pos]
                d = cluster_distance(clusters[ia], clusters[ib], D, linkage)
                if best is None or d < best[0]:
                    best = (d, ia, ib)

        height, ia, ib = best
        merged = clusters[ia] + clusters[ib]
        history.append({
            "id_a": ia, "id_b": ib, "new_id": next_id,
            "members_a": list(clusters[ia]), "members_b": list(clusters[ib]),
            "height": height, "size": len(merged),
            "labels": _labels_now(clusters, n),   # cluster id per point, pre-merge
        })
        Z.append([ia, ib, height, len(merged)])

        del clusters[ia]
        del clusters[ib]
        clusters[next_id] = merged
        next_id += 1

    return np.array(Z, dtype=float), history

Cada merge se registra dos veces: una en la matriz de linkage Z en el formato propio de scipy —[id_a, id_b, height, size], donde cada cluster nuevo recibe el siguiente id libre— y otra en una entrada más completa de history que además toma una foto de a qué cluster pertenecía cada punto justo antes del merge, que es lo que la animación reproduce. El cluster fusionado hereda los miembros de ambos hijos y un id nuevo, así que los ids suben desde n y el id del último merge es la raíz del árbol. Esta es la versión greedy y legible: memoria O(n²) para la matriz de distancias y un escaneo completo de pares en cada paso. No es así como agruparías un millón de puntos, y de eso trata el capítulo.

El árbol por sí solo no es un clustering: es todos los clusterings a la vez, uno por cada lugar donde podrías cortarlo. Para obtener etiquetas planas en una k específica, reproduce el árbol desde abajo y detente antes de tiempo:

def cut_tree(Z, n, k):
    """Cut the merge tree to get k flat clusters.

    Every row of Z is a merge; the first N-k of them are the merges that happen
    below the cut line. Replay exactly those with a union-find, and whatever
    connected components remain are the k flat clusters. Labels are remapped to
    a dense 0..k-1 so they line up with what a library returns.
    """
    parent = list(range(2 * n - 1))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for row, (a, b, _h, _s) in enumerate(Z[:n - k]):
        new = n + row
        parent[int(a)] = new
        parent[int(b)] = new

    roots = [find(i) for i in range(n)]
    order = {}
    labels = np.empty(n, dtype=int)
    for i, r in enumerate(roots):
        if r not in order:
            order[r] = len(order)
        labels[i] = order[r]
    return labels

Los primeros n−k merges son los que están debajo de la línea de corte; juega exactamente esos con un union-find y las componentes conexas que sobrevivan son tus k clusters. Corta en k=1 y obtienes todo el dataset; corta en k=n y obtienes cada punto por separado; corta en cualquier punto intermedio y lees un clustering del mismo árbol sin tener que reconstruirlo nunca.

Míralo trabajar

Por esto son treinta puntos y no treinta mil. Abajo hay una corrida real de la función agglomerate de arriba sobre los tres blobs, un merge por frame, con average linkage. El panel de arriba son los puntos, coloreados por su cluster actual: gris mientras un punto sigue siendo singleton, un color sólido en cuanto se une a algo. La línea roja punteada salta entre los dos clusters que están a punto de fusionarse en ese paso. El panel de abajo es el dendrograma construyéndose barra por barra: cada merge agrega un corchete a su propia altura, el actual en rojo, así que ves el árbol crecer desde las hojas mientras los puntos se condensan en el plano de arriba.

Dale play y observa el orden en que ocurren los merges. Las primeras fusiones son diminutas —puntos que están prácticamente encimados, uniéndose a distancia 0.19, 0.29, 0.33— y todas pasan dentro de los blobs, abajo en el dendrograma. El polvo gris se condensa en tres grumos de color bastante antes de que algo cruce entre blobs. Luego cambia el carácter. Una vez que cada blob es un solo cluster, los únicos merges que quedan son entre blobs, y ocurren a través de un hueco enorme: el último merge dentro de un blob está a distancia 1.90, y luego el árbol brinca a 5.94 para unir dos blobs y a 8.97 para tragarse el tercero. Esos dos corchetes altos hasta arriba, varados muy por encima de todo lo demás, son el algoritmo diciéndote que aquí hay tres grupos reales. Tú no elegiste tres. Viste cómo las distancias de merge lo anunciaban.

Reinicia y córrelo otra vez: es determinista, así que dibuja exactamente el mismo árbol siempre. Aquí no hay seed, ni arranque aleatorio, ni nada con lo que puedas tener suerte o mala suerte. Mismos datos, mismo linkage, misma transcripción.

La implementación completa

El archivo entero, sin librería, de arriba a abajo. Esto es exactamente lo que corrió la animación:

"""Agglomerative hierarchical clustering, built from scratch.

No k up front, no centroids. Start with every point as its own cluster, then
repeatedly fuse the two closest clusters — where "closest" is decided by a
linkage rule — until a single cluster holds everything. Record every merge and
its height (the distance the two clusters merged at) so we can draw a dendrogram
and cut the tree at any k we like. Pure NumPy; no ML library in this file.

Every function below appears in the chapter one step at a time (the
`# region:` markers are what the book's include directives pull in).
"""

import numpy as np
import pandas as pd


# region: pairwise
def pairwise(X):
    """Euclidean distance from every point to every other point.

    X is (N, D); the result is an (N, N) matrix where entry (i, j) is
    ||x_i - x_j||. This is computed once, up front — every linkage rule below
    is just a way of reducing a block of this matrix down to one number.
    """
    diff = X[:, None, :] - X[None, :, :]      # (N, N, D)
    return np.sqrt((diff ** 2).sum(axis=2))   # (N, N)
# endregion


# region: linkage_rules
def cluster_distance(members_a, members_b, D, linkage):
    """Distance between two clusters, reduced from the point distance matrix D.

    A cluster is just a list of the original point indices it contains. Pull
    the block of D between the two member sets and collapse it to a single
    number the way the chosen linkage says to:

      single   = the closest pair of points across the two clusters (min)
      complete = the farthest pair (max)
      average  = the mean over all cross-cluster pairs

    That one choice is the whole personality of the algorithm.
    """
    block = D[np.ix_(members_a, members_b)]
    if linkage == "single":
        return float(block.min())
    if linkage == "complete":
        return float(block.max())
    if linkage == "average":
        return float(block.mean())
    raise ValueError(f"unknown linkage: {linkage}")
# endregion


# region: agglomerate
def agglomerate(X, linkage="average"):
    """Grow the merge tree: fuse the two nearest clusters, N-1 times.

    Clusters are held in a dict id -> list of member point indices. Every point
    starts as its own cluster with id 0..N-1. At each step we scan all pairs of
    live clusters, find the closest under the linkage rule, merge them into a
    new cluster (given the next fresh id, scipy-style: N, N+1, ...), and record
    the merge.

    Returns a scipy-compatible linkage matrix Z with one row per merge —
    [id_a, id_b, height, size] — plus a `history` list, one entry per merge,
    that the chapter replays frame by frame to animate the agglomeration.
    """
    D = pairwise(X)
    n = len(X)
    clusters = {i: [i] for i in range(n)}     # id -> member point indices
    next_id = n
    Z = []
    history = []

    for _ in range(n - 1):
        # find the closest pair of live clusters under the linkage rule
        ids = list(clusters)
        best = None
        for a_pos in range(len(ids)):
            for b_pos in range(a_pos + 1, len(ids)):
                ia, ib = ids[a_pos], ids[b_pos]
                d = cluster_distance(clusters[ia], clusters[ib], D, linkage)
                if best is None or d < best[0]:
                    best = (d, ia, ib)

        height, ia, ib = best
        merged = clusters[ia] + clusters[ib]
        history.append({
            "id_a": ia, "id_b": ib, "new_id": next_id,
            "members_a": list(clusters[ia]), "members_b": list(clusters[ib]),
            "height": height, "size": len(merged),
            "labels": _labels_now(clusters, n),   # cluster id per point, pre-merge
        })
        Z.append([ia, ib, height, len(merged)])

        del clusters[ia]
        del clusters[ib]
        clusters[next_id] = merged
        next_id += 1

    return np.array(Z, dtype=float), history
# endregion


def _labels_now(clusters, n):
    """A cluster id per original point given the current set of live clusters."""
    lab = np.empty(n, dtype=int)
    for cid, members in clusters.items():
        for m in members:
            lab[m] = cid
    return lab.tolist()


# region: cut_tree
def cut_tree(Z, n, k):
    """Cut the merge tree to get k flat clusters.

    Every row of Z is a merge; the first N-k of them are the merges that happen
    below the cut line. Replay exactly those with a union-find, and whatever
    connected components remain are the k flat clusters. Labels are remapped to
    a dense 0..k-1 so they line up with what a library returns.
    """
    parent = list(range(2 * n - 1))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for row, (a, b, _h, _s) in enumerate(Z[:n - k]):
        new = n + row
        parent[int(a)] = new
        parent[int(b)] = new

    roots = [find(i) for i in range(n)]
    order = {}
    labels = np.empty(n, dtype=int)
    for i, r in enumerate(roots):
        if r not in order:
            order[r] = len(order)
        labels[i] = order[r]
    return labels
# endregion


def load_data(path="../data/blobs.csv"):
    """make_blobs snapshot: 30 2-D points (x, y) plus the true blob id.

    The blob column is ground truth we NEVER cluster on — agglomerate sees only
    the coordinates. It exists so we can score the flat clustering afterwards.
    """
    return pd.read_csv(path)

La versión con librería

Nadie escribe esto a mano en producción, y una vez que ya lo construiste no lo necesitas. AgglomerativeClustering de scikit-learn es el mismo merge bottom-up con un loop interno en C y la misma elección de linkage, y toma k directamente como n_clusters:

def sklearn_agglomerative(X, k, linkage="average"):
    """Cluster X into k groups with scikit-learn's agglomerative clustering.

    Same linkage rule as our from-scratch build, Euclidean metric. Returns the
    flat labels at the k-cut — the one thing the library gives you directly.
    """
    model = AgglomerativeClustering(n_clusters=k, linkage=linkage, metric="euclidean")
    return model.fit_predict(X)

Fíjate en lo que devuelve: etiquetas planas, y nada más. Esa es la librería tomando una decisión por ti: corre los merges internamente y te entrega solo el corte en la k que pediste, tirando el árbol a la basura a menos que hagas un esfuerzo extra por conservarlo. Nuestra versión devuelve el árbol completo porque el árbol es la parte interesante; la librería optimiza para el caso común en el que ya sabes k y solo quieres los grupos. Para validar nuestras alturas de merge contra una referencia confiable tomamos prestado el linkage de scipy, que produce una matriz de linkage en el mismo formato que la nuestra:

def scipy_reference(X, linkage="average"):
    """scipy's linkage matrix, used only to check our recorded merge heights.

    Same [id_a, id_b, height, size] rows our agglomerate() produces, computed by
    a battle-tested implementation. We compare the sorted merge heights against
    these to prove the from-scratch tree is the real tree.
    """
    return scipy_linkage(X, method=linkage, metric="euclidean")

No agrupamos con scipy: lo usamos solo para probar que nuestras alturas registradas son las alturas reales, ordenando ambas y comparándolas. Coinciden hasta 2.2e-16, que es el epsilon de máquina: nuestro árbol hecho desde cero es byte por byte el mismo árbol que construye scipy.

Desde cero contra la librería

Mismos datos, mismo average linkage, corte en k=3: nuestras etiquetas planas hechas desde cero contra las de scikit-learn. Como no hay inercia que comparar, la métrica honesta es el acuerdo: el adjusted Rand index, que califica qué tan bien coinciden dos etiquetados después de corregir por azar, donde 1.0 es coincidencia perfecta y 0 es aleatorio.

Las tres barras están clavadas en 1.0. Nuestro clustering y el de sklearn coinciden perfectamente, y ambos recuperan los blobs verdaderos a la perfección: cada punto cayó en el grupo del que realmente fue generado, sin que ninguna de las dos implementaciones viera jamás una etiqueta. Sobre tres blobs limpios y bien separados solo hay una forma sensata de cortar el árbol en k=3, ambos árboles son idénticos, y el corte cae en el mismo lugar. El valor de la librería aquí no es una mejor respuesta; es el loop en C que encuentra la misma respuesta sobre datos mucho más grandes que treinta puntos.

Y esta es la recompensa de construir el árbol y no nada más las etiquetas: no tenemos que confiar en el corte, lo podemos ver. Aquí está el dendrograma completo, coloreado por los tres clusters debajo del corte y con los merges entre blobs en gris por encima, y la línea punteada marcando dónde cae k=3: a la altura 3.92, tirada en el hueco vacío entre el último merge dentro de un blob en 1.90 y el primer merge entre blobs en 5.94:

Los corchetes grises altos varados hasta arriba son toda la historia: todo lo que está debajo de 1.90 es un merge dentro de un blob, todo lo que está arriba de 5.94 es un merge entre blobs, y la línea roja corta por la franja vacía entre ambos. Cualquier corte en esa franja da tres clusters. Ese hueco es lo que k-means nunca te mostró: habría tomado tu k y se habría puesto a trabajar, pero jamás te habría dicho que el tres estaba ahí, en los datos, evidente, desde el momento en que dibujaste el árbol.

Puntos clave

Échale mano al clustering jerárquico cuando no sepas k y no quieras fingir que sí, o cuando lo que estás agrupando sea genuinamente anidado y el árbol sea la respuesta que de verdad quieres: una taxonomía, una jerarquía de temas, una familia de documentos relacionados. Constrúyelo una vez, lee las alturas de los merges, corta debajo del hueco más grande. En datos chicos o medianos donde te puedas dar el lujo de la matriz de distancias $n^2$, es el primer movimiento honesto para explorar, porque te muestra la estructura antes de obligarte a comprometerte con un número.

Déjalo atrás en el momento en que el tamaño se vuelva el problema. La memoria cuadrática y el tiempo cúbico son paredes duras, no constantes que puedas ajustar para que desaparezcan, y pasando unos cuantos miles de puntos o muestreas hasta un tamaño que el árbol aguante o te regresas a k-means, que se mantiene lineal y no le importa qué tan grandes sean los datos. Y hagas lo que hagas, nombra tu linkage: single, complete y average son tres algoritmos distintos usando el mismo nombre, y el single linkage en particular va a encadenar felizmente dos clusters reales a través de un puente de puntos sueltos, así que un clustering que se ve mal muchas veces es un linkage que estaba mal para esos datos. Entre este capítulo y el anterior ya tienes los dos instintos de clustering que cubren casi todo lo que te vas a encontrar: k-means cuando sabes cuántos grupos hay y los grupos son redondos, jerárquico cuando no lo sabes y quizá no lo sean. Casi todo lo más elegante es una variación de estos dos, que es la mejor razón para haber construido los dos a mano.