EKI09 - Unsupervised Learning

Lernen ohne Labels: Dimensionsreduktion (PCA, Autoencoder), Ausreißererkennung, Datengenerierung und Clustering (k-Means, k-Means++) auf Datensätzen, über die wenig bekannt ist.

Überblick

Unsupervised Learning (unüberwachtes Lernen) beschäftigt sich mit Datensätzen, über die wenig bekannt ist und die insbesondere kein Label besitzen. Im Gegensatz zum Supervised Learning gibt es also keine "richtige Antwort", auf die hin optimiert wird - stattdessen versucht man, Struktur direkt in den Daten zu finden.

Beispiele für solche unlabeled Datensätze (Folie 9.4):

1. Gewicht, systolischer und diastolischer Blutdruck und HbA1c-Wert von 492,500 Personen
2. Uhrzeit, Anzahl der gekauften Artikel und Gesamtbetrag von 2,740,200 Transaktionen eines E-Commerce Unternehmens
3. Kursverläufe der S&P 500 Konzerne über einen Zeitraum von einem Jahr
4. Genexpressionsdaten von 97 Zelltypen mit je 2000 Genen

Hinweis: Die Zahlen "492,500" und "2,740,200" verwenden auf den (deutschsprachigen) Folien das englische Tausendertrennzeichen (Komma). Gemeint sind 492.500 Personen bzw. 2.740.200 Transaktionen. Original beibehalten.

Was wollen wir über solche Daten wissen?

Aufgabe	Frage	Deutsch / Englisch
Ausreißererkennung	Gibt es Daten, die stark von den anderen abweichen?	anomaly / outlier detection
Clustering	Kann der gesamte Datensatz sinnvoll in wenige Untergruppen auseinandergebrochen werden?	clustering
Dimensionsreduktion	Gibt es Daten, die besonders ähnlich zueinander sind?	dimensionality reduction
Datengenerierung	Wie sehen ähnliche Daten aus?	data generation

Einordnung in die KI-Landkarte

Auf der KI-Landkarte (Folie 9.3, nach B. Humm) gehört Unsupervised Learning zum Bereich Non-symbolic AI / Machine learning im Feld Learning (Machine learning, Information retrieval, Data mining). Zu den dort genannten Verfahren zählen u.a. Artificial Neural Networks, Support Vector Machines, lineare/logistische Regression, Random Forest, Gradient Boosting Tree, k-Nearest Neighbors, K-means und Naive Bayes.

graph TD
    A["Unsupervised Learning (keine Labels)"] --> B["Dimensionsreduktion"]
    A --> C["Clustering"]
    A --> D["Ausreissererkennung"]
    A --> E["Datengenerierung"]
    B --> B1["PCA"]
    B --> B2["Autoencoder"]
    C --> C1["k-Means / k-Means++"]
    E --> E1["PCA (neue Daten)"]
    E --> E2["Autoencoder (Latent Space)"]

---

Dimensionsreduktion

Warum überhaupt reduzieren? Der Fluch der Dimensionalität

Motivation (Folien 9.6-9.7): Betrachtet man Einheitsobjekte (Strecke, Quadrat, Würfel, ...) mit jeweils Volumen 1, so wächst der maximale Abstand zweier Punkte (die Raumdiagonale) mit der Dimension:

Dimension $n$	Objekt	Volumen $V_n$	max. Abstand (Diagonale) $d_n$
1	Strecke $[0,1]$	$1$	$d_1 = 1$
2	Quadrat $[0,1]^2$	$1$	$d_2 = \sqrt{2}$
3	Würfel $[0,1]^3$	$1$	$d_3 = \sqrt{3}$
allgemein	$[0,1]^n$	$V_n = 1$	$d_n = \sqrt{n}$

$$V_n = 1 \qquad \text{und} \qquad d_n = \sqrt{n}$$

Je höher die Dimension, desto größer die mögliche Distanz zwischen zwei Punkten (bei gleichem Volumen). Ein weiterer Effekt: Verdoppelt man die Seitenlänge, wächst der Raum exponentiell:

$$V([0,1]^n) = 1 \qquad\qquad V([0,2]^n) = 2^n$$

Konkret: $V([0,2]) = 2$, $V([0,2]^2) = 4 = 2^2$, ..., $V([0,2]^n) = 2^n$.

Dadurch werden statistische Analysen in hohen Dimensionen schwierig - die Daten "verdünnen" sich. Dieses Phänomen heißt:

Curse of dimensionality (Fluch der Dimensionalität) - R. Bellman

Hinweis: Die Textextraktion der Folie gibt fälschlich "$d_n = n$" an. Die Folienabbildung selbst zeigt korrekt $d_2 = \sqrt{2}$, $d_3 = \sqrt{3}$ und allgemein $d_n = \sqrt{n}$ (Raumdiagonale des Einheitshyperwürfels). Es handelt sich um einen Extraktionsfehler, nicht um einen Folienfehler.

Problemstellung

Sei $x = (x_1, x_2, \ldots, x_p) \in \mathbb{R}^p$. Wie können wir die Dimension von $x$ reduzieren?

Gesucht ist eine Projektion

$$\phi : \mathbb{R}^p \to \mathbb{R}^d \quad \text{mit } d < p$$

Beispiel (Folie 9.8): Temperaturkurven von 73 spanischen und 35 kanadischen Wetterstationen. Jede Kurve ist durch 365 Tageswerte gegeben, also $365$-dimensional ($\mathbb{R}^{365}$). Ziel: Reduktion z.B. auf $d = 2$.

Vier einfache Ansätze

graph LR
    P["x aus R^p"] --> M1["Daten weglassen"]
    P --> M2["Zufallsprojektion"]
    P --> M3["Feature Engineering"]
    P --> M4["gelernte Projektion (PCA / Autoencoder)"]
    M1 --> Z["y aus R^d, d < p"]
    M2 --> Z
    M3 --> Z
    M4 --> Z

1. Daten weglassen (Folie 9.9)

$$\phi(x) = (x_1, x_2, \ldots, x_d)$$

Beispiel: nur 2 statt 365 Temperaturwerte behalten. Aber: Welche Tage? 1. und 2. Januar (stark redundant, fast perfekt korreliert) oder 1. Januar und 1. Juli (informativer)? Es droht ggf. hoher Datenverlust. Sinnvoll nur bei offensichtlich redundanten Daten, z.B.

• (Temp. in °C, Temp. in °F) $\to$ (Temp. in °C)
• (Größe, Gewicht, BMI) $\to$ (Größe, Gewicht)

2. Zufallsprojektion (Folie 9.10)

Für jede Matrix $R \in \mathbb{R}^{p \times d}$ ist

$$\phi(x) = R\,x$$

eine Projektion von $\mathbb{R}^p$ auf $\mathbb{R}^d$. Bei der zufälligen Projektion wählt man eine zufällige Matrix $R$ und projiziert den Datensatz. Ergebnis kann gut oder schlecht sein, ist aber nicht vorhersagbar.

3. Feature Engineering (Folie 9.11)

Man erstellt neue, aussagekräftige Features, z.B.

$$\phi(x_1, x_2, \ldots, x_p) = \left( \min_{i=1,\ldots,p} x_i,\ \max_{i=1,\ldots,p} x_i \right)$$

also z.B. minimale und maximale Temperatur im Jahr. Für sinnvolle Features wird jedoch Expertenwissen benötigt.

Fazit der einfachen Verfahren (Folie 9.12)

Verfahren	Nachteil
Variablen weglassen	kann zum Verlust wichtiger Informationen führen
Zufällige Projektionen	kann zu guten oder schlechten Projektionen führen, aber nicht vorhersagbar
Feature Engineering	zur Erstellung sinnvoller Features wird Expertenwissen benötigt

Frage: Gibt es Methoden, die selbstständig und datenbasiert Projektionen lernen? Ja, zum Beispiel Hauptkomponentenanalyse und Autoencoder.

---

Hauptkomponentenanalyse (Principal Component Analysis, PCA)

Idee: Varianz als Information

Die PCA transformiert die ursprünglichen Features in neue, unkorrelierte Hauptkomponenten (principal components) PC1, PC2, ..., die nach der von ihnen erklärten Varianz geordnet sind. Die Varianz eines Features $x$ ist (Folie 9.14):

$$\mathrm{Varianz}(x) = \frac{1}{n-1} \sum_{i} (x_i - \bar{x})^2$$

Im Beispiel auf Folie 9.14 haben die fünf Originalfeatures $f_1, \ldots, f_5$ jeweils ähnlich kleine Varianzen (ca. $0{,}003$). Nach der PCA konzentriert sich die Varianz stark auf die ersten Komponenten:

Komponente	Varianz (ca.)
PC1	0.00962
PC2	0.00287
PC3	0.00184
PC4	0.00131
PC5	0.00033

Diese pro Komponente erklärte Varianz heißt erklärte Varianz (explained variance). Da der Großteil der Varianz in PC1 und PC2 steckt, kann man die übrigen Komponenten weglassen.

Anwendung: 2D-Plot (Folie 9.15)

"Darf man das überhaupt?" - Ja: Wir werfen alle Komponenten außer PC1 und PC2 weg, da sich die meiste Varianz der Daten nun in PC1 und PC2 befindet. Damit lässt sich ein 2-dimensionaler Plot erstellen, der vieles von den Daten erklärt. ("Warum nicht?")

Algorithmus (Folie 9.16)

PCA-Algorithmus:
1. Normalisiere die Features, sodass der Erwartungswert (Mittelwert)
   jedes Features null ist.
2. Berechne aus den n normalisierten Features die Kovarianzmatrix.
   -> symmetrische n x n Matrix
3. Berechne die n Eigenvektoren dieser Matrix und ihre zugehoerigen
   Eigenwerte:  M x = lambda x,  x != 0
4. Sortiere die Eigenvektoren nach absteigender Groesse ihrer Eigenwerte.
5. Bilde Linearkombinationen aus den Bestandteilen der Eigenvektoren
   und der Features:
     - Eigenvektor mit groesstem Eigenwert  -> Koeffizienten a_i -> PC1
     - Eigenvektor mit zweitgroesstem Eigenwert -> Koeffizienten b_i -> PC2
     - ...
     - Eigenvektor mit kleinstem Eigenwert -> letzte Hauptkomponente

Die Eigenwertgleichung lautet

$$M\,x = \lambda\,x, \qquad x \neq 0$$

Die Hauptkomponenten sind Linearkombinationen der Features $f_1, \ldots, f_n$:

$$PC_1 = a_1 f_1 + a_2 f_2 + \cdots + a_n f_n$$ $$PC_2 = b_1 f_1 + b_2 f_2 + \cdots + b_n f_n$$

wobei $(a_i)$ der Eigenvektor zum größten und $(b_i)$ der Eigenvektor zum zweitgrößten Eigenwert ist.

Hinweis: Schritt 1 heißt auf der Folie "Normalisiere die Features", verlangt aber nur, dass der Erwartungswert null wird - das ist streng genommen ein Zentrieren (Subtraktion des Mittelwerts), nicht eine vollständige Standardisierung/Skalierung. Der Begriff "Normalisierung" wird hier also lose verwendet (vgl. die andere Bedeutung von Normalisierung im Clustering-Beispiel unten). Außerdem steht $n$ hier für die Anzahl der Features (die Kovarianzmatrix ist $n \times n$), während $n$ an anderen Stellen des Foliensatzes für die Anzahl der Datenpunkte steht - eine Doppelbelegung des Symbols.

Beispiel: Temperaturkurven (Folien 9.17-9.20)

73 spanische Wetterstationen, jede Temperaturkurve $365$-dimensional, Projektion auf zwei Komponenten mit scikit-learn:

from sklearn.decomposition import PCA

model = PCA(n_components=2)
model.fit(X)
X_proj = model.transform(X)

Vollständiges Beispiel inklusive Plot (Folie 9.20). Die beiden markierten Zeilen model.fit(X) + model.transform(X) lassen sich zu fit_transform zusammenfassen:

import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
from sklearn.decomposition import PCA

def load_data() -> np.ndarray:
    filepath = "temperature_data_es.csv"
    df = pd.read_csv(filepath).to_numpy().transpose()
    return df

if __name__ == '__main__':
    X = load_data()
    model = PCA(n_components=2)
    X_proj = model.fit_transform(X)          # entspricht fit(X) + transform(X)
    plt.scatter(X_proj[:, 0], X_proj[:, 1])
    plt.xlabel("First principal component")
    plt.ylabel("Second principal component")
    plt.show()

Der resultierende Scatter-Plot (PC1 gegen PC2) verteilt die Stationen in der Ebene; beschriftet man die Punkte (Folie 9.19), erkennt man geografische Muster (Küsten- vs. Bergstationen wie NAVACERRADA).

Weitere Anwendung: Datengenerierung (Folie 9.21)

Mit der PCA kann man auch neue Daten erzeugen: Erzeugt man neue Punkte im niedrigdimensionalen PC-Raum und transformiert diese zurück, entstehen neue, plausible Temperaturkurven (im Plot orange, den originalen Kurven ähnlich).

---

Autoencoder

Ein Autoencoder ist ein neuronales Netz, das lernt, seinen eigenen Input möglichst gut zu rekonstruieren, dabei aber durch einen "Flaschenhals" (den Latent Space) gezwungen wird, die Daten komprimiert darzustellen (Folie 9.23).

graph LR
    X["x (Input, originale Daten)"] --> ENC["Encoder"]
    ENC --> L["Latent Space (niedrig-dimensionaler Raum)"]
    L --> DEC["Decoder"]
    DEC --> XH["x-hat (Output, Approximation)"]

Baustein	Funktion
Encoder	Projektion vom Input in den Latent Space (Dimensionsreduktion)
Latent Space	niedrig-dimensionaler Raum (der "Flaschenhals")
Decoder	Transformation vom Latent Space zum Output (unvollständige Rekonstruktion)
Output $\hat{x}$	(möglichst gute) Approximation der originalen Daten

Anwendungen (Folie 9.24)

• Dimensionsreduktion - nicht-linear gegenüber der linearen PCA.
• Entfernung von Rauschen (noise reduction) - Training mit Daten, denen Rauschen hinzugefügt wurde; die Kostenfunktion minimiert die Differenz zwischen dem Output und dem Originalbild ohne Rauschen.
• Ausreißererkennung (outlier detection) - schlecht rekonstruierbare Punkte sind verdächtig.
• Datengenerierung (data generation) - ein zufälliger Vektor im Latent Space wird durch den Decoder in neue Daten übersetzt.

---

Clustering

Clustering beantwortet die Frage (Folie 9.26): Gibt es Gruppen von Punkten, sodass Beobachtungen innerhalb einer Gruppe ähnlicher/näher sind als Punkte verschiedener Gruppen?

Beispiel: Kundensegmentierung (Customer Segmentation, Folie 9.27)

Warum Clustering? Um Aussagen über Gruppen im Datensatz zu machen (z.B. Kundensegmente).

Ziel: Personalisierung von Werbung; Erhöhung von Kundenzufriedenheit und -loyalität.

Daten: Alter und jährliches Einkommen von 201 Kunden.

Ergebnis: Zuordnung der Kunden zu Kundensegmenten. Weitere mögliche Daten: Online-Verhalten, demografische Daten, ...

Wichtig: Kundensegmente sind nicht a priori gegeben! Sie werden erst durch das Clustering aus den Daten gebildet.

Wie viele Cluster? (Folien 9.28, 9.37)

Die Anzahl $k$ der Cluster ist ein Parameter, der vorgegeben werden muss. Der Foliensatz zeigt denselben Datensatz mit unterschiedlichen $k$ (z.B. $k = 2, 3, 4$) und stellt die Frage "Wie viele Cluster gibt es?", ohne ein formales Auswahlkriterium anzugeben.

Hinweis: Methoden zur automatischen Bestimmung der Clusteranzahl (z.B. Elbow-Methode oder Silhouette-Koeffizient) werden in diesem Foliensatz nicht behandelt. Die Frage "Wie viele Cluster?" wird nur visuell/qualitativ aufgeworfen. Ebenso wird die Cluster-Güte nur informell über die Wahl geeigneter Merkmalsskalen diskutiert (siehe Normalisierung unten), nicht über ein numerisches Bewertungsmaß.

Distanzmaß und die Bedeutung der Skalierung (Folien 9.29-9.30)

k-Means nutzt den euklidischen Abstand. Für zwei Punkte $x, y \in \mathbb{R}^p$:

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

Das ist problematisch, wenn Features unterschiedliche Wertebereiche haben. Auf Folie 9.29 gilt: "Alter 30 und 60 sind näher als Einkommen 50000 und 50031" - obwohl der Altersunterschied inhaltlich riesig, der Einkommensunterschied winzig ist. Das Einkommen dominiert also die Distanz.

Lösung: Min-Max-Normalisierung aller Features vor dem Clustering (Folie 9.30, "Besser!"):

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

# Folie 9.29: OHNE Normalisierung (Einkommen dominiert)
import matplotlib.pyplot as plt
import pandas as pd
from sklearn.cluster import KMeans

filepath = "customer_segmentation.csv"
df = pd.read_csv(filepath)

num_clusters = 3
model = KMeans(n_clusters=num_clusters)
model.fit(df)
df['Cluster'] = model.predict(df)

for cluster in range(num_clusters):
    cluster_data = df[df['Cluster'] == cluster]
    plt.scatter(cluster_data['Age'], cluster_data['Annual_Income'])

plt.xlabel('Age')
plt.ylabel('Annual Income')
plt.show()

# Folie 9.30: MIT Min-Max-Normalisierung -> "Besser!"
df_norm = (df - df.min()) / (df.max() - df.min())

num_clusters = 3
model = KMeans(n_clusters=num_clusters)
model.fit(df_norm)
df_norm['Cluster'] = model.predict(df_norm)

Hinweis zur Begriffsnutzung: "Normalisierung" meint hier Min-Max-Skalierung auf $[0,1]$, während dasselbe Wort im PCA-Algorithmus (Folie 9.16) das Zentrieren auf Mittelwert null bezeichnet. Zwei verschiedene Operationen, gleicher Name - auf die Unterscheidung achten.

---

Clustering-Algorithmen: k-Means

Grundidee (Folie 9.32)

• Initiale Wahl von zufälligen Clusterzentren.
• Bestimmen und iteratives Update der Clusterzentren, bis Konvergenz.

Die Folie zeigt diesen Ablauf als vierteilige Bildsequenz: von willkürlich gesetzten Zentren über wechselnde Zuordnungen bis zur stabilen Aufteilung.

Formale Definition (Folie 9.33)

Gegeben:

• Datensatz $X_1, \ldots, X_n$
• Gewünschte Anzahl $k$ der Cluster

Gesucht:

• Cluster $C_1, \ldots, C_k$ mit ihren zugeordneten $X_j$
• Clusterzentren (Zentroide) $m_1, \ldots, m_k$ für jedes der $k$ Cluster

Pseudocode

k-Means Algorithmus:

1. Waehle zufaellig k Datensaetze, um die initialen Clusterzentren
   m_1, ..., m_k festzulegen.

2. Ordne jeden Datensatz demjenigen Cluster zu, dessen Zentrum am
   naechsten liegt (kleinster euklidischer Abstand):

     C_i = { X_j : ||X_j - m_i||^2 = min_{p=1,...,k} ||X_j - m_p||^2 }

3. Berechne fuer jedes Cluster sein Clusterzentrum neu als Mittelwert
   der zugeordneten Datenpunkte:

     m_i = (1 / |C_i|) * sum_{X_j in C_i} X_j

4. Wiederhole Schritte 2 und 3, bis sich die Clusterzentren m_i nicht
   mehr veraendern (Konvergenz).

Die zentralen Formeln (Folie 9.33):

Zuordnung (Assignment):

$$C_i = \left\{ X_j : \| X_j - m_i \|^2 = \min_{p=1,\ldots,k} \| X_j - m_p \|^2 \right\}$$

Update der Zentroide:

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

graph TD
    S1["1. k zufaellige Zentren waehlen"] --> S2["2. Zuordnung: jeden Punkt zum naechsten Zentrum"]
    S2 --> S3["3. Update: Zentrum = Mittelwert der zugeordneten Punkte"]
    S3 --> S4{"Zentren veraendert?"}
    S4 -->|"ja"| S2
    S4 -->|"nein"| S5["fertig: stabile Cluster"]

Kleines durchgerechnetes Beispiel (eine Iteration)

Hinweis: Die folgenden konkreten Zahlen stehen nicht auf den Folien; sie sind eine didaktische Rekonstruktion einer einzelnen Iteration und folgen exakt den Formeln von Folie 9.33. Folie 9.32 zeigt den Ablauf nur bildlich.

Gegeben seien fünf 1D-Punkte $\{1, 2, 3, 10, 11\}$ und $k = 2$.

1. Initiale Zentren (zufällig gewählt): $m_1 = 2$, $m_2 = 10$.
2. Zuordnung (jeder Punkt zum näheren Zentrum):
   • $1 \to m_1$ (Abstand 1 vs. 9)
   • $2 \to m_1$ (0 vs. 8)
   • $3 \to m_1$ (1 vs. 7)
   • $10 \to m_2$ (8 vs. 0)
   • $11 \to m_2$ (9 vs. 1)
   • $C_1 = \{1,2,3\}$, $C_2 = \{10,11\}$
3. Update:
   • $m_1 = \frac{1+2+3}{3} = 2$
   • $m_2 = \frac{10+11}{2} = 10{,}5$
4. Nächste Zuordnung ändert nichts mehr an den Mengen $\to$ Konvergenz. Endgültige Zentren: $m_1 = 2$, $m_2 = 10{,}5$.

scikit-learn (Folie 9.34)

from sklearn.cluster import KMeans

model = KMeans(n_clusters=k)
model.fit(data)
prediction = model.predict(data)

Beispiel: Wetterstationen (Folien 9.35-9.37)

Temperaturkurven von 73 spanischen und 35 kanadischen Wetterstationen werden per Feature Engineering auf 2D reduziert (Min./Max.-Temperatur) und dann geclustert:

import matplotlib.pyplot as plt
import numpy as np
from sklearn.cluster import KMeans
from pca_example import load_data

if __name__ == '__main__':
    data, labels = load_data('both')
    # 365-dim Kurven -> 2D: (min, max) je Station
    data_2d = np.stack([np.min(data, axis=-1), np.max(data, axis=-1)], axis=-1)

    fig, axes = plt.subplots(3, sharex=True, sharey=True)
    for k, ax in zip([2, 3, 4], axes):
        model = KMeans(n_clusters=k)
        model.fit(data_2d)
        pred = model.predict(data_2d)
        ax.scatter(data_2d[:, 0], data_2d[:, 1], c=pred)

    plt.show()

Die drei Subplots zeigen dieselben Daten mit $k = 2, 3, 4$ und illustrieren erneut die offene Frage "Wie viele Cluster?".

---

k-Means-Varianten

Motivation (Folie 9.38)

k-Means wählt die initialen Clusterzentren zufällig (gleichverteilt). Ist das sinnvoll? Ungünstige Startzentren können zu schlechten Clustern führen. Varianten:

Variante	Unterschied zu k-Means
k-means	wählt initiale Clusterzentren zufällig (gleichverteilt)
k-means++	wählt Clusterzentren sukzessive mit unterschiedlicher Verteilung (bessere Initialisierung)
k-medians	wählt statt des Mittelwerts jeweils den Median pro Cluster
k-medoids	erlaubt als Clusterzentren nur Punkte aus dem Datensatz

k-Means++ Algorithmus (Folie 9.39)

k-Means++ verbessert nur die Auswahl der initialen Clusterzentren. Alles Weitere - das iterative Zuordnen der Punkte und die Neuberechnung der Zentren - verläuft wie beim normalen k-Means.

k-Means++ Initialisierung:

1. Waehle (gleichverteilt) ein zufaelliges Clusterzentrum m_1 aus dem
   Datensatz.

Fuer j = 2, ..., k:
   2. Bestimme fuer jeden Punkt X den Abstand zum naechsten bereits
      bekannten Clusterzentrum:

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

   3. Waehle das naechste Clusterzentrum m_j aus allen Punkten mit einer
      Wahrscheinlichkeit proportional zu D^2(X):

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

Die Formeln (Folie 9.39):

$$D(X) = \min_{i=1,\ldots,j-1} \| X - m_i \|$$ $$P(X_j) = \frac{D^2(X)}{\displaystyle\sum_{i=1}^{n} D^2(X_i)}$$

Punkte, die weit von den bereits gewählten Zentren entfernt sind, werden also mit höherer Wahrscheinlichkeit als neue Zentren gezogen - das streut die Startzentren gut über den Datenraum.

---

Übersicht weiterer Clustering-Algorithmen (Folie 9.40)

Der Foliensatz zeigt abschließend die bekannte scikit-learn-Vergleichsgrafik (plot_cluster_comparison) mit dem Verhalten verschiedener Algorithmen auf unterschiedlich geformten Datensätzen (konzentrische Kreise, Halbmonde, Blobs, anisotrope Blobs, gleichverteiltes Rauschen). Genannte Verfahren:

MiniBatch KMeans, Affinity Propagation, MeanShift, Spectral Clustering, Ward, Agglomerative Clustering, DBSCAN, HDBSCAN, OPTICS, BIRCH, Gaussian Mixture.

Kernbeobachtung der Grafik: k-Means-artige Verfahren finden nur "runde"/konvexe Cluster gut, während dichtebasierte (DBSCAN/HDBSCAN/OPTICS) auch Kreise und Halbmonde korrekt trennen.

Hinweis: Diese weiteren Algorithmen (inkl. hierarchischem/agglomerativem Clustering wie Ward und DBSCAN) erscheinen ausschließlich als Namen in der Vergleichsabbildung. Ein Dendrogramm sowie Details/Formeln zu diesen Verfahren werden nicht gezeigt. Prüfungsrelevant im Detail ist aus dem Bereich Clustering nur k-Means (und k-Means++).

---

Prüfungsrelevanz

• Unsupervised vs. Supervised: Unsupervised Learning arbeitet ohne Labels; Ziele sind Ausreißererkennung, Clustering, Dimensionsreduktion und Datengenerierung.
• Curse of Dimensionality: Verständnis von $V_n = 1$, $d_n = \sqrt{n}$ und dem exponentiellen Volumenwachstum $V([0,2]^n) = 2^n$ (nach R. Bellman).
• Vier einfache Reduktionsverfahren und ihre Nachteile: Weglassen, Zufallsprojektion ($\phi(x) = Rx$), Feature Engineering (min/max), gelernte Projektionen.
• PCA-Algorithmus in 5 Schritten: zentrieren, Kovarianzmatrix, Eigenvektoren/Eigenwerte ($Mx = \lambda x$), nach Eigenwert sortieren, Hauptkomponenten als Linearkombination. Konzept der erklärten Varianz.
• PCA-Anwendungen: 2D-Visualisierung (PC1/PC2), Datengenerierung. scikit-learn: PCA(n_components=2).fit_transform(X).
• Autoencoder: Aufbau Encoder - Latent Space - Decoder; nichtlineare Dimensionsreduktion, Noise Reduction, Outlier Detection, Datengenerierung.
• k-Means: Pseudocode (Init, Zuordnung, Update, Wiederholung), euklidischer Abstand, Assignment- und Zentroid-Formel; Konvergenz, wenn sich Zentren nicht mehr ändern.
• Bedeutung der Normalisierung vor k-Means (Skalen-Dominanz); Min-Max-Formel.
• k-Means-Varianten: k-means++, k-medians, k-medoids; k-Means++-Initialisierung mit $D(X)$ und $P(X_j) \propto D^2(X)$.
• Wichtige Formeln: euklidischer Abstand $\sqrt{\sum (x_i - y_i)^2}$; Varianz $\frac{1}{n-1}\sum (x_i - \bar x)^2$; Zentroid $\frac{1}{|C_i|}\sum X_j$.

---

Mini-Test

Mini-Test "Unsupervised Learning" (Folie 9.41), verbatim:

• Was ist Unsupervised Learning?
• Was ist das Ziel der Clusteranalyse?
• Was sind Ausreißer? Warum wollen wir sie detektieren?
• Wo spielt die Generierung neuer Daten eine Rolle?
• Warum wollen wir die Dimension von Datensätzen reduzieren?
• Welche Möglichkeiten der Dimensionsreduktion gibt es?
• Wie können wir mit Hilfe der Hauptkomponentenanalyse neue Daten erzeugen?
• Wie sind Autoencoder aufgebaut?
• Wie können wir mit Autoencodern die Dimension reduzieren?
• Wie funktioniert der k-Means Algorithmus?