Verteilte k-means im Funken

Question

Ich möchte den K-Means-Algorithmus in Spark implementieren. Ich suche einen Ausgangspunkt und habe gefunden Berkeleys naive Umsetzung. Ist das jedoch verteilt?

Ich meine, ich sehe keine MapReduce -Operationen. Oder macht der Rahmen, wenn er in Spark eingereicht wird, tatsächlich die benötigten Tricks unter der Haube, um den Algorithmus zu verteilen?

_{Ich fand das auch Spark zeigt MapReduce den Ausgang Und ich benutze Spark 1.6.}

---

Bearbeiten: Dieser Code erzeugt einen Laufzeitfehler. Überprüfen Sie hier.

Answer 1

In diesem Link, den Sie gepostet haben, können Sie sich die Python vollständige Lösung ansehen hier Am Ende und gehen Sie durch, um zu sehen, was alles verteilt ist. Kurz gesagt, einige Teile sind verteilt, wie das Lesen von Daten aus der Datei, aber die sehr wichtigen Teile wie die Entfernungsberechnung sind dies nicht.

Rennen, sehen wir:

sc = SparkContext("local[6]", "PythonKMeans")

Dies instanziiert den Kontext und schafft einen lokalen Cluster, dem die Jobs eingereicht werden

lines = sc.textFile(..)

Dies ist noch eingerichtet. Es wurden noch keine Operationen stattgefunden. Sie können dies überprüfen, indem Sie Zeitanweisungen in den Code einlegen

data = lines.map(lambda x: (x.split("#")[0], parseVector(x.split("#")[1])))

Die Lambda hier wird auf Zeilen angewendet, sodass diese Operation die Datei parallel aufteilt. Beachten Sie, dass die tatsächliche Zeile auch a hat cache() am Ende (siehe Zwischenspeicher]). data ist nur ein Hinweis auf das Spark -Objekt im Speicher. (Ich mag hier falsch liegen, aber ich denke, die Operation passiert noch nicht)

count = data.count ()

Dies zwingt die parallele Berechnung, und die Anzahl der zu speichern. Am Ende sind die Referenzdaten weiterhin gültig, und wir werden sie für weitere Berechnungen verwenden. Ich werde hier mit detaillierten Erklärungen aufhören, aber wo immer data Wird verwendet, ist eine mögliche parallele Berechnung. Der Python -Code selbst ist ein einzelnes Gewinde und Schnittstellen mit dem Spark -Cluster.

Eine interessante Zeile ist:

tempdist = sum (np.sum ((Zentroids [x] - y) ** 2) für (x, y) in NewCentroids.Initems ()))

centroids ist ein Objekt im Python -Speicher, wie es ist ist newCentroids. An diesem Punkt werden alle Berechnungen im Speicher durchgeführt (und werden auf den Kunden, In der Regel sind Clients schlank, dh begrenzte Funktionen oder der Kunde ist eine SSH -Shell, sodass die Computerressourcen gemeinsam genutzt werden. Sie sollten idealerweise noch nie Tun Sie hier eine Berechnung), damit keine Parallelisierung verwendet wird. Sie können diese Methode weiter optimieren, indem Sie diese Berechnung parallel durchführen. Idealerweise möchten Sie, dass das Python -Programm niemals direkt mit den Werten von individuellen Punkten $ $ und $ y $ verarbeitet.

Answer 2

Ich weiß nichts über diese spezifische Implementierung, aber wir verwenden die Mllib K-Means Hier bei meiner Arbeit, zu einem gewissen Erfolg. Es ist verteilt und läuft auf Spark!