Was ist der k-Nearest-Neighbor-Algorithmus (KNN)?

Während der KNN-Algorithmus entweder für Regressions- oder Klassifizierungsprobleme verwendet werden kann, wird er in der Regel als Klassifizierungsalgorithmus verwendet, der davon ausgeht, dass ähnliche Punkte nahe beieinander gefunden werden können.

Bei Klassifizierungsproblemen wird eine Klassenkennzeichnung auf Grundlage einer Mehrheitswahl zugewiesen – d. h. es wird die Kennzeichnung verwendet, die am häufigsten rund um einen bestimmten Datenpunkt vorhanden ist. Während dies technisch als „relative Mehrheitsabstimmung“ („plurality voting“) bezeichnet wird, wird in der Literatur häufiger der Begriff „Mehrheitsabstimmung“ („majority vote“) verwendet. Der Unterschied zwischen diesen Terminologien besteht darin, dass „Mehrheitsabstimmung“ technisch gesehen eine Mehrheit von mehr als 50 % erfordert, was vor allem dann funktioniert, wenn es nur zwei Kategorien gibt. Wenn es mehrere Klassen gibt – z. B. vier Kategorien – werden nicht unbedingt 50 % der Stimmen benötigt, um eine Schlussfolgerung über eine Klasse zu ziehen; Sie könnten eine Klassenkennzeichnung mit einem Stimmenanteil von mehr als 25 % zuweisen. Die University of Wisconsin-Madison fasst dies hier mit einem Beispiel gut zusammen.

Regressionsprobleme verwenden ein ähnliches Konzept wie Klassifizierungsprobleme, aber in diesem Fall wird der Durchschnitt der k nächsten Nachbarn herangezogen, um eine Vorhersage über eine Klassifizierung zu treffen. Der Hauptunterschied besteht darin, dass die Klassifizierung für diskrete Werte verwendet wird, während die Regression für kontinuierliche Werte verwendet wird. Bevor jedoch eine Klassifizierung durchgeführt werden kann, muss die Entfernung definiert werden. Am häufigsten wird der euklidische Abstand verwendet, auf den wir weiter unten noch näher eingehen werden.

Es ist auch erwähnenswert, dass der KNN-Algorithmus auch Teil einer Familie von „Lazy Learning“-Modellen ist, was bedeutet, dass er nur einen Trainingsdatensatz speichert und nicht eine Trainingsphase durchläuft. Das bedeutet auch, dass die gesamte Berechnung zum Zeitpunkt der Klassifizierung oder Vorhersage erfolgt. Da er stark auf Speicher angewiesen ist, um alle Trainingsdaten zu speichern, wird er auch als instanzbasierte oder speicherbasierte Lernmethode bezeichnet.

Evelyn Fix und Joseph Hodges werden die ersten Ideen rund um das KNN-Modell in diesem Artikel von 1951 zugeschrieben, während Thomas Cover ihr Konzept in seiner Studie"Nearest Neighbor Pattern Classification" erweitert. Obwohl er nicht mehr so populär ist wie früher, ist er aufgrund seiner Einfachheit und Genauigkeit immer noch einer der ersten Algorithmen, die man im Bereich Data Science lernt. Wenn ein Datensatz jedoch wächst, wird KNN zunehmend ineffizient, was die Gesamtleistung des Modells beeinträchtigt. Es wird häufig für einfache Empfehlungssysteme, Mustererkennung, Datenabbau, Finanzmarktvorhersagen, Angriffserkennung und mehr eingesetzt.

Zusammenfassend lässt sich sagen, dass das Ziel des k-Nearest-Neighbor-Algorithmus darin besteht, die nächsten Nachbarn eines bestimmten Abfragepunkts zu identifizieren, damit wir diesem Punkt eine Klassenkennzeichnung zuweisen können. Um dies zu erreichen, hat KNN einige Anforderungen:

Um zu bestimmen, welche Datenpunkte einem bestimmten Abfragepunkt am nächsten liegen, muss die Entfernung zwischen dem Abfragepunkt und den anderen Datenpunkten berechnet werden. Diese Entfernungsmetriken helfen bei der Bildung von Entscheidungsgrenzen, die Abfragepunkte in verschiedene Regionen unterteilen. Häufig werden Entscheidungsgrenzen mit Voronoi-Diagrammen visualisiert.

Es gibt zwar mehrere Entfernungsmaße, aus denen Sie wählen können, aber in diesem Artikel werden nur die folgenden behandelt:

Euklidische Entfernung (p=2): Dies ist die am häufigsten verwendete Entfernungsmessung und beschränkt sich auf reellwertige Vektoren. Mit der folgenden Formel wird eine gerade Linie zwischen dem Abfragepunkt und dem anderen gemessenen Punkt gemessen.

Manhattan-Entfernung (p=1): Dies ist auch eine weitere beliebte Entfernungsmetrik, die den absoluten Wert zwischen zwei Punkten misst. Sie wird auch als Taxi-Entfernung oder Stadtblockentfernung bezeichnet, da sie häufig mit einem Gitternetz visualisiert wird und veranschaulicht, wie man über Stadtstraßen von einer Adresse zur anderen navigieren kann.

Minkowski-Entfernung: Dieses Entfernungsmaß ist die verallgemeinerte Form des euklidischen und des Manhattan-Entfernungsmaßes. Der Parameter p in der folgenden Formel ermöglicht die Erstellung anderer Entfernungsmetriken. Die euklidische Entfernung wird durch diese Formel dargestellt, wenn p gleich zwei ist und die Manhattan-Entfernung mit p gleich eins.

Hamming-Entfernung: Diese Technik wird in der Regel bei booleschen oder String-Vektoren verwendet, um die Punkte zu identifizieren, an denen die Vektoren nicht übereinstimmen. Daher wird sie auch als Überlappungsmetrik bezeichnet. Dies kann mit der folgenden Formel dargestellt werden:

Wenn Sie beispielsweise die folgenden Strings hätten, wäre die Hamming-Entfernung 2, da sich nur zwei der Werte unterscheiden.

Der K-Wert im k-NN-Algorithmus legt fest, wie viele Nachbarn überprüft werden, um die Klassifizierung eines bestimmten Abfragepunkts zu bestimmen. Wenn zum Beispiel k=1, wird die Instanz derselben Klasse wie ihr nächster einzelner Nachbar zugewiesen.

Die Definition von k kann ein Balanceakt sein, da unterschiedliche Werte zu einer Über- oder Unteranpassung führen können. Niedrigere Werte von k können eine hohe Varianz haben, aber eine niedrige Verzerrung, und größere Werte von k können zu einer hohen Verzerrung und einer geringeren Varianz führen. Die Auswahl von k hängt größtenteils von den Eingabedaten ab, da Daten mit mehr Sonderfällen oder Rauschen mit höheren Werten von k wahrscheinlich besser funktionieren. Insgesamt wird empfohlen, eine ungerade Zahl für k zu verwenden, um Gleichstände bei der Klassifizierung zu vermeiden, und Kreuzvalidierungstaktiken können Ihnen helfen, das optimale k für Ihren Datensatz auszuwählen.

Um tiefer einzutauchen, können Sie mehr über den KNN-Algorithmus erfahren, indem Sie Python und scikit-learn (auch bekannt als sklearn) verwenden. Unser Tutorial in Watson Studio hilft Ihnen dabei, die grundlegende Syntax aus dieser Bibliothek zu lernen, die auch andere beliebte Bibliotheken wie NumPy, Pandas und Matplotlib enthält. Der folgende Code ist ein Beispiel für die Erstellung und Vorhersage eines KNN-Modells:

Der k-NN-Algorithmus wird in einer Vielzahl von Anwendungen eingesetzt, vor allem im Bereich der Klassifizierung. Zu diesen Anwendungsfällen gehören:

• Datenvorverarbeitung: Datensätze enthalten häufig fehlende Werte, aber der KNN-Algorithmus kann diese Werte in einem Prozess schätzen, der als Imputation fehlender Daten bekannt ist.
  
  
• Empfehlungsmaschinen: Mithilfe von Clickstream-Daten von Websites wird der KNN-Algorithmus verwendet, um Nutzern automatische Empfehlungen für zusätzliche Inhalte zu geben. Diese Untersuchung zeigt, dass ein Benutzer einer bestimmten Gruppe zugewiesen wird und basierend auf dem Benutzerverhalten dieser Gruppe eine Empfehlung erhält. Angesichts der Skalierungsprobleme bei KNN ist dieser Ansatz jedoch für größere Datensätze möglicherweise nicht optimal.
  
  
• Finanzen: Er wird auch in einer Vielzahl von finanziellen und wirtschaftlichen Anwendungsfällen eingesetzt. Ein Artikel zeigt zum Beispiel, wie die Verwendung von KNN auf Kreditdaten Banken dabei helfen kann, das Risiko eines Kredits für ein Unternehmen oder eine Person zu bewerten. Er wird verwendet, um die Kreditwürdigkeit eines Kreditantragstellers zu bestimmen. Eine andere Zeitschrift hebt seine Verwendung bei forecasting, Devisenkursen, Termingeschäften und Analysen zur Geldwäsche hervor.
  
  
• Gesundheitswesen: KNN wird auch in der Gesundheitsbranche eingesetzt, um Vorhersagen über das Risiko von Herzinfarkten und Prostatakrebs zu treffen. Der Algorithmus berechnet dazu die wahrscheinlichsten Genexpressionen.
  
  
• Mustererkennung: KNN hat auch bei der Erkennung von Mustern geholfen, beispielsweise bei der Klassifizierung von Texten und Ziffern. Dies war besonders hilfreich bei der Identifizierung handgeschriebener Zahlen, die Sie möglicherweise auf Formularen oder Briefumschlägen finden.

Wie jeder maschinelle Lernalgorithmus hat k-NN seine Stärken und Schwächen. Je nach Projekt und Anwendung kann er die richtige Wahl sein oder auch nicht.

• Einfache Implementierung: Angesichts der Einfachheit und Genauigkeit des Algorithmus gehört er zu den ersten Klassifikatoren, die ein angehender Data Scientist lernt.
  
• Passt sich leicht an: Wenn neue Trainingsmuster hinzugefügt werden, passt sich der Algorithmus an die neuen Daten an, da alle Trainingsdaten im Arbeitsspeicher gespeichert sind.
  
  
• Wenige Hyperparameter: KNN benötigt nur einen k-Wert und eine Entfernungsmetrik, was im Vergleich zu anderen Algorithmen für maschinelles Lernen niedrig ist.

• Nicht gut skalierbar: Da KNN ein Lazy-Algorithmus ist, beansprucht er im Vergleich zu anderen Klassifikatoren mehr Arbeitsspeicher und Datenspeicher. Dies kann sowohl zeitlich als auch finanziell kostspielig sein. Mehr Arbeitsspeicher und Speicherplatz treiben die Geschäftskosten in die Höhe, und die Verarbeitung von mehr Daten kann länger dauern. Während verschiedene Datenstrukturen wie Ball-Tree erstellt wurden, um die rechnerischen Ineffizienzen zu beheben, kann je nach Geschäftsproblem ein anderer Klassifikator ideal sein.
  
  
• Fluch der Dimensionalität: Der KNN-Algorithmus neigt dazu, dem Fluch der Dimensionalität zum Opfer zu fallen, was bedeutet, dass er bei hochdimensionalen Dateneingaben nicht gut funktioniert. Dies wird manchmal auch als Peaking-Phänomen bezeichnet, bei dem, nachdem der Algorithmus die optimale Anzahl von Merkmalen erreicht hat, zusätzliche Merkmale die Anzahl der Klassifikationsfehler erhöhen, insbesondere wenn die Stichprobengröße kleiner ist.
  
  
• Anfällig für Überanpassung: Aufgrund des „Fluchs der Dimensionalität“ ist KNN auch anfälliger für Überanpassung. Während Techniken zur Merkmalsauswahl und Dimensionalitätsreduzierung verwendet werden, um zu verhindern, dass dies geschieht, kann sich der Wert von k auch auf das Verhalten des Modells auswirken. Niedrigere Werte von k können zu einer Überanpassung der Daten führen, während höhere Werte von k dazu neigen, die Vorhersagewerte zu „glätten“, da sie die Werte über einen größeren Bereich oder eine größere Nachbarschaft mitteln. Wenn der Wert von k jedoch zu hoch ist, kann er die Daten unteranpassen.