Mein Thema ist Ähnlichkeit und Clustering von (einer Reihe von) Text (en). Kurz gesagt: Ich möchte gesammelte Texte zu Clustern zusammenfassen und sie sollten am Ende in aussagekräftigen Clustern erscheinen. Dafür ist mein bisheriger Ansatz wie folgt, mein Problem liegt im Clustering. Die aktuelle Software ist in PHP geschrieben.

1) Ähnlichkeit: Ich behandle jedes Dokument als "Wortsack" und wandle Wörter in Vektoren um. ich benutze

Filterung (nur "echte" Wörter)Tokenisierung (Sätze in Wörter aufteilen)stemming (Wörter auf ihre Grundform reduzieren; Porter's Stemmer)Beschneiden (Schneiden von Wörtern mit zu hoher und zu niedriger Frequenz)

als Methoden zur Dimensionsreduktion. Danach verwende ich Cosinus-Ähnlichkeit (wie auf verschiedenen Websites im Web vorgeschlagen / beschrieben)und hier.

Das Ergebnis ist dann eine Ähnlichkeitsmatrix wie diese:

<code>        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
</code>

A… E sind meine Texte und die Zahl ist die Ähnlichkeit in Prozent; Je höher, desto ähnlicher sind die Texte. Da sim (A, B) == sim (B, A) nur die Hälfte der Matrix ausfüllt, beträgt die Ähnlichkeit von Text A zu Text D 71%.

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

Ich habe selbst eine grundlegende Implementierung ausprobiert, die im Grunde genommen so war (60% als feste Ähnlichkeitsschwelle).

<code>    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
</code>

Es funktionierte (irgendwie), war aber überhaupt nicht gut und die Ergebnisse waren oft Monster-Cluster. Ich möchte dies wiederholen und habe bereits alle Arten von Clustering-Algorithmen untersucht, bin mir aber immer noch nicht sicher, welche am besten funktionieren wird. Ich denke, es sollte ein agglomerativer Algorithmus sein, da jedes Textpaar am Anfang als Cluster angesehen werden kann. Es bleibt jedoch die Frage, was das Stoppkriterium ist und ob der Algorithmus vorhandene Cluster teilen und / oder zusammenführen soll.

Es tut mir leid, wenn ein Teil des Materials grundlegend erscheint, aber ich bin in diesem Bereich relativ neu. Danke für die Hilfe.