LSA - Latente semantische Analyse - Wie man es in PHP programmiert?

Question

Ich möchte Latent Semantic Analysis (LSA) in PHP implementieren, um Themen/Tags für Texte zu finden.

Hier ist, was ich denke, ich muss tun. Ist das korrekt? Wie kann ich es in PHP codieren? Wie bestimme ich, welche Wörter ich wählen soll?

Ich möchte keine externen Bibliotheken verwenden. I've already an implementation for the Singular Value Decomposition (SVD).

1. Alle Wörter aus dem angegebenen Text extrahieren.
2. Gewicht der Wörter/Phrasen, z.B. mit tf–idf. Wenn die Gewichtung zu komplex ist, nehmen Sie einfach die Anzahl der Vorkommen.
3. Erstellen Sie eine Matrix: Die Spalten sind einige Dokumente aus der Datenbank (je mehr desto besser?), Die Zeilen sind alle eindeutige Wörter, die Werte sind die Nummern der Vorkommen oder das Gewicht.
4. Tun Sie die Singular Value Decomposition (SVD).
5. Verwenden Sie die Werte in der Matrix S (SVD), um die Dimensionsreduktion durchzuführen (wie?).

Ich hoffe, Sie können mir helfen. Vielen Dank im Voraus!

Answer 1

LSA Verbindungen:

• Landauer (co-creator) article on LSA
• the R-project lsa user guide

ist die komplette Algorithmus. Wenn du SVD hast, bist du am meisten da. Die obigen Papiere erklären es besser als ich.

Annahmen:

• Ihre SVD-Funktion werden die Einzelwerte und singulären Vektoren in absteigender Reihenfolge geben. Wenn nicht, musst du mehr Akrobatik machen.

M: corpus Matrix, w (Wörter) von d (Dokumente) (w Reihen, d Spalten). Dies können rohe Zahlen oder Tfidf oder was auch immer sein. Stoppwörter können oder können nicht eliminiert werden, und Stemming kann passieren (Landauer sagt halt Stoppwörter und stagnieren nicht, aber ja zu tfidf).

U,Sigma,V = singular_value_decomposition(M) 

U: w x w 
Sigma: min(w,d) length vector, or w * d matrix with diagonal filled in the first min(w,d) spots with the singular values 
V: d x d matrix 

Thus U * Sigma * V = M 
# you might have to do some transposes depending on how your SVD code 
# returns U and V. verify this so that you don't go crazy :) 

Dann wird die reductionality .... die tatsächliche schlägt LSA Papier eine gute Näherung für die Basis genug Vektoren, so dass ihre Singulärwerte sind mehr als 50% der Gesamtfläche der Singulärwerte zu behalten ist.

Mehr erschöpfende ... (Pseudo-Code)

Let s1 = sum(Sigma). 
total = 0 
for ii in range(len(Sigma)): 
    val = Sigma[ii] 
    total += val 
    if total > .5 * s1: 
     return ii 

Dies wird den Rang der neuen Basis zurückkehren, das war min (d, w) vor, und wir werden jetzt ungefähre mit {ii}.

(hier '-> Prime, nicht transponieren)

Wir schaffen neue Matrizen: U', Sigma 'V', mit Größen w x ii, ii x ii und ii x d.

Das ist die Essenz des LSA-Algorithmus.

Diese resultierende Matrix U '* Sigma' * V 'kann für eine' verbesserte 'Kosinusähnlichkeitssuche verwendet werden, oder Sie können zum Beispiel die oberen drei Wörter für jedes Dokument auswählen. Ob dies mehr als ein einfacher Tf-IDF ist, ist eine Frage der Debatte.

Für mich funktioniert LSA schlecht in realen Datensätzen aufgrund von Polysemie und Datensätzen mit zu vielen Themen. Ihre mathematische/probabilistische Basis ist nicht richtig (sie nimmt normal-ish (Gaußsche) Verteilungen an, was für Wortzählungen nicht sinnvoll ist).

Ihre Laufleistung wird definitiv variieren.

Tagging LSA verwendet (ein Verfahren!)

1. Konstrukt des U 'Sigma' V‘dimensional reduzierte Matrizen unter Verwendung von SVD und eine Reduktion heuristische

2. Von Hand, Blick über die U 'Matrix, und kommen Sie mit Begriffen, die jedes "Thema" beschreiben. Zum Beispiel, wenn die größten Teile dieses Vektors "Bronx, Yankees, Manhattan" waren, dann könnte "New York City" ein guter Ausdruck dafür sein. Behalte diese in einem assoziativen Array oder einer Liste. Dieser Schritt sollte vernünftig sein, da die Anzahl der Vektoren endlich sein wird.

3. Angenommen, Sie haben einen Vektor (v1) von Wörtern für ein Dokument, dann liefert v1 * t (U ') die stärksten' Themen 'für das Dokument. Wählen Sie die 3 höchsten und geben Sie ihre "Themen" wie im vorherigen Schritt berechnet.

Answer 2

Das alles sieht gut aus, bis zum letzten Schritt. Die übliche Schreibweise für SVD ist, dass sie drei Matrizen A = USV * zurückgibt. S ist eine Diagonalmatrix (dh alle Nullstellen außerhalb der Diagonalen), die in diesem Fall im Prinzip ein Maß dafür angibt, wie viel jede Dimension von den Originaldaten erfasst. Die Zahlen ("singuläre Werte") werden sinken, und Sie können nach einer Drop-off-Zahl für die Anzahl der nützlichen Dimensionen suchen. Andernfalls möchten Sie einfach eine beliebige Zahl N für die Anzahl der zu verwendenden Dimensionen auswählen.

Hier bekomme ich ein wenig verschwommen. Die Koordinaten der Begriffe (Wörter) im reduzierten Raum sind entweder in U oder V, ich denke, je nachdem, ob sie sich in den Zeilen oder Spalten der Eingabematrix befinden. Aus der Ferne denke ich, dass die Koordinaten für die Wörter die Zeilen von U sein werden. Das heißt, die erste Zeile von U entspricht der ersten Zeile der Eingabematrix, d. H. Dem ersten Wort. Dann nehmen Sie einfach die ersten N Spalten dieser Reihe als die Koordinate des Wortes im reduzierten Raum.

HTH

Update:

Dieser Prozess so ist noch nicht genau sagen, wie Tags auszuwählen. Ich habe noch nie von jemandem gehört, der LSI verwendet, um Tags auszuwählen (ein maschineller Lernalgorithmus könnte für die Aufgabe besser geeignet sein, wie etwa Entscheidungsbäume). LSI sagt Ihnen, ob zwei Wörter ähnlich sind. Das ist ein langer Weg von der Zuordnung von Tags.

Es gibt zwei Aufgaben: a) Was sind die zu verwendenden Tags? b) Wie wählt man die besten drei Tags ?. Ich habe nicht viel Ahnung davon, wie LSI Ihnen bei der Beantwortung helfen wird (a). Sie können den Satz von Tags manuell auswählen. Wenn Sie jedoch LSI verwenden, sollten die Tags wahrscheinlich Wörter sein, die in den Dokumenten vorkommen. Für (b) möchten Sie dann die Tags auswählen, die Wörtern am nächsten sind, die im Dokument gefunden werden. Sie könnten mit ein paar Möglichkeiten experimentieren, dies zu implementieren. Wählen Sie die drei Tags, die am nächsten an any Wort im Dokument sind, wo die Nähe durch die Kosinusähnlichkeit (siehe Wikipedia) zwischen der Koordinate des Tags (die Zeile in U) und der Koordinate des Wortes (die Zeile in U) gemessen wird.

Answer 3

Diese Antwort bezieht sich nicht direkt auf die Frage des Posters, sondern auf die Meta-Frage, wie man Nachrichten autotagieren kann.Das OP erwähnt die Named Entity Recognition, aber ich glaube, dass sie etwas mehr im Sinne des Autotagging bedeuten. Wenn sie wirklich NER bedeuten, dann ist diese Antwort hogwash :)

In Anbetracht dieser Einschränkungen (600 Artikel/Tag, 100-200 Zeichen/Stück) mit divergierenden Quellen, hier sind einige Tagging-Optionen:

1. Von Hand. Ein Analyst könnte leicht 600 davon pro Tag machen, wahrscheinlich in ein paar Stunden. Etwas wie Amazon Mechanical Turk, oder machen Benutzer es tun, könnte auch machbar sein. Eine gewisse Anzahl von "hand-tagged" zu haben, auch wenn es nur 50 oder 100 ist, wird eine gute Grundlage sein, um zu vergleichen, was auch immer die autogenerierten Methoden Ihnen bringen.

2. Dimentionalität Reduktionen, mit LSA, Topic-Modelle (Latent Dirichlet Allocation) und dergleichen .... Ich hatte wirklich wenig Glück mit LSA auf realen Daten-Sets und ich bin unzufrieden mit seinen statistischen Basis. LDA Ich finde viel besser, und hat eine incredible mailing list, die am besten darüber nachdenkt, wie Themen zu Texten zugeordnet werden.

3. Einfache Heuristiken ... Wenn Sie aktuelle Nachrichten haben, dann nutzen Sie die Struktur der Nachricht aus. Konzentriere dich auf den ersten Satz, wähle alle gängigen Wörter aus (Stoppwörter) und wähle die besten 3 Substantive aus den ersten beiden Sätzen aus. Oder hack, nimm alle Substantive im ersten Satz und sieh, wo dich das hinbringt. Wenn die Texte alle in Englisch sind, dann führe einen Teil der Sprachanalyse über den ganzen Shebang durch und sieh, was dich davon anspricht. Mit strukturierten Elementen, wie Nachrichten, wirft LSA und andere auftragsunabhängige Methoden (tf-idf) eine Menge Informationen aus.

Viel Glück!

(wenn Sie diese Antwort, retag vielleicht die Frage, um es fit)

Answer 4

Es gibt ein zusätzliches SO auf die Gefahren fädeln diese bei link text in PHP alle tun.

Speziell gibt es einen Link zu diesem Papier auf Latent Semantic Mapping, die beschreibt, wie Sie die resultierenden "Themen" für einen Text erhalten.