Automatische Kennzeichnung

    In diesem Artikel werden wir versuchen, das Problem der Mehrfachklassifizierung am Beispiel der Lösung des Problems der automatischen Platzierung von Such-Tags für Textdokumente in unserem Projekt www.favoraim.com zu erläutern . Leser, die mit dem Thema gut vertraut sind, werden höchstwahrscheinlich nichts Neues für sich finden. Bei der Lösung dieses Problems lesen wir jedoch viele verschiedene Literaturstellen, in denen nur sehr wenig oder gar nichts über das Problem der Mehrfachklassifizierung gesagt wurde.

    Beginnen wir also mit der Erklärung des Klassifizierungsproblems. Sei X die Menge der Beschreibungen von Objekten, Y die Menge der Nummern (oder Namen) von Klassen. Es gibt eine unbekannte Zielbeziehung - eine Zuordnung, Bildderen Werte nur an den Objekten der endgültigen Trainingsstichprobe bekannt sind Bild. Algorithmus erforderlichBildin der Lage, ein beliebiges Objekt x∈X zu klassifizieren. Die probabilistische Formulierung des Problems ist jedoch häufiger. Sei X die Menge der Beschreibungen von Objekten, Y die Menge der Nummern (oder Namen) von Klassen. Ein probabilistisches Maß P wird auf der Menge von "Objekt, Klasse" X × Y-Paaren definiert. Es gibt eine endliche Trainingsmenge von unabhängigen Beobachtungen, Bilddie gemäß dem probabilistischen Maß P erhalten werden.

    Nun wenden wir uns der Aufgabe der automatischen Anordnung von Suchmarken zu. Wir haben ein Objekt x - ein Textdokument und viele KlassenBild- Tags suchen. Jedes Dokument muss mit einem oder mehreren Such-Tags abgeglichen werden. Wir haben zum Beispiel eine Veranstaltung mit dem Titel „Konzert der Apocalyptica-Gruppe“, der folgende Such-Tags zugeordnet werden können: „Apocalyptica“, „Konzert“, „Heavy Metal“, „Cello“ usw. Wir haben auch ein Trainingsmuster, d.h. Dokumentensatz mit bereits platzierten Such-Tags. Somit haben wir ein Klassifizierungsproblem mit sich überschneidenden Klassen, d.h. Ein Objekt kann mehreren Klassen gleichzeitig angehören. Stattdessen lösen wir N binäre Klassifikationsprobleme. Wir klassifizieren jedes Paar Bildin Klassen {0,1}, d. H. Bestimmen Sie, ob das Such-Tag in BildDokument x eingefügt werden kann oder nicht.
    Um dieses Problem zu lösen, werden wir Textdokumente in Form einer „Worttüte“ oder eines mehrdimensionalen Wortvektors und deren Gewicht (Häufigkeit des Auftretens) in einem Dokument ( http://en.wikipedia.org/wiki/Bag-of-words_model ) präsentieren. In Abb. Fig. 1 zeigt ein Histogramm von Geschäftstrainings-Beschreibungswörtern. 2 - ein Histogramm von Wörtern, die die Meisterklasse in Fotografie beschreiben.

    Bild

    Bild

    Als Klassifizierungsmethode können Sie eine beliebige statistische (Bayes'sche) Klassifizierungsmethode verwenden. Das Wahrscheinlichkeitsmodell für den Klassifikator ist das Bedingungsmodell p (y (d), y∈Y. Nun müssen wir die Dichte p (y│d), y∈Y, d.h. die Wahrscheinlichkeit, dass Sie für unser Dokument d einen Suchbegriff eingeben können y∈Y. Es gibt viele Methoden, um die Dichte wiederherzustellen. Sie können mit dem naiven Bayes'schen Modell für die Dokumentklassifizierung beginnen (http://ru.wikipedia.org/wiki/Document Classification ). Für dieses Modell wird eine „naive“ Annahme über die Unabhängigkeit der im Dokument enthaltenen Wörter gemacht, und obwohl dies offensichtlich eine falsche Annahme ist, funktioniert das Modell recht gut.
    Nachdem wir die Verteilungsdichte wiederhergestellt haben und für jedes Tag y∈Y die Wahrscheinlichkeit ermittelt haben, dass es unserem Dokument d zugewiesen werden kann, müssen wir bestimmen, welche Tags dem Dokument zugewiesen und welche gelöscht werden sollen, d. H. Finden Sie die minimale Grenzschwelle für die Wahrscheinlichkeit p (y (d). Hier müssen Sie die Analyse der ROC-Kurve verwenden ( http://www.machinelearning.ru/wiki/index.php?title=ROC- curve ).
    Die ROC-Kurve zeigt die Abhängigkeit der Anzahl korrekt klassifizierter positiver Beispiele (True Positive Rate) von der Anzahl falsch klassifizierter negativer Beispiele (False Positive Rate). Es wird davon ausgegangen, dass der Klassifikator einen bestimmten Parameter hat, der variiert, und wir werden die eine oder andere Partition in zwei Klassen aufteilen. Dieser Parameter wird häufig als Schwellenwert oder Grenzwert bezeichnet. In unserem Fall spielt die Wahrscheinlichkeit p (y│d) die Rolle dieses Parameters. Die ROC-Kurve wird aus der Kontrollprobe erstellt, die normalerweise Teil der Trainingsprobe ist. Gleichzeitig können Objekte der Kontrollprobe nicht zum Trainieren des Klassifikators verwendet werden, da wir sonst aufgrund des Phänomens der Umschulung eine zu optimistische ROC-Kurve erhalten können. Wenn die Ressourcen es uns jedoch erlauben, Wir können Kreuzvalidierung verwenden. Das Wesentliche ist, dass die Trainingsstichprobe in k Teile unterteilt ist, von denen k-1 zum Trainieren des Modells verwendet werden, der verbleibende Teil wird als Kontrollstichprobe verwendet. Dieser Vorgang wird k-mal durchgeführt. In der Praxis ist diese Technik problematisch, weil Das Rechnen nimmt viel Zeit in Anspruch.

    Bild

    Die ROC-Kurve weist die folgenden Haupteigenschaften auf. Sensitivität (Sensitivität) - dies ist der Anteil wirklich positiver Fälle. Die Spezifität ist der Anteil wirklich negativer Fälle, die vom Modell korrekt identifiziert wurden. Beachten Sie, dass fpr = 100-Spezifität ist. Fläche unter der ROC-Kurve (AUC). Der AUC-Wert wird normalerweise zur Beurteilung der Qualität des Klassifikators verwendet. Beispielsweise entspricht die Abhängigkeit fpr = tpr dem ungünstigsten Fall (zufällige Wahrsagerei). In Abb. 3 Der schlimmste Fall wird durch eine gestrichelte Linie angezeigt. Je höher die Dichte, desto besser liefert der Prädiktor den Klassifikator. Für einen idealen Klassifikator verläuft das ROC-Kurvendiagramm durch die obere linke Ecke.
    Jetzt müssen Sie die minimale Abschaltschwelle auswählen. Es gibt 3 Ansätze.
    • Die Anforderung der minimalen Empfindlichkeit (Spezifität) des Modells. Das heißt Einer der Werte wird konstant gesetzt, und auf dieser Grundlage wird der Wert der Abschaltschwelle ausgewählt.
    • Die Forderung nach maximaler Gesamtsensitivität und Spezifität des Modells.
    • Die Forderung nach einem Gleichgewicht zwischen Sensitivität und Spezifität, d.h. wenn Spezifität - Empfindlichkeit. Hier ist die Schwelle der Schnittpunkt zweier Kurven, wenn die Grenzschwelle entlang der x-Achse und die Modellempfindlichkeit und -spezifität entlang der y-Achse aufgetragen sind (Abb. 4).


    Bild

    Daher können wir unserem Dokument d die Such-Tags zuweisen, für die p (y│d)> c ausgeführt wird, wobei c der Grenzschwellenwert ist.

    Nun ein wenig üben. Das erste, was Sie tun müssen, ist, den Text unseres Dokuments in die normale Form umzuwandeln und dabei Stoppwörter zu entfernen (z. B. normalized_string ("Beispielzeile in normaler Form") = "Beispielzeile in normaler Form"). Für diese Zwecke sind PostgreSQL-FTS-Wörterbücher gut geeignet. Als nächstes benötigen wir eine Reihe von Dokumenten mit Tags, die bereits für das Training unseres Klassifikators festgelegt wurden. Als Beispiel werde ich den Bayesian naiven Klassifikator-Pseudocode für das Training anführen.

    Map> naiveBayes;
    for (Entry entry: docSet)
    {
    	for (String lexem: get_normalized_string(entry.key).split(MY_DELIMS))
    	{
    		for (String tag: entry.value)
    		{
    			naiveBayes[tag][lexem]++;
    		}
    	}
    }


    Daher ordnen wir jedem Such-Tag ein Histogramm von Tokens aus Dokumenten in unserem Trainingsset zu. Nachdem der Klassifikator trainiert wurde, können Sie die Wahrscheinlichkeiten für das Vorhandensein eines Tags in einem neuen Dokument berechnen. Im naiven Bayes'schen Modell wird die Wahrscheinlichkeit des Auftretens des t-Tags für das Dokument d durch die Formel berechnet Bild, wobei P (t) die Wahrscheinlichkeit des Auftretens des t-Tags ist und Bilddie Token des Dokuments d einschließlich Wiederholungen sind. Die Wahrscheinlichkeit P (t) kann geschätzt werden als Bild, wobei Bilddie Anzahl der Dokumente im Trainingssatz mit dem Tag t und N die Anzahl aller Dokumente im Trainingssatz ist. Die Wahrscheinlichkeitsschätzung P (l│t) unter Verwendung des Trainingssatzes ist wie folgt Bild, wobei Bilddie Anzahl der Vorkommen des Tokens l in allen Dokumenten mit dem Tag t undBild- Die Anzahl aller Token in allen Dokumenten mit dem Tag t. Um einen Überlauf in der Formel zur Berechnung der Wahrscheinlichkeiten aufgrund der Vielzahl von Faktoren zu vermeiden, wird in der Praxis in der Regel anstelle des Produkts die Summe der Logarithmen verwendet. Der Logarithmus beeinflusst das Auffinden des Maximums nicht, da der Logarithmus eine monoton ansteigende Funktion ist.

    Map probs;
    for (String tag: naiveBayes.keySet())
    {
    	probs[tag] = log(P(t));
    	for (String lexem: get_normalized_string(document).split(MY_DELIMS))
    	{
    		probs[tag] += log(naiveBayes[tag][lexem]/sum(naiveBayes[tag]));
    	}
    }
    


    Es bleibt die ROC-Kurve zu bauen. Als Pseudocode füge ich wahrscheinlich Copy-Paste ein.

    Der kanonische Algorithmus zur Erstellung der ROC-Kurve
    Eingaben: L - viele Beispiele; f [i] ist die vom Modell erhaltene Bewertung oder die Wahrscheinlichkeit, dass das i-te Beispiel einen positiven Ausgang hat; min und max sind die von f zurückgegebenen Minimal- und Maximalwerte; dx ist der schritt; P und N sind die Anzahl der positiven bzw. negativen Beispiele.

    t=min
    повторять
        FP=TP=0
        для всех примеров i принадлежит L {
            если f[i] >= t тогда // этот пример находится за порогом
                если i положительный пример тогда
                    { TP=TP+1 }
                иначе // это отрицательный пример
                    { FP=FP+1 }
        }
        Se=TP/P*100
        100_m_Sp=FP/N // расчет (100 минус Sp)
        Добавить точку (100_m_Sp, Se) в ROC кривую
        t=t+dx
    пока (t>max)

    Um nach der Cutoff-Schwelle zu suchen, wird vorgeschlagen, standardmäßig Methode 2 zu wählen: Die Forderung nach maximaler Gesamtsensitivität und Spezifität des Modells ist meines Erachtens nicht schwer zu finden. Dies ist wahrscheinlich alles, wenn Sie Fragen oder Anregungen haben, schreiben, ich werde sie gerne beantworten.

    Jetzt auch beliebt: