Capítulo 29 de 37 · intermedio

Clustering con K-means

De qué trata este capítulo

Todos los modelos anteriores venían con hoja de respuestas. Los datos traían una columna de etiquetas, entrenábamos para acertarle y nos calificábamos según qué tan seguido lo lográbamos. Este capítulo se lleva la hoja de respuestas. Aquí tienes 150 puntos en un plano y nada más: sin clases, sin verdad, puras coordenadas. La chamba es encontrar los grupos que ya están ahí, sin que nadie te diga nunca qué es un grupo.

Eso es clustering, y k-means es el primero al que todo mundo le tira. La idea cabe en una frase: adivina dónde están los centros de los clusters, asigna cada punto a su centro más cercano, mueve cada centro al promedio de los puntos que lo eligieron, y repite hasta que nada se mueva. Lo construimos a mano en NumPy, una función a la vez, luego dejamos que scikit-learn arme lo mismo y vemos cómo los dos aterrizan en la respuesta idéntica. Y como todo el algoritmo son puros puntos y centros deslizándose por un plano, podemos verlo pasar: los centroides arrancan regados sobre puntos aleatorios y caminan, cuadro por cuadro, hasta el corazón de cada mancha.

Los datos son cuatro blobs bien separados de make_blobs. Sí tenemos los ids reales de cada blob, pero solo para calificar el resultado hasta el final. k-means nunca los ve. Esa es la línea de la que realmente trata este capítulo: la primera vez en el curso que el modelo aprende estructura sin que nadie sostenga la respuesta.

Un poco de historia

La receta es más vieja que el nombre. En 1956 el matemático polaco Hugo Steinhaus escribió el problema de partir un cuerpo en pedazos que minimicen la distancia de cada punto al centro de su pedazo — el objetivo de k-means, en francés, sin computadora donde correrlo. Un año después, en 1957, Stuart Lloyd en Bell Labs describió exactamente la iteración de asignar-y-promediar que usamos hoy, como una forma de cuantizar señales para modulación por codificación de pulsos. Su escrito circuló internamente y no se publicó formalmente hasta 1982, que es la razón por la que verás al algoritmo llamado "algoritmo de Lloyd" y fechado en dos décadas distintas según quién lo esté citando.

Edward Forgy propuso esencialmente el mismo método en 1965, así que el esquema crudo a veces también carga su nombre. La etiqueta que se quedó vino de James MacQueen, quien en 1967 acuñó el término "k-means" y lo planteó como el procedimiento que enseñamos ahora. Durante treinta años corrió con el seeding que le dieras, y un mal seeding podía arruinarlo — hasta 2007, cuando David Arthur y Sergei Vassilvitskii agregaron k-means++, una manera más lista de colocar los centros iniciales que volvió todo lo suficientemente robusto como para ser un default sensato. Esa es la versión que trae scikit-learn, y la versión hacia la que construimos aquí.

La intuición

Mira los datos sin colores encima. Tu ojo encuentra los grupos al instante: hay un montoncito arriba, otro a la derecha, otro abajo, otro a la izquierda. No calculaste nada; nada más viste densidad. k-means es una manera de hacer que una computadora haga eso mismo, y el truco es que ella tampoco ve nunca los grupos. Solo conoce dos movimientos.

Adivina k puntos centro. Luego repite en bucle: colorea cada punto según el centro que le quede más cerca, y desliza cada centro a la posición promedio de los puntos que ahora tienen su color. Ese es el algoritmo completo. Los centros persiguen la densidad. Los puntos cercanos a un centro lo jalan hacia ellos; cuando un centro se mete a un montón, más puntos lo reclaman, lo que lo aprieta más adentro, hasta que se asienta en el punto de equilibrio y se detiene. Haz eso con los k centros al mismo tiempo y se reparten para cubrir los blobs, cada uno estacionándose en medio de un grupo.

Lo único que el algoritmo no puede hacer es decidir cuántos grupos hay. Tú le pasas k. Si le atinas a k, encuentra clusters limpios; si le fallas, te va a entregar exactamente esa cantidad de todos modos, partiendo un grupo real a la mitad o fusionando dos sin quejarse. Estos son los datos crudos sobre los que va a trabajar: 150 puntos, sin etiquetas, en gris:

Cuatro blobs, y los encontraste sin que nadie te dijera que eran cuatro. Ahora hagamos que el algoritmo encuentre lo mismo.

Las matemáticas

Sean $x_1, \dots, x_N$ los puntos y $\mu_1, \dots, \mu_k$ los $k$ centros de cluster, o centroides. Asigna cada punto a su centroide más cercano; escribe $c_i$ para el índice del centroide al que pertenece el punto $i$ . La cantidad que k-means minimiza es la suma de cuadrados dentro del cluster, llamada inercia:

J = \sum_{i=1}^{N} \bigl\lVert x_i - \mu_{c_i} \bigr\rVert^{2}

Cada punto aporta la distancia al cuadrado hacia su propio centroide. Un cluster apretado aporta poco; uno flojo, mucho. El algoritmo de Lloyd empuja $J$ hacia abajo alternando dos pasos, cada uno de los cuales es el minimizador exacto de $J$ si mantienes fija la otra mitad.

El paso de asignación fija los centroides y elige el mejor cluster para cada punto — el más cercano:

c_i \;=\; \arg\min_{j \,\in\, \{1,\dots,k\}} \; \bigl\lVert x_i - \mu_j \bigr\rVert^{2}

El paso de actualización fija las asignaciones y elige el mejor centroide para cada cluster. Toma un conjunto de puntos y pregunta qué única ubicación minimiza la suma de distancias al cuadrado hacia ellos; la respuesta es su media, y por eso el paso es nada más un promedio:

\mu_j \;=\; \frac{1}{|S_j|} \sum_{i \,\in\, S_j} x_i \qquad S_j = \{\, i : c_i = j \,\}

Ambos pasos solo pueden bajar $J$ o dejarla igual, y hay una cantidad finita de formas de asignar $N$ puntos a $k$ clusters, así que el bucle tiene que parar. Esa es toda la garantía — y también todo el detalle. Converge, pero a un mínimo local de $J$ , y a cuál depende por completo de dónde arrancaron los centroides. Ese único hecho es la razón por la que el seeding se lleva su propia función más adelante.

En qué es bueno y en qué no

El lado bueno es por qué está en todos lados. Es rápido: cada iteración es una matriz de distancias y un promedio por grupo, y normalmente converge en un puño de pasadas, así que escala a datos con los que métodos más elegantes se atragantan. Es lo bastante simple para implementarlo en una tarde y lo bastante simple para explicárselo a alguien que no se dedica a esto. La salida es un centroide por cluster, que es un resumen genuino y aprovechable: el cliente promedio de cada segmento, el prototipo de cada grupo. Sobre datos que de verdad caen en blobs redondos y más o menos parejos, es difícil de superar e inútil de complicar.

El lado malo es la forma de sus suposiciones. k-means traza fronteras rectas a media distancia entre centroides y asume que todo cluster es una bola redonda de tamaño similar, porque la distancia euclidiana al cuadrado es todo lo que conoce. Dale dos franjas largas, o un grupo chico y denso junto a uno grande y disperso, o clusters con forma de medialuna, y los parte mal con total seguridad. Necesita que elijas k por adelantado, y no tiene opinión sobre si tu k sirvió de algo. Y es sensible a dónde arrancan los centroides: un seed descuidado puede asentarse en un mal mínimo local y entregarte un clustering que es estable, plausible y equivocado. Casi todas esas debilidades tienen arreglo, y la más grande, el seeding, la construimos directamente.

Los datos

Cuatro blobs gaussianos del make_blobs de scikit-learn, 150 puntos en 2-D, con una semilla aleatoria fija para que el snapshot sea estable. Dos features para poder poner todo en una página y verlo de verdad; cuatro centros separados lo suficiente como para que la respuesta correcta sea obvia para un humano, que es justo lo que quieres cuando estás checando si el algoritmo está de acuerdo. El generador también devuelve un id real de blob para cada punto. Esos los commiteamos, pero los tratamos como sobre sellado: las coordenadas entran a k-means, los ids salen solo a la hora de calificar, para calcular qué tan bien el resultado no supervisado coincidió con la estructura que de verdad estaba ahí.

Constrúyelo, una función a la vez

Siete funciones cortas. Cada una es un paso del algoritmo de Lloyd o una pieza de su contabilidad, y se apilan en el orden en que realmente las escribirías: primero el kernel de distancia, luego los dos pasos que lo usan, luego el objetivo, luego el seeding, y al final el bucle que amarra todo.

Todo descansa en un solo cálculo de distancia. Dados los puntos y los centroides actuales, queremos la distancia al cuadrado de cada punto a cada centroide de un jalón — una malla completa, sin loops:

def distances(X, centroids):
    """Squared Euclidean distance from every point to every centroid.

    X is (N, D), centroids is (k, D); the result is (N, k), where entry
    (i, j) is ||x_i - mu_j||^2. Broadcasting does the whole thing at once —
    no loop over points, no loop over centroids.
    """
    diff = X[:, None, :] - centroids[None, :, :]   # (N, k, D)
    return (diff ** 2).sum(axis=2)                 # (N, k)

Esa malla (N, k) es el caballito de batalla. El paso de asignación es una línea encima de ella: para cada punto, cuál centroide queda más cerca.

def assign(X, centroids):
    """Assignment step: label each point with its nearest centroid.

    Returns an (N,) array of cluster indices in [0, k). argmin over the
    distance matrix picks the closest centroid for every point at once.
    """
    return np.argmin(distances(X, centroids), axis=1)

argmin a lo largo del eje de centroides convierte la malla de distancias en una etiqueta de cluster por punto. Esa es la primera mitad de una iteración de Lloyd. La segunda mitad mueve cada centroide a la media de los puntos que acaban de elegirlo:

def update(X, labels, centroids):
    """Update step: move each centroid to the mean of its assigned points.

    k is read off the current centroids. A cluster that ended up empty keeps
    its old position — there is no mean to move to — so the loop never divides
    by zero and never loses a centroid.
    """
    new = centroids.copy()
    for j in range(len(centroids)):
        pts = X[labels == j]
        if len(pts):
            new[j] = pts.mean(axis=0)
    return new

El único detalle es un cluster vacío: un centroide que ningún punto eligió no tiene media a la cual moverse. Lo dejamos donde está en lugar de dividir entre cero, lo que mantiene vivos los k centroides durante toda la corrida. Ahora el objetivo que los dos pasos minimizan calladitos, para poder verlo caer:

def inertia(X, labels, centroids):
    """Within-cluster sum of squares — the objective k-means minimizes.

    Sum over points of the squared distance to the point's OWN centroid.
    Every Lloyd iteration drives this down; when it can't fall further, the
    algorithm has converged.
    """
    d2 = distances(X, centroids)
    return float(d2[np.arange(len(X)), labels].sum())

Esa es la inercia tal cual sale de las matemáticas: saca de la malla la distancia de cada punto a su propio centroide y suma. Cada iteración debería hacer este número más chico o dejarlo plano, nunca más grande — si alguna vez sube, hay un bug.

Ahora el seeding, y aquí es donde k-means se gana o se pierde. La forma ingenua es tomar k puntos al azar y llamarlos los centroides iniciales:

def init_random(X, k, rng):
    """The naive seed: k distinct data points picked uniformly at random.

    Simple, and sometimes fine — but nothing stops it from dropping two seeds
    inside the same blob and none in another, which is exactly the bad start
    that makes k-means take longer or converge to a worse answer.
    """
    idx = rng.choice(len(X), size=k, replace=False)
    return X[idx].copy()

Funciona lo suficientemente seguido como para ser tentador, y es lo que vamos a usar para la animación precisamente porque es un poco torpe: les da a los centroides de dónde caminar. Pero puede soltar dos seeds dentro de un mismo blob y ninguno en otro, y de ahí k-means converge felizmente a una respuesta equivocada pero estable. k-means++ lo arregla separando los seeds a propósito: el primer centro al azar, y luego cada centro siguiente elegido con probabilidad proporcional a su distancia al cuadrado de los centros ya escogidos, así que las regiones lejanas tienen mucha más chance de recibir uno:

def init_centroids(X, k, rng):
    """k-means++ seeding: spread the first centroids out on purpose.

    Pick the first centroid uniformly at random, then pick each next one with
    probability proportional to its squared distance from the centroids
    already chosen. Far-apart seeds are what save k-means from the bad local
    minima a naive random start can fall into.
    """
    first = int(rng.integers(len(X)))
    centroids = [X[first]]
    for _ in range(1, k):
        d2 = distances(X, np.array(centroids)).min(axis=1)
        probs = d2 / d2.sum()
        nxt = int(rng.choice(len(X), p=probs))
        centroids.append(X[nxt])
    return np.array(centroids)

Ese único cambio es la diferencia entre un algoritmo al que tienes que estar cuidando con reinicios y uno en el que puedes confiar al primer intento. Por último, el bucle que junta todo: asignar, actualizar, repetir hasta que las etiquetas dejen de cambiar:

def kmeans(X, k, rng, max_iter=100, init=init_centroids):
    """Lloyd's algorithm: assign, update, repeat until labels stop changing.

    `init` chooses the seeding — k-means++ by default, or pass init_random for
    the naive version. Returns the final labels, centroids, and inertia, plus
    the full per-iteration history: a list of {centroids, labels, inertia}
    snapshots the chapter replays frame by frame so you watch the centroids move.
    """
    centroids = init(X, k, rng)
    labels = assign(X, centroids)
    history = [_snapshot(X, labels, centroids)]
    for _ in range(max_iter):
        centroids = update(X, labels, centroids)   # move to the means
        new_labels = assign(X, centroids)          # re-assign to new centroids
        history.append(_snapshot(X, new_labels, centroids))
        if np.array_equal(new_labels, labels):     # nothing moved — done
            labels = new_labels
            break
        labels = new_labels
    return labels, centroids, inertia(X, labels, centroids), history

Guarda un snapshot en cada iteración — centroides, etiquetas, inercia — que es lo que la animación de abajo reproduce. La convergencia es la prueba más simple posible: si una pasada de asignación regresa exactamente las etiquetas que ya teníamos, ningún punto puede moverse otra vez, y terminamos.

Míralo trabajar

Esta es toda la razón por la que vale la pena usar datos en 2-D. Abajo hay una corrida real de la función kmeans de arriba, un cuadro por iteración, inicializada desde puntos aleatorios para que la veas trabajar en vez de brincar directo a la respuesta. Los puntos están coloreados por su cluster actual. Los cuatro rombos son los centroides — obsérvalos moverse. El anillo punteado alrededor de cada cluster llega hasta su punto asignado más lejano, así que puedes ver cómo el territorio de cada grupo se infla y se encoge conforme las fronteras se mueven. El panel de abajo sigue la inercia, el número que todo esto está empujando hacia abajo.

Dale play. Los centroides arrancan regados sobre puntos arbitrarios y el coloreado es un desastre. Luego cada cuadro hace un asignar-y-promediar, y ves a los rombos marchar hacia el centro de los blobs mientras los anillos se cierran apretados a su alrededor.

Fíjate sobre todo en los primeros dos cuadros: ahí es donde pasa casi todo el trabajo. La inercia cae de unos 7,081 en el arranque aleatorio a más o menos 2,456 después del primer movimiento, y sigue bajando: un acantilado empinado que se aplana rápido. Para el último cuadro ningún punto cambia de cluster, los rombos se detuvieron, y la corrida convergió en seis iteraciones a una inercia de 342. Ese aplanamiento es toda la historia del algoritmo de Lloyd: progreso enorme en el primer paso o dos, luego ajuste fino, luego alto total. Reinicia y córrelo otra vez — como el seeding aquí es aleatorio, pero los blobs están limpios, camina a los mismos cuatro grupos cada vez.

Esa última parte es suerte de los datos, no una garantía. Con datos más desordenados un seed aleatorio puede dejar varado a un centroide y congelarse en un peor mínimo local, que es el argumento a favor de k-means++ hecho visible: separa los seeds y el buen final deja de ser suerte.

La implementación completa

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

"""K-means clustering (Lloyd's algorithm), built from scratch.

No labels this time. Group unlabeled 2-D points into k clusters by alternating
two steps: assign every point to its nearest centroid, then move every centroid
to the mean of the points now assigned to it. Repeat until the assignments stop
changing. Pure NumPy — no ML library anywhere 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: distances
def distances(X, centroids):
    """Squared Euclidean distance from every point to every centroid.

    X is (N, D), centroids is (k, D); the result is (N, k), where entry
    (i, j) is ||x_i - mu_j||^2. Broadcasting does the whole thing at once —
    no loop over points, no loop over centroids.
    """
    diff = X[:, None, :] - centroids[None, :, :]   # (N, k, D)
    return (diff ** 2).sum(axis=2)                 # (N, k)
# endregion


# region: assign
def assign(X, centroids):
    """Assignment step: label each point with its nearest centroid.

    Returns an (N,) array of cluster indices in [0, k). argmin over the
    distance matrix picks the closest centroid for every point at once.
    """
    return np.argmin(distances(X, centroids), axis=1)
# endregion


# region: update
def update(X, labels, centroids):
    """Update step: move each centroid to the mean of its assigned points.

    k is read off the current centroids. A cluster that ended up empty keeps
    its old position — there is no mean to move to — so the loop never divides
    by zero and never loses a centroid.
    """
    new = centroids.copy()
    for j in range(len(centroids)):
        pts = X[labels == j]
        if len(pts):
            new[j] = pts.mean(axis=0)
    return new
# endregion


# region: inertia
def inertia(X, labels, centroids):
    """Within-cluster sum of squares — the objective k-means minimizes.

    Sum over points of the squared distance to the point's OWN centroid.
    Every Lloyd iteration drives this down; when it can't fall further, the
    algorithm has converged.
    """
    d2 = distances(X, centroids)
    return float(d2[np.arange(len(X)), labels].sum())
# endregion


# region: init_random
def init_random(X, k, rng):
    """The naive seed: k distinct data points picked uniformly at random.

    Simple, and sometimes fine — but nothing stops it from dropping two seeds
    inside the same blob and none in another, which is exactly the bad start
    that makes k-means take longer or converge to a worse answer.
    """
    idx = rng.choice(len(X), size=k, replace=False)
    return X[idx].copy()
# endregion


# region: init_centroids
def init_centroids(X, k, rng):
    """k-means++ seeding: spread the first centroids out on purpose.

    Pick the first centroid uniformly at random, then pick each next one with
    probability proportional to its squared distance from the centroids
    already chosen. Far-apart seeds are what save k-means from the bad local
    minima a naive random start can fall into.
    """
    first = int(rng.integers(len(X)))
    centroids = [X[first]]
    for _ in range(1, k):
        d2 = distances(X, np.array(centroids)).min(axis=1)
        probs = d2 / d2.sum()
        nxt = int(rng.choice(len(X), p=probs))
        centroids.append(X[nxt])
    return np.array(centroids)
# endregion


# region: kmeans
def kmeans(X, k, rng, max_iter=100, init=init_centroids):
    """Lloyd's algorithm: assign, update, repeat until labels stop changing.

    `init` chooses the seeding — k-means++ by default, or pass init_random for
    the naive version. Returns the final labels, centroids, and inertia, plus
    the full per-iteration history: a list of {centroids, labels, inertia}
    snapshots the chapter replays frame by frame so you watch the centroids move.
    """
    centroids = init(X, k, rng)
    labels = assign(X, centroids)
    history = [_snapshot(X, labels, centroids)]
    for _ in range(max_iter):
        centroids = update(X, labels, centroids)   # move to the means
        new_labels = assign(X, centroids)          # re-assign to new centroids
        history.append(_snapshot(X, new_labels, centroids))
        if np.array_equal(new_labels, labels):     # nothing moved — done
            labels = new_labels
            break
        labels = new_labels
    return labels, centroids, inertia(X, labels, centroids), history
# endregion


def _snapshot(X, labels, centroids):
    """One frame of the run: the centroids, the assignment to them, its cost."""
    return {
        "centroids": centroids.copy(),
        "labels": labels.copy(),
        "inertia": inertia(X, labels, centroids),
    }


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

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

La versión con librería

Nadie manda a producción un k-means hecho a mano, y una vez que ya lo construiste no lo necesitas. El KMeans de scikit-learn es el mismo bucle de Lloyd con las esquinas limadas: seeding k-means++ por default, varios reinicios aleatorios para que un seed con mala suerte no decida la respuesta, y un bucle interno en C. Minimiza la misma inercia, así que con datos limpios debería aterrizar donde nosotros:

def sklearn_kmeans(X, k, seed=0):
    """Cluster X into k groups with scikit-learn. Returns labels, the cluster
    centers, and the final inertia — the same three things our kmeans returns."""
    km = KMeans(n_clusters=k, init="k-means++", n_init=10, random_state=seed)
    labels = km.fit_predict(X)
    return labels, km.cluster_centers_, float(km.inertia_)

La librería también hace barata la pregunta de k. La inercia siempre baja conforme agregas clusters — más centroides, distancias más cortas, hasta llegar a un punto por cluster y cero inercia — así que no puedes simplemente minimizarla. Lo que buscas en cambio es el codo: la k donde la curva deja de caer en picada y se pone casi plana, el punto de rendimientos decrecientes. Ajusta KMeans sobre un rango de k y grafica cada inercia convergida:

def elbow(X, ks):
    """Fit KMeans for a range of k and record each converged inertia.

    Inertia only ever falls as k grows, so you don't pick the minimum — you
    look for the 'elbow', the k where the curve stops dropping steeply and
    adding clusters buys you almost nothing.
    """
    out = []
    for k in ks:
        km = KMeans(n_clusters=k, n_init=10, random_state=0)
        km.fit(X)
        out.append((int(k), float(km.inertia_)))
    return out

El doblez está tan limpio como se pone esto en la vida real. La inercia se cae de un acantilado, de 7,881 en k=1 a 921.8 en k=3, baja una vez más a 342.2 en k=4, y de ahí la curva se pone casi plana — k=5 solo te lleva hasta 301.7, y cada cluster después de ese rebana todavía menos. El punto naranja en k=4 es el codo, y es la respuesta correcta porque construimos los datos con cuatro blobs. En la vida real el codo suele estar más borroso que esto y te apoyas en él como pista, no como veredicto.

Hecho a mano contra librería

Mismos datos, misma k, ambos corridos hasta converger: nuestro k-means++ desde cero contra el KMeans de sklearn. Las barras son la inercia final:

Son idénticos: 342.2 y 342.2. Eso no es coincidencia y tampoco es un empate que necesitó redondeo para disimularse; sobre cuatro blobs limpios y bien separados hay un solo clustering obvio, su inercia es 342.2, y cualquier implementación correcta que alcance el óptimo global aterriza ahí. Nuestro bucle escrito a mano lo encontró en dos iteraciones desde un seed de k-means++; sklearn también lo encontró. Cuando la respuesta es así de inequívoca, el valor de la librería no es un mejor número, son los reinicios de n_init y el bucle en C que te mantienen en ese número cuando el clustering correcto no está a la vista.

Ahora abre el sobre sellado. Nunca entrenamos con los ids reales de los blobs, pero podemos calificar contra ellos con el índice de Rand ajustado, que puntúa qué tanto concuerdan dos etiquetados después de corregir por azar — 1.0 es coincidencia perfecta, 0 es aleatorio. Tanto nuestro clustering como el de sklearn sacan 1.0: cada punto cayó en el grupo del que realmente fue generado. El algoritmo no supervisado recuperó la estructura exacta con la que se construyeron los datos, sin que nunca le mostraran una sola etiqueta.

Conclusiones

Este es el capítulo donde el curso cruza una línea. Todo lo anterior era supervisado: una columna de etiquetas, un objetivo que igualar, un accuracy que reportar. k-means no tiene nada de eso. Aprende la forma de los datos a partir de los datos, y la única razón por la que aquí pudimos ponerle un número es que resultó que conocíamos la verdad y la mantuvimos escondida hasta el final. Con datos reales sin etiquetar no tienes ese sobre. Tienes inercia, un codo y tu propio criterio sobre si los grupos que encontró significan algo. El clustering mueve la pregunta difícil de "¿el modelo está bien?" a "¿el modelo sirve?", y ninguna métrica te responde eso.

Tírale primero a k-means cuando necesites segmentar algo y creas que los grupos son más o menos redondos y más o menos balanceados: es rápido, es simple, te da un centroide utilizable por cluster, y con seeding k-means++ es lo bastante confiable para creerle a la primera. Vete más allá cuando esas suposiciones se rompan: cuando no sepas k y no te quieras comprometer con una, cuando los clusters se aniden unos dentro de otros, o cuando un cluster sea una racha larga o una medialuna en lugar de una bola. Los siguientes dos capítulos son exactamente esas salidas. El clustering jerárquico se niega a fijar k por adelantado y te entrega el árbol completo de agrupamientos para que lo cortes donde quieras. Las mezclas gaussianas conservan los centroides pero dejan que los clusters sean elipses estiradas e inclinadas con bordes suaves, así que un punto puede pertenecer parcialmente a dos grupos a la vez. Ambos son k-means con una suposición relajada — que es la mejor razón posible para haber construido k-means a mano primero.