Kapitel 2 – PCA & k-means

Folien: 📄 03_dimred.pdf · Woche 2, Prof. Franz

Worum geht es?

Reale Daten haben oft sehr viele Variablen: ein MNIST-Bild hat 784 Pixel, ein Microarray misst rund 30 000 Gene. Mit so vielen Dimensionen arbeiten Lernverfahren schlecht, und anschauen kann man die Daten auch nicht mehr. Das Kapitel behandelt zwei klassische unüberwachte Verfahren (unsupervised learning), die solche Daten vereinfachen:

• Die Hauptkomponentenanalyse (Principal Component Analysis, PCA) reduziert die Zahl der Variablen. Sie dreht das Koordinatensystem so, dass die Daten entlang der ersten Achsen möglichst stark streuen, und wirft die Achsen mit wenig Varianz weg. Mathematisch läuft das auf die Eigenwertzerlegung der Kovarianzmatrix hinaus.
• k-Means (Vektorquantisierung) reduziert die Zahl der Datenpunkte. Es fasst ähnliche Punkte zu $K$ Clustern zusammen und repräsentiert jeden Cluster durch seinen Mittelwert.

Beide Verfahren brauchen keine Labels. Sie dienen zur Visualisierung, zur Kompression und als Vorverarbeitung für spätere Klassifikatoren (z.B. Eigengesichter mit Naive Bayes im Praktikum, siehe Kapitel 3).

Vorwissen aus Kapitel 1: Erwartungswert, Varianz, Kovarianz. Aus der linearen Algebra: Eigenwerte und Eigenvektoren, Orthonormalbasen.

Aufbau des Kapitels

Abschnitt	Inhalt
2.1 Dimensionsreduktion & Kovarianz	Merkmalsselektion vs. -extraktion, Kovarianzmatrix, Varianz entlang einer Richtung $\mathbf q^\top\Sigma\mathbf q$
2.2 Herleitung der PCA	PCA als Optimierungsproblem, Lagrange-Multiplikatoren, Eigenwertgleichung, Scores, Dekorrelation
2.3 Eigenschaften der PCA	Kodieren und Dekodieren, optimale Rekonstruktion, erklärte Varianz, Beispiele, Grenzen, Algorithmus
2.4 Clusteranalyse	Was ist ein Cluster, Ähnlichkeitsmaße, partitionierende vs. hierarchische Verfahren, Datenreduktion durch Clustern
2.5 k-Means	Algorithmus, durchgerechnetes Beispiel, Zielfunktion, lokale Minima, Wahl von $K$, Probleme

Termin 3 („PCA I“) deckt ungefähr 2.1 und 2.2 ab, Termin 4 („PCA II / k-means“) den Rest.

Die wichtigsten Formeln auf einen Blick

Was	Formel
Kovarianzmatrix	$\Sigma = \mathcal E\big[(\mathbf x-\boldsymbol\mu)(\mathbf x-\boldsymbol\mu)^\top\big]$
Varianz in Richtung $\mathbf q$ ($\lVert\mathbf q\rVert=1$)	$\sigma^2(\mathbf q)=\mathbf q^\top\Sigma\mathbf q$
PCA-Bedingung	$\Sigma\mathbf q_i=\beta_i\mathbf q_i$
Scores	$a_i=\mathbf q_i^\top\mathbf x$ (zentrierte Daten)
Rekonstruktion mit $\ell$ Komponenten	$\hat{\mathbf x}=\sum_{i=1}^{\ell}a_i\mathbf q_i$
Rekonstruktionsfehler	$\mathcal E\lVert\mathbf x-\hat{\mathbf x}\rVert^2=\sum_{i=\ell+1}^{n}\beta_i$
Erklärte Varianz	$P_\ell=\sum_{i=1}^{\ell}\beta_i \big/ \sum_{i=1}^{n}\beta_i$
k-Means-Zuweisung	$\hat k_n=\arg\min_k\lVert\mathbf x_n-\boldsymbol\mu_k\rVert^2$
k-Means-Update	$\boldsymbol\mu_k=\sum_n r_{kn}\mathbf x_n \big/ \sum_n r_{kn}$

Prüfungsrelevant / Selbsttest

1. Was ist der Unterschied zwischen Merkmalsselektion und Merkmalsextraktion? Zu welcher Art gehört die PCA?

Antwort

Bei der Selektion wählt man eine Teilmenge der vorhandenen Variablen aus (die übrigen werden unverändert weggelassen). Bei der Extraktion berechnet man neue Variablen als Funktion aller alten. Die PCA ist Merkmalsextraktion: Jeder Score $a_i=\mathbf q_i^\top\mathbf x$ ist eine Linearkombination aller Originalvariablen.

2. Leite her, warum die Varianz der Daten entlang einer Einheitsrichtung $\mathbf q$ gleich $\mathbf q^\top\Sigma\mathbf q$ ist.

Antwort

Projektion: $a=\mathbf q^\top(\mathbf x-\boldsymbol\mu)$, also $\mathcal E[a]=0$. Dann $\sigma^2(\mathbf q)=\mathcal E[a^2]=\mathcal E[\mathbf q^\top(\mathbf x-\boldsymbol\mu)(\mathbf x-\boldsymbol\mu)^\top\mathbf q]=\mathbf q^\top\mathcal E[(\mathbf x-\boldsymbol\mu)(\mathbf x-\boldsymbol\mu)^\top]\mathbf q=\mathbf q^\top\Sigma\mathbf q$. Man nutzt $a^2=a\cdot a^\top$ (ein Skalar ist sein eigenes Transponiertes) und die Linearität des Erwartungswerts.

3. Warum braucht die PCA die Nebenbedingung $\mathbf q^\top\mathbf q=1$, und wie führt sie auf ein Eigenwertproblem?

Antwort

Ohne Nebenbedingung kann man $\mathbf q^\top\Sigma\mathbf q$ durch Skalieren von $\mathbf q$ beliebig groß machen, es gibt kein endliches Maximum. Mit Lagrange: $L=-\mathbf q^\top\Sigma\mathbf q+\beta(\mathbf q^\top\mathbf q-1)$, $\nabla_{\mathbf q}L=-2\Sigma\mathbf q+2\beta\mathbf q=0$, also $\Sigma\mathbf q=\beta\mathbf q$.

4. Was ist die Varianz entlang der $i$-ten Hauptkomponente, und warum sind alle Eigenwerte von $\Sigma$ nicht negativ?

Antwort

$\sigma^2(\mathbf q_i)=\mathbf q_i^\top\Sigma\mathbf q_i=\mathbf q_i^\top\beta_i\mathbf q_i=\beta_i$. Der Eigenwert ist die Varianz in dieser Richtung. Varianzen sind nie negativ, also $\beta_i\ge0$: $\Sigma$ ist positiv semidefinit. Die Komponente mit dem größten Eigenwert ist die Richtung maximaler Varianz.

5. Gegeben $\Sigma=\begin{pmatrix}2.5&2\\2&2.5\end{pmatrix}$. Bestimme die Hauptkomponenten und die erklärte Varianz der ersten.

Antwort

$\det(\Sigma-\beta I)=(2.5-\beta)^2-4=0\Rightarrow\beta=2.5\pm2$, also $\beta_1=4.5$, $\beta_2=0.5$. Eigenvektoren $\mathbf q_1=\tfrac1{\sqrt2}(1,1)^\top$, $\mathbf q_2=\tfrac1{\sqrt2}(1,-1)^\top$. Erklärte Varianz $4.5/5=90\,\%$. Siehe das durchgerechnete Beispiel.

6. Wie groß ist der mittlere quadratische Rekonstruktionsfehler, wenn man nur die ersten $\ell$ von $n$ Hauptkomponenten behält?

Antwort

Die Summe der weggelassenen Eigenwerte: $\mathcal E\lVert\mathbf x-\hat{\mathbf x}\rVert^2=\sum_{i=\ell+1}^n\beta_i$. Weil die PCA die kleinsten Eigenwerte weglässt, ist dieser Fehler unter allen $\ell$-dimensionalen Orthonormalbasen minimal.

7. Warum ist die PCA nicht immer gut geeignet, um Cluster zu trennen?

Antwort

Die PCA sucht Richtungen großer Varianz, nicht Richtungen guter Trennbarkeit. Sie kennt keine Labels und keine Clusterstruktur. Bei drei Clustern (📄 03_dimred.pdf, Folie 37) kann die Projektion auf die erste Komponente zwei Cluster übereinanderlegen. Außerdem findet sie nur lineare Strukturen.

8. Beschreibe die beiden Schritte von k-Means und erkläre, warum der Algorithmus immer terminiert.

Antwort

Zuweisung: jeder Punkt zum nächsten Zentrum. Anpassung: jedes Zentrum auf den Mittelwert seiner Punkte. Beide Schritte senken die Summe der quadrierten Abstände $J$ (oder lassen sie gleich). Es gibt nur endlich viele Zuordnungen der $N$ Punkte zu $K$ Clustern, also kann $J$ nicht unendlich oft echt sinken. Irgendwann ändert sich die Zuordnung nicht mehr.

9. Warum findet k-Means nicht unbedingt die beste Clusterung, und was tut man dagegen?

Antwort

$J$ hat lokale Minima, und k-Means ist ein Abstiegsverfahren, das vom Startwert abhängt (📄 03_dimred.pdf, Folie 45: zwei Läufe, zwei Ergebnisse). Das globale Optimum zu finden ist NP-hart. Praxis: mehrere Läufe mit verschiedenen Zufallsstarts, den mit kleinstem $J$ nehmen.

10. Wie wählt man die Anzahl der Cluster $K$ bei k-Means?

Antwort

„Ellenbogen“-Kriterium (📄 03_dimred.pdf, Folie 46): k-Means für mehrere $K$ laufen lassen, die summierte Varianz innerhalb der Cluster gegen $K$ auftragen und das $K$ nach dem letzten großen Abfall wählen. Den Minimalwert zu nehmen geht nicht, da die Varianz mit wachsendem $K$ immer weiter sinkt (bei $K=N$ ist sie 0).