La historia de la invención del algoritmo K-means

La agrupación de K-medias se inventó en 1956. La forma más común de este algoritmo es una heurística de mejora iterativa llamada algoritmo de Lloyd. El algoritmo de Lloyd primero divide los puntos de entrada en k grupos de inicialización. Los grupos de inicialización pueden ser aleatorios o utilizar algunos datos heurísticos. Luego calcule el punto central de cada grupo, divida los objetos al centro más cercano según la posición del punto central y redefina la agrupación. Continúe calculando repetidamente el centro y reagrupe hasta la convergencia, es decir, los objetos ya no cambian de agrupación (la posición del punto central ya no cambia).

El algoritmo de Lloyd y el promedio K suelen estar estrechamente relacionados, pero en aplicaciones prácticas, el algoritmo de Lloyd es una regla heurística para resolver problemas de promedio K. Para ciertas combinaciones de puntos de partida y centros de gravedad, el algoritmo de Lloyd puede converger a resultados incorrectos. (Hay diferentes soluciones óptimas en la función anterior)

A pesar de los cambios, el algoritmo de Lloyd sigue siendo popular porque converge muy rápidamente en la práctica. De hecho, se observa que el número de iteraciones es mucho menor que el número de puntos. Pero recientemente David Arthur y Sergei Vassilvitskii propusieron que la existencia de conjuntos de puntos específicos hace que el algoritmo de promedio K requiera un tiempo superpolinomial para lograr la convergencia.

El algoritmo K-means aproximado está diseñado para calcular el subconjunto de datos original.

A partir del rendimiento del algoritmo, no se garantiza la obtención de la solución óptima global. La calidad de la solución final depende en gran medida de la agrupación de inicialización. Dado que este algoritmo es muy rápido, un método común es ejecutar el algoritmo de promedio K varias veces para seleccionar la solución óptima.

Una desventaja del algoritmo K-promedio es que el número de paquetes K es un parámetro de entrada y un K inapropiado puede arrojar malos resultados. Además, el algoritmo supone que el error cuadrático medio es el parámetro óptimo para calcular la dispersión del grupo.