Der k-Nächste-Nachbarn-Algorithmus (k-NN) ist eine nicht-parametrische, instanzbasierte Lernmethode, die für Klassifikation und Regression verwendet wird. In beiden Fällen besteht die Eingabe aus den k nächsten Trainingsbeispielen in einem Merkmalsraum. Die Ausgabe hängt davon ab, ob k-NN für Klassifikation oder Regression verwendet wird: Bei der Klassifikation ist die Ausgabe eine Klassenmitgliedschaft, die durch eine Mehrheitsabstimmung unter den k nächsten Nachbarn bestimmt wird; bei der Regression ist die Ausgabe der Durchschnitt (oder gewichtete Durchschnitt) der Werte der k nächsten Nachbarn. k-NN ist eine Art von trägem Lernen, bei dem die Funktion nur lokal approximiert wird und alle Berechnungen bis zur Funktionsauswertung aufgeschoben werden. Da der Algorithmus auf Distanzberechnungen beruht, ist er empfindlich gegenüber der lokalen Struktur der Daten und der Wahl der Distanzmetrik.
Der Algorithmus wurde erstmals 1951 von Evelyn Fix und Joseph Hodges an der US Air Force School of Aviation Medicine entwickelt, ursprünglich als nicht-parametrische Klassifikationstechnik. Er wurde später von Thomas Cover und Peter Hart im Jahr 1967 erweitert und formalisiert, die seine asymptotischen Fehlergrenzen etablierten. Seitdem ist k-NN zu einem grundlegenden Werkzeug im maschinellen Lernen, in der Mustererkennung und im Data Mining geworden und wird oft als Basislinie für komplexere Modelle verwendet.
Funktionsweise
Bei einem gegebenen Abfragepunkt berechnet der Algorithmus die Distanz (typischerweise euklidisch, Manhattan oder Minkowski) zu jedem Trainingsbeispiel. Anschließend wählt er die k Trainingsbeispiele mit den kleinsten Distanzen aus. Für die Klassifikation ist das vorhergesagte Label dasjenige, das unter diesen k Nachbarn am häufigsten vorkommt. Für die Regression ist der vorhergesagte Wert der Mittelwert der Zielwerte der Nachbarn. Die Wahl von k ist entscheidend: Ein kleines k (z. B. 1) führt zu hoher Varianz und Empfindlichkeit gegenüber Rauschen, während ein großes k lokale Muster glätten kann und die Verzerrung erhöht. Üblich ist die Auswahl von k mittels Kreuzvalidierung, wobei für binäre Klassifikation oft ungerade Werte verwendet werden, um Gleichstände zu vermeiden.
Der Algorithmus erfordert außerdem eine Distanzmetrik. Die euklidische Distanz ist Standard für kontinuierliche Merkmale, aber für hochdimensionale oder kategoriale Daten können andere Metriken wie die Hamming-Distanz oder die Kosinus-Ähnlichkeit verwendet werden. Merkmalsskalierung (z. B. Normalisierung oder Standardisierung) ist unerlässlich, da Merkmale mit größeren Bereichen die Distanzberechnung dominieren.
Eigenschaften und Varianten
k-NN ist nicht-parametrisch, was bedeutet, dass es keine starken Annahmen über die zugrunde liegende Datenverteilung macht. Es ist auch instanzbasiert, da es den gesamten Trainingssatz speichert und direkt zur Vorhersagezeit verwendet. Dies macht das Training trivial (im Wesentlichen nur das Speichern der Daten), aber die Vorhersage rechenintensiv, mit einer Zeitkomplexität von O(nd) pro Abfrage, wobei n die Anzahl der Trainingsbeispiele und d die Anzahl der Merkmale ist.
Mehrere Varianten adressieren diese Einschränkungen. Gewichtetes k-NN weist näheren Nachbarn einen höheren Einfluss zu, oft unter Verwendung inverser Distanzgewichte. Lokal gewichtete Regression passt ein lineares Modell innerhalb der Nachbarschaft an. Für große Datensätze reduzieren approximative Nächste-Nachbarn-Suchtechniken wie k-d-Bäume, Ballbäume oder Locality-Sensitive Hashing die Suchkosten. In hohen Dimensionen verschlechtert der Fluch der Dimensionalität die Leistung, da Distanzen weniger unterscheidbar werden; Dimensionsreduktion oder Merkmalsauswahl wird oft angewendet.
Anwendungen
Der Algorithmus wird häufig in Bereichen wie Computersehen für die Bildklassifikation, Verarbeitung natürlicher Sprache für die Textkategorisierung und in der Bioinformatik für die Genexpressionsanalyse verwendet. Er kommt in Empfehlungssystemen vor, wo er Benutzer oder Artikel mit ähnlichen Präferenzen findet. Im Finanzwesen wird er für Kreditwürdigkeitsprüfung und Betrugserkennung eingesetzt. Seine Einfachheit und Interpretierbarkeit machen ihn zu einer häufigen ersten Wahl für explorative Analysen und als Benchmark gegen komplexere Modelle wie neuronale Netze.
Stärken und Einschränkungen
Die Hauptstärken von k-NN sind seine Einfachheit, die einfache Implementierung und die Effektivität bei kleinen bis mittelgroßen Datensätzen mit niedriger bis mittlerer Dimensionalität. Es erfordert keine Trainingsphase und eignet sich daher für inkrementelles Lernen. Zu seinen Einschränkungen gehören jedoch der hohe Speicherbedarf (Speichern aller Trainingsdaten), die langsame Vorhersagezeit, die Empfindlichkeit gegenüber irrelevanten Merkmalen und Rauschen sowie die schlechte Leistung in hochdimensionalen Räumen. Es nimmt außerdem an, dass alle Merkmale gleich wichtig sind, was in der Praxis selten zutrifft.
Beziehung zu anderen Methoden
k-NN wird oft mit anderen nicht-parametrischen Methoden wie Entscheidungsbäumen und Support-Vektor-Maschinen verglichen. Es ist eine grundlegende Technik im maschinellen Lernen und wird häufig in Lehrplänen der künstlichen Intelligenz unterrichtet. Seine Prinzipien liegen fortgeschritteneren Methoden wie Datenaugmentierung zugrunde, die synthetische Nachbarn erzeugen, und es wird im Curriculum-Lernen verwendet, um Trainingsbeispiele nach Schwierigkeit zu ordnen. In der modernen Praxis wird k-NN manchmal als letzte Schicht in Deep-Learning-Modellen für Metrik-Lernen verwendet, bei dem gelernte Einbettungen mittels Nächste-Nachbarn-Suche verglichen werden.
Siehe auch
Referenzen
- Cover, T., & Hart, P. (1967). Nearest neighbor pattern classification. IEEE Transactions on Information Theory.
- Fix, E., & Hodges, J. L. (1951). Discriminatory analysis, nonparametric discrimination: consistency properties. USAF School of Aviation Medicine.
- Altman, N. S. (1992). An introduction to kernel and nearest-neighbor nonparametric regression. The American Statistician.