inf-schule | K-Nächste-Nachbar-Klassifikation: Einführung

Abstandsmaß

Bisher haben wir die nächsten Nachbarn graphisch bestimmt. Die graphische Bestimmung ist ungenau und im Fall von mehr als zwei erklärenden Attributen auch schwieriger oder gar nicht mehr möglich (siehe Abschnitt 'Erweiterung der Attribute'). Daher ist es notwendig, dass wir ein Abstandsmaß zwischen zwei Punkten festlegen. Dafür gibt es viele Möglichkeiten. Wir beschränken uns hier auf den (gewichteten) euklidischen Abstand, den du bereits aus dem Mathematikunterricht kennen solltest.

Euklidischer Abstand (2D)

Der euklidische Abstand zweier Punkte A und B entspricht im zweidimensionalen der Länge der Strecke AB zwischen den beiden Punkten. Diese berechnet über den Satz des Pythagoras als $$AB = \sqrt{AC^2 + BC^2} $$
In unserem Beispiel haben die Punkte $$A = (5,3)$$ und $$B = (8,7)$$ damit einen Abstand von $$AB = \sqrt{(8-5)^2 + (7-3)^2} = 5 $$.

Betrachten wir das Einführungsbeispiel:

Für unser Beispiel bedeutet das $$Abstand = \sqrt{(gepl.Reisezeit1 - gepl.Reisezeit2)^2 + (gepl. Umstiegszeit1 - gepl.Umstiegszeit2)^2} $$

Aufgabe 1 - Abstandsberechnungen

Im obigen Punktdiagramm die Daten mehrerer Verbindung angegeben.

Berechne den nächsten Nachbarn für die blaue Verbindung mittels des euklidischen Abstands.
Vergleiche deine Ergebnisse mit den Abständen im Punktdiagramm.

Gewichteter euklidischer Abstand (2D)

Da die x-Achse und die y-Achse im Punktdiagramm nicht gleich skaliert wurden, unterscheidet sich der Eindruck des Abstands im Punktdiagramm von den berechneten euklidischen Distanzen zwischen den Punkten. Eine Minute Umstiegszeit entspricht graphisch nicht gleich einer Minute Reisezeit. Im Hinblick auf die betrachteten Attribute scheint dies sinnvoll zu sein. Betrachten wir folgendes Beispiel:
Dein Zug mit einer geplanten Reisezeit von 60 Minuten und einer geplanten kürzesten Umstiegszeit von 7 Minuten fällt aus. Du hast nun die Auswahl zwischen

einem Zug mit einer geplanten Reisezeit von 65 Minuten und ebenfalls 7 Minuten Umstiegszeit oder
einem Zug mit einer geplanten Reisezeit von ebenfalls 60 Minuten aber einer geplanten kürzesten Umstiegszeit von 2 Minuten.

Du würdest vermuten, dass du mit dem ersten Zug sicherer pünktlich ankommst als mit dem zweiten.

Aufgrund dessen ordnen wir den Attributen verschiedene Gewichte zu, die bei der Berechnung des euklidischen Abstands beachtet werden. Diese Gewichte passen wir an die Skalierung des Punktdiagramms an und wählen daher die folgende Gewichtung: 1 Minute Umstiegszeit entspricht 10 Minuten Reisezeit.

Aufgabe 2 - Gewichtung

Finde heraus, woran du die genannte Gewichtung im obigen Punktdiagramm erkennen kannst.

Für unser Beispiel ergibt sich daraus die Formel $$Abstand = \sqrt{\left(\frac{gepl.Reisezeit1 - gepl.Reisezeit2}{10}\right)^2 + \left(\frac{gepl. Umstiegszeit1 - gepl.Umstiegszeit2}{1}\right)^2} $$

Aufgabe 3 - Erneute Abstandsberechnungen

Berechne den nächsten Nachbarn für die blaue Verbindung mittels des gewichteten euklidischen Abstands.
Vergleiche deine Ergebnisse mit den Abständen im Punktdiagramm und den Ergebnissen aus Aufgabe 1.