K-Nearest Neighbors
- Eingeführt von
- Cover, T.M. & Hart, P.E.
- Jahr
- 1967
- Typ
- Instance-based (non-parametric) learning
Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen
Was leistet sie?
K-Nearest Neighbors (KNN), formalisiert von Cover und Hart im Jahr 1967, ist eine nicht-parametrische, instanzbasierte Methode, die eine neue Beobachtung klassifiziert oder vorhersagt, indem sie die k nächstgelegenen Beispiele in den Trainingsdaten betrachtet.
Für die Klassifikation wird eine Mehrheitsentscheidung unter diesen Nachbarn getroffen; für die Regression wird der Durchschnitt ihrer Werte gebildet.
Die Intuition hinter der Methode
Die Idee ist einfach: ähnliche Eingaben führen tendenziell zu ähnlichen Ausgaben. Um einen neuen Punkt zu labeln, findet KNN die Handvoll Trainingsbeispiele, die ihm im Merkmalsraum am nächsten liegen, und lässt diese entscheiden. Es wird keine Gleichung im Voraus angepasst – die Trainingsdaten selbst bilden das Modell, und eine Vorhersage wird erst getroffen, wenn ein neuer Punkt eintrifft.
Geschichte
Die Klassifikation von Mustern durch nächste Nachbarn erhielt ihre formale statistische Grundlage von Thomas Cover und Peter Hart in ihrer Arbeit von 1967 in der IEEE Transactions on Information Theory, die die Fehlerrate der Nächste-Nachbar-Regel analysierte. KNN wurde zu einer der frühesten und beständigsten instanzbasierten Lernmethoden und bleibt ein Standard-Baseline-Klassifikator.
Wann wird sie eingesetzt?
Verwenden Sie KNN für die Klassifikation oder Vorhersage auf tabellarischen Daten mit kontinuierlichen, binären oder ordinalen Merkmalen und mindestens etwa 30 Beobachtungen. Es werden keine spezifischen Verteilungsannahmen getroffen, aber es erfordert, dass Merkmale normalisiert werden und die Anzahl der Merkmale im Verhältnis zur Stichprobengröße klein bleibt (p weit kleiner als n wird bevorzugt). Bei kleinen oder hochdimensionalen Stichproben dominiert der Fluch der Dimensionalität – Nachbarschaftsabstände werden informativ – und ein parametrisches Modell wie die logistische Regression oder Naive Bayes ist die bessere Wahl.
Grenzen und Hinweise
- Empfindlich gegenüber Merkmalskalierung; ohne Standardisierung dominieren Merkmale mit großer Skala die Distanz.
- Degradiert schnell in hohen Dimensionen (Fluch der Dimensionalität), wo Nachbarschaftsabstände ihre Bedeutung verlieren.
- Jede Vorhersage erfordert das Durchsuchen des gesamten Trainingsdatensatzes, was bei großen Datenmengen zur Vorhersagezeit langsam ist.
- Benötigt mindestens eine moderate Stichprobengröße; in kleinen Stichproben sind Abstände zu nächsten Nachbarn nicht aussagekräftig.
Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.
Stärken
- Konzeptionell einfach und leicht zu erklären: keine Trainingsgleichung, die Daten sind das Modell.
- Nicht-parametrisch – trifft keine Annahmen über die zugrundeliegende Verteilung.
- Behandelt natürlich Mehrklassenprobleme und komplexe, nichtlineare Entscheidungsgrenzen.
- Funktioniert sowohl für Klassifikation als auch für Regression mit der gleichen grundlegenden Idee.
Anwendungen
- Klassifikation von tabellarischen Daten in zwei oder mehr Kategorien.
- Numerische Vorhersage (Regression) durch Mittelung der nächsten Beispiele.
- Eine einfache, interpretierbare Baseline, bevor komplexere Modelle ausprobiert werden.
- Mustererkennung, bei der die Ähnlichkeit zu bekannten Beispielen die Entscheidung bestimmt.
So funktioniert es
So funktioniert es
Für eine neue Beobachtung misst KNN, wie weit sie von jedem Trainingsbeispiel entfernt ist, typischerweise unter Verwendung der Euklidischen Distanz über die Merkmale. Da die Distanz skalenabhängig ist, müssen die Merkmale zuerst standardisiert werden – andernfalls würde eine Variable, die auf einer großen numerischen Skala gemessen wird, die Berechnung dominieren und verzerren, welche Nachbarn als die nächsten gelten.
Formel
d(x, x_i) = \sqrt{\sum_{j=1}^{p}(x_j - x_{ij})^2}Die k Trainingspunkte mit den kleinsten Distanzen zur neuen Beobachtung werden als deren Nachbarn ausgewählt. Der Wert von k steuert, wie lokal die Entscheidung ist: ein kleines k folgt den Daten genau, ist aber anfällig für Rauschen, während ein größeres k die Grenze glättet. k sollte mittels Kreuzvalidierung (z. B. der Elbow-Methode) gewählt und nicht erraten werden.
Die Nachbarn entscheiden über die Vorhersage: bei der Klassifikation nimmt der neue Punkt die häufigste Klasse unter seinen k Nachbarn an (Mehrheitsentscheidung), und bei der Regression nimmt er den Durchschnitt ihrer Werte an. Dies macht die Methode leicht verständlich, aber jede Vorhersage erfordert das Durchsuchen des Trainingsdatensatzes.
Formel
\hat{y} = \text{mode/mean of the } k \text{ nearest neighbors}Häufige Fallstricke
- Überspringen der Merkmalsstandardisierung, sodass eine Variable mit großer Skala die Distanz unbemerkt kontrolliert.
- Auswahl von k von Hand anstatt mittels Kreuzvalidierung.
- Anwendung von KNN mit vielen Merkmalen und wenigen Beobachtungen, wo das Verhältnis von Dimension zu Stichprobe es bricht.
- Berichterstattung nur der Genauigkeit anstelle von Präzision, Recall, F1 und einer Konfusionsmatrix.
Häufig gestellte Fragen
Wie wähle ich den Wert von k?
k sollte mittels Kreuzvalidierung ausgewählt und nicht erraten werden – zum Beispiel, indem eine Reihe von Werten ausprobiert und die Elbow-Methode verwendet wird, um zu finden, wo sich der Fehler nicht mehr verbessert. Ein kleines k folgt den Daten genau, ist aber anfällig für Rauschen, während ein größeres k die Entscheidungsgrenze glättet.
Warum muss ich die Merkmale standardisieren?
KNN entscheidet, wer 'am nächsten' ist, anhand der Distanz, die skalenabhängig ist. Wenn ein Merkmal auf einer viel größeren numerischen Skala als die anderen liegt, dominiert es die Distanz und verzerrt die Nachbarschaftsgruppe. Die Standardisierung von Merkmalen (z. B. mit einem StandardScaler) ist erforderlich, damit jedes Merkmal fair beiträgt.
Warum hat KNN Schwierigkeiten mit vielen Merkmalen?
In hochdimensionalen Räumen werden alle Punkte ungefähr gleich weit entfernt – der Fluch der Dimensionalität – sodass 'nächste' Nachbarn nicht mehr sinnvoll nahe sind. Die Leistung von KNN sinkt schnell, und ein parametrisches Modell wie Naive Bayes oder logistische Regression ist normalerweise vorzuziehen. Wenn p weit kleiner als n ist, hilft das.
Gibt es einen Trainingsschritt?
Nicht im üblichen Sinne. KNN ist instanzbasiert (lazy): es speichert einfach die Trainingsdaten und erledigt die gesamte Arbeit zur Vorhersagezeit, wenn es Distanzen berechnet, um die nächsten Nachbarn eines neuen Punktes zu finden.
Verwandte Methoden
Quellen
Cover, T.M. & Hart, P.E. (1967). Nearest Neighbor Pattern Classification. IEEE Transactions on Information Theory, 13(1), 21–27.
DOI-Referenz öffnenKopiert.