Entscheidungsbaum ID3 selbst programmieren

Einführung: Warum Entscheidungsbäume selbst programmieren?

Entscheidungsbäume sind ein zentrales Konzept im maschinellen Lernen und tauchen in aktuellen KI-Anwendungen wie personalisierten Newsfeeds oder Gaming-Bots auf. In dieser Anleitung zeige ich dir, wie du den ID3-Algorithmus für den CSCI 184 HW 1 – Part 2 implementierst – ohne auf scikit-learn zurückzugreifen. Du wirst lernen, wie man Bäume mit fester Tiefe erzeugt, Lernkurven plottet und die Ergebnisse mit scikit-learn vergleicht. Das Ganze basiert auf den bekannten MONK’s Datensätzen, die oft in der KI-Forschung verwendet werden.

Grundlagen des ID3-Algorithmus

ID3 (Iterative Dichotomiser 3) wählt bei jedem Knoten das Attribut mit der höchsten Informationsgewinn (basierend auf Entropie). Für deine Hausaufgabe musst du den Baum auf eine maximale Tiefe begrenzen. Stell dir vor, du trainierst einen Bot für ein Spiel wie FIFA 26 – der Bot lernt Entscheidungen Schritt für Schritt, ähnlich wie ein Entscheidungsbaum.

Entropie und Informationsgewinn

Die Entropie misst die Unreinheit einer Menge. Für binäre Klassifikation (wie bei MONK’s) gilt:

import math
def entropy(labels):
    total = len(labels)
    if total == 0:
        return 0
    p1 = sum(labels) / total
    p0 = 1 - p1
    if p1 == 0 or p0 == 0:
        return 0
    return -p1 * math.log2(p1) - p0 * math.log2(p0)

Implementierung des Entscheidungsbaums mit fester Tiefe

Deine Funktion id3(data, attributes, max_depth) soll rekursiv den Baum aufbauen. Hier ein Skelett:

def id3(data, attributes, max_depth, depth=0):
    # Abbruchbedingungen: alle gleiche Klasse, keine Attribute oder max_depth erreicht
    if depth == max_depth or len(set(data['label'])) == 1 or len(attributes) == 0:
        return majority_class(data['label'])
    best_attr = select_best_attribute(data, attributes)
    tree = {best_attr: {}}
    for value in get_values(data, best_attr):
        subset = data[data[best_attr] == value]
        tree[best_attr][value] = id3(subset, attributes - {best_attr}, max_depth, depth+1)
    return tree

Tipp für Lernkurven (Aufgabe a)

Für Tiefe 1 bis 10 musst du den durchschnittlichen Trainings- und Testfehler über mehrere Durchläufe berechnen. Verwende eine Schleife und speichere die Fehler in Listen. Am Ende plottest du sie mit matplotlib. Denk daran: Bei geringer Tiefe (z. B. 1) ist der Baum ein Weak Learner – ähnlich wie ein einfacher Filter in einer Social-Media-App.

Visualisierung und Confusion Matrix (Aufgabe b & c)

Nutze die bereitgestellte render_dot_file()-Funktion, um den Baum als PNG zu speichern. Für die Confusion Matrix kannst du sklearn.metrics.confusion_matrix verwenden – aber nur für Aufgabe c (scikit-learn). In Aufgabe b musst du deine eigene Implementierung nutzen. Beispiel:

from sklearn.metrics import confusion_matrix
predictions = [predict(tree, example) for example in test_data]
cm = confusion_matrix(true_labels, predictions)
print(cm)

Vergleich mit scikit-learn (Aufgabe c)

Scikit-learns DecisionTreeClassifier(criterion='entropy', max_depth=d) macht das Gleiche, aber optimiert. Deine selbst geschriebene Version hilft dir, die inneren Abläufe zu verstehen – das ist wie der Unterschied zwischen einem selbst gebauten PC und einem Fertig-Desktop. Für die Hausaufgabe musst du beide Ergebnisse präsentieren.

Häufige Fehler und Lösungen

Endlosrekursion: Vergiss nicht, die Tiefe zu inkrementieren und abzubrechen.
Falsche Entropieberechnung: Achte auf den Logarithmus von 0 – fange das mit einer if-Abfrage ab.
Datenformat: Die MONK’s-Dateien haben sechs Attribute (Spalten 2–7) und die Klasse in Spalte 1. Lade sie mit pandas.read_csv(..., header=None).

Fazit

Mit dieser Anleitung solltest du in der Lage sein, den ID3-Algorithmus für deine CSCI 184 Hausaufgabe zu implementieren. Denk daran: Übung macht den Meister – probiere verschiedene Tiefen aus und beobachte, wie sich Overfitting zeigt. Viel Erfolg!