Der K-Nächste-Nachbarn-Algorithmus (KNN) ist ein überwachter Lernalgorithmus, der Entscheidungen über die Klassifizierung oder Vorhersage eines Datenpunkts trifft, indem er die nächstgelegenen „k“ Nachbarn im Datensatz analysiert.

Video

Quiz

KNN — Der K-Nearest-Neighbor-Algorithmus

Der KNN-Algorithmus gehört zu den einfachsten und beliebtesten Methoden im maschinellen Lernen. In diesem Beitrag erfährst du, wie er funktioniert und wo er eingesetzt wird.

Inhaltsübersicht

Was ist der KNN-Algorithmus?

Der K-Nearest-Neighbor-Algorithmus (KNN) ist ein Algorithmus aus dem Bereich des maschinellen Lernens. Er funktioniert so:

Für einen neuen, unbekannten Datenpunkt findet er die nächsten Nachbarn aus einem vorhandenen Datensatz. Das k steht dabei für die Anzahl der Nachbarn, die er bestimmt. Basierend auf deren Eigenschaften trifft er dann eine Vorhersage über den unbekannten Datenpunkt.

Meistens wird der Algorithmus für Klassifizierungsaufgaben verwendet. Das bedeutet, dass er neue Datenpunkte einer Kategorie, wie zum Beispiel „Birne“ oder „Apfel“ zuordnet. Er kann aber auch für Regressionen eingesetzt werden. Dort sagt er einen numerischen Wert vorher, zum Beispiel das Gewicht, oder den Preis eines Objektes.

Lazy Learning

Der KNN-Algorithmus ist ein speicherbasiertes Verfahren und gehört damit zur Familie der „Lazy Learning“-Modelle. Das bedeutet, dass er den gesamten Trainingsdatensatz speichert, anstatt eine ganze Trainingsphase zu durchlaufen. Bei jeder Vorhersage berechnet er die Distanz zu allen gespeicherten Punkten, um die k nächsten Nachbarn zu identifizieren.

Wie funktioniert KNN?

Der KNN-Algorithmus funktioniert sowohl bei Klassifikations- als auch bei Regressionsaufgaben. Das heißt, KNN kann sowohl mit kategorialen als auch mit numerischen Daten arbeiten.

Übrigens: KNN zählt zu den überwachten Lernalgorithmen, da er auf einem beschrifteten Datensatz basiert. Das heißt, ein Mensch hat beim Trainingsdatensatz dem Algorithmus die richtigen Ausgaben vorgegeben, an denen er lernen soll, um später neue Datenpunkte selbst zu kategorisieren bzw. vorherzusagen.

Klassifikationsaufgaben

Bei der Klassifikation sucht der Algorithmus die k nächsten Nachbarn eines neuen Datenpunkts und entscheidet dann, welche Klasse dieser Punkt bekommen soll. Das geschieht nach dem Mehrheitswahlprinzip: Die Klasse, die unter den Nachbarn am häufigsten vorkommt, wird dem neuen Punkt zugewiesen.

knn, knn algorithm, k nearest neighbor, k-nearest neighbors — KNN — Klassifizierung

Wenn zum Beispiel von fünf Nachbarn drei zur Klasse A, einer zur Klasse B und einer zu Klasse C gehören, wird der neue Punkt der Klasse A zugeordnet.

Regressionsaufgaben

Bei der Regression hingegen identifiziert KNN die k nächsten Nachbarn eines neuen Datenpunktes und berechnet dann den Durchschnitt ihrer Werte. Dieser Durchschnitt dient als Vorhersage für den neuen Punkt und ist besonders nützlich zur Schätzung kontinuierlicher Werte wie Preise oder Temperaturen.

Aber egal ob bei Klassifizierung oder Regression, ein wesentlicher Punkt bei der Anwendung des KNN-Algorithmus ist die Festlegung von zwei entscheidenden Parametern: der Distanzmetrik, um die Nachbarn zu bestimmen, und der Anzahl der Nachbarn „k“. Diese Faktoren beeinflussen maßgeblich die Genauigkeit und Relevanz der Vorhersagen des Algorithmus.

Distanzmetriken

Um zu bestimmen, welches die nächsten Nachbarn sind, muss die Distanz zwischen dem neuen Datenpunkt und allen anderen Punkten im Datensatz berechnet werden. Hierfür stehen verschiedene Distanzmetriken zur Verfügung:

Die euklidische Distanz ist die am häufigsten verwendete Distanzmetrik im KNN-Algorithmus. Sie misst den direkten Abstand zwischen zwei Punkten im n-dimensionalen Raum. Diese Metrik ist besonders intuitiv, da sie dem gewohnten Konzept der „Luftlinie“ entspricht.

$d = \sqrt{\sum\limits_{i=1}^{n} (x_i - y_i)^2}$
Die Manhatten-Distanz misst den Abstand zwischen zwei Punkten, indem sie die absolute Differenz der Koordinaten summiert. Sie wird auch als „Taximetrik“ bezeichnet, da sie veranschaulicht, wie ein Taxi die Straßen einer Stadt entlangfährt, anstatt eine direkte Linie zwischen zwei Punkten zu wählen.

$d = \sum\limits_{i=1}^{n} |x_i - y_i|$
Die Hamming-Distanz wird häufig bei kategorischen Daten verwendet, um den Unterschied zwischen zwei Zeichenfolgen oder binären Vektoren zu messen. Sie zählt die Anzahl der Positionen, an denen die entsprechenden Elemente unterschiedlich sind. Diese Metrik ist besonders nützlich in Anwendungen wie der Fehlererkennung und -korrektur.

$d = \sum\limits_{i=1}^{n} |x_i - y_i|$

Die Minkowski-Distanz

Die Minkowski-Distanz ist eine verallgemeinerte Form der euklidischen und der Manhattan-Distanz. Für p = 1 ergibt sich die Manhattan-Distanz, während p = 2 der euklidischen Distanz entspricht.

$d = \left( \sum\limits_{i=1}^{n} |x_i - y_i|^p \right)^{1/p}$

Die richtige Wahl von k

Der k-Wert im KNN-Algorithmus bestimmt, wie viele Nachbarn zur Klassifikation oder zur Vorhersage eines neuen Datenpunkts herangezogen werden. Ist beispielsweise k = 1, dann erhält der Datenpunkt die Klasse bzw. den Wert seines nächsten Nachbarn.

Die richtige Balance zwischen einem zu kleinen und einem zu großen Wert von „k“ ist entscheidend, um ein robustes und effektives Modell zu erstellen.

Ein zu kleiner Wert für k (z. B. k = 1) macht das Modell anfällig für Rauschen und Ausreißer, da es nur den nächsten Nachbarn betrachtet. Dies kann zu „Overfitting“ führen, bei dem das Modell zu stark an die Trainingsdaten angepasst wird und bei neuen Daten schlechter abschneidet.

Im Gegensatz dazu kann ein zu großer Wert für k dazu führen, dass das Modell wichtige Muster in den Daten ignoriert („Underfitting“).

In Klassifizierungsproblemen kann es manchmal zu einem „Unentschieden“ kommen. Zum Beispiel wenn bei k = 4 zwei Nachbarn zu Klasse A und zwei zu Klasse B gehören. Um diese Situation zu vermeiden, sollte ein ungerader k-Wert gewählt werden. Das verringert die Wahrscheinlichkeit, dass mehrere Klassen gleich viele Stimmen erhalten.

Außerdem kann es sinnvoll sein, die Nachbarn nach ihrer Distanz zu gewichten, um den Einfluss näherer Nachbarn auf die Entscheidungsfindung zu verstärken.

Die spezifische Wahl von k

Der Wert von k sollte immer an die spezifischen Eigenschaften der Eingabedaten angepasst werden. Es gibt nämlich keinen allgemein gültigen k-Wert, der für alle Datensätze optimal ist.

Eine gängige Methode zur Festlegung eines geeigneten k-Werts ist die Anwendung von Kreuzvalidierung. Dabei wird der Datensatz in Trainings- und Testdaten unterteilt, um verschiedene k-Werte zu testen und die Modellleistung zu bewerten. So lässt sich der optimale Wert ermitteln.

Anwendungen von KNN

Der KNN-Algorithmus wird aufgrund seiner Einfachheit in vielen Bereichen eingesetzt, insbesondere in der Klassifikation. Hier sind einige der häufigsten Anwendungsgebiete:

Analyse fehlender Werte
Im Bereich der Datenvorverarbeitung wird KNN verwendet, um fehlende Werte in Datensätzen zu identifizieren und zu ersetzen. Der Algorithmus sucht nach ähnlichen Punkten und nutzt deren Werte, um die Lücken zu füllen. Diese Methode verbessert die Datenqualität und führt zu genaueren Analysen.
Empfehlungssysteme
Ein weiterer Anwendungsbereich sind Empfehlungssysteme, in denen KNN Produkte oder Inhalte basierend auf den Vorlieben ähnlicher Nutzer empfiehlt. Wenn ein Nutzer zum Beispiel bestimmte Filme mag, schlägt der Algorithmus ähnliche Filme vor, die andere Benutzer mit ähnlichen Interessen positiv bewertet haben.
Medizinische Diagnosen
In der medizinischen Diagnostik wird KNN eingesetzt, um Patienten basierend auf ihren Symptomen zu kategorisieren oder Diagnosen zu stellen. Der Algorithmus analysiert Patientendaten und vergleicht sie mit ähnlichen Fällen, um Empfehlungen zu geben oder potenzielle Diagnosen zu identifizieren.
Betrugserkennung
Der Algorithmus eignet sich auch gut zur Erkennung von Ausreißern, wie zum Beispiel bei der Identifizierung von Betrug im Finanzwesen. KNN kann neue Transaktionen analysieren und sie mit historischen Daten vergleichen, um ungewöhnliche Muster zu erkennen, die auf betrügerische Aktivitäten hindeuten könnten.
Handschrifterkennung
KNN wird ebenfalls in der Handschrifterkennung eingesetzt, um handgeschriebene Zeichen und Ziffern zu klassifizieren. Der Algorithmus vergleicht neue Eingaben mit einem Datensatz bekannter Beispiele, was die Erkennung von handschriftlichen Ziffern in Anwendungen wie der automatischen Postverarbeitung erleichtert.

Vor- und Nachteile von KNN

Der KNN-Algorithmus hat sich als vielseitiges Werkzeug im Bereich des maschinellen Lernens etabliert, bringt jedoch sowohl Vor- als auch Nachteile mit sich, die bei der Anwendung berücksichtigt werden sollten.

Vorteile

Einfachheit und Benutzerfreundlichkeit: KNN ist einfach zu implementieren. Seine intuitive Funktionsweise macht ihn besonders für Einsteiger im maschinellen Lernen attraktiv.
Multiklassifikation: KNN ist sehr vielseitig einsetzbar, da es sich nicht nur für Klassifikationsaufgaben mit zwei Klassen eignet, sondern kann auch problemlos mit mehreren Klassen umgehen.
Anpassungsfähigkeit: Der Algorithmus kann leicht auf neue Datenpunkte angewendet werden, ohne dass ein umfangreiches Training erforderlich ist. Neue Daten können einfach dem bestehenden Datensatz hinzugefügt werden.

Nachteile

Hoher Rechenaufwand: Da KNN die Distanz zu allen Punkten im Datensatz berechnet, kann der Algorithmus bei großen Datensätzen sehr rechenintensiv und langsam sein. Dies kann die Effizienz der Vorhersagen erheblich beeinträchtigen.
Skalierungsprobleme: Wenn Merkmale im KNN-Algorithmus unterschiedliche Wertebereiche haben, kann die Distanzberechnung verzerrt werden. Um diese Probleme zu vermeiden, sollten Daten normalisiert oder standardisiert werden, damit alle Merkmale gleich gewichtet werden.
„Fluch der Dimensionalität“: Der Fluch der Dimensionalität ist ein Problem, das auftritt, wenn die Anzahl der Merkmale in einem Datensatz zu groß wird. Es erschwert die Anwendung von Algorithmen wie KNN, da die Abstände zwischen den Datenpunkten weniger aussagekräftig werden. Dadurch werden mehr Daten benötigt, um genaue Vorhersagen zu treffen.
Überanpassung: KNN ist anfällig für Überanpassung, insbesondere bei kleinen k-Werten. Das Modell kann sich zu stark an die Trainingsdaten anpassen und auf Rauschen oder Ausreißer reagieren, was zu einer verminderten Vorhersagegenauigkeit bei neuen, unbekannten Daten führt.

KNN — häufigste Fragen

Was ist KNN?

Der K-Nächste-Nachbarn-Algorithmus (KNN) ist ein überwachter Lernalgorithmus, der Entscheidungen über die Klassifizierung oder Vorhersage eines Datenpunkts trifft, indem er die nächstgelegenen „k“ Nachbarn im Datensatz analysiert.
Was ist der KNN-Algorithmus?

Der K-Nearest-Neighbor-Algorithmus (KNN) ist ein Verfahren des maschinellen Lernens, das bei einem neuen, unbekannten Datenpunkt die „k“ nächsten Nachbarn aus einem bestehenden Datensatz identifiziert und basierend auf deren Eigenschaften Vorhersagen trifft.

Decision Tree

Ein Decision Tree (Entscheidungsbaum) ist ein weiterer Algorithmus, der im maschinellen Lernen eingesetzt wird. Wie ein Entscheidungsbaum aufgebaut ist und wozu er verwendet wird, zeigen wir dir hier!