Effektives Clustering einer Ähnlichkeitsmatrix

Question

Mein Thema ist Ähnlichkeit und Clustering von (einem Bündel von) Text (en). Auf den Punkt gebracht: Ich möchte gesammelte Texte zusammenfassen und sie sollten am Ende in sinnvollen Clustern erscheinen. Um dies zu tun, ist mein Ansatz wie folgt, mein Problem ist das Clustering. Die aktuelle Software ist in PHP geschrieben.

1) Ähnlichkeit: Ich behandle jedes Dokument als "Bag-of-words" und wandele Wörter in Vektoren um. Ich verwende

• Filterung (nur "real" words)
• tokenization (split Sätze in Wörter)
• herrühren (reduzieren Worten auf ihre Grundform; Porter stemmer)
• Beschneiden (Schnitt von Wörtern mit zu hoch & niedrige Frequenz)

als Methoden zur Dimensionsreduzierung. . Danach habe ich Kosinusähnlichkeit bin mit (wie auf verschiedenen Websites im Internet and here vorgeschlagen/beschrieben

Das Ergebnis ist dann eine Ähnlichkeitsmatrix wie folgt aus:

 A B C D E 
    A 0 30 51 75 80 
    B X 0 21 55 70 
    C X X 0 25 10 
    D X X X 0 15 
    E X X X X 0 

A ... E sind meine Texte und die Zahl ist die Ähnlichkeit in Prozent, je höher, desto ähnlicher sind die Texte, weil sim (A, B) == sim (B, A) nur die Hälfte der Matrix ausgefüllt ist. Also die Ähnlichkeit von Text A zu Text D ist 71%.

Ich möchte jetzt eine a priori unbekannte (!) Anzahl von Clustern aus dieser Matrix generieren.Die Cluster sollten die ähnlichen Elemente darstellen (bis zu einem bestimmten Stopp p Kriterium) zusammen.

habe ich versucht, eine grundlegende Implementierung selbst, die im Grunde wie dieses (60% als feste Ähnlichkeitsschwelle) war

foreach article 
     get similar entries where sim > 60 
       foreach similar entry 
       check if one of the entries already has a cluster number 
       if no: assign new cluster number to all similar entries 
       if yes: use that number 

Es funktionierte (irgendwie), aber es war überhaupt nicht gut und die Ergebnisse waren oft Monster-Cluster. Also, ich möchte das wiederholen und habe bereits alle Arten von Clustering-Algorithmen untersucht, aber ich bin mir immer noch nicht sicher, welche am besten funktionieren wird. Ich denke, es sollte ein agglomerativer Algorithmus sein, weil jedes Textpaar am Anfang als Cluster betrachtet werden kann. Aber immer noch sind die Fragen, was das Stopp-Kriterium ist und ob der Algorithmus existierende Cluster teilen und/oder zusammenführen soll.

Entschuldigung, wenn einige der Sachen einfach scheinen, aber ich bin auf diesem Gebiet relativ neu. Danke für die Hilfe.

Answer 1

Probieren Sie einfach einige. Es gibt so viele Clustering-Algorithmen, niemand wird sie alle kennen. Außerdem hängt es sehr stark von Ihrem Datensatz und der vorhandenen Clusterstruktur ab. Am Ende kann es auch nur diesen einen Monstercluster in Bezug auf Kosinusabstand und BofW-Merkmale geben.

Answer 2

Da Sie beide neu auf dem Gebiet sind, eine unbekannte Anzahl von Clustern haben und bereits Cosinus-Distanz verwenden, würde ich den FLAME Clustering-Algorithmus empfehlen.

Es ist intuitiv, einfach zu implementieren und Implementierungen in einer großen Anzahl von Sprachen (nicht PHP, vor allem, weil sehr wenige Leute PHP für Data Science verwenden).

Nicht zu vergessen, es ist tatsächlich gut genug, um von einer großen Anzahl von Menschen in der Forschung verwendet werden.Wenn Sie sonst nichts wissen, was genau die Mängel in diesem Cluster-Algorithmus sind, den Sie ansprechen wollen, wenn Sie auf einen anderen gehen.

Answer 3

Vielleicht können Sie Ihre Ähnlichkeitsmatrix in eine Unähnlichkeitsmatrix transformieren, wie zum Beispiel x zu 1/x transformieren, dann besteht Ihr Problem darin, eine Unähnlichkeitsmatrix zu gruppieren. Ich denke, der hierarchische Cluster könnte funktionieren. Diese können Ihnen helfen: hierarchical clustering und Clustering a dissimilarity matrix