Wie kann ich Zeichenfolgen nach gemeinsamen Themen gruppieren?

10

Ich versuche zum Beispiel, Strings über das Programmieren mit anderen Strings über das Programmieren, Strings über die Physik mit anderen Strings über die Physik usw. für eine breite Palette von Themen zu gruppieren. Trotz des krassen theoretischen sprachlichen Aspekts des Problems möchte ich dies tatsächlich mit Programmierung / Software tun.

Der Überblick: Wie würde ich bei einer großen Anzahl von Zeichenfolgen vorgehen, um sie nach semantischen Themen zu gruppieren?

Die besondere Anwendung: Ich habe ~ 200.000 Trivia-Fragen, die ich in allgemeine Gruppierungen einteilen möchte (Autos, Computer, Politik, Kanada, Essen, Barack Obama usw.).

Was ich mir angesehen habe: Wikipedia hat eine Liste von Toolkits für die Verarbeitung natürlicher Sprache (vorausgesetzt, ich versuche tatsächlich, NLP zu nennen), also habe ich mir einige angesehen, aber keine scheint etwas Ähnliches zu meinen Bedürfnissen zu tun.

Anmerkungen: Es wurde darauf hingewiesen, dass hierfür zusätzliche Kenntnisse erforderlich sind (z. B. ein Porsche als Auto, C ++ als Programmiersprache). Ich gehe dann davon aus, dass Trainingsdaten benötigt werden, aber wenn ich nur die Liste der Fragen und Antworten habe, wie kann ich Trainingsdaten generieren? Und wie verwende ich dann Trainingsdaten?

Weitere Hinweise: Wenn die aktuelle Formatierung meiner Fragen und Antworten hilft (obwohl es wie JSON aussieht, handelt es sich im Grunde genommen um eine Rohtextdatei):

// row 1: is metadata
// row 2: is a very specific kind of "category"
// row 3: is the question
// row 4: is the answer
{
  15343
  A MUSICAL PASTICHE
  Of classical music's "three B's", he was the one born in Hamburg in 1833
  Johannes Brahms
}

Bevor jedoch jemand darauf hinweist, dass es bereits eine Kategorie gibt, beachten Sie, dass es ~ 200.000 Fragen und Antworten wie diese und im Grunde ebenso viele "Kategorien" gibt. Ich versuche, diese in breitere Gruppen wie die oben aufgeführten zu gruppieren. Auch diese Formatierung kann für alle Fragen sehr einfach geändert werden, ich mache es programmgesteuert.

Und noch mehr Anmerkungen: Ich weiß eigentlich nicht, wie viele Kategorien ich brauche (mindestens 10-20), weil ich nicht alle Fragen selbst durchgelesen habe. Ich hatte teilweise erwartet, dass die endliche Zahl während der Kategorisierung irgendwie bestimmt wird. In jedem Fall kann ich immer manuell eine Reihe von Kategorien erstellen.

Whymarrh
quelle
Wie haben Sie Karotten verwendet? Aus meiner kurzen Lektüre geht hervor, dass es leicht sein sollte, 200.000 Datensätze zu verarbeiten.
Es dauerte nur viel länger als ich dachte und zwang mich, die anfängliche Speicherzuweisung der JVM auf 1024 m und den maximalen Speicher auf 2048 m zu erhöhen. Es war nicht so schlimm, wie ich es vielleicht gemacht habe.
Sie benötigen nur genügend Trainingsdaten und sollten dann in der Lage sein, die Fragen in diese Kategorien einzuteilen. Ein vollautomatischer Ansatz wird sie wahrscheinlich auf andere Weise gruppieren, z. B. bei Fragen, die das Wort "Auto" enthalten. Sie können Synonyme nicht gleichzeitig mit dem Erstellen einer Gruppierung lernen.
Hat aufgehört - Anony-Mousse
Eh, Sie machen Massenverarbeitung; Die JVM zu geben ist kein wirkliches Problem. Wie lange hat es gedauert? Woher haben Sie die Dokumente geladen? Eine benutzerdefinierte Quelle?
Ich habe vielleicht 10 Minuten gebraucht, aber ich stimme zu, dass die Massenverarbeitung per Definition zeitaufwändig und speicherintensiv ist. Obwohl dieser ganze Scherz darüber nicht das Problem war, eher eine Randnotiz.

Antworten:

4

Dies ist ein ziemlich normales Problem in NLP, und die magischen Google-Wörter, nach denen Sie suchen, sind "Themenmodellierung". Obwohl Ihre Zeichenfolgen recht kurz sind, können Sie mit Latent Dirichlet Allocation oder einer ähnlichen Methode einige Erfolge erzielen . Es gibt eine schöne Blog - Post von Edwin Chen hier , die hinter dem Algorithmus die allgemeine Idee legt. Die Details der Implementierung werden in diesem Hinweis von Yi Wang behandelt.

Wenn Sie nach einer Standardlösung suchen, empfehle ich, das topicmodelsPaket für R auszuprobieren, da dies eine recht gute Schnittstelle sowohl zu LDA als auch zu einem anspruchsvolleren Modell für korrelierte Themen bietet. Es gibt auch eine gute Liste von Implementierungen, die von David Mimno hier gepflegt werden .

Martin O'Leary
quelle
Vielen Dank, Chens Blog-Beitrag scheint genau das zu sein, was ich versuche zu tun. Gibt es eine Chance, dass Sie etwas von dem verwendet haben, was Sie zuvor aufgelistet / getan haben? Ich bin hier auf völlig neuen Wegen und würde mich über eine Anleitung freuen, die ich tun müsste (unter Verwendung einer der Standardlösungen). Wie soll ich meine "Dokumente" formatieren? Sollte ich auf jede Frage und Antwort IDs anwenden, damit ich feststellen kann, welches Dokument zu welcher Gruppe gehört? Wie verwende ich die ausgegebenen Daten? Wie gesagt, ich verstehe nicht viele Details.
Whymarrh
Ich habe das R-Topicmodels-Paket ziemlich oft verwendet. Ich würde es auf jeden Fall empfehlen, wenn Sie Ihren eigenen Code rollen - es gibt eine Dokumentation mit einem Beispiel unter cran.r-project.org/web/packages/topicmodels/vignettes/… . Die spezifische Formatierung jedes Dokuments spielt keine Rolle, da sowieso alles auf eine "Tasche voller Wörter" -Darstellung reduziert wird. Wirf einfach den gesamten zugehörigen Text in eine Zeichenfolge.
Martin O'Leary
4

Sie versuchen hier zwei Probleme zu lösen.

Problem 1: Kategorisieren Sie Fragenzeichenfolgen in die richtige Kategorie.

Problem 2: Erstellen Sie die richtigen Kategorien.

Das erste Problem könnte durch sogenannte überwachte Algorithmen gelöst werden, viele Klassifikatoren können eine sehr gute Genauigkeit und Leistung liefern. Problem 2, Kategorien aus dem Nichts (Tonnen von Daten) zu erstellen, ist jedoch viel schwieriger. Dies ist ein unbeaufsichtigtes Problem. Angesichts vieler Daten entscheidet der Computer anhand einiger Kriterien autonom über Kategorien. Im Idealfall sollten diese Kriterien und der Algorithmus Ihre Daten übersichtlich in Clustern organisieren. Diese könnten dann beschriftet werden. Da dies jedoch eine viel schwierigere Aufgabe ist, würde ich sagen, dass es hier keine akzeptable Drop-In-Lösung gibt, die ohne großen Optimierungsaufwand, der höchstwahrscheinlich Experten erfordern würde, ein gutes Ergebnis liefert.

Ich fürchte, hier gibt es noch keinen magischen Knopf. Was Sie jedoch tun können, ist, der Maschine ein wenig zu helfen. Sie können beispielsweise den Kategoriesatz festlegen. Wenn Sie sich für Kategorien entschieden haben, können Sie Trainingsdaten erstellen. In diesem Setup sind die Trainingsdaten nur Frage- und korrekte Kategoriepaare.

Je mehr Trainingsdaten desto besser. Da es sich bei der Aufgabe jedoch immer noch um eine automatische Aufgabe handelt, ist es zunächst nicht sinnvoll, die Dinge manuell zu erledigen. Warum sollten Sie Trainingsdaten haben wollen? Genauigkeitsbewertung. Wenn Sie gute Ergebnisse erzielen möchten, ist es wichtig, dass Sie eine Bewertung der Leistung eines Setups vornehmen können. Und der einzige Weg, dies etwas systematisch zu tun, besteht darin, einige Quests selbst manuell zu kennzeichnen. Sonst bist du im Blind.

Dann stellen sich einige neue Fragen. Erstens: Wie viele Trainingsdaten benötige ich? "Es hängt davon ab, ob". Ohne Ihre Daten oder Kategorien gesehen zu haben, bin ich mir nicht sicher, ob ich überhaupt eine Vermutung anstellen würde. aber ich kann eine "Baseball-Schätzung" nehmen und ungefähr 500 Fragen sagen. Beachten Sie, dass ich um eine Größenordnung abweichen könnte.

Bedeutet das wirklich, dass Sie 500 Fragen von Hand markieren müssten? Ja und nein. Es ist möglich, Zwischenergebnisse und eine gewisse Klugheit zu verwenden, um Klassifikatoren zu "booten". Es ist jedoch immer noch manuelle Arbeit, und wenn Sie darüber nachdenken, werden 500 Fragen nicht so lange dauern, bis sie markiert sind. Hier klug zu sein kann schnell zu schlechteren Ergebnissen führen als fleißig zu sein.

Wenn Sie über ausreichende Trainingsdaten verfügen, nehmen Sie 75% davon und erstellen Sie einen Klassifikator mit Ihrem bevorzugten Werkzeug (z. B. den hier genannten oder so weiter). Lassen Sie den Klassifizierer nun versuchen, die gehaltenen 25% der Daten zu kennzeichnen und die resultierende Genauigkeit zu messen. Wenn das Ergebnis gut ist, dann Pop-Champagner. Wenn nicht, machen Sie mehr Trainingsdaten oder versuchen Sie es mit einem anderen Klassifikator.

TL; DR

Zusammenfassend ist hier, wie ich es gemacht hätte.

0) Use a supervised learner.
1) Create a category set yourself. 
2) Label manually about 500 questions
3) Use 75% of those to train a classifier.
4) Check performance.
5) If good then cheers else goto 2.

quelle
Eine kleine Frage: Sie sagen "ungefähr 500 Fragen" für die Trainingsdaten und markieren diese manuell, aber auch "Ich könnte um eine Größenordnung abweichen". Wenn ich also stattdessen 5.000 oder 50.000 Fragen verwenden würde, würde ich trotzdem so viele manuell markieren?
Die Sache ist; Ohne Ihre Daten gesehen zu haben oder eine sehr klare Vorstellung von den kleinsten Details in Ihrem Projekt zu haben, ist es schwierig, eine gute Schätzung abzugeben. Sollte dies jedoch viel zu niedrig sein, wurde der Tagging-Aufwand nicht verschwendet. Sie benötigen noch manuell beschriftete Fragen zur Bewertung. Je mehr Bewertungsdaten Sie haben, desto bessere Bewertungen können Sie vornehmen.
Mit einer Größenordnung meinte ich 50-500-5000. Ich glaube nicht, dass Sie 50.000 klassifizieren müssen. Das ist 1/4 Ihres gesamten Korpus! Sollten 500 Fragen viel zu niedrig sein, können Klassifizierer gebootet werden. Die Idee hier ist, dass Sie den Klassifikator auf einem kleinen Anfangskorpus (z. B. Ihrem 500) trainieren und dann den Rest markieren. Jetzt können Sie einige Fälle verwenden, in denen der Klassifizierer sehr zuversichtlich war, einen neuen, größeren Klassifizierer neu zu trainieren.
Eine weitere wichtige Sache, die Sie beachten sollten. Die Leistung vieler Klassifikatoren ist in der Menge der Trainingsdaten nicht linear, sondern ist typischerweise eine sigmoidartige Kurve. Das bedeutet, dass 500 weitere getaggte Fragen fast genauso gut sein können wie 5000. Mein Rat ist, in kleinen Schritten zu arbeiten.
Welche Details würden zusätzliche Einblicke in mein Projekt geben? Ich kann einige Beispielfragen teilen, um meine Formatierung zu zeigen, aber ich bin bereit, das Format meiner Fragen und Antworten an den Kategorisierungsprozess anzupassen. Ich schätze die Hilfe.