K-Nearest Neighbors (KNN)

K-nächste Nachbarn (KNN) ist ein Algorithmus für überwachtes Lernen, der das Label eines neuen Beispiels anhand der k nächstgelegenen beschrifteten Beispiele vorhersagt: Bei der Klassifizierung wird unter diesen Nachbarn eine Mehrheitsentscheidung getroffen, bei der Regression ihr Mittelwert verwendet. KNN ist nichtparametrisch und „träge“: Der Algorithmus lernt keine Gewichte, sondern speichert lediglich die Trainingsdaten und führt alle Berechnungen erst bei einer angeforderten Vorhersage aus. Evelyn Fix und Joseph Hodges stellten das Verfahren 1951 vor. 1967 bewiesen Thomas Cover und Peter Hart, dass die Fehlerrate der Ein-Nächster-Nachbar-Regel bei unbegrenzter Datenmenge höchstens doppelt so hoch ist wie die des bestmöglichen Klassifikators. Dieselbe Suche nach nächsten Nachbarn wird heute in großem Maßstab in Vektordatenbanken und Bildsuchsystemen eingesetzt, die Einbettungen aus neuronalen Netzen vergleichen.

So trifft KNN eine Vorhersage#

Für jeden Abfragepunkt führt KNN drei Schritte aus:

1. Abstand messen: Der Abstand zwischen der Abfrage und jedem gespeicherten Beispiel wird berechnet. Der euklidische Abstand ist die Standardeinstellung, Manhattan- und Minkowski-Abstände sind gängige Alternativen, und für Einbettungen ist die Kosinusähnlichkeit üblich, da die Richtung eines Vektors seine Bedeutung trägt.
2. Nachbarn auswählen: Die k Beispiele mit den kleinsten Abständen werden ausgewählt.
3. Labels zusammenführen: Bei der Klassifizierung wird die häufigste Klasse unter den Nachbarn gewählt, bei der Regression der Mittelwert ihrer Werte. Bei der Entfernungsgewichtung (weights="distance" in scikit-learn) zählen nähere Nachbarn stärker.

Jedes Merkmal trägt zum Abstand bei, daher dominieren Merkmale mit großen Skalen: Das Einkommen in Euro würde das Alter in Jahren überwiegen. KNN-Pipelines standardisieren Merkmale deshalb zuerst oder vergleichen Einbettungen aus einem Modell zur Merkmalsextraktion, damit jede Dimension auf einer vergleichbaren Skala beiträgt.

k auswählen#

Der Wert von k bestimmt das Gleichgewicht zwischen Overfitting und Underfitting. Bei k = 1 beansprucht jeder Trainingspunkt, auch verrauschte und falsch beschriftete Punkte, einen eigenen Bereich, und die Entscheidungsgrenze wird gezackt. Bei sehr großem k reicht jede Abstimmung weit über die Abfrage hinaus und verwischt echte Klassengrenzen. Bei zwei Klassen verhindert ein ungerades k Stimmengleichstände, und Kreuzvalidierung ist das übliche Verfahren zur Wahl von k. Beim verrauschten Zwei-Monde-Datensatz von scikit-learn zeigt sich dieser Zielkonflikt an drei Werten:

from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier

# Two interleaving half-moons with overlapping, noisy points
X, y = make_moons(n_samples=1000, noise=0.35, random_state=0)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=0)

# Fitting only stores the points; each prediction is a vote among the k nearest ones
for k in (1, 15, 300):
    knn = KNeighborsClassifier(n_neighbors=k)
    knn.fit(X_train, y_train)
    print(f"k={k}: train {knn.score(X_train, y_train):.2f}, test {knn.score(X_test, y_test):.2f}")

Bei k = 1 merkt sich der Klassifikator seine Trainingspunkte und erzielt darauf einen Wert von 1.00 sowie 0.83 auf zurückgehaltenen Punkten. Bei k = 15 erreicht er 0.90 und 0.89 – das beste Testergebnis der drei Einstellungen. k = 300, also fast die Hälfte der 700 Trainingspunkte, glättet die Grenze so stark, dass beide Werte auf 0.84 und 0.81 sinken.

Nachbarsuche beschleunigen#

Bei einer Brute-Force-Suche wird die Abfrage mit allen n gespeicherten Punkten in d Dimensionen verglichen. Jede Vorhersage kostet daher ungefähr n × d Operationen, und der Speicherbedarf wächst mit dem Datensatz. Strukturen zur Raumaufteilung wie k-d-Bäume und Ball-Bäume überspringen in niedrigen Dimensionen die meisten Vergleiche. algorithm="auto" von scikit-learn wählt zwischen Brute Force, k-d-Baum und Ball-Baum. In hohen Dimensionen sorgt der Fluch der Dimensionalität dafür, dass die Abstände zwischen Punkten nahezu gleich sind und das Beschneiden von Bäumen keinen Vorteil mehr bringt. Große Systeme wechseln dann zu Indizes für die approximative Nächste-Nachbar-Suche (ANN), etwa HNSW-Graphen und Inverted-File-Indizes (IVF) mit Produktquantisierung, die in Bibliotheken wie FAISS implementiert sind. Diese Indizes liefern die meisten tatsächlichen nächsten Nachbarn, während sie die Abfrage nur mit einem kleinen Teil der gespeicherten Vektoren vergleichen:

KNN und verwandte Verfahren#

• K-means-Clustering: Ein unüberwachter Algorithmus, der unbeschriftete Punkte um erlernte Schwerpunkte in k Cluster gruppiert. Die gemeinsame Bezeichnung ist Zufall: Bei k-means steht k für die Anzahl der Cluster.
• Vektorsuche: Die Suchvariante desselben Vorgangs: Sie gibt die gespeicherten Elemente zurück, die einer Abfrageeinbettung am nächsten liegen, in der Regel mithilfe eines approximativen Index. Die Anwendung verwendet diese Elemente direkt.
• Support-Vektor-Maschinen und logistische Regression: Parametrische Modelle, die während des Trainings eine Entscheidungsgrenze lernen. Dadurch bleiben die Vorhersagekosten bei wachsendem Trainingsdatensatz konstant.

Anwendungen in der Praxis#

• Empfehlungssysteme: Die elementbasierte kollaborative Filterung empfiehlt Produkte, deren Bewertungs- oder Kaufvektoren den Elementen am nächsten liegen, die ein Nutzer bereits mochte.
• Anomalieerkennung: Der Abstand eines Punktes zu seinem k-ten nächsten Nachbarn dient als Anomaliewert. So fallen Transaktionen oder Sensormesswerte auf, die weit von allen normalen Beispielen entfernt sind.
• Ersetzung fehlender Werte: KNNImputer von scikit-learn füllt jede Lücke mit dem Mittelwert des jeweiligen Merkmals über die k ähnlichsten Zeilen.
• Bildsuche und Re-Identifizierung: Systeme vergleichen die Einbettung eines Bildes mit einer Galerie, um dasselbe Produkt, Gesicht oder dieselbe Person zu finden, die von einer anderen Kamera erfasst wurde. Die Ultralytics-Lösung zur Ähnlichkeitssuche erstellt mit CLIP von OpenAI Einbettungen für einen Bildordner, berechnet in einer exakten Brute-Force-Suche die Kosinusähnlichkeit jedes indexierten Bildes zu einer Textabfrage wie „rotes Auto“ und gibt die ähnlichsten Bilder zurück – standardmäßig bis zu 30.