4.3 K-Nearest-Neighbor

Das Klassifikationsverfahren K-Nearest-Neighbor (KNN) ist ein sogenanntes instanzenbasiertes Verfahren, d. h. die Beispieldaten repräsentieren das Klassifikationswissen. Es wird kein Modell erstellt, das von den Beispieldaten abstrahiert. Bei der Klassifizierung neuer Datensätze werden die zu einer Instanz jeweils ähnlichsten Beispieldatensätze gesucht, eben die Nachbarn. Diejenige Klasse, die bei diesen Nachbarn am häufigsten auftritt, wird der Instanz zugeordnet. Die Ähnlichkeit zwischen zwei Instanzen wird durch Abstandsmaße berechnet, z. B. durch die Manhattan-, die Euklidische oder durch die Hamming Distanz, die allesamt auf den Abständen zwischen den Attributwerten der beiden Instanzen basieren.

Euklidische Distanz: $d i s t_{E} (v, w) = \sqrt{\sum i (v_{i} - w_{i})^{2}}$

Manhattan Distanz: $d i s t_{M a n} (v, w) = \sum i | v_{i} - w_{i} |$

Hamming Distanz: $d i s t_{H} (v, w) = c o u n t (v_{i} \neq w_{i})$ wobei jeweils $v_{i}$ , $w_{i}$ Attributwerte der beiden Instanzen $v, w$ sind.

In der Abbildung 4.7 ist das Verfahren für zweidimensionale Daten veranschaulicht. Die orangenen Kreise repräsentieren Instanzen der Klasse 1, die blauen Quadrate solche der Klasse 2. Der gestrichelt gezeichnete Kreis beinhaltet die nächsten Nachbarn der neuen, bisher nicht klassifizierten Instanz, visualisiert durch einen gelben Stern. Da vier der Instanzen der Klasse 2 (blaue Quadrate) angehören, und nur eine der Klasse 1 (orangener Kreis) gewinnt Klasse 2. Damit wird die neue Instanz der Klasse 2 zugeordnet. In diesem Beispiel ist die festgelegte Zahl der nächsten Nachbarn k=5.

Abbildung 4.7: Visualisierung des KNN Verfahrens

Der Algorithmus KNN kann wie folgt skizziert werden:

\begin{algorithm}
\caption{k-Nearest Neighbour}
\begin{algorithmic}
  \STATE Speichere jedes Trainingsbeispiel $t_i$ zusammen mit seiner Klasse:( $t_i$, $class(t_i) $)
  \STATE Klassifikationsschritt für zu klassifizierenden Datensatz y:
  \STATE Berechne die Ähnlichkeit von $y$ zu jedem Trainingsbeispiel $t_i$
  \STATE Wähle die $k$ Beispiele aus den Trainingsbeispielen, die $y$ am ähnlichsten sind
  \STATE Die zu $y$ gehörige Klasse $class(y)$ ist diejenige, die unter den $k$ ähnlichsten Trainingsbeispielen am häufigsten vorkommt
\end{algorithmic}
\end{algorithm}

KNN Übung 1

Gegeben seien die folgenden Daten, die zur Voraussage des Einkommensniveaus dienen sollen:

Abbildung 4.8: Beispieldaten für Übung

Nun soll ein neuer Datensatz eines 26-jährigen, verheirateten Akademikers ohne Eigenheim mit Hilfe des KNN Verfahrens mit k=2 eingeordnet werden. Berechnen Sie die Distanzen der 8 Datensätze zu dem neuen und legen Sie dementsprechend die Klasse des neuen Datensatzes fest.

Augenscheinlich fällt das Alter bei der Distanzberechnung sehr stark ins Gewicht, weil z. B. die Distanz der Werte des Attributs Alter zwischen dem neuen und dem ersten Datensatz 33 beträgt, während diese Distanz beim Attribut Eigenheim nur 1 beträgt. Dies bedeutet eine starke Ungleichgewichtung dieser beiden Attribute. Die ähnlichsten Datensätze können nur von Personen kommen, die nahezu gleich alt sind wie eine neu einzuordnende Person. Sollen die Attribute aber vergleichbar gewichtet werden, so ist eine Normalisierung der Abstände zwischen den Attributwerten angebracht.

KNN Übung 2

Normalisieren Sie das Attribut Alter in Abbildung 4.8 in das Einheitsintervall mit der Formel

$N_{m i n - m a x} = \frac{x - m i n (x)}{m a x (x) - m i n (x)}$

Berechnen Sie die Distanzen und legen Sie die Klasse des neuen Datensatzes fest.

Das KNN-Verfahren liefert oft recht gute Ergebnisse. Angenehm ist, dass es für quantitative und für qualitative Merkmale herangezogen werden kann. Bei quantitativen Merkmalen sollte als Distanzfunktion die Hamming-Distanz eingesetzt werden. Ein Nachteil des KNN-Verfahrens ist die aufwändige Klassifikationsphase. Denn für jeden neuen zu klassifizierenden Datensatz müssen alle Trainingsdaten herangezogen werden. Mit steigender Zahl von Datensätzen (sowohl Trainings- als auch Test oder zu klassifizierende Datensätze) wird das Verfahren langwierig. Außerdem liefert das Verfahren kein explizites Wissen über die Klassen, weil kein Modell erstellt wird.

Häufig wird gefragt, welches k, also welche Anzahl von nächsten Nachbarn, am besten geeignet sei. Natürlich lässt sich dies nicht exakt für jede Art von Daten sagen. Allerdings weiß man, dass k typischerweise kleiner als 10 und größer als 1 sein sollte. Ein zu großes k macht das Verfahren sehr aufwändig. Ein zu kleines k führt zu übermäßiger Sensitivität gegenüber Ausreißern.