K-Nearest Neighbors

Der k-nächste Nachbarn (KNN) Algorithmus ist ein nichtparametrischer, überwachter Lernalgorithmus, der für Klassifizierungs- und Regressionsaufgaben im maschinellen Lernen verwendet wird. Er basiert auf dem Konzept der Nähe und geht davon aus, dass ähnliche Datenpunkte nah beieinander liegen. KNN ist ein sogenannter „Lazy Learning“-Algorithmus, was bedeutet, dass er keine Trainingsphase benötigt, sondern die gesamte Trainingsmenge speichert und diese zur Vorhersage der Klasse oder des Wertes neuer Datenpunkte nutzt. Der Algorithmus sagt das Ergebnis für einen Testdatenpunkt voraus, indem er die ‘k’ Trainingsdatenpunkte identifiziert, die dem Testpunkt am nächsten liegen, und basierend auf diesen Nachbarn das Ergebnis ableitet. Diese Methode ist sehr intuitiv und ahmt menschliche Wahrnehmungsstrategien nach, die sich darauf stützen, neue Daten mit bekannten Beispielen zu vergleichen.

Wie KNN funktioniert

KNN arbeitet, indem er die ‘k’ nächsten Datenpunkte zu einem gegebenen Abfragepunkt identifiziert und diese Nachbarn für eine Vorhersage nutzt.

• Bei Klassifikationsaufgaben ordnet der Algorithmus den Abfragepunkt derjenigen Klasse zu, die unter seinen ‘k’ nächsten Nachbarn am häufigsten vorkommt, was als Mehrheitsentscheid bezeichnet wird. Die Mehrheitsentscheidung in KNN kann als „Pluralitätsentscheidung“ verstanden werden, wenn es mehrere Klassen gibt: Der Abfragepunkt wird der Klasse mit der höchsten Anzahl unter den nächsten Nachbarn zugewiesen, auch wenn sie keine absolute Mehrheit bildet.
• Bei Regressionsaufgaben sagt er den Wert voraus, indem er die Werte der ‘k’ nächsten Nachbarn mittelt.

Die Prinzipien der Nähe und Ähnlichkeit, die auch der menschlichen Wahrnehmung zugrunde liegen, sind zentral für die Funktionsweise von KNN, da davon ausgegangen wird, dass nahe beieinanderliegende Datenpunkte ähnliche Eigenschaften und damit ähnliche Ergebnisse aufweisen.

Distanzmetriken

Um die nächsten Nachbarn zu bestimmen, verwendet KNN verschiedene Distanzmetriken, die entscheidend für seine Leistung sind:

• Euklidische Distanz: Die Luftliniendistanz zwischen zwei Punkten im mehrdimensionalen Raum, wird vor allem bei kontinuierlichen Variablen eingesetzt. Sie ist die am häufigsten verwendete Distanzmetrik für KNN und besonders nützlich bei dichten und kontinuierlichen Daten.
• Manhattan-Distanz: Auch als Taxifahrer-Distanz bekannt, berechnet sie den Abstand, indem die absoluten Differenzen der Koordinaten zweier Punkte aufsummiert werden. Sie ist nützlich für Szenarien mit rasterartiger Bewegung, bei denen Bewegungen auf orthogonale Richtungen beschränkt sind.
• Minkowski-Distanz: Eine Verallgemeinerung der euklidischen und Manhattan-Distanz, parametrisiert durch ‘p’. Ist p=1, entspricht sie der Manhattan-Distanz, bei p=2 der euklidischen Distanz. Diese Distanzmetrik bietet Flexibilität je nach gewähltendem ‘p’-Wert.
• Hamming-Distanz: Wird für kategoriale Daten verwendet und zählt die Anzahl der unterschiedlichen Bits zwischen zwei Binärvektoren. Besonders nützlich bei binären Klassifikationsproblemen, in denen Merkmale binäre Werte haben.

Die Wahl des richtigen ‘k’-Werts

Der Parameter ‘k’ bei KNN steht für die Anzahl der zu berücksichtigenden Nachbarn. Die richtige Wahl von ‘k’ ist entscheidend:

• Ein kleines ‘k’ kann zu Overfitting führen, da das Modell zu empfindlich auf das Rauschen in den Trainingsdaten reagiert und zufällige Muster erlernt, die sich nicht verallgemeinern lassen.
• Ein großes ‘k’ kann zu Underfitting führen, da das Modell zu allgemein wird und wichtige Muster ignoriert, was die Vorhersageleistung mindert.
• Typischerweise wird ‘k’ durch Kreuzvalidierung bestimmt und sollte eine ungerade Zahl sein, um Gleichstände bei Klassifikationsentscheidungen zu vermeiden. Die Wahl von ‘k’ hat einen erheblichen Einfluss auf die Genauigkeit des Modells und wird meist empirisch festgelegt.

Vorteile und Nachteile

Vorteile

• Einfach und intuitiv: Leicht zu verstehen und zu implementieren, daher besonders für Einsteiger geeignet. Die Einfachheit von KNN liegt im direkten Vergleich von Testinstanzen mit gespeicherten Beispielen.
• Keine Trainingsphase: KNN braucht keine explizite Trainingsphase, da Vorhersagen mit dem gespeicherten Datensatz getroffen werden. Das Modell kann somit einfach durch Hinzufügen neuer Datenpunkte aktualisiert werden.
• Vielseitig: Für Klassifikations- und Regressionsaufgaben geeignet und in vielen Bereichen einsetzbar. Auch für Multi-Label-Klassifikationen ist KNN nützlich.

Nachteile

• Rechnerisch aufwendig: Da für jeden neuen Datenpunkt der gesamte Datensatz verglichen wird, kann KNN bei großen Datenmengen langsam und ressourcenintensiv sein. Die Zeitkomplexität beträgt O(n), wobei n die Anzahl der Trainingsbeispiele ist.
• Empfindlich gegenüber Ausreißern: Das Vorhandensein von Ausreißern kann die Vorhersagen stark beeinflussen, da diese Ausreißer besonders bei kleinem ‘k’ die Ergebnisse verzerren können.
• Fluch der Dimensionalität: In hochdimensionalen Räumen kann die Leistung des Algorithmus abnehmen, da die Abstände zwischen den Datenpunkten weniger aussagekräftig werden. Mit steigender Dimensionalität nimmt das Volumen des Raumes zu, wodurch die Daten immer spärlicher werden. Diese Sparsität erschwert es KNN, effektiv nächste Nachbarn zu finden.

Anwendungsfälle

KNN wird aufgrund seiner Einfachheit und Effektivität in vielen Bereichen eingesetzt:

• Empfehlungssysteme: Zur Empfehlung von Produkten oder Inhalten an Nutzer basierend auf den Vorlieben ähnlicher Nutzer. KNN kann ähnliche Nutzer oder Objekte durch Bewertung der Merkmalähnlichkeit identifizieren.
• Mustererkennung: Eingesetzt bei Handschriftenerkennung und anderen Aufgaben der Mustererkennung, bei denen Bilder anhand der Ähnlichkeit von Pixelwerten klassifiziert werden.
• Datenimputation: Hilfreich beim Auffüllen fehlender Werte in Datensätzen, indem diese auf Basis ähnlicher Datenpunkte geschätzt werden, um die Integrität des Datensatzes zu erhalten.
• Finanzen und Gesundheitswesen: Eingesetzt bei Börsenprognosen, Risikobewertungen und medizinischer Diagnostik durch Analyse von Ähnlichkeiten in historischen Daten. Im Gesundheitsbereich kann KNN Diagnosen vorhersagen, indem Symptome mit bekannten Fällen verglichen werden.

Implementierung in Python

KNN kann mit Bibliotheken wie scikit-learn in Python implementiert werden. Hier ein einfaches Beispiel für die Verwendung von KNN zur Klassifikation:

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

# Datensatz laden
iris = load_iris()
X, y = iris.data, iris.target

# Daten in Trainings- und Testmenge aufteilen
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# KNN-Klassifikator mit k=3 initialisieren
knn = KNeighborsClassifier(n_neighbors=3)

# Modell fitten
knn.fit(X_train, y_train)

# Vorhersagen treffen
y_pred = knn.predict(X_test)

# Genauigkeit bewerten
accuracy = accuracy_score(y_test, y_pred)
print(f"Accuracy: {accuracy:.2f}")

K-Nearest Neighbors (KNN) in der wissenschaftlichen Forschung

K-Nearest Neighbors (KNN) ist ein grundlegender Algorithmus, der in verschiedenen Bereichen wie Multimedia-Informationsabruf, Data Mining und maschinellem Lernen, insbesondere bei großen Datensätzen, eingesetzt wird.

Bedeutende Forschungsarbeiten:

• „Approximate k-NN Graph Construction: a Generic Online Approach“ von Wan-Lei Zhao et al.:
  Stellt eine effektive Methode für die ungefähre k-nächster Nachbarn-Suche und den Graphenaufbau vor. Die Arbeit zeigt eine dynamische und praktikable Lösung für verschiedene Datenmengen und Dimensionen und unterstützt Online-Updates, was bei vielen bestehenden Methoden nicht möglich ist. Mehr erfahren.

• „Parallel Nearest Neighbors in Low Dimensions with Batch Updates“ von Magdalen Dobson und Guy Blelloch:
  Führt parallele Algorithmen ein, die kd-Baum und Morton-Ordering zu einer sogenannten zd-tree-Struktur kombinieren, optimiert für niedrigdimensionale Daten. Die Autoren zeigen, dass ihr Ansatz schneller ist als bestehende Algorithmen und erhebliche Geschwindigkeitsvorteile durch parallele Verarbeitung erzielt. Der zd-tree unterstützt erstmals parallele Batch-dynamische Updates bei k-nächster Nachbarn-Datenstrukturen. Mehr erfahren.

• „Twin Neural Network Improved k-Nearest Neighbor Regression“ von Sebastian J. Wetzel:
  Untersucht einen neuartigen Ansatz zur k-nächster Nachbarn Regression mittels Twin Neural Networks. Diese Methode konzentriert sich auf die Vorhersage von Unterschieden zwischen Regressionszielen und führt bei kleinen bis mittleren Datensätzen zu einer verbesserten Leistung im Vergleich zu traditionellen neuronalen Netzen und k-nächster Nachbarn Regressionstechniken. Mehr erfahren.