K-Nearest Neighbors (KNN): Was es ist und wie es beim maschinellen Lernen verwendet wird

K-Nearest Neighbors (KNN) ist eine grundlegende Technik des maschinellen Lernens (ML). Dieser Leitfaden hilft Ihnen, KNN, seine Funktionsweise sowie seine Anwendungen, Vorteile und Herausforderungen zu verstehen.

Inhaltsverzeichnis

Was ist der k-nächste-Nachbarn-Algorithmus?

Wie funktioniert KNN?

Unterschied zwischen k-nächsten Nachbarn und anderen Algorithmen

Wie wird KNN beim maschinellen Lernen verwendet?

Anwendungen des KNN

Vorteile von KNN

Nachteile des KNN

Was ist der k-nächste-Nachbarn-Algorithmus?

Der k-Nearest Neighbors (KNN)-Algorithmus ist eine überwachte Lerntechnik, die sowohl für die Klassifizierung als auch für die Regression verwendet wird. KNN bestimmt die Bezeichnung (Klassifizierung) oder den vorhergesagten Wert (Regression) eines bestimmten Datenpunkts durch Auswertung benachbarter Datenpunkte im Datensatz.

Wie funktioniert KNN?

KNN basiert auf der Annahme, dass Datenpunkte, die in einem Datensatz räumlich nahe beieinander liegen, tendenziell ähnliche Werte haben oder zu ähnlichen Kategorien gehören. KNN nutzt diese einfache, aber wirkungsvolle Idee, um einen neuen Datenpunkt zu klassifizieren, indem eine voreingestellte Anzahl (der Hyperparameter k) benachbarter Datenpunkte innerhalb des gekennzeichneten Trainingsdatensatzes ermittelt wird. Dieser Wert k ist einer der KNN-Hyperparameter, bei denen es sich um voreingestellte Konfigurationsvariablen handelt, die ML-Praktiker verwenden, um zu steuern, wie der Algorithmus lernt.

Anschließend bestimmt der Algorithmus, welche der Nachbarwerte dem neuen Datenpunkt am nächsten liegen, und weist ihm dieselbe Bezeichnung oder Kategorie wie seine Nachbarn zu. Der gewählte Wert von k beeinflusst die Modellleistung. Kleinere Werte erhöhen die Rauschempfindlichkeit, während größere Werte die Robustheit erhöhen, jedoch dazu führen können, dass der KNN lokale Muster übersieht.

Die Nähe oder Distanz zwischen Datenpunkten wird mithilfe von Metriken berechnet, die ursprünglich zur Messung der Ähnlichkeit von Punkten in einem mathematischen Raum entwickelt wurden. Zu den gängigen Maßen gehören die euklidische Distanz, die Manhattan-Distanz und die Minkowski-Distanz. Die KNN-Leistung wird durch die gewählte Metrik beeinflusst, und verschiedene Metriken schneiden bei unterschiedlichen Datentypen und -größen besser ab.

Beispielsweise kann die Anzahl der Dimensionen in den Daten, bei denen es sich um einzelne Attribute handelt, die jeden Datenpunkt beschreiben, die Leistung der Metrik beeinflussen. Unabhängig von der gewählten Distanzmetrik besteht das Ziel darin, einen neuen Datenpunkt basierend auf seiner Distanz zu anderen Datenpunkten zu kategorisieren oder vorherzusagen.

• Der euklidische Abstandist der Abstand entlang einer geraden Linie zwischen zwei Punkten im Raum und die am häufigsten verwendete Metrik. Es eignet sich am besten für Daten mit einer geringeren Anzahl an Dimensionen und ohne signifikante Ausreißer.
• Die Manhattan-Distanzist die Summe der absoluten Differenzen zwischen den Koordinaten der gemessenen Datenpunkte. Diese Metrik ist nützlich, wenn die Daten hochdimensional sind oder wenn Datenpunkte eine gitterartige Struktur bilden.
• Die Minkowski-Distanzist eine einstellbare Metrik, die je nach Wert eines einstellbaren Parameters entweder wie die euklidische oder die Manhattan-Distanz wirken kann. Durch Anpassen dieses Parameters wird gesteuert, wie die Entfernung berechnet wird. Dies ist nützlich, um KNN an verschiedene Datentypen anzupassen.

Andere, weniger gebräuchliche Maßeinheiten sind Tschebyscheff-, Hamming- und Mahalanobis-Abstände. Diese Metriken sind spezialisierter und eignen sich für bestimmte Datentypen und -verteilungen. Beispielsweise misst der Mahalanobis-Abstand den Abstand eines Punktes von einer Punktverteilung unter Berücksichtigung der Beziehungen zwischen Variablen. Daher eignet sich die Mahalanobis-Distanz gut für die Arbeit mit Daten, bei denen Features unterschiedliche Maßstäbe verwenden.

KNN wird oft als „fauler“ Lernalgorithmus bezeichnet, da er im Gegensatz zu vielen anderen Algorithmen kein Training erfordert. Stattdessen speichert KNN Daten und verwendet sie nur dann, um Entscheidungen zu treffen, wenn neue Datenpunkte eine Regression oder Klassifizierung erfordern. Dies bedeutet jedoch, dass Vorhersagen häufig einen hohen Rechenaufwand erfordern, da für jede Vorhersage der gesamte Datensatz ausgewertet wird. ∫

Unterschied zwischen k-nächsten Nachbarn und anderen Algorithmen

KNN ist Teil einer größeren Familie überwachter ML-Techniken, die auf Klassifizierung und Regression ausgerichtet sind und Entscheidungsbäume/Random Forests, logistische Regression und Support Vector Machines (SVMs) umfassen. Allerdings unterscheidet sich KNN von diesen Techniken unter anderem durch seine Einfachheit und den direkten Ansatz beim Umgang mit Daten.

Entscheidungsbäume und Zufallswälder

Wie KNN werden Entscheidungsbäume und Zufallswälder zur Klassifizierung und Regression verwendet. Im Gegensatz zum distanzbasierten Ansatz von KNN verwenden diese Algorithmen jedoch explizite Regeln, die während des Trainings aus den Daten gelernt wurden. Entscheidungsbäume und Zufallswälder weisen tendenziell eine schnellere Vorhersagegeschwindigkeit auf, da sie über vorab trainierte Regeln verfügen. Dies bedeutet, dass sie für Echtzeit-Vorhersageaufgaben und die Verarbeitung großer Datensätze besser geeignet sind als KNN.

Logistische Regression

Die logistische Regression geht davon aus, dass Daten linear verteilt sind und klassifiziert Daten mithilfe einer geraden Linie oder Hyperebene (einer Grenze, die Datenpunkte in höherdimensionalen Räumen trennt), um Daten in Kategorien zu unterteilen. KNN hingegen geht nicht von einer bestimmten Datenverteilung aus. Daher kann sich KNN leichter an komplexe oder nichtlineare Daten anpassen, während die logistische Regression am besten mit linearen Daten verwendet wird.

Unterstützen Sie Vektormaschinen

Anstatt wie KNN auf Abstände zwischen Punkten zu achten, konzentrieren sich Support Vector Machines (SVM) darauf, eine klare Trennlinie zwischen Gruppen von Datenpunkten zu erstellen, oft mit dem Ziel, die Lücke zwischen ihnen so groß wie möglich zu machen. SVM eignet sich hervorragend für den Umgang mit komplexen Datensätzen mit vielen Funktionen oder wenn eine klare Trennung zwischen Datenpunktgruppen erforderlich ist. Im Vergleich dazu ist KNN einfacher zu verwenden und zu verstehen, funktioniert aber bei großen Datensätzen nicht so gut.

Wie wird KNN beim maschinellen Lernen verwendet?

Viele ML-Algorithmen können nur einen Aufgabentyp bearbeiten. KNN zeichnet sich durch seine Fähigkeit aus, nicht nur einen, sondern zwei häufige Anwendungsfälle zu bewältigen: Klassifizierung und Regression.

Einstufung

KNN klassifiziert Datenpunkte mithilfe einer Distanzmetrik, um die k-nächsten Nachbarn zu bestimmen und dem neuen Datenpunkt basierend auf den Beschriftungen der Nachbarn eine Beschriftung zuzuweisen. Zu den häufigsten Anwendungsfällen der KNN-Klassifizierung gehören die E-Mail-Spam-Klassifizierung, die Gruppierung von Kunden in Kategorien basierend auf der Kaufhistorie und die Erkennung handschriftlicher Nummern.

Rückschritt

KNN führt eine Regression durch, indem es den Wert eines Datenpunkts basierend auf dem Durchschnitt (oder gewichteten Durchschnitt) seiner k-nächsten Nachbarn schätzt. KNN kann beispielsweise Immobilienpreise basierend auf ähnlichen Immobilien in der Nachbarschaft, Aktienkurse basierend auf historischen Daten für ähnliche Aktien oder Temperaturen basierend auf historischen Wetterdaten an ähnlichen Orten vorhersagen.

Anwendungen des KNN-Algorithmus in ML

Aufgrund seiner relativen Einfachheit und der Fähigkeit, sowohl Klassifizierung als auch Regression durchzuführen, bietet KNN ein breites Anwendungsspektrum. Dazu gehören Bilderkennung, Empfehlungssysteme und Textklassifizierung.

Bilderkennung

Die Bilderkennung ist aufgrund ihrer Klassifizierungsfähigkeiten eine der häufigsten Anwendungen von KNN. KNN führt die Bilderkennung durch, indem es Merkmale im unbekannten Bild, wie Farben und Formen, mit Merkmalen in einem beschrifteten Bilddatensatz vergleicht. Dies macht KNN in Bereichen wie Computer Vision nützlich.

Empfehlungssysteme

KNN kann Benutzern Produkte oder Inhalte empfehlen, indem es ihre Präferenzdaten mit den Daten ähnlicher Benutzer vergleicht. Wenn ein Benutzer beispielsweise mehrere klassische Jazzlieder gehört hat, kann KNN Benutzer mit ähnlichen Vorlieben finden und Songs empfehlen, die diesen Benutzern gefallen haben. Daher kann KNN dazu beitragen, das Benutzererlebnis zu personalisieren, indem Produkte oder Inhalte auf der Grundlage ähnlicher Daten empfohlen werden.

Textklassifizierung

Bei der Textklassifizierung wird versucht, nicht kategorisierten Text anhand seiner Ähnlichkeit mit vorkategorisiertem Text zu klassifizieren. Die Fähigkeit von KNN, die Nähe von Wortmustern zu bewerten, macht es zu einem effektiven Werkzeug für diesen Anwendungsfall. Die Textklassifizierung ist besonders nützlich für Aufgaben wie die Stimmungsanalyse, bei der Texte als positiv, negativ oder neutral klassifiziert werden, oder für die Bestimmung der Kategorie eines Nachrichtenartikels.

Vorteile des KNN-Algorithmus in ML

KNN bietet mehrere bemerkenswerte Vorteile, darunter seine Einfachheit, Vielseitigkeit und das Fehlen einer Schulungsphase.

Einfachheit

Im Vergleich zu vielen anderen ML-Algorithmen ist KNN leicht zu verstehen und zu verwenden. Die Logik hinter KNN ist intuitiv – es klassifiziert oder prognostiziert (Regression) neue Datenpunkte basierend auf den Werten benachbarter Datenpunkte – was es zu einer beliebten Wahl für ML-Praktiker, insbesondere für Anfänger, macht. Zusätzlich zur Auswahl eines Werts für k ist für die Verwendung von KNN eine minimale Optimierung der Hyperparameter erforderlich.

Vielseitigkeit

KNN kann sowohl für Klassifizierungs- als auch für Regressionsaufgaben verwendet werden, was bedeutet, dass es auf eine Vielzahl von Problemen und Datentypen angewendet werden kann, von der Bilderkennung bis zur Vorhersage numerischer Werte. Im Gegensatz zu spezialisierten Algorithmen, die auf einen Aufgabentyp beschränkt sind, kann KNN auf jeden entsprechend strukturierten, gekennzeichneten Datensatz angewendet werden.

Explizite Trainingsphase

Viele ML-Modelle erfordern eine zeit- und ressourcenintensive Trainingsphase, bevor sie nützlich werden. KNN hingegen speichert einfach die Trainingsdaten und verwendet sie direkt zum Vorhersagezeitpunkt. Auf diese Weise kann KNN mit neuen Daten aktualisiert werden, die sofort für die Vorhersage zur Verfügung stehen. Dies macht KNN besonders für kleine Datensätze attraktiv.

Nachteile des KNN-Algorithmus in ML

Trotz seiner Stärken bringt KNN auch einige Herausforderungen mit sich. Dazu gehören hohe Rechen- und Speicherkosten, Empfindlichkeit gegenüber Rauschen und irrelevanten Merkmalen sowie der „Fluch der Dimensionalität“.

Rechenaufwand der Vorhersage

Da KNN bei jeder Vorhersage den Abstand zwischen einem neuen Datenpunkt und jedem Datenpunkt in seinem gesamten Trainingsdatensatz berechnet, steigt der Rechenaufwand der Vorhersage schnell an, wenn der Datensatz wächst. Dies kann zu langsamen Vorhersagen führen, wenn der Datensatz groß ist oder das KNN auf unzureichender Hardware ausgeführt wird.

Fluch der Dimensionalität

KNN leidet unter dem sogenannten „Fluch der Dimensionalität“, der seine Fähigkeit zur Verarbeitung hochdimensionaler Daten einschränkt. Wenn die Anzahl der Features in einem Datensatz zunimmt, werden die meisten Datenpunkte dünner und nahezu gleich weit voneinander entfernt. Daher werden Entfernungsmetriken weniger nützlich, was es für KNN schwierig macht, in hochdimensionalen Datensätzen Nachbarn zu finden, die wirklich in der Nähe sind.

Speicherintensiv

Ein einzigartiges Merkmal von KNN besteht darin, dass es den gesamten Trainingsdatensatz im Speicher speichert, um ihn zum Vorhersagezeitpunkt zu verwenden. Bei begrenztem Speicher oder großen Datensätzen kann dies problematisch und unpraktisch sein. Andere ML-Algorithmen umgehen diese Herausforderung, indem sie Trainingsdaten durch Modelltraining und Parameteroptimierung in erlernte Merkmale verdichten und destillieren. KNN hingegen muss jeden Datenpunkt behalten, was bedeutet, dass der Speicher linear mit der Größe des Trainingsdatensatzes wächst.

Empfindlichkeit gegenüber Rauschen und irrelevanten Funktionen

Die Stärke von KNN liegt in der einfachen, intuitiven Entfernungsberechnung. Dies bedeutet jedoch auch, dass unwichtige Merkmale oder Rauschen zu irreführenden Entfernungsberechnungen führen können, was sich negativ auf die Vorhersagegenauigkeit auswirkt. Daher werden bei KNN häufig Techniken zur Merkmalsauswahl oder Dimensionsreduktion wie die Hauptkomponentenanalyse (PCA) verwendet, um sicherzustellen, dass die wichtigen Merkmale den größten Einfluss auf die Vorhersage haben.