2.0 ­čÜž K-n├Ąchste-Nachbarn (K-NN) (k-nearest-neighbours)

  • Die Trainings-Daten werden in einem n-dimensionalen Vektorraum angeordnet und sind klassifiziert (Datenpunkte mit Klassifizierung, Label) -> ├╝berwachtes Lernen. Die Dimension n des Vektorraums ist die Anzahl der Attribute der Entit├Ąten, Beispiele:
    • Pflanzenbl├Ątter: (L├Ąnge,Breite)->Klassifizierung: Planzenart
    • Ausfall einer Pumpe: (Laufzeit,Durchschnittliche Drehzahl)->Klassifizierung: Kaputt? (ja,nein)
  • Um bei einem neuen Datenpunkt die Klassifizierung voraussagen zu k├Ânnen werden die k-n├Ąchsten Nachbarn im Vektorraum ermittelt (Distanzma├č, Metrik) und aus deren mehrheitlichen Klassifizierungen die wahrscheinliche Klassifizierung des Datenpunktes bestimmt. Die k n├Ąchsten Nachbarn bestimmen die Zugeh├Ârigkeit zur Klasse.

Lesen: https://www.tecislava.com/blog/k-nearest-neighbor­čöŚ Aufgabe machen: https://www.tecislava.com/blog/ubung-k-nearest-neighbor­čöŚ
Umfangreiche Beschreibung: [www.ibm.com/de-de/topics/knn ­čöŚ]

Weiterer m├Âglicher Einstieg mit dem Demonstrator: https://klassenkarte.de/index.php/ki/zum/­čöŚ

Sehr anschaulich mit Java-Programm

Auf der KI-Fortbildung hat uns Siegmar von Detten eine prima k-NN-Java-Visualisierung gezeigt, folgender Code wurde durch seine Software inspiriert.

Software f├╝r k-NN

Diese Software ist noch lange nicht “sch├Ân” nach meinem Empfinden, aber ich muss “liefern” damit ich dem Bildungsplan hinterher komme…

Der Code dient zu Unterrichtszwecken und soll “zwangsarm” verbessert werden k├Ânnen, daher unter CC BY-SA und nicht unter GPL lizensiert, bei GPL h├Ątten Ver├Ąnderungen dokumentiert werden m├╝ssen:

ToDo:

  • Zustands-L├Âsung f├╝r Oberfl├Ąche, Zustandsdiagramm.
  • Sauberes OOP-Klassendiagramm und SuS-Aufgaben zum Code: Sequenzdiagramme ­čźą..
  • Labels k├Ânnen String-Namen erhalten
  • Datenpunkte l├Âschen k├Ânnen
  • Daten normalisieren..
  • Testdaten durchrechnen lassen..

Begriffe und Einstellungen erkl├Ąrt

Laden Sie das Java-Programm und starten Sie es in Ihrer Entwicklungsumgebung, z.B. BlueJ.

Beim Start wird der Datensatz daten.csv geladen und angezeigt. Ich weis nicht was das f├╝r Daten sind. Ich behaupte einfach es sind die L├Ąngen und Breiten von Bl├╝tenbl├Ąttern und die Label geben die Pflanzenart an.

Wenn nun ein neues Bl├╝tenblatt bestimmt werden soll klickt man einfach auf die L├Ąnge-Breite-Position und die k-n├Ąchsten-Nachbarn (Datenpunkte) werden bestimmt (voreingestellt sind k=3 Nachbarn) und die Mehrheit dieser Labels bestimmt das Label f├╝r das neue Blatt.

Mit Maus folgen k├Ânnen die Nachbarn der Mausposition flie├čend beobachtet werden. Mit Datenpunktgr├Âsse kann die Darstellungsgr├Âsse der Datenpunkte ge├Ąndert werden.

Der Einfluss der Abstandsfunktion und des k-Werts wird nun beleuchtet.

2,0;2,0;1
5,0;6,0;1
7,0;8,0;1
5,0;2,0;1
4,0;2,0;1
3,0;1,0;1
10,0;10,0;2
13,0;9,0;2
13,0;4,0;3
12,0;5,0;4
15,0;1,0;4
15,0;7,0;3
13,0;8,0;3
12,0;2,0;4
10,1;3,9;4
10,0;2,0;4
12,0;1,0;4
3,0;9,0;6
2,0;8,0;6
k-NN daten.csv
k-NN daten.csv

Abstandsfunktionen, Distanzma├č, Metrik

Wie weit bin ich von einem anderen Punkt entfernt? Wie Nah ist mir ein Nachbar? Gibt es da Unterschiede?
Wie weit sind zwei Punkte in einem n-dimensionalen-Vektrorraum von einander entfernt?
Ich bin noch nicht aufgekl├Ąrt, welche der Distanzma├če die sinnvollste ist. Kann mir die Vielfalt der Distanzma├če nur durch den Rechenaufwand zur Bestimmung erkl├Ąren.

Luftlinie: Euklidische Distanz

Ich kann mich frei im Raum bewegen und die Entfernung ist die Luftlinie. Formel siehe Forsa.

Gerastert: Manhattan, Taxidistanz

Mit Hochh├Ąusern dazwischen kann ich nur auf Stra├čen im Raster gehen, Manhattan, Mannheim. Formel siehe Forsa.

Das Maximum der Distanzen der jeweiligen Dimension

Schau die in jeder Dimension (z.B. x,y,z) die Distanz darin an und nimm das Maximum.

Aufgabenmuster

Berechne zu verschieden Punktepaaren (n-Dimensionen) die jeweilige Distanz aus..

Den Wert von k ermitteln wie viele Nachbarn sollen es sein?

Toll: k=1 ist doof weil nur der n├Ąchste Nachbar z├Ąhlt, kann aber ein Ausrei├čer sein. Ein zu gro├čes k kann auch wieder falsche Aussagen liefern. Es wird empfohlen mit guten Testdaten die Vorhersage f├╝r verschiedene k zu ermitteln und dann den besten k-Wert zu w├Ąhlen.

Wichtige Begriffe des maschinellen Lernens

  • Gelabelte Daten, klassifizierte Daten: Gelabelte Daten sind Daten, die bereits einer Klasse zugeordnet sind.
  • Trainingsdaten: Gelabelte Daten, mit denen der Algorithmus trainiert wird.
    • Besonderheit: Beim k-n├Ąchste-Nachbarn Verfahren wird der Algorithmus nicht trainiert, die Trainingsdaten werden direkt zur Vorhersage der Klasse eines neuen Datenpunkts verwendet. Aus diesem Grund wird der Algorithmus auch als lazy learner bezeichnet.
  • Testdaten: Um eine Aussage ├╝ber die Qualit├Ąt des k-n├Ąchste-Nachbarn Verfahren machen zu k├Ânnen, muss der Algorithmus mit sogenannten Testdaten ├╝berpr├╝ft werden. Die Testdaten sind wie die Trainingsdaten gelabelt. F├╝r jeden einzelne Datenpunkt der Testdaten wird mit dem k-n├Ąchste-Nachbarn Verfahren eine Klasse, die Vorhersage, berechnet und diese mit dem Label an dem Testdatenpunkt verglichen. Stimmt die Vorhersage mit dem Label ├╝berein, so wurde der Testdatenpunkt richtig klassifiziert. Die Qualit├Ąt des k-n├Ąchste-Nachbarn Verfahren ist dann von der Fehlerquote der klassifizierten Testdaten abh├Ąngig.
  • Ausrei├čer: Ein Ausrei├čer ist ein Datenpunkt, der einer Klasse zugeordnet ist, die eigentlich nicht zu erwarten w├Ąre oder sehr ungew├Âhnlich ist. Ausrei├čer k├Ânnen z.B. durch Messfehler, fehlerhafte Daten, ungew├Âhnliche Ereignisse oder echte Abweichungen entstehen.

Ein Kommentar

Schreibe einen Kommentar

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