Der KNN Algorithmus: Funktionsweise und praktische Anwendung im Machine Learning

Der K-Nearest Neighbors (KNN) Algorithmus ist ein fundamentaler Baustein im Bereich des maschinellen Lernens und gehört zu den einfachsten, aber dennoch leistungsstarken überwachten Lernverfahren. Er wird sowohl für Klassifikations- als auch für Regressionsprobleme eingesetzt und zeichnet sich durch seine intuitive Natur und relative Einfachheit in der Implementierung aus. Entwickler, Datenwissenschaftler und Technologiebegeisterte finden im KNN-Algorithmus einen hervorragenden Einstieg in die Welt der prädiktiven Modellierung, insbesondere wenn es darum geht, Muster in Daten zu erkennen und Vorhersagen auf Basis der Ähnlichkeit von Datenpunkten zu treffen.

In diesem umfassenden Blogbeitrag tauchen wir tief in die Definition, die Kernkonzepte und die Mechanismen des KNN-Algorithmus ein. Wir werden detailliert erläutern, wie er funktioniert, verschiedene Distanzmaße vorstellen, die für die Berechnung von Ähnlichkeiten entscheidend sind, und aufzeigen, wie der optimale Parameter ‚K‘ gewählt wird, um Überanpassung (Overfitting) zu vermeiden. Zudem bieten wir praktische, gut kommentierte Python-Codebeispiele unter Verwendung der Scikit-Learn-Bibliothek, um die Anwendung des KNN in realen Szenarien wie der Pflanzenklassifikation am bekannten Iris-Datensatz zu demonstrieren. Dieser Artikel richtet sich an alle, die ihr Verständnis dieses vielseitigen Algorithmus vertiefen und seine Anwendung im Kontext moderner Data-Science-Herausforderungen meistern möchten.

Grundlagen des K-Nearest Neighbors Algorithmus

Der K-Nearest Neighbors (KNN) Algorithmus ist ein nicht-parametrisches, faules Lernverfahren, was bedeutet, dass er während der Trainingsphase keine explizite Modellfunktion lernt, sondern die Trainingsdaten lediglich speichert. Die eigentliche Berechnung oder das „Lernen“ findet erst statt, wenn eine Vorhersage für einen neuen Datenpunkt angefordert wird. Dies unterscheidet ihn von „eifrigen“ Lernverfahren, die ein Modell vorab aufbauen. Bevor wir uns mit den spezifischen Schritten des KNN befassen, ist es wichtig, die Konzepte des überwachten Lernens zu rekapitulieren.

Beim überwachten Lernen wird ein Algorithmus mit einem Datensatz trainiert, der sowohl Eingabemerkmale als auch die entsprechenden Zielwerte (Labels) enthält. Das Ziel ist es, ein Modell zu erstellen, das die Beziehung zwischen den Eingabemerkmalen und den Zielwerten lernt. Sobald das Modell trainiert ist, kann es neue, ungesehene Datenpunkte nehmen und deren entsprechende Zielwerte vorhersagen. Der KNN-Algorithmus nutzt diese Idee, indem er die Klasse oder den Wert eines neuen Datenpunkts basierend auf der Mehrheit der Klassen oder dem Durchschnitt der Werte seiner nächsten Nachbarn im Trainingsdatensatz bestimmt.

Wie der KNN Algorithmus funktioniert: Ein Schritt-für-Schritt-Leitfaden

Die Intuition hinter dem KNN-Algorithmus ist denkbar einfach: „Punkte, die einander ähneln, sind wahrscheinlich derselben Kategorie zuzuordnen.“ Um dies in der Praxis umzusetzen, durchläuft der Algorithmus die folgenden Schritte:

Schritt 1: Festlegung des Parameters K

Zunächst muss der Wert für K gewählt werden. K repräsentiert die Anzahl der nächsten Nachbarn, die bei der Vorhersage berücksichtigt werden sollen. Die Wahl von K ist entscheidend für die Leistung des Modells; ein zu kleines K kann das Modell anfällig für Rauschen machen, während ein zu großes K die Klassifizierungsgrenzen verwischen und zu einer Unteranpassung führen kann. Typischerweise wird K als ungerade Zahl gewählt, um Gleichstände bei der Klassifikation zu vermeiden.

Schritt 2: Berechnung der Distanz

Für einen neuen, unklassifizierten Datenpunkt berechnet der Algorithmus die Distanz zu jedem Datenpunkt im Trainingsdatensatz. Es gibt verschiedene Metriken zur Distanzberechnung, die gängigsten sind die euklidische Distanz und die Manhattan-Distanz. Die Wahl der Distanzmetrik hängt von der Art der Daten und des Problems ab.

Die euklidische Distanz ist die geradlinige Distanz zwischen zwei Punkten in einem euklidischen Raum und wird oft verwendet, wenn die Merkmale kontinuierlich sind und isotrope Eigenschaften aufweisen (d.h., die Relevanz der Merkmale ist in alle Richtungen gleich). Für zwei Punkte $p = (p_1, p_2, …, p_n)$ und $q = (q_1, q_2, …, q_n)$ in einem n-dimensionalen Raum wird sie berechnet als:

$d(p, q) = sqrt{(p_1-q_1)^2 + (p_2-q_2)^2 + … + (p_n-q_n)^2}$

Die Manhattan-Distanz (auch L1-Distanz oder City-Block-Distanz genannt) misst die Summe der absoluten Unterschiede zwischen den Koordinaten der Punkte. Sie ist nützlich, wenn die Bewegung auf einem Gitter eingeschränkt ist (wie in einem Stadtplan) oder wenn die Merkmale unterschiedliche Skalen oder Bedeutungen haben.

$d(p, q) = |p_1-q_1| + |p_2-q_2| + … + |p_n-q_n|$

Distanzmetrik	Formel	Anwendungsszenario
Euklidische Distanz	$sqrt{sum_{i=1}^{n}(p_i-q_i)^2}$	Kontinuierliche Daten, physikalische Entfernungen, isotrope Merkmale
Manhattan-Distanz	$sum_{i=1}^{n}|p_i-q_i|$	Hohe Dimensionalität, gemischte Datentypen, Feature-Auswahl
Minkowski-Distanz	$(sum_{i=1}^{n}|p_i-q_i|^r)^{1/r}$	Verallgemeinerung (r=1 Manhattan, r=2 Euklidisch)

Schritt 3: Auswahl der K nächsten Nachbarn

Nachdem alle Distanzen berechnet wurden, werden die K Datenpunkte aus dem Trainingsdatensatz ausgewählt, die die geringste Distanz zum neuen Datenpunkt aufweisen. Diese K Punkte sind die „nächsten Nachbarn“.

Schritt 4: Aggregation der Nachbarklassen/-werte

Für Klassifikationsprobleme werden die Klassen der K nächsten Nachbarn gezählt. Für Regressionsprobleme wird der Durchschnitt der Zielwerte der K nächsten Nachbarn berechnet.

Schritt 5: Zuweisung des neuen Datenpunkts

Im Falle der Klassifikation wird der neue Datenpunkt der Kategorie zugewiesen, die unter seinen K nächsten Nachbarn am häufigsten vorkommt (Mehrheitsentscheid). Bei der Regression wird der Durchschnitt der Zielwerte der K Nachbarn als Vorhersage für den neuen Punkt genommen.

Schritt 6: Modell ist einsatzbereit

Der neue Datenpunkt ist nun klassifiziert oder sein Wert vorhergesagt. Dieser Prozess wird für jeden neuen Datenpunkt wiederholt, für den eine Vorhersage benötigt wird. Es ist wichtig zu beachten, dass KNN keine explizite Trainingsphase im herkömmlichen Sinne hat; das „Modell“ sind die Trainingsdaten selbst.

Praktische Anwendung des KNN Algorithmus mit Python und Scikit-Learn

Um die Funktionsweise des K-Nearest Neighbors Algorithmus zu demonstrieren, verwenden wir Python zusammen mit der beliebten maschinellen Lernbibliothek Scikit-Learn. Der Iris-Datensatz, ein Klassiker im Machine Learning, eignet sich hervorragend für ein solches Beispiel, da er relativ klein und gut verständlich ist.

Iris-Datensatz Klassifikation mit KNeighborsClassifier

Der Iris-Datensatz enthält 150 Beobachtungen von Iris-Pflanzen, aufgeteilt in drei Spezies (Setosa, Versicolor, Virginica), mit jeweils vier Merkmalen: Kelchblattlänge, Kelchblattbreite, Blütenblattlänge und Blütenblattbreite. Unser Ziel ist es, die Spezies einer Iris-Pflanze anhand dieser vier Merkmale vorherzusagen.

Zunächst importieren wir die benötigten Bibliotheken, laden den Datensatz und teilen ihn in Trainings- und Testsets auf. Es ist auch wichtig, die Daten zu skalieren, da distanzbasierte Algorithmen empfindlich auf unterschiedliche Skalen der Merkmale reagieren können. Die Standardisierung (Z-Score-Normalisierung) ist hier eine gängige Praxis.

import numpy as np
import pandas as pd
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, confusion_matrix
import matplotlib.pyplot as plt
import seaborn as sns

# 1. Daten laden
iris = load_iris()
X = iris.data # Merkmale
y = iris.target # Zielvariable (Spezies)

# Merkmalsnamen und Zielnamen für bessere Lesbarkeit
feature_names = iris.feature_names
target_names = iris.target_names

print(f"Merkmale (X) Form: {X.shape}")
print(f"Zielvariable (y) Form: {y.shape}")
print(f"Merkmalsnamen: {feature_names}")
print(f"Zielnamen: {target_names}")

# 2. Daten aufteilen in Trainings- und Testset
# test_size=0.3 bedeutet 30% der Daten für den Test
# random_state für Reproduzierbarkeit
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42, stratify=y)

print(f"nX_train Form: {X_train.shape}")
print(f"X_test Form: {X_test.shape}")
print(f"y_train Form: {y_train.shape}")
print(f"y_test Form: {y_test.shape}")

# 3. Merkmale skalieren (Standardisierung)
# Dies ist entscheidend für distanzbasierte Algorithmen wie KNN
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)

print("nDaten erfolgreich skaliert.")

Nach der Vorbereitung der Daten können wir den `KNeighborsClassifier` initialisieren und trainieren. Hier wählen wir einen initialen Wert für K, zum Beispiel 5. Anschließend bewerten wir die Leistung des Modells.

# 4. KNN-Modell initialisieren und trainieren
# K = 5, distanzmetrik ist standardmäßig 'minkowski' (euklidisch, p=2)
knn = KNeighborsClassifier(n_neighbors=5)
knn.fit(X_train_scaled, y_train)

# 5. Vorhersagen treffen
y_pred = knn.predict(X_test_scaled)

# 6. Modellbewertung
accuracy = accuracy_score(y_test, y_pred)
print(f"nGenauigkeit des Modells (K=5): {accuracy:.4f}")

print("nKlassifikationsbericht:")
print(classification_report(y_test, y_pred, target_names=target_names))

print("nKonfusionsmatrix:")
cm = confusion_matrix(y_test, y_pred)
print(cm)

# Visualisierung der Konfusionsmatrix
plt.figure(figsize=(8, 6))
sns.heatmap(cm, annot=True, fmt="d", cmap="Blues",
            xticklabels=target_names, yticklabels=target_names)
plt.title('Konfusionsmatrix für KNN (K=5)')
plt.xlabel('Vorhergesagte Klasse')
plt.ylabel('Tatsächliche Klasse')
plt.show()

Die erste Ausführung mit K=5 zeigt oft bereits eine hohe Genauigkeit, da der Iris-Datensatz relativ gut separierbar ist. Der Klassifikationsbericht liefert präzisere Metriken wie Präzision, Recall und F1-Score für jede Klasse, während die Konfusionsmatrix eine detaillierte Aufschlüsselung der korrekten und inkorrekten Klassifikationen bietet.

Bestimmung des optimalen K-Werts zur Vermeidung von Overfitting

Die Wahl des optimalen K-Werts ist entscheidend für die Leistungsfähigkeit des KNN-Algorithmus. Ein zu kleiner K-Wert kann zu Überanpassung (Overfitting) führen, bei der das Modell zu stark an die Trainingsdaten angepasst ist und bei neuen, ungesehenen Daten schlecht generalisiert. Ein zu großer K-Wert hingegen kann zu Unteranpassung führen, da zu viele, möglicherweise irrelevante Nachbarn die Vorhersage dominieren.

Eine gängige Methode zur Bestimmung des optimalen K ist die Analyse der Fehlerrate über verschiedene K-Werte. Wir können dies tun, indem wir den Algorithmus mit verschiedenen K-Werten trainieren und die Fehlerrate auf einem Validierungs- oder Testset überwachen. Ziel ist es, den K-Wert zu finden, der die niedrigste Fehlerrate auf den Testdaten aufweist.

# Liste zur Speicherung der Fehlerraten
error_rate = []

# Wir testen K-Werte von 1 bis 30
for i in range(1, 31):
    knn = KNeighborsClassifier(n_neighbors=i)
    knn.fit(X_train_scaled, y_train)
    pred_i = knn.predict(X_test_scaled)
    # Fehlerrate = 1 - Genauigkeit
    error_rate.append(np.mean(pred_i != y_test))

# Visualisierung der Fehlerrate vs. K-Wert
plt.figure(figsize=(10, 6))
plt.plot(range(1, 31), error_rate, color='blue', linestyle='dashed', marker='o',
         markerfacecolor='red', markersize=10)
plt.title('Fehlerrate vs. K-Wert')
plt.xlabel('K-Wert')
plt.ylabel('Fehlerrate')
plt.xticks(np.arange(1, 31, 2))
plt.grid(True)
plt.show()

# Finden des K-Werts mit der minimalen Fehlerrate
optimal_k = error_rate.index(min(error_rate)) + 1
print(f"Der optimale K-Wert basierend auf der minimalen Fehlerrate ist: {optimal_k}")
print(f"Minimale Fehlerrate: {min(error_rate):.4f}")

# Re-Training des Modells mit dem optimalen K-Wert
knn_optimal = KNeighborsClassifier(n_neighbors=optimal_k)
knn_optimal.fit(X_train_scaled, y_train)
y_pred_optimal = knn_optimal.predict(X_test_scaled)
accuracy_optimal = accuracy_score(y_test, y_pred_optimal)
print(f"nGenauigkeit mit optimalem K ({optimal_k}): {accuracy_optimal:.4f}")
print("nKlassifikationsbericht mit optimalem K:")
print(classification_report(y_test, y_pred_optimal, target_names=target_names))

Anhand des Graphen der Fehlerrate gegen den K-Wert können wir einen Bereich identifizieren, in dem die Fehlerrate am niedrigsten ist. Ein K-Wert zwischen 5 und 18, wie im Referenzinhalt angedeutet, ist oft ein guter Bereich, in dem das Modell eine Balance zwischen Bias und Varianz findet. Ein zu hoher K-Wert führt zu einer Glättung der Entscheidungsgrenzen und kann dazu führen, dass wichtige lokale Muster übersehen werden. Ein zu niedriger K-Wert kann dazu führen, dass das Modell übermäßig auf einzelne Ausreißer reagiert.

Overfitting (Überanpassung) tritt auf, wenn ein Modell die Trainingsdaten zu gut lernt, einschließlich des Rauschens und der Details, die für die Generalisierung auf neue Daten nicht relevant sind. Das Ergebnis ist ein Modell, das auf den Trainingsdaten hervorragend, auf ungesehenen Testdaten jedoch schlecht abschneidet. Im Kontext von KNN tritt dies häufig bei sehr kleinen K-Werten auf, da das Modell dann sehr spezifisch auf die nächstgelegenen Trainingspunkte reagiert.

Anwendungsfelder des KNN Algorithmus in der Praxis

Trotz seiner Einfachheit findet der KNN-Algorithmus in verschiedenen Domänen breite Anwendung. Seine Stärke liegt in der Fähigkeit, komplexe, nicht-lineare Beziehungen zu modellieren, ohne eine explizite Annahme über die Datenverteilung machen zu müssen.

• Optische Zeichenerkennung (OCR): KNN wird eingesetzt, um handgeschriebene oder gedruckte Zeichen zu erkennen. Jedes Zeichen wird als Datenpunkt in einem hochdimensionalen Raum betrachtet, und ein unbekanntes Zeichen wird durch Vergleich mit den nächsten bekannten Zeichen klassifiziert.
• Kreditwürdigkeitsprüfung: Banken und Finanzinstitute nutzen KNN, um die Kreditwürdigkeit eines Antragstellers zu beurteilen. Die Merkmale des Antragstellers (Einkommen, Beschäftigungsstatus, bisherige Kredithistorie) werden mit denen bestehender Kunden verglichen, um ein Kreditrisiko vorherzusagen.
• Darlehensvergabe: Ähnlich der Kreditwürdigkeitsprüfung wird KNN verwendet, um zu entscheiden, ob einem Individuum ein Darlehen gewährt werden soll. Es wird geprüft, ob die Merkmale des Antragstellers denen von Personen ähneln, die in der Vergangenheit Kredite erfolgreich zurückgezahlt oder ausfallen lassen haben.
• Empfehlungssysteme: Im E-Commerce kann KNN verwendet werden, um Produkte basierend auf den Präferenzen ähnlicher Benutzer zu empfehlen. Wenn Benutzer A und Benutzer B ähnliche Käufe getätigt haben, könnten Produkte, die Benutzer A mag, Benutzer B empfohlen werden.
• Diagnose in der Medizin: KNN kann Ärzte bei der Diagnose von Krankheiten unterstützen, indem es die Symptome eines Patienten mit denen von Patienten mit bekannten Diagnosen vergleicht, um die wahrscheinlichste Krankheit zu identifizieren.

Abwägung: Vor- und Nachteile des KNN Algorithmus

Wie jeder Algorithmus hat auch KNN spezifische Stärken und Schwächen, die bei der Auswahl des passenden Modells für ein bestimmtes Problem berücksichtigt werden müssen.

Vorteile des KNN Algorithmus

• Der KNN-Algorithmus ist extrem einfach zu verstehen und zu implementieren, was ihn zu einem hervorragenden Ausgangspunkt für Anfänger im maschinellen Lernen macht.
• Er ist ein nicht-parametrischer Algorithmus, was bedeutet, dass er keine Annahmen über die zugrunde liegende Datenverteilung macht. Dies macht ihn flexibel und anwendbar auf eine Vielzahl von Datensätzen.
• KNN ist vielseitig und kann sowohl für Klassifikations- als auch für Regressionsaufgaben eingesetzt werden, indem einfach die Aggregationsmethode für die Nachbarn geändert wird (Mehrheitsentscheid für Klassifikation, Durchschnitt für Regression).
• Die Trainingsphase ist sehr schnell, da der Algorithmus lediglich die Trainingsdaten speichert und keine komplexen Berechnungen durchführt, um ein Modell zu erstellen.
• Er kann leicht an neue Daten angepasst werden; da keine explizite Modellierung stattfindet, können neue Trainingsdaten einfach hinzugefügt werden.

Nachteile des KNN Algorithmus

• Der größte Nachteil ist die Rechenintensität während der Vorhersagephase. Für jeden neuen Datenpunkt muss die Distanz zu allen Trainingsdatenpunkten berechnet werden. Dies führt zu einer erheblich langsameren Vorhersagezeit, insbesondere bei sehr großen Datensätzen und einer hohen Anzahl von Merkmalen (hohe Dimensionalität). Dies wird oft als „Curse of Dimensionality“ bezeichnet.
• KNN ist empfindlich gegenüber der Skalierung der Merkmale. Merkmale mit größeren Wertebereichen können die Distanzberechnung dominieren, weshalb eine Datenskalierung (z.B. Standardisierung oder Normalisierung) oft unerlässlich ist.
• Der Algorithmus ist empfindlich gegenüber Ausreißern und irrelevanten Merkmalen. Ausreißer können die Mehrheitsentscheidung (bei Klassifikation) oder den Durchschnitt (bei Regression) stark beeinflussen. Irrelevante Merkmale erhöhen die Dimensionalität und das Rauschen, ohne zur Vorhersagekraft beizutragen.
• Die Wahl des optimalen K-Werts kann schwierig sein und erfordert oft experimentelle Validierung, wie oben mit der Fehlerrate gezeigt.
• Bei ungleich verteilten Klassen kann KNN Schwierigkeiten haben. Minderheitsklassen können von Mehrheitsklassen „überstimmt“ werden, selbst wenn der neue Punkt tatsächlich zur Minderheitsklasse gehört.

Fazit: KNN als Tor zu intelligenten Systemen

Der K-Nearest Neighbors Algorithmus ist ein einfacher, aber wirkungsvoller Einstieg in das überwachte maschinelle Lernen. Seine intuitive Natur und die flexible Anwendung in Klassifikations- und Regressionsproblemen machen ihn zu einem wertvollen Werkzeug, insbesondere für erste Analysen und kleinere Datensätze. Obwohl er bei hoher Dimensionalität oder sehr großen Datenmengen an seine Grenzen stößt, bieten moderne Optimierungstechniken und geschickte Vorverarbeitung oft Lösungen für diese Herausforderungen. KNN bleibt ein wichtiger Algorithmus, der uns dabei hilft, die Grundlagen intuitiver, lernbasierter Systeme zu verstehen, die in zahlreichen Branchen eingesetzt werden können, um kleine, aber intelligente Entscheidungen selbstständig zu treffen.

Wir hoffen, dieser tiefgehende Einblick in den KNN-Algorithmus hat Ihr Verständnis erweitert und Sie inspiriert, selbst mit Machine-Learning-Modellen zu experimentieren. Ihr Feedback und Ihre Fragen sind uns wichtig – teilen Sie Ihre Gedanken gerne in den Kommentaren mit und entdecken Sie weitere spannende Themen rund um Datenwissenschaft und KI in unserem Blog!

Möchten Sie Ihr Wissen im Bereich Data Science testen? Es gibt viele Ressourcen und Online-Tests, mit denen Sie Ihre Fähigkeiten in Machine Learning und Datenanalyse überprüfen können, und sich in dem von Ihnen gewünschten Bereich testen können.

Falls Sie Ihre Kenntnisse in anderen Clusteralgorithmen erweitern möchten, finden Sie in unserem Blog auch Artikel zu Themen wie K-Means, hierarchische agglomerative Clusteranalyse (CAH) oder DBSCAN (Density-Based Spatial Clustering of Applications with Noise), die jeweils ihre eigenen Stärken für unterschiedliche Datenstrukturen und Problemstellungen bieten.