This is an old revision of the document!
k Nearest Neighbors
Bemerkungen
- Die untenstehenden Codes sind für TigerJython gedacht
- Die Codes sind nicht unbedingt schnell sondern illustrativ
- Es werden folgende Daten benötigt:
- {kurse:efcomputergrafik:knn:knn_r2_trainingsdaten.zip|Trainingsdate}} für zweidimensionales kNN
- Testdaten für zweidimensionales kNN
- ZIP-Code Daten
- Training: Bilddateien als ZIP
- Test: Bilddateien als ZIP
- (Optional) Training als CSV
- (Optional) Test als CSV
Einführung
Ziel
Den $k$-nearest-neighbour Algorithmus in $\mathbb{R}^2$ implementieren.
Wichtige Zutaten
- Liste mit Distanzen und Klassen, i.e.
[[1,0.033131],[0,0.123131],[1,0.123124141],[0,1.2123141]]
- Sortieren dieser Liste um die $k$ nächsten Nachbarn resp. deren Klasse zu bestimmen:
- Sortieren von Listen kann mit Python mit sorted gelöst werden. Speziell für unseren Fall ist “Example 3” spannend.
- Auf Grund der sortierted Liste kann die Mehrheitsmeinung der $k$ nächsten Nachbarn bestimmt werden
Empfehlung: Mindestens zwei Funktionen definieren. Eine zur Berechnugn der Distanz-Klassen-Liste, eine zur Zuweisung der Klasse (0 oder 1).
Die Daten finden sich in einer neuen ZIP-Datein
Ziffern als Pixellisten
Ziele
- Klassifizierungsfehler auf Testdaten für verschiedene $k$ berechnen und Tabelle erstellen.
- ZIP-Code Problematik verstehen: ZIP-Code → Ziffer → 16×16 Bild → Liste mit 256 Graustufen-Werten → kNN in $\mathbb{R}^{256}$.
- Einzelne Ziffern als Grafikdatei einlesen und als 256 Zahlwerte pro Bild als Liste speichern:
- Eine Funktion schreiben, die als Argument einen Dateinamen hat und als Rückgabewert eine Liste mit 256 Elementen.
- Diese Funktion auf alle Dateien anwenden (siehe unten) und die Ziffer aus dem Dateinamen in eine Liste von Liste mit 256+1 Elementen speichern
Hinweise
- Klassifizierungsfehler: $Y$ sind die wahren Klassen des Testsets, $\hat Y$ die vorhergesagten Klassen. Der Klassifizierungsfehler die relative Anzahl der falsch klassifizierten $\hat Y$. Wenn $Z=\begin{cases} 1&\text{wenn }Y\neq\hat Y\\0&\text{sonst.}\end{cases}$ dann ist der Klassifizierungsfehler $$\frac{1}{n}\sum_{i=1}^n Z.$$ NB: Der Klassifizierungsfehler ist nichts anderes als die falsch klassifizierten in Prozent!.
- Konvertierung der Bild-Dateien zu Zahlwerten
- Bilder können in Tigerjython mit getImage eingelesen werden.
- Verzeichnisse können mit os.listdir() durchlaufen werden:
- listdir.py
import os for filename in os.listdir("C:/temp/"): print(filename)
- Mit
filename.split('_', 3)
kann der String “filename” aufgeteilt ("gesplitted") werden, die 3 steht dabei für das Dritte Element nach dem Split in der Liste und entspricht der Ziffer. - Die Graustufenwerte von 0 bis 255 sollten auf Werte zwischen -1 und 1 “umgelegt” werden.
- Ziel ist eine Liste mit 256 + 1 Einträgen pro Bilddatei. Diese Liste könnte dann wieder als CSV Datei gespeichert werden.
- Speicherung als CSV passiert am einfachsten über CSV schreiben:
- writecsv.py
outcsv = open("C:/temp/outfile.csv", 'a'); # CSV-writer konfigurieren. writer = csv.writer(outcsv, delimiter=',', lineterminator='\n') for item in datalist: #Jeden Eintrag der Datalist als Zeile ausgeben writer.writerow([item[0], item[1], item[2]]) # Wrtier schliessen outcsv.close()
Lösungen
$k$ Nearest Neighbours auf Pixellisten
Ziele
- $k$ nearest neighbours in $k$-Dimensionen durchführen
- Einem Bild aus den Testdaten einen Zahlwert auf Grund der Trainingsdaten zuordnen
Der Code unten soll als Grundlage für den eigentlichen kNN Klassifizierer gelten. Es muss einizg noch die Funktion assignClass
geschrieben werden. Das Einlesen der Trainings- und Testdaten ist bereits programmiert, ebenso die Umwanldung eines Bildes in eine Pixelliste.
- stub_knn_digits.py
import gpanel #um bilder einzulesen import csv #um CSV-Dateien zu lesen. # Pfad zu den Bilddateien digitsdirectory = 'C:/temp/digits/' # Trainingsdaten trainingset = list(csv.reader(open(digitsdirectory + 'digitsdata.csv', 'r'), delimiter=',', quoting=csv.QUOTE_NONNUMERIC)) # Testdate testset = list(csv.reader(open(digitsdirectory + 'digitsdatatest.csv', 'r'), delimiter=',', quoting=csv.QUOTE_NONNUMERIC)) def getPixeListFromFilePath(filepath): img = gpanel.getImage(filepath) w = img.getWidth() h = img.getHeight() pixellist = [] for y in range(h): for x in range(w): # color is ein Objekt mit verschiedenen Attributen, u.a. red, green, blue. # bei grau sind rot=gruen=blau, d.h., eine Farbe auslesen reicht. # siehe auch https://docs.oracle.com/javase/7/docs/api/java/awt/Color.html color = img.getPixelColor(x, y) # umlegen auf das Intervall [-1,1] zwecks Normalisierung value = color.red / 255 * 2 - 1 # an liste anhaengen pixellist.append(value) return pixellist def assignClass(point, k): # Funktion die den Abstand von point zu den k naechsten # Nachbarn im trainingset berechnet mit Pythagoras in # 16x16=256 Dimensionen # gibt die Mehrheitsklasse wieder. Tip: Liste mit Häufigkeiten zurückgeben. return(assignedclass) ## Funktion Testen # Auf einem Testbild testpoint = getPixeListFromFilePath(digitsdirectory + 'test/testimg_993918225911_2_.gif') print(assignClass(testpoint, 100)) # Auf Testdaten for i in range(len(testset)): print(assignClass(testset[i][0:255], 30)) print(testset[i][256])