Was bedeutet kNN?

Der kNN- oder auch K-Nearest-Neighbor-Algorithmus ist ein nähebasierter Machine-Learning-Algorithmus, der Datenpunkte mit dem Datensatz vergleicht, mit dem er trainiert wurde und den er für Vorhersagen gespeichert hat. Durch diese instanzbasierte Lernfunktion ist kNN ein „träger“ (lazy) Algorithmus, der sich gut für Klassifizierungs- oder Regressionsprobleme eignet. kNN basiert auf der Annahme, dass ähnliche Punkte nahe beieinander gefunden werden – Gleich und Gleich gesellt sich gern.

Als Klassifizierungsalgorithmus weist kNN neue Datenpunkte der Mehrheitsmenge innerhalb ihrer Nachbarn zu. Als Regressionsalgorithmus trifft kNN Vorhersagen anhand des Durschnitts der Werte in der Nähe des Abfragepunkts.

kNN ist ein beaufsichtigter Lernalgorithmus, bei dem „k“ für die Anzahl der nächsten Nachbarn steht, die für das Klassifizierungs- bzw. Regressionsproblem berücksichtigt werden, während „NN“ für die nächsten Nachbarn der für „k“ ausgewählten Zahl steht.

kNN wurde ursprünglich im Jahr 1951 von Evelyn Fix und Joseph Hodges bei ihrer Forschungsarbeit für das US-Militär entwickelt¹. Sie veröffentlichten eine Erklärung zur Trennschärfeanalyse, einer nichtparametrischen Klassifizierungsmethode. 1967 erweiterten Thomas Cover und Peter Hart diese nichtparametrische Klassifizierungsmethode und veröffentlichten ihren Artikel „Nearest Neighbor Pattern Classification“². Beinahe 20 Jahre später wurde der Algorithmus von James Keller als „Fuzzy kNN“ weiterentwickelt, um die Fehlerraten zu reduzieren³.

Heutzutage ist der kNN-Algorithmus aufgrund seiner Anpassbarkeit an verschiedenste Bereiche – von Genetik über Finanzen bis hin zum Kundenservice – sehr weit verbreitet.

Der kNN-Algorithmus ist ein beaufsichtigter Lernalgorithmus, d. h. er wird mit Trainingsdaten gefüttert und merkt sich diese Daten. Anhand dieser unbeschrifteten Daten lernt der Algorithmus eine Funktion, die für neue, unbeschriftete Daten eine passende Ausgabe liefert.

Auf diese Weise kann der Algorithmus Klassifizierungs- oder Regressionsprobleme lösen. Die Berechnung von kNN erfolgt zwar zur Abfragezeit und nicht während der Trainingsphase, aber der Algorithmus hat wichtige Datenspeicheranforderungen und ist daher recht arbeitsspeicherintensiv.

Für Klassifizierungsprobleme weist der kNN-Algorithmus eine mehrheitsbasierte Klassenbeschriftung zu und verwendet also die Beschriftung, die um einen bestimmten Datenpunkt herum am häufigsten auftritt. Die Ausgabe eine Klassifizierungsproblems ist also der Modus der nächsten Nachbarn.

Wichtige Unterscheidung: Mehrheitsbeschluss und Pluralitätsbeschluss

Beim Mehrheitsbeschluss gilt jeder Wert über 50 % als Mehrheit. Dies gilt auch, wenn zwei Klassenbeschriftungen betrachtet werden. Wenn wir jedoch mehrere Klassenbeschriftungen betrachten, kommt der Pluralitätsbeschluss zum Einsatz. In diesen Fällen reichen 33,3 % aus, um eine Mehrheit zu bilden und eine Vorhersage zu treffen. Der Pluralitätsbeschluss ist daher die passende Beschreibung für den kNN-Modus.

Sehen wir uns eine Abbildung dieser Unterscheidung an:

Eine binäre Vorhersage

Y: 🎉🎉🎉❤️❤️❤️❤️❤️

Mehrheitsbeschluss: ❤️

Pluralitätsbeschluss: ❤️

Situation mit mehreren Klassen

Y: ⏰⏰⏰💰💰💰🏠🏠🏠🏠

Mehrheitsbeschluss: N/V

Pluralitätsbeschluss: ❤️

Regressionsprobleme verwenden den Mittelwert der nächsten Nachbarn, um eine Klassifizierung vorherzusagen. Regressionsprobleme liefern Zahlenwerte als Ausgabe von Abfragen.

Angenommen, Sie erstellen ein Diagramm, um das Gewicht von Personen anhand ihrer Größe vorherzusagen, dann sind die Werte für die Größe unabhängig und die Werte für das Gewicht abhängig. Anhand des durchschnittlichen Verhältnisses zwischen Körpergröße und Gewicht können Sie das Gewicht einer Person (abhängige Variable) anhand von deren Größe (unabhängige Variable) schätzen.

Der Schlüssel zum kNN-Algorithmus ist die Ermittlung der Distanz zwischen dem Abfragepunkt und den anderen Datenpunkten. Anhand von Distanzmetriken können wir Entscheidungsgrenzen aufstellen. Diese Grenzen bilden unterschiedliche Datenpunktregionen. Es gibt verschiedene Methoden für die Distanzberechnung:

• Die Euklidische Distanz ist die am häufigsten verwendete Distanzmessung und verwendet eine gerade Linie zwischen dem Abfragepunkt und dem anderen gemessenen Punkt.
• Die Manhattan-Distanz ist ebenfalls eine beliebte Distanzmessung, die den absoluten Wert zwischen zwei Punkten ermittelt. Sie wird auf einem Raster dargestellt und manchmal auch als „Taxi“-Geometrie bezeichnet: Wie gelangt man von Punkt A (dem Abfragepunkt) nach Punkt B (dem gemessenen Punkt)?
• Die Minkowski-Distanz ist eine Verallgemeinerung der Euklidischen und der Manhattan-Distanzmetriken und ermöglicht die Schaffung neuer Distanzmetriken. Sie wird in einem genormten Vektorraum berechnet. Bei der Minkowski-Distanz ist „p“ der Parameter, der die bei der Berechnung zu verwendende Distanz definiert. Für p=1 wird die Manhattan-Distanz verwendet. Für p=2 wird die Euklidische Distanz verwendet.
• Die Hamming-Distanz wird manchmal auch als Überlappungsmetrik bezeichnet und verwendet boolesche oder Zeichenfolgenvektoren, um zu identifizieren, wo Vektoren nicht übereinstimmen. Sie misst also die Distanz zwischen zwei Zeichenfolgen mit gleicher Länge. Dies ist besonders hilfreich für die Fehlererkennung und für Fehlerkorrekturcodes.

Um den besten „k“-Wert – die Anzahl der berücksichtigten nächsten Nachbarn – auszuwählen, müssen Sie einige Werte ausprobieren, um herauszufinden, welche „k“-Werte die exaktesten Vorhersagen mit der geringsten Fehleranzahl liefern. Die Ermittlung des besten Werts ist ein Balanceakt:

• Niedrigere „k“-Werte führen zu instabilen Vorhersagen.
  Zum Beispiel: Ein Abfragepunkt ist umgeben von zwei grünen Punkten und einem roten Dreieck. Wenn k=1 ist und der Punkt einem der grünen Punkte am nächsten liegt, dann gibt der Algorithmus fälschlicherweise einen grünen Punkt als Ergebnis der Abfrage zurück. Niedrige „k“-Werte bedeuten eine hohe Varianz (das Modell passt zu gut zu den Trainingsdaten), hohe Komplexität und niedrige Verzerrung (das Modell ist komplex genug, um gut zu den Trainingsdaten zu passen).
• Hohe „k“-Werte führen zu mehr Rauschen.
  Höhere „k“-Werte verbessern die Genauigkeit der Vorhersagen, da die Modi oder Mittelwerte anhand von mehr Zahlen berechnet werden. Zu hohe „k“-Werte führen jedoch oft zu niedriger Varianz, niedriger Komplexität und starker Verzerrung (das Modell ist NICHT komplex genug, um gut zu den Trainingsdaten zu passen).

Im Idealfall sollten Sie einen „k“-Wert verwenden, der einen Mittelweg zwischen hoher Varianz und starker Verzerrung bildet. Außerdem ist es hilfreich, ungerade Werte für „k“ zu verwenden, um Gleichstände bei der Klassifizierungsanalyse zu vermeiden.

Der optimale „k“-Wert hängt auch von Ihrem Datensatz ab. Um den richtigen Wert zu finden, können Sie versuchen, die Quadratwurzel von „N“ zu ermitteln, wobei „N“ die Anzahl der Datenpunkte im Trainingsdatensatz ist. Kreuzvalidierungstechniken sind oft auch hilfreich, um den passenden „k“-Wert für Ihren Datensatz auszuwählen.

Der kNN-Algorithmus wird oft als der einfachste beaufsichtigte Lernalgorithmus bezeichnet, wodurch sich mehrere Vorteile ergeben:

• Einfachheit: kNN ist aufgrund der Einfachheit und Genauigkeit auch recht einfach zu implementieren. Daher ist dies oft eine der ersten Klassifizierungsmethoden, die Datenwissenschaftler kennenlernen.
• Anpassbarkeit: Sobald neue Trainingsdaten zum Datensatz hinzugefügt werden, passt der kNN-Algorithmus die Vorhersagen unter Berücksichtigung dieser neuen Daten an.
• Einfach zu programmieren: kNN erfordert nur wenige Hyperparameter: einen „k“-Wert und eine Distanzmetrik. Damit ist dieser Algorithmus relativ unkompliziert.

Außerdem erfordert der kNN-Algorithmus keine Trainingszeit, da die Trainingsdaten zunächst nur gespeichert werden und die Rechenleistung erst zum Vorhersagezeitpunkt eingesetzt wird.

Der kNN-Algorithmus ist zwar einfach, ist daher aber auch mit einigen Herausforderungen und Einschränkungen verbunden:

• Mangelhafte Skalierbarkeit: Der kNN-Algorithmus verbraucht viel Arbeits- und Datenspeicher und ist daher mit recht hohen Speicherkosten verbunden. Aufgrund der Arbeitsspeicherabhängigkeit ist dieser Algorithmus auch rechenintensiv, was sich wiederum auf andere Ressourcen auswirkt.
• Fluch der Dimensionalität: Dies ist ein Phänomen in der Informatik, bei dem ein fester Satz an Trainingsbeispielen durch eine Zunahme der Dimensionen und die dadurch entstehende Zunahme an Merkmalswerten in diesen Dimensionen unbrauchbar wird. Die Trainingsdaten des Modells können also mit der wachsenden Dimensionalität des Hyperraums nicht mithalten. Dadurch werden die Vorhersagen ungenauer, da die Distanz zwischen dem Abfragepunkt und ähnlichen Punkten zunimmt – in anderen Dimensionen.
• Überanpassung: Wie wir bereits gesehen haben, beeinflusst der „k“-Wert das Verhalten des Algorithmus. Dies ist besonders bei zu niedrigen „k“-Werten der Fall. Niedrigere „k“-Werte können zu einer Überanpassung führen, während höhere Werte die Vorhersagen „glätten“, da der Algorithmus die Werte über einen größeren Bereich mittelt.

Der für seine Einfachheit und Genauigkeit beliebte kNN-Algorithmus kommt in vielen Bereichen zum Einsatz, insbesondere für Klassifizierungsanalysen.

• Relevanzrangfolgen: kNN verwendet Algorithmen für natürliche Sprachverarbeitung (Natural Language Processing, NLP), um die relevantesten Ergebnisse für eine Abfrage zu ermitteln.
• Ähnlichkeitssuche für Bilder oder Videos: Die Bildähnlichkeitssuche verwendet Beschreibungen in natürlicher Sprache, um passende Bilder anhand von Textabfragen zu finden.

• Mustererkennung: kNN kann eingesetzt werden, um Muster in Text- oder Zahlenklassifizierungen zu finden.
• Finanzwesen: kNN wird im Finanzwesen eingesetzt, um Vorhersagen für Aktienmärkte, Wechselkurse usw. zu treffen.
• Produktempfehlungen und Empfehlungs-Engines: Denken Sie an Netflix! „Wenn Ihnen dies gefallen hat, dann gefällt Ihnen bestimmt auch ...“ Jede Site, die eine Version dieses Satzes verwendet, ob sichtbar oder nicht, verwendet höchstwahrscheinlich einen kNN-Algorithmus für ihre Empfehlungs-Engine.
• Gesundheitswesen: In der Medizin und der medizinischen Forschung wird der kNN-Algorithmus eingesetzt, um die Wahrscheinlichkeit bestimmter Genausdrücke zu berechnen. Damit können Ärzte die Wahrscheinlichkeit für Krebs, Herzinfarkte oder andere Erbkrankheiten vorhersagen.
• Vorverarbeitung der Daten: Der kNN-Algorithmus kann fehlende Werte in Datensätzen durch Schätzung ermitteln.

Mit Elasticsearch können Sie Ihre eigene kNN-Suche implementieren. Zwei Methoden werden unterstützt: geschätzte kNN-Suche und exakte Brute-Force-kNN-Suche. Sie können die kNN-Suche für Funktionen wie Ähnlichkeitssuche, Relevanzrangfolge auf Basis von NLP-Algorithmen sowie für Produktempfehlungen und Empfehlungs-Engines einsetzen.

kNN-Suche mit Elastic implementieren

kNN ist der k-Nearest-Neighbor-Algorithmus (k-nächster-Nachbar), wobei „k“ die Anzahl der nächsten Nachbarn ist, die bei der Analyse berücksichtigt werden.