k-Nächste-Nachbarn (k-NN)
Form die Nachbarschaft: ein Datenpunkt fragt seine k nächsten Bekannten – und stimmt ab.
Interaktives Klassifikations-Feld. Mit Pfeiltasten links und rechts änderst du k. Mit Pfeiltasten hoch und runter wählst du nacheinander einen Test-Ring aus und hörst seine Nachbar-Abstimmung. Escape hebt die Auswahl auf. Mit der Maus oder per Touch kannst du Punkte malen, löschen und Test-Ringe greifen.
0 / 0 Ringe korrekt. k ist 1
Zwei saubere Gruppen, aber ein verirrter roter Punkt kippt bei k=1 einen Ring. Schieb k ein Stück hoch (k=3) – schon glättet die Mehrheit die Grenze.
Jeder Ring ist ein Test-Punkt, der richtig klassifiziert werden will. Färbe das Feld so, dass alle Ringe grün leuchten – mit drei Werkzeugen: k schieben, Punkte malen und einen Test-Punkt greifen, um seine Nachbarn zu sehen.
Was auf dem Feld passiert
Diese Demo sortiert Punkte nach ihren Nachbarn. Hier steht, was du auf dem Bild siehst — die räumliche Aussage hinter den Zahlen.
- Was du siehst
- Ein quadratisches Feld voller bekannter Punkte in zwei Farben, Blau und Rot. Der eingefärbte Hintergrund teilt das Feld in eine blaue und eine rote Gegend, dazwischen verläuft eine geschwungene Grenze. Punkte mit einem Ring drumherum sind Testpunkte, die noch auf ihr Urteil warten.
- Was passiert
- Greifst du einen Ring, ziehen kurze Linien zu seinen k nächsten Nachbarn, und der Punkt nimmt die Farbe an, die unter diesen Nachbarn überwiegt. Schiebst du k hoch, wird die Grenze zwischen den Farbgegenden glatter; ziehst du k herunter, wird sie zackiger und schmiegt sich um einzelne Ausreißer.
- Was du tun kannst
- Wähle eine Aufgabe, stelle k mit dem Schieber ein, male neue Punkte in Blau oder Rot oder radiere sie weg, greife einen Ring zum Nachschauen und wechsle das Abstandsmaß.
- Worauf du achtest
- k-NN rechnet keine Formel aus. Es schaut nur, was in der Nähe liegt, und stimmt ab. Die Grenze zwischen den Farben zeichnen allein die Nachbarn — und k entscheidet, wie ruhig oder nervös sie verläuft.
Definition
k-NN in einem Satz
Analogie
Du ziehst in eine neue Stadt und willst wissen, ob deine Straße eher ruhig oder lebhaft ist. Du fragst einfach die k nächsten Nachbarn – und übernimmst, was die Mehrheit sagt.
Genau so klassifiziert k-NN: Für einen neuen Punkt sucht es die k ähnlichsten Beispiele und lässt sie abstimmen. Kein Training, keine Formel – nur Nachbarschaft.
Definition
k-NN ist ein Lazy Learner: Es speichert die Trainingsdaten und entscheidet erst zur Vorhersagezeit. Die Klasse eines Punktes ist die Mehrheitsklasse seiner k nächsten Nachbarn nach einer Distanz-Metrik.
Klein gewähltes k → zackige, rauschempfindliche Grenze (Varianz). Groß gewähltes k → glatte, träge Grenze (Bias). Dazwischen liegt der Sweet-Spot.
k-NN klassifiziert einen neuen Punkt in vier Schritten – ohne jedes Training, allein durch den Vergleich mit den nächsten Beispielen:
- Distanzen messen: Berechne den Abstand vom neuen Punkt zu jedem Trainingspunkt (z. B. euklidisch – Luftlinie – oder Manhattan – Häuserblock-Weg).
- Die k nächsten auswählen: Sortiere nach Abstand und behalte die k nächsten Nachbarn. k ist der einzige echte Regler.
- Abstimmen lassen: Zähle, welche Klasse unter diesen k Nachbarn am häufigsten vorkommt.
- Mehrheit gewinnt: Die häufigste Klasse wird die Vorhersage. Bei Gleichstand hilft ein ungerades k.
Genau das siehst du unten: Greif einen Ring und die k Nachbarn, ihre Distanz-Linien und die laufende Abstimmung leuchten auf. Schiebst du k, ändert sich die Mehrheit live.
Lazy Learning
k-NN trainiert nie. Die farbige Grenze entsteht erst in dem Moment, in dem du klassifizierst – jeder Punkt befragt einfach seine nächsten Nachbarn.
Mehrheits-Abstimmung
Greif einen Ring: die k nächsten Nachbarn leuchten auf, die Linien zeigen die Distanzen, und die Mehrheit gewinnt. Das ist die ganze Entscheidung.
Der k-Hebel = Bias-Varianz
Kleines k bügelt nichts aus und folgt jedem Ausreißer (Varianz). Großes k glättet alles, auch echte Struktur (Bias). Du hast es gerade selbst gespürt: zu klein bricht hier, zu groß bricht dort.
Prüfen
Kurzes Quiz – sitzt k-NN?
Warum nennt man k-NN einen „Lazy Learner"?
Wähle eine Antwort
1. Warum nennt man k-NN einen „Lazy Learner"?
2. Du erhöhst k von 1 auf einen großen Wert. Was passiert mit der Entscheidungsgrenze?
3. Ein einzelner Ausreißer-Punkt sitzt mitten im falschen Gebiet. Wie überstimmst du ihn am ehesten?
4. Wovon hängt ab, welche Nachbarn überhaupt „die nächsten" sind?
5. Warum wählt man k oft ungerade (1, 3, 5, …)?
Die Idee: frag deine Nachbarn
k-Nearest-Neighbors (k-NN) ist einer der einfachsten Klassifikationsalgorithmen überhaupt. Ein neuer, unbekannter Punkt bekommt einfach die Klasse, die unter seinen k nächsten Nachbarn in der Mehrheit ist. Es gibt keine Formel, kein Modell, keine Gewichte, die trainiert werden. Der Algorithmus verlässt sich allein auf die Annahme, dass Punkte, die nah beieinander liegen, meist zur selben Klasse gehören.
Lazy Learning: kein Training
k-NN ist ein Lazy Learner (fauler Lerner): In der Trainingsphase passiert nichts weiter, als dass alle Trainingspunkte gespeichert werden. Die gesamte Arbeit wird erst bei der Vorhersage getan. Deshalb ist das Training extrem schnell, jede einzelne Vorhersage aber vergleichsweise teuer, weil dafür der Abstand zu allen gespeicherten Punkten berechnet werden muss.
So läuft eine Vorhersage ab
- Abstände messen: Berechne die Distanz vom neuen Punkt zu jedem gespeicherten Punkt.
- k Nächste wählen: Sortiere nach Abstand und nimm die k dichtesten Nachbarn.
- Abstimmen: Jeder Nachbar gibt eine Stimme für seine Klasse ab; die Mehrheit gewinnt.
Das Distanzmaß (Metrik)
Was nah bedeutet, legt die Metrik fest. Die euklidische Distanz misst die Luftlinie (wurzel aus der Summe der quadrierten Differenzen), die Manhattan-Distanz nur die Wege entlang der Achsen. Die Wahl der Metrik verändert die Form der Entscheidungsgrenze sichtbar. Wichtig: Merkmale sollten vorher auf eine ähnliche Skala gebracht werden, sonst dominiert eine Achse mit großen Zahlenwerten die Distanz.
Die Rolle von k
Der Parameter k steuert, wie glatt die Entscheidungsgrenze wird. Ein kleines k (etwa k=1) folgt jedem Detail und reagiert empfindlich auf Ausreißer und Rauschen (hohe Varianz). Ein großes k mittelt über viele Nachbarn und glättet die Grenze, kann aber feine Strukturen verwischen (hoher Bias). Es gibt kein universell bestes k; der passende Wert hängt von den Daten ab und wird meist durch Ausprobieren oder Kreuzvalidierung gefunden. Ein ungerades k vermeidet bei zwei Klassen ein Unentschieden.
Eigenschaften
- Nicht-parametrisch: keine Annahme über die Form der Daten
- Instanzbasiert: die Trainingsdaten selbst sind das Modell
- Intuitiv: die Entscheidung lässt sich direkt an den Nachbarn ablesen
- Aufwändig zur Laufzeit: jede Vorhersage prüft alle gespeicherten Punkte
Spiele mit der Demo! Greif einen Test-Ring und schieb den k-Regler: Bei k=1 kann ein einzelner Ausreißer den Ring in die falsche Klasse kippen, bei einem größeren k überstimmt die Mehrheit den Störer. Auf der Spiral-Ebene siehst du das Gegenteil, ein zu großes k verwischt die feinen Arme, hier hilft nur ein mittleres k. Wechsle auch zwischen euklidisch und Manhattan und beobachte, wie sich die Grenze verformt.
1951: Fix und Hodges
Die Wurzeln von k-NN reichen zu einem technischen Bericht von Evelyn Fix und Joseph Hodges für die US Air Force zurück. Sie untersuchten die nicht-parametrische Unterscheidung von Klassen, also die Zuordnung ohne Annahme einer festen Verteilung, und legten damit den formalen Grundstein der Methode.
1967: Cover und Hart
Thomas Cover und Peter Hart veröffentlichten mit "Nearest Neighbor Pattern Classification" die berühmte theoretische Analyse. Sie bewiesen, dass die Fehlerrate des einfachen Nächster-Nachbar-Verfahrens (k=1) bei beliebig vielen Daten höchstens doppelt so hoch ist wie die des bestmöglichen (Bayes-optimalen) Klassifikators. Ein bemerkenswert starkes Ergebnis für ein so simples Verfahren.
Warum k-NN bis heute zählt
Trotz seines Alters ist k-NN weiter im Einsatz, oft als robuste Vergleichsbasis (Baseline) und als Kern von Empfehlungssystemen und Ähnlichkeitssuche. Moderne Varianten beschleunigen die teure Nachbarsuche mit räumlichen Datenstrukturen wie k-d-Bäumen oder mit approximativen Verfahren, die nur noch näherungsweise die nächsten Nachbarn finden, dafür aber sehr schnell sind.
1
# k-Nearest-Neighbors (k-NN) - Klassifikation
2
# Idee: ein Punkt erbt die Klasse seiner Nachbarn
3
# Lazy Learning - es gibt KEINE echte Trainingsphase
4
funktion trainiere(trainingsdaten):
5
# nichts anpassen, nichts berechnen ...
6
speicher = trainingsdaten # nur merken
7
return speicher
8
9
# Vorhersage fuer einen neuen, unbekannten Punkt
10
funktion klassifiziere(punkt, k, metrik):
11
# 1. Abstand zu ALLEN gespeicherten Punkten messen
12
fuer jeden nachbar in speicher:
13
abstand[nachbar] = distanz(punkt, nachbar, metrik)
14
15
# 2. Nach Abstand sortieren, die k naechsten nehmen
16
sortiere speicher nach abstand aufsteigend
17
nachbarn = die ersten k eintraege
18
19
# 3. Mehrheitsentscheid unter den k Nachbarn
20
stimmen_A = anzahl nachbarn mit klasse A
21
stimmen_B = anzahl nachbarn mit klasse B
22
wenn stimmen_A >= stimmen_B:
23
return klasse A
24
sonst:
25
return klasse B
26
27
# Distanzmass - wie "nah" gemessen wird
28
funktion distanz(a, b, metrik):
29
wenn metrik == euklidisch:
30
# Luftlinie
31
return wurzel((a.x-b.x)^2 + (a.y-b.y)^2)
32
sonst:
33
# Manhattan - nur entlang der Achsen
34
return |a.x-b.x| + |a.y-b.y|
35
36
# k klein = feine, aber verrauschte Grenze
37
# ungerades k vermeidet Gleichstand bei 2 Klassen
38
# Achtung: Merkmale vorher skalieren (sonst dominiert eine Achse)
39
# Kosten: jede Vorhersage vergleicht mit allen n Punkten (O(n))
40
# Theorie: bei viel Daten hoechstens 2x Bayes-Fehler (Cover & Hart)
💾 Merken statt lernen
k-NN trainiert nicht im üblichen Sinn. Es speichert einfach alle Trainingspunkte samt ihrer Klasse. Deshalb heißt es Lazy Learning: Die eigentliche Arbeit wird bis zur Vorhersage aufgeschoben.
funktion trainiere(trainingsdaten):
# nichts anpassen, nichts berechnen ...
speicher = trainingsdaten # nur merken
return speicher
💾 Speichern
Alle Trainingspunkte mit ihrer Klasse merken. Kein Training, nur Ablegen.
↔️ Abstände messen
Distanz vom neuen Punkt zu jedem gespeicherten Punkt berechnen.
👥 k Nächste wählen
Nach Abstand sortieren und die k dichtesten Nachbarn auswählen.
☑️ Abstimmen
Jeder Nachbar stimmt für seine Klasse, die Mehrheit gewinnt.
🏷️ Klasse zuweisen
Der neue Punkt bekommt die Klasse mit den meisten Stimmen.