LSA - Latent Semantic Analysis - Wie es in PHP codieren?

StackOverflow https://stackoverflow.com/questions/1014927

Frage

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

Hier ist, was ich glaube, ich habe zu tun. Ist das richtig? Wie kann ich es in PHP-Code? Wie kann ich feststellen, welche Worte wählen?

Ich will keine externen Bibliotheken verwenden. Ich habe bereits eine Implementierung für die Einzelwertzerlegung (SVD) .

  1. Extrahieren Sie alle Wörter aus dem gegebenen Text.
  2. Gewicht der Worte / Sätze, zum Beispiel mit TF-IDF . Wenn Gewichtung zu komplex ist, nehmen Sie nur die Anzahl der Vorkommen.
  3. eine Matrix aufbauen: Die Säulen sind einige Dokumente aus der Datenbank (je mehr desto besser?), Die Zeilen sind alle eindeutigen Worten, die Werte sind die Zahlen von Ereignissen oder das Gewicht
    4. .
  4. Sie die Einzelwertzerlegung (SVD).
  5. Verwenden Sie die Werte in der Matrix S (SVD), um die Dimensionsreduktion zu tun (wie?).

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

War es hilfreich?

Lösung

LSA Verbindungen:

Dies ist der komplette Algorithmus. Wenn Sie SVD haben, sind Sie die meisten der Weg dorthin. Die Papiere oben erklären es besser als ich.

Annahmen:

  • Ihre SVD-Funktion werden die Einzelwerte und singulären Vektoren in absteigender Reihenfolge geben. Wenn nicht, müssen Sie mehr Akrobatik tun.

M : corpus Matrix, w (Wörter) von d (Dokumente) (w Reihen, d Spalten). Diese können Rohzählungen sein, oder TFIDF oder was auch immer. Stoppwörter können oder auch nicht beseitigt werden und ergeben passieren kann (Landauer sagt Stoppwörter halten und stammen 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 .... das eigentliche LSA Papier schlägt vor, eine gute Näherung für die Basis genügend Vektoren, so dass ihre singulären Werte sind mehr als 50% der Summe der Einzelwerte zu halten ist.

Weitere erschöpfender ... (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 verbessert ‚Suche Kosinusähnlichkeit‘ kann verwendet werden‘, oder Sie können die oberen 3 Worte für jedes Dokument in ihm beispielsweise auswählen. Ob diese yeilds mehr als ein einfacher TF-IDF ist eine Angelegenheit von einiger Debatte.

Für mich LSA führt schlecht in der realen Welt Datensätze wegen Mehrdeutigkeit, und Datensätze mit zu vielen Themen. Es ist mathematisch / probabilistische Basis unsolide ist (es normal-ish (Gaussian) Verteilungen geht davon aus, die keinen Sinn machen machen für Wort zählt).

Ihre Meilenzahl wird auf jeden Fall unterschiedlich sein.

Tagging LSA mit (einer Methode!)

  1. konstruieren, um das U 'Sigma' V‘dimensional reduzierte Matrizen unter Verwendung von SVD und eine Reduktion heuristischen

  2. Mit der Hand, über die Matrix ‚U aussehen, und kommt mit Begriffen, die jedes‚Thema‘zu beschreiben. Wenn zum Beispiel die die größten Teile dieses Vektors sind „Bronx, Yankees, Manhattan“ und dann „New York City“ könnte eine gute Bezeichnung für sie sein. Halten Sie diese in einem assoziativen Array oder einer Liste. Dieser Schritt sollte angemessen sein, da die Anzahl der Vektoren endlich sein wird.

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

Andere Tipps

Diese Antwort ist nicht direkt auf die Frage Poster, sondern auf die Meta-Frage, wie Nachrichten AutoTag. Die OP Nennungen Named Entity Recognition, aber ich glaube, dass sie etwas mehr entlang der Linie der automatischen Tag-Kennzeichnung bedeuten. Wenn sie wirklich NER bedeuten, dann ist diese Antwort ist Quatsch:)

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

  1. Mit der Hand. leicht tun pro Tag diese 600, wahrscheinlich in ein paar Stunden ein Analyst könnte. So etwas wie Amazon Mechanical Turk, oder machen Benutzer tun es könnte auch möglich sein. eine Anzahl von „Hand-Tag“ hat, auch wenn es nur 50 oder 100, ist eine gute Grundlage für den Vergleich, was ist die automatisch generierten Methoden, die Sie unten erhalten.

  2. Dimentionality Reduzierungen, mit LSA, Topic-Modellen (Latent Dirichlet Allocation) und dergleichen .... Ich habe auf reale Datensatz wirklich schlecht Glück mit LSA hatte, und ich bin nicht zufrieden mit seinem statistische Basis. LDA finde ich viel besser und hat eine unglaublich Mailing-Liste, die hat die besten Ideen auf, wie man Themen Texte zuzuordnen.

  3. Einfache Heuristiken ... wenn Sie aktuelle Nachrichten, dann die Struktur des Artikels nutzen. Konzentrieren Sie sich auf den ersten Satz, werfen Sie alle gemeinsamen Wörter (Worte stoppen) und wählen Sie die besten 3 Substantive aus den ersten beiden Sätzen. Oder Heck, nehmen alle Substantive im ersten Satz, und sehen, wohin man bekommt. Wenn die Texte alle in Englisch sind, dann tun Teil der Sprachanalyse auf dem ganzen Kram, und sehen, was, dass man bekommt. Mit strukturierten Produkten, wie Nachrichten, LSA und andere, um unabhängige Methoden (tf-idf) wirft eine Vielzahl von Informationen aus.

Viel Glück!

(wenn Sie diese Antwort, vielleicht die Frage retag es zu passen)

Das ist alles richtig aussieht, bis zum letzten Schritt. Die übliche Schreibweise für SVD ist, dass es gibt drei Matrizen A = USV *. S ist eine Diagonalmatrix (alle Nullen aus der Diagonale bedeutet), dass in diesem Fall gibt im Grunde ein Maß dafür, wie viel jede Dimension erfasst der Originaldaten. Die Zahlen ( „Einzelwerte“) wird nach unten gehen, und Sie können für einen Drop-off sehen, wie viele Dimensionen nützlich sind. Andernfalls werden Sie wollen einfach nur eine beliebige Anzahl N für wählen, wie viele Dimensionen zu nehmen.

Hier bekomme ich ein wenig unscharf. Die Koordinaten der Begriffe (Worte) in der reduzierten Raum-Dimension wird entweder in U oder V, glaube ich, je nachdem, ob sie in den Zeilen oder Spalten der Eingangsmatrix geben. Aus der Hand, glaube ich, die Koordinaten für die Worte werden die Reihen von U. d.h. die ersten Reihe von U zu der ersten Zeile der Eingangsmatrix entspricht, d.h. das erste Wort. Dann nehmen Sie nur die ersten N Spalten dieser Zeile wie das Wort der im reduzierten Raum koordinieren.

HTH

Update:

Dieser Prozess so ist noch nicht sagen Ihnen genau, wie Tags auszuwählen. Ich habe noch nie von jemand mit LSI gehört Tags zu wählen (eine Maschine Lernalgorithmus könnte sein, mehr für die Aufgabe geeignet, wie, sagen wir, Entscheidungsbäume). LSI sagt Ihnen, ob zwei Wörter ähnlich sind. Das ist ein langer Weg-Tags aus zuweisen.

Es gibt zwei Aufgaben- a), was den Satz von Tags zu verwenden? b) wie die besten drei Tags wählen ?. Ich habe nicht viel von einem Gefühl dafür, wie LSI wird Ihnen helfen, zu beantworten (a). Sie können den Satz von Tags von Hand wählen. Aber, wenn Sie LSI verwenden, sollten die Tags wahrscheinlich Worte sein, die in den Dokumenten vorkommen. Dann gilt für (b), möchten Sie die Tags auszuwählen, die in dem Dokument am nächsten Worte. Sie könnten mit ein paar Möglichkeiten, dass die Umsetzung experimentieren. Wählen Sie die drei Tags, die am nächsten zu sind alle Wort im Dokument, in dem der Nähe der Kosinusähnlichkeit gemessen wird (siehe Wikipedia) zwischen dem Tag-Koordinate (die entsprechenden Zeile in U) und das Wort der Koordinate (die entsprechende Zeile in U).

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

Im Einzelnen gibt es einen Link gibt es zu diesem Papier auf Latent Semantic Mapping , die beschreibt, wie die sich daraus ergebenden „Themen“ für einen Text zu erhalten.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top