K-Means Clustering Paritioning

Question

Ich benutze Matlab und ich habe diese sehr sehr große .mat Datei namens MeansOfK, die fast 5.000.000 x N enthält. Meine Testdaten bestehen aus Auto und Nicht-Auto. Mein Problem ist, dass wenn ich k-Mittel zu den MeansofK verwende. Es hat immer keinen Speicher mehr.

[idx, ctr] = kmeans(MeansOfK , k, 'Distance', 'sqEuclidean'); 

Meine Optionen sind

1.i die Kluft verwenden und Technik erobern, wobei ich das Auto und nicht-Auto auf kleinere Partitionen aufzuteilen und in k-Mittel setzen.

2.Ich separiere die Auto- und Nicht-Auto-Klassen und versuche, beide Klassen k-means zu verwenden.

die endgültige Ausgabe wäre die kombinierten Klassen von Auto oder Nicht-Auto. aus dem K-Means-Prozess.

so meine Frage ist?

Ist was mach ich machbar? Wird es die Ausgabe meiner k-Mittel beeinflussen, wenn ich die Datei partitioniere anstatt sie als Ganzes zu machen?

Vorschläge und Antworten sind immer willkommen :) Dank

Answer 1

Was Sie tun können, können Sie die Ergebnisse von Johnson-Lindenstrauss lemma nutzen, wo Sie Ihr Dataset in den unteren Dimensionsbereich einbetten und wenn Sie die Kmeans-Berechnung für kleinere Datasets durchführen. wenn Sie Datenmatrix zum Beispiel ist A die Sie tun können:

% N is the number of data points and s is the reduced dimension 
S = randn (N, s)/s q r t (s) ; 
C = A ∗ S ; 

% now you can do you kmeans computation on C 
[idx, ctr] = kmeans(MeansOfK , k, 'Distance', 'sqEuclidean'); 

Grundsätzlich können Sie idx und ctr Ergebnisse für Originaldaten verwenden, die Ihnen (1 + epsilon) Annäherung. Auch können Sie bessere Ergebnisse basierend auf Arbeit von Dan Feldman erreichen, die im Grunde sagt, dass Sie SVD auf Ihren Daten berechnen und auf k/epsilon-Engine-Werte projizieren können, um den Kmeans-Wert zu berechnen und (1 + Epsilon) -Approximation zu erhalten.

---

UPDATE

Basierend auf Kommentar, den ich coresets Ansatz zu nutzen, wiederum bezogen auf das Papier von Dan Feldman bei el, Turning Big Data Into Tiny Data vorschlagen möchten. Die Techniken bieten die Möglichkeit, große Datenmengen in kleinere zu reduzieren, wobei eine garantierte (1 + Epsilon) Näherung für die optimale kmeans-Lösung gewährleistet ist. Darüber hinaus können Sie mit der Erstellung von Streaming-Kernsätzen fortfahren, mit der Sie die O(logn * epsilon) Approximation beibehalten können, während Sie Daten streamen (Abschnitt 10, Abbildung 3), z. in Ihrem Fall in kleinere Stücke aufteilen. Wenn Sie schließlich kmeans Berechnung auf dem resultierenden Kernsatz ausführen können.

Auch Sie könnten wahrscheinlich in Betracht ziehen, einen Blick in meine jüngsten publication zu erhalten, um Details zu erfahren, wie Sie mit Ihrem Fall umgehen. Hier finden Sie auch eine Referenz in meinem github account, wenn Sie es verwenden möchten.

Answer 2

würde ich Ihre einzige wirkliche Option sagen, wenn nicht möglich, Speicher zu erhöhen, ist, die Daten in kleinere Gruppen aufzuteilen. Als ich ein Big-Data-Projekt mit kollaborativen Filteralgorithmen durchführte, haben wir uns mit Mengen von bis zu 700 Millionen + beschäftigt und immer, wenn wir den Speicher voll ausgelastet hatten, mussten wir die Daten in kleinere Mengen aufteilen und die Algorithmen separat ausführen.