Clustering hochdimensionaler Daten

8

TL; DR: Wie kann ich bei einem großen Bilddatensatz (ca. 36 GiB Rohpixel) unbeschrifteter Daten die Bilder (basierend auf den Pixelwerten) gruppieren, ohne zunächst die Anzahl der Cluster Kzu kennen?

Ich arbeite derzeit an einem unbeaufsichtigten Lernprojekt, um Bilder zu gruppieren. Stellen Sie sich das als Clustering von MNIST mit 16 x 16 x 3 RGB-Pixelwerten vor, nur dass ich ungefähr 48 Millionen Beispiele habe, die ich zum Clustering benötige. Ohne ihre Identität zu kennen, weiß ich, dass einige der Bilder definitiv verwandt sind, weil sie aus derselben Quelle stammen, aber - sagen wir - ich kenne auch keine geeignete K, um "nur" K-means am Set noch laufen zu lassen .

Ich dachte daran, eine manuelle 2D-Einbettung mit t-SNE durchzuführen und dann manuell im eingebetteten Bereich zu gruppieren (eine einfachere Aufgabe als manuell in 16x16x3-d), aber alle t-SNE-Implementierungen, die ich finden konnte, erforderten das Laden der Daten in den Speicher. Ich habe auch darüber nachgedacht, zuerst t-SNE und dann K-means für die eingebetteten t-SNE-Daten auszuführen. Wenn Sie sich jedoch die Ergebnisse von t-SNE von MNIST ansehen, ist es sehr offensichtlich, dass diese Cluster möglicherweise verzerrt und verzerrt sind und wahrscheinlich werden auf nichtlineare Weise. Selbst wenn ich a kennen Kwürde, würden die Cluster wahrscheinlich aufgeteilt werden. Die Verwendung von Mahalanobis-Entfernungen für K-Mittel mag eine interessante Sache sein, aber da ich zunächst keine Kovarianzen kenne, scheint dies auch eine Sackgasse zu sein.

Derzeit versuche ich, die PCA-Komprimierung für die Beispiele auszuführen, um zumindest etwas Speicher für t-SNE zurückzugewinnen, aber das könnte funktionieren oder nicht ... kann ich vorerst nicht sagen.

Kann mir jemand einen Zeiger in die richtige Richtung geben, um dies zu tun ( idealerweise , aber definitiv nicht erforderlich in einem Python-, TensorFlow- oder Apache Beam / Dataflow-Kontext)? Ich habe vor einiger Zeit daran gearbeitet, ein Streaming / Ball-K-Mittel zu portieren, das die nette Eigenschaft hat, neue Cluster "on demand" zu erstellen, aber bevor ich das wieder in Python / TensorFlow / Dataflow implementiere, hatte ich gehofft, dass es jemand könnte Gib mir einige Ideen, wo ich anfangen soll oder was ich vermeiden soll.

Sonnenseite
quelle
Sind Sie auf k-means eingestellt? Wenn Sie nicht wissen, wie viele Cluster Sie möchten, verwenden Sie eine hierarchische Methode.
MissMonicaE
1
@MissMonicaE Auf keinen Fall auf k-means gesetzt, kam mir nur zuerst in den Sinn. Können Sie mir eine hierarchische Methode geben, die in diesem Zusammenhang sinnvoll wäre?
Sunside
1
Leider sind die einzigen Algorithmen, mit denen ich vertraut bin, AGNES und DIANA, die Unähnlichkeitsmatrizen verwenden (das R-Paket verwendet die Rohdaten, aber ich bin nicht sicher, ob Bilder funktionieren würden - ich habe immer nur einfache numerische Daten geclustert ).
MissMonicaE
2
Probieren Sie dichtebasierte Methoden aus. Sie sind weniger heuristisch als k-means. Ich greife nur dann auf k-means zurück, wenn es sich um ein Spielzeugproblem handelt und wenn die Daten ausschließlich aus einer Normalverteilung stammen. Bitte beziehen Sie sich auf stats.stackexchange.com/questions/133656/…
Jon
1
Ich werde Sie auch auf diese Präsentation auf DBSCAN youtube.com/watch?v=5cOhL4B5waU
Jon

Antworten:

11

Ich glaube nicht eine der Clustering-Techniken "nur" in einem solchen Maßstab funktioniert. Das skalierbarste ist angeblich k-means (verwenden Sie Spark / Mahout nicht, sie sind wirklich schlecht) und DBSCAN (es gibt einige gute verteilte Versionen).

Neben der Skalierung stehen Sie jedoch vor vielen anderen Herausforderungen, da das Clustering schwierig ist . Es ist nicht so, als würde es gerade ausreichen, um den Algorithmus auszuführen, und dann haben Sie Cluster. Clustering ist eine explorative Technik. Es gibt kein "korrektes" Clustering. Stattdessen müssen Sie das Clustering immer wieder ausführen und sich jeden Cluster ansehen . Weil da wird nicht eine einzige Parametereinstellung sein, der alles richtig macht. Stattdessen werden unterschiedliche Cluster möglicherweise nur bei unterschiedlichen Parametern angezeigt.

Die größte Herausforderung in Ihrem Fall ist jedoch wahrscheinlich die Distanzfunktion. Mit Ausnahme idealisierter Einstellungen wie MNIST funktioniert die euklidische Entfernung überhaupt nicht. Auch an den Rohpixeln funktioniert nichts. Sie müssen also zuerst die Feature-Extraktion durchführen und dann eine Ähnlichkeitsfunktion definieren.

Arbeiten Sie beim Clustering mit einem Beispiel . Cluster der Probe identifizieren interessante Cluster, dann denken Sie an einen Weg , um das Etikett auf Ihren gesamten Datensatz zu verallgemeinern. Zum Beispiel durch Klassifizierung (Ihre beschrifteten Datenpunkte sind Ihr Trainingssatz, sagen Sie die Beschriftungen von nicht beschrifteten Punkten voraus).

Hat aufgehört - Anony-Mousse
quelle
0

Wenn Sie versuchen, die Dimensionalität zu reduzieren, sollten Sie Mahout verwenden - es ist erstklassig und das einzige Open-Source-Projekt, das wirklich verteilte Versionen von PCA / SVD anbietet.

http://mahout.apache.org/docs/0.13.1-SNAPSHOT/algorithms/linear-algebra/d-spca.html

http://mahout.apache.org/docs/0.13.1-SNAPSHOT/algorithms/linear-algebra/d-ssvd.html

Mahout hat auch die DBSCAN-Implementierung WIP als Teil eines Google Summer of Code-Projekts, die es wert ist, im Auge behalten zu werden.

Ich vermute, dass Anony's Bemerkung "Mahout is Bad" (ich stimme Spark zu) für die veraltete MapReduce-Version von Mahout relevant ist (da die neue Version K-Means noch nicht sofort implementiert hat, obwohl es eine Diskussion darüber gibt die Mailingliste darüber, wie man das ziemlich einfach macht).

rawkintrevo
quelle