¿Deberíamos usar k-means ++ en lugar de k-means?

Question

El k-means++ algoritmo ayuda de dos siguientes puntos del original de k-medias algoritmo:

1. La k-medio original algoritmo tiene el peor caso de tiempo de super-polinomio en tamaño de entrada en funcionamiento, mientras que k-medias ++ tiene reivindicado ser O (log k).
2. La aproximación encontrada puede producir un resultado no tan satisfactorio con respecto a la función objetivo en comparación con la agrupación óptima.

¿Pero hay algún inconveniente de k-means ++? ¿Deberíamos usarlo siempre en lugar de k-means a partir de ahora?

Answer 1

Nadie reclama k-means++ se ejecuta en O (lg k) time; su calidad de solución es O (lg k) -competitivo con la solución óptima. Ambos k-significa ++ y el método común, llamado algoritmo de Lloyd, son aproximaciones a un problema de optimización de NP-hard.

No estoy seguro de cuál es el peor caso de tiempo de ejecución de k -means ++ is; tenga en cuenta que en la descripción original Arthur & Vassilvitskii's, los pasos 2-4 del algoritmo se refieren al algoritmo de Lloyd. Afirman que funciona mejor y más rápido en la práctica porque parte de una mejor posición.

Los inconvenientes de k-means ++ son así:

1. Es también podemos encontrar una solución subóptima (que sigue siendo una aproximación).
2. No es consistentemente más rápido que el algoritmo de Lloyd (ver Arthur & tablas de Vassilvitskii).
3. Es más complicado que el algo de Lloyd.
4. Es relativamente nuevo, mientras que Lloyd's ha demostrado que vale más de 50 años.
5. Pueden existir mejores algoritmos para espacios métricos específicos.

Dicho esto, si la biblioteca k-means apoya k-means ++, entonces por todos los medios probarlo.

Answer 2

No

pregunta, sino una aceleración fácil de cualquier método kmeans para N grande:

1) en primer lugar qué kmeans sobre una muestra aleatoria de decir sqrt (N) de los puntos
2) a continuación, ejecutar k completo significa de esos centros.

He encontrado esto 5-10 veces más rápido que kmeans ++ para N 10000, k 20, con resultados similares.
lo bien que funciona para usted dependerá de lo bien que un (N) muestra sqrt se aproxima al conjunto, así como en N, tenue, k, nInit, delta ...

¿Cuáles son sus N (número de puntos de datos), tenue (número de características) yk?
El amplio rango en N, dim, k, ruido de datos, métricas ... de los usuarios, sin mencionar la falta de puntos de referencia públicos, dificultan la comparación de métodos.

Agregado: el código Python para kmeans() y kmeanssample() es here en SO; los comentarios son bienvenidos