TU Berlin – FG Angewandte Mathematik
Prof. Dr. Gabriele Steidl
Dr. Johannes Hertrich
Jonas Bresch
Numerische Mathematik I
Wintersemester 2023/24
Programmieraufgabe 2
In dieser Programmieraufgabe werden wir die Hauptkomponentenanalyse und den K-
Means-Algorithmus verwenden, um handgeschriebene Ziffern maschinell zu lernen. Als
Grundlage verwenden wir einen Ausschnitt des MNIST-Datensatzes, welcher aus Trainings-
und Testdaten sowie der Zuordnung zu den richtigen Ziffern besteht.
Die Bilder der Trainingsdaten können mit den Funktionen
• imgs = [Link](’train-images-idx3-ubyte’, dtype=np.uint8)
• imgs = [Link](imgs[16:], [-1, 28, 28])
geladen werden. Die zugehörigen Labels mit
• labs = [Link](’train-labels-idx1-ubyte’, dtype=np.uint8)
• labs = labs[8:]
Analog können die Testdaten eingelesen werden.
1. Schreibe zwei Funktionen, welche für eine gegebene Menge an Bildern {xn : n =
0, . . . , N − 1} pixelweise den empirischen Mittelwert und die empirische Varianz,
N −1 N −1
1 X 1 X
b= xn und V = (xn − b)2 ,
N N
n=0 n=0
berechnen, wobei das Quadrat komponentenweise angewendet wird. Benutze diese
Funktionen, um den Mittelwert und die Varianz aus den ersten 100 Trainingsbildern je
Ziffer zu bestimmen. Stelle die zehn berechneten Mittelwerte und Varianzen grafisch
dar.
1 Abgabe am: 05. Januar 2024
2. Für die Hauptkomponentenanalyse benötigen wir eine Eigenwertzerlegung der ska-
lierten empirischen Kovarianzmatrix S = Y Y T mit Y := [x0 − b, . . . , xN −1 − b], wobei
die Daten xn als Spaltenvektoren dargestellt wurden. Berechne die Eigenwerte der
Matrix S und die Singulärwerte von Y mittels entsprechender numpy-Funktionen für
die Kovarianzmatrix der ersten 1000 Trainingsbilder und stelle die ersten 50 Eigen-
werte und quadrierten Singulärwerte grafisch dar.
3. Schreibe eine Funktion, welche für einen gegebenen Datensatz den bestmöglichen
d-dimensionalen affinen Unterraum Hd = {At + b : t ∈ Rd }, sodass
N
X −1
(A, b) := argmin ||projHd (xn ) − xn ||22 ,
A,b n=0
bestimmt. Benutze diese Funktion, um den Mittelwert und die ersten fünf Hauptkom-
ponenten für die ersten 1000 Trainingsbilder zu bestimmen. Stelle den Mittelwert
und die Hauptkomponenten grafisch dar. Schreibe eine Funktion, welche ein Test-
Datum auf den bestimmten Unterraum Hd projiziert. Wähle vier beliebige Testdaten,
projiziere auf die ersten fünf Hauptkomponenten und stelle Testbild und Projektion
grafisch dar.
4. Implementiere den K-Means-Algorithmus. Erzeuge einen Datensatz bestehend aus
den ersten 1000 Trainingsbildern für zwei unterschiedliche Ziffern. Projiziere die Da-
ten auf die ersten beiden Hauptkomponenten der gewählten Daten mittels
AT (xn − b).
Verwende den K-Means-Algorithmus, um die reduzierten Daten in zwei Klassen ein-
zuteilen, wobei die ersten Klassenmittelpunkte den Mittelwerten der projizierten zwei
Ziffern entsprechen. Stelle die erhaltene Klassifizierung mit
[Link]
grafisch dar. Wähle nun für jede der beiden Ziffern 100 Testbilder aus und klassifi-
ziere diese. Stelle in einer Tabelle dar, wie viele Testbilder je Ziffer richtig und falsch
klassifiziert wurden.
Verwende außer skimage, numpy und matplotlib keine weiteren Pakete. Kommentiere
den Quellcode! Füge deiner Abgabe ein Hauptprogramm (Python-Skript) bei, welches ei-
genständig alle Ausgaben erzeugt. Beschrifte die Ausgaben direkt oder erläutere in einer
Readme-Datei in welcher Reihenfolge die Ausgaben erfolgen.
2 Abgabe am: 05. Januar 2024