Kampis Elektroecke

Der k-NN als Einstieg in das maschinelle Lernen

In diesem Beispiel möchte ich (als Einstieg ins maschinelle Lernen) einen Klassifikationsalgorithmus vorstellen, der nicht direkt was mit “richtigem” lernen zu tun hat, den sogenannten k-Nearest Neighbors (k-nächste Nachbarn). Mit diesem Algorithmus soll eine Klassifikation von Lilienarten entwickelt und getestet werden.

Wie funktioniert der Algorithmus?:

Der k-NN Algorithmus bestimmt die Klasse des zu untersuchenden Elements mit Hilfe einer Abstandsbestimmung zwischen dem unbekannten und den trainierten Elementen. Dazu werden von den zu untersuchenden Elementen (in diesem Beispiel die Lilien) Eigenschaften definiert, wie z. B.:

  • Länge des Kelchblattes
  • Breite des Kelchblattes
  • Länge des Blütenblattes
  • Breite des Blütenblattes

Für die Trainingsdaten werden nun beliebig viele Blüten aufgenommen, die Werte der Merkmale und die zugehörige Art der Lilien bestimmt.

Die Werte der einzelnen Merkmale werden bei der Verwendung des k-NN Algorithmus in ein Koordinatensystem eingetragen, wobei jede Achse des Koordinatensystems einem Merkmal entspricht. Für die Lilie ergibt sich damit ein 4-dimensionales Koordinatensystem. Bei der Auswahl der Trainingsdaten ist es wichtig, dass die einzelnen Untergruppen (hier die Arten der Lilien) sehr gut anhand ihrer Merkmale getrennt werden können, damit der k-NN Algorithmus gute Ergebnisse erzielen kann. Ich habe das beispielhaft mal für zwei Merkmale geplottet:

Wie auf dem Bild zu erkennen ist, lässt sich die Art der Lilie sehr gut durch die Maße der Blütenblätter alleine bestimmen. Wenn sich die Merkmale so gut separieren lassen, kann ohne Probleme ein k-NN Algorithmus zur Klassifikation eingesetzt werden.

Auch hier noch einmal der Hinweis, dass es sich beim k-NN Algorithmus nicht um einen Lernalgorithmus, sondern um einen Klassifizierungsalgorithmus handelt, da der Algorithmus keine Gewichte o. ä. lernt! Weiterhin skaliert der Algorithmus nicht sehr gut mit multidimensionalen Daten und vielen Datenpunkten. Die Komplexität und Vorhersagezeit sind direkt abhängig von der Anzahl der Dimensionen und der, zum Training verwendeten, Datenpunkte. Bei Daten, welche nicht gut geclustert werden können (wie z. B. Bildern) ist der Algorithmus zudem auch noch sehr ungenau.

Umsetzung mit Scikit-learn und Python

Für die Umsetzung der Lösung werden als erstes einige Python-Pakete benötigt, die in das Python-Skript importiert werden müssen:

Das Paket scikit-learn bringt den benötigten Lilien-Datensatz bereits mit, weswegen er nur noch geladen werden muss:

Bei dem Datensatz handelt es sich um ein Objekt, welches einem Dictionary in Python sehr ähnlich ist. Die Daten sind unter dem Schlüssel data und die Label unter dem Schlüssel target als Werte von 0 – 2 gespeichert.

Beim maschinellen Lernen übergibt man die Label nie als Text, sondern codiert diese immer mit Zahlen von 0 bis N – 1, wobei N die Anzahl der verschiedenen Klassen darstellt. Durch dieses Vorgehen lässt sich die Geschwindigkeit des Trainings erhöhen. Da es in dem Lilien-Beispiel insgesamt drei Klassen gibt, werden die einzelnen Lilienarten mit den Labeln 0 bis 2 versehen. Später wird ein spezialisierter Labelencoder die Aufgabe mit dem codieren und decodieren der Label übernehmen, aber in diesem Beispiel ist die Zuordnung vorgegeben.

Unter dem Schlüssel target_names sind die Namen der einzelnen Werte für target in einem entsprechenden Array gespeichert. Index 0 ist dabei der Name für das Label 0, Index 1 der Name für das Label 1 und Index 2 der Name für das Label 2. Diese Information ist aber erst wichtig, wenn der Algorithmus ein Ergebnis für eine unbekannte Lilie geliefert hat, da dann mit dieser Information aus dem zurückgelieferten Label die Lilienart bestimmt werden kann.

Nach dem Laden der Daten speichere ich die Sektion mit den Daten und den Labeln des Dictionarys in einzelnen Variablen und teile die Daten im Anschluss in Trainings- und Verifikationsdaten auf.

Die Trainingsdaten sollen für das Training des k-NN Algorithmus verwendet werden. Mit den Verifikationsdaten möchte ich die Genauigkeit bzw. die Zuverlässigkeit des trainieren k-NN überprüfen. Dies ist ein übliches Vorgehen beim maschinellen Lernen. Üblicherweise werden eine beliebige Menge Daten aufgenommen und dann in Trainings- und Testdaten (hier Verifikationsdaten) unterteilt. Die Trainingsdaten werden beim Training eines neuronalen Netzes zudem noch einmal unterteilt. Mit dem einen Teil lernt das Netzwerk und der andere Teil wird vom Netzwerk zur Kontrolle genutzt. Da beim k-NN Algorithmus kein Lernen stattfindet, fallen die Kontrolldaten weg und es werden nur Trainingsdaten benötigt. 

Anschließend kann der k-NN Algorithmus auf die Trainingsdaten und die Trainingslabel angewendet werden:

Mit Hilfe der score()-Methode des KNeighborsClassifier()-Objektes kann der trainierte Algorithmus getestet werden. Dafür muss man der Methode lediglich ein paar Testdaten und Testlabel geben. Anschließend geht die Methode die Testdaten durch, sucht für jeden Datenpunkt in den Testdaten den nächsten Nachbarn und vergleicht das vorgegebene Label des Datenpunktes mit dem gefundenen Label. Der Rückgabewert entspricht der Genauigkeit des trainierten Modells:

Auf den Iris-Datensatz angewendet erreicht der k-NN Algorithmus eine Genauigkeit von etwa ~97%, was schon ein sehr gutes Ergebnis für eine einfache Klassifizierung ohne “richtiges Lernen” ist.

Im Vergleich dazu dann noch einmal der k-NN für eine unüberwachte Lernaufgabe…

Der k-NN Algorithmus zum unüberwachten Lernen

Mit Hilfe des k-NN Algorithmus kann nicht nur ein überwachtes Klassifizieren, sondern auch ein unüberwachtes Klassifizieren realisiert werden. Dazu nehme ich an, dass ich nur die Merkmale der Lilien kenne, nicht aber ihre Art. Da ich nun keinen Bezug mehr zu den Arten habe, kann mir der Algorithmus nicht die Art der unbekannten Lilie nennen, sondern nur die Ähnlichkeit zu einem bestimmten Trainingsdatenpunkt – als Trainingsdatenpunkt bezeichnet man sämtliche Merkmale, die zu einem bestimmten Objekt, hier also den Lilien, gehört.

Für dieses Beispiel wird der selbe Trainingsdatensatz wie beim überwachten Lernen verwendet und ein k-NN darauf angewendet:

Allerdings werden dieses Mal nur die Trainingsdaten ohne die dazu gehörigen Label in den NN Algorithmus gegeben. Anschließend kann der k-NN auf die Testdaten angewendet werden und die Genauigkeit überprüft werden, was auf Grund der fehlenden score()-Methode händisch gemacht werden muss:

Dazu werden alle Datenpunkte durchgearbeitet und zu jedem Datenpunkt der nächste Nachbar bestimmt. Von dem gefundenen Nachbarn wird das Label bestimmt und dann mit dem Label aus den Testlabeln verglichen. Falls die Label nicht übereinstimmen, wird ein Fehlerwert hochgezählt. Am Ende ergibt sich eine Genauigkeit von ~94%.

Das unüberwachte Lernen eignet sich hervoragend, wenn man verschiedene Datenpunkte hinsichtlich ihrer Ähnlichkeit untersuchen will. Dafür ist das Label der trainierten Datenpunkte nämlich nicht wichtig, da am Ende nur die Ähnlichkeit eines unbekannten Datenpunktes zu einem anderen (bekannten) Datenpunkt interessant ist.

Das Jupyter Notebook zu diesem Projekt steht in meinem GitLab-Repository zum Download bereit.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.