=== Unterlagen & Daten === * {{efinf:blcks2017:bigdatab:handout20181213.pdf|Slides Einführung}} und {{efinf:blcks2017:bigdatab:tigerjython_cheatsheet.pdf|Cheatsheet}} === 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. 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. 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) ==== 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 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: {{ :efinf:blcks2017:bigdata:l2:structure.png?400 |}} Die Daten finden sich in einer neuen {{efinf:blcks2017:bigdatab:data2.zip|ZIP-Datein}} 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) ==== 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!. 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) ==== 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: import os for filename in os.listdir("C:/temp/"): print(filename) 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 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 ([[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: 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. {{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: 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. 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. [[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. 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) ==== 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 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. [[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: 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. === kNN in Python === Nachher kann relativ einfach mit Python kNN implementiert werden: #!/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"))) === Implementierung von Random Forests === #!/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