Startseite
Themen
KNN
Der KNN-Algorithmus ist ein nicht parametrischer Klassifikator für überwachtes Lernen, der Nähe nutzt, um Klassifikationen oder Vorhersagen über die Gruppierung eines einzelnen Datenpunkts zu treffen. Er ist einer der beliebtesten und einfachsten Klassifikations- und Regressionsklassifikatoren, die heute im maschinellen Lernen verwendet werden.
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 (Link befindet sich außerhalb von ibm.com) gut mit einem Beispiel 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 dieser Arbeit (Link befindet sich außerhalb von ibm.com ) aus dem Jahr 1951 zugeschrieben, während Thomas Cover ihr Konzept in seiner Forschung (Link befindet sich außerhalb von ibm.com) „Nearest Neighbor Pattern Klassifizierung“, 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. Er wird häufig für einfache Empfehlungssysteme, Mustererkennung, Data Mining, Finanzmarktvorhersagen, Angriffserkennung und mehr verwendet.
Lernen Sie die Bausteine und Best Practices kennen, die Ihren Teams helfen, verantwortungsvolle KI zu beschleunigen.
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:
Bestimmen Sie Ihre Entfernungsmetriken
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.
KNN und Python
Um tiefer einzutauchen, können Sie mehr über den k-NN-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:
from sklearn.neighbors import KNeighborsClassifier
model_name = ‘K-Nearest Neighbor Classifier’
knnClassifier = KNeighborsClassifier(n_neighbors = 5, metric = ‘minkowski’, p=2)
knn_model = Pipeline(steps=[(‘preprocessor’, preprocessorForFeatures), (‘classifier’ , knnClassifier)])
knn_model.fit(X_train, y_train)
y_pred = knn_model.predict(X_test)
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 wurde der KNN-Algorithmus verwendet, um Nutzern automatische Empfehlungen für zusätzliche Inhalte zu geben. Diese Studie (Link befindet sich außerhalb von ibm.com) zeigt, dass der Benutzer a einer bestimmten Gruppe zugewiesen ist und auf Grundlage des Benutzerverhaltens 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.
- Finanzwesen: Er wird auch in einer Vielzahl von finanziellen und wirtschaftlichen Anwendungsfällen eingesetzt. Ein Artikel (Link befindet sich außerhalb von ibm.com) zeigt beispielsweise, wie die Verwendung von KNN für Kreditdaten Banken dabei helfen kann, das Risiko eines Darlehens an ein Unternehmen oder eine Einzelperson zu bewerten. Er wird verwendet, um die Kreditwürdigkeit eines Kreditantragstellers zu bestimmen. Ein weiteres Journal (Link befindet sich außerhalb von ibm.com) hebt die Verwendung in Aktienmarktprognosen, Währungskursen, Termingeschäften und Geldwäsche-Analysen 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 Identifizierung von Mustern geholfen, z. B. bei der Text- und Ziffernklassifizierung (Link befindet sich außerhalb von ibm.com). 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.
IBM Cloud Pak for Data ist eine offene, erweiterbare Datenplattform, die eine Data Fabric bietet, mit der alle Daten für KI und Analysen in jeder Cloud verfügbar gemacht werden.
Experimentieren Sie mit Foundation Models und erstellen Sie automatisch maschinelle Lernmodelle in unserem Studio der nächsten Generation für KI-Entwickler.
Erfahren Sie mehr über Db2 on Cloud, eine vollständig verwaltete SQL-Cloud-Datenbank, die für eine robuste Leistung konfiguriert und optimiert ist.
Lernen Sie die grundlegenden Konzepte für KI und generative KI kennen, einschließlich Prompt Engineering, große Sprachmodelle und die besten Open-Source-Projekte.
Lernen Sie die Grundlagen der Durchführung von k-Means-Clustering in Python kennen, indem Sie IBM Watson Studio Jupyter Notebooks auf watsonx.ai verwenden.
Lernen Sie die Grundlagen der Durchführung von k-Means-Clustering in R kennen, indem Sie IBM Watson Studio Jupyter Notebooks auf watsonx.ai verwenden.
Lernen Sie die Grundlagen der Lösung eines auf Klassifizierung basierenden Problems des maschinellen Lernens kennen und erhalten Sie eine vergleichende Studie zu einigen der derzeit beliebtesten Algorithmen.
Identifizieren von Klassen mit nächstgelegenen Nachbarn (nearest neighbors).