El algoritmo de k-medias

El algoritmo de k-medias reparte un conjunto de puntos en k grupos de manera que cada punto quede lo más cerca posible del centro de su grupo. Es el procedimiento más usado del aprendizaje no supervisado, la rama del aprendizaje automático que trabaja con datos sin etiquetas: nadie dice al algoritmo qué grupos hay ni cuáles son, solo cuántos debe encontrar. Se usa para segmentar clientes, comprimir imágenes reduciendo sus colores a unos pocos, agrupar documentos por tema y, como paso previo, para resumir millones de puntos en unos cientos de representantes. Es simple, rápido y casi siempre lo primero que se prueba, y por eso conviene entender bien qué hace y en qué se equivoca.

El algoritmo alterna dos pasos que la figura de esta página ejecuta uno a uno. Primero, asignación: cada punto se une al centro más cercano y toma su color. Segundo, actualización: cada centro se desplaza a la posición media de los puntos que se le han unido. Se repite hasta que ningún centro se mueve. Cada paso reduce, o deja igual, una cantidad que se llama inercia: la suma de las distancias al cuadrado de cada punto a su centro. Como la inercia no puede bajar indefinidamente, el proceso termina siempre, y casi siempre en pocas rondas. La figura muestra la inercia en cada paso y, a la derecha, la inercia final que se obtiene con cada valor de k entre uno y ocho.

La primera cosa que la figura enseña es que el resultado depende de la posición inicial de los centros. El algoritmo garantiza llegar a un mínimo de la inercia, pero local: si dos centros caen dentro del mismo grupo natural y un tercero queda a medio camino entre otros dos, ese reparto puede ser estable y ningún paso lo arregla. Con el conjunto de cinco grupos desiguales basta pulsar «Otros centros» unas veces para ver soluciones distintas con inercias distintas. La respuesta práctica es ejecutar el algoritmo varias veces desde puntos distintos y quedarse con la mejor; la respuesta elegante la dieron David Arthur y Sergei Vassilvitskii en 2007 con k-means++, que elige los centros iniciales uno a uno con probabilidad proporcional al cuadrado de la distancia a los ya elegidos, de modo que empiezan separados, y demostraron que eso garantiza en promedio una inercia a lo sumo unas pocas veces mayor que la óptima. El botón de la figura lo activa y las malas salidas se vuelven raras.

La segunda cosa es que k hay que elegirlo, y el algoritmo no ayuda. La inercia baja siempre al aumentar k, porque más centros están más cerca de todo, hasta llegar a cero cuando hay un centro por punto. La gráfica de la derecha, la curva del codo, muestra ese descenso; la heurística consiste en buscar el punto donde deja de bajar deprisa, el codo, y tomar ese k. Con tres grupos claros el codo está en tres y se ve bien. Con los cinco grupos desiguales está en cinco pero menos marcado. Con los datos uniformes no hay codo, la curva baja suavemente, y esa ausencia es la señal: no hay grupos que encontrar. Y sin embargo el algoritmo devuelve k grupos igual, con colores nítidos y fronteras rectas. K-medias siempre encuentra grupos, existan o no, y esa es la razón principal para desconfiar de un resultado que no se ha contrastado.

La tercera cosa es la forma. K-medias asigna cada punto al centro más cercano, y eso parte el plano en regiones convexas separadas por rectas, las celdas de Voronoi de los centros. Solo puede encontrar grupos redondos, o al menos convexos, y de tamaños parecidos. El conjunto del anillo con un punto en el centro lo muestra: un ser humano ve dos grupos, el anillo y el centro, y k-medias con k = 2 parte el anillo por la mitad y mete el centro con una de las mitades. Para grupos con esa forma hacen falta otros métodos, como el agrupamiento espectral o el basado en densidad, que definen la cercanía por cadenas de vecinos y no por la distancia a un centro.

El algoritmo tiene tantos padres como usos. Hugo Steinhaus lo planteó en 1956 como el problema de dividir un cuerpo en partes; Stuart Lloyd lo describió en 1957 en un informe interno de los Laboratorios Bell para cuantizar señales, que no se publicó hasta 1982; Edward Forgy lo publicó en 1965; y James MacQueen le puso el nombre en 1967 y propuso la versión que actualiza el centro después de cada punto en lugar de después de todos. Que se inventara varias veces dice algo de su naturalidad: es la primera idea que se le ocurre a cualquiera que quiera agrupar puntos, y por eso su lección más útil es la de la figura, que esa primera idea tiene condiciones, y que los grupos que devuelve son tan buenos como las suposiciones que uno hizo al elegir k y al aceptar que sean redondos.