3.2 Klassifikation: kNN, Bäume, Naive Bayes, SVM

Worum geht’s#

Klassifikation ist die wohl alltäglichste Lernaufgabe: Gegeben sind beschriftete Beispiele — Pilze mit „essbar/giftig”, Mails mit „Spam/kein Spam” —, gesucht ist eine Funktion, die ein neues Objekt einer dieser Klassen zuordnet. Anders als bei der Regression (3.1) ist die Zielgröße diskret. Das klingt nach einem einzigen Problem, doch die spannende Beobachtung dieses Kapitels ist, dass dafür vier sehr unterschiedliche Denkweisen existieren — und jede eine andere Frage stellt.

Mir ging es beim Durcharbeiten weniger um die vier Algorithmen als Rezepte, sondern um die Achse, auf der sie liegen. Ein k-nächste-Nachbarn-Klassifikator (kNN) merkt sich einfach alle Daten und entscheidet erst zur Anfragezeit — er lernt streng genommen gar kein Modell. Ein Entscheidungsbaum komprimiert die Daten dagegen vorab zu einer Reihe von Ja/Nein-Fragen. Naive Bayes baut ein Wahrscheinlichkeitsmodell der Daten und dreht es per Bayes-Regel um. Eine Support Vector Machine (SVM) sucht nicht irgendeine Trennfläche, sondern die mit maximalem Sicherheitsabstand. Hinter dieser Vielfalt steht eine einzige tiefe Unterscheidung — generativ gegen diskriminativ —, und genau die will ich greifbar machen, statt vier Folien-Rezepte nachzuerzählen.

Kernkonzepte#

kNN — der faule Klassifikator#

kNN ist der minimalistischste Ansatz überhaupt: Es gibt keine Trainingsphase. Man speichert alle Beispiele und klassifiziert einen Anfragepunkt $x$, indem man seine $k$ nächsten Nachbarn sucht und unter ihnen abstimmen lässt.

Der einzige echte Hyperparameter ist $k$, und er steuert direkt einen Bias-Varianz-Kompromiss: Bei $k = 1$ folgt die Entscheidungsgrenze jedem einzelnen Punkt — sehr flexibel, aber rauschempfindlich und überangepasst. Große $k$ mitteln über viele Nachbarn und glätten die Grenze, bis sie bei $k = N$ alles der globalen Mehrheit zuschlägt. Praktisch wählt man $k$ ungerade (kein Patt) und meist klein: Laut Vorlesung erreicht man mit $k = 3, 5, 7$ schon Klassifikationsleistungen, die sich durch Erhöhen von $k$ kaum noch verbessern. Genau diesen Effekt macht die folgende Insel sichtbar.

kNN hat keine Trainingskosten, aber teure Vorhersagen ($O(N)$ Distanzen je Anfrage) und leidet unter dem Fluch der Dimensionalität: In hochdimensionalen Räumen werden alle Abstände ähnlich groß, und „nächster Nachbar” verliert seine Aussagekraft.

Entscheidungsbäume — Fragen statt Distanzen#

Ein Entscheidungsbaum klassifiziert durch eine Folge von Tests an den Attributen: An jedem inneren Knoten wird ein Attribut abgefragt, jede Kante entspricht einem Antwortwert, jedes Blatt einer Klasse. Der Reiz liegt in der Lesbarkeit — der Baum ist seine eigene Erklärung, was ihn zur Brücke zwischen Lernen und symbolischer KI (8.1) macht.

Der einfachste Vorläufer ist die OneR-Regel (1-Regel): eine einzige IF (Attribut = w) THEN (Klasse = k)-Regel, ausgewählt über das Attribut mit der besten Vorhersage — in der Vorlesung am Tennis-/Wetterdatensatz demonstriert. Der Entscheidungsbaum verallgemeinert das zu einer geschachtelten Folge solcher Tests.

Gebaut wird er gierig und rekursiv: Wähle das Attribut, das die Beispiele am „reinsten” aufteilt, und wiederhole das auf jeder Teilmenge. Die Vorlesung nennt dazu zwei Auswahl-Strategien: Strategie 1 wählt stets das Attribut, das die verbleibenden Beispiele am wenigsten fehlklassifiziert (genau das Kriterium aus Blatt 7); Strategie 2 wählt das Attribut mit dem maximalen Informationsgewinn — die Grundlage des ID3-Algorithmus. „Reinheit” lässt sich also verschieden messen — über die Fehlklassifikationsrate (wie viele Sätze liegen nach dem Split noch falsch?), über die Entropie bzw. den daraus folgenden Informationsgewinn, oder über die Gini-Unreinheit:

Die Vorlesung nennt mehrere Implementierungen: ID3 für nominale Merkmale, J48 (die WEKA-Variante von C4.5) für numerische Merkmale. Ein ungebremster Baum wächst, bis jedes Blatt rein ist — und passt sich dabei an das Rauschen der Trainingsdaten an (Überanpassung). Gegenmittel ist Pruning: nachträgliches Zurückschneiden zu schwacher Splits oder ein vorzeitiger Stopp, was Generalisierung gegen Trainingsgenauigkeit eintauscht. Bündelt man viele Bäume zu einem Ensemble — per Bagging (Mehrheitsvotum unabhängig trainierter Bäume, z. B. Random Forest) oder Boosting (sequentiell, jeder Baum gewichtet die Fehler des Vorgängers stärker, z. B. XGBoost / Gradient Boosted Trees) —, wird aus schwachen Lernern ein starker Klassifikator. In der KNIME-Churn-Prediction der Vorlesung gewinnt entsprechend der Gradient-Boosted-Tree.

Naive Bayes — generativ und erstaunlich robust#

Bevor man Merkmale anschaut, lohnt die Baseline der Vorlesung: ZeroR (0-Regel) ordnet jeden Punkt schlicht der häufigsten Klasse zu (nur die A-priori $P(K_i)$). ZeroR klassifiziert im Folienbeispiel rund 62 % korrekt — ein aufwändigeres Verfahren muss diese Marke erst schlagen, sonst lohnt der Aufwand nicht. Genau dieser Benchmark-Gedanke macht ZeroR (und Naive Bayes) als Vergleichspunkt nützlich.

Naive Bayes dreht die Frage dann um: Statt direkt $P(c \mid x)$ zu modellieren, beschreibt es, wie die Daten entstehen ($P(x \mid c)$), und wendet die Bayes-Regel an. Die titelgebende naive Annahme ist die bedingte Unabhängigkeit der Merkmale gegeben die Klasse:

Die Vorlesung rechnet das am Früchte-Beispiel vor (Merkmale länglich, gelblich, süßlich; Klassen Banane/Orange/Sonstiges). Es zeigt zugleich eine Tücke: Sobald ein bedingter Faktor $P(x_i \mid c) = 0$ ist, kippt das ganze Produkt auf null (Orange wird so für eine längliche Frucht ausgeschlossen). Gegenmittel ist die Laplace-Glättung — man addiert zu allen Zählern einen festen Wert (z. B. 1). Für numerische Merkmale schätzt man $P(x_i \mid c)$ stattdessen über eine Dichtefunktion aus Mittelwert und Standardabweichung.

SVM — der maximale Sicherheitsabstand#

Eine SVM sucht unter allen trennenden Hyperebenen $w \cdot x + b = 0$ diejenige mit dem größten Abstand (Margin) zu den nächsten Punkten beider Klassen. Nur diese Randpunkte, die Stützvektoren, bestimmen die Lösung; alle übrigen sind irrelevant. Der maximale Margin ist das geometrische Argument dafür, warum SVMs gut generalisieren.

Generativ vs. diskriminativ ist die Achse, die diese Verfahren ordnet: Naive Bayes ist generativ (es modelliert $P(x \mid c)$ und kann Daten erzeugen); kNN, Entscheidungsbäume und SVM sind diskriminativ — sie ziehen direkt die Trennlinie, ohne die Datenverteilung zu erklären.

Praxis#

Ich setze die vier Begriffe an einem kleinen, vollständig nachrechenbaren Datensatz fest: dem Wachstums-Datensatz aus Blatt 7 (16 Sätze, Attribute Feuchte, Säure, Temp, Zielklasse Wachstum; python/data/wachstum.csv). Derselbe Datensatz taucht in 5.1 beim Clustering wieder auf — dort ohne Labels.

(a) Trainings-Workflow. Der Ablauf ist verfahrensunabhängig immer derselbe und unten als Flussdiagramm gerendert: Den beschrifteten Datensatz $D$ in Trainings- und Testteil aufspalten (bei knappen Daten Kreuzvalidierung), auf dem Trainingsteil einen Lernalgorithmus (Baum, Naive Bayes, kNN, SVM …) ein Modell $K$ anpassen lassen, dieses auf dem zurückgehaltenen Testteil evaluieren und — falls nötig — über eine Rückkopplung Hyperparameter oder Modellklasse anpassen. Erst der so geprüfte Klassifikator geht in die Anwendung.

(b) Verwendung von $K$. Ein trainierter Klassifikator bildet einen neuen, ungesehenen Merkmalsvektor $x=[M_1,\dots,M_m]$ auf eine der Klassen $C_1, C_2, C_3$ ab (viele Verfahren liefern zusätzlich eine Wahrscheinlichkeits-/Konfidenz­schätzung je Klasse). Eingesetzt wird $K$ als Entscheidungs- oder Vorfilter: Pilz essbar/giftig, Mail Spam/Ham, Kreditantrag gut/schlecht. Wichtig ist die Annahme, dass neue Daten aus derselben Verteilung stammen wie die Trainingsdaten — bricht sie (Verteilungsdrift), sinkt die Güte.

(c) Bewertungskriterien. Nicht nur die Genauigkeit (Anteil korrekt klassifizierter Sätze), sondern bei mehreren/unausgewogenen Klassen vor allem die Konfusionsmatrix und daraus Precision, Recall und F1 je Klasse; für binäre Probleme zusätzlich ROC/AUC. Daneben zählen Generalisierung (Train- vs. Test-Lücke), Robustheit gegen Rauschen, Interpretierbarkeit (ein Baum erklärt sich selbst, eine SVM kaum), sowie Trainings-/Vorhersagekosten (kNN ist im Training billig, in der Vorhersage teuer).

(d) Güte-Bewertung. Man bewertet nie auf den Trainingsdaten (das überschätzt die Leistung), sondern auf einem zurückgehaltenen Testteil bzw. per $k$-facher Kreuzvalidierung (Mittel über $k$ Faltungen, ehrlich bei kleinen Datensätzen). Aus der Konfusionsmatrix des Testteils liest man die Maße aus (c) ab; eine Baseline (ZeroR = häufigste Klasse) zeigt, ob das Modell überhaupt etwas Nützliches gelernt hat. Genau dieses Vorgehen setze ich in A5 praktisch um.

(a) Wurzelwahl. Für jedes Attribut bilde ich den ersten Split, gebe jeder entstehenden Gruppe ihre Mehrheitsklasse und zähle die verbleibenden Fehler. Ohne jeden Split wäre die Mehrheit „gut”, was 8 von 16 Sätzen falsch lässt.

• Feuchte: feucht → 4 schlecht / 1 gut (1 Fehler), trocken → 7 gut / 4 schlecht (4 Fehler) ⟹ 5 Fehler.
• Säure: drei gemischte Gruppen ⟹ 7 Fehler.
• Temp (bester Schwellwert) ⟹ 7 Fehler.

Feuchte minimiert die Fehlerzahl und wird damit zur Wurzel. Anschaulich: Nasse Erde bedeutet fast immer schlechtes Wachstum (4 von 5), das Attribut trennt am schärfsten.

(b) Klassifikation. Der fertige Baum führt Nr.17 über trocken → neutral → Temp $\le 7$ auf gut, und Nr.18 landet schon im Feucht-Ast (alkalisch wächst hier nie) auf schlecht. Den Python-Lauf unten nutze ich, um genau diese beiden Vorhersagen unabhängig zu bestätigen.

(c) Regeln (gleichbedeutend mit dem Baum):

1. Feuchte = feucht und Säure ≠ neutral ⟹ schlecht
2. Feuchte = feucht und Säure = neutral und Temp ≤ 9 ⟹ schlecht (sonst gut, das ist allein Nr.12)
3. Feuchte = trocken und Säure = alkalisch ⟹ gut
4. Feuchte = trocken und Säure = basisch und Temp > 3 ⟹ gut (sonst schlecht)
5. Feuchte = trocken und Säure = neutral und Temp ≤ 7 ⟹ gut, sonst schlecht

Nachrechnen in Python#

Das Skript python/src/eport_figures/praxis/p_3_2_klassifikation.py rechnet die Wurzelwahl per Fehlklassifikation selbst nach, baut dann mit sklearn den vollständigen Baum (Kriterium Entropie), druckt ihn als Regeln und klassifiziert Nr.17/Nr.18 — das löst A2b unabhängig vom Handbaum. Der Kern der Wurzelwahl:

def _misclass_split(df, series):
    """Fehlklassifikationen eines Splits: jede Gruppe -> ihre Mehrheitsklasse."""
    err = 0
    for _, idx in series.groupby(series).groups.items():
        labels = df.loc[idx, "Wachstum"]
        err += int((labels != labels.value_counts().idxmax()).sum())
    return err

clf = DecisionTreeClassifier(criterion="entropy", random_state=0).fit(feat, y)
print(export_text(clf, feature_names=list(feat.columns)))
print(clf.predict(qfeat))   # Vorhersage für Nr.17 und Nr.18

Die echte Ausgabe:

=== A2a: erster Split — Fehlklassifikationen je Attribut ===
  Datensatz: 16 Sätze, Klassen ['gut', 'schlecht']
  ohne Split: Mehrheit 'gut', 8 Fehler von 16

  Feuchte  -> 5 Fehler   [feucht: {'schlecht': 4, 'gut': 1}, trocken: {'gut': 7, 'schlecht': 4}]
  Saeure   -> 7 Fehler   [alkalisch: {'schlecht': 2, 'gut': 2}, basisch: {'gut': 3, 'schlecht': 2}, neutral: {'schlecht': 4, 'gut': 3}]
  Temp<=3   -> 7 Fehler   (bester Schwellwert)

  -> Wurzel = 'Feuchte' mit 5 Fehlern (minimiert die Fehlklassifikation).
     Feuchte trennt am schärfsten: 'feucht' ist fast reines 'schlecht' (4 von 5).

=== A2c: Baum als Regeln (sklearn, criterion='entropy') ===
|--- Feuchte_trocken <= 0.50
|   |--- Temp <= 9.00
|   |   |--- class: schlecht
|   |--- Temp >  9.00
|   |   |--- class: gut
|--- Feuchte_trocken >  0.50
|   |--- Saeure_neutral <= 0.50
|   |   |--- Temp <= 3.50
|   |   |   |--- class: schlecht
|   |   |--- Temp >  3.50
|   |   |   |--- class: gut
|   |--- Saeure_neutral >  0.50
|   |   |--- Temp <= 7.50
|   |   |   |--- class: gut
|   |   |--- Temp >  7.50
|   |   |   |--- class: schlecht

  Trainingsgenauigkeit: 100.0 %

=== A2b: Klassifikation neuer Sätze ===
  Nr.17 [trocken, neutral, Temp 7]  ->  gut
  Nr.18 [feucht, alkalisch, Temp 7]  ->  schlecht
  Erwartet (Handbaum): Nr.17 -> gut (trocken/neutral/Temp<=7), Nr.18 -> schlecht (feucht)

=== kNN auf denselben (one-hot) Daten ===
  k=1:  Nr.17 -> gut       Nr.18 -> schlecht   (LOO-Genauigkeit 56.2 %)
  k=3:  Nr.17 -> gut       Nr.18 -> schlecht   (LOO-Genauigkeit 62.5 %)
  k=5:  Nr.17 -> gut       Nr.18 -> schlecht   (LOO-Genauigkeit 56.2 %)

Das Skript bestätigt meine Handrechnung an beiden Stellen: Feuchte ist mit 5 Fehlern die fehlerminimale Wurzel, und beide Anfragesätze werden wie erwartet klassifiziert — Nr.17 → gut, Nr.18 → schlecht. Ein ehrlicher Hinweis: sklearn optimiert die Entropie, nicht die Fehlklassifikation, und ordnet die Wurzel-Kante spiegelverkehrt (Feuchte_trocken ≤ 0.5 ist der Feucht-Ast). Im Feucht-Ast nutzt es zudem direkt Temp ≤ 9 statt meines Zwischenschritts über die Säure. Beide Bäume sind auf diesen Daten trainingsfehlerfrei und liefern dieselben Vorhersagen — ein schöner Beleg dafür, dass es den Baum nicht gibt, sondern viele äquivalente.

Auffällig ist die kNN-Zeile: Auf demselben Datensatz erreicht kNN nur rund 56–63 % Leave-one-out-Genauigkeit, weil die one-hot-codierten Nominalattribute alle denselben Abstand haben und die Temperatur die Distanz dominiert. Für Nr.17/Nr.18 stimmt es zwar zufällig mit dem Baum überein, doch der Vergleich zeigt: Ein Verfahren, das die Attributstruktur nutzt (Baum), schlägt hier das rein distanzbasierte kNN deutlich.

Aufgabe 5 (Blatt 7) — den KI-Assistenten auf echte Datensätze loslassen#

Ich übernehme die Rolle des KI-Assistenten und löse die Pilzsucher-Klassifikation in Python auf dem echten UCI-Mushroom-Datensatz (data/mushroom.csv, 8124 Pilze, 22 nominale Merkmale) — und prüfe das Ergebnis mit einem sauberen Train/Test-Split statt der Leistung blind zu glauben:

=== Aufgabe 5 / A3c — Pilz-Klassifikator (UCI Mushroom, 8124 Sätze) ===
  8124 Pilze, 22 Merkmale, Klassen essbar(e)/giftig(p)
  Split: 5686 Training / 2438 Test (stratifiziert)
    Entscheidungsbaum  Test-Genauigkeit 100.00 %
    Naive Bayes        Test-Genauigkeit  94.95 %
    kNN (k=5)          Test-Genauigkeit  99.79 %
  Bestes Einzelmerkmal (OneR): 'odor' klassifiziert allein schon 98.5 % korrekt.

=== Aufgabe 5b — weiterer echter Datensatz: Breast Cancer (569 Sätze) ===
  569 Sätze, 30 numerische Merkmale, 2 Klassen
    Random Forest      Test-Genauigkeit  94.15 %
    Log. Regression    Test-Genauigkeit  98.83 %

Drei Beobachtungen. Erstens ist der Mushroom-Satz fast trivial separierbar: Der Entscheidungsbaum trifft auf dem Testteil jeden Pilz, und schon das einzige Merkmal odor (Geruch) klassifiziert per OneR-Regel $98{,}5\,\%$ korrekt — ein schönes Beispiel dafür, dass manchmal ein gutes Merkmal mehr zählt als ein komplexes Modell. Zweitens verliert Naive Bayes ein paar Prozent, weil seine Unabhängigkeitsannahme die korrelierten Pilzmerkmale verletzt — genau die Tücke aus den Kernkonzepten. Drittens zeigt der Wechsel zum medizinischen Breast-Cancer-Datensatz (569 Sätze, 30 numerische Merkmale), dass derselbe Workflow ohne Umbau trägt — hier liegt die lineare logistische Regression ($98{,}8\,\%$) sogar vor dem Random Forest.

Bezug zur mobilen Pilzsucher-App. Wie nutzt man das Modell auf dem Smartphone, ohne eine schwergewichtige ML-Lernumgebung mitzuliefern? Der Baum beantwortet das elegant: Ein trainierter Entscheidungsbaum ist eine kompakte Folge von if/then-Regeln. Man exportiert sie (oder die odor-Tabelle) als wenige Zeilen Code bzw. JSON und bettet sie direkt in die App ein; die Lernumgebung bleibt auf dem Entwicklungsrechner, nur das Ergebnis wandert ins Gerät. Wichtige Warnung: Auf einem echten Wildpilz darf man sich auf so ein Modell nicht verlassen — der Datensatz deckt nur 23 Arten ab, und ein odor-Merkmal lässt sich per Foto-App gar nicht erheben. Das Experiment lehrt Methodik, ersetzt keinen Pilzberater.

Querbezüge#

• 3.1 / 3.3 / 3.4 (Maschinelles Lernen): kNN, Bäume, Naive Bayes und SVM sind die Klassifikations-Werkzeuge, deren Implementierung 3.3 in Python vertieft und deren Güte 3.4 (Evaluation, erklärbare KI) mit Konfusionsmatrix, Präzision und Recall bewertet. Der Entscheidungsbaum ist dort das Paradebeispiel eines von Haus aus interpretierbaren Modells.
• 5.1 (Clustering): Genau derselbe Wachstums-Datensatz wird beim Clustering ohne die Spalte Wachstum verwendet. Der Gegensatz ist lehrreich: Klassifikation ist überwacht (Labels vorhanden, kNN nutzt sie), Clustering unüberwacht (es sucht Gruppen ohne Labels). kNN und k-Means teilen die euklidische Distanz und den Buchstaben $k$, meinen damit aber völlig Verschiedenes — Nachbarschaft gegen Clusterzahl.
• 8.1 (Symbolik / Expertensysteme): Die Übersetzung des Baums in Wenn-dann-Regeln (Teil c) ist die direkte Brücke vom Lernen zur symbolischen KI: Ein gelernter Baum ist eine kompakte Regelbasis, wie sie ein Expertensystem von Hand pflegt — nur eben aus Daten gewonnen statt von Experten formuliert.
• Stochastik: Naive Bayes ist angewandte Wahrscheinlichkeitsrechnung — die Bayes-Regel, bedingte Unabhängigkeit und der MAP-Schätzer stammen direkt aus der Stochastik-Vorlesung.
• Lineare Algebra & Numerik: Die SVM-Trennebene $w\cdot x + b$ ist ein Skalarprodukt, der Kernel-Trick ersetzt es durch eine Kernfunktion, und die Margin-Maximierung ist ein quadratisches Optimierungsproblem (Numerik).
• Algorithmen & Datenstrukturen: Effizientes kNN braucht räumliche Indexstrukturen wie k-d-Bäume, um nicht jede Anfrage in $O(N)$ zu beantworten — ein direkter Anwendungsfall der A&D-Vorlesung.

Quellen#

• Foliensätze _340_ML_Classification.pdf, _341_ML_kNN.pdf, _342_ML_DecisionTree.pdf, _343_ML_NaiveBayes.pdf, _344_ML_SVM.pdf — Grundlage für Notation und Verfahrensgerüste. Die Einordnung entlang der Achse generativ/diskriminativ und der direkte Vergleich Baum gegen kNN auf identischen Daten ist meine eigene Rahmung, nicht die Folienreihenfolge.
• Übungsblatt 7 (ki_ueb320_Learn.pdf), Aufgaben 1, 2 und 5 — die Baumkonstruktion auf dem Wachstums-Datensatz, die Klassifikator-Theorie und das KI-Assistent-Experiment auf echten Datensätzen.
• Russell & Norvig, Artificial Intelligence: A Modern Approach, Kap. 19 — als Referenz für die saubere Definition von Informationsgewinn, Pruning und die Abgrenzung generativ/diskriminativ konsultiert.
• Quinlan (1986), Induction of Decision Trees (Machine Learning) — die Primärquelle des ID3-Algorithmus und des Informationsgewinns, und Cortes & Vapnik (1995), Support-Vector Networks (Machine Learning) — die Originalarbeit zur SVM mit Soft-Margin und Kernen; beide habe ich für die korrekte Einordnung der namentlich genannten Verfahren herangezogen.
• scikit-learn (DecisionTreeClassifier, KNeighborsClassifier, export_text, plot_tree) — ausprobiert, um den Handbaum gegenzurechnen; die Erkenntnis, dass der entropiebasierte sklearn-Baum von meinem Fehlklassifikations-Baum abweicht, aber dieselben Vorhersagen liefert, stammt direkt aus diesem Experiment.