Clustering k-means: el punto de partida decide lo que encuentras

k-means es el primer algoritmo de clustering que todos aprendemos, pero tiene una propiedad de la que nadie habla: encuentra una respuesta distinta dependiendo de dónde le toque empezar. Gira el control de abajo y observa cómo los mismos puntos, divididos en la misma cantidad de grupos, acaban en otro lugar.

Ejemplo resuelto — Clustering k-means: el punto de partida decide lo que encuentras

Suma de cuadrados intra-clúster	1,0989
Iteraciones para converger	2
Diferencia entre ellos	430,8%
Respuestas distintas	3 de 24
Así que este inicio es	el mejor encontrado

Estos son los valores que muestra la calculadora al abrir la página. Cambia cualquier entrada de arriba para recalcularlos.

Cargando simulación interactiva...

Lección

La teoría — Clustering k-means: el punto de partida decide lo que encuentras

k-medias busca k grupos repitiendo dos pasos hasta que nada se mueva: asigna cada punto al centro más cercano y luego desplaza cada centro a la media de lo que capturó. Lo que intenta minimizar es la suma de cuadrados intra-clúster, la distancia total al cuadrado desde cada punto a su propio centro, y cada uno de los dos pasos solo puede reducirla. Esa es toda la demostración de que el algoritmo se detiene.

Qué significa cada símbolo

k: cuántos clústeres has pedido, algo que nada en los datos te indica
WCSS: la distancia total al cuadrado desde cada punto a su propio centro

Supone: Que un clúster es una nube redondeada de tamaño similar al resto, porque la distancia euclidiana al cuadrado respecto a una media no puede expresar otra cosa. No es que k-medias encuentre mal los grupos alargados, anidados o muy desiguales. Sencillamente, no son el tipo de cosa que busca.

Todas esas ejecuciones convergieron 🖖

Mantén las tres manchas y k = 3, y recorre el control de inicio del 1 al 24. Veintidós de los inicios se estabilizan en 1,0989. Los números 17 y 21 lo hacen en 5,8172 y 5,8331, lo cual es 5,3 veces peor: fusionan dos de las manchas y parten la tercera por la mitad. Nada salió mal en esas dos ejecuciones. Está garantizado que el algoritmo de Lloyd converge: la suma de cuadrados intra-clúster cae a cada paso y no puede caer eternamente, por lo que debe detenerse. De 1.536 ejecuciones pasando por todos los conjuntos, todas las k y ambas inicializaciones, ni una sola falló en hacerlo. Lo que no está garantizado es que se detenga en un buen lugar. Por lo tanto, "el algoritmo convergió" es una afirmación sobre aritmética más que sobre tus datos. Si ejecutaste k-means una sola vez, no tienes forma de saber cuál de estas dos respuestas tienes en las manos.

k-means++ reduce el daño a la mitad sin prometer nada 🖖

Cambia Cómo empieza a k-means++ y la dispersión en este conjunto se desvanece: los veinticuatro inicios encuentran 1,0989. Es la solución a la que todos recurren, y funciona distribuyendo los centros iniciales en lugar de soltarlos al azar. Pero la mejora es estadística, no una garantía, y vale la pena saber de cuánto estamos hablando. Midiendo sobre 112 combinaciones de conjuntos de puntos, tamaños de muestra y k: k-means++ encontró un óptimo estrictamente mejor que el inicio aleatorio en 38 de ellas, el aleatorio lo hizo mejor en 17 y empataron en 57. La dispersión media entre veinticuatro inicios cayó del 55,5% al 31,7%. Básicamente reduce a la mitad lo mal que puede ir una ejecución desafortunada, pero en uno de cada seis casos te habría ido mejor tirando dardos. Ajusta el anillo a 90 puntos y k = 5 para ver uno de esos ejemplos: el aleatorio alcanza 0,9884 y k-means++ se queda en 1,0213.

Una respuesta estable, equilibrada y segura a una pregunta sin respuesta 🖖

Carga el último ajuste predeterminado. Los puntos forman una cuadrícula regular sin ningún clúster en absoluto, y k-means los divide en cuatro grupos de exactamente 25. Ahora mira lo que dicen todos tus diagnósticos sobre ese resultado. Convergió, en once iteraciones. Es estable: las veinticuatro posiciones de inicio llegan a la misma respuesta, por lo que reiniciar no te avisa de que algo vaya mal. Los clústeres están perfectamente equilibrados, que es el aspecto que suele tener un buen clustering. Tres señales distintas apuntan en la misma dirección, y sin embargo no hay nada ahí. Esta es la parte del clustering que no tiene arreglo técnico: k-means responde a la pregunta de "dónde irían k centros" y siempre tiene una respuesta, independientemente de si la pregunta "cuántos grupos hay en estos datos" tiene alguna.

Problema resuelto al detalle

No sabes cuántos clústeres tienen tus datos, así que planeas deducirlo directamente del codo en la curva de puntuación. Pon a prueba esta lectura en los cuatro conjuntos de puntos y cuenta cuántas veces aciertas. El panel inferior te da la mejor puntuación para cada k del 1 al 8, con la caída desde la k anterior dibujada detrás.

Abre este problema en la herramienta
1. Primero, veamos por qué buscamos un codo en lugar de un mínimo. Selecciona el conjunto de puntos Tres nubes y lee la curva: 10,3978 en k = 1. Luego 5,6145, 1,0989, 0,9241, 0,8052, 0,6875, 0,6077 y 0,5366. Nunca sube. No puede hacerlo. Cualquier agrupamiento en k grupos se puede convertir en uno de k + 1 dividiendo un grupo. Esa división solo consigue acercar los puntos a su propio centro. Si aumentas k hasta igualar el número de puntos, cada punto formará su propio clúster y la puntuación será exactamente 0.
  
  $WCSS (k) = \sum_{j = 1}^{k} \sum_{x \in C_{j}} ∥ x - μ_{j} ∥^{2}, WCSS (k + 1) \leq WCSS (k) three blobs : 10.3978, 5.6145, 1.0989, 0.9241, 0.8052, 0.6875, 0.6077, 0.5366$
2. Por tanto, la curva carece de mínimo que encontrar. La lectura debe centrarse en las caídas. En las nubes, marcan 46,0%, luego 80,4%, seguidas de 15,9%, 12,9%, 14,6%, 11,6% y 11,7%. La caída tras k = 3 es una quinta parte de la caída previa: un desplome por un factor de 5,06. Sabemos que k = 3 es exactamente la forma en que se construyeron los datos. El método funciona aquí. Este es el caso que se enseña a todo el mundo.
  
  $drop (k) = 1 - \frac{WCSS ( k + 1 )}{WCSS ( k )}, elbow = ar g max_{k} \frac{drop ( k - 1 )}{drop ( k )} three blobs : 46 . 0%, 80 . 4%, 15 . 9%, 12 . 9%, 14 . 6%, 11 . 6%, 11 . 7% \Rightarrow k = 3, \times 5.06$
3. Pasemos a la Retícula, que no tiene clústeres en absoluto. Sus caídas son del 41,6%, 34,1%, 36,8%, 16,4%, 16,9%, 12,8% y 15,7%. Se produce un desplome por un factor de 2,25 después de k = 4. Es exactamente la forma que te han enseñado a buscar. La lectura del codo devuelve «cuatro clústeres» para un conjunto sin ninguno.
  
  $lattice : 41 . 6%, 34 . 1%, 36 . 8%, 16 . 4%, 16 . 9%, 12 . 8%, 15 . 7% \Rightarrow k = 4, \times 2.25$
4. Luego el Anillo, donde de verdad existen dos grupos. Sus caídas son del 37,2%, 32,8%, 38,5%, 33,4%, 43,1%, 25,3% y 15,3%. No hay ninguna tendencia, tan solo dos descensos al final. El desplome más brusco se produce después de k = 6. La lectura dice seis. La respuesta es dos.
  
  $ring : 37 . 2%, 32 . 8%, 38 . 5%, 33 . 4%, 43 . 1%, 25 . 3%, 15 . 3% \Rightarrow k = 6, \times 1.70$
5. Y Desigual, tres clústeres de tamaños diferentes: 43,8%, 48,4%, 35,4%, 24,7%, 16,1%, 14,4% y 21,8%. Un descenso suave sin desplomes por ninguna parte. El más pronunciado es por un factor de 1,53, algo incapaz de formar una esquina. La lectura no te aporta nada frente a unos datos que realmente contienen tres clústeres.
  
  $uneven : 43 . 8%, 48 . 4%, 35 . 4%, 24 . 7%, 16 . 1%, 14 . 4%, 21 . 8% \Rightarrow k = 5, \times 1.53$
Respuesta

Un acierto de cuatro: correcto en las nubes, cuatro clústeres inventados en la retícula, seis propuestos frente a los dos del anillo y silencio con el conjunto desigual. El patrón no es aleatorio. El codo se marca con claridad justo cuando los clústeres son redondos, de tamaño parecido y están bien separados. Es decir, cuando podías haberlos contado a simple vista. En cambio, desaparece en cualquier conjunto donde de verdad necesitabas ayuda. Conviene saberlo antes de usar la curva para justificar un número ante alguien. Por ese motivo, el método del codo se sitúa junto al coeficiente de silueta, el estadístico de brecha y los criterios de información, no por encima de ellos. Ninguno de estos aparece en esta página. Cada uno representa una manera distinta de formular la misma pregunta que la curva de puntuación no sabe contestar. No preguntan «dónde irían k centros», algo que siempre tiene respuesta, sino «¿realmente hay grupos aquí?».

$set three blobs lattice ring uneven elbow says 3465 truth 3023 sharpness \times 5.06 \times 2.25 \times 1.70 \times 1.53$

Ruta de aprendizaje

Ajuste de una recta a los datos

Referencias (3)

The algorithm itself. Written in 1957 for quantising a signal into levels, circulated as a Bell Labs memorandum, and not published for twenty-five years: S. P. Lloyd, “Least squares quantization in PCM.” IEEE Transactions on Information Theory 28(2), 129–137, 1982.
The initialisation the second insight block measures — and the source of the bound that makes it worth using, which is a guarantee about the EXPECTED score rather than about any single run: D. Arthur and S. Vassilvitskii, “k-means++: The Advantages of Careful Seeding.” In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’07), 1027–1035. SIAM, 2007.
Where the elbow reading comes from, and it was proposed with more caution than it is usually repeated with: R. L. Thorndike, “Who belongs in the family?” Psychometrika 18(4), 267–276, 1953.

Por el equipo de 42Math · Contrastado con fuentes publicadas. Se agradecen correcciones.