KNN - Theorie

2. AbstandsMetriken

Um zu ermitteln, welche Datenpunkte diesem unbekannten (noch nicht klassifizierten Punkt) am nächsten liegen, muss der Abstand zwischen diesen Punkten berechnet werden. 

Aber Achtung!⚠️ Abstand ist nicht gleich Abstand! 

Es gibt unterschiedliche sogenannten Abstandsmetriken. Das bedeutet,  Distanzen können unterschiedlich berechnet werden. 

Im Folgenden, werden 2 unterschiedliche Abstandsmetriken vorgestellt. Die Dimension, in welcher der Abstand berechnet wird, bezeichnet die Anzahl features, die wir in unserem Modell mit einberechnen wollen. 

1. Euklidischer Abstand 

Der euklidische Abstand zwischen zwei Punkten  berechnen  wir intuitiv richtig. 

Wenn wir zwei Punkte auf einer Ebene oder im dreidimensionalen Raum durch eine Gerade miteinander verbinden, dann ist die euklidische Distanz nichts anderes als die Länge dieser Gerade zwischen den zwei Punkten. 

Bei n-Dimensionen können wir diese Distanz zwar anschaulich nicht mehr zeigen, jedoch gilt die folgende allgemeine Form des euklidischen Abstands weiterhin: 

2. Manhattan Abstand (auch Taxi-Abstand)

Die Manhattan-Metrik weist allen Distanzen zwischen zwei Punkten die Summe der absoluten Differenzen ihrer Einzelkoordinaten zu. Wege zwischen Elementen ähneln hier den kürzesten Strecken, die ein Taxifahrer im Straßengitter New Yorks zurücklegt.

3. k-Nachbarn

Der k-Wert im KNN-Algorithmus legt fest, wie viele Nachbarn geprüft werden, um die Klassifizierung zu bestimmen. 

Wenn beispielsweise k = 1 ist, wird die Instanz der gleichen Klasse zugeordnet wie ihr einziger nächster Nachbar.

Wie man k festlegt, ist nicht ganz einfach. Je nach Wert von k, kann es zu einer Über- oder Unteranpassung führen (Under- oder Overfitting). 

Die Auswahl von k hängt weitgehend von den Eingabedaten ab. Insgesamt ist es empfehlenswert, eine ungerade Zahl für k zu wählen, um „Unentschieden" in der Klassifizierung zu vermeiden.

Unter den k Nachbarn, werden die Klassen gezählt, welche dort vorkommen. Dem unbekannten Punkt wird dann der Klasse zugewiesen, welche am häufigsten vorkommt.