k-Nächste-Nachbarn-Algorithmus einfach erklärt

Beim überwachten Lernen bekommt ein Lernalgorithmus Datensätze, die zu jeder Eingabe einen passenden Ausgabewert enthalten. Solche Datensätze heißen markiert oder gelabelt. Ein Label ist also die bekannte richtige Antwort, zum Beispiel „Katze“ oder „Hund“ bei einem Bild.

kNN ist ein Klassifikationsverfahren. Das heißt: Es ordnet ein neues Objekt einer Klasse zu, zum Beispiel „Spam“ oder „kein Spam“. Dafür berücksichtigt es die k nächsten Nachbarn des neuen Objekts. Das sind die k nächsten Trainingsbeispiele, deren Klasse schon bekannt ist.

Das Lernen ist bei kNN sehr einfach: Es besteht aus simplem Abspeichern der Trainingsbeispiele. Das nennt man auch „lazy learning“ („träges Lernen“).

Um die Nähe zu messen, braucht man einen Abstand. Der euklidische Abstand zweier Punkte in der Ebene ist die Länge der Strecke, die sie verbindet, zum Beispiel mit einem Lineal gemessen. Mit Koordinaten rechnest du ihn mit dem Satz des Pythagoras: Du bildest die Unterschiede der beiden Koordinaten, quadrierst sie, addierst und ziehst die Wurzel. Es sind auch andere Abstandsmaße denkbar.

Für A = (a₁, a₂) und B = (b₁, b₂) gilt: d(A, B) = √((b₁ − a₁)² + (b₂ − a₂)²). Bei mehr Merkmalen kommt für jedes Merkmal ein weiterer Summand dazu.

So gehst du vor: Berechne den Abstand des neuen Punktes zu allen Trainingspunkten. Wähle die k Punkte mit den kleinsten Abständen. Zähle ihre Klassen. Der neue Punkt bekommt die Klasse, die unter diesen k Nachbarn am häufigsten vorkommt. Das ist die Mehrheitsentscheidung. Bei zwei Klassen kann ein ungerades k ein Unentschieden verhindern.

Ist k klein gewählt, besteht die Gefahr, dass Rauschen in den Trainingsdaten die Klassifikationsergebnisse auf den Testdaten verschlechtert. Mit Rauschen sind einzelne ungewöhnliche oder fehlerhafte Datenpunkte gemeint. Bei k = 1 zählt nur der allernächste Nachbar.

Wird k zu groß gewählt, besteht die Gefahr, Punkte mit großem Abstand zum neuen Punkt in die Entscheidung einzubeziehen. Diese Gefahr ist insbesondere groß, wenn die Trainingsdaten nicht gleichverteilt vorliegen oder nur wenige Beispiele vorhanden sind. Bei nicht gleichmäßig verteilten Trainingsdaten kann man eine gewichtete Abstandsfunktion verwenden. Sie gibt näheren Punkten ein höheres Gewicht als weiter entfernten.

Zur Normalisierung: Merkmale mit einem kontinuierlichen Wertebereich werden in der Regel auf den Wertebereich zwischen 0 und 1 normalisiert. Kontinuierlich heißt: Die Werte können beliebige Zahlen in einem Bereich sein, zum Beispiel Längen. Man macht das, damit der Algorithmus Merkmale mit großen und mit kleinen Zahlenwerten gleich stark gewichtet. Eine Datennormalisierung kann die Genauigkeit von kNN erhöhen. Das ist keine Garantie.

Ausgedachtes Beispiel: Ein Merkmal hat Werte um 170 (Körpergröße in Zentimetern), ein anderes Werte von 1 bis 6 (Schulnote). Die Zahlen sind sehr verschieden groß. Nach der Normalisierung liegen beide zwischen 0 und 1.

Um ein Verfahren fair zu bewerten, teilt man den Datensatz auf. Bei der Holdout-Methode gibt es einen Trainingsdatensatz, mit dem das System trainiert wird. Es gibt einen Testdatensatz, mit dem nach dem Training die Vorhersagequalität für unbekannte Daten überprüft wird. Und es gibt ein oder mehrere Validierungsdatensätze, falls eine Hyperparameteroptimierung geplant ist. Hyperparameter sind Einstellungen, mit denen man den Lernvorgang an die Aufgabe anpasst. Mit den Validierungsdaten prüft man, welche Einstellung gut passt. Die Testdaten trennt man vorher ab. Training und Test sollten dieselbe Verteilung der Daten repräsentieren.

Allgemein beim Lernen mit Beispieldaten kann man solche Einstellungen mit Validierungsdaten vergleichen. Das ist hier ein allgemeines Vorgehen, keine besondere Regel für kNN.

Warum nicht einfach mit den Trainingsdaten prüfen? Ein überangepasstes Modell gibt die Trainingsdaten korrekt wieder, weil es sie sozusagen „auswendig gelernt“ hat. Auf neuen Daten verallgemeinert es dann nicht mehr. Steigt der Fehler auf den Testdaten, während der Fehler auf den Trainingsdaten fällt, liegt möglicherweise eine Überanpassung vor.