algorithm - the - single linkage
Agrupación jerárquica distribuida (5)
¿Hay algún algoritmo que pueda ayudar con la agrupación jerárquica? Google map-reduce tiene solo un ejemplo de k-clustering. En caso de clúster jerárquico, no estoy seguro de cómo es posible dividir el trabajo entre nodos. Otro recurso que encontré es: http://issues.apache.org/jira/browse/MAHOUT-19 Pero no es evidente, qué algoritmos se usan.
Podrías ver parte del trabajo que se hace con los mapas de autoorganización (método de redes neuronales de Kohonen) ... los chicos de la Universidad Tecnológica de Viena han trabajado en el cálculo distribuido de su creciente algoritmo de mapa jerárquico.
Esto está un poco al borde de su pregunta de agrupamiento, por lo que puede no ser de ayuda, pero no puedo pensar en nada más cerca;)
Clark Olson revisa varios algoritmos distribuidos para la agrupación jerárquica:
CF Olson. "Algoritmos paralelos para la agrupación jerárquica". Parallel Computing , 21: 1313 - 1325 , 1995, doi: 10.1016 / 0167 - 8191 (95) 00017 - I.
Parunak et al. describe un algoritmo inspirado en cómo las hormigas clasifican sus nidos:
H. Van Dyke Parunak, Richard Rohwer, Theodore C. Belding y Sven Brueckner: "Agrupación jerárquica descentralizada dinámica en cualquier momento". En Proc. 4 ° Taller Internacional sobre Sistemas de Autoorganización de Ingeniería (ESOA) , 2006, doi: 10.1007 / 978-3-540-69868-5
Echa un vistazo a esta revisión muy legible si es un poco anticuada por Olson (1995) . La mayoría de los periódicos desde entonces requieren una tarifa para acceder. :-)
Si usa R, recomiendo probar pvclust, que logra el paralelismo usando nieve , otro módulo R.
También puede ver Encontrar y evaluar la estructura de la comunidad 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 medir la división de redes en la calidad de las comunidades (modularidad gráfica).
En primer lugar, debe decidir si va a construir su jerarquía de abajo hacia arriba o de arriba hacia abajo.
De abajo hacia arriba se llama Agrupamiento aglomerativo jerárquico. Aquí hay un algoritmo simple y bien documentado: http://nlp.stanford.edu/IR-book/html/htmledition/hierarchical-agglomerative-clustering-1.html .
La distribución de un algoritmo ascendente es complicado porque cada proceso distribuido necesita todo el conjunto de datos para tomar decisiones sobre los clústeres apropiados. También necesita una lista de clústeres en su nivel actual para que no agregue un punto de datos a más de un clúster en el mismo nivel.
La construcción jerárquica de arriba hacia abajo se llama agrupamiento divisivo . K-means es una opción para decidir cómo dividir los nodos de su jerarquía. Este documento analiza K-means y 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, solo necesita dividir cada nodo padre en nodos secundarios relativamente bien balanceados.
Un enfoque de arriba hacia abajo es más fácil de distribuir. Después de dividir su primer nodo, cada nodo creado puede enviarse a un proceso distribuido para dividirse de nuevo, y así sucesivamente ... Cada proceso distribuido solo necesita conocer el subconjunto del conjunto de datos que está dividiendo. Solo el proceso principal conoce el conjunto de datos completo.
Además, cada división podría realizarse en paralelo. Dos ejemplos para k-means: