KNNKlassifikation

KNNKlassifikation ist ein instanzbasierter Lernalgorithmus des überwachten Lernens. Bei einem neuen Datenpunkt x wird die Klasse durch Berücksichtigung der k nächsten Trainingsbeispiele im Merkmalsraum vorhergesagt. Die Methode speichert das Trainingsset und führt die Vorhersage anhand der Nachbarn durch, ohne eine explizite Modellstruktur zu erlernen.

Dabei wählt man eine Distanzmetrik, üblicherweise den euklidischen Abstand, aber auch Manhattan oder Minkowski sind gebräuchlich. Für x bestimmt man die k Trainingsbeispiele mit den geringsten Distanzen zu x. Die vorhergesagte Klasse y hat durch Mehrheitsabstimmung der Nachbarn; optional können die Nachbarn gewichtet werden, zum Beispiel mit dem Kehrwert der Distanz.

Da kein Training im klassischen Sinn erfolgt, hängt die Vorhersage zeitlich stark von der Größe des Trainingssets ab. Ohne Indexstruktur muss jedes Mal das gesamte Training durchsucht werden, was teuer sein kann. Beschleunigungen ergeben sich durch Datenstrukturen wie KD-Bäume oder Ball-Bäume sowie durch Vorverarbeitung der Merkmale (Normalisierung, Skalierung).

Vorteile sind Einfachheit, kein Annahmen über Verteilungen und gute Anpassungsfähigkeit an komplexe Trennflächen. Nachteile sind hohe Abhängigkeit von der Datenmenge, Empfindlichkeit gegenüber Rauschen und hohen Dimensionalitäten sowie eine langsame Abfrage bei großen Datensätzen, da jedes neue Beispiel k Nachbarn durchsuchen muss. Zudem erfordert KNNKlassifikation eine sinnvolle Merkmalsdarstellung, da die Distanz zwischen Punkten stark von der Feature-Skalierung beeinflusst wird.

Anwendungen finden sich in Bereichen wie Mustererkennung, Bild- oder Textklassifikation und anderen Kontexten, in denen robuste Nichtlinearitäten wichtig sind und der Trainingsaufwand gering bleiben soll, sofern ausreichende Rechenleistung für Vorhersagen vorhanden ist.