Klassifizierung mit k-NN
Jetzt baust du dein erstes KI-Verfahren: k-NN (k-nearest neighbors, deutsch: k-nächste Nachbarn). Es ist ein klassisches Verfahren des überwachten Lernens und gleichzeitig einfach genug, um es in ein paar Zeilen Java zu implementieren.
Die Idee
k-NN ist faul: Es „lernt" nichts im Voraus. Statt ein kompliziertes Modell zu bauen, merkt es sich einfach alle Trainingsdaten. Wenn ein neuer, unbekannter Datenpunkt klassifiziert werden soll, schaut es sich die k nächsten Nachbarn in den Trainingsdaten an und gibt die Mehrheitsentscheidung zurück.
flowchart TD
A["Neuer Datenpunkt<br/>Label unbekannt"] --> B["Berechne Distanz<br/>zu allen Trainingspunkten"]
B --> C["Finde die k nächsten<br/>(z.B. k = 3)"]
C --> D["Welches Label ist<br/>in der Mehrheit?"]
D --> E["Verleihe dem neuen<br/>Punkt dieses Label"]
Schritt 1: Die Distanz
Zwei Punkte haben die Koordinaten und . Die euklidische Distanz ist:
In Java:
double distanz = Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));Bevor du den Code anschaust: Berechne auf Papier die Distanz zwischen dem Punkt (150, 7) und dem Punkt (100, 3). Was kommt heraus?
Tipp
Setze ein: , , , .
Schritt 2: Die Distanz als Methode
Wir erweitern die Datenpunkt-Klasse um eine Methode, die die Distanz zu einem anderen Datenpunkt berechnet.
Vergleiche deine Papierberechnung mit dem Programm. Stimmt der Wert überein?
Füge einen dritten Punkt new Datenpunkt(180, 8, "Apfel") hinzu und berechne die Distanz vom Apfel (150, 7) zu diesem Punkt. Was fällt auf?
Tipp
Der zweite Apfel (180, 8) ist näher am Apfel (150, 7) als die Birne (100, 3). Das ist genau die Grundlage von k-NN: nähere Nachbarn sind aussagekräftiger.
Schritt 3: Den Klassifikator bauen
Jetzt bauen wir den Klassifikator als Klasse KNNKlassifikator. Sie speichert die Trainingsdaten in einem Feld und klassifiziert neue Punkte in drei Schritten:
- Distanz zu allen Trainingspunkten berechnen
- Die k nächsten finden
- Mehrheitsentscheidung über die Labels
Bevor du das Programm ausführst: Der Testpunkt ist (170, 7). Welches Label erwartest du? Begründe mit den Trainingsdaten im Programm unten.
Tipp
Es zählt nicht der eine nächste Nachbar, sondern die Mehrheit unter den drei nächsten. Rechne die Distanzen von (170, 7) zu allen sechs Trainingspunkten aus und ordne sie der Größe nach.
k-NN ist ein diskriminatives Verfahren: Es ordnet Daten einer Kategorie zu. Es ist überwacht, weil es gelabelte Trainingsdaten benötigt. Und es ist faul (lazy learning), weil die meiste Arbeit erst bei der Klassifizierung passiert, nicht beim Training.
Ein Merkmal entscheidet fast allein. Das Gewicht liegt zwischen 90 und 200 Gramm, die Süßigkeit zwischen 2 und 9. Ein Unterschied von 50 Gramm geht mit 50 in die Distanz ein, ein Unterschied von 5 Süßigkeitsstufen nur mit 5. Die Süßigkeit fällt gegenüber dem Gewicht also kaum ins Gewicht — obwohl sie als Merkmal genauso wichtig sein könnte.
Echte KI-Systeme normieren deshalb ihre Merkmale: Sie rechnen jedes Merkmal auf denselben Bereich um (z.B. 0 bis 1), bevor sie Distanzen berechnen. Überlege: Wie würdest du die sechs Trainingspunkte auf den Bereich 0 bis 1 umrechnen?
a) Setze den Testpunkt auf (140, 6) — eine Frucht genau zwischen den beiden Gruppen. Führe das Programm mit k = 1, k = 3 und k = 5 aus. Was fällt auf?
b) Füge einen Ausreißer hinzu: einen Apfel bei (300, 2). Wie verändert sich die Klassifizierung des Testpunkts (170, 7) bei k = 3?
Tipp zu a)
Achte auf die Zeile „Stimmen: …". Bei k = 1 gibt es nur eine Stimme, bei k = 3 sind es drei. Schau nach, wer diese Stimmen abgibt.
Tipp zu b)
Bei k = 3 werden die drei nächsten Nachbarn gezählt. Wenn ein Apfel weit weg liegt, ist er wahrscheinlich nicht unter den nächsten drei — er sollte das Ergebnis nicht verändern. Aber probiere es aus.
Die Entscheidungsgrenze
Dieselben sechs Trainingspunkte, aber gezeichnet. Die eingefärbte Fläche zeigt, wie der Klassifikator jeden Punkt der Ebene einordnen würde — nicht nur den einen Testpunkt. Die Linie zwischen den beiden Farben heißt Entscheidungsgrenze.
a) Der Testpunkt steht schon auf (140 | 6) — dem Punkt aus der letzten Aufgabe. Schiebe k von 1 auf 3 auf 5 und beobachte die Tabelle unter der Zeichnung. Findest du dein Ergebnis von eben wieder?
b) Klicke an verschiedene Stellen der Fläche. Wo liegt die Grenze so, dass du sie nicht erwartet hättest?
c) Setze das Werkzeug auf + Apfel und setze einen Apfel weit rechts unten bei etwa (300 | 2) — den Ausreißer aus Aufgabe b). Verändert sich die Grenze in der Nähe des Testpunkts?
d) Setze den Haken bei Merkmale normieren. Die Grenze dreht sich. Erkläre mit dem Kasten oben, warum sie vorher fast senkrecht stand.
Tipp zu d)
Eine senkrechte Grenze bedeutet: Nur die x-Achse entscheidet, die y-Achse spielt keine Rolle. Was war noch einmal der Zahlenbereich des Gewichts, und was der der Süßigkeit?