k-nearest neighbor - einfach erklärt!

K-nearest neighbors (kurz KNN) beschreibt einen Supervised Learning Algorithmus, der mithilfe von Abstandsberechnungen zwischen Punkten Daten klassifiziert. Dieser kann neuen Datenpunkten eine Klasse zuweisen, indem die k-nächsten Datenpunkte bestimmt werden und deren mehrheitliche Klasse auf den neuen Datenpunkt angewandt wird.

Wie funktioniert der Algorithmus?

Bei einer Klassifizierung wird allgemein versucht, die Punkte in einem Datensatz einer bestimmten Klasse zuzuordnen. Entsprechend soll ein Modell trainiert werden, das dann selbstständig für neue Punkte entscheiden kann, zu welcher Klasse sie am besten gehören sollen. Diese Modelle können entweder im Bereich des supervised oder des unsupervised Learnings liegen. Man unterscheidet damit, ob der Trainingsdatensatz schon eine spezielle Klassenzuordnung hat oder nicht.

Wenn wir beispielsweise die Kunden eines Unternehmens in drei verschiedene Gruppen aufteilen wollen, abhängig von ihrer Kaufkraft und der Anzahl der Einkäufe, unterscheiden wir einen supervised Learning Algorithmus, bei dem die Kunden im Trainingsdatensatz schon einer Kundengruppe zugeordnet wurden und das Modell anhand dieser gegebenen Klassifizierung auf neue Werte schließen soll. Beim unsupervised Learning hingegen sind die Kunden im Trainingsdatensatz noch nicht klassifiziert und das Modell muss anhand der erkannten Strukturen eigenständig Gruppierungen finden.

Angenommen wir nehmen folgende Kunden als Beispiel für die Erklärung des KNN-Algorithmus:

Kunde	Gesamtumsatz	Anzahl Käufe	Gruppierung
A	10.000 €	5	A
B	1.500 €	1	B
C	7.500 €	3	A

Beispielhafte Kunden für Klassifizierung

Für den k-Nearest Neighbor Algorithmus muss am Anfang erst ein konkreter Wert für k bestimmt werden. Dieser gibt an mit wie vielen Nachbarn wir im Endeffekt den neuen Datenpunkt vergleichen. Für unser Beispiel wählen wir k = 2. Angenommen wir erhalten nun einen neuen Kunden D, der bereits für 9.000 € bei uns eingekauft hat und insgesamt vier Einkäufe getätigt hat. Um dessen Klassifizierung zu bestimmen, suchen wir nun die zwei (k=2) nächsten Nachbarn zu diesem Datenpunkt und bestimmen deren Klasse.

K-Nearest Neighbors am Beispiel | Quelle: Autor

In unserem Fall sind das Kunde A und C, die beide der Klasse „A“ angehören. Also klassifizieren wir den neuen Kunden D auch als A-Kunde, da dessen nächste zwei Nachbarn in der Mehrheit der Klasse „A“ angehören.

Neben der Wahl des Wertes k bestimmt die Abstandsberechnung zwischen den Punkten über die Qualität des Modells. Dazu gibt es verschiedene Berechnungsweisen.

Wie können Abstände berechnet werden?

Je nach Anwendungsfall und Ausprägung der Daten können verschiedene Abstandsfunktionen genutzt werden zur Ermittlung der nächsten Nachbarn. Diese werden wir in diesem Kapitel genauer unter die Lupe nehmen.

Euklidische Distanz

DIe euklidische Distanz ist die am weit verbreitesten und lässt sich für reelle Vektoren mit vielen Dimensionen anwenden. Dabei werden die Abstände zwischen zwei Punkten in allen Dimensionen berechnet, quadriert und anschließend aufsummiert. Die Wurzel von dieser Summe ist dann das schlussendliche Ergebnis.

\(\) \[d(x,y) = \sqrt{\sum_{i = 1}^{n}(y_{i} – x_{i})^2}\]

Es wird dabei einfach eine direkte Linie zwischen den beiden Punkten x und y gelegt und deren Länge gemessen.

Manhattan Distanz

Die Manhattan Distanz hingegen berechnet die absolute Differenz der Punkte in allen Dimensionen und wird deshalb auch als „Taxi-Distanz“ bezeichnet. Das Vorgehen ähnelt nämlich der Fahrt eines Taxis durch die senkrechten Straßen in New York.

\(\) \[d(x,y) = \sum_{i = 1}^{n}|y_{i} – x_{i}|\]

Die Anwendung dieser Distanzfunktion macht vor allem dann Sinn, wenn man Objekte miteinander vergleichen will. Wenn beispielsweise zwei Häuser verglichen werden sollen, indem man sich die Anzahl der Zimmer und die Wohnfläche in Quadratmeter genauer anschaut, macht es keinen Sinn, die euklidische Distanz zu nehmen, sondern getrennt die Differenz in den Zimmern und dann die Differenz in der Wohnfläche zu betrachten. Ansonsten würden diese Dimensionen mit verschiedenen Einheiten durcheinander gebracht.

Andere Distanzen

Darüber hinaus gibt es noch weitere Distanzfunktionen, die sich einsetzen lassen, wenn man spezielle Datenformate nutzt. Die Hamming Distanz bietet sich beispielsweise bei boole’schen Werten, wie True und False an. Der Minkowski Abstand hingegen ist eine Mischung aus der euklischen und der Manhattan Distanz.

Welche Anwendungen nutzen den KNN?

Bei der Arbeit mit großen Datenmengen hilft das Klassifizieren dabei einen ersten Eindruck über die Feature-Ausprägungen und die Verteilung der Datenpunkte zu bekommen. Darüber hinaus gibt es auch viele andere Anwendungen für das Klassifizierungen:

Marktsegmentierung: Man versucht ähnliche Kundengruppen mit vergleichbarem Kaufverhalten oder sonstigen Eigenschaften zu finden.
Bildsegmentierung: Es wird versucht innerhalb eines Bildes die Stellen zu finden, die zu einem bestimmten Objekt gehören, bspw. alle Pixel, die Teil eines Autos bzw. der Straße sind.
Dokumentenclustering: Innerhalb eines Schriftstückes wird versucht Passagen mit ähnlichen Inhaltsschwerpunkten zu finden.
Recommendation Engine: Bei der Empfehlung von Produkten werden mithilfe des k-Nearest Neighbors ähnliche Kunden gesucht und deren gekaufte Produkte dem jeweils anderen Kunden vorgeschlagen, sofern er diese noch nicht gekauft hat.
Gesundheitswesen: Bei der Erprobung von Medikamenten und deren Wirksamkeit werden mithilfe von KNN besonders ähnliche Patienten gesucht und dann einer Patientin das Medikament verabreicht und der anderen Person nicht. Dadurch kann man vergleichen, welche Effekte vom Medikament ausgelöst wurden und welche möglicherweise sowieso eingetreten wären.

Was sind die Vor- und Nachteile des k-Nearest Neighbor Algorithmus?

Das k-Nearest Neighbor Modell erfreut sich großer Beliebtheit, weil es einfach zu verstehen und anzuwenden ist. Außerdem gibt es nur zwei Hyperparameter, die sich variieren lässt, nämlich zum einen die Anzahl der Nachbarn k und die Abstandsmetrik. Auf der anderen Seite ist dies natürlich auch ein Nachteil, da sich der Algorithmus nur wenig bis gar. nicht auf den konkreten Anwendungsfall anpassen lässt.

Aufgrund der einfachen Vorgehensweise benötigt der k-Nearest Neighbors Algorithmus jedoch bei großen Datensätzen auch viel Zeit und Arbeitsspeicher, was bei größeren Projekten schnell zu einem Kostenfaktor wird. Deshalb setzen größere Datenprojekte gerne zu aufwändigeren Modellen, wie beispielsweise dem k-Means Clustering.

Was ist der Unterschied zwischen k-nearest neighbors und k-Means?

Obwohl die Namen des k-Nearest Neighbors Algorithmus und des k-Means Clusterings im ersten Moment sehr ähnlich klingen, haben sie in Wirklichkeit relativ wenige Gemeinsamkeiten und werden für komplett unterschiedliche Anwendungen genutzt. Das k in k-Means Clustering beschreibt die Anzahl an Klassen, in die der Algorithmus einen Datensatz aufteilt. Bei den k-Nearest Neighbors hingegen steht das k für die Anzahl der Nachbarn, die genutzt werden, um die Klasse des neuen Datenpunktes zu bestimmen.

Außerdem ist das k-Nearest Neighbors Modell ein Supervised Learning Modell, da es die Zuteilung in Gruppen benötigt, um daraus neue ableiten zu können. Das k-Means Clustering hingegen zählt zu den Unsupervised Learning Algorithmen, da es im Stande ist aufgrund der Strukturen in den Daten verschiedene Gruppen eigenständig zu erkennen und die Daten diesen Klassen zuzuordnen.

Wie kann man k-nearest neighbor in Python implementieren?

Das k-nearest neigbor Matching ist eine nützliche Technik, um ähnliche Datenpunkte in einem Datensatz zu finden. In diesem Abschnitt werden wir den Prozess der Durchführung der K-NN-Übereinstimmung in Python anhand eines öffentlichen Datensatzes durchgehen und Codebeispiele bereitstellen.

Schritt 1: Importiere Bibliotheken

Beginne damit, die notwendigen Python-Bibliotheken zu importieren, einschließlich numpy für numerische Operationen und sklearn für die Implementierung von K-NN.

Schritt 2: Lade einen öffentlichen Datensatz

Für dieses Beispiel verwenden wir den Iris-Datensatz, einen bekannten Datensatz, der in der scikit-learn-Bibliothek verfügbar ist.

Schritt 3: Erstelle ein K-NN-Modell

Erstelle anschließend ein K-NN-Modell mit der NearestNeighbors-Klasse von scikit-learn. Du musst die Anzahl der Nachbarn (K) angeben, die berücksichtigt werden sollen.

Schritt 4: Führe die K-NN-Übereinstimmung durch

Nun, da Du ein K-NN-Modell auf Deinem Datensatz trainiert hast, kannst Du es verwenden, um die K nächsten Nachbarn für einen gegebenen Datenpunkt zu finden. In diesem Beispiel werden wir die nächsten Nachbarn für einen zufälligen Datenpunkt aus dem Datensatz finden.

Schritt 5: Ergebnisse überprüfen

Du kannst nun die Ergebnisse der K-NN-Übereinstimmung überprüfen. Abstände wird die Abstände vom Abfragepunkt zu seinen K nächsten Nachbarn enthalten, und Indizes wird die Indizes dieser Nachbarn im ursprünglichen Datensatz enthalten.

Schritt 6: Interpretation und weitere Analyse

Die Ergebnisse zeigen Dir die K nächsten Nachbarn des Abfragepunkts sowie ihre Abstände. Du kannst diese Ergebnisse für verschiedene Zwecke interpretieren, wie das Finden ähnlicher Datenpunkte, das Clustern oder die Ausreißererkennung.

Dieses Beispiel zeigt die grundlegenden Schritte zur Durchführung der K-NN-Übereinstimmung in Python anhand eines öffentlichen Datensatzes. Du kannst dieselben Prinzipien auf Deine eigenen Datensätze und Anwendungsfälle anwenden. Die K-NN-Übereinstimmung ist eine vielseitige Technik mit Anwendungen in verschiedenen Bereichen, einschließlich Empfehlungssystemen, Bildanalyse und Anomalieerkennung.

Wie kann das k-nearest neighbor Matching verbessert werden?

K-Nearest Neighbor (K-NN), obwohl ein einfacher Algorithmus, kann von sorgfältigen Überlegungen und Anpassungen profitieren, um seine Leistung zu optimieren. Hier sind wichtige Strategien zur Verbesserung von K-NN:

Optimale Auswahl des K-Werts: Die Wahl der richtigen Anzahl von Nachbarn (K) ist entscheidend. Ein kleines K kann zu rauschhaften Vorhersagen führen, während ein großes K eine Verzerrung einführen kann. Verwende Techniken wie die Kreuzvalidierung, um das richtige Gleichgewicht zu finden und das ideale K für Deinen Datensatz zu bestimmen.
Auswahl und Konstruktion von Merkmalen: Die Qualität Deiner Merkmale spielt eine entscheidende Rolle für den Erfolg von K-NN. Identifiziere die relevantesten Merkmale und erwäge die Merkmalskonstruktion, um neue Attribute zu erstellen, die die Fähigkeit des Algorithmus zur Erkennung von Mustern in Deinen Daten verbessern.
Abstandsmetriken: Die Wahl einer Abstandsmetrik wie Euklidischer oder Manhattener Abstand ist von entscheidender Bedeutung. Sie beeinflusst, wie K-NN Merkmalskalen und Datenverteilung wahrnimmt. Experimentiere mit verschiedenen Metriken oder verwende benutzerdefinierte Abstandsmetriken, die auf die Eigenschaften Deines Fachgebiets zugeschnitten sind.
Skalierung von Merkmalen: Merkmale weisen oft unterschiedliche Skalen auf, was die Leistung von K-NN beeinflussen kann. Durch die Standardisierung von Merkmalen (Z-Score-Normalisierung) oder das Skalieren auf einen konsistenten Bereich (Min-Max-Skalierung) wird verhindert, dass bestimmte Merkmale eine übermäßige Wirkung entfalten.
Datenverarbeitung: Der Umgang mit fehlenden Werten und Ausreißern ist unerlässlich. Verwende Techniken wie die Imputation für fehlende Daten und robuste Abstandsmetriken, um Ausreißer zu behandeln und die Robustheit von K-NN gegenüber rauschigen Daten zu stärken.
Gewichtetes K-NN: Das Standard-K-NN behandelt alle Nachbarn gleich. Das gewichtete K-NN weist basierend auf Abständen unterschiedliche Gewichte zu, sodass näher gelegene Nachbarn mehr Einfluss auf Vorhersagen haben können, was in Szenarien von Vorteil sein kann, in denen bestimmte Nachbarn eine größere Bedeutung haben.
Dimensionsreduktion: Hochdimensionale Daten können aufgrund des „Fluchs der Dimensionalität“ Herausforderungen darstellen. Techniken zur Dimensionsreduktion wie die Hauptkomponentenanalyse (PCA) oder die t-verteilte stochastische Nachbarschaftseinbettung (t-SNE) bewahren wesentliche Informationen bei gleichzeitiger Reduzierung der Dimensionalität und Verbesserung der Effizienz von K-NN.

Durch die sorgfältige Umsetzung dieser Strategien, die auf Deinen spezifischen Datensatz und Dein Problem zugeschnitten sind, kannst Du die Leistung und Zuverlässigkeit des k-nearest neighbor Algorithmus erheblich steigern. Denke daran, dass Experimentieren und iterative Verbesserung der Schlüssel sind, um optimale Ergebnisse in Deinen Projekten im Bereich des maschinellen Lernens zu erzielen.

Das solltest Du mitnehmen

k-Nearest Neighbors ist ein Supervised Learning Algorithmus, der mithilfe von Distanzberechnungen zwischen Datenpunkten diese in Gruppen aufteilt.
Ein neuer Punkt kann einer Gruppe zugeordnet werden, indem die k Nachbar Datenpunkte betrachtet werden und deren Mehrheitsklasse genutzt wird.
Ein solches Clusteringverfahren kann sinnvoll sein, um sich in großen Datensätzen zurechtzufinden, Produktempfehlungen für neue Kunden auszusprechen oder für die Einteilungen in Test- und Kontrollgruppen in medizinischen Versuchen.