Entscheidungsbäume und Multi-Class-Klassifikation in CS6601: Eine praktische Anleitung mit Vectorization

Einführung in Entscheidungsbäume und Multi-Class-Klassifikation

Entscheidungsbäume sind ein grundlegendes Werkzeug des überwachten maschinellen Lernens. Sie nehmen einen Vektor von Attributwerten als Eingabe und geben eine Entscheidung aus – sei es eine binäre Klassifikation (z. B. „Spam“ oder „Kein Spam“) oder eine Multi-Class-Klassifikation (z. B. „Katzen“, „Hunde“, „Vögel“). In diesem Tutorial zeigen wir dir, wie du einen Entscheidungsbaum von Grund auf implementierst, ähnlich wie im CS6601 Assignment 4. Dabei gehen wir besonders auf die Herausforderungen der Multi-Class-Klassifikation und die Optimierung durch Vectorization ein.

Warum Entscheidungsbäume?

Entscheidungsbäume sind einfach zu interpretieren und benötigen wenig Datenvorverarbeitung. Sie sind die Basis für viele moderne Ensemble-Methoden wie Random Forests. Im Zeitalter von KI-Apps und personalisierten Empfehlungssystemen – wie etwa bei Spotify, das dir täglich neue Playlists vorschlägt – helfen Entscheidungsbäume, Muster in Nutzerdaten zu erkennen. Stell dir vor, du entwickelst eine App, die anhand von Spielzeit, Genre-Präferenz und Tageszeit entscheidet, welcher Song als Nächstes gespielt wird. Ein Entscheidungsbaum könnte genau das abbilden.

Die Grundlagen: Binäre vs. Multi-Class-Klassifikation

In der binären Klassifikation gibt es genau zwei Ausgabeklassen (z. B. „+“ und „-“). Bei der Multi-Class-Klassifikation sind es mehr als zwei – zum Beispiel 3 Klassen im Datensatz simple_multi.csv oder sogar 9 Klassen in complex_multi.csv. Der Algorithmus muss lernen, die Datenpunkte einer der vielen Klassen zuzuordnen. Ein häufiges Problem ist der Klassenungleichgewicht, wenn eine Klasse viel häufiger vorkommt als andere. In der Praxis – etwa bei der Fehlererkennung in selbstfahrenden Autos – kann eine seltene Klasse (z. B. „Fußgänger bei Nacht“) entscheidend sein.

Der Datensatz: Von einfach bis komplex

Im Assignment arbeitest du mit verschiedenen CSV-Dateien:

• hand_binary.csv und hand_multi.csv: Kleine Datensätze zum Testen des grundlegenden Verständnisses.
• simple_binary.csv und simple_multi.csv: 100 Beispiele – ideal für erste Implementierungen.
• mod_complex_binary.csv und mod_complex_multi.csv: 1600–2400 Beispiele – hier wird Vectorization wichtig.
• complex_binary.csv und complex_multi.csv: 2800–4800 Beispiele – echte Herausforderungen.
• challenge_binary.csv und challenge_multi.csv: bis zu 10800 Beispiele – nur mit optimiertem Code zu bewältigen.

Der Pfad zu den Daten lautet stets ./data/dateiname.csv.

Vectorization: Der Turbo für deinen Code

Vectorization bedeutet, dass du Operationen auf ganzen Arrays (z. B. numpy-Arrays) ausführst, statt elementweise zu iterieren. Das ist nicht nur schneller, sondern auch kürzer und lesbarer. Im Assignment bekommst du mit vectorize.csv eine Warmup-Aufgabe, um den Umgang mit Matrizen zu üben. Stell dir vor, du berechnest für tausende Datenpunkte die Entfernung zu allen Zentroiden – ohne Vectorization würde dein Code Minuten brauchen, mit Vectorization Sekunden.

Praxisbeispiel: Matrix-Operationen für Entscheidungsbäume

Nehmen wir an, du möchtest für jeden Datenpunkt die Wahrscheinlichkeit jeder Klasse berechnen. Mit numpy kannst du das in einer Zeile erledigen:

import numpy as np
probs = np.exp(scores) / np.sum(np.exp(scores), axis=1, keepdims=True)

Solche Operationen sind essentiell, wenn du später eine Confusion Matrix oder Metriken wie Precision, Recall und F1-Score berechnest. Im Assignment musst du alle Metriken selbst implementieren – ohne sklearn!

Implementierung eines Entscheidungsbaums

Der Kern des Assignments ist der Bau eines Entscheidungsbaums. Du musst Funktionen schreiben, die:

1. Den besten Split anhand eines Kriteriums (z. B. Gini-Impurity oder Entropie) finden.
2. Den Datensatz rekursiv aufteilen, bis eine Abbruchbedingung erreicht ist (maximale Tiefe, minimale Stichprobenanzahl).
3. Eine Vorhersage für neue Datenpunkte treffen.

Gini-Impurity vs. Entropie

Für die Multi-Class-Klassifikation eignet sich besonders die Gini-Impurity, da sie recheneffizienter ist. Die Formel lautet:

Gini(D) = 1 - Σ (p_i)^2

wobei p_i der Anteil der Klasse i im Datensatz D ist. Ein kleiner Gini-Wert bedeutet eine reine Aufteilung.

Rekursives Splitting

Ein Entscheidungsbaum wächst rekursiv. Für jeden Knoten wählst du das Merkmal und den Schwellenwert, der die Daten am besten trennt. Das wiederholst du für die beiden Kindknoten, bis die maximale Tiefe erreicht ist oder alle Datenpunkte in einem Knoten zur selben Klasse gehören. Achte darauf, dass du keine Bibliotheken außer numpy, math, collections.Counter und time verwendest – das ist strikt vorgegeben.

Performance-Metriken und Confusion Matrix

Um die Qualität deines Baums zu bewerten, berechnest du eine Confusion Matrix. Für binäre Klassifikation sieht sie so aus:

Daraus leitest du Metriken ab wie:

• Accuracy: (TP + TN) / (TP + TN + FP + FN)
• Precision: TP / (TP + FP)
• Recall: TP / (TP + FN)
• F1-Score: 2 * Precision * Recall / (Precision + Recall)

Für Multi-Class-Klassifikation kannst du jede Klasse einzeln betrachten (One-vs-Rest) oder einen gewichteten Durchschnitt berechnen. In deinem Code musst du diese Metriken für beliebig viele Klassen implementieren.

Random Forests: Mehr Bäume, bessere Vorhersagen

Ein einzelner Entscheidungsbaum neigt zu Overfitting. Die Lösung: Random Forests. Du trainierst viele Bäume auf zufälligen Teilmengen der Daten und Features und lässt sie dann abstimmen. Das reduziert die Varianz und verbessert die Generalisierung. Im Assignment implementierst du einen Random Forest, der aus einer Liste von Entscheidungsbäumen besteht. Die Vorhersage erfolgt per Mehrheitsentscheid (bei Klassifikation).

Wann lohnt sich ein Random Forest?

Stell dir vor, du entwickelst eine App zur Vorhersage von Aktienkursen (ein Trendthema unter Studierenden). Ein einzelner Baum könnte auf verrauschten Daten schlecht abschneiden, aber ein Wald aus 100 Bäumen liefert robustere Ergebnisse. Allerdings steigt der Rechenaufwand – hier kommt Vectorization wieder ins Spiel, um die vielen Bäume effizient zu trainieren.

Häufige Fehler und Tipps

• Rundung: Runde alle Ergebnisse auf 6 Dezimalstellen mit round(x, 6).
• Imports: Verwende nur die erlaubten Bibliotheken. Kein sklearn, pandas oder graphviz im eigentlichen Code (nur im Notebook zur Visualisierung).
• Tests: Nutze die bereitgestellten Testdateien decision_trees_submission_tests.py und die Jupyter-Notebooks, um deine Implementierung schrittweise zu prüfen.
• Zeitlimits: Achte auf die Laufzeit – besonders bei den Challenge-Datensätzen. Vectorization ist hier der Schlüssel.
• Gradescope: Du kannst nur 2 Submissions pro Stunde einreichen. Wähle am Ende deine beste Abgabe als „Active“ aus.

Fazit

Entscheidungsbäume und Multi-Class-Klassifikation sind zentrale Konzepte des maschinellen Lernens. Mit diesem Tutorial hast du eine solide Grundlage, um das CS6601 Assignment 4 zu meistern. Denk daran: Übung macht den Meister – und Vectorization macht den Code schnell. Viel Erfolg!