Ich versuche% zu implementieren co_de% in K means in hadoop-1.0.1 Sprache. Ich bin jetzt frustriert. Obwohl ich eine Github Link von der vollständige Implementierung von co_de%% aber als Neuling in java , ich will, es lernen, ohne dass andere den Code zu kopieren. Ich habe Grundkenntnisse in k means und Hadoop Funktion, die bei hadoop . Kann mir jemand auf die Idee liefert% zu implementieren co_de% map und reduce Klasse. Benötigt es eine Iteration?
Ok, ich gebe Ihnen eine Antwort, was ich bei der Implementierung von k-means in MapReduce dachte. Diese Implementierung unterscheidet sich von der von Mahout, hauptsächlich weil es zeigen soll, wie der Algorithmus in einem verteilten Setup funktionieren kann (und nicht für die reale Produktionsnutzung). Ich nehme auch an, dass Sie wirklich wissen, wie k-means funktioniert.
Nachdem wir das gesagt haben, müssen wir den gesamten Algorithmus in drei Hauptstufen unterteilen:
Die Jobstufe
Die Jobstufe ist ziemlich einfach, sie schreibt die Eingabe (Schlüssel = die Klasse ClusterCenter und Wert = die Klasse VectorWritable ), behandelt die Iteration mit dem Hadoop-Job und liest die Ausgabe des gesamten Jobs .
VectorWritable ist eine serialisierbare Implementierung eines Vektors, in diesem Fall aus meiner eigenen Math-Bibliothek, aber eigentlich nichts anderes als ein einfaches Doppel-Array.
Das ClusterCenter ist hauptsächlich ein VectorWritable , aber mit Komfortfunktionen, die ein Zentrum normalerweise benötigt (zum Beispiel Mittelung).
In k bedeutet, dass Sie eine Reihe von k-Vektoren haben, die Ihre anfänglichen Zentren und einige Eingabevektoren sind, die Sie gruppieren möchten. Das ist in MapReduce genauso, aber ich schreibe sie in zwei verschiedene Dateien. Die erste Datei enthält nur die Vektoren und ein Dummy-Schlüsselzentrum und die andere Datei enthält die wirklichen Anfangszentren (nämlich cen.seq ).
Nachdem alles auf die Festplatte geschrieben wurde, können Sie Ihren ersten Job starten. Dies wird natürlich zuerst ein Mapper starten, was das nächste Thema ist.
Die Kartenebene
In MapReduce ist es immer klug zu wissen, was hereinkommt und was ausgeht (in Bezug auf Objekte).
Also wissen wir von der Job-Ebene, dass wir ClusterCenter und VectorWritable als Eingabe haben, während die ClusterCenter derzeit nur ein Dummy ist. Natürlich wollen wir dasselbe wie die Ausgabe haben, weil die Kartenstufe der berühmte Zuordnungsschritt von normalen k-Mitteln ist.
Sie lesen die Real-Center-Datei, die Sie auf Job-Ebene erstellt haben, in den Speicher, um die Eingabevektoren mit den Zentren zu vergleichen. Daher haben Sie diese Entfernungsmetrik definiert, im Mapper ist sie fest auf ManhattanDistance codiert.
Um etwas genauer zu sein, erhalten Sie einen Teil Ihrer Eingabe in der Map-Phase und dann durchlaufen Sie jedes Eingabe- "Schlüsselwertpaar" (es ist ein Paar oder Tupel bestehend aus Schlüssel und Wert), das mit jedem der Zentren verglichen wird . Hier verfolgen Sie, welcher Mittelpunkt der nächste ist und ordnen ihn dann dem Mittelpunkt zu, indem Sie das nächste ClusterCenter -Objekt zusammen mit dem Eingabevektor selbst auf die Festplatte schreiben.
Ihre Ausgabe ist dann: n-Vektoren mit ihrem zugewiesenen Mittelpunkt (als Schlüssel). Hadoop sortiert und gruppiert jetzt nach Ihrem Schlüssel, sodass Sie jeden zugewiesenen Vektor für ein einzelnes Zentrum in der Reduzierungsaufgabe erhalten.
Die Stufe reduzieren
Wie bereits erwähnt, haben Sie eine ClusterCenter und ihre zugewiesenen VectorWritable in der Reduzierungsstufe.
Dies ist der übliche Update-Schritt, den Sie in normalen k-Means haben. Sie iterieren einfach alle Vektoren, summieren sie und mitteln sie.
Nun haben Sie einen neuen "Mittelwert", den Sie mit dem Mittelwert vergleichen können, den Sie vorher zugewiesen hatten. Hier können Sie einen Unterschied zwischen den beiden Zentren messen, der angibt, wie stark sich das Zentrum bewegt hat. Im Idealfall wäre es nicht umgezogen und converged .
Der Zähler in Hadoop wird verwendet, um diese Konvergenz zu verfolgen. Der Name ist ein bisschen irreführend, weil er tatsächlich verfolgt, wie viele Zentren nicht zu einem Endpunkt konvergiert haben, aber ich hoffe, dass Sie damit leben können .
Im Grunde schreiben Sie jetzt das neue Zentrum und alle Vektoren für die nächste Iteration wieder auf die Festplatte. Außerdem schreiben Sie im Bereinigungsschritt alle neuen erfassten Zentren in den Pfad, der im Kartenschritt verwendet wird, sodass die neue Iteration über die neuen Vektoren verfügt.
Jetzt in der Job-Phase sollte der MapReduce-Job jetzt ausgeführt werden. Jetzt untersuchen wir den Zähler dieses Jobs, um die Anzahl der noch nicht konvergierten Zentren zu ermitteln. Dieser Zähler wird in der while-Schleife verwendet, um festzustellen, ob der gesamte Algorithmus beendet werden kann oder nicht. Ist dies nicht der Fall, kehren Sie erneut zum Absatz Map Level zurück, verwenden Sie jedoch die Ausgabe des vorherigen Jobs als Eingabe.
Eigentlich war das der ganze Voodoo.
Aus offensichtlichen Gründen sollte dies nicht in der Produktion verwendet werden, weil seine Leistung schrecklich ist. Verwenden Sie besser die besser abgestimmte Version von Mahout. Aber für Bildungszwecke ist dieser Algorithmus in Ordnung;)
Wenn Sie weitere Fragen haben, schreiben Sie mir bitte eine Mail oder einen Kommentar.