k-Nächste Nachbarn (kNN)

Von /

Der k-Nächste-Nachbarn-Algorithmus (kNN) ist ein Grundbaustein des überwachten maschinellen Lernens. Seine Stärke liegt in seiner Einfachheit und dennoch überraschenden Effizienz in vielen realen Anwendungen. Er zählt zu den sogenannten „Lazy Learning“-Algorithmen, da er keine aufwendige Trainingsphase durchläuft, sondern lediglich Daten speichert und während der Vorhersagephase tätig wird.

Algorithmus-Überblick und Einsatzmöglichkeiten

Der kNN-Algorithmus arbeitet nach einem sehr intuitiven Prinzip: Ähnlich wie wir Menschen neue Objekte klassifizieren, indem wir sie mit ähnlichen Objekten vergleichen, basiert auch kNN auf der Annahme, dass ähnliche Datenpunkte nahe beieinander liegen.

Funktionsweise:

  • Bei der Vorhersage eines neuen Datenpunkts sucht der Algorithmus die k nächstgelegenen Nachbarn in den Trainingsdaten.
  • Der neue Punkt wird dann in die Klasse eingeordnet, die unter diesen k Nachbarn am häufigsten vorkommt (bei Klassifikationsaufgaben) oder durch den Mittelwert der Nachbarn (bei Regressionsaufgaben).

Einsatzmöglichkeiten:

  • Klassifikation: kNN wird oft zur Erkennung von Handschriften, Gesichtern oder auch zur Analyse von Textdaten eingesetzt.
  • Regression: Auch für Vorhersagen von kontinuierlichen Werten (z.B. Immobilienpreise oder Temperaturprognosen) ist kNN geeignet.
  • Anomalieerkennung: Da kNN auch nicht normale Datenpunkte (Anomalien) erkennt, findet es Anwendung in der Erkennung von Betrug oder seltenen Krankheiten.
kNN Klassifikation im 2D-Raum
kNN Klassifikation im 2D-Raum

Mathematische Herleitung und Schritt-für-Schritt Vorgehen

kNN basiert auf einer Distanzmetrik, um die Ähnlichkeit zwischen Datenpunkten zu berechnen. Die euklidische Distanz ist die gebräuchlichste Methode. Sie misst den geradlinigen Abstand zwischen zwei Punkten in einem n-dimensionalen Raum:

 

d(x,y)=∑i=1n(xi−yi)2d(x, y) = \sqrt{\sum_{i=1}^{n} (x_i – y_i)^2}

Implementierung und Hyperparameter

Die Wahl von k, also der Anzahl der zu berücksichtigenden Nachbarn, ist der wichtigste Hyperparameter des kNN-Algorithmus. Dieser Parameter bestimmt, wie „lokal“ die Entscheidung ist. Eine kleine Wahl von k (z.B. k=1) kann zu einem Modell führen, das zu stark auf kleine Fluktuationen in den Daten reagiert und Overfitting verursacht. Eine zu große Wahl von k (z.B. k=20) führt dazu, dass das Modell zu viele Nachbarn einbezieht und möglicherweise wichtige lokale Muster übersehen werden (Underfitting). Die richtige Wahl von k ist sehr problembezogen.

Wahl von k:

  • Kleine Werte von k führen zu flexiblen, aber möglicherweise verrauschten Modellen.
  • Große Werte von k glätten die Entscheidung, können jedoch subtile Muster in den Daten ignorieren.

Optimierung:

In der Praxis wird der beste k-Wert meist durch Cross-Validation ermittelt, bei der verschiedene Werte von k getestet werden und derjenige gewählt wird, der die beste Leistung auf einem Validierungssatz erzielt.

kNN Einfluss von k auf die Modellleistung

Beispiel: kNN zur Klassifikation von handschriftlichen Ziffern (MNIST-Dataset)

Eine der klassischen Anwendungen von kNN ist die Klassifikation handgeschriebener Ziffern. Hier wird z.B. der MNIST-Datensatz, der 70.000 Bilder von Ziffern (0 bis 9) enthält, verwendet, um die Leistung von kNN zu demonstrieren.

Vorgehensweise:

  1. Datenvorbereitung: Jedes Bild im MNIST-Datensatz ist 28×28 Pixel groß, was als Vektor mit 784 Merkmalen (Pixelwerte) dargestellt wird.
  2. kNN-Anwendung: Um eine Ziffer zu klassifizieren, wird die euklidische Distanz zu allen anderen Bildern im Trainingssatz berechnet. Die k nächsten Nachbarn entscheiden dann über die Klassifizierung.
  3. Leistungsbewertung: Trotz der einfachen Struktur kann kNN auf dem MNIST-Datensatz eine respektable Genauigkeit erzielen, wobei allerdings Einschränkungen bezüglich Rechenaufwand und Speicherplatz bestehen.

Implementierung in Python

from sklearn.datasets import fetch_openml
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
import matplotlib.pyplot as plt

# MNIST-Datensatz laden
mnist = fetch_openml(‚mnist_784‘)
X, y = mnist[‚data‘], mnist[‚target‘].astype(int)

# Trainings- und Testdatensätze erstellen
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.1, random_state=42)

# kNN mit k=5
k = 5
knn = KNeighborsClassifier(n_neighbors=k)
knn.fit(X_train, y_train)

# Wähle ein Beispielbild aus dem Testset und finde die nächsten Nachbarn
index = 0 # Beispielindex
example_image = X_test[index].reshape(1, -1)
neighbors = knn.kneighbors(example_image, return_distance=False)

# Plot des Beispielbildes und der k nächsten Nachbarn
plt.figure(figsize=(10, 2))
plt.subplot(1, k+1, 1)
plt.imshow(example_image.reshape(28, 28), cmap=’gray‘)
plt.title(‚Zu klassif. Bild‘)

for i, neighbor_index in enumerate(neighbors[0]):
plt.subplot(1, k+1, i+2)
plt.imshow(X_train[neighbor_index].reshape(28, 28), cmap=’gray‘)
plt.title(f’Nachbar {i+1}‘)

plt.tight_layout()
plt.show()

kNN Klassifikation für handschriftliche Ziffern
Beispielbild aus dem MNIST-Datensatz mit den k nächsten Nachbarn, die zur Klassifizierung herangezogen werden

Zusammenfassung

Insgesamt bietet der k-Nächste-Nachbarn-Algorithmus (kNN) einen einfachen und zugleich effektiven Ansatz zur Klassifikation und Regression, der besonders in Anwendungen wie der Mustererkennung glänzt.

Referenzen

[R1]: Cover, T. M., & Hart, P. E. (1967): Nearest Neighbor Pattern Classification. IEEE Transactions on Information Theory, 13(1), 21-27.
[R2]: scikit-learn: k-NN Algorithm Documentation: Eine umfassende Beschreibung der Funktion und Implementierung des kNN-Algorithmus mit Hilfe der scikit-learn-Bibliothek. Link zur Dokumentation
[R3]: MNIST-Datensatz: Details und Download des MNIST-Datensatzes von handschriftlichen Ziffern. Link zur MNIST-Seite
[R4]: Wikipedia: k-nearest neighbors algorithm: Ein allgemeiner Überblick über den Algorithmus und seine Anwendungen. Link zum Wikipedia-Artikel

Nach oben scrollen