This is an old revision of the document!
k Nearest Neighbors
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).
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
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()