Nächste-Nachbarn-Klassifikation
Die Nächste-Nachbarn-Klassifikation ist eine nichtparametrische 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 <math>k</math> 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. Eine Datennormalisierung kann die Genauigkeit dieses Algorithmus erhöhen.<ref>{{#invoke:Vorlage:Literatur|f}}</ref><ref>{{#invoke:Vorlage:Literatur|f}}</ref>
k-Nearest-Neighbor-Algorithmus
Die Klassifikation eines Objekts <math>x \in \R^n</math> (oft beschrieben durch einen Merkmalsvektor) erfolgt im einfachsten Fall durch Mehrheitsentscheidung. An der Mehrheitsentscheidung beteiligen sich die k nächsten bereits klassifizierten Objekte von <math>x</math>. Dabei sind viele Abstandsmaße denkbar (Euklidischer Abstand, Manhattan-Metrik usw.). <math>x</math> wird der Klasse zugewiesen, welche die größte Anzahl der Objekte dieser <math>k</math> Nachbarn hat. Für zwei Klassen kann ein Unentschieden bei der Mehrheitsentscheidung durch ein ungerades <math>k</math> verhindert werden.
Für ein klein gewähltes <math>k</math> besteht die Gefahr, dass Rauschen in den Trainingsdaten die Klassifikationsergebnisse auf den Testdaten verschlechtert. Für <math>k=1</math> ergibt sich ein Voronoi-Diagramm. Wird <math>k</math> zu groß gewählt, besteht die Gefahr, Punkte mit großem Abstand zu <math>x</math> 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.
Pseudocode-Beispiel
<syntaxhighlight lang="python" line="1"> function KNaechsteNachbarn(trainDaten, trainLabels, neuerPunkt, k=3)
"""
Parameter:
trainDaten (Liste von Listen): Trainingsdaten (Merkmalsvektoren).
trainLabels (Liste): Zugehörige Klassenlabels.
neuerPunkt (Liste): Zu klassifizierender Datenpunkt.
k (Ganzzahl): Anzahl der zu berücksichtigenden nächsten Nachbarn.
Rückgabe:
Vorhergesagtes Klassenlabel (Ganzzahl).
"""
# 1. Prüfung auf gleiche Dimension aller Punkte
dimension = length(neuerPunkt)
for index, trainingspunkt in trainDaten:
if length(trainingspunkt) != dimension:
error("Trainingspunkt " + index + " hat falsche Dimension: "
+ length(trainingspunkt) + " statt " + dimension)
# 2. Sicherstellung eines gültigen k-Werts
anzahlTrainingspunkte = length(trainDaten)
if k <= 0:
k = 1 # Mindestens ein Nachbar muss berücksichtigt werden
elif k > anzahlTrainingspunkte:
k = anzahlTrainingspunkte # k darf nicht größer als die Datenmenge sein
# 3. Berechnung der quadrierten euklidischen Distanzen
distanzen = []
for index, trainingspunkt in trainDaten:
distanzQuadrat = 0
# Summe der quadrierten Differenzen in allen Dimensionen
for i in 0 bis dimension-1:
differenz = trainingspunkt[i] - neuerPunkt[i]
distanzQuadrat = distanzQuadrat + (differenz * differenz)
# Speichere Tupel aus (Distanzquadrat, Index)
distanzen.hinzufügen((distanzQuadrat, index))
# 4. Sortierung der Distanzen und Auswahl der k nächsten Nachbarn
# Aufsteigend nach Distanzquadrat
distanzen.sortiere(nach = x -> x[0]) nachbarIndizes = [] for i in 0 bis k-1:
# Extrahiere Indizes der k kleinsten Distanzen
nachbarIndizes.hinzufügen(distanzen[i][1])
# 5. Mehrheitsentscheid (Majority Vote mit Tie-Breaking)
klassenAnzahl = {}
for index in nachbarIndizes:
label = trainLabels[index]
if label in klassenAnzahl:
klassenAnzahl[label] = klassenAnzahl[label] + 1
else:
klassenAnzahl[label] = 1
# Bestimmung der Siegerklasse mit Gleichstandsregelung
maxStimmen = max(klassenAnzahl.werte())
kandidaten = []
for klasse, stimmen in klassenAnzahl:
if stimmen == maxStimmen:
kandidaten.hinzufügen(klasse)
# Wähle die kleinste Klassenkennung als Tie-Breaker (z. B. 0 < 1)
return min(kandidaten)
</syntaxhighlight>
Siehe auch
- Mustererkennung
- Merkmalsraum
- Scikit-learn eine freie Software-Bibliothek zum maschinellen Lernen für die Programmiersprache Python
- OpenCV eine freie Programmbibliothek mit Algorithmen für die Bildverarbeitung und maschinelles Sehen
Literatur
- {{#invoke:Vorlage:Literatur|f}}
- {{#invoke:Vorlage:Literatur|f}}
Einzelnachweise
<references />