Der k-Nearest-Neighbor Algorithmus einfach erklärt

January 3, 2021
4 min
Machine Learning
Credits to Pexels from pixabay.com

Einer der einfachsten und gängigsten Algorithmen zur Klassifizierung von Daten ist der k-Nearest-Neighbor Algorithmus (KNN). Dieser Algorithmus kann dem Bereich des Supervised Learning zugeordnet werden und wird oft am Anfang eines Projektes verwendet, um einen ersten Überblick über die Daten zu erhalten. Ein großer Vorteil dieses Algorithmus ist, dass er im Gegensatz zu bspw. Neuronalen Netzen kein aufwendiges Training benötigt, sondern alle Daten bei jeder Klassifizierung verwendet werden. Der KNN-Algorithmus geht auf den Stanford Professor Thomas Cover zurück, der diesen in einem Paper 1967 beschrieben hat [1].

Der k-Nearest-Neighbor Algorithmus

Das Ziel des KNN-Algorithmus ist auf Basis der Nachbarn (Neighbors) des zu klassifizierenden Datenpunktes heraus zu finden, zu welcher Klasse der Punkt gehört. Wie so oft kann ein Algorithmus am besten an Hand eines Beispiels erläutert werden. Da wir aus dem technischen Bereich kommen, wählen wir als Beispielsobjekt eine Pumpe. Für diese Pumpe soll vorhergesagt werden, ob sie ausfallen wird oder nicht. Um eine Aussage treffen zu können werden Beispiele von Pumpen benötigt, die ausgefallen sind und von Pumpen die nicht ausgefallen sind. Wir nehmen an, dass in unserem Beispiel der Ausfall von Pumpen an Hand der durchschnittlichen Drehzahl und der Laufzeit der Pumpe festgemacht wurde. Wir haben also zwei Parameter, an denen wir den Ausfall bemessen können. Die Anzahl der Parameter ist gleichzeitig die Dimension unseres Vektorraums, den wir für unseren Algorithmus benötigen. Man spricht hier von einem N-Dimensionalen Vektorraum, wobei n die Dimension des Eingabevektors ist, den wir als x bezeichnen. Würden wir den Ausfall der Pumpe an drei Parametern festmachen, hätten wir einen Vektorraum mit n = 3. Haben wir mehrere Pumpen beobachtet, können wir diese in ein Koordinatensystem einzeichnen, dargestellt in der folgenden Abbildung.

k-nearest-neighbor klassifikation
Koordinatensystem eines zweidimensionalen Vektorraums

Die grünen Punkte symbolisieren hierbei Pumpen die nicht ausgefallen sind, die roten Punkte stehen für ausgefallene Pumpen. Betrachtet man die Verteilung der Punkte, fällt auf, dass Pumpen mit einer hohen durchschnittlichen Drehzahl und einer langen Laufzeit eher ausfallen, als Pumpen mit einer niedrigen durchschnittlichen Drehzahl. Der graue Punkt im Koordinatensystem symbolisiert die zu klassifizierende Pumpe. Wir möchten also herausfinden, ob es wahrscheinlich ist, dass die Pumpe ausfällt oder nicht. Um dies herauszufinden wird der Abstand zu den Punkten, die der Pumpe am nächsten sind, verwendet. Hier kommt der Buchstabe k des Algorithmus ins Spiel: k steht für die Anzahl der Nachbarn, welche in die Betrachtung mit einfließen. Wählen wir k = 1 ist nur der Punkt für die Klassifizierung unseres x verantwortlich, der x am nächsten ist. Wählen wir k = 3 bilden die drei Punkte, die k am nächsten sind die Basis der Klassifizierung. Würden wir in unserem Beispiel k =1 wählen, würde vorhergesagt, dass die Pumpe ausfällt, da der nächste Nachbar zu dieser Klasse gehört, dargestellt in der nächsten Abbildung.

Klassifikation mit einem k von eins

Bei k = 3 würde unser x zur Klasse „Pumpe in Ordnung“ gehören, zu sehen in der nächsten Abbildung. Bei der Auswahl wie groß k werden soll, müssen zwei Dinge beachtet werden. Zum einen darf k nicht zu klein, bspw. eins, gewählt werden, da Ausreißer sonst zu stark ins Gewicht fallen. Wie bei unserem Beispiel würde unser x als wahrscheinlicher Ausfall klassifiziert, obwohl die Klassifikation augenscheinlich nur auf einem Ausreißer basiert, der aus der Reihe ausgefallen ist. Neben einem zu kleinen k, darf k aber auch nicht zu groß gewählt werden. In unserem Beispiel haben wir 20 Beispiele von Pumpen, von denen elf ausgefallen sind und neun in Ordnung. Würden wir k = 20 wählen, würde unser x immer als wahrscheinlicher Ausfall klassifiziert werden, da elf der 20 Nachbarn zu dieser Klasse gehören.

Klassifikation mit einem k von drei

Zusammenfassend ist also darauf zu achten, ein k zu wählen, das weder zu groß noch zu klein ist. Um den Algorithmus anwenden zu können, müssen wir noch herausfinden wie der Abstand von x zu den anderen Punkten berechnet wird. Hierzu können mehrere Methoden verwendet werden, wir verwenden hiervon den euklidischen Abstand (Distanz).

Der euklidische Abstand

Die Formel des euklidischen Abstandssieht folgendermaßen aus:

Formel des euklidischen Abstands

Bezieht man die Formel auf unser Beispiel des Pumpenausfalls würden wir die Formel 20 mal anwenden, um den Abstand von jedem y zu unserem x zu bestimmen. Da wir den Ausfall unserer Pumpe an zwei Parametern festmachen, haben wir ein n von zwei, was zu folgender Formel für ein Beispiel führt:

Nun berechnen wir den Abstand von unserem x zu dem blau dargestellten y in unserem Koordinatensystem.

Abstand von x zu y

Da wir uns in einem zweidimensionalen Vektorraum befinden, haben unsere Vektoren die folgenden Parameter:

Unsere Pumpe x ist 5.000 Stunden gelaufen, und hatte dabei eine durchschnittliche Drehzahl von 1.660 Umdrehungen pro Minute, während die Pumpe y 6.300 Stunden mit einer Drehzahl von 1.820 im Betrieb war. Setzen wir diese Werte in die Formel ein, erhalten wir:

Der Abstand unserer beiden Punkte beträgt also 1.310. Würden wir den Ausfall der Pumpe an drei Parametern festmachen würde der dritte Parameter einfach in der Formel hinzugefügt werden. Auf diese Weise kann der Abstand aller Pumpen zu der Pumpe x berechnet werden, und diese dann mittels des KNN-Algorithmus klassifiziert werden. Hätten wir ein k von 3 würden die drei Punkte mit dem geringsten Abstand zu x darüber bestimmen, welcher Kategorie die Pumpe zugeordnet wird.

Zusammenfassend ist der KNN-Algorithmus eine sehr einfache Möglichkeit, um Daten zu klassifizieren. Es wird kein Training des Algorithmus benötigt, sondern die Daten können einfach klassifiziert werden. Man benötigt lediglich eine Methode, um die Abstände zwischen den Punkten berechnen zu können, bspw. den euklidischen Abstand. Weitere Machine Learning Methoden wie Decision Trees, Support Vector Machines werden in folgenden Artikeln behandelt.

Hier haben wir eine Übung (inklusive Lösungsweg) für euch erstellt. Damit könnt ihr testen, ob ihr verstanden habt wie man den KNN-Algorithmus anwendet und wie sich bspw. unterschiedliche k-Werte auf den Algorithmus auswirken.

Referenzen
Portrait of Blogger
Maximilian Both
<  Previous
Supervised, Unsupervised und Reinforcement Learning – Was bedeutet was?
Next  >
Übung k-Nearest-Neighbor

Kommentare