Übungen: Unsupervised Learning

Aufgaben zu Kapitel 09 - Dimensionsreduktion (PCA, Autoencoder), Curse of Dimensionality, Clustering mit k-Means und seinen Varianten. Alle Fragen und Loesungen stuetzen sich ausschliesslich auf den Kapitelinhalt.

Beginner

Aufgabe 1 (Beginner) - Was ist Unsupervised Learning?

Welche Aussage beschreibt Unsupervised Learning korrekt?

a) Es optimiert ein Modell auf eine bekannte "richtige Antwort" (Label) hin. b) Es arbeitet mit Datensaetzen ohne Label und sucht Struktur direkt in den Daten. c) Es ist ein Spezialfall der Regression mit numerischem Ausgabewert. d) Es benoetigt fuer jedes Trainingsbeispiel eine von Hand vergebene Kategorie.

Lösung anzeigen

Richtig ist b).

Unsupervised Learning beschaeftigt sich mit Datensaetzen, ueber die wenig bekannt ist und die insbesondere kein Label besitzen. Im Gegensatz zum Supervised Learning gibt es keine "richtige Antwort", auf die hin optimiert wird - stattdessen wird versucht, Struktur direkt in den Daten zu finden.

a) und d) beschreiben Supervised Learning (Klassifikation/Regression).
c) ist falsch: Regression ist eine Supervised-Aufgabe mit Labels.

Die vier typischen Aufgaben ohne Label sind: Ausreissererkennung, Clustering, Dimensionsreduktion und Datengenerierung.

Siehe EKI09.

Aufgabe 2 (Beginner) - Die vier Aufgaben

Nennen Sie die vier Aufgaben des Unsupervised Learning und ordnen Sie jeder die passende Leitfrage zu.

Lösung anzeigen

Aufgabe	Leitfrage
Ausreissererkennung (anomaly / outlier detection)	Gibt es Daten, die stark von den anderen abweichen?
Clustering	Kann der Datensatz sinnvoll in wenige Untergruppen zerlegt werden?
Dimensionsreduktion (dimensionality reduction)	Gibt es Daten, die besonders aehnlich zueinander sind?
Datengenerierung (data generation)	Wie sehen aehnliche (neue) Daten aus?

Tipp: Merke dir die vier ueber ihre Gegensatzpaare: Ausreisser = das Ungewoehnliche finden, Clustering = Gruppen bilden, Dimensionsreduktion = Redundanz entfernen, Datengenerierung = Neues erzeugen.

Siehe EKI09.

Aufgabe 3 (Beginner) - Aufbau eines Autoencoders

Welche Reihenfolge der Bausteine beschreibt einen Autoencoder korrekt?

a) Decoder -> Latent Space -> Encoder -> Output b) Encoder -> Latent Space -> Decoder -> Output ( $\hat{x}$ ) c) Input -> Pooling -> Fully Connected -> Output d) Encoder -> Output -> Decoder -> Latent Space

Lösung anzeigen

Richtig ist b).

Ein Autoencoder ist ein neuronales Netz, das seinen eigenen Input rekonstruieren soll, dabei aber durch einen "Flaschenhals" gezwungen wird, die Daten komprimiert darzustellen:

graph LR
    X["x (Input)"] --> ENC["Encoder"]
    ENC --> L["Latent Space (Flaschenhals)"]
    L --> DEC["Decoder"]
    DEC --> XH["x-hat (Approximation)"]

Encoder: Projektion vom Input in den Latent Space (Dimensionsreduktion).
Latent Space: niedrig-dimensionaler Raum, der Flaschenhals.
Decoder: Transformation vom Latent Space zum Output.
Output $\hat{x}$ : moeglichst gute Approximation der Originaldaten.
c) beschreibt ein CNN (Computer Vision), nicht einen Autoencoder.

Siehe EKI09.

Aufgabe 4 (Beginner) - Euklidischer Abstand

Berechnen Sie den euklidischen Abstand der beiden Punkte $x = (0, 0)$ und $y = (3, 4)$ .

Lösung anzeigen

Formel fuer den euklidischen Abstand:

d(x, y) = \sqrt{ \sum_{i=1}^{p} (x_i - y_i)^2 }

Einsetzen:

d = \sqrt{(0-3)^2 + (0-4)^2} = \sqrt{9 + 16} = \sqrt{25} = 5

Tipp: Dieses 3-4-5-Dreieck ist der klassische Merkfall. k-Means nutzt genau dieses Distanzmass, um jeden Punkt dem naechsten Zentrum zuzuordnen.

Siehe EKI09.

Fortgeschritten

Aufgabe 5 (Fortgeschritten) - Min-Max-Normalisierung und Skalendominanz

Ein Kundendatensatz hat die Features Alter und jaehrliches Einkommen:

Kunde	Alter	Einkommen
A	25	30000
B	40	50000
C	60	80000

a) Warum dominiert das Einkommen den euklidischen Abstand, wenn man die Rohwerte direkt verwendet? b) Normalisieren Sie beide Features mit Min-Max-Normalisierung auf $[0, 1]$ .

Lösung anzeigen

a) Skalendominanz. Der euklidische Abstand quadriert die Differenzen pro Feature. Die Einkommensdifferenzen liegen im Bereich von Zehntausenden, die Altersdifferenzen nur bei einigen Dutzend. Beispiel A gegen C: Alter-Beitrag $(25-60)^2 = 1225$ , Einkommen-Beitrag $(30000-80000)^2 = 2\,500\,000\,000$ . Das Einkommen dominiert die Distanz vollstaendig, das Alter faellt praktisch weg - obwohl der Altersunterschied inhaltlich sehr gross ist.

b) Min-Max-Normalisierung mit

x' = \frac{x - x_{\min}}{x_{\max} - x_{\min}}

Alter: $x_{\min} = 25$ , $x_{\max} = 60$ , Spanne $= 35$ . Einkommen: $x_{\min} = 30000$ , $x_{\max} = 80000$ , Spanne $= 50000$ .

Kunde	Alter'	Einkommen'
A	$(25-25)/35 = 0$	$(30000-30000)/50000 = 0$
B	$(40-25)/35 = 0{,}4286$	$(50000-30000)/50000 = 0{,}4$
C	$(60-25)/35 = 1$	$(80000-30000)/50000 = 1$

Jetzt liegen beide Features im Bereich $[0, 1]$ und tragen vergleichbar zur Distanz bei.

Falle: "Normalisierung" hat im Kapitel zwei Bedeutungen. Hier (Clustering) meint sie Min-Max-Skalierung auf $[0,1]$ . Im PCA-Algorithmus meint dasselbe Wort dagegen nur das Zentrieren (Mittelwert null). Nicht verwechseln.

Siehe EKI09.

Aufgabe 6 (Fortgeschritten) - Zuordnung per euklidischem Abstand

Gegeben sind zwei Clusterzentren $m_1 = (2, 2)$ und $m_2 = (8, 8)$ sowie der Punkt $X = (3, 5)$ . Welchem Cluster wird $X$ zugeordnet? Rechnen Sie mit den quadrierten Abstaenden.

Lösung anzeigen

k-Means ordnet jeden Punkt dem Zentrum mit dem kleinsten (quadrierten) euklidischen Abstand zu:

C_i = \left\{ X_j : \| X_j - m_i \|^2 = \min_{p} \| X_j - m_p \|^2 \right\}

Abstand zu $m_1$ :

\| X - m_1 \|^2 = (3-2)^2 + (5-2)^2 = 1 + 9 = 10

Abstand zu $m_2$ :

\| X - m_2 \|^2 = (3-8)^2 + (5-8)^2 = 25 + 9 = 34

Da $10 < 34$ , wird $X$ dem Cluster $C_1$ (Zentrum $m_1$ ) zugeordnet.

Tipp: Fuer die reine Zuordnung reicht der quadrierte Abstand - die Wurzel aendert die Reihenfolge nicht und spart Rechenaufwand. Das entspricht exakt der Assignment-Formel der Folie.

Siehe EKI09.

Aufgabe 7 (Fortgeschritten) - Curse of Dimensionality

a) Wie gross ist der maximale Abstand (Raumdiagonale) im Einheitshyperwuerfel $[0,1]^n$ in Dimension $n$ ? b) Welches Volumen hat der Wuerfel $[0,2]^n$ , und was bedeutet das fuer wachsende $n$ ? c) Warum erschwert der Fluch der Dimensionalitaet statistische Analysen?

Lösung anzeigen

a) Bei konstantem Volumen $V_n = 1$ waechst die Raumdiagonale mit

d_n = \sqrt{n}

Also $d_1 = 1$ , $d_2 = \sqrt{2}$ , $d_3 = \sqrt{3}$ usw. Je hoeher die Dimension, desto groesser der moegliche Abstand zweier Punkte - bei gleichem Volumen.

b) Verdoppelt man die Seitenlaenge, waechst das Volumen exponentiell:

V([0,2]^n) = 2^n

Also $2, 4, 8, 16, \ldots$ Der Raum "blaeht sich auf".

c) Weil bei steigender Dimension die verfuegbaren Datenpunkte denselben, aber exponentiell groesseren Raum fuellen muessen, "verduennen" sich die Daten: Punkte liegen tendenziell weit voneinander entfernt, Distanzen werden weniger aussagekraeftig. Dieses Phaenomen heisst Curse of Dimensionality (nach R. Bellman) und motiviert die Dimensionsreduktion.

Falle: Eine Textextraktion der Folie gibt faelschlich $d_n = n$ an. Korrekt ist $d_n = \sqrt{n}$ (Raumdiagonale des Einheitshyperwuerfels).

Siehe EKI09.

Aufgabe 8 (Fortgeschritten) - k-Means und seine Varianten

Ordnen Sie jeder Variante ihren Unterschied zum klassischen k-Means zu.

Varianten: k-means++, k-medians, k-medoids. Beschreibungen:

Erlaubt als Clusterzentren nur Punkte aus dem Datensatz.
Waehlt die initialen Zentren sukzessive mit einer besseren Verteilung.
Nutzt statt des Mittelwerts den Median pro Cluster.

Lösung anzeigen

Variante	Beschreibung	Unterschied zu k-means
k-means++	2	waehlt Clusterzentren sukzessive mit unterschiedlicher Verteilung (bessere Initialisierung)
k-medians	3	nimmt den Median statt des Mittelwerts pro Cluster
k-medoids	1	erlaubt als Zentren nur Punkte aus dem Datensatz

Zur Erinnerung: Das klassische k-means waehlt die initialen Zentren zufaellig (gleichverteilt). Unguenstige Startzentren koennen zu schlechten Clustern fuehren - genau das verbessert k-means++.

Tipp: k-means++ aendert nur die Initialisierung. Das iterative Zuordnen und Neuberechnen der Zentren laeuft danach wie beim normalen k-Means.

Siehe EKI09.

Anspruchsvoll

Aufgabe 9 (Anspruchsvoll) - Eine k-Means-Iteration Schritt fuer Schritt

Gegeben sind sechs Punkte in 2D:

P_1=(1,2),\ P_2=(1,4),\ P_3=(2,2),\ P_4=(8,6),\ P_5=(9,5),\ P_6=(8,4)

mit $k = 2$ und den initialen Zentren $m_1 = (1,2)$ und $m_2 = (8,6)$ .

Fuehren Sie eine vollstaendige k-Means-Iteration durch: (a) Zuordnung aller Punkte, (b) Neuberechnung der Zentroide.

Lösung anzeigen

Schritt a) Zuordnung - je Punkt der kleinere quadrierte Abstand:

Punkt	$\\|X-m_1\\|^2$	$\\|X-m_2\\|^2$	Cluster
$P_1=(1,2)$	$0+0=0$	$49+16=65$	$C_1$
$P_2=(1,4)$	$0+4=4$	$49+4=53$	$C_1$
$P_3=(2,2)$	$1+0=1$	$36+16=52$	$C_1$
$P_4=(8,6)$	$49+16=65$	$0+0=0$	$C_2$
$P_5=(9,5)$	$64+9=73$	$1+1=2$	$C_2$
$P_6=(8,4)$	$49+4=53$	$0+4=4$	$C_2$

Ergebnis: $C_1 = \{P_1, P_2, P_3\}$ , $C_2 = \{P_4, P_5, P_6\}$ .

Schritt b) Update der Zentroide als Mittelwert der zugeordneten Punkte:

m_i = \frac{1}{|C_i|} \sum_{X_j \in C_i} X_j

m_1 = \left( \frac{1+1+2}{3},\ \frac{2+4+2}{3} \right) = \left( \frac{4}{3},\ \frac{8}{3} \right) \approx (1{,}33,\ 2{,}67)

m_2 = \left( \frac{8+9+8}{3},\ \frac{6+5+4}{3} \right) = \left( \frac{25}{3},\ 5 \right) \approx (8{,}33,\ 5{,}00)

Damit ist eine Iteration abgeschlossen. Im naechsten Schritt wuerde man erneut zuordnen; da die Gruppen stabil bleiben, konvergiert der Algorithmus. Konvergenz liegt vor, sobald sich die Zentren nicht mehr aendern.

Falle: Nach dem Update erst die Punkte neu zuordnen und dann pruefen, ob sich die Zuordnung geaendert hat - nicht nur die Zentren einmalig verschieben. Der Algorithmus wechselt strikt zwischen Zuordnung (Schritt 2) und Update (Schritt 3).

Siehe EKI09.

Aufgabe 10 (Anspruchsvoll) - PCA-Algorithmus und erklaerte Varianz

a) Bringen Sie die fuenf Schritte des PCA-Algorithmus in die richtige Reihenfolge. b) Nach einer PCA ergeben sich die folgenden Varianzen. Wie viel Prozent der Gesamtvarianz erklaeren PC1 und PC2 zusammen, und was folgt daraus?

Komponente	Varianz
PC1	0.00962
PC2	0.00287
PC3	0.00184
PC4	0.00131
PC5	0.00033

Lösung anzeigen

a) PCA-Algorithmus (5 Schritte):

Normalisiere die Features, sodass der Mittelwert jedes Features null ist (Zentrieren).
Berechne aus den Features die Kovarianzmatrix (symmetrische $n \times n$ Matrix).
Berechne die Eigenvektoren und ihre Eigenwerte aus $M x = \lambda x$ , $x \neq 0$ .
Sortiere die Eigenvektoren nach absteigendem Eigenwert.
Bilde die Hauptkomponenten als Linearkombinationen der Features (groesster Eigenwert -> PC1, zweitgroesster -> PC2, ...).

b) Erklaerte Varianz. Gesamtvarianz:

0{,}00962 + 0{,}00287 + 0{,}00184 + 0{,}00131 + 0{,}00033 = 0{,}01597

Anteil von PC1 und PC2:

\frac{0{,}00962 + 0{,}00287}{0{,}01597} = \frac{0{,}01249}{0{,}01597} \approx 0{,}782 = 78{,}2\,\%

PC1 und PC2 erklaeren zusammen rund 78 % der Gesamtvarianz. Weil der Grossteil der Varianz (= Information) in den ersten beiden Komponenten steckt, kann man die uebrigen Komponenten weglassen und die Daten in einem 2D-Plot (PC1 gegen PC2) darstellen.

Tipp: Schritt 1 heisst auf der Folie "Normalisieren", verlangt aber nur den Mittelwert null - das ist streng genommen ein Zentrieren, nicht dieselbe Operation wie die Min-Max-Normalisierung im Clustering.

Siehe EKI09.

Aufgabe 11 (Anspruchsvoll) - k-Means++ Initialisierung

Erklaeren Sie den Pseudocode der k-Means++-Initialisierung. Warum werden weit entfernte Punkte mit hoeherer Wahrscheinlichkeit als naechstes Zentrum gewaehlt?

1. Waehle (gleichverteilt) ein zufaelliges Clusterzentrum m_1.
Fuer j = 2, ..., k:
   2. Bestimme fuer jeden Punkt X:  D(X) = min_{i<j} ||X - m_i||
   3. Waehle m_j mit Wahrscheinlichkeit  P(X) = D^2(X) / sum_i D^2(X_i)

Lösung anzeigen

Ablauf:

Schritt 1: Das erste Zentrum $m_1$ wird gleichverteilt zufaellig aus dem Datensatz gezogen.
Schritt 2: Fuer jeden Punkt $X$ wird der Abstand zum naechstgelegenen bereits gewaehlten Zentrum bestimmt:

D(X) = \min_{i=1,\ldots,j-1} \| X - m_i \|

Schritt 3: Das naechste Zentrum $m_j$ wird zufaellig gezogen, aber mit einer Wahrscheinlichkeit proportional zu $D^2(X)$ :

P(X_j) = \frac{D^2(X)}{\sum_{i=1}^{n} D^2(X_i)}

Warum weit entfernte Punkte bevorzugt werden: Je groesser $D(X)$ , desto groesser $D^2(X)$ und damit die Auswahlwahrscheinlichkeit. Punkte, die weit von allen bisherigen Zentren liegen, werden also bevorzugt gezogen. Dadurch werden die Startzentren gut ueber den Datenraum gestreut, statt zufaellig dicht beieinander zu liegen. Das vermeidet die schlechten Cluster, die beim rein zufaelligen k-Means durch unguenstige Startzentren entstehen koennen.

Tipp: Die Quadrierung $D^2$ verstaerkt den Effekt: Ein doppelt so weit entfernter Punkt ist viermal so wahrscheinlich. Danach laeuft der normale k-Means (Zuordnung + Update) unveraendert weiter.

Siehe EKI09.

Klausur-Niveau

Aufgabe 12 (Klausur-Niveau) - Kundensegmentierung als angewandtes Szenario

Ein E-Commerce-Unternehmen moechte seine 201 Kunden anhand von Alter und jaehrlichem Einkommen in Segmente einteilen, um Werbung zu personalisieren.

a) Welche Unsupervised-Aufgabe und welches Verfahren sind hier passend, und warum ist das kein Supervised-Problem? b) Welcher Vorverarbeitungsschritt ist zwingend, bevor man k-Means anwendet, und warum? c) Der Parameter $k$ ist unbekannt. Was sagt der Foliensatz dazu?

Lösung anzeigen

a) Clustering mit k-Means. Die Aufgabe ist Clustering, weil Gruppen (Kundensegmente) im Datensatz gefunden werden sollen. Es ist kein Supervised-Problem, weil die Segmente nicht a priori gegeben sind - es existiert kein Label "Segment", auf das man trainieren koennte. Die Segmente werden erst durch das Clustering aus den Daten gebildet. Ziel ist die Personalisierung von Werbung sowie hoehere Kundenzufriedenheit und -loyalitaet.

b) Min-Max-Normalisierung. k-Means nutzt den euklidischen Abstand. Ohne Normalisierung wuerde das Einkommen (grosse Zahlen) die Distanz dominieren und das Alter praktisch verschwinden ("Alter 30 und 60 sind naeher als Einkommen 50000 und 50031"). Daher normalisiert man beide Features mit

x' = \frac{x - x_{\min}}{x_{\max} - x_{\min}}

auf $[0,1]$ , sodass beide vergleichbar zur Distanz beitragen ("Besser!").

c) Wahl von $k$ . Der Foliensatz gibt kein formales Auswahlkriterium an. Er zeigt denselben Datensatz mit $k = 2, 3, 4$ und stellt die Frage "Wie viele Cluster?" nur visuell/qualitativ. Methoden wie Elbow oder Silhouette werden nicht behandelt.

Falle: In der Klausur nicht die Elbow- oder Silhouette-Methode als "Loesung" nennen - der Foliensatz behandelt sie explizit nicht. Die Frage nach $k$ bleibt bewusst offen.

Siehe EKI09.

Aufgabe 13 (Klausur-Niveau) - PCA vs. Autoencoder und Datengenerierung

a) Vergleichen Sie PCA und Autoencoder als Verfahren zur Dimensionsreduktion. b) Erklaeren Sie, wie man mit beiden Verfahren neue Daten erzeugen kann. c) Warum sind gelernte Projektionen den drei einfachen Ansaetzen (Weglassen, Zufallsprojektion, Feature Engineering) ueberlegen?

Lösung anzeigen

a) PCA vs. Autoencoder:

Aspekt	PCA	Autoencoder
Art der Projektion	linear (Hauptkomponenten als Linearkombination)	nicht-linear (neuronales Netz)
Aufbau	Kovarianzmatrix, Eigenvektoren/-werte	Encoder - Latent Space - Decoder
Ordnung	Komponenten nach erklaerter Varianz sortiert	Latent Space als Flaschenhals
Weitere Anwendungen	2D-Plot, Datengenerierung	Noise Reduction, Outlier Detection, Datengenerierung

Der Autoencoder kann also auch nicht-lineare Strukturen erfassen, die die lineare PCA nicht abbildet.

b) Datengenerierung:

PCA: Man erzeugt neue Punkte im niedrigdimensionalen PC-Raum und transformiert sie zurueck in den Originalraum. So entstehen neue, plausible Daten (im Temperatur-Beispiel neue Kurven, die den Originalen aehneln).
Autoencoder: Ein zufaelliger Vektor im Latent Space wird durch den Decoder in neue Daten uebersetzt.

In beiden Faellen erzeugt man also im niedrigdimensionalen Raum einen neuen Punkt und bildet ihn in den hochdimensionalen Datenraum ab.

c) Ueberlegenheit gelernter Projektionen: Die drei einfachen Verfahren haben je einen Nachteil - Weglassen kann wichtige Information verlieren; Zufallsprojektionen sind nicht vorhersagbar (gut oder schlecht); Feature Engineering braucht Expertenwissen. PCA und Autoencoder lernen die Projektion selbststaendig und datenbasiert und maximieren dabei den Informationserhalt (PCA ueber die Varianz, Autoencoder ueber die Rekonstruktionsguete).

Tipp: Merksatz zur Datengenerierung: "Im kleinen Raum einen Punkt erzeugen, dann zurueck in den grossen Raum abbilden." Bei PCA ist das die Ruecktransformation, beim Autoencoder der Decoder.

Siehe EKI09.