Meta fair presenta e-means, un algoritmo de clustering que supera a k-means con significativamente menos iteraciones

Los investigadores de Meta FAIR han presentado e-means, un nuevo algoritmo de clustering diseñado como un reemplazo directo para el k-means de Lloyd. Este método logra la misma pérdida que el k-means de Lloyd después de 25 épocas, utilizando solo entre 1,4 y 2,6 épocas. La implementación está disponible en FAISS versión 1.16.0 en faiss.contrib.e_means, con el objetivo de agilizar el paso de clustering offline en la indexación vectorial y las tuberías de datos. e-means funciona como una variante mini-batch de k-means, actualizando los centros de los clústeres utilizando promedios móviles exponenciales. Las pruebas revelaron importantes ganancias de rendimiento: un solo paso de e-means que procesa 512 puntos tardó solo 0,001 segundos, en comparación con 0,176 segundos para un paso de Lloyd que tocaba 100.000 puntos. Además, e-means demostró una mayor estabilidad, permaneciendo en el 0% de los inicios en un ejemplo de juguete de 5 clústeres, mientras que Lloyd se quedaba atascado en el 46%. Además, los hallazgos resaltan la robustez de e-means. Al tratar con un gran número de clústeres, como 16.384 en el conjunto de datos DEEP, el mecanismo de recuperación de e-means impidió que murieran el 0,3% de los clústeres, en comparación con el 26,3% cuando la recuperación estaba deshabilitada. Los autores también notaron que el descenso de gradiente estándar funcionó peor que EMA, terminando un 1,6% (DEEP) y un 0,4% (SIFT) por encima de EMA en su mejor configuración.