Was ist K-nächster Nachbar? Ein ML-Algorithmus zur Klassifizierung von Daten

Algorithmen treiben die Welt des maschinellen Lernens an.

Sie werden oft für ihre Vorhersagefähigkeiten gelobt und als harte Arbeiter bezeichnet, die riesige Datenmengen verbrauchen, um sofortige Ergebnisse zu erzielen.

Unter ihnen gibt es einen Algorithmus, der oft als faul bezeichnet wird. Aber es ist eine ziemliche Leistung, wenn es um die Klassifizierung von Datenpunkten geht. Er heißt k-nächste-Nachbarn-Algorithmus und wird oft als einer der wichtigsten zitiert   maschinelles Lernen   Algorithmen.

Was ist der Algorithmus für k-nächste Nachbarn?

Der Algorithmus für k-nächste Nachbarn (KNN) ist ein Datenklassifizierungsverfahren zum Abschätzen der Wahrscheinlichkeit, dass ein Datenpunkt ein Mitglied der einen oder anderen Gruppe wird, basierend darauf, zu welcher Gruppe die ihm am nächsten liegenden Datenpunkte gehören.

Der k-nächste-Nachbar-Algorithmus ist eine Art von   überwachtes maschinelles Lernen   Algorithmus zur Lösung von Klassifikations- und Regressionsproblemen. Es wird jedoch hauptsächlich für Klassifizierungsprobleme verwendet.

KNN ist ein faul lernender und nichtparametrischer Algorithmus.

Er wird Lazy-Learning-Algorithmus oder Lazy Learner genannt, weil er kein Training durchführt, wenn Sie die Trainingsdaten bereitstellen. Stattdessen speichert es die Daten nur während der Trainingszeit und führt keine Berechnungen durch. Es erstellt kein Modell, bis eine Abfrage für das Dataset ausgeführt wird. Damit ist KNN ideal für   Data-Mining.

Es wird als nichtparametrische Methode betrachtet, da es keine Annahmen über die zugrunde liegende Datenverteilung trifft. Einfach ausgedrückt versucht KNN festzustellen, zu welcher Gruppe ein Datenpunkt gehört, indem es sich die Datenpunkte um ihn herum ansieht.

Stellen Sie sich vor, es gibt zwei Gruppen, A und B.

Um zu bestimmen, ob sich ein Datenpunkt in Gruppe A oder Gruppe B befindet, betrachtet der Algorithmus die Zustände der Datenpunkte in seiner Nähe. Wenn die Mehrheit der Datenpunkte in Gruppe A ist, ist es sehr wahrscheinlich, dass der fragliche Datenpunkt in Gruppe A ist und umgekehrt.

Kurz gesagt beinhaltet KNN das Klassifizieren eines Datenpunkts durch Betrachten des nächsten annotierten Datenpunkts, der auch als nächster Nachbar bekannt ist.

Verwechseln Sie die K-NN-Klassifizierung nicht mit K-Means-Clustering. KNN ist ein überwachter Klassifizierungsalgorithmus, der neue Datenpunkte basierend auf den nächstgelegenen Datenpunkten klassifiziert. Auf der anderen Seite ist K-means-Clustering ein   unbeaufsichtigt   Clustering-Algorithmus, der Daten in eine Anzahl K von Clustern gruppiert.

Wie funktioniert KNN?

Wie oben erwähnt, wird überwiegend der KNN-Algorithmus als Klassifikator verwendet. Werfen wir einen Blick darauf, wie KNN funktioniert, um unsichtbare Eingabedatenpunkte zu klassifizieren.

Im Gegensatz zur Klassifizierung mit künstlichen neuronalen Netzen ist die Klassifizierung der k-nächsten Nachbarn leicht zu verstehen und einfach zu implementieren. Es ist ideal in Situationen, in denen die Datenpunkte gut definiert oder nicht linear sind.

Im Wesentlichen führt KNN einen Abstimmungsmechanismus durch, um die Klasse einer unsichtbaren Beobachtung zu bestimmen. Das bedeutet, dass die Klasse mit der Mehrheitsstimme zur Klasse des betreffenden Datenpunkts wird.

Wenn der Wert von K gleich eins ist, verwenden wir nur den nächsten Nachbarn, um die Klasse eines Datenpunkts zu bestimmen. Wenn der Wert von K gleich zehn ist, verwenden wir die zehn nächsten Nachbarn und so weiter.

Um dies ins rechte Licht zu rücken, betrachten Sie einen nicht klassifizierten Datenpunkt X. Es gibt mehrere Datenpunkte mit bekannten Kategorien, A und B, in einem Streudiagramm.

Angenommen, der Datenpunkt X befindet sich in der Nähe von Gruppe A.

Wie Sie wissen, klassifizieren wir einen Datenpunkt, indem wir uns die nächstgelegenen beschrifteten Punkte ansehen. Wenn der Wert von K gleich eins ist, verwenden wir nur einen nächsten Nachbarn, um die Gruppe des Datenpunkts zu bestimmen.

In diesem Fall gehört der Datenpunkt X zur Gruppe A, da sein nächster Nachbar in derselben Gruppe ist. Wenn Gruppe A mehr als zehn Datenpunkte hat und der Wert von K gleich 10 ist, dann gehört der Datenpunkt X immer noch zu Gruppe A, da alle seine nächsten Nachbarn in derselben Gruppe sind.

Angenommen, ein weiterer nicht klassifizierter Datenpunkt Y wird zwischen Gruppe A und Gruppe B platziert. Wenn K gleich 10 ist, wählen wir die Gruppe mit den meisten Stimmen aus, was bedeutet, dass wir Y der Gruppe zuordnen, in der es die meisten Nachbarn hat. Wenn Y beispielsweise sieben Nachbarn in Gruppe B und drei Nachbarn in Gruppe A hat, gehört es zu Gruppe B.

Die Tatsache, dass der Klassifikator die Kategorie mit der höchsten Stimmenzahl zuweist, gilt unabhängig von der Anzahl der vorhandenen Kategorien.

Sie fragen sich vielleicht, wie die Entfernungsmetrik berechnet wird, um zu bestimmen, ob ein Datenpunkt ein Nachbar ist oder nicht.

Es gibt vier Möglichkeiten, das Distanzmaß zwischen dem Datenpunkt und seinem nächsten Nachbarn zu berechnen: Euklidische Distanz , Manhattan-Distanz , Hamming-Distanz und Minkowski-Distanz . Von den dreien ist die euklidische Distanz die am häufigsten verwendete Distanzfunktion oder -metrik.

Um die Genauigkeit der KNN-Klassifikation zu validieren, a   Verwirrung Matrix   wird genutzt. Auch andere statistische Methoden wie der Likelihood-Ratio-Test werden zur Validierung herangezogen.

Bei der KNN-Regression sind die meisten Schritte gleich. Anstatt die Klasse mit den höchsten Stimmen zuzuweisen, wird der Durchschnitt der Werte der Nachbarn berechnet und dem unbekannten Datenpunkt zugewiesen.

Warum den KNN-Algorithmus verwenden?

Die Klassifizierung ist ein kritisches Problem in der Datenwissenschaft und im maschinellen Lernen. Das KNN ist einer der ältesten und dennoch genauesten Algorithmen, die für Musterklassifizierungs- und Regressionsmodelle verwendet werden.

Hier sind einige der Bereiche, in denen der k-nächste-Nachbar-Algorithmus verwendet werden kann:

• Bonitätsbewertung: Der KNN-Algorithmus hilft bei der Bestimmung der Bonitätsbewertung einer Person, indem er sie mit Personen mit ähnlichen Merkmalen vergleicht.
• Kreditgenehmigung: Ähnlich wie bei der Bonitätsbewertung ist der k-nächste-Nachbar-Algorithmus hilfreich, um Personen zu identifizieren, die mit größerer Wahrscheinlichkeit mit Krediten in Verzug geraten, indem ihre Merkmale mit ähnlichen Personen verglichen werden.
• Datenvorverarbeitung: Datensätze können viele fehlende Werte aufweisen. Der KNN-Algorithmus wird für einen Prozess namens Imputation fehlender Daten verwendet, der die fehlenden Werte schätzt.
• Mustererkennung: Die Fähigkeit des KNN-Algorithmus, Muster zu erkennen, schafft ein breites Anwendungsspektrum. Es hilft beispielsweise, Muster bei der Kreditkartennutzung zu erkennen und ungewöhnliche Muster zu erkennen. Die Mustererkennung ist auch nützlich, um Muster im Kaufverhalten von Kunden zu identifizieren.
• Aktienkursvorhersage: Da der KNN-Algorithmus ein Gespür für die Vorhersage der Werte unbekannter Entitäten hat, ist er nützlich, um den zukünftigen Wert von Aktien auf der Grundlage historischer Daten vorherzusagen.
• Empfehlungssysteme: Da KNN helfen kann, Benutzer mit ähnlichen Merkmalen zu finden, kann es in Empfehlungssystemen verwendet werden. Beispielsweise kann es in einer Online-Video-Streaming-Plattform verwendet werden, um Inhalte vorzuschlagen, die ein Benutzer mit größerer Wahrscheinlichkeit ansieht, indem analysiert wird, was ähnliche Benutzer sehen.
• Computer Vision: Der KNN-Algorithmus wird zur Bildklassifizierung verwendet. Da es in der Lage ist, ähnliche Datenpunkte zu gruppieren, z. B. Katzen zusammen und Hunde in einer anderen Klasse zu gruppieren, ist es in mehreren Fällen nützlich   Computer Vision   Anwendungen.

So wählen Sie den optimalen Wert von K

Es gibt keinen bestimmten Weg, um den besten K-Wert – mit anderen Worten – die Anzahl der Nachbarn in KNN zu bestimmen. Das bedeutet, dass Sie möglicherweise mit einigen Werten experimentieren müssen, bevor Sie sich entscheiden, mit welchem ​​Sie fortfahren möchten.

Eine Möglichkeit, dies zu tun, besteht darin, zu berücksichtigen (oder vorzugeben), dass ein Teil der Trainingsgebiete "unbekannt" ist. Dann können Sie die unbekannten Daten in der Testmenge mithilfe des k-nearest-neighbours-Algorithmus kategorisieren und analysieren, wie gut die neue Kategorisierung ist, indem Sie sie mit den Informationen vergleichen, die Sie bereits in den Trainingsdaten haben.

Bei einem Zwei-Klassen-Problem ist es besser, einen ungeraden Wert für K zu wählen. Andernfalls kann ein Szenario entstehen, in dem die Anzahl der Nachbarn in jeder Klasse gleich ist. Außerdem darf der Wert von K kein Vielfaches der Anzahl der vorhandenen Klassen sein.

Eine andere Möglichkeit, den optimalen Wert von K auszuwählen, besteht darin, sqrt(N) zu berechnen, wobei N die Anzahl der Stichproben im Trainingsdatensatz bezeichnet.

Allerdings kann K mit niedrigeren Werten wie K=1 oder K=2 verrauscht sein und den Auswirkungen von Ausreißern unterliegen. Auch die Wahrscheinlichkeit einer Überanpassung ist in solchen Fällen hoch.

Andererseits führt K mit größeren Werten in den meisten Fällen zu glatteren Entscheidungsgrenzen, sollte aber nicht zu groß sein. Andernfalls werden Gruppen mit einer geringeren Anzahl von Datenpunkten immer von anderen Gruppen überstimmt. Außerdem ist ein größeres K rechenintensiv.

Vor- und Nachteile von KNN

Einer der bedeutendsten Vorteile der Verwendung des KNN-Algorithmus besteht darin, dass kein Modell erstellt oder mehrere Parameter angepasst werden müssen. Da es sich um einen faulen Lernalgorithmus handelt und nicht um einen eifrigen Lerner, muss das Modell nicht trainiert werden. Stattdessen werden alle Datenpunkte zum Zeitpunkt der Vorhersage verwendet.

Das ist natürlich rechenintensiv und zeitaufwändig. Wenn Sie jedoch über die erforderlichen Rechenressourcen verfügen, können Sie KNN zum Lösen von Regressions- und Klassifizierungsproblemen verwenden. Es gibt jedoch mehrere schnellere Algorithmen, die genaue Vorhersagen erstellen können.

Natürlich ist KNN kein perfekter Algorithmus für maschinelles Lernen. Da der KNN-Prädiktor alles von Grund auf berechnet, ist er möglicherweise nicht ideal für große Datensätze.

KNN und der Fluch der Dimensionalität

Wenn Sie riesige Datenmengen zur Hand haben, kann es ziemlich schwierig sein, schnell und unkompliziert Informationen daraus zu extrahieren. Dafür können wir Dimensionsreduktionsalgorithmen verwenden, die im Wesentlichen dazu führen, dass die Daten "direkt auf den Punkt kommen".

Der Begriff „Fluch der Dimensionalität“ könnte den Eindruck erwecken, dass er direkt aus einem Science-Fiction-Film stammt. Das bedeutet aber, dass die Daten zu viele Merkmale aufweisen.

Wenn Daten zu viele Merkmale aufweisen, besteht ein hohes Risiko einer Überanpassung des Modells, was zu ungenauen Modellen führt. Zu viele Dimensionen machen es auch schwieriger, Daten zu gruppieren, da alle Datenstichproben im Datensatz gleich weit voneinander entfernt erscheinen.

Der Algorithmus für k-nächste Nachbarn ist aufgrund des Fluchs der Dimensionalität sehr anfällig für Überanpassung. Dieses Problem lässt sich aber mit lösen   Brute-Force-Implementierung   des KNN-Algorithmus. Aber es ist nicht praktikabel für große Datensätze.

KNN funktioniert nicht gut, wenn es zu viele Funktionen gibt. Daher müssen Techniken zur Dimensionsreduktion wie Hauptkomponentenanalyse (PCA) und Merkmalsauswahl während der Datenvorbereitungsphase durchgeführt werden.

KNN: der faule Algorithmus, der Herzen gewann

Obwohl KNN der faulste unter den Algorithmen ist, hat es sich einen beeindruckenden Ruf aufgebaut und ist ein Algorithmus der Wahl für verschiedene Klassifizierungs- und Regressionsprobleme. Natürlich ist es aufgrund seiner Faulheit möglicherweise nicht die beste Wahl für Fälle mit großen Datensätzen. Aber es ist einer der ältesten, einfachsten und genauesten Algorithmen, die es gibt.

Das Trainieren und Validieren eines Algorithmus mit einer begrenzten Datenmenge kann eine Herkulesaufgabe sein. Aber es gibt einen Weg, es effizient zu tun. Dies wird Kreuzvalidierung genannt und beinhaltet das Reservieren eines Teils der Trainingsdaten als Testdatensatz.