Was ist k-Nächste-Nachbarn (kNN)?
Definition
Der k-Nächste-Nachbarn-Algorithmus (kNN) ist ein überwachtes Lernverfahren, das einen Punkt anhand der Mehrheitsklasse seiner k nächsten gespeicherten Punkte klassifiziert.
kNN hat keinen expliziten Trainingsschritt. Der Algorithmus speichert die beschrifteten Beispiele und führt seine Berechnung aus, sobald eine Anfrage eintrifft. Scikit-learn bezeichnet dies als instanzbasiertes, nicht verallgemeinerndes Lernen.
So funktioniert es
- Legen Sie k und ein Abstandsmaß fest. Der euklidische Abstand ist die häufigste Wahl.
- Finden Sie die k gespeicherten Punkte, die dem Abfragepunkt am nächsten liegen.
- Weisen Sie dem Abfragepunkt die Klasse zu, die die meisten dieser k Punkte haben.
Standardmäßig hat jeder Nachbar eine Stimme. Beim gewichteten kNN zählen nähere Nachbarn stärker, zum Beispiel mit einem Gewicht von 1/d, wobei d der Abstand zum Nachbarn ist.
Die Wahl von k
Der beste Wert von k hängt von den Daten ab. Ein größeres k unterdrückt Rauschen, macht die Klassengrenzen aber weniger scharf. Eine Kreuzvalidierung findet aus den Daten einen guten Wert für k. Bei zwei Klassen vermeidet ein ungerades k Stimmengleichstand.
Grenzen
- Haben die Merkmale unterschiedliche Einheiten oder Skalen, kann eine Normalisierung jedes Merkmals die Genauigkeit stark verbessern.
- Eine Brute-Force-Suche vergleicht die Anfrage mit jedem gespeicherten Punkt. Das wird undurchführbar, wenn die Anzahl der Punkte wächst.
- Baumbasierte Suche, etwa mit einem KD-Baum, ist nur in niedrigen Dimensionen schnell (unter etwa 20). In hohen Dimensionen ist auch der euklidische Abstand weniger nützlich, weil alle Vektoren fast gleich weit von der Anfrage entfernt sind.
- Bibliotheken wie Faiss durchsuchen große Vektormengen. Sie bieten exakte Suche und komprimierte Indizes. Komprimierte Indizes liefern eine weniger genaue Suche.
Geschichte
Evelyn Fix und Joseph Hodges entwickelten die Methode erstmals 1951 in einem Bericht für die USAF School of Aviation Medicine. Thomas Cover und Hart veröffentlichten 1967 „Nearest neighbor pattern classification“. Bei unbegrenzten Trainingsdaten ist die Fehlerrate der 1-Nächster-Nachbar-Regel nicht schlechter als das Doppelte der Bayes-Fehlerrate.
Häufig gestellte Fragen
- Wie wählt man k bei kNN?
- Testen Sie mehrere Werte von k mit einer Kreuzvalidierung und behalten Sie den Wert, der auf zurückgehaltenen Daten das beste Ergebnis liefert. Der beste Wert von k hängt von den Daten ab. Ein größeres k unterdrückt Rauschen, macht die Klassengrenzen aber weniger scharf. Bei einem Problem mit zwei Klassen vermeidet ein ungerades k Stimmengleichstand.
- Braucht kNN ein Training?
- Nein, kNN hat keinen expliziten Trainingsschritt. Der Algorithmus speichert die beschrifteten Beispiele und führt alle Berechnungen aus, sobald eine Anfrage eintrifft. Scikit-learn bezeichnet dies als instanzbasiertes, nicht verallgemeinerndes Lernen.
- Was ist gewichtetes kNN?
- Beim gewichteten kNN zählen nähere Nachbarn bei der Abstimmung stärker als entferntere. Eine übliche Wahl ist ein Gewicht von 1/d, wobei d der Abstand zum Nachbarn ist. Standardmäßig verwendet scikit-learn gleichmäßige Gewichte, und weights = 'distance' ergibt Gewichte, die proportional zum Kehrwert des Abstands sind.
Referenzen
- sklearn-neighbors
- scikit-learn User Guide, 1.6 Nearest Neighbors scikit-learn
- wikipedia-knn
- k-nearest neighbors algorithm Wikipedia
- faiss-readme
- Faiss: a library for efficient similarity search and clustering of dense vectors Meta Research (facebookresearch/faiss on GitHub)
- faiss-getting-started
- Faiss wiki: Getting started Meta Research (facebookresearch/faiss on GitHub)
Dies ist ein Referenzeintrag. TarmacView bietet Drohneninspektionsdienste an und verkauft nicht die in diesem Glossar beschriebene Ausrüstung oder Materialien.