Agrupación jerárquica distribuida

Question

¿Existe algún algoritmo que pueda ayudar con la agrupación jerárquica?Map-reduce de Google solo tiene un ejemplo de k-clustering.En el caso de una agrupación jerárquica, no estoy seguro de cómo es posible dividir el trabajo entre los nodos.Otro recurso que encontré es: http://issues.apache.org/jira/browse/MAHOUT-19Pero no está claro qué algoritmos se utilizan.

Answer 1

Primero, tienes que decidir si vas a construir tu jerarquía de abajo hacia arriba o de arriba hacia abajo.

De abajo hacia arriba se llama agrupación aglomerativa jerárquica.Aquí hay un algoritmo simple y bien documentado: http://nlp.stanford.edu/IR-book/html/htmledition/hierarchical-agglomerative-clustering-1.html.

Distribuir un algoritmo ascendente es complicado porque cada proceso distribuido necesita todo el conjunto de datos para tomar decisiones sobre los grupos apropiados.También necesita una lista de clústeres en su nivel actual para no agregar un punto de datos a más de un clúster en el mismo nivel.

La construcción de jerarquía de arriba hacia abajo se llama Agrupación divisiva. K-medias es una opción para decidir cómo dividir los nodos de su jerarquía.Este artículo analiza las K-medias y la partición divisoria de dirección principal (PDDP) para la división de nodos: http://scgroup.hpclab.ceid.upatras.gr/faculty/stratis/Papers/tm07book.pdf.Al final, sólo necesita dividir cada nodo principal en nodos secundarios relativamente bien equilibrados.

Un enfoque de arriba hacia abajo es más fácil de distribuir.Después de la primera división del nodo, cada nodo creado se puede enviar a un proceso distribuido para dividirlo nuevamente y así sucesivamente...Cada proceso distribuido sólo necesita ser consciente del subconjunto del conjunto de datos que está dividiendo.Sólo el proceso principal conoce el conjunto de datos completo.

Además, cada split podría realizarse en paralelo.Dos ejemplos de k-medias:

• http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.101.1882&rep=rep1&type=pdf
• http://www.ece.northwestern.edu/~wkliao/Kmeans/index.html.

Answer 2

Clark Olson revisa varios algoritmos distribuidos para agrupación jerárquica:

C.F.Olson."Algoritmos paralelos para la agrupación jerárquica". Computación paralela, 21:1313-1325, 1995, doi:10.1016/0167-8191(95)00017-I.

Parunak et al.Describa un algoritmo inspirado en cómo las hormigas clasifican sus nidos:

h.Van Dyke Parunak, Richard Rohwer, Theodore C.Belding y Sven Brueckner:"Clúster jerárquico dinámico descentralizado en cualquier momento". En Proc.4to Taller Internacional sobre Sistemas de Autoorganización de Ingeniería (ESOA), 2006, doi:10.1007/978-3-540-69868-5

Answer 3

Mira esto, muy legible aunque un poco anticuado. revisión de Olson (1995).Desde entonces, la mayoría de los artículos requieren una tarifa para acceder.:-)

Si usas R, te recomiendo probar PVClust que logra el paralelismo usando nieve, otro módulo R.

Answer 4

Puedes ver también Encontrar y evaluar la estructura comunitaria en redes. por Newman y Girvan, donde proponen un enfoque para evaluar comunidades en redes (y un conjunto de algoritmos basados ​​en este enfoque) y una medida de la división de la red en la calidad de las comunidades (modularidad del gráfico).

Answer 5

Podrías ver algunos de los trabajos que se están realizando con mapas autoorganizados (método de red neuronal de Kohonen)...los chicos de Universidad Tecnológica de Viena han trabajado un poco en el cálculo distribuido de su creciente algoritmo de mapa jerárquico.

Esto está un poco al límite de su pregunta sobre agrupación, por lo que puede que no ayude, pero no se me ocurre nada más cercano;)