Differences
This shows you the differences between two versions of the page.
Next revision | Previous revision | ||
kurse:efcomputergrafik:knn [2020/03/24 12:07] Simon Knaus created |
kurse:efcomputergrafik:knn [2020/03/24 14:55] (current) Simon Knaus [$k$ Nearest Neighbors] |
||
---|---|---|---|
Line 1: | Line 1: | ||
- | ==== k Nearest Neighbors ==== | + | ==== $k$ Nearest Neighbors ==== |
+ | Bei $k$ nearest neighbours (kNN) geht es darum, einem dazukommenden Punkt diese Klasse zuzuweisen, welche die nächsten $k$-Punkte mehrheitlich haben. | ||
+ | Der Trainingsdatensatz sind damit alle Punkte, von welchem man die Klasse und Koordinaten kennt. Auf Grund dieser Klassen und Koordinaten wird einem neuen Datenpunkt einzig auf Grund der Koordinaten eine Klasse zugeordnet. | ||
- | === Einführung === | + | {{ : |
- | == Ziel == | + | === Bemerkungen ==== |
+ | * Die untenstehenden Codes sind für TigerJython gedacht | ||
+ | * Die Codes sind nicht unbedingt schnell sondern illustrativ | ||
+ | * Es werden folgende Daten benötigt: | ||
+ | * {{kurse: | ||
+ | * {{kurse: | ||
+ | * ZIP-Code Daten | ||
+ | * Training: {{kurse: | ||
+ | * Test: {{kurse: | ||
+ | * (Optional) {{kurse: | ||
+ | * (Optional) {{kurse: | ||
+ | |||
+ | ==== Einführung | ||
+ | === Ziel === | ||
Den $k$-nearest-neighbour Algorithmus in $\mathbb{R}^2$ implementieren. | Den $k$-nearest-neighbour Algorithmus in $\mathbb{R}^2$ implementieren. | ||
Line 14: | Line 29: | ||
- | Wer $k$-nearest-neighbour implementiert hat, kann sich überlegen, wie die untenstehende Daten klassifiziert werden sollen: | + | Die Daten finden sich in einer {{kurse:efcomputergrafik:knn:knn_r2_trainingsdaten.zip|ZIP-Datei}} |
- | {{ : | + | |
- | Die Daten finden sich in einer neuen {{efinf: | + | |
- | < | + | < |
<file python knn.py> | <file python knn.py> | ||
from gpanel import * | from gpanel import * | ||
Line 116: | Line 129: | ||
</ | </ | ||
+ | </ | ||
+ | |||
+ | ==== Ziffern als Pixellisten ==== | ||
+ | === Ziele === | ||
+ | |||
+ | * Klassifizierungsfehler auf {{kurse: | ||
+ | * ZIP-Code Problematik verstehen: ZIP-Code -> Ziffer -> 16x16 Bild -> Liste mit 256 Graustufen-Werten -> kNN in $\mathbb{R}^{256}$. | ||
+ | * Einzelne Ziffern als {{kurse: | ||
+ | * 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 === | ||
+ | * **Klassifizierungsfehler**: | ||
+ | * **Konvertierung der Bild-Dateien zu Zahlwerten** | ||
+ | * Bilder können in Tigerjython mit [[http:// | ||
+ | * Verzeichnisse können mit os.listdir() durchlaufen werden: <file python listdir.py> | ||
+ | for filename in os.listdir(" | ||
+ | print(filename) | ||
+ | |||
+ | </ | ||
+ | * Mit '' | ||
+ | * Die Graustufenwerte von 0 bis 255 sollten auf Werte zwischen -1 und 1 " | ||
+ | * Ziel ist eine Liste mit 256 + 1 Einträgen pro Bilddatei. Diese Liste könnte dann wieder als [[https:// | ||
+ | * Speicherung als CSV passiert am einfachsten über CSV schreiben: <file python writecsv.py> | ||
+ | |||
+ | # CSV-writer konfigurieren. | ||
+ | writer = csv.writer(outcsv, | ||
+ | |||
+ | for item in datalist: | ||
+ | #Jeden Eintrag der Datalist als Zeile ausgeben | ||
+ | writer.writerow([item[0], | ||
+ | |||
+ | # Wrtier schliessen | ||
+ | outcsv.close() | ||
+ | </ | ||
+ | === Lösungen === | ||
+ | <hidden Liste von Bilddateien> | ||
+ | <code python pixelist_from_directory.py> | ||
+ | |||
+ | import gpanel | ||
+ | import os #um Verzeichnisse zu listen | ||
+ | import csv #um CSV-Dateien zu lesen. | ||
+ | |||
+ | # Pfad zu den Bilddateien | ||
+ | digitsdirectory = ' | ||
+ | |||
+ | |||
+ | 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, | ||
+ | # siehe auch https:// | ||
+ | color = img.getPixelColor(x, | ||
+ | |||
+ | # 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(' | ||
+ | |||
+ | |||
+ | # leere Liste fuer alle Trainingsdaten der Form [-0.93, | ||
+ | |||
+ | trainingset = [] | ||
+ | |||
+ | # durch alle files im Ziffernverzeichnis loopen | ||
+ | for filename in [filename for filename in os.listdir(digitsdirectory) if filename.endswith(" | ||
+ | |||
+ | # 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) | ||
+ | |||
+ | </ | ||
+ | </ | ||
+ | |||
+ | ==== $k$ Nearest Neighbours auf Pixellisten ==== | ||
+ | |||
+ | === Ziele === | ||
+ | * $k$ nearest neighbours in $k$-Dimensionen durchführen | ||
+ | * Einem Bild aus den Testdaten einen Zahlwert auf Grund der Trainingsdaten zuordnen | ||
+ | Der Code unten soll als Grundlage für den eigentlichen kNN Klassifizierer gelten. Es muss einizg noch die Funktion '' | ||
+ | |||
+ | <code python stub_knn_digits.py> | ||
+ | |||
+ | import gpanel | ||
+ | import csv #um CSV-Dateien zu lesen. | ||
+ | |||
+ | # Pfad zu den Bilddateien | ||
+ | digitsdirectory = ' | ||
+ | |||
+ | |||
+ | # Trainingsdaten | ||
+ | trainingset = list(csv.reader(open(digitsdirectory + ' | ||
+ | # Testdate | ||
+ | testset = list(csv.reader(open(digitsdirectory + ' | ||
+ | |||
+ | |||
+ | |||
+ | 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, | ||
+ | # siehe auch https:// | ||
+ | color = img.getPixelColor(x, | ||
+ | |||
+ | # umlegen auf das Intervall [-1,1] zwecks Normalisierung | ||
+ | value = color.red / 255 * 2 - 1 | ||
+ | # an liste anhaengen | ||
+ | pixellist.append(value) | ||
+ | | ||
+ | return pixellist | ||
+ | |||
+ | def assignClass(point, | ||
+ | # Funktion die den Abstand von point zu den k naechsten | ||
+ | # Nachbarn im trainingset berechnet mit Pythagoras in | ||
+ | # 16x16=256 Dimensionen | ||
+ | | ||
+ | # gibt die Mehrheitsklasse wieder. Tip: Liste mit Häufigkeiten zurückgeben. | ||
+ | return(assignedclass) | ||
+ | |||
+ | ## Funktion Testen | ||
+ | |||
+ | # Auf einem Testbild | ||
+ | testpoint = getPixeListFromFilePath(digitsdirectory + ' | ||
+ | print(assignClass(testpoint, | ||
+ | |||
+ | # Auf Testdaten | ||
+ | for i in range(len(testset)): | ||
+ | print(assignClass(testset[i][0: | ||
+ | print(testset[i][256]) | ||
+ | </ | ||
+ | === Lösungen === | ||
+ | <hidden Loesung> | ||
+ | <code python convertimagetopixellist.py> | ||
+ | |||
+ | import gpanel | ||
+ | import os #um Verzeichnisse zu listen | ||
+ | import csv #um CSV-Dateien zu lesen. | ||
+ | |||
+ | # Pfad zu den Bilddateien | ||
+ | digitsdirectory = ' | ||
+ | |||
+ | |||
+ | 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, | ||
+ | # siehe auch https:// | ||
+ | color = img.getPixelColor(x, | ||
+ | |||
+ | # 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(' | ||
+ | |||
+ | |||
+ | # leere Liste fuer alle Trainingsdaten der Form [-0.93, | ||
+ | |||
+ | trainingset = [] | ||
+ | |||
+ | # durch alle files im Ziffernverzeichnis loopen | ||
+ | for filename in [filename for filename in os.listdir(digitsdirectory) if filename.endswith(" | ||
+ | |||
+ | |||
+ | # 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: | ||
+ | # trainingset = list(csv.reader(open(' | ||
+ | |||
+ | |||
+ | # Funktion, die einem Punkt eine Klasse auf Grund der k naechsten Nachbarn zuweist. | ||
+ | def assignClass(point, | ||
+ | |||
+ | # 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], | ||
+ | |||
+ | # das waere ein sehr Pythonesquer Weg mit Lambda-Funktionen | ||
+ | # nearest = sorted(distlist, | ||
+ | |||
+ | # 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, | ||
+ | |||
+ | # 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/ | ||
+ | # Wenn anstelle der Anzahl/ | ||
+ | # kann dies mit classcounts.index(max(classcounts)) passieren. | ||
+ | |||
+ | return classcounts | ||
+ | |||
+ | |||
+ | # Teste das Programm | ||
+ | |||
+ | testpoint = getPixeListFromFilePath(digitsdirectory + ' | ||
+ | print assignClass(testpoint, | ||
+ | testpoint = getPixeListFromFilePath(digitsdirectory + ' | ||
+ | print assignClass(testpoint, | ||
+ | testpoint = getPixeListFromFilePath(digitsdirectory + ' | ||
+ | print assignClass(testpoint, | ||
+ | testpoint = getPixeListFromFilePath(' | ||
+ | print assignClass(testpoint, | ||
+ | |||
+ | </ | ||
</ | </ |