Den $k$-nearest-neighbour Algorithmus in $\mathbb{R}^2$ implementieren.

• 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).

Wer $k$-nearest-neighbour implementiert hat, kann sich überlegen, wie die untenstehende Daten klassifiziert werden sollen: Die Daten finden sich in einer neuen ZIP-Datein

• 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

• 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()
     

• $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])