K-Means||

Implementado en Spark, y usable a través de las APIs de R y Python, el algoritmo K-Means es uno de los más utilizados desde su época de salida. Es tal su alcance de uso que varias investigaciones han buscado optimizar su uso y procesamiento. Así, uno de sus aspectos cruciales para obtener una solución adecuada es una inicialización adecuada. Respecto a ello, Bahmani el al. (2012) menciona que existe el algoritmo de inicialización k-means++, el cual obtiene un conjunto de centros que se encuentra probablemente cerca a la solución óptima. Sin embargo, dada su naturaleza secuencial (se debe pasar k sobre los datos para encontrar un buen conjunto inicial de centros), este algoritmo tiene capacidades limitadas al aplicarse en conjuntos de datos masivos y por ello los autores proponen el algoritmo k-means||.

El algoritmo k-means|| reduce drásticamente el número de pases que se debe realizar para obtener, en paralelo, una buena inicialización. Este enfoque se diferencia de otros procesos de paralelización de k-means, enfocados usualmente en la etapa post-inicialización. Dicho algoritmo se ha mostrado tener una solución cercana al óptimo en un número de pases reducido.

La idea principal es que, en lugar de muestrear un solo punto en cada iteración como en el algoritmo k-means++, se muestrean \(O(k)\) puntos en cada iteración durante aproximadamente \(O(log(n))\) rondas. Al final del proceso se obtienen \(O(k log(n))\) puntos que forman una solución cercana al óptimo. Estos puntos se utilizan como centros iniciales para el algoritmo de Lloyd.