K-Nearest Neighbors

K-Nearest Neighbors (KNN) ist einer der einfachsten und intuitivsten Machine-Learning-Algorithmen. Um einen neuen Datenpunkt zu klassifizieren, betrachtet er die K nächsten Trainingsbeispiele und führt eine Abstimmung durch — die Mehrheitsklasse gewinnt. Bei der Regression werden stattdessen die Werte der K Nachbarn gemittelt.

Dieses Kapitel behandelt:

• Wie der KNN-Algorithmus Schritt für Schritt funktioniert
• Distanzmetriken: Euklidisch, Manhattan und Minkowski
• Warum Feature-Skalierung für KNN entscheidend ist
• Wie man den richtigen Wert für K wählt
• Klassifikation und Regression mit scikit-learn
• Auswertung eines KNN-Klassifikators mit einer Konfusionsmatrix
• Stärken, Einschränkungen und wann KNN eingesetzt werden sollte

Wie KNN funktioniert

KNN ist ein Lazy Learner — es findet kein echtes „Training" statt. Stattdessen memoriert er den gesamten Datensatz und verschiebt alle Berechnungen auf den Zeitpunkt der Vorhersage.

Für einen neuen Punkt führt der Algorithmus folgende Schritte aus:

1. Berechnet den Abstand vom neuen Punkt zu jedem Trainingspunkt.
2. Wählt die K Trainingspunkte mit den kleinsten Abständen (die „nächsten Nachbarn").
3. Aggregiert ihre Labels:
   • Klassifikation — der neue Punkt erhält das häufigste Klassen-Label.
   • Regression — der neue Punkt erhält den Durchschnitt (oder gewichteten Durchschnitt) der Zielwerte der Nachbarn.

Da kein Modell trainiert werden muss, ist das Hinzufügen neuer Daten trivial — man hängt sie einfach an den Datensatz an. Der Nachteil ist, dass die Vorhersage bei großen Datensätzen langsam ist, weil die vollständige Abstandsberechnung jedes Mal durchgeführt wird.

Distanzmetriken

Das „Nächste" in KNN wird durch eine Distanzfunktion definiert. Die Standardeinstellung in scikit-learn ist die Euklidische Distanz, der geradlinige Abstand im n-dimensionalen Raum:

d(p, q) = sqrt( (p1-q1)² + (p2-q2)² + … + (pn-qn)² )

Zwei häufige Alternativen:

Die Metrik kann in scikit-learn mit dem Parameter metric geändert werden:

from sklearn.neighbors import KNeighborsClassifier

knn = KNeighborsClassifier(n_neighbors=5, metric='manhattan')

Warum Feature-Skalierung entscheidend ist

KNN berechnet rohe Abstände. Ein Feature, das in Tausenden gemessen wird (z. B. Gehalt), dominiert vollständig ein Feature, das in einzelnen Stellen gemessen wird (z. B. Jahre der Berufserfahrung), selbst wenn das kleinere Feature informativer ist.

Skaliere Features immer, bevor du KNN verwendest. Siehe das Kapitel zur Feature-Skalierung für eine vollständige Erklärung; die Kurzversion lautet:

from sklearn.preprocessing import StandardScaler

scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)   # fit on training data only
X_test_scaled  = scaler.transform(X_test)         # apply same transform to test data

Rufe fit_transform niemals auf dem Testset auf — das würde Testset-Statistiken in den Scaler einfließen lassen.

K wählen

K steuert den Bias-Varianz-Kompromiss:

• Kleines K (z. B. K=1) — sehr flexibel, passt sich den Trainingsdaten eng an, aber rauschempfindlich und anfällig für Overfitting. Ein einzelner Ausreißer als Nachbar kann die Vorhersage verändern.
• Großes K — glattere Entscheidungsgrenze, geringere Varianz, kann jedoch zu Underfitting führen und echte Klassengrenzen verwischen.

Der Standardansatz besteht darin, einen Bereich von K-Werten auszuprobieren und denjenigen mit der besten kreuzvalidierten Genauigkeit zu wählen:

import numpy as np
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import cross_val_score
from sklearn.datasets import load_iris
from sklearn.preprocessing import StandardScaler

iris = load_iris()
X, y = iris.data, iris.target

scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

k_range = range(1, 31)
cv_scores = []

for k in k_range:
    knn = KNeighborsClassifier(n_neighbors=k)
    scores = cross_val_score(knn, X_scaled, y, cv=5, scoring='accuracy')
    cv_scores.append(scores.mean())

best_k = k_range[np.argmax(cv_scores)]
print(f"Best K: {best_k}, CV Accuracy: {max(cv_scores):.4f}")

Erwartete Ausgabe:

Best K: 6, CV Accuracy: 0.9667

Weitere Details zur Kreuzvalidierung findest du im Kapitel zur Kreuzvalidierung.

Praktische Faustregeln:

• Bevorzuge ungerades K bei binärer Klassifikation, um Unentschieden zu vermeiden.
• Ein gängiger Ausgangspunkt ist K = sqrt(n), wobei n die Anzahl der Trainingsbeispiele ist.
• Validiere immer mit Kreuzvalidierung statt zu raten.

KNN-Klassifikation mit scikit-learn

Das folgende Beispiel verwendet den Iris-Datensatz — ein echtes Mehrklassenproblem — und führt durch den vollständigen Arbeitsablauf: Aufteilen, Skalieren, Trainieren, Vorhersagen, Auswerten.

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score, classification_report

# 1. Load a real dataset
iris = load_iris()
X, y = iris.data, iris.target

# 2. Split into training and test sets
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42, stratify=y
)

# 3. Scale features — critical for KNN
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled  = scaler.transform(X_test)

# 4. Train the classifier
knn = KNeighborsClassifier(n_neighbors=5)
knn.fit(X_train_scaled, y_train)

# 5. Predict and evaluate
y_pred = knn.predict(X_test_scaled)
print(f"Accuracy: {accuracy_score(y_test, y_pred):.2f}")
print()
print(classification_report(y_test, y_pred, target_names=iris.target_names))

Erwartete Ausgabe:

Accuracy: 0.93

              precision    recall  f1-score   support

      setosa       1.00      1.00      1.00        10
  versicolor       0.83      1.00      0.91        10
   virginica       1.00      0.80      0.89        10

    accuracy                           0.93        30
   macro avg       0.94      0.93      0.93        30
weighted avg       0.94      0.93      0.93        30

KNN mit K=5 erzielt eine Genauigkeit von 93 % auf diesem Testset mit 30 Samples. Setosa wird perfekt klassifiziert, weil es linear von den anderen beiden trennbar ist; Versicolor und Virginica überlappen sich etwas, was zu einigen Fehlklassifikationen führt.

Beachte das Argument stratify=y in train_test_split — es erhält die Klassenanteile in jeder Aufteilung, was besonders bei unausgewogenen Datensätzen wichtig ist. Siehe Train/Test-Aufteilung für Details.

Auswertung mit einer Konfusionsmatrix

Eine Konfusionsmatrix zeigt genau, welche Klassen das Modell miteinander verwechselt:

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import confusion_matrix

iris = load_iris()
X, y = iris.data, iris.target

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42, stratify=y
)

scaler = StandardScaler()
X_train_s = scaler.fit_transform(X_train)
X_test_s  = scaler.transform(X_test)

knn = KNeighborsClassifier(n_neighbors=5)
knn.fit(X_train_s, y_train)
y_pred = knn.predict(X_test_s)

cm = confusion_matrix(y_test, y_pred)
print(cm)

Erwartete Ausgabe:

[[10  0  0]
 [ 0 10  0]
 [ 0  2  8]]

Jede Zeile ist eine wahre Klasse; jede Spalte ist eine vorhergesagte Klasse. Diagonalwerte sind korrekte Vorhersagen; außerdiagonale Werte sind Fehlklassifikationen. Hier wurden 2 Virginica-Samples fälschlicherweise als Versicolor klassifiziert. Siehe das Kapitel zur Konfusionsmatrix für eine tiefere Erklärung.

KNN-Regression mit scikit-learn

Bei der Regression sagt KNN den Mittelwert der Zielwerte der K nächsten Nachbarn voraus. Ersetze KNeighborsClassifier durch KNeighborsRegressor:

from sklearn.datasets import fetch_california_housing
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsRegressor
from sklearn.metrics import mean_squared_error, r2_score
import numpy as np

# Load a real regression dataset (a subset for speed)
housing = fetch_california_housing()
X, y = housing.data[:2000], housing.target[:2000]

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42
)

scaler = StandardScaler()
X_train_s = scaler.fit_transform(X_train)
X_test_s  = scaler.transform(X_test)

knn_reg = KNeighborsRegressor(n_neighbors=5)
knn_reg.fit(X_train_s, y_train)
y_pred = knn_reg.predict(X_test_s)

rmse = np.sqrt(mean_squared_error(y_test, y_pred))
r2   = r2_score(y_test, y_pred)
print(f"RMSE: {rmse:.4f}")
print(f"R²:   {r2:.4f}")

Erwartete Ausgabe:

RMSE: 0.4217
R²:   0.8053

Der RMSE hat die gleichen Einheiten wie die Zielvariable (mittlerer Hauswert in $100k). Ein R² von 0,81 bedeutet, dass das Modell etwa 81 % der Varianz in diesem 2.000-Sample-Subset erklärt — ein starkes Ergebnis für einen nicht optimierten KNN-Basislinie.

Gewichtetes KNN

Standardmäßig haben alle K Nachbarn gleiches Gewicht, unabhängig davon, wie nah sie sind. Das Setzen von weights='distance' lässt nähere Nachbarn stärker zählen:

from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import accuracy_score

iris = load_iris()
X, y = iris.data, iris.target
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42, stratify=y
)

scaler = StandardScaler()
X_train_s = scaler.fit_transform(X_train)
X_test_s  = scaler.transform(X_test)

knn_uniform  = KNeighborsClassifier(n_neighbors=5, weights='uniform')
knn_distance = KNeighborsClassifier(n_neighbors=5, weights='distance')

knn_uniform.fit(X_train_s, y_train)
knn_distance.fit(X_train_s, y_train)

print(f"Uniform weights accuracy:  {accuracy_score(y_test, knn_uniform.predict(X_test_s)):.2f}")
print(f"Distance weights accuracy: {accuracy_score(y_test, knn_distance.predict(X_test_s)):.2f}")

Erwartete Ausgabe:

Uniform weights accuracy:  0.93
Distance weights accuracy: 0.97

Die Distanzgewichtung verbessert hier die Genauigkeit von 0,93 auf 0,97 — nähere Nachbarn haben mehr Einfluss, was hilft, mehrdeutige Grenzfälle aufzulösen.

Stärken und Einschränkungen

Wann KNN eingesetzt werden sollte

• Der Datensatz ist klein bis mittelgroß (Zehntausende von Samples).
• Du brauchst eine schnelle, interpretierbare Basislinie — KNN ist leicht zu erklären und zu debuggen.
• Du hast gut skalierte Features mit niedriger Dimensionalität.
• Die Entscheidungsgrenze ist komplex und nicht-linear.

Wann KNN vermieden werden sollte

• Große Datensätze. Die Vorhersagezeit skaliert mit der Anzahl der Trainingssamples (O(n·d) pro Anfrage). Bei Millionen von Samples solltest du Bibliotheken für approximative nächste Nachbarn (Faiss, Annoy) in Betracht ziehen oder zu einem schnelleren Algorithmus wechseln.
• Hochdimensionale Daten. In vielen Dimensionen werden alle Punkte annähernd gleich weit entfernt — der „Fluch der Dimensionalität". KNN verschlechtert sich schnell bei mehr als etwa 20 Features. Wende zuerst Dimensionsreduktion an (PCA, Feature-Selektion).
• Irrelevante Features. Jedes Feature nimmt an der Abstandsberechnung teil. Rauschende oder irrelevante Features verwässern das Signal. Entferne oder reduziere sie vor dem Training.
• Speicherbeschränkte Umgebungen. KNN speichert den gesamten Trainingsdatensatz; ein Datensatz mit Millionen von Zeilen belegt erheblichen RAM.

Zusammenfassung

Verwandte Kapitel:

• Feature-Skalierung — warum und wie man vor KNN skaliert
• Train/Test-Aufteilung — Daten korrekt aufteilen
• Kreuzvalidierung — K mit k-facher Kreuzvalidierung wählen
• Konfusionsmatrix — Klassifikationsergebnisse interpretieren
• Grid Search — systematische Hyperparameter-Optimierung