Question Cluster hiérarchique distribué


Existe-t-il des algorithmes pouvant aider à la classification hiérarchique? Google Map-Reduce n’a qu’un exemple de k-clustering. En cas de regroupement hiérarchique, je ne sais pas comment diviser le travail entre les nœuds. Une autre ressource que j'ai trouvée est: http://issues.apache.org/jira/browse/MAHOUT-19 Mais ce n’est pas évident, quels algorithmes sont utilisés.


21
2017-09-17 16:00


origine


Réponses:


Tout d'abord, vous devez décider si vous allez construire votre hiérarchie de manière ascendante ou descendante.

Bottom-up est appelé clustering agglomératif hiérarchique. Voici un algorithme simple et bien documenté: http://nlp.stanford.edu/IR-book/html/htmledition/hierarchical-agglomerative-clustering-1.html.

La distribution d'un algorithme ascendant est délicate car chaque processus distribué a besoin de l'ensemble de données pour faire des choix sur les clusters appropriés. Il a également besoin d'une liste de grappes à son niveau actuel pour ne pas ajouter de point de données à plusieurs grappes au même niveau.

La construction de la hiérarchie descendante est appelée Cluster divisant. K-moyennes est une option pour décider comment fractionner les nœuds de votre hiérarchie. Cet article porte sur le partitionnement par division des moyennes K et des directions principales (PDDP) pour la division des nœuds: http://scgroup.hpclab.ceid.upatras.gr/faculty/stratis/Papers/tm07book.pdf. Au final, il vous suffit de séparer chaque nœud parent en nœuds enfants relativement bien équilibrés.

Une approche descendante est plus facile à distribuer. Après la séparation de votre premier nœud, chaque nœud créé peut être livré à un processus distribué pour être divisé à nouveau, etc. Chaque processus distribué n'a besoin que de connaître le sous-ensemble du jeu de données qu'il divise. Seul le processus parent est au courant de l'ensemble de données complet.

De plus, chaque division pourrait être effectuée en parallèle. Deux exemples pour k-means:


17
2017-10-10 18:45



Clark Olson passe en revue plusieurs algorithmes distribués pour la classification hiérarchique:

C. F. Olson. "Algorithmes parallèles pour   Classification hiérarchique." Parallèle   L'informatique21: 1313-1325, 1995, doi: 10.1016 / 0167-8191 (95) 00017-I.

Parunak et al. décrire un algorithme inspiré de la manière dont les fourmis classent leurs nids:

H. Van Dyke Parunak, Richard Rohwer,   Theodore C. Belding et Sven   Brueckner: "Dynamique Décentralisé   Clustering hiérarchique à tout moment.    Proc. 4ème atelier international sur l'ingénierie des systèmes auto-organisateurs   (ESOA), 2006, doi: 10.1007 / 978-3-540-69868-5


2
2017-10-09 18:35



Découvrez cette très lisible si un peu daté revue par Olson (1995). La plupart des journaux exigent depuis lors des frais d’accès. :-)

Si vous utilisez R, je vous recommande d’essayer pvclust qui réalise le parallélisme en utilisant neige, un autre module R.


2
2018-05-12 16:56



Vous pouvez voir aussi Trouver et évaluer la structure de la communauté dans les réseaux par Newman et Girvan, où ils proposent une approche pour évaluer les communautés dans les réseaux (et un ensemble d'algorithmes basés sur cette approche) et une mesure de la division du réseau en qualité des communautés (modularité des graphes).


1
2018-05-12 14:35



Vous pouvez regarder une partie du travail effectué avec des cartes auto-organisatrices (méthode de réseau neuronal de Kohonen) ... les gars de Université de technologie de Vienne ont travaillé sur le calcul distribué de leur algorithme hiérarchique croissant.

Ceci est un peu sur le bord de votre question de clustering, donc cela peut ne pas vous aider, mais je ne peux rien penser de plus proche;)


0
2017-09-17 16:28