Existe-t-il des algorithmes qui peuvent aider au clustering hiérarchique ? Le map-reduce de Google ne propose qu'un exemple de k-clustering. Dans le cas du clustering hiérarchique, je ne sais pas comment il est possible de 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 il n'est pas évident de savoir quels algorithmes sont utilisés.
Réponses
Trop de publicités?
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 est appelée regroupement 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 des données pour choisir les clusters appropriés. Il a également besoin d'une liste des clusters à son niveau actuel afin de ne pas ajouter un point de données à plus d'un cluster au même niveau.
La construction d'une hiérarchie descendante est appelée Regroupement divisé . K-means est une option pour décider de la manière de diviser les nœuds de votre hiérarchie. Cet article examine les méthodes K-means et PDDP (Principal Direction Divisive Partitioning) pour la division des nœuds : http://scgroup.hpclab.ceid.upatras.gr/faculty/stratis/Papers/tm07book.pdf . Au final, il suffit de diviser chaque nœud parent en nœuds enfants relativement bien équilibrés.
Une approche descendante est plus facile à distribuer. Après votre premier fractionnement de nœuds, chaque nœud créé peut être envoyé à un processus distribué pour être à nouveau fractionné et ainsi de suite... Chaque processus distribué ne doit connaître que le sous-ensemble de l'ensemble de données qu'il divise. Seul le processus parent est au courant de l'ensemble des données.
En outre, chaque fractionnement peut être effectué en parallèle. Deux exemples pour k-means :
Vebjorn Ljosa
Points
6215
Clark Olson passe en revue plusieurs algorithmes distribués pour le clustering hiérarchique :
C. F. Olson. "Algorithmes parallèles pour le Hierarchical Clustering". Parallèle Calculs parallèles , 21:1313-1325, 1995, doi:10.1016/0167-8191(95)00017-I .
Parunak et al. décrivent un algorithme inspiré de la façon dont les fourmis trient leurs nids :
H. Van Dyke Parunak, Richard Rohwer, Theodore C. Belding,et Sven Brueckner : "Dynamic Decentralized Any-Time Hierarchical Clustering". Any-Time Hierarchical Clustering". Dans Proc. 4e Atelier international sur l'ingénierie des systèmes auto-organisés (ESOA) , 2006, doi:10.1007/978-3-540-69868-5
bubaker
Points
1680
Consultez ce document très lisible, même s'il date un peu. revue par Olson (1995) . Depuis, la plupart des journaux sont payants :-)
Si vous utilisez R, je vous recommande d'essayer pvclust qui réalise le parallélisme en utilisant neige un autre module R.
jingerbread
Points
11
Vous pouvez également voir Trouver et évaluer la structure des communautés 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 qualité de la division du réseau en communautés (modularité du graphe).
Jaykul
Points
6484
Vous pourriez examiner certains des travaux réalisés avec les cartes auto-organisatrices (méthode des réseaux neuronaux de Kohonen)... les gars de l'Institut de l'informatique et des télécommunications de l'Université du Michigan (IUFM). Université de technologie de Vienne ont effectué des travaux sur le calcul distribué de leur algorithme de carte hiérarchique croissante.
C'est un peu à la limite de votre question sur le regroupement, donc cela ne vous aidera peut-être pas, mais je ne vois rien de plus proche ;)
