Ich habe eine Datenbank mit Schlüsselwörtern, die bei Suchanfragen von Personen verschiedener Gruppen verwendet werden. Etwas wie:
%Vor%und so weiter
Ich möchte sehen, welche Keywords für eine bestimmte Gruppe am charakteristischsten sind. Ich versuche zu tun, was OkCupid in ihrem Blog getan hat: Ссылка
Kann jemand geeignete Algorithmen / Terminologie / Ratschläge zu dieser Aufgabe empfehlen?
(Ich mache das in Python)
Vielen Dank im Voraus!
Ihre Frage stellt mehr oder weniger den Hauptanwendungsfall für den ID3-Algorithmus dar.
Die Ausgabe von ID3 ist ein Klassifikator, der eine binäre Baumstruktur hat (ID3, C4.5, usw. werden oft als Entscheidungsbäume bezeichnet). Der Wikipedia-Eintrag für Decision Tree Learning hat tatsächlich eine ordentliche Zusammenfassung (auf der Algorithmenebene) von ID3.
Zwei übliche Metrik in ID3, die bestimmt, wie dieser Teil der Daten an einem bestimmten Knoten aufgeteilt werden soll, heißt Information Entropy . (Eine weniger verwendete Metrik ist Gini-Verunreinigung .) Der ID3-Algorithmus ist nur ein rekursiver Sink-Parser, der alle Kombinationen von Variable / Wert testet und den Knoten der Kombination aufteilt, die den niedrigsten gewichteten Durchschnitt Entropy / p>
Intuitiv versucht Information Entropy, die Variable (Spalte) und den Wert innerhalb dieser Variablen zu identifizieren, die die Daten "am besten" aufteilt. Ein "bester Split" entspricht unserer Intuition. Das ist viel einfacher zu zeigen als mit Prosa zu beschreiben. Betrachten Sie diesen Datensatz:
%Vor%Wenn die Daten in Spalte 4 aufgeteilt sind (führt die Person jede Woche mindestens 90 Minuten Aerobic-Übungen durch?), dann sehen die resultierenden zwei Gruppen von Klassenschildern wie folgt aus:
Ja Gruppe: [Wahr, Wahr, Wahr, Falsch]
Keine Gruppe: [False, False, False]
Fast, aber nicht ganz, perfekte Heterogenität zwischen den beiden Gruppen. Offensichtlich ist Spalte 4 die 'beste' Variable, auf der diese Daten aufgeteilt werden können.
Die Metrik, die im ID3-Algorithmus verwendet wird, um die beste Aufteilung zu bestimmen, ist nur ein mathematischer Formalismus dieser Intuition.
Dies ist keine perfekte (mathematisch präzise) Analogie, aber grob kann man sich vorstellen, dass die Informationsentropie mit kategorischen Variablen (diskrete Werte) in Beziehung steht, da Varianz mit kontinuierlichen Variablen (Floats) in Beziehung steht. Mit anderen Worten: Information Entropy (grob) drückt die Varianz (oder Standardabweichung) diskreter Daten aus.
Hier ist eine Python-Funktion zum Berechnen der Entropie (mit NumPy ):
%Vor%Die obige Entropiefunktion ist nur diese beiden Ausdrücke kombiniert und auf Code reduziert:
%Vor%Die perfekte Heterogenität hat Entropie = 0, also ist die "unterscheidendste" Variable / der Wert derjenige, bei dem die gewichtete durchschnittliche Entropie am niedrigsten ist, wenn Sie die Daten für diese Variable und diesen Wert teilen. Entropiewerte nahe 1 sind fast vollständig "gemischt" oder fast zufällig.
%Vor%Zusammengefasst, für Ihr spezielles Problem, um das am meisten "unterscheidende" Schlüsselwort zu bestimmen, berechnen Sie die Entropie für jede der zwei Klassenbeschriftungslisten und berechnen dann ihren gewichteten Durchschnitt (gewichtet mit der Anzahl der Elemente in jeder Liste). Das Schlüsselwort, das zu der Aufteilung mit der niedrigsten gewichteten durchschnittlichen Entropie führt, ist das, wonach Sie suchen.
Was im Grunde genommen zu berechnen war, ist der Begriff Häufigkeit mal die inverse Dokumenthäufigkeit. tf-idf
Ich denke, die beste Wahl ist Chi ^ 2, infogain, tfidf, bedingte Wahrscheinlichkeit. Warum brauchen alle von ihnen lineare Komplexität. Alle Entscheidungsbäume sind nicht sehr skalierbar, wenn wir über Textdatenbanken sprechen. Aber für die Berechnung solcher Eigenschaften können wir jedes Index-Werkzeug wie Lucene verwenden. Mein Rat ist also, den Informationsgewinn für jedes Wort zu berechnen und am besten zu wählen. Ссылка
Tags und Links python algorithm machine-learning statistics