Laboratorio de agrupamiento (clustering)
Agrupa puntos en tu navegador con k-medias, DBSCAN y agrupamiento jerárquico. Mira cómo se mueven los centroides y compara clústeres con la silueta.
Acerca de
El agrupamiento (clustering) consiste en encontrar grupos en datos que nadie etiquetó. No hay hoja de respuestas: el algoritmo solo ve coordenadas y tiene que decidir qué puntos "van juntos" únicamente a partir de la distancia. Por eso, elegir un algoritmo es elegir qué es un clúster.
Este laboratorio ejecuta tres respuestas clásicas a esa pregunta sobre los mismos puntos, de verdad, en tu navegador:
- K-medias (k-means) dice que un clúster es un conjunto de puntos más cercanos a un centro que a cualquier otro. Es rápido y sencillo, pero supone grupos redondos y de tamaño parecido.
- DBSCAN dice que un clúster es una región densa, separada de otras regiones densas por espacio poco poblado. Encuentra formas irregulares y etiqueta los valores atípicos como ruido, pero le cuesta cuando la densidad varía.
- El agrupamiento jerárquico (aglomerativo) no se compromete con una sola respuesta. Fusiona una y otra vez los dos grupos más cercanos y registra un árbol (un dendrograma) que puedes cortar a cualquier altura.
Haz clic en el lienzo para añadir puntos, Mayús + clic para soltar una pequeña ráfaga y Alt + clic (Opción + clic) para quitar uno. Luego compara cómo reacciona cada algoritmo. Prueba las lunas y los anillos con k-medias: falla de una forma muy instructiva.
Entre sus usos reales están la segmentación de clientes, la agrupación de noticias, la compresión de paletas de color (k-medias sobre los colores de los píxeles), la detección de zonas calientes en datos de ubicación y, cada vez más, la organización de los embeddings de texto que producen los modelos de lenguaje. Consulta la lección de aprendizaje no supervisado para ver el panorama general y el Embedding Explorer para ver clústeres en el espacio del significado (ambos en inglés).
Cómo funciona
Los tres algoritmos usan la distancia euclidiana simple entre puntos. Lo que cambia es la regla para agrupar.
| Algoritmo | Tú eliges | Formas que encuentra | Valores atípicos | Costo (n puntos) |
|---|---|---|---|---|
| K-medias | k | Convexas, más o menos redondas | Se fuerzan a un clúster | O(n·k) por iteración |
| DBSCAN | eps, minPts | Cualquier forma densa y conectada | Se etiquetan como ruido | O(n²) aquí, O(n log n) con un índice |
| Aglomerativo | enlace, dónde cortar | Depende del enlace | Se fusionan al final (enlace simple) | O(n²) de memoria, de O(n²) a O(n³) de tiempo |
Qué muestra el lienzo
- Los colores de los puntos son los ids de clúster, tomados de la paleta viridis. Los puntos grises aún no están asignados.
- K-medias: las regiones teñidas son las celdas de Voronoi de los centroides (cada ubicación se colorea según su centroide más cercano). Las líneas discontinuas son las trayectorias de los centroides.
- DBSCAN: los puntos rellenos son puntos núcleo, los anillos huecos son puntos frontera y las cruces son ruido. Pasa el cursor sobre un punto para ver su bola eps y sus vecinos.
- Jerárquico: los colores salen de cortar el dendrograma por debajo de la línea amarilla. Haz clic en el dendrograma para mover el corte.
Todo se calcula de forma exacta: sin respuestas precalculadas ni animaciones simuladas. Los conjuntos de datos se generan con un generador de números aleatorios con semilla, así que puedes reproducir una ejecución; pulsa N para obtener una muestra nueva.
K-medias
K-medias busca k centros que minimicen la inercia: la suma de las distancias al cuadrado de cada punto a su centro más cercano. Encontrar el mínimo global es NP-difícil, así que en la práctica todos usan la heurística de Lloyd (Lloyd, 1982), que alterna dos pasos:
- Asignar: dale a cada punto el color de su centroide más cercano.
- Actualizar: mueve cada centroide a la media de los puntos que tiene asignados.
Cada paso solo puede bajar (o mantener) la inercia, y hay un número finito de asignaciones, así que el ciclo siempre termina. Pero se detiene en un mínimo local que depende de dónde empezaron los centroides. Avanza paso a paso en una ejecución y observa la gráfica de inercia: cae rápido y luego se aplana.
Por qué importa la inicialización
La inicialización aleatoria elige k puntos de datos al azar. Dos centroides pueden caer en la misma mancha y no separarse nunca. k-means++ (Arthur y Vassilvitskii, 2007) elige el primer centro al azar y cada uno de los siguientes con probabilidad proporcional a su distancia al cuadrado al centro más cercano ya elegido. Así los centros quedan repartidos y la inercia esperada queda dentro de un factor O(log k) del óptimo. Es la opción predeterminada en scikit-learn. Compara ambas en el conjunto de manchas varias veces con R.
Dónde falla
Las celdas de Voronoi son convexas, así que k-medias solo puede dividir el plano con fronteras rectas. No puede seguir lunas ni anillos, y en manchas estiradas (anisotrópicas) prefiere cortarlas de través. Tampoco tiene noción de valores atípicos: cada punto tira de algún centroide. En este laboratorio, un clúster vacío conserva su centroide anterior; las bibliotecas suelen reubicarlo en un punto lejano.
DBSCAN
DBSCAN (Ester, Kriegel, Sander y Xu, 1996) define los clústeres por densidad. Con dos ajustes, un radio eps y un conteo minPts, cada punto recibe un papel:
- Núcleo: hay al menos minPts puntos (incluido él mismo) a una distancia de eps o menos.
- Frontera: no es núcleo, pero está a una distancia de eps o menos de un punto núcleo.
- Ruido: ni lo uno ni lo otro. Se reportan como valores atípicos en lugar de forzarlos a un grupo.
Un clúster es todo lo que se alcanza saltando de punto núcleo en punto núcleo con pasos de eps como máximo, más los puntos frontera que cuelgan de ellos. Pulsa Animar para ver ese relleno por inundación: empieza en un punto núcleo no visitado y crece hasta que no quedan puntos alcanzables; luego empieza el siguiente clúster.
Cómo elegir eps
El artículo original sugiere la gráfica de k-distancias que aparece bajo el lienzo: para cada punto, la distancia a su vecino más cercano número (minPts menos 1), ordenada. Los puntos dentro de los clústeres tienen valores pequeños; el ruido, valores grandes. Un buen eps está cerca del codo, donde la curva se dispara. Haz clic en la gráfica para fijar eps ahí. Una regla práctica común para minPts es el doble del número de dimensiones (Schubert et al., 2017), o sea 4 en 2D, y más para datos ruidosos.
Dónde falla
Un único eps para todo el conjunto de datos implica que no se pueden encontrar a la vez clústeres de densidades muy distintas: un radio lo bastante grande para el clúster disperso fusiona los densos. HDBSCAN extiende la idea probando, en efecto, todos los valores de eps y quedándose con los clústeres más estables. Los puntos frontera que tocan dos clústeres se asignan al que los alcance primero.
Jerárquico
El agrupamiento aglomerativo empieza con cada punto como su propio clúster y fusiona repetidamente los dos clústeres más cercanos hasta que solo queda uno. El registro de fusiones, con la distancia a la que ocurrió cada una, es un dendrograma. Cortarlo con una línea horizontal da un agrupamiento plano: cada rama por debajo de la línea es un clúster.
"Los clústeres más cercanos" necesita una definición. Eso es el enlace (linkage):
- Simple: distancia entre los dos miembros más cercanos. Sigue cadenas, así que recupera anillos y lunas, pero un solo puente de puntos puede pegar dos clústeres.
- Completo: distancia entre los dos miembros más lejanos. Produce clústeres compactos de diámetro similar.
- Promedio: distancia media entre todos los pares cruzados (UPGMA). Un punto intermedio entre los dos anteriores.
- Ward: fusiona el par que menos aumenta la varianza total dentro de los clústeres (Ward, 1963). Es el primo jerárquico de k-medias, con un gusto parecido por los clústeres redondos.
El laboratorio actualiza las distancias con la fórmula de Lance-Williams, que expresa la distancia de un clúster recién fusionado a cada uno de los demás en términos de distancias ya conocidas, así que no se recalcula nada a partir de los puntos originales. Las alturas se dibujan en escala de raíz cuadrada para que las fusiones tempranas y pequeñas sigan siendo visibles.
Evaluar clústeres
Sin etiquetas, ¿cómo sabes si un agrupamiento es bueno? No puedes saberlo del todo. Pero dos medidas internas ayudan.
La inercia y el codo
La inercia siempre baja a medida que k crece (con k igual a n vale cero). Grafícala contra k y busca el "codo", donde los clústeres adicionales dejan de compensar. La gráfica bajo el lienzo ejecuta k-means++ hasta converger para k = 1 a 8 (el mejor de cuatro reinicios) sobre tus puntos actuales. Haz clic en un k para usarlo. Los codos suelen ser ambiguos, y por eso existe la segunda medida.
La silueta
Para cada punto, sea a su distancia media a los demás miembros de su propio clúster y b su distancia media a los miembros del clúster más cercano. Su silueta es (b - a) / max(a, b) (Rousseeuw, 1987). Cerca de 1 significa que está bien dentro de un clúster claro; cerca de 0, que está sobre una frontera; negativa, que probablemente está en el clúster equivocado. El laboratorio reporta la media sobre todos los puntos agrupados (en DBSCAN se excluye el ruido). La barra amarilla de la gráfica del codo marca el k con la mejor silueta.
Ambas medidas premian las manchas redondas y bien separadas. En lunas y anillos, la respuesta "correcta" (un clúster por forma) a menudo puntúa peor que un corte de k-medias. Es una lección real: las métricas internas también codifican supuestos. Cuando tienes aunque sea unas pocas etiquetas, las medidas externas como el índice de Rand ajustado son más confiables.
Cosas para probar
- Anillos con k-medias (k = 2), luego DBSCAN y luego enlace simple. ¿Cuáles recuperan los dos anillos?
- Ruido uniforme: la gráfica del codo no tiene codo y las siluetas son mediocres para cualquier k. No hay clústeres que encontrar.
- Manchas anisotrópicas: k-medias corta las elipses de través; el enlace promedio o el simple funcionan mejor.
- Añade una ráfaga lejana con Mayús + clic y observa cómo arrastra un centroide de k-medias, mientras DBSCAN la considera ruido o un clúster nuevo.