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$
- Flaschenhals kNN verstehen: Dimensionen, Anzahl Pixel, Farben, Sortierung
Tipps
- Algorithmus mit weniger Trainingsdaten / Testdaten testen. Laufzeit!!
- Klassifikationsgüte allenfalls mit eigener Schlaufe über verschiedene $k$ automatisiert ausrechnen
- Bild beschneiden, Graustufen etc. IrfanView
Zusatzinfos
Sortieren ist kostspielig: Einfache Sortieralgorithmen (BubbleSort) haben eine Komplexität von $\mathcal O(n^2)$, d.h., es werden ca. $n^2$ Operationen benötigt um $n$ Elemente zu sortieren.
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ätzlich 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
pip install numpy pip install scipy pip install sklearn pip install imageio
Ein wichtiges Konstrukt sind sogenannte numpy-Arrays: Diese sind grundsätzlich der Python (geschachtelten) Liste sehr ähnlich, sind aber im Umang viel praktischer. Mehr Details gibt's z.B. hier und hier. Das wichtigste dabei ist wohl, wie auf Elemente zugegriffen werden kann und wie Teilmengen von diesen gebildet werden können:
data = array([[2,3],[3,4]]) #zugriff via Zeile/Spalte: data[0,1] data[1,1] # fuer trainingsdaten trainingdata[0,256] # die Zahl des ersten Bildes trainingdata[4,2] # den Wert des dritten Pixel des 5 Bildes trainingsdata[0,:] # alle Werte inkl. Zahl des ersten Bildes.
Nachher kann relativ einfach mit Python kNN implementiert werden:
- knn_scikit.py
#!/usr/bin/python # -*- coding: utf-8 -*- from sklearn.neighbors import KNeighborsClassifier from numpy import genfromtxt,asarray from imageio import imread # Trainingdaten einlesen trainingdata = genfromtxt('C:/temp/digits/digitsdata.csv', delimiter=',') # Testdaten einlesen testdata = genfromtxt('C:/temp/digits/digitsdatatest.csv', delimiter=',') # Trainingsfeatures und -klassen trennen. # Kolonne 0:255: Features, Kolonne 256 Klasse # Fuer Ekrlaerung der Syntax siehe: https://docs.scipy.org/doc/numpy-1.13.0/reference/arrays.indexing.html train_digits_features = trainingdata[:, :-1] train_digits_class = trainingdata[:, -1] # Testfeatures und -klassen trennen. test_digits_features = testdata[:, :-1] test_digits_class = testdata[:, -1] # kNN initilisieren mit 5 Nachbarn knn = KNeighborsClassifier(n_neighbors=5) # kNN traininieren knn.fit(train_digits_features, train_digits_class) # Vorhersage predicted_class = knn.predict(test_digits_features) # Wahre Test digits ausgeben print(test_digits_class) # Predicted Test digits ausgeben print(predicted_class) ## Vergleichen und Klassifikationsguete berechnen. ## Differenz muss = 0 sein wenn richtig klassifziert. Boolsche Variablen koennen summiert werden. print sum(predicted_class - test_digits_class == 0) / float(len(predicted_class)) # Aquivalent der Funktion getPixelListFromFilePath def getPixelArrayFromFilePath(filepath): img = imread(filepath) return(asarray(((img.flatten()/float(255)*2-1).reshape(1,-1)))) getPixelArrayFromFilePath("C:/temp/digits/test/testimg_181710187299_0_.gif") print(knn.predict(getPixelArrayFromFilePath("C:/temp/digits/test/testimg_181710187299_0_.gif")))