Tema

Agrupamiento por k medias

Machine Learning
Nivel base
Con simulador interactivo

El algoritmo de k medias alterna dos pasos hasta converger, asignar cada punto al centroide más cercano y recalcular cada centroide como la media de los puntos que se le asignaron, lo que minimiza la suma de distancias al cuadrado dentro de los grupos.

Nombre en inglés

K means clustering

Intuición

Conviene verlo como k imanes colocados al azar que atraen los puntos cercanos y luego se desplazan al centro de gravedad de lo que atrajeron. Cada paso reduce la función objetivo o la deja igual, de modo que el proceso siempre para, aunque el punto donde para depende de dónde se colocaron los imanes al principio. Por eso se repite con varias inicializaciones y se conserva la mejor.

Fórmula

J = sum_{i=1}^{n} || x_i - mu_{c(i)} ||^2,  con mu_k = (1 / |C_k|) sum_{x en C_k} x

Ejemplo resuelto

Los datos en una recta son 1, 2, 3, 10, 11 y 12, con k igual a 2 y centroides iniciales en 1 y en 2. En la primera asignación el 1 va al primer centroide y los demás al segundo, porque todos están más cerca de 2. Los centroides pasan a 1 y a 38 dividido entre 5 = 7.6. En la segunda asignación el 2 y el 3 se acercan más al 1 que al 7.6, mientras que 10, 11 y 12 se quedan con el segundo. Los centroides pasan a 2 y a 11, la siguiente asignación no cambia y el algoritmo para con J igual a 4.

Errores frecuentes

Aplicarlo a grupos alargados o de tamaños muy distintos, ya que la asignación al centroide más cercano impone fronteras rectas y favorece grupos esféricos y parecidos.
No escalar las variables, con lo que la columna de mayor rango decide sola la pertenencia y las demás quedan de adorno.
Elegir k maximizando la calidad del ajuste, cuando la función objetivo siempre mejora al subir k y hace falta el codo de la curva o la silueta para decidir.

Ejercicio

Un grupo contiene los puntos 4, 6 y 8 de una recta. Calcula su centroide y la suma de distancias al cuadrado dentro del grupo.

Ver la solución

El centroide es la media, o sea 4 + 6 + 8 dividido entre 3 = 6. Las distancias al centroide valen 2, 0 y 2, y sus cuadrados valen 4, 0 y 4. La suma dentro del grupo vale 8. Conviene notar que la media minimiza esa suma, y por eso el paso de recálculo usa la media y no la mediana, que en cambio minimizaría la suma de distancias sin elevar al cuadrado.