Return to site

K-Nearest Neighbors

· ML Algorithmen

Der k-nearest-neighbours (KNN) Algorithmus ist ein Verfahren, mit dem neue Daten auf Basis von vorhandenen Daten klassifiziert werden können. Regression ist mit KNN auch möglich und wird im weiteren Verlauf dieses Artikels erläutert.

Beispiel: Klassifizierung von Wohnungsmieten

Bei KNN werden zu einem neuen Punkt die k nächsten Nachbarn (k ist hier eine beliebige Zahl) bestimmt, daher der Name des Algorithmus. Man versucht hier "ähnliche", also naheliegende Punkte heranzuziehen um zu entscheiden, welche Klasse ein Punkt bekommt. Die Klasse, die unter den k Nachbarn am häufigsten vorkommt wird die Klasse, zu der der neue Datenpunkt gehört. Kommen zwei oder mehr Klassen gleich häufig vor, so wird zwischen diesen zufällig entschieden, oder der neue Datenpunkt bekommt beide Klassen (falls möglich). Das folgende Bild zeigt ein Beispiel.

Bestimmung von k

Die Wahl von k hängt von der Anzahl der Referenzdatenpunkte ab, sollte dabei nicht zu klein aber auch nicht zu groß gewählt werden.

Im gezeigten Bild sehen wir an einem Beispiel, dass unser zu klassifizierende Datenpunkt (schwarzer Punkt) für k = 1 als blau klassifiziert wird, auch wenn er insgesamt näher an einer Gruppe von roten Punkten liegt. Das liegt daran, dass der blaue Punkt selbst ein Ausreißer ist. In der Statistik spricht man hier von Varianz oder dem Rauschen in den Daten. Niedrige Werte für k machen die Klassifikation anfällig für Varianz, also einzelne falsch klassifizierte Punkte in den Referenzdaten.

Wählen wir k höher, so wird der Punkt als rot klassifiziert. Der Algorithmus betrachtet nun einen größeren Kontext, in dem ersichtlich wird, dass der Punkt eher als rot als als blau einzuordnen ist. Bei vielen Punkten geht der Trend daher in die Richtung, dass für größere k die Grenze zwischen Klassen "weicher" wird. Wählen wir k so groß wie die Menge an Punkten, so werden alle zu klassifizierenden Punkte die Klasse erhalten, die insgesamt mehr Datenpunkte enthält. Dieser Extremfall ist in den meisten Fällen auch zu vermeiden.

Der optimale Wert für k kann auch algorithmisch bestimmt werden. Um den optimalen Wert für k zu bestimmen, wird der Referenzdatensatz in zwei Datensätze aufgeteilt: Ein Trainingsdatensatz und ein Testdatensatz. Der Testdatensatz enthält einige wenige zufällig gewählten Punkte (die nicht mehr in den Trainingsdaten vorkommen). Für verschiedene Werte von k werden die Testdaten anhand der Trainingsdaten klassifiziert. Danach gleicht man die berechneten Klassen mit den vorgegebenen Klassen ab. Aus der Differenz ergibt sich ein Fehlerwert, der ein Minimum erreicht wenn k optimal ist. Das hängt mit der bereits erwähnten Varianz für niedrige k zusammen. Für zu hohe k wird die Klassifikation zu ungenau, da zu viele Punkte mit einbezogen werden, die durch ihre Distanz nicht wirklich ähnlich zu dem zu klassifizierenden Punkt sind.

Regression mit KNN

K-nearest-neighbours ist nicht für Regression konzipiert worden, jedoch kann man den Algorithmus dafür auslegen, indem die Vorhersage, die im Falle einer Klassifikation die häufigste Klasse unter den k nächsten Nachbarn ist, nun ein Wert ist, der aus den Werten der k nächsten Nachbarn interpoliert wird. Anstatt die häufigste Klasse zu wählen, wird meistens aus den Regressionswerten ("Labels") der k nächsten Nachbarn ein (gewichteter) Durchschnitt berechnet.

Vor- und Nachteile

Während der Algorithmus sehr intuitiv und einfach zu implementieren ist und meistens gute Ergebnisse liefert, hängt seine Effizienz stark davon ab, wie schnell man die nächsten Nachbarn bestimmen kann. Bei vielen Datenpunkten in hohen Dimensionen wird dies zu einem Problem, da für jeden Punkt die Abstände zu jedem anderen Punkt berechnet und am Ende sortiert werden müssen. Ist die Liste der Abstände einmal sortiert, werden die k nächsten Punkte aus der Liste betrachtet. Dabei spielt es für die Rechenzeit (fast) keine Rolle, wie wir k wählen. Dadurch wird die Rechenzeit zumindest vorhersehbar.

All Posts
×

Almost done…

We just sent you an email. Please click the link in the email to confirm your subscription!

OK