Agrupación de un gran conjunto de datos 3D en muchos clusters

Question

Tengo una nube de puntos 3D con varios millones de puntos y necesito dividirla en aproximadamente 50k clusters. Como los clusters tienen que ser esféricos, lo que suele ser un inconveniente de k-means, este último parece bastante apropiado. Mi problema es que $k$ es demasiado grande, por lo que el tiempo de ejecución es inaceptable. Las agrupaciones no tienen que ser exactas, puedo tolerar bastante bien las clasificaciones erróneas.

Encontré un documento sobre mini-lote k-means que podría funcionar. Y este trabajo utilizando MapReduce . También leí este y otras preguntas, pero la pregunta y las respuestas son demasiado vagas. Este (diapositiva 2) la fuente afirma que con el uso de árboles k-d el tiempo de ejecución se puede reducir de $O(l*K*m*n)$ a $O(m*logm)$ No puedo encontrar cómo debería funcionar.

¿Es el mini-batch k-means el camino a seguir? ¿Hay alguna solución sencilla para los datos de baja dimensión (3D)?

Agradecería una implementación en C++, hasta ahora sólo he podido encontrar mini batch k-means en scikit que podría traducir. ¿Puede recomendar algún otro?

Answer 1

He visto que la gente utiliza la ÓPTICA en millones de puntos, pero eso no creará cúmulos "esféricos".

Probablemente algo extremadamente simple como LEADER es lo que quieres.

K-means con k grande es bastante problemático. En primer lugar, el tiempo de ejecución aumenta considerablemente con k y, en segundo lugar, en los datos ruidosos, a menudo aparecen clústeres con un solo valor atípico.

Para datos tridimensionales, merece la pena probar los árboles k-d. En particular, para k grandes. Sin embargo, estos métodos no son fáciles de aplicar. Se necesitaría una unión de dos árboles con el vecino más cercano (uno con los datos y otro con los centros). Eso requiere un manejo de datos bastante complejo que no es divertido de hacer, y no conozco ninguna biblioteca de árboles k-d que proporcione esta funcionalidad.

Los k-means en miniatura tampoco te ayudarán mucho. El tamaño de los lotes debe ser mucho mayor que k. Además, nunca converge. Así que tendrías que ejecutarlo todo lo que puedas permitirte y luego esperar que el resultado sea lo suficientemente bueno. Eso está bien para la bolsa de palabras visual, pero no para muchos otros casos.