K-Nearest Neighbors (KNN) gehört zu den intuitivsten Machine-Learning-Algorithmen. Für einen neuen Datenpunkt werden die ähnlichsten bekannten Beispiele gesucht und deren Labels für die Entscheidung verwendet.
KNN wird typischerweise dem Supervised Learning zugeordnet.
Ablauf
- Trainingsdaten und Labels einlesen.
- Distanz vom neuen Punkt zu allen Trainingspunkten berechnen.
- Nach Distanz sortieren.
- Die nächsten
KPunkte auswählen. - Das häufigste Label zurückgeben.
Bedeutung von K
K bestimmt, wie viele Nachbarn abstimmen. Bei K = 1 entscheidet nur der nächste Punkt. Bei K = 5 werden fünf Nachbarn berücksichtigt.
Ungerade Werte wie 3 oder 5 sind bei binärer Klassifikation häufig praktisch, die optimale Wahl sollte jedoch validiert werden.
Euklidische Distanz
Ein häufig verwendetes Distanzmaß ist die Euclidean Distance:
d = sqrt((x2 - x1)^2 + (y2 - y1)^2)
Je kleiner die Distanz, desto ähnlicher sind sich die Punkte hinsichtlich der verwendeten Merkmale.
Warum Skalierung wichtig ist
Wenn ein Feature Werte zwischen 1 und 100 und ein anderes zwischen 1 und 500000 besitzt, kann das zweite Feature die Distanz dominieren. Standardization oder Min-Max Scaling sind deshalb oft notwendig.
Classification und Regression
Bei Classification wird das häufigste Label der Nachbarn gewählt.
Bei Regression kann beispielsweise der Durchschnitt der Werte der nächsten Nachbarn verwendet werden.
Vorteile
- Einfach verständlich
- Kaum explizite Trainingsphase
- Geeignet für kleine und mittlere Datensätze
- Für Klassifikation und Regression nutzbar
Grenzen
- Vorhersagen können bei großen Datenmengen teuer sein
- Empfindlich gegenüber unterschiedlichen Skalen
- Irrelevante Features verschlechtern das Ergebnis
- Hohe Dimensionalität reduziert die Aussagekraft von Distanzen
K auswählen
Ein sehr kleines K kann zu stark auf Rauschen reagieren. Ein sehr großes K kann lokale Strukturen verwischen. Mehrere Werte sollten daher auf Validierungsdaten verglichen werden.
Typische Anwendungen
- Kundenklassifikation
- Ähnlichkeitsbasierte Empfehlungen
- Einfache Anomalieerkennung
- Medizinische Klassifikation
- Mustererkennung
- Baseline-Modelle
Implementierung
Die Grundlogik lautet:
calculate distance to every training sample
sort by distance
take the nearest K
count labels
return the most frequent label
Die JavaScript-Implementierung im bereitgestellten Projekt verwendet genau dieses Verfahren mit euklidischer Distanz.
Fazit
KNN basiert auf der einfachen Annahme, dass ähnliche Datenpunkte häufig ähnliche Ergebnisse haben. Für gute Resultate sind insbesondere K, Distanzmaß, Skalierung, Datensatzgröße und Dimensionalität wichtig.