Verteilte hierarchisches Clustern

Question

Gibt es Algorithmen, die mit hierarchischen Clustering helfen kann? Google-Karte-reduce hat nur ein Beispiel für k-Clustering. Im Falle einer hierarchischen Clustering, ich bin nicht sicher, wie es möglich ist, die Arbeit zwischen den Knoten zu teilen. Andere Ressourcen, die ich gefunden ist: http://issues.apache.org/jira/browse/ MAHOUT-19 Aber es ist nicht ersichtlich, welche Algorithmen verwendet werden.

Answer 1

Als erstes müssen Sie entscheiden, ob Sie Ihre Hierarchie von unten nach oben oder von oben nach unten bauen fahren.

Bottom-up ist hierarchisch angehäufte Bündelung genannt. Hier ist ein einfacher, gut dokumentierte Algorithmus: http: //nlp.stanford.edu/IR-book/html/htmledition/hierarchical-agglomerative-clustering-1.html .

Verteilen eines Bottom-up-Algorithmus ist schwierig, weil jeder verteilte Prozess den gesamten Datensatz zu machen Entscheidungen über entsprechende Cluster benötigt. Es muss auch eine Liste der Cluster auf dem derzeitigen Niveau, so dass es nicht einen Datenpunkt zu mehr als einem Cluster auf dem gleichen Niveau hinzufügt.

Top-down-Hierarchie Konstruktion Divisive Clustering . K-Means eine Option ist, um zu entscheiden, wie Sie Ihre Hierarchie aufzuspalten Knoten. Dieses Papier befasst sich mit K-Mittel und Hauptrichtung Divisive Partitioning (PDDP) für Knoten Splitting: http://scgroup.hpclab.ceid.upatras.gr/faculty/stratis/Papers/tm07book.pdf . Am Ende müssen Sie nur jeden übergeordneten Knoten in relativ gut ausgewogenen Kinderknoten aufzuzuspalten.

Ein Top-down-Ansatz ist einfacher zu verteilen. Nach dem ersten Knoten Split kann jeder Knoten erstellt zu einem verteilten Prozess ausgeliefert werden wieder aufgeteilt werden und so weiter ... Jeder verteilte Prozess muss nur Kenntnis von der Teilmenge des Datensatzes sein, es Splitting ist. Nur der übergeordnete Prozess ist sich der vollständigen Datensatz.

Darüber hinaus könnte jede Spaltung parallel durchgeführt werden. Zwei Beispiele für 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 Bewertungen mehrere verteilte Algorithmen für hierarchisches Clustering:

  

C. F. Olson. „Parallele Algorithmen für   Hierarchical Clustering.“ Parallel   Computing , 21: 1313-1325, 1995, doi: 10.1016 / 0167-8191 (95) 00017-I .

Parunak et al. einen Algorithmus beschreibt inspiriert durch, wie Ameisen ihre Nester sortieren:

  

H. Van Dyke Parunak, Richard Rohwer,   Theodore C. Belding und Sven   Brückner: „Dynamic Dezentrales   Alle Zeit Hierarchical Clustering.“In    Proc. 4. International Workshop on Technik Selbstorganisierende Systeme   (ESOA) 2006 doi: 10.1007 / 978- 3-540-69868-5

Answer 3

Sehen Sie sich diese sehr gut lesbar, wenn etwas veraltet Bewertung von Olson (1995) . Die meisten Papiere da benötigen dann eine Gebühr für den Zugriff. : -)

Wenn Sie R verwenden, empfehle ich versuchen, pvclust das erreicht Parallelität mit Schnee , ein weiteres R-Modul.

Answer 4

Sie können auch Suchen und Auswerten Gemeinschaftsstruktur in Netzwerken von Newman und Girvan, wo sie eine aproach zur Bewertung Gemeinden in Netzwerken (und eine Reihe von Algorithmen, die auf diesem Ansatz basiert) vorzuschlagen und Maß der Netzteilung in Gemeinden Qualität (graph Modularität).

Answer 5

Sie auf einen Teil der Arbeit aussehen könnte werden mit Self-Organizing Maps (Kohonen-neuronales Netz-Methode) ... die Jungs unter TU Wien einige Arbeit auf verteilte Berechnung ihrer wachsenden hierarchischen Karte Algorithmus getan haben.

Dies ist ein wenig am Rande der Clustering-Frage, so kann es nicht helfen, aber ich kann mich nichts näher;)