Nächste-Nachbarn-Klassifikation

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Die fraglichen Angaben werden daher möglicherweise demnächst entfernt. Bitte hilf der Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst. Näheres ist eventuell auf der Diskussionsseite oder in der Versionsgeschichte angegeben. Bitte entferne zuletzt diese Warnmarkierung.
Artikel komplett unbelegt. --217.186.67.100 17:08, 28. Okt. 2012 (CET)
K-Nächste-Nachbarn in einer zweidimensionalen Punktmenge mit k=1 (dunkelblau) und k=5 (hellblau). Der Radius der Kreise ist nicht fest.

Die Nächste-Nachbarn-Klassifikation ist eine parameterfreie Methode zur Schätzung von Wahrscheinlichkeitsdichtefunktionen. Der daraus resultierende k-Nearest-Neighbor-Algorithmus (KNN, zu deutsch „k-nächste-Nachbarn-Algorithmus“) ist ein Klassifikationsverfahren, bei dem eine Klassenzuordnung unter Berücksichtigung seiner k nächsten Nachbarn vorgenommen wird. Der Teil des Lernens besteht aus simplem Abspeichern der Trainingsbeispiele, was auch als lazy learning („träges Lernen“) bezeichnet wird.

k-Nearest-Neighbor-Algorithmus[Bearbeiten]

Die Klassifikation eines Objekts x \in \R^n (oft beschrieben durch einen Merkmalsvektor) erfolgt im einfachsten Fall durch Mehrheitsentscheidung. An der Mehrheitsentscheidung beteiligen sich die k nächsten bereits klassifizierten Objekte von x. Dabei sind viele Abstandsmaße denkbar (Euklidischer Abstand, Manhattan-Metrik, usw.). x wird der Klasse zugewiesen, welche die größte Anzahl der Objekte dieser k Nachbarn hat.

Voronoi-Diagramm mit sieben Stützstellen

Für ein klein gewähltes k besteht die Gefahr, dass Rauschen in den Trainingsdaten die Klassifikationsergebnisse verschlechtert. Für k=1 ergibt sich ein Voronoi-Diagramm. Wird k zu groß gewählt, besteht die Gefahr, Punkte mit großem Abstand zu x in die Klassifikationsentscheidung mit einzubeziehen. Diese Gefahr ist insbesondere groß, wenn die Trainingsdaten nicht gleichverteilt vorliegen oder nur wenige Beispiele vorhanden sind. Bei nicht gleichmäßig verteilten Trainingsdaten kann eine gewichtete Abstandsfunktion verwendet werden, die näheren Punkten ein höheres Gewicht zuweist als weiter entfernten. Ein praktisches Problem ist auch der Speicher- und Rechenaufwand des Algorithmus bei hochdimensionalen Räumen und vielen Trainingsdaten.

Siehe auch[Bearbeiten]