Multiklassen-Klassifizierung

Unter Multiklassen-Klassifizierung (Multiclass Classification) versteht man Klassifizierungsprobleme, bei denen Daten in genau eine von drei oder mehr möglichen Klassen eingeordnet werden sollen. Versucht man beispielsweise Bildern von Äpfeln, Birnen, und Orangen die jeweils korrekte Frucht zuzuordnen, so steht man vor einem Multiklassen-Klassifizierungsproblem.

Strategien zur Multiklassen-Klassifizierung

Es gibt natürlich verschiedene Strategien und Verfahren um ein Multiklassen-Klassifizierungsproblen anzugehen. Einige Verfahren, z.B. SVC oder auch ein einfaches Perzeptron, sind speziell für binäre Klassifizierungsprobleme ausgelegt, können aber auch zur Multiklassen-Klassifzierung verwendet werden indem wir das Problem auf mehrere binäre Klassifizierungen reduzieren (siehe Einer gegen alle und nachfolgende Abschnitte). Andere Verfahren können bereits inhärent mit mehr als zwei Klassen umgehen. Zu diesen Verfahren zählen unter anderem:

• Entscheidungsbaumverfahren
• Multilayer Perceptron (MLP)
• Nächster-Nachbar Verfahren

Im Folgenden stellen wir kurz einige Strategien vor, um ein Multiklassen-Klassifizierungsproblem in mehrere binäre Klassifizierungsprobleme zu überführen.

Einer gegen alle (One-vs.-all, OvA)

Bei "Einer gegen alle" (One-vs.-all, OvA) wird für jede Klasse ein binärer Klassifikator trainiert, der die gegebene Klasse von allen anderen Klassen unterscheiden können soll. Am Ende wird dann die Klasse gewählt, deren binärer Klassifikator "ausschlägt". In der Praxis können mehrere der Klassifikatoren (oder auch gar keiner) ein positives Ergebnis liefern. Daher ist ein nachgelagerter Prozess notwendig, der beispielsweise anhand von Klassifikationswahrscheinlichkeiten (Wie sicher sind sich die einzelnen Klassifikatoren jeweils mit ihrer Zuordnung?) eine abschließende eindeutige Entscheidung trifft.

Potenzielle Nachteile:

• Keine ausbalancierten Trainingsdaten, da in der Regel jeder Klassifikator wesentlich weniger Positivbeispiele (die Klasse, um die es gerade geht) als Negativbeispiele (alle anderen Klassen) sieht.
• Je nach Definition können die Konfidenzwerte der verschiedenen Klassifikatoren in unterschiedlichen Größenordnungen liegen.

Einer gegen einen (One-vs.-One, OvO)

Bei "Einer gegen einen" (One-vs.-One, OvO) wird für jedes Paar von Klassen ein binärer Klassifikator trainiert, der zwischen den beiden Klassen unterscheiden können soll. Am Ende wird dann die Klasse gewählt, für die sich die meisten Klassifikatoren entscheiden. In der Praxis können mehrere Klassen gleich viele "Stimmen" erhalten, weshalb eine Quantifizierung des Vertrauens in die Entscheidung der Klassifikatoren notwendig ist um eine eindeutige Entscheidung treffen zu können.

Potenzielle Nachteile:

• Viele Klassifikatoren müssen trainiert werden.
• Je nach Definition können die Konfidenzwerte der verschiedenen Klassifikatoren in unterschiedlichen Größenordnung liegen.

Fehlerkorrigierender Output Code

Die verschiedenen Klassen werden durch Binärfolgen einer festen Länge codiert (Codewörter), wobei die Anzahl der Bits in den Binärfolgen i.d.R. größer ist als die Zahl der Klassen. Pro Bit in der Binärfolge wird ein binärer Klassifikator trainiert. Einem neuen Objekt wird dann diejenige Klasse zugeordnet, deren Binärcode am nächsten an der vorhergesagten Binärfolge liegt. Die Motivation hinter dieser Strategie ist, dass bei einer Binärfolgenlänge, die größer als die Anzahl der Klassen ist, Fehler einzelner Klassifikatoren von den anderen Klassifikatoren korrigiert werden können. Damit diese fehlerkorrigierende Funktion auch tatsächlich zum Tragen kommt, ist es wichtig, dass die verschiedenen Klassifikatoren unkorreliert sind, also unterschiedliche Eigenschaften der Objekte erlernen. Unkorrelierte Klassifikatoren werden z.B. durch eine geschickte Wahl der Codewörter begünstigt.

Potenzielle Nachteile:

• Obwohl mehr Klassifikatoren trainiert werden als es Klassen gibt und somit Fehler einzelner Klassifikatoren möglicherweise ausgeglichen werden können, kann es in der Praxis auch passieren, dass alle Klassifikatoren sehr ähnliche Zusammenhänge lernen und sich damit nicht gegenseitig korrigieren können.

Hierarchische Klassifizierung

Die Idee hinter hierarchischer Klassifizierung ist, einen Baum zu konstruieren, dessen Blätter die verschiedenen Klassen sind. Ein möglicher Aufbau wäre z.B. auf der ersten Ebene zwischen Klasse A und den restlichen Klassen, dann auf der zweiten Ebene zwischen Klasse B und den verbleibenden restlichen Klassen, usw. zu unterscheiden, was dann einer Art OvA mit Hierarchie entsprechen würde. Es sind aber auch ganz andere Baumstrukturen vorstellbar und der konkrete Anwendungsfall könnte eine bestimmte Baumstruktur nahelegen: Wenn wir z.B. verschiedene Hunde- und Katzenarten klassifizieren wollten, könnten wir in der ersten Ebene zwischen Hunden und Katzen unterscheiden und in der zweiten Ebene die konkrete Gattung bestimmen.

Evaluation von Multiklassen-Klassifikatoren

Die Konfusionsmatrix zeigt den Zusammenhang zwischen den vom Klassifikator bestimmten Klassenzugehörigkeiten und den tatsächlichen Klassenzugehörigkeiten auf. Im nachfolgenden Beispiel beziehen sich die Spalten auf die vom Klassifikator vergebenen Klassenzugehörigkeiten und die Zeilen auf die tatsächlichen Klassenzugehörigkeiten am Beispiel eines Klassifikators für den MNIST-Datensatz von handgeschriebenen Ziffern 0-9.

Die Zahl in der i-ten Zeile und j-ten Spalte der Matrix gibt an, wie oft der Klassifikator die j-te Klasse vorhergesagt hat für Objekte, die in Wirklichkeit der Klasse i angehören. Insbesondere erhalten wir also die Gesamtzahl der richtig klassifizierten Objekte indem wir die Diagonaleinträge summieren.

Wie bei binären Klassifizierungen sind Präzision und Sensitivität wichtige Metriken, um die Güte eines Klassifikators zu quantifizieren. Allerdings gibt es im Multiklassen-Fall nicht nur einen Wert für Präzision und Sensitivität, sondern die beiden Größen sind pro Klasse definiert. Als skalare Kenngröße, die sowohl Präzision als auch Sensitivität berücksichtigt, wird häufig der F1-Wert betrachtet. Möchte man hierbei Präzision und Sensitivität unterschiedlich gewichten, so kann man den Fbeta-Wert als Verallgemeinerung des F1-Werts verwenden.

• Präzision (Precision): Wie viel Prozent der Bilder, die der Klassifikator als Apfel kategorisiert hat, bilden tatsächlich einen Apfel ab?
• Sensitivität (Recall): Wie viel Prozent der Bilder, die tatsächlich einen Apfel darstellen, wurden vom Klassifikator als Apfel erkannt?
• F1-Wert (F1-score): Harmonisches Mittel aus Präzision und Sensitivität.
• Fbeta-Wert (Fbeta-score): Gewichtetes harmonisches Mittel aus Präzision und Sensitivität. Kann genutzt werden, um eine der beiden Kenngrößen stärker zu Gewichten.

Da Präzision, Sensitivität und F1-Wert (oder allgemeiner Fbeta-Wert) pro Klasse definiert sind, müssen wir die Werte mitteln um auf eine einzige skalare Kenngröße für die Güte des Klassifikators zu kommen. Hier wird zwischen dem Makro-Mittel und dem gewichteten Mittel unterschieden.

• Makro-Mittel: Einfaches arithmetisches Mittel der Kenngrößenwerte über die Klassen.
• gewichtetes Mittel: Gewichtetes arithmetisches Mittle der Kenngrößenwerte über die Klassen, wobei die Gewichte die Anteile der Objekte in der jeweiligen Klasse an der Gesamtzahl der Objekte sind.

Haben wir für Äpfel eine Präzision von 80%, für Orangen eine von 70%, und für Birnen eine Präzision von 90%, so ist das Makro-Mittel für die Sensitivität also 80%. Das gewichtete Mittel erhalten wir, wenn wir die Kenngröße pro Klasse durch die Anzahl der Beobachtungen pro Klasse teilen. Haben wir also 20 Äpfel, 30 Orangen und 50 Birnen, und sind die Präzisionen so wie eben, dann berechnet sich das gewichtete Mittel zu (20x80% + 30x70% + 50x90%)/(20+30+50) = 82%. Auf selbige Art können wir das Makro-Mittel und das gewichtete Mittel für die Sensitivität und den F1-Wert berechnen.

Die Genauigkeit (Accuracy) ist übrigens über alle Klassen hinweg der Anteil der Objekte, die der Klassifikator richtig klassifiziert hat.

Umgang mit unbalancierten Datensätzen

Enthalten in einem Datensatz für ein Multiklassen-Klassifizierungsproblem nicht alle Klassen (in etwa) gleich viele Objekte, sondern einige Klassen wesentlich mehr als andere, so sprechen wir von einem unbalancierten Datensatz. Ein unbalancierter Datensatz kann beim Trainieren eines Klassifikators Probleme bereiten, da häufig Klassen mit mehr Objekten bevorzugt werden. Liegen für einen Datensatz etwa 99% der Beobachtungen in Klasse A und nur 1% der Beobachtungen in Klasse B, so hat der Klassifikator, der jedem Objekt die Klasse A zuordnet, bereits eine Genauigkeit von 99% und wird damit bei einer naiven Bewertungsstrategie vermutlich besser bewertet als viele Klassifikatoren, die auch häufiger mal Klasse B auswählen.

Die folgenden Strategien werden häufig zum Umgang mit unbalancierten Datensätzen verwendet:

• Undersampling: Verkleinere den Datensatz, so dass jede Klasse in etwa so viele Objekte enthält wie die kleinste Klasse.
• Oversampling: Vergrößere den Datensatz, entweder durch Duplikate oder synthetisch generierte Daten, so dass jede Klasse in etwa so viele Objekte enthält wie die größte Klasse. Ein Algorithmus zum Oversamplen durch synthetisch generierte Daten ist SMOTE (Synthetic Minority Over-sampling Technique).
• Kostensensitives Lernen (Cost-Sensitive Learning): Viele Machine-Learning-Algorithmen bieten Möglichkeiten, Falschklassifizierung je nach tatsächlicher Klasse des Objekts unterschiedlich stark zu bestrafen und dadurch beim Trainieren des Klassifikators die unterschiedlichen Klassengrößen zu berücksichtigen.