¿Rápido k-significa como algoritmo para 10 ^ 10 puntos?

Estoy buscando hacer clusters de k-means en un conjunto de puntos de 10 dimensiones. El truco: hay 10 ^ 10 puntos .

Estoy buscando solo el centro y el tamaño de los grupos más grandes (digamos de 10 a 100 grupos); No me importa en qué grupo termina cada punto. Usar k-means específicamente no es importante; Solo estoy buscando un efecto similar, cualquier medio k aproximado o algoritmo relacionado sería genial (minibatch-SGD significa, ...). Dado que GMM es, en cierto sentido, el mismo problema que k-means, hacer GMM con los mismos datos de tamaño también es interesante.

A esta escala, el submuestreo de los datos probablemente no cambie el resultado de manera significativa: las probabilidades de encontrar los mismos 10 grupos principales utilizando una muestra de datos de 1/10000 son muy buenas. Pero incluso entonces, ese es un problema de 10 ^ 6 puntos que está en / más allá del borde del tractable.

k-means se basa en promedios .

Modela clústeres utilizando medios y, por lo tanto, la mejora al agregar más datos es marginal. El error de la estimación promedio se reduce con 1 / sqrt (n); así que agregar más datos vale cada vez menos ...

Las estrategias para datos tan grandes siempre giran en torno al muestreo:

Si quieres tiempo de ejecución sublineal, ¡tienes que hacer un muestreo!

De hecho, Mini-Batch-Kmeans etc. hace exactamente esto: muestra repetidamente del conjunto de datos.

Sin embargo, el muestreo (en particular, el muestreo imparcial) tampoco es exactamente gratuito ... por lo general, tendrá que leer sus datos linealmente para muestrear, porque no tiene acceso aleatorio a registros individuales.

Yo iría con el algoritmo de MacQueen. Está en línea; de manera predeterminada, realiza una sola pasada sobre sus datos (aunque es popular repetir esto). No es fácil de distribuir, pero supongo que puede permitirse leer linealmente sus datos, digamos 10 veces desde un SSD.

Como comentario adicional, tenga en cuenta que el uso de K-means para datos 10D podría terminar en ninguna parte de acuerdo con la maldición de la dimensionalidad. Por supuesto, varía un poco según la naturaleza de los datos, pero una vez que traté de determinar el umbral en el que K-Means comienza a comportarse de manera extraña con respecto a la dimensionalidad, obtuve algo así como 7D. Después de 7 dimensiones, comenzó a fallar los grupos correctos (mis datos se generaron manualmente de acuerdo con 4 distribuciones gaussianas bien separadas y utilicé la función kmeans de MATLAB para mi pequeño experimento).