This is an old revision of the document!
Unterlagen & Daten
Lektionen
- Woche 1
-
- Einführung Big Data / Machine Learning / Artificial Intelligence
-
- Progammierung kNN
- Intelligente Transformationen: Mathematik im Hintergrund
-
- Woche 2
-
- Einführung Problematik Zahlenerkennung (Ziffernerkennung): Test und Training, Klassifikationsgüte.
- Berechnnung Klassifikationsfehler in Abhängigkeit von $k$
-
- Aufbereitung Daten aus preprocessed 16×16 Bildern.
- Evtl. Einführung kNN in hohen Dimensionen
-
- Woche 3
-
- Einführung kNN in hohen Dimensionen: kNN-Klassifizierer
- Test- und Trainings-Daten
-
- Klassifizierung abschliessen
- Tuning: k, Konfusionsmatrix
- Python 2.7 installieren
-
- Woche 4
-
- Übersicht zentrale Begriffe und Ideen
- Implementierung Scikit
- Tour d'horizon: Trees, Random Forests, Neural Networks
-
- Prüfung / Challenge auf ungesehenen Testdaten
- Neural Networks
-
L1
Daten der Punkte und Slides Einführung der ersten Veranstaltung.
- readdata.py
from gpanel import * import csv #um Text-Dateien im CSV-Format zu lesen import random # CSV-File öffnen csvfile = open('C:/temp/data.csv', 'r') # CSV-File einlesen. reader = csv.reader(csvfile, delimiter=',',quoting=csv.QUOTE_NONNUMERIC) # CSV-File in Liste umwandeln datalist = list(reader) # reader schliessen reader.close() # Liste anschauen: # print(datalist) # GPanel aufsetzen makeGPanel(-20,20,-20,20) drawGrid(-15,15,-15,15) # Punkte zeichnen # Alle Punkte in einer Schlaufen zeichnen, x-Koordinate: 1 Komponenten, y-Koordinate: 2. Komponente, Farbe: 3-Komponente # Mögliche hilfreiche Funktion move, if, setColor, fillCircle, etc.
L2
Ziel
- Den $k$-nearest-neighbour Algorithmus in $\mathbb{R}^2$ implementieren.
- Auf Grund einer Liste mit Kooordinaten
[[0.1231,1.3],[1.31,-0.32],...]
wird eine Klasse zugewiesen, d.h. entweder 0 oder 1.
Wichtige Zutaten
- Liste mit Distanzen und Klassen, i.e.
[[0.033131,1],[0.123131,0],[0.123124141,1],[1.2123141,0]]
- 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.
- Auf Grund der sortierten Liste kann die Mehrheitsmeinung der $k$ nächsten Nachbarn bestimmt werden
def computeDistances(xn,yn): # Funktion berechnet die Distanz von (xn,yn) zu den Punkten in datalist return(distanceClassList) def assignClass(distClassList): # die k nächsten nachbar raussuchen # mehrheit herausfinden # mehrheismeinung zurückgeben return(klasse)
Empfehlung: Mindestens zwei Funktionen definieren. Eine zur Berechnung der Distanz-Klassen-Liste, sowie eine zur Zuweisung der Klasse (0 oder 1) resp. Farbe auf Grund der Liste .
Testen des Algorithmus mit
- Einem fixen Punkt, z.B. (3,2)
- 100, 1000, 10'000 zufällig als Quadrat dargestellte eingefärbte Punkten.
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
L3
Ziele
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_i=\begin{cases} 1&\text{wenn }Y_i\neq\hat Y_i\\0&\text{sonst.}\end{cases}$ dann ist der Klassifizierungsfehler $$\frac{1}{n}\sum_{i=1}^n Z_i.$$ NB: Der Klassifizierungsfehler ist nichts anderes als die falsch klassifizierten in Prozent!.
L4
Ziele
- Musterlösung Klassifikationsfehler in Abhängigkeit von $k$ verstehen.
- 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
- 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)
Möchte man nur GIF-Dateien lesen, kann dies mit List Comprehensions und Filtern gelöst werden
- listdirfilter.py
import os for filename in [filename for filename in os.listdir("C:/temp") if filename.endswith("gif")]: print(filename)
- Mit
filename.split('_')[2]
kann der String “filename” aufgeteilt ("gesplitted") werden, die 2 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()
Die Anzahl Nachbarn $k$ ist ein sogenannter “Tunig-Parameter”: Ein Parameter, der die Aussage des Klassifizierers massgeblich beeinflusst. Angehängte Graphik illustriert diesen Zusammenhang.
L5
Ziele
- Musterlösung zur Konvertierung von Bild → Pixelliste verstehen / beenden.
- Implementierung kNN-Klassifizierer auf den Zeichendaten. Entweder die eigenen Zeichendaten oder die vorbereiteten Daten von Ks
- Klassifizieren einer eigenen, handgeschriebenen Zahl
Distanz in $n$ Dimensionen
Beim kNN-Algorithmus geht es darum, den Abstand zu den Nachbarn zu berechnen. Bis jetzt war unser Problem $2$-dimensional. Neu ist es $256$-dimensional, da jeder Pixel einer Dimension entspricht. Daher:
- Im eindimensionalen Fall ($\mathbb{R}^1$): $P=(p_1)$, $Q=(q_1)$, $d(P,Q)=\sqrt{(p_1-q_1)^2}$
- Im zweidimensionalen Fall ($\mathbb{R}^2$): $P=(p_1,p_2)$, $Q=(q_1,q_2)$, $d(P,Q)=\sqrt{(p_1-q_1)^2+(p_2-q_2)^2}$
- Im dreidimensionalen Fall ($\mathbb{R}^3$): $P=(p_1,p_2,p_3)$, $Q=(q_1,q_2,q_3)$, $d(P,Q)=\sqrt{(p_1-q_1)^2+(p_2-q_2)^2+(p_3-q_3)^2}$
- Im vierdimensionalen Fall ($\mathbb{R}^4$): $P=(p_1,p_2,p_3,p_4)$, $Q=(q_1,q_2,q_3,q_4)$, $d(P,Q)=\sqrt{(p_1-q_1)^2+(p_2-q_2)^2+(p_3-q_3)^2+(p_4-q_4)^2}$
- Im $n$-dimensionalen Fall ($\mathbb{R}^n$): $P=(p_1,p_2,p_3,\ldots,p_n)$, $Q=(q_1,q_2,q_3,\ldots,q_n)$, $d(P,Q)=\sqrt{(p_1-q_1)^2+(p_2-q_2)^2+(p_3-q_3)^2+\cdots+(p_n-q_n)^2}=\sqrt{\sum_{i=1}^n(p_i-q_i)^2}$
Konvertierung Bild <-> Pixelliste
Musterlösung um eine Pixelliste aus allen Dateien eines Verzeichnisses zu erstellen:
- pixelist_from_directory.py
import gpanel #um bilder einzulesen import os #um Verzeichnisse zu listen import csv #um CSV-Dateien zu lesen. # Pfad zu den Bilddateien digitsdirectory = 'C:/temp/digits/train/' 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 # Lese Ziffer aus Dateiname aus. def getDigitFromFileName(filename): return int(filename.split('_', 3)[2]) # leere Liste fuer alle Trainingsdaten der Form [-0.93,0.331,....,0.99,3] trainingset = [] # durch alle files im Ziffernverzeichnis loopen for filename in [filename for filename in os.listdir(digitsdirectory) if filename.endswith("gif")]: # Ziffer auslesen currdigit = getDigitFromFileName(filename) # Pixelliste von Datei auslesen currpixellist = getPixeListFromFilePath(digitsdirectory + filename) # Der Pixelliste die Ziffer anhaengen currpixellist.append(currdigit) # Gesamte Liste dem trainingsset anhaengen. trainingset.append(currpixellist) # Das Trainingsset kann jetzt verwendet werden # print(trainingsset)
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 csv #um CSV-Dateien zu lesen. # Trainingsdaten trainingset = list(csv.reader(open(digitsdirectory + 'digitsdata.csv', 'r'), delimiter=',', quoting=csv.QUOTE_NONNUMERIC)) # Testdaten testset = list(csv.reader(open(digitsdirectory + 'digitsdatatest.csv', 'r'), delimiter=',', quoting=csv.QUOTE_NONNUMERIC)) def assignClass(point, k): # Funktion die den Abstand von point zu den k naechsten # Nachbarn im trainingset berechnet mit Pythagoras in # 16x16=256 Dimensionen # über alle Trainingsdaten iterieren for i in range(len(trainingsset)): dist = 0; # über alle 256 Pixel iterieren (für alle Trainingsdaten) for j in range(255): dist = dist + (point[j] - trainingsset[i][j])^2 #etc. # gibt die Mehrheitsklasse wieder. Tip: Liste mit Häufigkeiten zurückgeben. return(assignedclass) ## Funktion Testen auf ersten Testbild print(assignClass(testset[0][0:255], 30)) # Auf allen Testdaten for i in range(len(testset)): print(assignClass(testset[i][0:255], 30)) print(testset[i][256])
L6
Ziele
- kNN für Ziffern abschliessen / Musterlösung verstehen
- Klassifikationsgüte für verschiedene $k$ ausrechnen
- Konfusionsmatrix berechnen für ein bestimmtes $k$
Tipps
- Algorithmus mit weniger Trainingsdaten / Testdaten testen. Laufzeit!!
- Klassifikationsgüte allenfalls mit eigener Schlaufe über verschiedene $k$ automatisiert ausrechnen
L7
Ziele
- kNN mit Python und Scikit durchführen
- Jeder kann die zentralen Begriffen erklären / beschreiben (→Slides)
Zusatzhintergrund Python
Um mit bereits implementierten Methoden von scikit zu arbeiten, müssen zusätlich die Module numpy, scipy und sklearn installiert werden. Dies geschieht am besten, auf der Kommandozeile / Konsole mit pip
. Vorgänging muss bereits Python (2.7) installiert sein:
Navigation zu PIP
- Pfad aus Explorer kopieren, üblicherweise
C:\Python27\Scripts
- Im DOS-Prompt (Windows + R → cmd) zum Verzeichnis navigieren mit
cd C:\Python27\Scripts
- Dann
pip install …
und die Modulnamen