Multilabel-Klassifizierung

Im maschinellen Lernen ist die Multilabel-Klassifizierung ( auch Multioutput-Klassifizierung genannt) eine Variante des Klassifizierungsproblems , bei der jeder Instanz mehrere, sich nicht ausschließende Labels zugewiesen werden können. Sie ist eine Verallgemeinerung der Mehrklassenklassifizierung , bei der Instanzen einer von mindestens zwei Klassen zugeordnet werden. Im Gegensatz zur Multilabel-Klassifizierung sind die Labels bei der Multilabel-Klassifizierung nicht exklusiv, und es gibt keine Beschränkung hinsichtlich der Anzahl der Klassen, denen eine Instanz zugeordnet werden kann. Die Formulierung des Multilabel-Lernens wurde erstmals von Shen et al. im Kontext der semantischen Szenenklassifizierung eingeführt ^{[1, 2 ] und erlangte später in} verschiedenen Bereichen des maschinellen Lernens an Bedeutung.

Formal gesehen ist die Multi-Label-Klassifizierung das Problem, ein Modell zu finden, das Eingaben x auf binäre Vektoren y abbildet ; das heißt, es ordnet jedem Element (Label) in y den Wert 0 oder 1 zu .

Für die Multilabel-Klassifizierung existieren verschiedene Problemtransformationsmethoden, die sich grob in folgende Kategorien unterteilen lassen:

Der Basisansatz, die sogenannte binäre Relevanzmethode [ ^{3 ] ,} besteht darin, für jedes Label einen separaten binären Klassifikator zu trainieren. Das kombinierte Modell sagt dann für eine unbekannte Stichprobe alle Labels voraus, für die die jeweiligen Klassifikatoren ein positives Ergebnis vorhersagen. Obwohl diese Methode der Aufteilung der Aufgabe in mehrere binäre Aufgaben oberflächlich betrachtet den One-vs.-All- (OvA) und One-vs.-Rest- (OvR) Methoden zur Mehrklassenklassifizierung ähneln mag , unterscheidet sie sich grundlegend von beiden. Denn ein einzelner Klassifikator bei binärer Relevanz behandelt jeweils nur ein Label, ohne die anderen Labels zu berücksichtigen. Eine Klassifikatorkette ist eine alternative Methode, um ein Mehrklassen-Klassifizierungsproblem in mehrere binäre Klassifizierungsprobleme zu transformieren. Sie unterscheidet sich von der binären Relevanz dadurch, dass die Labels sequenziell vorhergesagt werden und die Ausgabe aller vorherigen Klassifikatoren (d. h. positiv oder negativ für ein bestimmtes Label) als Merkmale für die nachfolgenden Klassifikatoren verwendet wird. ^{[ 3 ]} Klassifikatorketten wurden beispielsweise zur Vorhersage von HIV -Resistenzen eingesetzt. ^{[ 4 ] [ 5 ]} Bayes'sche Netze wurden auch zur optimalen Anordnung von Klassifikatoren in Klassifikatorketten eingesetzt . ^{[ 6 ]}

Im Falle der Umwandlung des Problems in mehrere binäre Klassifizierungen lautet die Likelihood-Funktion , wobei der Index über die Stichproben läuft, der Index über die Labels läuft, die binären Ergebnisse 0 oder 1 angibt, das Kronecker-Delta angibt und die mehrfachen Hot-Encoded-Labels der Stichprobe angibt . ${\displaystyle L=\prod _{i=1}^{n}(\prod _{k}(\prod _{j_{k}}(p_{k,j_{k}}(x_{i})^{\delta _{y_{i,k},j_{k}}})))}$${\displaystyle i}$${\displaystyle k}$${\displaystyle j_{k}}$${\displaystyle \delta _{a,b}}$${\displaystyle y_{i,k}\in {0,1}}$${\displaystyle i}$

Die Label-Potenzmengen-Transformation (LP-Transformation) erzeugt für jede im Trainingsdatensatz vorhandene Labelkombination einen binären Klassifikator. Wenn beispielsweise die möglichen Labels für ein Beispiel A, B und C wären, stellt die Label-Potenzmengen-Repräsentation dieses Problems ein Mehrklassen-Klassifizierungsproblem mit den Klassen [0 0 0], [1 0 0], [0 1 0], [0 0 1], [1 1 0], [1 0 1], [0 1 1] und [1 1 1] dar, wobei beispielsweise [1 0 1] ein Beispiel bezeichnet, in dem die Labels A und C vorhanden sind, Label B jedoch fehlt. ^{[ 7 ]}

Ein Satz von Mehrklassenklassifikatoren kann verwendet werden, um einen Multi-Label-Ensemble-Klassifikator zu erstellen. In einem gegebenen Beispiel gibt jeder Klassifikator eine einzelne Klasse aus (entsprechend einem einzelnen Label im Multi-Label-Problem). Diese Vorhersagen werden dann durch ein Ensemble-Verfahren kombiniert, üblicherweise ein Abstimmungsverfahren, bei dem jede Klasse, die einen erforderlichen Prozentsatz an Stimmen von einzelnen Klassifikatoren erhält (oft als Diskriminierungsschwelle bezeichnet ^{[ 8 ]} ), als vorhandenes Label in der Multi-Label-Ausgabe vorhergesagt wird. Es existieren jedoch komplexere Ensemble-Verfahren, wie z. B. Committee Machines . Eine weitere Variante ist der Random k- Labelsets (RAKEL)-Algorithmus, der mehrere LP-Klassifikatoren verwendet, die jeweils mit einer zufälligen Teilmenge der tatsächlichen Labels trainiert werden; die Labelvorhersage erfolgt dann durch ein Abstimmungsverfahren. ^{[ 9 ]} Ein Satz von Mehrklassenklassifikatoren kann auf ähnliche Weise verwendet werden, um einen Multi-Label-Ensemble-Klassifikator zu erstellen. In diesem Fall stimmt jeder Klassifikator einmal für jedes Label ab, das er vorhersagt, anstatt für ein einzelnes Label.

Einige Klassifizierungsalgorithmen/-modelle wurden für die Multi-Label-Aufgabe angepasst, ohne dass eine Transformation des Problems erforderlich ist. Beispiele hierfür, auch für Multi-Label-Daten, sind:

• k-nächste Nachbarn : Der ML-kNN-Algorithmus erweitert den k-NN-Klassifikator auf Multilabel-Daten. ^{[ 10 ]}
• Entscheidungsbäume : „Clare“ ist ein angepasster C4.5-Algorithmus für die Multilabel-Klassifizierung; die Modifikation betrifft die Entropieberechnungen. ^{[ 11 ]} MMC, MMDT und SSC (eine Weiterentwicklung von MMDT) können Multilabel-Daten anhand mehrwertiger Attribute klassifizieren, ohne die Attribute in Einzelwerte umzuwandeln. Sie werden auch als mehrwertige und Multilabel-Entscheidungsbaum-Klassifizierungsmethoden bezeichnet. ^{[ 12 ] [ 13 ] [ 14 ]}
• Kernelmethoden für Vektorausgabe
• Neuronale Netze : BP-MLL ist eine Anpassung des populären Backpropagation-Algorithmus für Multi-Label-Lernen. ^{[ 15 ]}

Basierend auf den Lernparadigmen lassen sich die bestehenden Multi-Label-Klassifizierungsverfahren in Batch-Learning und Online-Machine-Learning unterteilen . Batch-Learning-Algorithmen benötigen alle Datenbeispiele im Voraus. Sie trainieren das Modell mit den gesamten Trainingsdaten und sagen anschließend das Testbeispiel anhand der gefundenen Beziehung voraus. Online-Lernalgorithmen hingegen bauen ihre Modelle inkrementell in sequenziellen Iterationen auf. In Iteration t erhält ein Online-Algorithmus ein Beispiel x_{_t} und sagt dessen Label(s) ŷ_{_t} mithilfe des aktuellen Modells voraus. Anschließend erhält der Algorithmus y _{_t} , das/die tatsächliche(n) Label(s) von x_{_t} , und aktualisiert sein Modell basierend auf dem Beispiel-Label-Paar (x _{_t} , y_{_t} ).

Datenströme sind potenziell unendliche Datensequenzen, die kontinuierlich und schnell anwachsen. ^{[ 16 ]} Die Multi-Label-Stream-Klassifizierung (MLSC) ist eine Variante der Multi-Label-Klassifizierung, die in Datenströmen durchgeführt wird. Sie wird auch als Online-Multi-Label-Klassifizierung bezeichnet. Die Schwierigkeiten der Multi-Label-Klassifizierung (exponentielle Anzahl möglicher Label-Sets, Erfassung von Abhängigkeiten zwischen Labels) verbinden sich mit den Schwierigkeiten von Datenströmen (Zeit- und Speicherbeschränkungen, Adressierung unendlicher Datenströme mit endlichen Mitteln, Konzeptdrift ).

Viele MLSC-Methoden greifen auf Ensemble-Methoden zurück , um ihre Vorhersageleistung zu verbessern und Konzeptdrift zu begegnen. Im Folgenden sind die in der Literatur am häufigsten verwendeten Ensemble-Methoden aufgeführt:

• Online-Bagging -basierte Methoden (OzaBagging ^{[ 17 ]} ) : Da die Wahrscheinlichkeit, K-mal einen bestimmten Datenpunkt in einer Bootstrap-Stichprobe zu finden, für große Datensätze annähernd Poisson(1) -verteilt ist , kann jede eingehende Dateninstanz in einem Datenstrom proportional zur Poisson(1)-Verteilung gewichtet werden, um Bootstrapping in einer Online-Umgebung zu simulieren. Dies wird als Online-Bagging (OzaBagging) bezeichnet. In der Literatur werden zahlreiche Multi-Label-Methoden vorgeschlagen, die Online-Bagging nutzen und jeweils unterschiedliche Problemtransformationsverfahren verwenden. EBR _[ ^{3 ] ,} ECC ^{[ 3 ]} , EPS ^{[ 18 ]} , EBRT ^{[ 19 ]} , EBMT _[ ^{19 ] und} ML -Random Rules ^{[ 20 ]} sind Beispiele für solche Methoden.
• ADWIN-Bagging- basierte Methoden ^{[ 21 ]} : Online-Bagging-Methoden für MLSC werden mitunter mit expliziten Mechanismen zur Erkennung von Konzeptdrift, wie z. B. ADWIN ^{[ 22 ]} (Adaptive Window), kombiniert. ADWIN verwendet ein Fenster variabler Größe, um Änderungen in der Datenverteilung zu erkennen und das Ensemble zu verbessern, indem es Komponenten mit schlechter Performance bei einer Drift in den Eingangsdaten zurücksetzt. Üblicherweise wird der Buchstabe „a“ als Index im Namen solcher Ensembles verwendet, um die Nutzung des ADWIN-Änderungsdetektors anzuzeigen. E _a BR, ^{[ 21 ]} , E _a CC, ^{[ 21 ]} und E _a HT _PS ^{[ 21 ]} sind Beispiele für solche Multi-Label-Ensembles.
• GOOWE-ML -basierte Methoden ^{[ 23 ]} : Durch die Interpretation der Relevanzwerte jeder Ensemble-Komponente als Vektoren im Labelraum und die Lösung eines Kleinste-Quadrate-Problems am Ende jedes Batches wird das geometrisch optimale, online gewichtete Ensemble für die Multi-Label-Klassifizierung (GOOWE-ML) vorgeschlagen. Das Ensemble minimiert den Abstand zwischen der gewichteten Vorhersage seiner Komponenten und dem Ground-Truth -Vektor für jede Instanz innerhalb eines Batches. Im Gegensatz zu Online Bagging und ADWIN Bagging verwendet GOOWE-ML ein gewichtetes Abstimmungsverfahren, bei dem leistungsstärkere Ensemble-Komponenten ein höheres Gewicht erhalten. Das GOOWE-ML-Ensemble wächst mit der Zeit, und die Komponente mit dem niedrigsten Gewicht wird durch eine neue Komponente ersetzt, sobald sie am Ende eines Batches voll ist. GOBR ^{[ 23 ]} , GOCC ^{[ 23 ]} , GOPS ^{[ 23 ]} und GORT ^{[ 23 ]} sind die vorgeschlagenen GOOWE-ML-basierten Multi-Label-Ensembles.
• Mehrere Fenster ^{[ 24 ]}  : Hierbei werden BR-Modelle mit einem gleitenden Fenster durch zwei Fenster pro Label ersetzt – eines für relevante und eines für nicht relevante Beispiele. Die Instanzen werden anhand eines Lastfaktors, der zwischen diesen beiden Fenstern gehalten wird, über- oder unterabgetastet. Dies ermöglicht die Erkennung von Konzeptdrifts, die für jedes Label unabhängig sind, und die Behandlung von Klassenungleichgewichten (Schiefe zwischen relevanten und nicht relevanten Beispielen).

Wenn man von einer Menge von Labels für eine Datenprobe ausgeht (nicht zu verwechseln mit einem One-Hot -Vektor; es ist einfach eine Sammlung aller Labels, die zu dieser Probe gehören), lässt sich der Grad, in dem ein Datensatz Multilabel ist, durch zwei Statistiken erfassen: ${\displaystyle Y_{i}}$${\displaystyle i^{th}}$

• Die Label-Kardinalität ist die durchschnittliche Anzahl der Labels pro Beispiel im Datensatz: wobei die Gesamtzahl der Datenbeispiele ist;${\displaystyle {\frac {1}{N}}\sum _{i=1}^{N}|Y_{i}|}$${\displaystyle N}$
• Die Labeldichte ist die Anzahl der Labels pro Stichprobe geteilt durch die Gesamtzahl der Labels, gemittelt über alle Stichproben: wobei die Gesamtzahl der verfügbaren Klassen ist (was die maximale Anzahl von Elementen ist, aus denen bestehen kann ).${\displaystyle {\frac {1}{N}}\sum _{i=1}^{N}{\frac {|Y_{i}|}{|L|}}}$${\displaystyle L=\bigcup _{i=1}^{N}Y_{i}}$${\displaystyle Y_{i}}$

Die Bewertungsmetriken für die Leistung bei der Multilabel-Klassifizierung unterscheiden sich grundlegend von denen der Mehrklassen- (oder Binär-)Klassifizierung, da die Klassifizierungsprobleme inhärent anders sind. Bezeichnet T die Menge der tatsächlichen Labels für eine gegebene Stichprobe und P die Menge der vorhergesagten Labels, so lassen sich die folgenden Metriken für diese Stichprobe definieren:

• Hamming- Verlust: Der Anteil der falschen Labels an der Gesamtzahl der Labels, d. h. , wobei das Ziel, die Vorhersage und der „Exklusiv-Oder“-Operator ist , der null zurückgibt, wenn Ziel und Vorhersage identisch sind, und eins andernfalls. Dies ist eine Verlustfunktion , daher ist der optimale Wert null und ihre obere Grenze eins.${\displaystyle {\frac {1}{|N|\cdot |L|}}\sum _{i=1}^{|N|}\sum _{j=1}^{|L|}\operatorname {xor} (y_{i,j},z_{i,j})}$${\displaystyle y_{i,j}}$${\displaystyle z_{i,j}}$${\displaystyle \operatorname {xor} (\cdot )}$
• Der eng verwandte Jaccard-Index , der im Multi-Label-Kontext auch als Schnittmenge über Vereinigung bezeichnet wird, ist definiert als die Anzahl der korrekt vorhergesagten Labels geteilt durch die Vereinigung der vorhergesagten und wahren Labels, , wobei und Mengen von vorhergesagten bzw. wahren Labels sind.${\displaystyle {\frac {|T\cap P|}{|T\cup P|}}}$${\displaystyle P}$${\displaystyle T}$
• Präzision, Trefferquote und Score : Die Präzision ist , die Trefferquote ist , und ist ihr harmonisches Mittel . ^{[ 25 ]}${\displaystyle F_{1}}$${\displaystyle {\frac {|T\cap P|}{|P|}}}$${\displaystyle {\frac {|T\cap P|}{|T|}}}$${\displaystyle F_{1}}$
• Exakte Übereinstimmung (auch Teilmengengenauigkeit genannt): ist die strengste Metrik und gibt den Prozentsatz der Stichproben an, bei denen alle ihre Labels korrekt klassifiziert wurden.

Die Kreuzvalidierung in Multi-Label-Szenarien wird dadurch erschwert, dass die übliche (binäre/multiklassige) Methode der geschichteten Stichprobenziehung nicht funktioniert; es wurden alternative Methoden der approximativen geschichteten Stichprobenziehung vorgeschlagen. ^{[ 26 ]}

Java-Implementierungen von Multi-Label-Algorithmen sind in den Softwarepaketen Mulan und Meka verfügbar , die beide auf Weka basieren .

Das Python-Paket scikit-learn implementiert einige Multi-Label-Algorithmen und Metriken .

Das Python-Paket scikit-multilearn ist speziell für die Multilabel-Klassifizierung entwickelt worden. Es bietet Multilabel-Implementierungen verschiedener bekannter Verfahren wie SVM, kNN und vielen weiteren . Das Paket basiert auf dem scikit-learn- Ökosystem.

Die Methode der binären Relevanz, Klassifikatorketten und andere Multilabel-Algorithmen mit vielen verschiedenen Basislernern sind im R-Paket mlr ^{[ 27 ] implementiert.}

Eine Liste häufig verwendeter Multi-Label-Datensätze ist auf der Mulan-Website verfügbar .

• Multiklassenklassifizierung
• Lernen mit mehreren Instanzen
• Strukturierte Vorhersage
• Lebensdauer der Korrelation

• Madjarov, Gjorgji; Kocev, Dragi; Gjorgjevikj, Dejan; Džeroski, Sašo (2012). „Ein umfassender experimenteller Vergleich von Methoden für das Multi-Label-Lernen“. Mustererkennung . 45 (9): 3084–3104 . Bibcode : 2012PatRe..45.3084M . doi : 10.1016/j.patcog.2012.03.004 . S2CID  14064264 .