K-Nearest-Neighbors (k-NN) ist ein nicht-parametrischer Algorithmus des überwachten Lernens, der sowohl für Klassifikation als auch für Regression verwendet wird. Bei der Klassifikation wird einem neuen Datenpunkt die Klasse zugewiesen, die unter seinen k nächsten Nachbarn im Merkmalsraum am häufigsten vorkommt, bestimmt durch eine Distanzmetrik. Bei der Regression ist die Ausgabe der Durchschnitt (oder gewichtete Durchschnitt) der Werte dieser Nachbarn. Der Algorithmus ist instanzbasiert, das heißt, er speichert den gesamten Trainingsdatensatz und führt Berechnungen nur dann durch, wenn eine Vorhersage benötigt wird, und verschiebt alle Generalisierung bis zum Abfragezeitpunkt.
Die Methode wurde erstmals 1951 von Evelyn Fix und Joseph Hodges entwickelt und später von Thomas Cover erweitert. Sie ist einer der einfachsten Algorithmen des maschinellen Lernens, kann aber in vielen Bereichen eine wettbewerbsfähige Genauigkeit erreichen, insbesondere wenn die Entscheidungsgrenze unregelmäßig ist. Ihre Leistung hängt stark von der Wahl von k, der Distanzmetrik und der Merkmalsskalierung ab.
Historische Entwicklung
Die Ursprünge von k-NN reichen bis ins Jahr 1951 zurück, als Evelyn Fix und Joseph Hodges, die an der US Air Force School of Aviation Medicine arbeiteten, eine nicht-parametrische Klassifikationsmethode auf Basis der nächsten Nachbarn einführten. Ihre Arbeit war motiviert durch die Notwendigkeit, Beobachtungen zu klassifizieren, ohne eine spezifische statistische Verteilung anzunehmen. 1967 veröffentlichten Thomas Cover und Peter Hart eine wegweisende Arbeit, die die Eigenschaften des Algorithmus formalisierte, einschließlich Grenzen für seine Fehlerrate im Verhältnis zum Bayes-optimalen Klassifikator. Dies etablierte k-NN als einen theoretisch fundierten Ansatz in der Mustererkennung. Der Algorithmus gewann in den 1960er und 1970er Jahren mit dem Aufstieg der Informatik an Popularität, da er minimale Trainingszeit, aber erheblichen Speicherbedarf erforderte. Spätere Entwicklungen, wie die Einführung von gewichteter Abstimmung und Distanzmetrik-Lernen, adressierten einige seiner Einschränkungen.
Algorithmus-Überblick
Bei der k-NN-Klassifikation besteht die Eingabe aus einem Trainingssatz von beschrifteten Beispielen, die jeweils als Merkmalsvektor in einem mehrdimensionalen Raum dargestellt werden. Der Algorithmus speichert diese Vektoren und ihre Beschriftungen. Wenn ein Abfragepunkt präsentiert wird, berechnet er die Distanz vom Abfragepunkt zu allen Trainingspunkten, wählt die k nächsten aus und weist die Klasse zu, die am häufigsten unter ihnen vorkommt. Für k=1 wird der Abfragepunkt einfach der Klasse seines nächsten Nachbarn zugewiesen. Die Wahl von k ist entscheidend: Ein kleines k kann zu hoher Varianz und Empfindlichkeit gegenüber Rauschen führen, während ein großes k die Entscheidungsgrenze überglätten und Punkte aus anderen Klassen einschließen kann.
Für die Regression ist die Ausgabe der Durchschnitt der Zielwerte der k nächsten Nachbarn. Dies wird als Nearest-Neighbor-Glättung bezeichnet. Wenn k=1 ist, wird es zur Nearest-Neighbor-Interpolation, bei der der vorhergesagte Wert genau dem des nächsten Trainingspunkts entspricht. Gewichtete Varianten weisen näheren Nachbarn einen höheren Einfluss zu, oft mit Gewichten proportional zum Kehrwert der Distanz (1/d).
Distanzmetriken und Merkmalsskalierung
Die Wahl der Distanzmetrik ist entscheidend. Für kontinuierliche Merkmale ist die euklidische Distanz am gebräuchlichsten. Für diskrete Merkmale, wie in der Textklassifikation, werden Hamming-Distanz oder Überlappungsmetriken verwendet. In spezialisierten Bereichen wie der Genexpressionsanalyse wurden Korrelationskoeffizienten (Pearson, Spearman) eingesetzt. Die Abhängigkeit des Algorithmus von der Distanz bedeutet, dass Merkmale mit unterschiedlichen Einheiten oder Skalen die Berechnung dominieren können. Daher ist die Normalisierung jedes Merkmals auf eine gemeinsame Skala (z. B. z-Score oder Min-Max-Skalierung) unerlässlich, um einen gleichen Beitrag sicherzustellen. Dieser Vorverarbeitungsschritt kann die Genauigkeit erheblich verbessern.
Statistische Eigenschaften
Aus statistischer Sicht ist k-NN eine nicht-parametrische Methode, da sie keine funktionale Form für die zugrunde liegende Datenverteilung annimmt. Die Trainingsdaten werden als Paare (X_i, Y_i) angenommen, wobei X_i ein Merkmalsvektor und Y_i die Klassenbeschriftung ist. Für einen gegebenen Abfragepunkt x werden die Trainingspunkte nach ihrer Distanz zu x neu geordnet. Die Fehlerrate des Algorithmus konvergiert mit zunehmender Stichprobengröße gegen die Bayes-Fehlerrate, vorausgesetzt, k wächst angemessen mit n und k/n nähert sich Null. Diese Eigenschaft, die von Cover und Hart etabliert wurde, macht k-NN asymptotisch optimal. In endlichen Stichproben leidet der Algorithmus jedoch unter dem Fluch der Dimensionalität: Mit zunehmender Anzahl von Merkmalen wächst das Volumen des Raums exponentiell, und Punkte werden spärlich, wodurch Distanzmaße weniger aussagekräftig werden.
Vorteile und Nachteile
Ein großer Vorteil von k-NN ist seine Einfachheit und das Fehlen einer Trainingsphase. Es kann leicht durch Hinzufügen neuer Datenpunkte aktualisiert werden. Es ist auch effektiv für Mehrklassenprobleme und kann komplexe Entscheidungsgrenzen erfassen. Es hat jedoch bemerkenswerte Nachteile. Die Vorhersagezeit ist langsam, da Distanzen zu allen Trainingspunkten berechnet werden müssen, was es für große Datensätze ohne Optimierung (z. B. mit KD-Bäumen oder Ball-Bäumen) unpraktisch macht. Es ist empfindlich gegenüber irrelevanten Merkmalen und verrauschten Daten. Der Algorithmus ist auch empfindlich gegenüber der lokalen Struktur der Daten, was bedeutet, dass Ausreißer oder unbalancierte Klassenverteilungen die Ergebnisse verzerren können. Bei verzerrten Verteilungen dominieren Mehrheitsklassen, da sie wahrscheinlicher unter den k Nachbarn erscheinen. Gewichtung durch inverse Distanz oder Abstraktionstechniken können dies mildern.
Varianten und Erweiterungen
Mehrere Varianten adressieren die Einschränkungen von k-NN. Gewichtetes k-NN weist Nachbarn Gewichte basierend auf der Distanz zu, sodass nähere Punkte mehr Einfluss haben. Methoden des Distanzmetrik-Lernens, wie Large Margin Nearest Neighbor und Neighborhood Components Analysis, lernen eine benutzerdefinierte Distanzmetrik, um die Genauigkeit zu verbessern. Bearbeitetes k-NN entfernt verrauschte oder falsch klassifizierte Trainingspunkte, um die Generalisierung zu verbessern. Kondensiertes k-NN reduziert die Größe des Trainingssatzes, indem nur Punkte behalten werden, die für die Klassifikation wesentlich sind. Lokal adaptives k-NN passt k basierend auf der Dichte der Region um den Abfragepunkt an. Diese Varianten wurden in Bereichen wie Machine learning und Artificial intelligence angewendet, um die Leistung zu verbessern.
Anwendungen
Der k-NN-Algorithmus wird in verschiedenen Bereichen verwendet. In der Mustererkennung wird er für Bildklassifikation und Handschrifterkennung angewendet. In der Medizin wird er für die Diagnose basierend auf Patientenmerkmalen verwendet. Im Finanzwesen hilft er bei der Kreditwürdigkeitsprüfung und Betrugserkennung. In Empfehlungssystemen findet er ähnliche Benutzer oder Artikel. In der Bioinformatik klassifiziert er Genexpressionsdaten. Seine Einfachheit macht ihn zu einer häufigen Basislinie für den Vergleich mit komplexeren Modellen wie Neural network und Deep learning.
Beziehung zu anderen Methoden
k-NN ist eine Form des instanzbasierten Lernens, das sich von modellbasierten Ansätzen wie Neural network oder Support Vector Machine unterscheidet, die während des Trainings ein explizites Modell aufbauen. Es ist auch mit der nicht-parametrischen Dichteschätzung verwandt. Im breiteren Kontext von Machine learning wird k-NN oft als Benchmark verwendet. Es hat die Entwicklung von Locality-Sensitive Hashing und approximativer Suche nach nächsten Nachbarn beeinflusst, die in groß angelegten Systemen verwendet werden. Während moderne Methoden wie Deep learning k-NN in vielen Aufgaben übertroffen haben, bleibt k-NN für kleine Datensätze und interpretierbare Vorhersagen wertvoll.
Praktische Überlegungen
Bei der Implementierung von k-NN treten mehrere praktische Probleme auf. Der Wert von k wird typischerweise durch Kreuzvalidierung gewählt. Ungerade Werte von k werden oft verwendet, um Gleichstände bei binärer Klassifikation zu vermeiden. Merkmalsskalierung ist unerlässlich. Effiziente Datenstrukturen wie KD-Bäume können die Suche nach nächsten Nachbarn beschleunigen, verschlechtern sich jedoch in hohen Dimensionen. Für sehr große Datensätze sind approximative Methoden notwendig. Der Speicherbedarf des Algorithmus ist proportional zur Größe des Trainingssatzes, was eine Einschränkung sein kann. In modernen Anwendungen wird k-NN manchmal mit anderen Algorithmen kombiniert, z. B. als endgültiger Klassifikator auf gelernten Einbettungen aus einem Neural network.
Siehe auch
- Maschinelles Lernen
- Künstliche Intelligenz
- Neuronales Netz
- Deep Learning
- Stanford AI Lab
- MIT CSAIL
- Carnegie Mellon University
- BAIR (Berkeley AI Research)
- Xerox PARC
- Thomas G. Dietterich
- Michael I. Jordan
- Daphne Koller
- Anima Anandkumar
- Samy Bengio
- Joshua Tenenbaum
- Brendan Lake
- Melanie Mitchell
- Aaron Courville
- Alexei Efros
- Ali Rahimi