Der K-Nächste-Nachbarn-Algorithmus, auch KNN oder k-NN genannt, ist ein nichtparametrischer, überwachter Lernklassifikator, der das Konzept der Nähe nutzt, um Klassifizierungen oder Vorhersagen über die Gruppierung eines einzelnen Datenpunktes zu treffen. Obwohl er sowohl für Regressions- als auch für Klassifikationsprobleme verwendet werden kann, wird er in der Regel als Klassifikationsalgorithmus eingesetzt, der von der Annahme ausgeht, dass ähnliche Punkte in der Nähe voneinander gefunden werden können.
Bei Klassifizierungsproblemen wird eine Bezeichnung für eine Klasse auf der Grundlage einer „Mehrheitswahl" zugewiesen, d. h. es wird die Bezeichnung verwendet, die um einen bestimmten Datenpunkt herum am häufigsten vorkommt. Obwohl dies technisch gesehen als „einfache Mehrheitswahl" gilt, wird in der Fachliteratur häufiger einfach der Begriff „Mehrheitswahl" verwendet. Der Unterschied zwischen diesen Begriffen besteht darin, dass die „Mehrheitswahl" technisch gesehen eine absolute Mehrheit von mehr als 50 % erfordert, was vor allem dann gut funktioniert, wenn nur zwei Kategorien vorhanden sind. Wenn Sie mehrere Klassen haben, z. B. vier Kategorien brauchen Sie nicht unbedingt 50 % der Stimmen, um eine Schlussfolgerung über eine Klasse zu ziehen. Sie können eine Klassenbezeichnung zuordnen, wenn diese Klasse mehr als 25 % der Stimmen erhält. Die University of Wisconsin-Madison fasst dies gut anhand eines Beispiels hier zusammen (PDF, 1,2 MB) (Link befindet sich außerhalb von ibm.com).
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 eingesetzt wird. Bevor jedoch eine Klassifizierung vorgenommen werden kann, muss der Abstand definiert werden. Am häufigsten wird der euklidische Abstand verwendet, auf den wir im Folgenden noch näher eingehen werden.
Es ist außerdem erwähnenswert, dass der KNN-Algorithmus zur Familie der „Lazy Learning"-Modelle (d. h. Modelle für „träges Lernen") gehört, was bedeutet, dass er nur einen Trainingsdatensatz speichert, anstatt eine Trainingsphase zu durchlaufen. Dies bedeutet auch, dass die gesamte Verarbeitung erfolgt, wenn eine Klassifizierung oder Vorhersage vorgenommen wird. Da sich dieser Ansatz stark auf den Arbeitsspeicher stützt, um alle Trainingsdaten zu speichern, wird er auch als instanz- oder speicherbasiertes Lernverfahren bezeichnet.
Die ersten Ideen zum KNN-Modell werden in diesem Arbeitspapier (PDF, 1,1 MB) (Link befindet sich außerhalb von ibm.com) von 1951 Evelyn Fix und Joseph Hodges zugeschrieben, während Thomas Cover ihr Konzept in seiner Forschungsarbeit (PDF 1 MB) (Link befindet sich außerhalb von ibm.com), „Nearest Neighbor Pattern Classification" (Klassifizierung von Mustern durch den nächsten Nachbarn), weiter ausbaut. Dieser Algorithmus ist zwar nicht mehr so populär wie früher, gehört aber aufgrund seiner Einfachheit und Genauigkeit immer noch zu den ersten Algorithmen, die man in der Datenwissenschaft lernt. Mit zunehmender Größe eines Datensatzes wird KNN jedoch zunehmend ineffizient, was wiederum die Gesamtleistung eines Modells beeinträchtigt. KNN wird häufig für einfache Empfehlungssysteme, Mustererkennung, Data Mining, Finanzmarktprognosen, Erkennung von Eindringlingen und vieles mehr verwendet.
Zusammenfassend lässt sich sagen, dass das Ziel des K-Nächste-Nachbarn-Algorithmus darin besteht, die nächsten Nachbarn eines bestimmten Abfragepunkts zu ermitteln, so dass wir diesem Punkt eine Klassenbezeichnung zuweisen können. Um dies erfolgreich tun zu können, hat KNN jedoch einige Anforderungen:
Bestimmung der Abstands-Metriken
Um zu ermitteln, welche Datenpunkte einem bestimmten Abfragepunkt am nächsten liegen, muss der Abstand zwischen dem Abfragepunkt und den anderen Datenpunkten berechnet werden. Diese Abstandsmetriken helfen bei der Bildung von Entscheidungsgrenzen, die die Abfragepunkte in verschiedene Regionen unterteilen. Sie werden häufig Entscheidungsgrenzen sehen, die mithilfe von Voronoi-Diagrammen visualisiert werden.
Es gibt zwar mehrere Abstandsmaße, aus denen Sie auswählen können, aber in diesem Artikel werden nur die folgenden Abstandsmaße behandelt:
Euklidischer Abstand (p=2): Dies ist das am häufigsten verwendete Abstandsmaß, das auf reellwertige Vektoren beschränkt ist. Über die nachstehende Formel wird eine gerade Linie zwischen dem Abfragepunkt und dem anderen zu messenden Punkt gemessen.
Manhattan-Abstand (p=1): Hierbei handelt es sich um eine weitere beliebte Abstandsmetrik, die den absoluten Wert zwischen zwei Punkten misst. Sie wird auch als „Taxidistanz" oder „Stadtblock-Distanz" bezeichnet, da sie üblicherweise mithilfe eines Rasters visualisiert wird, das veranschaulicht, wie man durch die Straßen einer Stadt von einer Adresse zu einer anderen gelangen kann.
Minkowski-Abstand: Dieses Abstandsmaß ist die verallgemeinerte Form der euklidischen und der Manhattan-Abstandsmetrik. Der Parameter p in der nachstehenden Formel ermöglicht die Entwicklung anderer Abstandsmetriken. Der euklidische Abstand wird durch diese Formel dargestellt, wenn p = 2. Der Manhattan-Abstand wird mit p = 1 bezeichnet.
Hamming-Abstand: Diese Methode wird typischerweise bei booleschen oder String-Vektoren verwendet, um die Punkte zu identifizieren, an denen die Vektoren nicht übereinstimmen. Aus diesem Grund wird diese Metrik auch als Überlappungsmetrik bezeichnet. Sie lässt sich mit der folgenden Formel darstellen:
Ein Beispiel: Bei den folgenden Zeichenketten wäre der Hamming-Abstand 2, da sich nur zwei der Werte unterscheiden.
Der k-Wert im KNN-Algorithmus legt fest, wie viele Nachbarn geprüft werden, um die Klassifizierung eines bestimmten Abfragepunkts zu bestimmen. Wenn beispielsweise k = 1 ist, wird die Instanz der gleichen Klasse zugeordnet wie ihr einziger nächster Nachbar. Die Festlegung von k kann ein Balanceakt sein, da unterschiedliche Werte zu einer Über- oder Unteranpassung führen können. Kleinere Werte von k können eine hohe Varianz, aber eine geringe Verzerrung aufweisen, und größere Werte von k können zu einer hohen Verzerrung und einer geringeren Varianz führen. Die Auswahl von k hängt weitgehend von den Eingabedaten ab, da Daten mit mehr Ausreißern oder Rauschen mit höheren Werten von k wahrscheinlich besser abschneiden werden. Insgesamt ist es empfehlenswert, eine ungerade Zahl für k zu wählen, um „Unentschieden" in der Klassifizierung zu vermeiden. Eine Kreuzvalidierungs-Taktik kann Ihnen dabei helfen, den optimalen k-Wett für Ihren Datensatz auszuwählen.
K-Nächste-Nachbarn und Python
Um mehr über den KNN-Algorithmus zu erfahren, können Sie Python und scikit-learn (auch bekannt als sklearn) verwenden. Unser Tutorial in Watson Studio hilft Ihnen, die grundlegende Syntax dieser Bibliothek zu erlernen, 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 KNN-Algorithmus wurde in einer Vielzahl von Anwendungen eingesetzt, vor allem im Bereich Klassifizierung. Einige dieser Anwendungsfälle umfassen:
- Vorverarbeitung von Daten: In Datensätzen fehlen häufig Werte, jedoch können diese Werte mithilfe des KNN-Algorithmus in einem Prozess geschätzt werden, der als „Imputation fehlender Daten" bekannt ist.
- Empfehlungsmechanismen: Der KNN-Algorithmus wurde unter Verwendung von Clickstream-Daten von Websites dafür eingesetzt, den Nutzern automatische Empfehlungen für zusätzliche Inhalte zu geben. Diese Untersuchung (Link befindet sich außerhalb von ibm.com) zeigt, dass ein Benutzer einer bestimmten Gruppe zugewiesen wird. Ihm wird dann auf der Grundlage des Benutzerverhaltens dieser Gruppe eine Empfehlung gemacht. Angesichts der Skalierungsprobleme mit KNN ist dieser Ansatz für größere Datensätze jedoch möglicherweise nicht optimal.
- Finanzwesen: KNN wurde weiterhin in einer Reihe von Anwendung in Finanz- und Wirtschaftswesen eingesetzt. Ein Arbeitspapier (PDF, 391 KB) (Link befindet sich außerhalb von ibm.com) zeigt beispielsweise, wie die Anwendung von KNN auf Kreditdaten Banken dabei helfen kann, das Risiko eines Kredits an ein Unternehmen oder eine Person zu bewerten. Er dient also der Feststellung der Kreditwürdigkeit eines Kreditantragstellers. In einem anderen Journal (PDF, 447 KB) (Link befindet sich außerhalb von ibm.com) wird seine Verwendung bei Börsenprognosen, Wechselkursen, Termingeschäften und Geldwäscheanalysen hervorgehoben.
- Gesundheitswesen: KNN fand ebenfalls im Gesundheitswesen Verwendung, um Vorhersagen über das Risiko von Herzinfarkten und Prostatakrebs zu treffen. Der Algorithmus errechnet in diesem Fall die wahrscheinlichsten Genexpressionen.
- Erkennung von Mustern: KNN hat auch bei der Erkennung von Mustern geholfen, z. B. bei der Klassifizierung von Zahlen und Texten (Link befindet sich außerhalb von ibm.com). Dies hat sich als besonders hilfreich erwiesen, um handschriftliche Nummern zu identifizieren, wie sie auf Formularen oder Briefumschlägen zu finden sind.
Wie jeder andere Algorithmus im Bereich maschinelles Lernen hat auch der KNN-Algorithmus seine speziellen Stärken und Schwächen. Je nach Projekt und Anwendung kann dieser Ansatz die richtige Wahl sein – oder auch nicht.
- Einfache Anwendung: Aufgrund seiner Unkompliziertheit und Genauigkeit ist dieser Algorithmus einer der ersten Klassifizierungsmechanismen, die ein angehender Datenwissenschaftler erlernt.
- Einfache Anpassung: 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 lediglich einen k-Wert und eine Abstandsmetrik, was im Vergleich zu anderen Algorithmen im maschinellen Lernen wenig ist.
- Schlechte Skalierung: Da KNN ein „träger" Algorithmus ist, benötigt er im Vergleich zu anderen Klassifikatoren mehr Arbeits- und Datenspeicher. Dies kann viel Zeit und Geld kosten. Mehr Arbeitsspeicher und Speicherplatz treiben die Geschäftskosten in die Höhe, und mehr Daten können längere Verarbeitungszeiten bedeuten. Es wurden zwar verschiedene Datenstrukturen, wie z. B. Ball-Tree, entwickelt, um die Schwächen in der Berechnung zu beheben, aber je nach Geschäftsproblem kann ein anderer Klassifikator besser geeignet sein.
- Der Fluch der Dimensionalität: Der KNN-Algorithmus neigt dazu, dem „Fluch der Dimensionalität" zum Opfer zu fallen, was bedeutet, dass er bei Eingabe hochdimensionaler Daten nicht gut funktioniert. Dies wird manchmal auch als Peaking-Phänomen bezeichnet (PDF, 340 MB) (Link befindet sich außerhalb von ibm.com), bei dem, nachdem der Algorithmus die optimale Anzahl von Merkmalen erreicht hat, zusätzliche Merkmale die Anzahl der Klassifizierungsfehler erhöhen, insbesondere wenn der Stichprobenumfang kleiner ist.
- Anfälligkeit für Überanpassung: Aufgrund des „Fluchs der Dimensionalität" ist KNN auch anfälliger für Überanpassung. Während Methoden zur Merkmalsauswahl und Dimensionalitätsreduktion eingesetzt werden, um dies zu verhindern, kann der Wert von k auch das Verhalten des Modells beeinflussen. Niedrigere Werte von k können zu einer Überanpassung der Daten führen, während höhere Werte von k die Vorhersagewerte eher „glätten", da die Werte über einen größeren Bereich oder eine größere Umgebung hinweg gemittelt werden. Ist der Wert von k jedoch zu hoch, kann es zu einer Unteranpassung der Daten kommen.
IBM Cloud Pak for Data ist eine offene, ausbaufähige Datenplattform, die eine Data Fabric-Lösung bereitstellt, um sämtliche Daten für KI und Analysezwecke auf jeder Cloud verfügbar zu machen.
Erstellen Sie KI-Modelle, führen Sie sie aus und verwalten Sie sie. Bereiten Sie Daten vor und erstellen Sie Modelle in jeder beliebigen Cloud mit Open-Source-Code oder visueller Modellierung. Prognostizieren und optimieren Sie Ihre Ergebnisse.
Erfahren Sie mehr über Db2 on Cloud, eine vollständig verwaltete SQL-Cloud-Datenbank, die für eine robuste Leistung konfiguriert und optimiert ist.