Welchen Algorithmus sollte ich verwenden, um einen großen binären Datensatz in wenige Kategorien zu gruppieren?

11

Ich habe eine große (650K Zeilen * 62 Spalten) Matrix von Binärdaten (nur 0-1 Einträge). Die Matrix ist meist spärlich: ca. 8% sind gefüllt.

Ich möchte es in 5 Gruppen gruppieren - sagen wir von 1 bis 5. Ich habe es mit hierarchischem Clustering versucht und es konnte die Größe nicht verarbeiten. Ich habe auch einen auf Hamming-Distanz basierenden k-Means-Clustering-Algorithmus verwendet, der die 650K-Bitvektoren der Länge 62 berücksichtigt. Mit keinem dieser Vektoren habe ich die richtigen Ergebnisse erzielt.

Bitte helfen Sie.

clustering dataset k-means binary-data Ungebunden26
quelle
Ich kann b / c meiner 1 Wiederholung nicht kommentieren, daher musste ich dies als Antwort eingeben. Sie könnten sich mit Jaccard-Ähnlichkeit befassen. Ich denke, Python Scipy hat Implementierungen davon. Jaccard ...
Gobrewers14
Gibt es einen Grund anzunehmen, dass die Daten natürlich zumindest teilweise in fünf Gruppen fallen? Interessieren Sie sich wirklich für das Zeilenclustering oder interessieren Sie sich auch für Beziehungen zwischen den 62 Merkmalen, die in den Bitvektoren codiert sind? Wenn letzteres der Fall ist, sind andere Techniken besser geeignet.
Micans

Antworten:

4

Sie stellen die falsche Frage.

Anstatt zu fragen, "welcher Algorithmus", sollten Sie fragen, "welche Kategorie / welcher Cluster in Ihrer Anwendung sinnvoll ist ".

Ich bin nicht überrascht, dass die oben genannten Algorithmen nicht funktioniert haben - sie sind für sehr unterschiedliche Anwendungsfälle konzipiert. k-means funktioniert nicht mit beliebigen anderen Abständen. Verwenden Sie es nicht mit Hamming-Abstand. Es gibt einen Grund, warum es k- means heißt. Es ist nur dann sinnvoll, wenn das arithmetische Mittel aussagekräftig ist (was nicht für Binärdaten gilt).

Vielleicht möchten Sie stattdessen k-Modi ausprobieren. IIRC ist eine Variante, die eigentlich für kategoriale Daten gedacht ist, und binäre Daten sind etwas kategorial (aber Sparsity kann Sie trotzdem töten).

Aber haben Sie zuerst Duplikate entfernt , um Ihre Daten zu vereinfachen, und beispielsweise eindeutige / leere Spalten entfernt?

Vielleicht sind APRIORI oder ähnliche Ansätze auch für Ihr Problem sinnvoller.

In jedem Fall müssen Sie zuerst herausfinden, was Sie benötigen, und dann, welcher Algorithmus diese Herausforderung lösen kann. Arbeiten Sie datengesteuert , nicht indem Sie zufällige Algorithmen ausprobieren.

Hat aufgehört - Anony-Mousse
quelle
Können Sie bitte erklären, warum "Nicht mit Hamming-Distanz verwenden"? Es könnte Sinn machen, schließlich ist es in Matlab verfügbar. Es macht mir nichts aus, eine neue Frage zu stellen, wenn es Sinn macht.
Dror Atariah
Wegen des Mittelwerts. Das arithmetische Mittel ist bei Hamming-Distanz oder Binärdaten bedeutungslos. Verwenden Sie stattdessen den Modus oder das Medoid .
Hat aufgehört - Anony-Mousse
Nur um sicherzugehen, dass ich es richtig mache: matlab verwendet das arithmetische Mittel, wenn die Zentroide aktualisiert werden, wenn das k-Mittel zusammen mit der Hamming-Metrik verwendet wird. Ist das richtig? Was ist der richtige Weg, um diese Metrik in Matlab zu verwenden?
Dror Atariah
k-means heißt k- means, weil es den Mittelwert verwendet. Ansonsten nennt man es k-Medoide, k-Modi usw. Der Mittelwert ist gut für L2 - Summe der quadratischen Abweichungen.
Hat aufgehört - Anony-Mousse
Matlab verwendet also k- means zusammen mit der Hamming-Metrik. das macht nicht viel Sinn.
Dror Atariah
3

Vielleicht bin ich mit der Antwort etwas spät dran, aber wahrscheinlich wäre es für einen Körper in Zukunft nützlich.

Die adaptive Resonanztheorie ist ein guter Algorithmus für binäre Klassifizierungsprobleme. Informieren Sie sich über ART 1. Weitere Informationen finden Sie im kostenlosen Buch Neural Network Design in Kapitel 19.

Dieses Netzwerk kombiniert eine großartige biologische Idee mit einer guten mathematischen Implementierung. Auch dieser Algorithmus ist einfach zu implementieren und in diesem Buch finden Sie auch schrittweise Anweisungen zum Erstellen dieses Klassifikators.

itdxer
quelle
2

Ein klassischer Algorithmus für das Clustering binärer Daten ist das Bernoulli-Mischungsmodell. Das Modell kann mit Bayes'schen Methoden und auch mit EM (Expectation Maximization) angepasst werden. Sie finden Beispiel-Python-Code überall im GitHub, während ersterer leistungsfähiger, aber auch schwieriger ist. Ich habe eine C # -Implementierung des Modells auf GitHub (verwendet Infer.NET, das eine restriktive Lizenz hat!).

Das Modell ist ziemlich einfach. Probieren Sie zuerst den Cluster aus, zu dem ein Datenpunkt gehört. Probieren Sie dann unabhängig von so vielen Bernoullis, wie Sie Dimensionen in Ihrem Datensatz haben. Beachten Sie, dass dies eine bedingte Unabhängigkeit der Binärwerte für den Cluster impliziert!

In der Bayes'schen Umgebung ist die vorherige Über-Cluster-Zuweisung eine Dirichlet-Verteilung. Dies ist der richtige Ort, um Prioritäten zu setzen, wenn Sie glauben, dass einige Cluster größer sind als andere. Für jeden Cluster müssen Sie zuvor eine Beta-Distribution für jede Bernoulli-Distribution angeben. Typischerweise ist dieser Prior Beta (1,1) oder Uniform. Vergessen Sie nicht, die Clusterzuweisungen zufällig zu initialisieren, wenn Daten angegeben werden. Dadurch wird die Symmetrie unterbrochen und der Sampler bleibt nicht hängen.

Es gibt einige coole Features des BMM-Modells in Bayes'scher Umgebung:

  1. Online-Clustering (Daten können als Stream ankommen)

  2. Das Modell kann verwendet werden, um auf die fehlenden Abmessungen zu schließen

Der erste ist sehr praktisch, wenn der Datensatz sehr groß ist und nicht in den Arbeitsspeicher eines Computers passt. Die zweite kann bei allen Arten von fehlenden Datenimputationsaufgaben verwendet werden, z. Eingabe der fehlenden Hälfte des binären MNIST-Bildes.

Vladislavs Dovgalecs
quelle