Agrupamiento de espacio vectorial enorme

Question

Estoy haciendo algunas pruebas agrupando un gran número de vectores dispersos muy grandes que representan frecuencia-documento-frecuencia-frecuencia-término de varios documentos hipertextuales. ¿Qué algoritmo sugeriría para agrupar estos datos, teniendo en cuenta las proporciones del conjunto de datos? La dimensión de los vectores sería> 3 · 10 y el número de vectores podría ser alrededor de 10 . He echado un vistazo a los algoritmos de dbscan y óptica. La cantidad de conglomerados no se conoce a priori. Y un índice espacial con tal alta dimensionalidad parece complicado.

Answer 1

He tenido resultados casi tan buenos con un simple clúster de K-means como casi cualquier otra cosa, y es definitivamente más rápido que la mayoría de las alternativas. También obtuve buenos resultados con una aglomeración por pares, pero es bastante más lenta. Para K-means, tienes que comenzar con una cantidad estimada de clusters, pero puedes ajustarla algorítmicamente a medida que avanzas. Si encuentra dos clústeres con medios que están demasiado cerca uno del otro, reducirá la cantidad de clústeres. Si encuentra grupos con un rango de variación demasiado grande, pruebe con más clústeres. He encontrado que sqrt (N) es un punto de partida razonable, pero generalmente empiezo con más de 10^7 documentos en lugar de 10^9. Para 10^9, podría tener sentido reducir eso un poco.

Si fuera por mí, sin embargo, pensaría mucho sobre comenzar reduciendo la dimensionalidad con algo así como Landmark MDS, y luego haciendo la agrupación.

Answer 2

Los árboles de decisión son populares para trabajar eficientemente en espacios de gran dimensión. Consulte Clustering Via Decision Tree Construction.

Además, Randomized Forests son aprendices extremadamente eficientes y OpenCV implementation exists si quieres jugar con él.

Answer 3

Oí que semantic hashing logra excelentes resultados. Sin embargo, las redes de creencias profundas son bastante difíciles de implementar. Es posible que desee probar el hash de min (que es un enfoque probabilístico, sin embargo) o locality sensistive hashing for euclidean spaces.

En general, la agrupación en tales espacios de gran dimensión es difícil debido a la maldición de la dimensionalidad y al hecho de que la mayoría de los artículos tienen distancias similares entre sí. Los enfoques estándar como K-Means podrían funcionar si reduce la dimensionalidad de antemano a través de SOM o PCA.

Answer 4

Cuando la agrupación de datos yo siempre trato al menos estos dos algoritmos en este orden:

1. K-medias: tratar de ajustar los resultados tanto como sea posible. Si logras que K-Means trabaje para ti y te proporcione resultados decentes, seguramente no te irá mejor que con cualquier otro algoritmo.

2. Maximización de las expectativas: el algoritmo K-means se desarrolló en realidad para ser una alternativa barata y buena al algoritmo EM. El algoritmo EM es más complejo de entender y más costoso de computar, pero los resultados de EM son excelentes. Puede obtener más información sobre EM http://en.wikipedia.org/wiki/Expectation-maximization_algorithm. Hay una aplicación OPENCV de EM: http://opencv.willowgarage.com/documentation/expectation-maximization.html

Si los resultados de ninguno de estos dos son satisfactorios, me gustaría empezar a buscar en otro lugar, pero no hasta que haya probado ambos.