Mejora de las variantes de K-Means

El análisis de clustering es uno de los algoritmos de procesamiento de datos más utilizados. Durante más de medio siglo, K-means sigue siendo el algoritmo de clustering más popular debido a su simplicidad. El clustering tradicional de K-means trata de asignar n objetos de datos a k clusters empezando con centros iniciales aleatorios. Sin embargo, la mayoría de las variantes de k-medias tienden a calcular la distancia de cada punto de datos a cada centroide de cluster en cada iteración. Proponemos una heurística rápida para superar este cuello de botella con sólo un aumento marginal del error cuadrático medio (MSE). Observamos que a lo largo de todas las iteraciones de K-means, un punto de datos cambia su pertenencia sólo entre un pequeño subconjunto de clusters. Nuestra heurística predice dichos clusters para cada punto de datos observando los clusters cercanos después de la primera iteración de k-means. Aumentamos variantes bien conocidas de k-means como Enhanced K-means y K-means with Triangle Inequality utilizando nuestra heurística para demostrar su eficacia. Para varios conjuntos de datos, nuestra heurística consigue un aumento de velocidad de hasta 3 veces en comparación con las variantes eficientes de k-means.