Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

Dimensionsreduktion: Hauptkomponentenanalyse (PCA)

Heinrich-Heine Universität Düsseldorf

Vorlesungsaufzeichnung Hauptkomponentenanalyse (VL 18)

PCA

Die Principal Component Analysis (Hauptkomponentenanalyse) ist ein unsupervised Verfahren, bei dem eine Koordinatentransformation auf den Daten vorgenommen wird, sodass die neuen Koordinatenachsen geordnet sind danach, wo die Daten die höhere Varianz aufweisen. Eine sehr häufige Anwendung ist eine Projektion auf die ersten (wenigen) Koordinaten nach einer PCA, um die Anzahl der Dimensionen zu reduzieren ohne dabei zu viel Informationen aus den Daten wegzuwerfen.

Wenn jemand „wir machen eine PCA“ sagt, sind meist die Schritte 1–2 gemeint, oft auch 1–3:

  1. fit — aus den Daten eine lineare, invertierbare Koordinatentransformation berechnen, genauer: eine Orthonormalbasis. Die neuen Koordinatenachsen heißen Hauptkomponenten oder Hauptachsen und sind danach geordnet, in welcher Richtung die Daten die höhere Varianz aufweisen.

  2. transform — die Transformation auf Daten anwenden. Das dürfen auch andere Daten sein als die, aus denen sie berechnet wurde; genau deshalb sind es zwei Schritte.

  3. Dimensionsreduktion — die transformierten Daten auf die ersten Hauptkomponenten projizieren, also auf einen niedrigdimensionalen linearen Unterraum.

In scikit-learn heißen die ersten beiden Schritte genau so (PCA().fit(x), pca.transform(x), und fit_transform für beides auf einmal), und Schritt 3 steckt im Parameter n_components: PCA(n_components=2) wirft beim Transformieren alle Hauptkomponenten außer den ersten beiden weg. Wer n_components weglässt, bekommt nur eine Drehung des Koordinatensystems und verliert nichts.

Die beiden Abbildungen zeigen genau diese zwei Fälle. Blau sind die Originaldaten im Raum, grau ihre Projektionen auf die Koordinatenebenen; eingeblendet ist die Differenz der Gesamtvarianz vor und nach der Projektion auf die xyxy-Ebene.

Fall (a): z ist konstant 1. Die Projektion auf die xy-Ebene hat exakt dieselbe Gesamtvarianz wie die Originaldaten — die dritte Koordinate trägt keine Information.

Figure 1:Fall (a): zz ist konstant 1. Die Projektion auf die xyxy-Ebene hat exakt dieselbe Gesamtvarianz wie die Originaldaten — die dritte Koordinate trägt keine Information.

Fall (b): z \sim \mathcal{N}(1,\ 0{,}1^2). Jetzt geht bei der Projektion etwas verloren, aber nur 0{,}01 von einer Gesamtvarianz von 2{,}28 — weniger als ein halbes Prozent.

Figure 2:Fall (b): z∼N(1, 0,12)z \sim \mathcal{N}(1,\ 0{,}1^2). Jetzt geht bei der Projektion etwas verloren, aber nur 0,010{,}01 von einer Gesamtvarianz von 2,282{,}28 — weniger als ein halbes Prozent.

Fall (b) ist der realistische: Eine Koordinate ist nie exakt konstant, sie schwankt nur wenig. Die PCA macht daraus eine quantitative Aussage — sie sagt nicht nur, dass man projizieren darf, sondern auch, wie viel Varianz das kostet (in scikit-learn pca.explained_variance_ratio_).

Eine Koordinatentransformation ist nichts anderes als eine Matrixmultiplikation mit einer invertierbaren quadratischen Matrix. So eine Matrix kann in jede Richtung stauchen oder strecken und außerdem um jede Achse um einen Winkel drehen oder scheren. Das Ziel der PCA ist es, Koordinaten zu finden, sodass in der ersten Achse, der xx-Achse, die höchste Varianz vorliegt. Erinnerung: Bei einer Matrix, interpretiert als lineare Abbildung durch Matrixmultiplikation, sind die Bilder der Basisvektoren genau die Spalten der Matrix. Wenn wir einen Vektor bestimmen können, der die Richtung der größten Varianz angibt, können wir diesen in eine Matrix als erste Spalte schreiben und auf den Untervektorraum projizieren, der orthogonal zu diesem Vektor ist (d.h. wir betrachten alle Vektoren, die mit unserer ersten Matrixspalte einen rechten Winkel haben, da bleibt ein Vektorraum eine Dimension kleiner übrig). Induktiv können wir nun weitermachen um eine Matrix MM zu bestimmen. Die Umkehrabbildung M−1M^{-1} ist dann eine Transformation, die die Richtung der größten Varianz auf den ersten Einheitsbasisvektor abbildet, also auf die xx-Achse.

Weil wir jede Hauptachse normieren und die nächste immer im Orthogonalkomplement der bisherigen suchen, sind die Spalten von MM normiert und stehen paarweise senkrecht aufeinander, sie bilden also eine Orthonormalbasis. Eine solche Matrix heißt orthogonal (auch: Orthonormalmatrix). Für sie gilt M⊤M=IM^\top M = I (Einheitsmatrix), also M−1=M⊤M^{-1} = M^\top: Die Rücktransformation ist einfach die Transponierte, das Invertieren ist geschenkt. Warum die Hauptachsen von selbst senkrecht aufeinander stehen, sehen wir am Ende der Herleitung unten.

Leider haben wir bisher noch nicht festgestellt, wie man die Richtung der größten Varianz herausfindet.

Herleitung

Diese Beispiele bringen uns darauf, uns vorzustellen, welche Matrix MM die beobachteten Daten aus einer Standardnormalverteilung hervorgebracht haben könnte (zumindest, bei welcher das am plausibelsten wäre). Genau die Eigenvektoren zum größten Eigenwert von MM sind dabei die Richtungen der größten Varianz.

So eine Kovarianzmatrix kann man immer aufstellen. Wenn wir das mit unseren echten Daten machen, und dann daraus eine “Wurzel” ziehen könnten, dann hätten wir die Matrix MM bestimmt. Zum Glück haben Kovarianzmatrizen eine besondere Eigenschaft: sie sind positiv definit und symmetrisch. (Im Kapitel Multivariate Normalverteilung haben wir gesehen, dass die Kovarianzmatrix die Ellipsen der Dichte beschreibt; die Eigenvektoren, die wir jetzt berechnen, sind genau die Achsen dieser Ellipsen.)

Um diese Matrix Σ\Sigma zu bestimmen, gibt es eine sehr einfache Möglichkeit, wenn CC eine Diagonalmatrix mit lauter positiven Einträgen ist, denn dann ist Σ\Sigma eine Diagonalmatrix, deren Einträge die jeweiligen Wurzeln sind. Wenn aber CC keine Diagonalmatrix ist, dann gibt es Verfahren, die Koordinaten zu wechseln, um aus CC eine Diagonalmatrix zu machen. Das bedeutet mathematisch, dass man CC ersetzen kann durch eine Transformation TT rückwärts, dann eine Diagonalmatrix C′C', dann die Transformation TT vorwärts. In Formeln: C=TC′T−1C = T C' T^{-1}.

Angenommen, wir hätten eine derartige Zerlegung bestimmt (man sagt auch: eine Eigenraumzerlegung), dann können wir Σ′\Sigma' als Wurzel zu C′C' berechnen und Σ=TΣ′T−1\Sigma = T \Sigma' T^{-1} erfüllt

Σ2=TΣ′T−1TΣ′T−1=TΣ′2T−1=TC′T−1=C.\Sigma^2 = T \Sigma' T^{-1} T \Sigma' T^{-1} = T \Sigma'^2 T^{-1} = T C' T^{-1} = C.

Die gesuchte Matrix TT erfüllt C=TC′T−1C = T C' T^{-1}, umgestellt also CT=TC′C T = T C'. Das bedeutet für jede Spalte v=T,iv = T_{,i} von TT und dem ii-ten Diagonaleintrag αi\alpha_i von C′C' eine Gleichung Cv=vαiC v = v \alpha_i, d.h. die Spalten von TT sind genau die Eigenvektoren von CC und die Diagonaleinträge von C′C' sind genau die Eigenwerte von CC zu diesen Eigenvektoren.

Dass Eigenvektoren zu verschiedenen Eigenwerten senkrecht aufeinander stehen, kann man in einer Zeile nachrechnen: Sind Cv1=λ1v1C v_1 = \lambda_1 v_1 und Cv2=λ2v2C v_2 = \lambda_2 v_2 mit λ1≠λ2\lambda_1 \neq \lambda_2, so ist wegen C=C⊤C = C^\top

λ1v1⊤v2=(Cv1)⊤v2=v1⊤Cv2=λ2v1⊤v2,\lambda_1 v_1^\top v_2 = (C v_1)^\top v_2 = v_1^\top C v_2 = \lambda_2 v_1^\top v_2,

also (λ1−λ2) v1⊤v2=0(\lambda_1 - \lambda_2)\, v_1^\top v_2 = 0 und damit v1⊤v2=0v_1^\top v_2 = 0. Normiert man die Eigenvektoren noch, so ist T⊤TT^\top T die Matrix aller Skalarprodukte vi⊤vjv_i^\top v_j, also die Einheitsmatrix. Das ist der Grund, warum die “Rotation” der PCA (die Matrix MM aus dem Abschnitt über Koordinatentransformationen oben) durch bloßes Transponieren invertiert wird, T−1=T⊤T^{-1} = T^\top, was auch der Code unten ausnutzt.

Damit haben wir also alle Zutaten beisammen, wenn wir nur irgendwie die Eigenvektoren der Kovarianzmatrix bestimmen können!

Ein gutes Verfahren, um den Eigenvektor zum größten Eigenwert zu bestimmen: fange mit einem zufälligen Vektor an und wende die Matrix darauf an. Wenn es ein Eigenvektor ist - gut, merken wir. Wenn nicht, so wird der Vektor dadurch in eine Richtung abgebildet, die mit höherer Wahrscheinlichkeit etwas mehr in Richtung des Eigenvektors zum größten Eigenwert zeigt. Wenden wir die Matrix also wiederholt an, ist die Chance groß, immer näher an einen Eigenvektor zu kommen.

Ein weniger effizientes Verfahren ist das, was Sie in der linearen Algebra gelernt haben sollten: man bestimmt zunächst die Eigenwerte als Nullstellen des charakteristischen Polynoms det⁡(M−XId)\det(M - X Id) und für jeden Eigenwert α\alpha bestimmt man den Eigenraum Ker(M−αId)Ker(M - \alpha Id) mit dem Gaussverfahren, d.h. man löst die Gleichung Mv=αvMv = \alpha v.

Numpy und scikit-learn greifen auf LAPACK zurück, was in Fortran geschrieben ist und eine Singulärwertzerlegung (die Zerlegung C=TC′T−1C = TC' T^{-1}) in zwei Schritten durchführt. Wir wollen uns darüber nicht länger den Kopf zerbrechen, denn das gehört in eine Lineare Algebra- oder Numerik-Vorlesung. Wir wollen natürlich trotzdem den Rechner zur Hilfe nehmen:

[2.75 1.5 ]
[[-0.89442719  0.4472136 ]
 [-0.4472136  -0.89442719]]
die Transformation T ist in diesem Beispiel:
[[-0.89442719 -0.4472136 ]
 [-0.4472136   0.89442719]]

Die Eigenwerte sind die Varianzen der Daten entlang der zugehörigen Eigenvektoren, der Hauptkomponenten. Ihr Anteil an der Gesamtvarianz tr⁡(C)=2.5+1.75=4.25\operatorname{tr}(C) = 2.5 + 1.75 = 4.25, hier also 2.75/4.25≈65%2.75/4.25 \approx 65\% und 1.5/4.25≈35%1.5/4.25 \approx 35\%, heißt erklärte Varianz (explained variance) der jeweiligen Komponente. Mit dieser Größe entscheidet man später, wie viele Komponenten man behält.

Dimensionsreduktion in fünf Schritten

Aus einem Datensatz x1,…,xN∈Rdx_1, \dots, x_N \in \mathbb{R}^d macht die PCA einen Datensatz in Rk\mathbb{R}^k mit k<dk < d:

  1. Zentrieren: Von jedem Merkmal seinen Mittelwert abziehen, sodass der Datensatz den Schwerpunkt 0 hat (meist auch skalieren, siehe unten).

  2. Kovarianzmatrix CC der zentrierten Daten berechnen.

  3. Eigenzerlegung: Eigenwerte λ1≥⋯≥λd\lambda_1 \geq \dots \geq \lambda_d und zugehörige normierte Eigenvektoren v1,…,vdv_1, \dots, v_d von CC bestimmen.

  4. Auswählen: Die kk Eigenvektoren zu den größten Eigenwerten behalten — sie erklären den Anteil (λ1+⋯+λk)/tr⁡(C)(\lambda_1 + \dots + \lambda_k) / \operatorname{tr}(C) der Gesamtvarianz.

  5. Projizieren: Jeden zentrierten Datenpunkt xx auf seine neuen Koordinaten (⟨x,v1⟩,…,⟨x,vk⟩)\big(\langle x, v_1 \rangle, \dots, \langle x, v_k \rangle\big) abbilden.

Eigenwerte: [8. 2.]  erklärte Varianz der 1. HK: 0.8
neue Koordinaten: [2.82842712 0.        ]

Jetzt betrachten wir anstelle der fiktiven Kovarianzmatrix CC ein echtes Sample xx, welches wir dann mit einer Koordinatentransformation verzerren und mit der eben besprochenen Methode die Koordinatentransformation ‘rückgängig’ machen:

[[45.88617049 12.27313705]
 [12.27313705  6.13139888]]
Drei Streudiagramme nebeneinander. Links eine kreisrunde Punktwolke aus einer zweidimensionalen Standardnormalverteilung; in der Mitte dieselbe Stichprobe nach einer willkürlichen linearen Transformation, zu einer schmalen, von links unten nach rechts oben geneigten Zigarre gestreckt; rechts die über die Singulärwertzerlegung zurücktransformierte Wolke, wieder kreisrund.

Betrachten Sie die Plots ganz genau. Haben wir die Transformation vollständig rückgängig gemacht? Und wenn ja/nein, woran erkennen Sie das?

Berechnung

Ebenso können wir nun natürlich mit Daten verfahren, die wir gar nicht selbst transformiert haben, die möglicherweise auch gar nicht ursprünglich aus einer Standardnormalverteilung gesampelt wurden.

[[ 0.68569351 -0.042434    1.27431544  0.51627069]
 [-0.042434    0.18997942 -0.32965638 -0.12163937]
 [ 1.27431544 -0.32965638  3.11627785  1.2956094 ]
 [ 0.51627069 -0.12163937  1.2956094   0.58100626]]
Streudiagramm der ersten beiden Hauptkomponenten des Iris-Datensatzes, nach Art eingefärbt. Eine Gruppe liegt als kompakte Säule rechts, deutlich von den übrigen abgesetzt; die beiden anderen bilden links eine gemeinsame, diagonal verlaufende Wolke und überlappen in der Mitte.
Dieselben Daten als räumliches Streudiagramm der ersten drei Hauptkomponenten. Die abgesetzte Gruppe bleibt klar für sich, die beiden anderen liegen nebeneinander und berühren sich; die dritte Komponente trennt sie nicht zusätzlich.

Berechnung mit scikit-learn

Wir müssen uns noch nicht einmal die Mühe machen, selbst die Singulärwertzerlegung oder die Eigenvektoren der Kovarianzmatrix auszurechnen - das kann scikit-learn auch für uns tun:

Dasselbe räumliche Streudiagramm der ersten drei Hauptkomponenten, diesmal von scikit-learns PCA berechnet. Die Gruppen liegen identisch, nur ist das Bild entlang der ersten Komponente gespiegelt — das Vorzeichen einer Hauptkomponente ist nicht festgelegt.

Ein ganz anderer Zugang zum Finden der Richtung maximaler Varianz ist es, die Summe der quadrierten Abstände der Punkte zu einer Geraden zu minimieren.

Die Summe der quadrierten Abstände ist, bis auf den Faktor 1n\frac1n, ein mittlerer quadratischer Fehler. Und zum mse\texttt{mse} kennen wir das beste konstante Modell schon: Es ist der Mittelwert (Kapitel Erwartungswert und Varianz, Abschnitt „Quadratische Abweichung“). In diesem Sinn ist die erste Hauptkomponente das beste lineare Modell — die Gerade durch den Mittelwert, die den mittleren quadratischen Abstand minimiert —, und die Animation zeigt, dass das genau die Richtung größter Varianz ist.

Ein Detail, das man leicht überliest und das die PCA von der linearen Regression unterscheidet: Hier wird der senkrechte Abstand zur Geraden minimiert, bei der Regression dagegen der vertikale Abstand in Richtung der Zielgröße. Die beiden Geraden sind deshalb im Allgemeinen verschieden.

Dieses Vorgehen ist hier bildlich dargestellt:

Die Gerade dreht sich, bis die Summe der quadrierten Abstände minimal wird — das ist dieselbe Richtung, die die größte Varianz hat.

Figure 3:Die Gerade dreht sich, bis die Summe der quadrierten Abstände minimal wird — das ist dieselbe Richtung, die die größte Varianz hat.

Anwendungsbeispiel MNIST

Bisher haben wir die Dimension nur zum plotten reduziert - für viele Algorithmen ist es aber erforderlich, die Dimension wenigstens hinreichend klein zu halten, damit das Programm nicht wochenlang laufen muss. Ein Datensatz, der etwas mehr als nur 4 Variablen hat, ist der MNIST Datensatz von handschriftlichen Ziffern.

Zehn handgeschriebene Ziffern von 0 bis 9 nebeneinander, jede als grobes Graustufenbild von 8 mal 8 Pixeln aus dem Digits-Datensatz.
0.7236776816130616
0.7165493927158051
0.9199617902288166

Wie viele Komponenten braucht man? Scikit-learn liefert die erklärte Varianz jeder Komponente direkt (explained_variance_ratio_, das sind die Eigenwerte der Kovarianzmatrix geteilt durch ihre Summe). Die kumulierte Kurve zeigt, wie viel Varianz die ersten nn Komponenten zusammen erklären:

Kurve der kumulierten erklärten Varianz über der Anzahl der Hauptkomponenten, von 1 bis gut 60. Sie steigt zunächst steil, erreicht die gestrichelt eingezeichnete 90-Prozent-Marke bei rund 20 Komponenten und nähert sich danach flach dem Wert 1.
Komponenten für 90% der Varianz: 21 von 64
Kurve der Clustering-Güte über der Anzahl behaltener Hauptkomponenten. Die x-Achse ist umgekehrt, läuft also von 33 Komponenten links nach 0 rechts. Die Güte schwankt bis etwa 10 Komponenten nur leicht um 0,73, fällt dann langsam und bricht unterhalb von 5 Komponenten steil auf null ein.

Wie man im Graph erkennen kann, leidet die 10-Means-Performance als Klassifikator erst, wenn man von den ursprünglich 64 Dimensionen nur noch 10 übrig lässt, und dann weiter reduziert.

Wir haben in den Iris-Daten bereits gesehen, dass die Kovarianzmatrizen innerhalb der Gruppen leicht unterschiedlich ausfallen. Genau genommen wollen wir für eine optimale Unterscheidung der Gruppen auch gar nicht die Richtungen der größten Varianz bevorzugt betrachten, sondern noch viel lieber die Richtung, die die beste Unterscheidung erlaubt. Um das zu betrachten, muss man die Klassen aber bereits kennen - also supervised learning. Ein solches Verfahren ist Linear Discriminant Analysis (LDA).

Skalenunterschiede

Problematisch wird es, wenn die Daten nicht, wie in den Beispielen zuvor, auf gleichen Skalen liegen (einmal Meter, einmal Zentimeter) oder sogar die Skalen unbekannt oder inkompatibel (Sekunden, Meter) sind.

Dann dominieren die Variablen mit großen Zahlen, was eine Verzerrung der eigentlich angestrebten Koordinatentransformation ist. Um das zu vermeiden, reskaliert man jede Variable mit der Standardabweichung. Ebenso verschiebt man jede Variable, sodass der Mittelwert 0 wird. Das nennt sich ‘Standardisierung’. Es ist dann besonders sinnvoll, wenn die Variable annähernd normalverteilt ist.

Eine ‘Normalisierung’ ist eine Reskalierung auf das Intervall [0,1][0,1]. Sie ist dann besonders sinnvoll, wenn die Variable nicht normalverteilt ist.

Jede solche Umskalierung nennt sich ‘Feature Scaling’.

In Python kann man das mit scikit-learn machen, indem man ein Scaler-Objekt verwendet:

Zwei Streudiagramme übereinander, beide zeigen dieselben Daten in vier deutlich getrennten senkrechten Bändern. Oben die Ausgangsdaten, deren waagerechte Achse bis 45 reicht, während die senkrechte nur von etwa minus 8 bis 11 läuft; unten dieselben Daten nach Standardskalierung, nun in beiden Richtungen etwa gleich weit ausgedehnt. Der Mittelwert ist jeweils als kleines Kreuz eingezeichnet.

Wir betrachten jetzt den Einfluss der Skalierung auf die PCA und anschließendes Clustering mit k-Means, denn anstatt einfach immer alles durch den StandardScaler zu jagen, sollte man stets betrachten, welchen Unterschied es macht:

Vier Streudiagramme als Zweimal-zwei-Gitter, vier Farbgruppen. Obere Zeile: PCA der unskalierten Daten, die Gruppen stehen als senkrechte Bänder nebeneinander. Untere Zeile: PCA nach Standardskalierung, das Bild ist gedreht und die Gruppen verlaufen diagonal. Linke Spalte eingefärbt nach den Labels von k-Means, rechte Spalte nach den tatsächlichen Klassen.

Man kann in der oberen Zeile deutlich erkennen, dass k-Means auf den unskalierten Daten gut funktioniert. An der unteren Zeile sehen wir, dass bei Standardskalierung die Hauptkomponenten anders liegen (daher sieht das Bild gedreht aus), aber auch, dass k-Means die Cluster nicht gut eingeteilt hat.

Das ist letztlich eine Inkarnation von Simpson’s Paradox, denn die “richtige” Art, die Daten zu skalieren, wäre hier so, dass die Cluster möglichst standardnormalverteilt werden. Um das zu erreichen müsste man aber erst Clustern, dann die Standardskalierung der Cluster berechnen, mit einem geeigneten Mittelwert davon dann die ganzen Daten gemeinsam skalieren. Danach ergibt sich beim Clustern wiederum ein anderes Bild - und man kann das Verfahren iterieren. In diesem Setting ist es vorteilhaft, nicht k-Means zu verwenden, sondern gleich ein Verfahren, welches keine standardnormalverteilten Cluster annimmt (z.B. gemischte Gausssche Modelle).

Anwendungsbeispiel Wine

Zuletzt betrachten wir noch ein ‘Erfolgsbeispiel’ des Standardskalierens:

Dasselbe Zweimal-zwei-Gitter für einen echten Datensatz mit drei Klassen. Oben die PCA ohne Skalierung, deren erste Komponente von minus 400 bis 1000 reicht und in der die Farben stark durcheinanderliegen; unten die PCA nach Standardskalierung, in der sich drei Gruppen klar abzeichnen und die k-Means-Labels links fast dieselbe Aufteilung zeigen wie die tatsächlichen Klassen rechts.

Statt hier nur auf das Bild zu achten, ist es besser, auch eine Kennzahl auszurechnen. Wie zuvor verwenden wir dazu ein Entropie-basiertes Maß, die gemeinsame Information I(X;Y)I(X;Y) der beiden Klassenvariablen (Kapitel Relative Entropie), normiert auf den Mittelwert ihrer beiden Entropien:

Die skalierte Variante ist mit 0.865642 Ähnlichkeit zur 'echten' Klasse besser als die unskalierte Variante mit nur 0.423309 Ähnlichkeit