• Slides Einführung und Cheatsheet

• Woche 1
  • Dienstag
    • Einführung Big Data / Machine Learning / Artificial Intelligence
  • Donnerstag
    • Progammierung kNN
    • Intelligente Transformationen: Mathematik im Hintergrund
• Woche 2
  • Dienstag
    • Einführung Problematik Zahlenerkennung (Ziffernerkennung): Test und Training, Klassifikationsgüte.
    • Berechnnung Klassifikationsfehler in Abhängigkeit von $k$
  • Donnerstag
    • Aufbereitung Daten aus preprocessed 16×16 Bildern.
    • Evtl. Einführung kNN in hohen Dimensionen
• Woche 3
  • Dienstag
    • Einführung kNN in hohen Dimensionen: kNN-Klassifizierer
    • Test- und Trainings-Daten
  • Donnerstag
    • Klassifizierung abschliessen
    • Tuning: k, Konfusionsmatrix
    • Python 2.7 installieren
• Woche 4
  • Dienstag
    • Übersicht zentrale Begriffe und Ideen
    • Implementierung Scikit
    • Tour d'horizon: Trees, Random Forests, Neural Networks
  • Donnerstag
    • Prüfung / Challenge auf ungesehenen Testdaten
    • Neural Networks

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.

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

• 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

• Idee von Trainings- und Testdaten verstehen
• kNN-Code testen/verstehen:
  • Musterlösung verstehen
  • Klassifizierungsfehler auf Testdaten für verschiedene $k$ berechnen und Tabelle erstellen.

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

• 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

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

• 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

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}$

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

• 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

• Algorithmus mit weniger Trainingsdaten / Testdaten testen. Laufzeit!!
• Klassifikationsgüte allenfalls mit eigener Schlaufe über verschiedene $k$ automatisiert ausrechnen

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.

• kNN mit Python und Scikit durchführen
• Jeder kann die zentralen Begriffen erklären / beschreiben (→Slides)

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:

• 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