k-Nächste-Nachbarn-Algorithmus einfach erklärt

Stell dir bekannte Früchte vor, zu denen Größe, Masse und Obstart gespeichert sind. Für eine neue Frucht sucht kNN nach bekannten Früchten mit ähnlichen Merkmalen. Deren Ergebnisse bilden die Grundlage der Vorhersage.

Weil die richtigen Ausgaben der Trainingsdaten bekannt sind, gehört kNN zum überwachten Lernen. Es ist kein Clustering-Verfahren: Beim Clustering werden Gruppen ohne vorgegebene Klassen gesucht.

kNN wird außerdem instanzbasiert und Lazy Learning genannt. Das Verfahren speichert die Trainingsdaten, erstellt aber keine umfangreiche Modellformel. Die eigentliche Rechenarbeit findet erst statt, wenn eine Vorhersage benötigt wird.

Der Ablauf in fünf Schritten

1. Lege $k$ und ein geeignetes Distanzmaß fest.
2. Berechne den Abstand des neuen Punkts zu jedem Trainingspunkt.
3. Sortiere die Trainingspunkte nach ihrem Abstand.
4. Wähle die ersten $k$ Punkte aus.
5. Bestimme aus diesen Nachbarn die Vorhersage.

Bei einer Klassifikation gewinnt die Klasse mit den meisten Stimmen. Bei mehr als zwei Klassen ist das genauer eine Pluralität: Die größte Stimmenzahl reicht aus, auch wenn sie nicht mehr als die Hälfte aller Stimmen umfasst.

Bei einer Regression wird ein Zahlenwert vorhergesagt. Dafür verwendet man typischerweise den Mittelwert der Zielwerte der Nachbarn.

„Ähnlich“ muss als Abstand zwischen den Merkmalen messbar gemacht werden. Für zwei numerische Merkmale verwendet man häufig die euklidische Distanz, also die direkte Verbindung zwischen zwei Punkten.

Für $P=(x_1,y_1)$ und $Q=(x_2,y_2)$ gilt:

$$d(P,Q)=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}$$

Die Manhattan-Distanz addiert dagegen die absoluten Koordinatendifferenzen:

$$d_M(P,Q)=|x_2-x_1|+|y_2-y_1|$$

Sie passt zu Situationen, in denen Wege nur entlang eines Rasters verlaufen. Die Hamming-Distanz zählt bei gleich langen Zeichenfolgen oder binären Vektoren die Positionen mit unterschiedlichen Einträgen. Welches Distanzmaß sinnvoll ist, hängt daher von der Art der Merkmale ab.

Vollständiges Klassifikationsbeispiel

Der neue Punkt ist $Q=(4,5)$. Vier Trainingspunkte sind bekannt:

Zum Sortieren reichen hier die quadrierten Abstände. Das Ziehen der Quadratwurzel würde ihre Reihenfolge nicht verändern. Die Reihenfolge lautet daher P2, P3, P4, P1.

Für $k=3$ sind P2, P3 und P4 die nächsten Nachbarn. Blau erhält zwei Stimmen, Rot eine Stimme. Die Vorhersage lautet Blau.

Warum die Skalierung wichtig ist

Angenommen, ein Merkmal liegt ungefähr zwischen 0 und 10, ein anderes zwischen 0 und 100000. Ohne Anpassung kann das zweite Merkmal den Abstand fast vollständig bestimmen, nur weil seine Zahlen größer sind.

Durch Normalisierung oder Standardisierung werden Merkmale auf vergleichbare Größenordnungen gebracht. Das macht sie nicht automatisch gleich wichtig, verhindert aber eine unbeabsichtigte Gewichtung allein durch unterschiedliche Skalen.

$k$ legt fest, wie viele Nachbarn Einfluss erhalten. Es gibt keinen Wert, der für alle Datensätze optimal ist.

• Bei $k=1$ übernimmt der neue Punkt das Ergebnis seines einzigen nächsten Nachbarn. Ein Ausreißer oder ein fehlerhaftes Label kann die Vorhersage stark beeinflussen.
• Ein kleines $k$ reagiert empfindlich auf lokale Besonderheiten und Rauschen. Das kann zu Überanpassung führen: Das Verfahren passt sehr gut zu den Trainingsdaten, verallgemeinert aber schlecht.
• Ein großes $k$ glättet lokale Muster. Ist $k$ zu groß, kann Unteranpassung entstehen, weil wichtige Unterschiede verschwinden.

Ein ungerades $k$ verringert bei zwei Klassen die Gefahr eines Gleichstands. Bei mehreren Klassen kann trotzdem ein Gleichstand um die größte Stimmenzahl auftreten. Eine vorher festgelegte Regel muss dann entscheiden, wie damit umgegangen wird.

k mit Validierungsdaten auswählen

Teile die vorhandenen beschrifteten Daten in Trainings- und Validierungsdaten. Probiere mehrere Werte für $k$ aus und miss für jeden Wert, wie oft die Validierungspunkte richtig vorhergesagt werden. Ein Wert mit guter Validierungsleistung ist ein Kandidat für das endgültige Verfahren.

Bei kleinen Datensätzen ist Leave-One-Out möglich:

1. Nimm einen Trainingspunkt vorübergehend heraus.
2. Klassifiziere ihn mit allen übrigen Punkten.
3. Wiederhole das für jeden Punkt und mehrere Werte von $k$.
4. Vergleiche die Trefferquoten.
5. Lege anschließend alle Punkte wieder in den Trainingsbestand zurück.

Nach der Wahl von Distanzmaß, Skalierung und $k$ wird das fertige Verfahren an separaten Testdaten geprüft. Diese Daten dürfen nicht schon zur Auswahl von $k$ gedient haben. Sonst wäre die Bewertung zu optimistisch.

Eine Konfusionsmatrix stellt für jede Klasse gegenüber, welches Label erwartet und welches vorhergesagt wurde. So erkennst du nicht nur die Gesamtzahl der Fehler, sondern auch, welche Klassen häufig verwechselt werden.

Die Genauigkeit berechnet sich als

$$\text{Genauigkeit}=\frac{\text{korrekte Testvorhersagen}}{\text{alle Testvorhersagen}}$$

Wo liegen die Grenzen von kNN?

• Vorhersagezeit: Für eine Abfrage müssen Abstände zu vielen gespeicherten Punkten berechnet werden. Große Datensätze können das Verfahren langsam machen.
• Speicherbedarf: Die Trainingsdaten müssen gespeichert bleiben.
• Viele Merkmale: In hohen Dimensionen werden Abstände oft weniger aussagekräftig. Für zuverlässige Nachbarschaften werden dann meist mehr Daten benötigt.
• Rauschen und Ausreißer: Besonders kleine Werte von $k$ reagieren empfindlich darauf.
• Unpassende Merkmale: Ein mathematisch kleiner Abstand ist nur dann sinnvoll, wenn die Merkmale tatsächlich relevante Ähnlichkeit ausdrücken.

Wenn du kNN beurteilst, frage immer in dieser Reihenfolge: Welche Merkmale beschreiben Ähnlichkeit? Wie wird Abstand gemessen? Welches $k$ bewährt sich bei der Validierung? Wie gut funktioniert die festgelegte Variante auf unbekannten Testdaten?