Clustering hiérarchique distribué

Question

Existe-t-il des algorithmes pouvant aider à la mise en cluster hiérarchique? La carte-réduction de Google n'a qu'un exemple de k-clustering. En cas de clustering hiérarchique, je ne sais pas comment il est possible de diviser le travail en nœuds. Une autre ressource que j'ai trouvée est: http://issues.apache.org/jira/browse/ MAHOUT-19 Mais on ne sait pas quels algorithmes sont utilisés.

Answer 1

Tout d'abord, vous devez décider si vous allez construire votre hiérarchie de bas en haut ou de haut en bas.

La méthode ascendante s’appelle clustering hiérarchique par agglomération. 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'intégralité du jeu de données pour pouvoir choisir les clusters appropriés. Il a également besoin d’une liste de clusters à son niveau actuel pour ne pas ajouter de point de données à plusieurs clusters du même niveau.

La construction de la hiérarchie descendante est appelée Regroupement par division / a>. K-means est une option permettant de décider de la division de votre hiérarchie. nœuds. Cet article examine le partitionnement des divisions KDP (PDD) et des directions principales (PDDP) pour la division des nœuds: http://scgroup.hpclab.ceid.upatras.gr/faculty/stratis/Papers/tm07book.pdf . En fin de compte, il vous suffit de scinder chaque nœud parent en nœuds enfants relativement bien équilibrés.

Une approche descendante est plus facile à distribuer. Une fois votre premier nœud fractionné, chaque nœud créé peut être envoyé à un processus distribué pour être fractionné à nouveau, etc. Chaque processus distribué doit uniquement connaître le sous-ensemble du jeu de données qu'il est en train de fractionner. Seul le processus parent a connaissance de l'ensemble de données complet.

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

• 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 examine plusieurs algorithmes distribués pour la classification hiérarchique:

  

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

Parunak et al. décrivez un algorithme inspiré par la façon dont les fourmis trient leurs nids:

  

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

Answer 3

Vérifiez cette très lisible si un peu daté examen par Olson (1995) . Depuis, la plupart des journaux exigent des frais d’accès. : -)

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

Answer 4

Vous pouvez également consulter la recherche et l'évaluation de 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é de communautés (modularité graphique).

Answer 5

Vous pouvez regarder une partie du travail effectué avec les cartes auto-organisées (méthode du réseau neuronal de Kohonen) ... les gars de Université de technologie de Vienne ont effectué des travaux sur le calcul distribué de leur algorithme de carte hiérarchique en pleine croissance.

Ceci est un peu à la limite de votre question sur les grappes, donc cela n’aidera peut-être pas, mais je ne peux penser à rien de plus près;)