Skip to content

K-Nearest-Neighbors

Künstliche Intelligenz (modern)

Als Beispiel für supervised learning schauen wir uns den ML-Algorithmus k-nearest-neighbors an.

Problem ​

Pilzsammler Heinz-Wilhelm kommt vom Pilzsammeln aus dem Böhmerwald nach Hause. Er hat 14 Stück gefunden und möchte diese überprüfen lassen. Also bringt er sie zum Pilzkontrolleur nach Bad Leonfelden. Dieser schaut sich die Pilze an und findet unter den 14 Exemplaren 7 essbare Wiesenchampignons, 6 giftige Karbolchampignons und sogar einen tödlichen Grünen Knollenblätterpilz!

Wiesenchampignons[1]
Karbolchampignons[2]
Grüner Knollenblätter[3]

Heinz-Wilhelm möchte nicht immer zum Kontrolleur und informiert sich, wie man die Pilze voneinander unterscheiden kann: Sie unterscheiden sich primär in der Farbe der Lamellen. Weitere Merkmale sind Fleischverfärbungen und Geruchsunterschiede.

Heinz-Wilhelm macht sich an die Arbeit und baut ein Pilzsortiermaschine.

Merkmale ​

Die Sortiermaschine, die Heinz-Wilhelm gebaut hat, untersucht die Farbe der Lamellen und die Fleischverfärbung und liefert zwei Zahlenwerte zurück. Heinz-Wilhelm erhält für die 14 kontrollierten Pilze die folgenden Werte:

PilzLamellenFleischSorteGeniessbarkeit
A12Karbolchampignongiftig
B0.53Karbolchampignongiftig
C1.254Karbolchampignongiftig
D2.31.75Karbolchampignongiftig
E12.3Karbolchampignongiftig
F2.53.1Karbolchampignongiftig
G1.56Knollenblättergiftig
H5.57Wiesenchampignonsessbar
I65.5Wiesenchampignonsessbar
J5.57.25Wiesenchampignonsessbar
K4.56.75Wiesenchampignonsessbar
L4.56.25Wiesenchampignonsessbar
M4.756.5Wiesenchampignonsessbar
N5.17.5Wiesenchampignonsessbar

Heinz-Wilhelm zeichnet die gemessenen Werte in einem Koordinatensystem auf. Er markiert die essbaren Champignons mit grüner Farbe und die ungeniessbaren und giftigen Pilze mit roter Farbe.

Messwerte im Koordinatensystem

Aufgabe

Können anhand dieser Merkmale die Pilze gut dem richtigen Typ zugeordnet werden?

Visualisierung ​

Jeder Pilz kann als Punkt in einem Koordinatensystem dargestellt werden. Dabei ist die x-Koordinate der Lamellenwert des Pilzes, die y-Koordinate ist der Fleischwert. Die Kategorie des Pilzes wird durch die Farbe des Punktes dargestellt.

Diese Methode funktioniert auch, wenn mehr als zwei Merkmale gemessen werden. Bei n Merkmalen wird ein n-dimensionales Koordinatensystem verwendet.

Die Daten können bequem in Excel visualisiert werden. In der untenstehenden Excel-Datei können die Daten der Pilze auf dem Arbeitsblatt «Klassifikation» oder «Training Dateneingabe» erfasst werden.

Sie werden automatisch im Diagramm auf dem Arbeitsblatt «Klassifikation» dargestellt.

Es liegen zwei Varianten vor: In der oberen Variante werden die Pilze nach essbar/nicht essbar klassifiziert, in der unteren nach ihrer Sorte.

Anwendung ​

Die oben genannten Punkte stellen unsere Trainingsdaten dar. Was geschieht jetzt, wenn wir einen neuen Punkt erhalten? Wie kann dieser möglichst klar einer der beiden Kategorien zugeordnet werden?

Aufgabe: neue Pilze

Er findet zwei weitere Pilze und misst diese: Kannst du die Werte für Heinz-Wilhelm hinzufügen und blau darstellen?

PilzLamellenFleischSorteGeniessbarkeit
X23????
Y3.54.5????

Zu welcher Kategorie würdest du die neuen Pilze zählen? geniessbar oder giftig?

im Arbeitsblatt «Klassifikation» können unter «Neuer Datensatz» die Daten eines neuen Pilzes eingegeben werden. Dieser wird im Diagramm gelb dargestellt.

k-nearest-neighbors ​

Der k-nearest-neighbors-Algorithmus ist ein Klassifikationsalgorithmus. Er kann für Probleme wie z.B. die Klassifikation der beiden neuen Pilze bei Heinz-Wilhelm eingesetzt werden.

Definition: k-nearest-neighbors

Der k-nearest-neighbors-Algorithmus klassifiziert einen neuen Datensatz a, welcher durch Merkmale a1,a2,…,an beschrieben wird, anhand der k bereits klassifizierten Datensätze (der Trainingsdaten), die ihm am nächsten liegen, also den kleinsten Abstand zu d haben.

Als Abstand wird üblicherweise der euklidische Abstand verwendet. D.h. der Abstand zwischen dem Datensatz a und dem Datensatz b mit den Merkmalen b1,b2,…,bn beträgt

(b1−a1)2+(b2−a2)2+⋯+(bn−an)2

Die Kategorie von a ergibt sich aus der Mehrheitsentscheidung dieser k Nachbarn: Der Datensatz wird jenem Label zugeordnet, das am häufigsten unter seinen nächsten Nachbarn vorkommt.

Lösung: Abstand berechnen

In der Ebene geht das einfach mit Pythagoras:

d(A,B)=(a1−b1)2+(a2−b2)2

Dieser sogenannte Euklidische Abstand lässt sich auch im Raum berechnen:

d(P,Q)=(p1−q1)2+(p2−q2)2+(p3−q3)2

Aufgabe: Klassifizierung

In Excel wird die Klassifizierung automatisch gemacht. Unter «Berechnung ganzer Datensatz» werden die Abstände aller Trainingsdaten zum neuen Datensatz berechnet und diese aufsteigend nummeriert (Rang).

Bestimmung des Parameters k – Allgemein[4] ​

Der Hyperparameter k legt fest, wie viele Nachbarn eines zu klassifizierenden
Datenpunkts für die Klassifikation – also die Einordnung in eine Klasse –
herangezogen werden. Die Wahl von k ist damit von zentraler Bedeutung für den
k-nächste-Nachbarn-Algorithmus. Der passende Wert wird in der Regel nicht zufällig
gewählt, sondern anhand von Validierungsdaten bestimmt.

Definition: Verfahren kurz gefasst

Die Validierungsdatenpunkte werden der Reihe nach für verschiedene Werte von k
mit Hilfe der Trainingsdaten klassifiziert. Danach wird geprüft, für welche Werte
von k der aktuell betrachtete Validierungsdatenpunkt korrekt klassifiziert
wurde. Dieses Vorgehen wird für alle Validierungsdaten sukzessive durchgeführt.
Die Werte für k, welche am häufigsten zu einer korrekten Klassifikation geführt
haben, sind unsere Kandidaten für den Parameter k.

Situation ​

In der Tabelle Bestimmung k_Allgemein der Excel-Arbeitsmappe werden die
eingegebenen Trainingsdaten automatisch in Trainings- und Validierungsdaten
aufgeteilt. Die aufgeteilten Daten werden links in den jeweiligen Bereichen
angezeigt.

Vorgehen ​

  1. Auswahl des aktuellen Validierungsdatenpunkts:
    Wähle einen Validierungsdatenpunkt aus den Validierungsdaten aus und trage
    ihn beim «Aktuellen Validierungsdatenpunkt» ein. Dabei müssen lediglich die
    Werte für die Merkmale Lamellen und Fleisch eingetragen werden. Wird der
    eingetragene Datenpunkt in den Validierungsdaten gefunden, wird das erwartete
    Label automatisch übernommen und der entsprechende Punkt hervorgehoben.

  2. Ablesen der Klassifikation für verschiedene Werte von k:
    Die Tabelle klassifiziert den eingetragenen Validierungsdatenpunkt automatisch
    für k=1,…,10 und vergleicht das berechnete Label mit dem erwarteten
    Label des Datenpunkts. Direkt angezeigt wird auch, ob die Klassifikation für
    einen Wert von k korrekt war – ob also das berechnete Label mit dem
    erwarteten Label übereinstimmt.

    Die Einträge im Bereich «Label k-ter Nachbar» stellen das Label des jeweils
    k-ten Nachbarn des betrachteten Validierungsdatenpunkts dar. So ist
    nachvollziehbar, wie das Modell auf die Klassifikation für den jeweiligen Wert
    von k kommt.

    Aufgabe

    Welches Ergebnis liefert die Tabelle für den Pilz mit den Werten (4.5, 6.75)?
    Für welche Werte von k wurde er korrekt klassifiziert?

  3. Eintragen des Klassifikationsergebnisses:
    Trage im Bereich «Bestimmung eines passenden Werts k» für jene Werte von k
    ein X ein, für die die Klassifikation korrekt war. Führe dieses Vorgehen für
    alle Validierungsdatenpunkte durch.

  4. Ablesen der besten Werte für k:
    In der Zeile «Korrekt» wird prozentual dargestellt, wie viele
    Validierungsdatenpunkte für die jeweiligen Werte von k korrekt vorhergesagt
    wurden. Die Werte von k mit dem höchsten Prozentsatz sind unsere Kandidaten
    für k.

Hinweis

Im rechten, oberen Bereich der Tabelle werden Informationen zu den 10 nächsten
Nachbarn des aktuell betrachteten Validierungsdatenpunkts angezeigt. Diese dienen
lediglich der zusätzlichen Information und haben keine direkte Bedeutung für die
Bestimmung der Kandidaten für den Parameter k.

Testen des trainierten Modells (Konfusionsmatrix)[5] ​

Nachdem ein Modell mit maschinellen Lernen trainiert wurde, muss die Güte des
Modells geprüft werden, bevor es eingesetzt werden kann. Das Testen ist neben
dem Training der zweite große Bestandteil des maschinellen Lernprozesses.

Definition: Verfahren kurz gefasst

Eine Menge an Testdaten wird mit Hilfe des trainierten Modells klassifiziert und
die erwarteten Label der Testdaten werden mit den vom Modell berechneten Label
verglichen. Die Ergebnisse dieser Vergleiche lassen sich in Form einer
Konfusionsmatrix übersichtlich darstellen.

Aus der Konfusionsmatrix kann die Genauigkeit (accuracy) des Modells berechnet
werden: Die Anzahl der korrekt klassifizierten Testdaten, dividiert durch die
Anzahl aller Testdaten.

Situation ​

In der Tabelle Testen_Konfusionsmatrix werden links die Testdaten angezeigt.
Diese kannst du beliebig verändern. Achte dabei aber darauf, dass du als
erwartetes Label nur Label aus den bei den Trainingsdaten zugelassenen Label
verwendest (Karbolchampignon, Knollenblaetter, Wiesenchampignon).

Vorgehen ​

  1. Eingabe des Parameters k:
    Gib neben der Zelle «Parameter k» den gewünschten Wert für k ein. Es werden
    nur ganzzahlige Werte von 1 bis 10 unterstützt.

  2. Auswahl des aktuellen Testdatenpunkts:
    Wähle einen Testdatenpunkt aus den Testdaten aus und trage ihn beim «Aktuellen
    Testdatensatz» ein. Dabei müssen lediglich die Werte für die Merkmale
    Lamellen und Fleisch eingetragen werden. Wird der Testdatenpunkt in den
    Testdaten gefunden, wird das erwartete Label automatisch übernommen und der
    entsprechende Datenpunkt hervorgehoben.

  3. Vergleich berechnetes Label – erwartetes Label und Eintragung in die Konfusionsmatrix:
    Vergleiche den Eintrag neben «Berechnetes Label» mit dem Eintrag neben
    «Erwartetes Label». Erhöhe den zugehörigen Eintrag in der Konfusionsmatrix
    um 1 – die Zelle ergibt sich aus dem erwarteten Label (Zeile) und dem
    berechneten Label (Spalte).

    Führe dieses Vorgehen für alle Testdatenpunkte durch.

  4. Ablesen der Genauigkeit:
    Die Genauigkeit des trainierten Modells für die Testdaten wird automatisch
    berechnet und in der Zelle «Genauigkeit» angezeigt.

Hinweis

Im rechten Bereich der Tabelle werden zusätzliche Informationen zu den
Trainingsdaten, den zum aktuellen Testdatenpunkt k nächsten Nachbarn sowie
eine graphische Darstellung der k nächsten Nachbarn angezeigt. Diese sind für
das Testen nicht direkt notwendig und dienen nur der zusätzlichen Information.

Aufgabe

Teste das Modell mit den beiden neuen Pilzen (2, 3) und (3.5, 4.5) für
k=3. Wie groß ist die Genauigkeit? Was würde ein Eintrag außerhalb der
Diagonale der Konfusionsmatrix bedeuten?

Weitere Beispiele ​


  1. Andreas Kunze via Wikimedia Commons (CC BY-SA 3.0) ↩︎

  2. James Lindsey at Ecology of Commanster via Wikimedia Commons (CC BY-SA 2.5) ↩︎

  3. Ak ccm via Wikimedia Commons (CC BY-SA 3.0) ↩︎

  4. Didaktik der Informatik, Universität Passau ↩︎

  5. Didaktik der Informatik, Universität Passau ↩︎

Gymnasium Kirchenfeld, fts & ros