k-means es el algoritmo clásico de agrupamiento: dado un conjunto de puntos sin etiquetas y un número k, los reparte en k grupos, cada uno representado por su centro. Es la primera especie de esta Pokédex que aprende sin maestro (aprendizaje no supervisado): no hay clase que predecir, solo grupos «naturales» que, se supone, reflejan algún mecanismo del dominio (Witten et al., 2017, p. 141).
Cómo funciona
Cada punto es un vector. El procedimiento que describen Witten et al. (2017) tiene cinco pasos (2017, pp. 142–143):
- Fijar k de antemano.
- Elegir k puntos al azar como centros iniciales.
- Asignar cada punto al centro más cercano (distancia euclídea).
- Reemplazar cada centro por el promedio, o centroide, de sus puntos: de ahí «means».
- Repetir 3 y 4 hasta que ninguna asignación cambie.
En el ejemplo del libro, quince puntos y k = 3 se estabilizan en pocas vueltas (Witten et al., 2017, p. 143). La convergencia está garantizada porque ningún paso empeora las cosas: el centroide es el punto que minimiza la suma de distancias al cuadrado dentro de un grupo, y asignar al centro más cercano también la reduce; el efecto global es minimizar la distancia cuadrática total (Witten et al., 2017, p. 144). En términos actuales, es una función de pérdida optimizada por turnos.
El nombre lo puso MacQueen (1967). El procedimiento alternado ya lo había formulado Stuart Lloyd en Bell Labs en 1957, para cuantizar señales en modulación por código de pulsos (PCM), aunque se publicó recién en 1982 (Lloyd, 1982); por eso también se lo llama algoritmo de Lloyd.
Qué cambió
Frente a k vecinos más cercanos, que guarda cada ejemplo, k-means resume: cada grupo queda condensado en un único vector, y sus parámetros son apenas k × d números (k centros de d dimensiones). El paso de asignación parte el espacio en celdas convexas, una por centro: la misma geometría que usa kNN con todos sus ejemplos, pero con solo k representantes.
Límites
El mínimo que encuentra es local: el resultado depende de las semillas iniciales, y cambios pequeños producen agrupamientos muy distintos. Witten et al. (2017) dan un ejemplo mínimo: cuatro puntos en los vértices de un rectángulo; si las semillas caen en los puntos medios de los lados largos, la solución es estable y equivocada (2017, p. 144). Se suele correr varias veces y quedarse con la mejor, o sembrar con k-means++, que elige cada semilla con probabilidad proporcional al cuadrado de su distancia a las ya elegidas (Witten et al., 2017, p. 144).
El problema de fondo es k, un hiperparámetro. Con los datos de entrenamiento, el «mejor» agrupamiento según la distancia total es siempre uno por punto; hay que penalizar los grupos de más (por ejemplo, con longitud mínima de descripción) o probar divisiones sucesivas (Witten et al., 2017, p. 146). A eso se suma su sesgo inductivo: supone grupos compactos y convexos.
Con texto, el procedimiento típico es convertir documentos en embeddings, reducir la dimensión y recién entonces agrupar (Alammar y Grootendorst, 2024, p. 139). k-means es una opción común, pero exige saber k; métodos basados en densidad como HDBSCAN deciden el número de grupos y dejan fuera los puntos atípicos (Alammar y Grootendorst, 2024, p. 143).