Differences

This shows you the differences between two versions of the page.

--- efinf:blcks2017:bigdatab:start [2018/03/06 11:25] – Simon Knaus
+++ efinf:blcks2017:bigdatab:start [2018/03/08 06:54] (current) – Simon Knaus
@@ Line 1: / Line 1: @@
+=== Unterlagen   & Daten ===
+  * {{efinf:blcks2017:bigdatab:handout20181213.pdf|Slides Einführung}} und {{efinf:blcks2017:bigdatab:tigerjython_cheatsheet.pdf|Cheatsheet}}
+<!--  * Daten Punktewolke: {{efinf:blcks2017:bigdata:data.zip|Training}} und {{efinf:blcks2017:bigdata:testdata.zip|Test}}
+  * Daten Ziffern
+    * Bildaten: {{efinf:blcks2017:bigdata:digits.zip|Training und Test}}
+    * Textdaten als CSV: {{efinf:blcks2017:bigdata:digitsdata.zip|Training}} und {{efinf:blcks2017:bigdata:digitsdatatest.zip|Test}}
+-->
+=== Lektionen ===
+  * Woche 1
+    * [[#L1|Dienstag]]
+      * Einführung Big Data / Machine Learning / Artificial Intelligence
+    * [[#L2|Donnerstag]]
+      * Progammierung kNN
+      * Intelligente Transformationen: Mathematik im Hintergrund
+  * Woche 2
+    * [[#L3|Dienstag]]
+      * Einführung Problematik Zahlenerkennung (Ziffernerkennung): Test und Training, Klassifikationsgüte.
+      * Berechnnung Klassifikationsfehler in Abhängigkeit von $k$
+    * [[#L4|Donnerstag]]
+      * Aufbereitung Daten aus preprocessed 16x16 Bildern.
+      * Evtl. Einführung kNN in hohen Dimensionen
+  * Woche 3
+    * [[#L5|Dienstag]]
+      * Einführung kNN in hohen Dimensionen: kNN-Klassifizierer
+      * Test- und Trainings-Daten
+    * [[#L6|Donnerstag]]
+      * Klassifizierung abschliessen
+      * Tuning: k, Konfusionsmatrix
+      * Python 2.7 installieren
+  * Woche 4
+    * [[#L7|Dienstag]]
+      * Übersicht zentrale Begriffe und Ideen
+      * Implementierung Scikit
+      * Tour d'horizon: Trees, Random Forests, Neural Networks
+    * [[#L8|Donnerstag]]
+      * Prüfung / Challenge auf ungesehenen Testdaten
+      * Neural Networks
+==== L1 ====
+{{efinf:blcks2017:bigdatab:data_l01.zip|Daten der Punkte}} und {{efinf:blcks2017:bigdatab:handout20181213.pdf|Slides Einführung}} der ersten Veranstaltung.
+<file python 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.
+</file>
+<hidden Lösung>
+<file python readdata_sol.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)
+#GPanel aufsetzen
+makeGPanel(-20,20,-20,20)
+drawGrid(-15,15,-15,15)
+# Punkte zeichnen
+for i in range(len(datalist)):
+    move(datalist[i][0], datalist[i][1])
+    if int(datalist[i][2])==1:
+        setColor("orange")
+    else:
+        setColor("blue")
+    fillCircle(0.1)
+</file>
+</hidden>
+==== 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 [[https://www.programiz.com/python-programming/methods/built-in/sorted|sorted]] gelöst werden.
+    * Auf Grund der sortierten Liste kann die Mehrheitsmeinung der $k$ nächsten Nachbarn bestimmt werden
+<code python>
+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)
+</code>
+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:
+{{ :efinf:blcks2017:bigdata:l2:structure.png?400 |}}
+Die Daten finden sich in einer neuen {{efinf:blcks2017:bigdatab:data2.zip|ZIP-Datein}}
+<hidden Lösung>
+<code python knn_classification.py>
+from gpanel import *
+import csv  # um Text-Dateien im CSV-Format zu lesen
+import random
+# CSV-File oefffnen
+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)
+# GPanel aufsetzen
+makeGPanel(-20, 20, -20, 20)
+drawGrid(-15, 15, -15, 15)
+# Punkte zeichnen
+for i in range(len(datalist)):
+    move(datalist[i][0], datalist[i][1])
+    if int(datalist[i][2]) == 1:
+        setColor('orange')
+    else:
+        setColor('green')
+    fillCircle(0.1)
+# Funktion, die einem Punkt eine Klasse auf Grund der k naechsten Nachbarn zuweist.
+def assignClass(point, k):
+    # Funktion die die Distanzen vom Punkt zu den exisitierenden Punkte berechnet
+    # Liste um die Distanzen zu speichern. Achtung: Speicher!!
+    distlist = []
+    #
+    for i in range(len(datalist)):
+        distlist.append([datalist[i][2],sqrt((point[0]
+                            - datalist[i][0]) ** 2 + (point[1]
+                            - datalist[i][1]) ** 2)])
+    # das waere ein sehr Pythonesquer Weg mit Lambda-Funktionen
+    # nearest = sorted(distlist,key=lambda result:result[1])
+	# definiere eine Funktion, welche das zweite Element zurueckgibt.
+    def sortFunction(item):
+        return item[1]
+    # Sortiere die liste! Achtung: Man koennte auch ohne key Arbeiten, wenn Distanz an 1. Stelle waere
+    nearest = sorted(distlist, key=sortFunction)
+    # Zaehle Klassennummern und entscheide ueber Klasse. Achtung: Laesst sich so nicht auf k>2 Klassen erweitern.
+    classsum = sum([nearest[i][0] for i in range(k)])
+    if classsum > k / 2:
+        retclass = 1
+    elif classsum < k / 2:
+        retclass = 0
+    else:
+        retclass = random.randint(0, 1)
+    return retclass
+#Funktion um Pt zu zeichnen und mit Label auf Grund der k-naechsten Nachbarn zu versehen
+def drawAndLablePoint(point, k):
+    guessedclass = assignClass(point, k)
+    move(point)
+    setColor('black')
+    fillRectangle(0.02, 0.02)
+    text(str(guessedclass))
+#Programm teseten
+drawAndLablePoint([-0.5, 0.5], 3)
+drawAndLablePoint([0.5, 0.5], 3)
+print assignClass([-1, -1], 3)
+print assignClass([-1, 1], 3)
+print assignClass([1, -1], 3)
+print assignClass([1, 1], 3)
+print assignClass([-1, 0.5], 3)
+</code>
+</hidden>
+==== L3 ====
+=== Ziele ===
+  * Idee von Trainings- und Testdaten verstehen
+  * [[#moegliche_loesung_knn|kNN-Code]] testen/verstehen:
+    * Musterlösung verstehen
+    * Klassifizierungsfehler auf {{efinf:blcks2017:bigdatab:testdata.zip|Testdaten}} für verschiedene $k$ berechnen und Tabelle erstellen.
+=== 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!.
+<hidden Lösung>
+<file python knn_evaluate.py>
+import time
+import csv  # um Text-Dateien im CSV-Format zu lesen
+import random
+from math import sqrt #ist  bei Standard Python nicht dabei
+# CSV-Files oefffnen
+traindata = open('C:/temp/data.csv', 'r')
+testdata = open('C:/temp/testdata.csv','r')
+# CSV-Files oefffnen
+trainreader = csv.reader(traindata, delimiter=',', quoting=csv.QUOTE_NONNUMERIC)
+testreader = csv.reader(testdata, delimiter=',', quoting=csv.QUOTE_NONNUMERIC)
+# CSV-Files in Liste umwandeln
+datalist = list(trainreader)
+testlist = list(testreader)
+# File-handle schliessen
+traindata.close()
+testdata.close()
+# Funktion, die einem Punkt eine Klasse auf Grund der k naechsten Nachbarn zuweist.
+def assignClass(point, k):
+    # Liste um die Distanzen zu speichern.
+    distlist = []
+    # Für jeden den Punkt point die Distanzen zu allen Punkten in datalist berechnen.
+    for i in range(len(datalist)):
+        distlist.append([datalist[i][2],sqrt((point[0]
+                            - datalist[i][0]) ** 2 + (point[1]
+                            - datalist[i][1]) ** 2)])
+    # das waere ein sehr Pythonesquer Weg mit Lambda-Funktionen
+    # nearest = sorted(distlist,key=lambda result:result[1])
+    # definiere eine Funktion, welche das zweite Element zurueckgibt.
+    def sortFunction(item):
+        return item[1]
+    # Sortiere die liste! Achtung: Man koennte auch ohne key Arbeiten, wenn Distanz an 1. Stelle waere
+    nearest = sorted(distlist, key=sortFunction)
+    # Zaehle Klassennummern und entscheide ueber Klasse. Achtung: Laesst sich so nicht auf k>2 Klassen erweitern.
+    classsum = sum([nearest[i][0] for i in range(k)])
+    if classsum > k / 2:
+        retclass = 1
+    elif classsum < k / 2:
+        retclass = 0
+    else:
+        retclass = random.randint(0, 1)
+    return retclass
+## Bereich zum Vergleichen:
+testlength=len(testlist)
+summary = []
+## Iteriere über mehrere Anzahl Nachbarn.
+for k in range(1,20):
+    correct = 0
+    for i in range(testlength):
+        # teste ob korrekt klassifiziert: wenn ja, correct um 1 erhöhen
+        if(abs(testlist[i][2]) - assignClass(testlist[i][0:2],k)<.5):
+            correct+=1
+    # k und relative Anzahl korrekter ablegen
+    summary.append([k,float(correct)/testlength])
+print(summary)
+</file>
+</hidden>
+==== L4 ====
+=== Ziele ===
+  * Musterlösung Klassifikationsfehler in Abhängigkeit von $k$ verstehen.
+  * ZIP-Code Problematik verstehen: ZIP-Code -> Ziffer -> 16x16 Bild -> Liste mit 256 Graustufen-Werten -> kNN in $\mathbb{R}^{256}$.
+  * Einzelne Ziffern als {{efinf:blcks2017:bigdatab:digits.zip|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 [[http://www.tigerjython.ch/index.php?inhalt_links=navigation.inc.php&inhalt_mitte=grafik/bildbearbeitung.inc.php|getImage]] eingelesen werden.
+    * Verzeichnisse können mit os.listdir() durchlaufen werden: <file python listdir.py>import os
+for filename in os.listdir("C:/temp/"):
+    print(filename)
+</file>Möchte man nur GIF-Dateien lesen, kann dies mit [[http://www.fh-wedel.de/~si/vorlesungen/fp/Syntax/MapFilter.html|List Comprehensions und Filtern]] gelöst werden<file python listdirfilter.py>
+import os
+for filename in [filename for filename in os.listdir("C:/temp") if filename.endswith("gif")]:
+  print(filename)
+ </file>
+    * Mit ''filename.split('_')[2]'' kann der String "filename" aufgeteilt ([[https://www.programiz.com/python-programming/methods/string/split|"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 [[https://de.wikipedia.org/wiki/CSV_(Dateiformat)|CSV]] Datei gespeichert werden.
+    * Speicherung als CSV passiert am einfachsten über CSV schreiben: <file python 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()
+ </file>
+Die Anzahl Nachbarn $k$ ist ein sogenannter "Tunig-Parameter": Ein Parameter, der die Aussage des Klassifizierers massgeblich beeinflusst.
+{{efinf:blcks2017:bigdata:guete_nach_k.pdf|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 {{efinf:blcks2017:bigdatab:digitsdata_csv.zip|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:
+<code python 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)
+</code>
+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.
+<code python 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])
+</code>
+==== 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. [[http://www.irfanview.de/|IrfanView]]
+=== Zusatzinfos ===
+Sortieren ist kostspielig:  Einfache Sortieralgorithmen ([[https://visualgo.net/bn/sorting|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.
+<hidden Lösung>
+<code python knn_bilder.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/'
+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)
+# Alternative: Einlesen von Datei
+# trainingset = list(csv.reader(open('C:/temp/digitsdata.csv', 'r'), delimiter=',', quoting=csv.QUOTE_NONNUMERIC))
+# Funktion, die einem Punkt eine Klasse auf Grund der k naechsten Nachbarn zuweist.
+def assignClass(point, k):
+    # Liste um die Distanzen zu speichern.
+    distlist = []
+    # Fuer jeden den Punkt point die Distanzen zu allen Punkten in datalist berechnen.
+    for i in range(len(trainingset)):
+        dist = 0
+        # schlaufe ueber die 256 pixel
+        for j in range(255):
+            dist += (point[j] - trainingset[i][j]) ** 2
+        distlist.append([trainingset[i][256], sqrt(dist)])
+    # das waere ein sehr Pythonesquer Weg mit Lambda-Funktionen
+    # nearest = sorted(distlist,key=lambda result:result[1])
+    # definiere eine Funktion, welche das zweite Element zurueckgibt.
+    def sortFunction(item):
+        return item[1]
+    # Sortiere die liste! Achtung: Man koennte auch ohne key Arbeiten, wenn Distanz an 1. Stelle waere
+    nearest = sorted(distlist, key=sortFunction)
+    # Zaehle k naechsten Klassennummern und entscheide ueber Klasse.
+    # Liste die die Anzahl Vorkommen von 0,1,2,...,9 enthaelt. An Stelle 0 die Null, an Stelle 1 die Eins etc.
+    classcounts = [0] * 10
+    # Loope durch die k naechsten Nachbarn und erhoehe den classcount jeweils um 1
+    # wenn eine Ziffer (Klasse) der jeweiligen Ziffer gefunden worden ist.
+    for j in range(k):
+        classcounts[int(nearest[j][0])] += 1
+    # Rueckggabe der Anzahl/Klasse.
+    # Wenn anstelle der Anzahl/Klasse die eigentlich Ziffer zurueckgegeben werden soll,
+    # kann dies mit    classcounts.index(max(classcounts)) passieren.
+    return classcounts
+# Teste das Programm
+testpoint = getPixeListFromFilePath(digitsdirectory + 'testimg_993918225911_2_.gif')
+print assignClass(testpoint, 100)
+testpoint = getPixeListFromFilePath(digitsdirectory + 'testimg_899286188295_1_.gif')
+print assignClass(testpoint, 100)
+testpoint = getPixeListFromFilePath(digitsdirectory + 'testimg_809996871457_8_.gif')
+print assignClass(testpoint, 100)
+testpoint = getPixeListFromFilePath('C:/temp/man1.gif')
+print assignClass(testpoint, 5)
+</code>
+</hidden>
+====  L7 ====
+=== Ziele ===
+  * Jeder kann die zentralen Begriffen erklären / beschreiben (->{{efinf:blcks2017:bigdatab:slides20180306.pdf|Slides}})
+  * kNN mit Python und Scikit durchführen
+  * Eigene Ziffer als GIF klassifizieren oder Random Forests durchführen
+=== Aufträge ===
+  * Bei installiertem Python 2.7. die notwendigen Module installieren (siehe [[#Zusatzhintergrund Python]])
+  * kNN in Python durchführen, siehe [[#kNN in Python|knn_scikit.py]]
+  * Wer soweit durch:
+    * Eigene Ziffer als GIF klassifizieren mit der Funktion ''getPixelArrayFromFilePath(filepath)''
+    * Random Forests durchführen und Klassifikationsgüte mit kNN vergleichen
+    * kNN für verschiedene ''$k$'' und Random Forests für verschieden ''n_estimators'' durchführen. Beides sind sogenannte "Tunig-Parameter", welche die Klassifikationsgüte beinflussen. Frage: Wie könnte ein optimales $k$ bestimmt werden?
+=== Zusatzhintergrund Python ===
+Um mit bereits implementierten Methoden von [[http://scikit-learn.org/stable/|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 [[https://www.python.org/downloads/release/python-2714/|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
+<code>
+pip install numpy
+pip install scipy
+pip install sklearn
+pip install imageio
+</code>
+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. [[http://www.scipy-lectures.org/intro/numpy/array_object.html|hier]] und [[https://docs.scipy.org/doc/numpy-1.13.0/reference/arrays.indexing.html|hier]]. Das wichtigste dabei ist wohl, wie auf Elemente zugegriffen werden kann und wie Teilmengen von diesen gebildet werden können:
+<code python>
+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.
+</code>
+=== kNN in Python ===
+Nachher kann relativ einfach mit Python kNN implementiert werden:
+<code python knn_scikit.py>
+#!/usr/bin/python
+# -*- coding: utf-8 -*-
+from sklearn.neighbors import KNeighborsClassifier
+from sklearn.metrics import confusion_matrix
+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))
+## Konfusionsmatrix berechnen
+mat_knn = confusion_matrix(test_digits_class, predicted_class)
+print(mat_knn)
+# 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")))
+</code>
+=== Implementierung von Random Forests ===
+<code python knn_rf_scikit.py>
+#!/usr/bin/python
+# -*- coding: utf-8 -*-
+from sklearn.neighbors import KNeighborsClassifier
+from numpy import genfromtxt, asarray, sum
+from sklearn.metrics import confusion_matrix
+from sklearn.ensemble import RandomForestClassifier
+#######################################################################
+#
+# Daten einlesen. Für Random Forests (rf) und k-Nearest-Neighbors (knn)
+#
+#######################################################################
+# 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 trainieren, vorhersagen und evaluieren.
+#
+#######################################################################
+#kNN initilisieren mit 10 Nachbarn
+knn = KNeighborsClassifier(n_neighbors = 10)
+# kNN traininieren
+knn.fit(train_digits_features, train_digits_class)
+# Vorhersage
+predicted_class_knn = knn.predict(test_digits_features)
+# Konfusionsmatrix
+mat_knn = confusion_matrix(test_digits_class, predicted_class_knn)
+print(mat_knn)# Güte
+guete_knn = sum(mat_knn.diagonal()) / float(sum(mat_knn))
+print "Guete kNN:", guete_knn
+#######################################################################
+#
+# Random Forests trainieren, vorhersagen und evaluieren.
+#
+#######################################################################
+rf = RandomForestClassifier(n_estimators = 200, random_state = 17)
+rf.fit(train_digits_features, train_digits_class)
+predicted_class_rf = rf.predict(test_digits_features)
+mat_rf = confusion_matrix(test_digits_class, predicted_class_rf)
+print(mat_rf)
+# Güte
+guete_rf = sum(mat_rf.diagonal()) / float(sum(mat_rf))
+print "Guete rf:", guete_rf
+</code>
+<!--
+==== L6 - L7 ====
+=== Ziele ===
+  * kNN in TigerJython einmal durchführen: "Proof-of-concept". Wer möchte, mit eigenen Ziffern aus {{efinf:blcks2017:bigdata:zifferna4scan.zip|Bildern}}.
+  * kNN in Python mit sklearn durchführen.
+  * Einfluss von $k$ und $n$ kennen / durchprobieren mit sklearn.
+    * Welches ist das optimale $k$ bei 100, 200, 500, 1000, 2000, 5000, 7000 Observationen?
+    * Wie stark hängt Klassifikationsgüte von Trainingsgrösse ab?
+    * ...
+  * Weiterführende Aspekte Computer Lernen kennenlernen:
+    * Künstliche Testsets  ("evaluation", "cross-validation"): Performance auf Testset auf Grund der Trainingsdaten vorhersagen
+    * Data Augmentation: Leicht veränderte Trainingsdate (Rotation, Scherung, etc.)
+    * Daten Qualität: Falsch klassifzierte Trainingsdaten.
+=== Zusatzhintergrund Python ===
+Um mit bereits implementierten Methoden von [[http://scikit-learn.org/stable/|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 [[https://www.python.org/downloads/release/python-2714/|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
+<code>
+pip install numpy
+pip install scipy
+pip install sklearn
+pip install imageio
+</code>
+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. [[http://www.scipy-lectures.org/intro/numpy/array_object.html|hier]] und [[[[https://docs.scipy.org/doc/numpy-1.13.0/reference/arrays.indexing.html|hier]]. Das wichtigste dabei ist wohl, wie auf Elemente zugegriffen werden kann und wie Teilmengen von diesen gebildet werden können:
+<code python>
+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.
+</code>
+Nachher kann relativ einfach mit Python kNN implementiert werden:
+<code python 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")))
+</code>
+==== L7 ====
+=== Ziele ===
+  * Jede/r kann die zentralen Begriffe der Slides erklären / berechnen / durchführen
+  * $k$-nearest neighbor und random forests in Python durchführen
+  * Vorbereitung Testcases Prüfung
+Die Slides der Stunde finden sich {{efinf:blcks2017:bigdata:handout20180206.pdf|hier}}.
+Eine Implementierung in Python, die ''knn_scikit.py'' aufgreift findet sich untenstehend
+<code python knn_rf_scikit.py>
+#!/usr/bin/python
+# -*- coding: utf-8 -*-
+from sklearn.neighbors import KNeighborsClassifier
+from numpy import genfromtxt, asarray, sum
+from sklearn.metrics import confusion_matrix
+from sklearn.ensemble import RandomForestClassifier
+#######################################################################
+#
+# Daten einlesen. Für Random Forests (rf) und k-Nearest-Neighbors (knn)
+#
+#######################################################################
+# 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 trainieren, vorhersagen und evaluieren.
+#
+#######################################################################
+#kNN initilisieren mit 10 Nachbarn
+knn = KNeighborsClassifier(n_neighbors = 10)
+# kNN traininieren
+knn.fit(train_digits_features, train_digits_class)
+# Vorhersage
+predicted_class_knn = knn.predict(test_digits_features)
+# Konfusionsmatrix
+mat_knn = confusion_matrix(test_digits_class, predicted_class_knn)
+print(mat_knn)# Güte
+guete_knn = sum(mat_knn.diagonal()) / float(sum(mat_knn))
+print "Guete kNN:", guete_knn
+#######################################################################
+#
+# Random Forests trainieren, vorhersagen und evaluieren.
+#
+#######################################################################
+rf = RandomForestClassifier(n_estimators = 200, random_state = 17)
+rf.fit(train_digits_features, train_digits_class)
+predicted_class_rf = rf.predict(test_digits_features)
+mat_rf = confusion_matrix(test_digits_class, predicted_class_rf)
+print(mat_rf)
+# Güte
+guete_rf = sum(mat_rf.diagonal()) / float(sum(mat_rf))
+print "Guete rf:", guete_rf
+</code>
+==== L8 ====
+Prüfung und ANN
+=== Evaluation ===
+  * {{efinf:blcks2017:bigdatab:exam.zip|Daten für die Prüfung}}. Die Daten sind im üblichen Format. Anstelle der Ziffer steht an der letzten Stelle eine '-99'.
+  * [[https://forms.office.com/Pages/ResponsePage.aspx?id=vUGvXYwzEUOxsOEpmInDS12XSwf-80xHjgGMQjpEmz9UMzhYQTZIRTdSS0hRTVpPVlJUNzJOQzU3My4u|Formular zur Abgabe der Testcases]]
+=== Artificial Neural Networks ===
+  * [[https://www.youtube.com/watch?v=3hnWf_wdgzs|Google Deep Dream]]
+  * https://www.google.ch/search?q=deep+dream+gallery&tbm=isch&tbo=u&source=univ&sa=Xbiw=1745&bih=863
+=== Feedback ===
+https://forms.office.com/Pages/ResponsePage.aspx?id=vUGvXYwzEUOxsOEpmInDS12XSwf-80xHjgGMQjpEmz9UQzJGV1gxMkFHRFJVNDdWWkc4RDMwU1Q4Mi4u