Klassifizierungen mittels des K-Nearest-Neighbor-Klassifikators • Aggregata

Die Texte in diesem Artikel wurden teilweise mit Hilfe künstlicher Intelligenz erarbeitet und von uns korrigiert und überarbeitet. Für die Generierung wurden folgende Dienste verwendet:

Bing DeepL Write

Einordnung

Klassifikation stellt einen relevanten Aufgabenbereich innerhalb des maschinellen Lernens dar und des Supervised Learnings dar. In diesem Bereich sind vor allem Methoden wie beispielsweise Decision Trees oder Random Forests häufig vertreten. Hierneben existiert allerdings noch ein anderer Algorithmus: Der K-Nearest-Neighbor-Klassifikator.

k-Nearest-Neighbor wird häufig auch als kNN oder k-NN bezeichnet.

Dieser Blogbeitrag erklärt die Funktionsweise des Verfahrens, wie der Algorithmus Datenpunkte klasifiziert und wie man dieses Verfahren anwendet.

Grundlagen

Bei dem k-NN-Algorithmus handelt es sich um ein Verfahren aus der Klasse des Supervised Learnings. Die Grundidee des Verfahrens ist es, anhand der Datenpunkte aus dem Trainingsdatensatz und eines Abstandsmaßes die $k \in \mathbb{N}$ Nachbarn eines zu klassifizierendes Datenpunktes zu finden und mittels der Klassen der Nachbarn eine Klassfikation durch einen Mehrheitsentscheid durchzuführen. Hierbei geht der Algorithmus von der Annahme aus, dass ähnliche Daten üblicherweise in der Nähe gefunden werden können. Besonders an diesem Vorgehen ist, dass keine Trainingsphase notwendig ist. Die Daten des Trainingsdatensatzes werden einfach in den Algorithmus geladen, anstatt sie weiterzuverarbeiten und entsprechende Parameter (iterativ) zu berechnen zu müssen.

Da das Modell keine Trainingsphase und keine Parameter enthält, die durch ein Training berechnet werden müssen, wird dieses Verfahren auch als nichtparametrisches Verfahren bezeichnet.

k-NN gehört damit zu den “lazy learning”-Modellen, die Trainingsdaten nur speichern, anstatt diese zu verarbeiten und ein entsprechendes Training mit den Daten durchzuführen.

Durch die Eigenschaft, dass kein Training durchgeführt werden muss, ist die entsprechende Phase des Ladens der Daten entsprechend schnell. Das bedeutet allerdings auch, dass alle Berechnungen erst dann ausgeführt werden, wenn eine Vorhersage über eine Klasse gemacht werden muss. Dies ist vor allem problematisch bei großen Trainingsdatensätzen.

Bei großen Datensätzen kann eine Näherungsversion von k-NN verwendet werden, um die Rechenzeit geringfügig zu reduzieren. Dies geht mit einem geringen Genauigkeitsverlust einher, welcher jedoch in der Praxis allerdings akzeptiert werden kann. Viele spätere Versionen des Algorithmus, welche als Verbesserungen vorgestellt wurden, versuchen hauptsächlich die Anzahl der Evaluationen für das Distanzmaß zu reduzieren.

Grundsätzlich kann k-NN auch für Regressionsprobleme verwendet werden, dies wird hier allerdings nicht behandelt. Ein kurzer Einblick hierein kann hier gefunden werden. ¹ ²

Anwendungsbeispiele

Das k-NN-Verfahren wird häufig in den folgenden Bereichen angewandt:

Empfehlungssysteme
Mustererkennung
Data mining
Vorhersagen für den Finanzmarkt
Eindringlingserkennung

und viele weitere Anwendungsfelder.

Wählen der Parameter

Wahl der Distanz-Metrik

Da k-NN die $k$ nächsten Nachbar sucht, müssen diese auch gemessen werden können. Hierzu wird ein mathematisches Abstandsmaß verwendet. ² Durch diese Abstandsmaße können später Entscheidungsgrenzen erstellt werden für den gegebenen Trainingsdatensatz, die verschiedene Regionen unterschiedlichen Klassen zuordnet. ¹

Grundsätzlich existieren viele verschiedene Möglichkeiten, Abstandsmaße zu verwenden. Klassischerweise wird die euklidische-Norm (auch $2$ -Norm genannt) verwendet. Diese ist auf dem $m$ -dimensionalen Raum $\mathbb{R}^m$ wie folgt definiert:

${\Vert x \Vert}_2 := \sqrt{\sum_{i=1}^{m} x_i^2}.$

Eine Verallgemeinerung kann durch die $p$ -Normen erreicht werden:

${\Vert x \Vert}_p := \sqrt[p]{\sum_{i=1}^{m} \vert x_i \vert^p}.$

Hierbei wurde die $2$ von oben durch eine Zahl $p \in \mathbb{R}, \enspace p \geq 1$ ersetzt. Dies bietet den Vorteil, dass Zuordnungsregionen nach dem Abstand anders geformt sind. Dies kann in der Praxis Vorteile haben und wird meist durch Ausprobieren oder Erfahrung in Projekte eingeführt. Ein Beispiel dafür kann hier eingesehen werden.

Eine Liste möglicher Abstandsmaße kann hier gefunden werden.

Wahl von k

Wie viele andere Algorithmen des maschinellen Lernens hat auch dieser Algorithmus einen numerischen Parameter, welcher unsere Ergebnisqualität steuert. In diesem Fall ist es unser Parameter $k \in \mathbb{N}$ . Als einfaches Beispiel können wir den Einfluss wie folgt verstehen:

Für $k = 1$ wird die Klassifikation mit dem nächstegelegenen Punkt durchgeführt. Hier ergibt sich das Problem, dass zufälliges Rauschen oder Störungen in den Daten die Klassifikation verfälschen können.

$k = 1$ bezeichnet auch den Nearest-Neighbor-Algorithmus. Dieser leidet unter starken Instabilitätsproblemen und sollte - wenn möglich - vermieden werden.

Für $k \rightarrow \infty$ werden alle im Datensatz enthaltenen Punkte in die Mehrheitsentscheidung einbezogen. In diesem Beispiel wird das Ergebniss immer gleich sein; jeder Punkt (unabhängig von seinen Eingangsdaten) wird auf die Klasse abgebildet, welche am häufigsten im Datensatz vorkommt.

Es zeigt sich, dass die richtige Wahl von $k$ ein relevanter Faktor ist, welcher unsere Ergebnisse auf eine relevante Art beeinflusst. Die beste Wahl von $k$ ist von den Daten abhängig, welche gegeben sind. In der Praxis wird das “optimale” $k$ mittels heuristische Methoden wie einer Hyperparameteroptimierung oder durch Verwendung von Bootstrapping bestimmt. ² ¹

Es ist ratsam, $k$ ungerade zu wählen. Damit wird vermieden, dass zwei Klassen in der Mehrheitsentscheidung ein Unentschieden erreichen. Dies ist vor allem bei binären Klassifikationsproblemen (mit lediglich zwei Klassen) ein relevanter Faktor. Hiermit wird die Situation eines “Unentschiedens” im Mehrheitsentscheid reduziert oder komplett vermieden.

Es wird empfohlen $k$ nicht zu klein zu wählen (Overfitting), da sonst die Klasenzuteilung bei kleinen Änderungen in den Eingangsdaten stark schwanken kann.

Es wird empfohlen $k$ nicht zu groß zu wählen (Underfitting), da sonst zufälliges Hintergrundrauschen aus den Daten übernommen wird.

Beispielhafte Ergebnisse einer k-NN-Implementierung ergab folgende Genauigkeiten bei dem Datensatz imbd-reviews:

Auch wenn es sich hier nur um ein einfaches Beispiel handelt, kann man erkennen, dass der Parameter $k$ einen Einfluss auf die Genauigkeit des Algorithmus hat.

Vor- und Nachteile des Algorithmus

Vorteile

Der k-NN-Algorithmus bietet eine Reihe von Vorteilen: ¹ ² ³ ⁴

Einfache Implementierung: Die Idee hinter diesem Algorithmus ist sehr einfach und erfordert kaum Vorkenntnisse im Bereich des maschinellen Lernens oder der Mathematik. Gepaart mit der Eigenschaft dass k-NN vergleichsweise gute Ergebnisse liefert ist dies ein guter Algorithmus um mit Klassifikation mittels klassischer “Machine Learning”-Algorithmen zu beginnen.
Änderungen in den Daten sind schnell möglich, da der Algorithmus keine Trainingsphase benötigt.
k-NN benötigt lediglich den $k$ -Parameter als relevanten Hyperparameter und eine Abstandsmetrik welche gewählt werden müssen. Dies ist vor allem im Vergleich mit den neuronalen Netzen eine sehr geringe Anzahl und lässt sich bei Bedarf auch relativ schnell ausprobieren.
Theoretisch ist k-NN ein sehr genauer Algorithmus. Wenn die Datenmenge gegen unendlich strebt, kann theoretisch gezeigt werden dass eine sehr kleine Fehlerrate erreicht werden kann. ²

Nachteile

Der k-NN-Algorithmus hat eine Reihe von praxisrelevanten Nachteilen: ¹ ² ³ ⁴

Da k-NN keine Trainingsphase aufweist, skaliert der Algorithmus sehr schlecht und benötigt entsprechend mehr Arbeitsspeicher und CPU-Resourcen. Dies macht sich insbesondere bei großen Datensätzen schnell bemerkbar.

Grundsätzlich wurde dieses Problem durch veränderte Datenstrukturen wie Ball-Tree verbessert. Trotzdem sollte bei größeren Datensätzen - je nach von der Anwendung - eher auf andere Algorithmen ausgewichen werden.

Wie viele andere “Machine Learning”-Algorithmen leidet auch k-NN unter dem Fluch der Dimensionalität. Große Dimensionen in den Eingangsdaten verzerren die Performance des Algorithmus (unter Umständen stark).

Um dieses Problem zu reduzieren kann in der Preprocessing-Phase eine Dimensionsreduktion durchgeführt werden, um Eingangsparameter mit geringer Wichtigkeit auszusortieren und nicht weiter zu betrachten. Hierbei handelt es sich um ein Vergleichsszenario zwischen Geschwindigkeit des Algoithmus (weniger Parameter) gegen dessen Genauigkeit (mehr Parameter), da durch das auszusortieren häufig aus dem Datensatz entfernt werden.

Ebenso häufig in verschiedenen anderen Algorithmen kommt auch hier das Problem des Overfittings oder Underfittings zum Tragen, wenn $k$ falsch gewählt wird oder der Datensatz zu klein gewählt ist.
Ist in dem Trainingsdatensatz eine Klasse besonders häufig vertreten, kann dies die Genauigkeit des Algorithmus stark verzerren. Dies liegt daran, dass es unter Umständen vorkommen kann, dass entsprechende Datenpunkte der Klasse (wenn diese ein gewisses Rauschen in den Daten besitzen), häufig über den Raum der Datenpunkte vorkommen und somit häufiger einen Nachbarn bilden.

Eine relativ einfache Lösung hierfür ist es, eine gewichteten Mehrheitsentscheid zu verwenden, welcher die Distanz zu den umliegenden Nachbarn mit einbezieht.

Dadurch das hier ein “lazy loading”-Modell vorliegt, können Vorhersagen für verschiedene Datenpunkte lange dauern, bis diese abgeschlossen sind. Dieses Problem verstärkt sich mit zunehmend großem Trainingsdatensatz.