python - machine - Agrupación jerárquica de 1 millón de objetos.
clustering python (2)
¿Puede alguien dirigirme a una herramienta de agrupamiento jerárquico (preferible en python) que puede agrupar ~ 1 millón de objetos? He intentado hcluster y también Orange .
hcluster tuvo problemas con objetos de 18k. Orange pudo agrupar objetos de 18k en segundos, pero falló con objetos de 100k (memoria saturada y finalmente se bloqueó).
Estoy ejecutando una CPU Xeon de 64 bits (2.53GHz) y 8GB de RAM + 3GB swap en Ubuntu 11.10.
El problema probablemente es que intentarán calcular la matriz de distancia 2D completa (aproximadamente 8 GB ingenuamente con doble precisión) y luego su algoritmo se ejecutará en tiempo O(n^3) todos modos.
Debería considerar seriamente utilizar un algoritmo de agrupamiento diferente . El agrupamiento jerárquico es lento y los resultados generalmente no son convincentes. En particular para millones de objetos, donde no puede simplemente mirar el dendrograma para elegir el corte apropiado.
Si realmente desea continuar con el agrupamiento jerárquico, creo que ELKI (aunque Java) tiene una implementación O(n^2) de SLINK . Que en 1 millón de objetos debe ser aproximadamente 1 millón de veces más rápido. No sé si ya tienen CLINK , también. Y no estoy seguro de si realmente existe algún algoritmo sub- O(n^3) para otras variantes además del enlace simple y el enlace completo.
Considera usar otros algoritmos. k-means, por ejemplo, se adapta muy bien al número de objetos (por lo general tampoco es muy bueno, a menos que sus datos sean muy claros y regulares). DBSCAN y OPTICS son bastante buenos en mi opinión, una vez que tenga una idea de los parámetros. Si su conjunto de datos es de baja dimensión, pueden acelerarse bastante bien con una estructura de índice adecuada. Luego deben ejecutarse en O(n log n) , si tiene un índice con tiempo de consulta O(log n) . Lo que puede hacer una gran diferencia para grandes conjuntos de datos. Personalmente he usado OPTICS en un conjunto de datos de imágenes de 110k sin problemas, por lo que puedo imaginar que se amplíe a 1 millón en su sistema.
Para vencer a O (n ^ 2), primero deberá reducir sus puntos 1M (documentos) a, por ejemplo, 1000 pilas de 1000 puntos cada una, o 100 pilas de 10k cada una, o ...
Dos posibles enfoques:
construya un árbol jerárquico a partir de 15k puntos, luego agregue el resto uno por uno: tiempo ~ 1M * treedepth
primero construya 100 o 1000 clústeres planos, luego construya su árbol jerárquico de los 100 o 1000 centros de clústeres.
¿Qué tan bien podría funcionar cualquiera de estos dos factores depende del tamaño y la forma de su árbol objetivo? ¿Cuántos niveles, cuántas hojas?
¿Qué software está utilizando y cuántas horas / días tiene que hacer la agrupación?
Para el enfoque de cluster plano, K-d_tree s funciona bien para los puntos en 2d, 3d, 20d, incluso 128d, no es su caso. Apenas sé nada sobre agrupar texto; Locality-sensitive_hashing ?
Eche un vistazo a la agrupación de scikit-learn : tiene varios métodos, incluido DBSCAN.
Añadido: ver también
"Algoritmos para buscar todos los pares similares de vectores en datos vectoriales dispersos", Beyardo et el. 2007
SO jerarquica-clusterizacion-heuristicas