Warum funktioniert Pythons Scikit-Learn-LDA nicht richtig und wie berechnet es LDA über SVD?

Ich habe die lineare Diskriminanzanalyse (LDA) aus der scikit-learnmaschinellen Lernbibliothek (Python) zur Dimensionsreduktion verwendet und war ein wenig neugierig auf die Ergebnisse. Ich frage mich jetzt, was die LDA scikit-learntut, damit die Ergebnisse anders aussehen als beispielsweise ein manueller Ansatz oder eine in R durchgeführte LDA. Es wäre großartig, wenn mir jemand hier einige Einblicke geben könnte.

Was im Grunde am meisten betrifft, ist, dass das scikit-ploteine Korrelation zwischen den beiden Variablen zeigt, wobei es eine Korrelation 0 geben sollte.

Für einen Test habe ich den Iris-Datensatz verwendet und die ersten beiden linearen Diskriminanten sahen folgendermaßen aus:

IMG-1. LDA via Scikit-Learn

Bildbeschreibung hier eingeben

Dies stimmt im Wesentlichen mit den Ergebnissen überein, die ich in der Dokumentation zu scikit-learn hier gefunden habe.

Nun ging ich Schritt für Schritt die LDA durch und bekam eine andere Projektion. Ich habe verschiedene Ansätze ausprobiert, um herauszufinden, was los war:

IMG-2. LDA auf Rohdaten (keine Zentrierung, keine Standardisierung)

Bildbeschreibung hier eingeben

Und hier wäre der schrittweise Ansatz, wenn ich zuerst die Daten standardisieren würde (z-Score-Normalisierung; Einheitsvarianz). Ich habe dasselbe nur mit Mittelwertzentrierung gemacht, was zu demselben relativen Projektionsbild führen sollte (und was es tatsächlich tat).

IMG-3. Schrittweise LDA nach Mittelwertzentrierung oder Standardisierung

Bildbeschreibung hier eingeben

IMG-4. LDA in R (Standardeinstellungen)

LDA in IMG-3, in dem ich die Daten zentriert habe (was der bevorzugte Ansatz wäre), sieht genauso aus wie der, den ich in einem Beitrag von jemandem gefunden habe, der die LDA in R durchgeführt hat Bildbeschreibung hier eingeben

Code als Referenz

Ich wollte nicht den gesamten Code hier einfügen, habe ihn jedoch als IPython-Notizbuch hier hochgeladen und in die verschiedenen Schritte unterteilt (siehe unten), die ich für die LDA-Projektion verwendet habe.

Schritt 1: Berechnen der d-dimensionalen Durchschnittsvektoren $m_{i} = \frac{1}{n_{i}} \sum_{x \in D_{i}}^{n} x_{k}$ $\mathbf m_i = \frac{1}{n_i} \sum\limits_{\mathbf x \in D_i}^n \; \mathbf x_k$
Schritt 2: Berechnen der Streumatrizen

2.1 Die Streumatrix wird nach folgender Gleichung berechnet: $S_W$

$S_{W} = \sum_{i = 1}^{c} S_{i} = \sum_{i = 1}^{c} \sum_{x \in D_{i}}^{n} (x - m_{i}) (x - m_{i})^{T}$ $S_W = \sum\limits_{i=1}^{c} S_i = \sum\limits_{i=1}^{c} \sum\limits_{\mathbf x \in D_i}^n (\mathbf x - \mathbf m_i)\;(\mathbf x - \mathbf m_i)^T$
2.2 Die Zwischenklassen-Streumatrix wird durch die folgende Gleichung berechnet: wobei der Gesamtmittelwert ist. $S_B$

$S_{B} = \sum_{i = 1}^{c} n_{i} (m_{i} - m) (m_{i} - m)^{T}$ $S_B = \sum\limits_{i=1}^{c} n_i (\mathbf m_i - \mathbf m) (\mathbf m_i - \mathbf m)^T$ $\mathbf m$
Schritt 3. Lösen des verallgemeinerten Eigenwertproblems für die Matrix $S_{W}^{-1}S_B$

3.1. Sortieren der Eigenvektoren durch Verringern der Eigenwerte

3.2. Auswahl von k Eigenvektoren mit den größten Eigenwerten. Kombinieren der beiden Eigenvektoren mit den höchsten Eigenwerten, um unsere dimensionale Eigenvektormatrix zu konstruieren $d \times k$ $\mathbf W$
Schritt 5: Transformieren der Samples in den neuen Unterraum
$y = W^{T} \times x .$ $\mathbf y = \mathbf W^T \times \mathbf x.$

python scikit-learn dimensionality-reduction discriminant-analysis svd Amöbe sagt Reinstate Monica
quelle

Ich habe noch nicht nach den Unterschieden gesucht, aber Sie können genau sehen, was Scikit-Learn in der Quelle tut .

Dougal

Es sieht so aus, als würden sie sich auch standardisieren (Zentrieren und dann Skalieren durch Division durch die Standardabweichung). Dies würde ich zu einem ähnlichen Ergebnis führen wie in meinem dritten Plot (und dem R-Plot) ... hmm

Seltsam: Die Handlung, die Sie mit scikit erhalten haben (und die, die sie in ihrer Dokumentation zeigen), ergibt keinen Sinn. LDA liefert immer Projektionen mit einer Korrelation von Null, aber offensichtlich besteht eine sehr starke Korrelation zwischen den Projektionen von scikit auf den Diskriminanzachsen 1 und 2. Da stimmt eindeutig etwas nicht.

Amöbe sagt Reinstate Monica

@ameoba Ja, das denke ich auch. Seltsam ist auch, dass die gleiche Handlung, die ich für scikit zeige, in der Beispieldokumentation enthalten ist: scikit-learn.org/stable/auto_examples/decomposition/… Das lässt mich denken, dass meine Verwendung von scikit korrekt ist, aber dass es etwas Seltsames gibt über die LDA-Funktion

@SebastianRaschka: Ja, mir ist aufgefallen. Es ist in der Tat komisch. Beachten Sie jedoch, dass die ersten Ihrer eigenen (Nicht-Scikit-) LDA-Diagramme auch eine Korrelation ungleich Null aufweisen und daher auch etwas damit nicht stimmt. Haben Sie die Daten zentriert? Die Projektion auf der zweiten Achse scheint keinen Mittelwert von Null zu haben.

Amöbe sagt Reinstate Monica

Antworten:

Update: Dank dieser Diskussion scikit-learnwurde das Update durchgeführt und funktioniert nun korrekt. Den LDA-Quellcode finden Sie hier . Das ursprüngliche Problem war auf einen kleinen Fehler zurückzuführen (siehe diese Github-Diskussion ), und meine Antwort zeigte tatsächlich nicht richtig darauf (entschuldige mich für die verursachte Verwirrung). Da das alles keine Rolle mehr spielt (Fehler behoben), habe ich meine Antwort überarbeitet, um mich darauf zu konzentrieren, wie LDA über SVD gelöst werden kann, was der Standardalgorithmus in ist scikit-learn.

Nach der Definition von Streumatrizen innerhalb und zwischen Klassen und besteht die in Ihrer Frage Standard-LDA-Berechnung darin, Eigenvektoren von als diskriminante Achsen ( siehe zB hier ). Dieselben Achsen können jedoch auf eine etwas andere Weise berechnet werden, indem eine Weißmachermatrix verwendet wird: $\boldsymbol \Sigma_W$ $\boldsymbol \Sigma_B$ $\boldsymbol \Sigma_W^{-1} \boldsymbol \Sigma_B$

Berechne . Dies ist eine Aufhellungstransformation in Bezug auf die gepoolte Kovarianz innerhalb der Klasse (siehe meine verknüpfte Antwort für Details). $\boldsymbol \Sigma_W^{-1/2}$

Beachten Sie, dass wenn Sie EIGEN-Zersetzung , dann . Man beachte auch, dass man dasselbe berechnet, indem man eine SVD gepoolter Daten innerhalb einer Klasse durchführt: . $\boldsymbol \Sigma_W = \mathbf{U}\mathbf{S}\mathbf{U}^\top$ $\boldsymbol \Sigma_W^{-1/2}=\mathbf{U}\mathbf{S}^{-1/2}\mathbf{U}^\top$ $\mathbf{X}_W = \mathbf{U} \mathbf{L} \mathbf{V}^\top \Rightarrow \boldsymbol\Sigma_W^{-1/2}=\mathbf{U}\mathbf{L}^{-1}\mathbf{U}^\top$
Finden Eigenvektoren von , nennen wir sie . $\boldsymbol \Sigma_W^{-1/2} \boldsymbol \Sigma_B \boldsymbol \Sigma_W^{-1/2}$ $\mathbf{A}^*$

Man beachte wiederum, dass man es berechnen kann, indem man eine SVD von Daten zwischen Klassen , die mit transformiert wurden , dh Daten zwischen Klassen, die in Bezug auf die innerhalb der Klasse weiß werden Kovarianz. $\mathbf{X}_B$ $\boldsymbol \Sigma_W^{-1/2}$
Die Diskriminanzachsen werden durch , dh durch die Hauptachsen transformierter Daten, die erneut transformiert werden . $\mathbf A$ $\boldsymbol \Sigma_W^{-1/2} \mathbf{A}^*$

In der Tat, wenn ein Eigenvektor der obigen Matrix ist, dann ist und Multiplikation von links mit und Definition von wir sofort : $\mathbf a^*$
$Σ_{W}^{- 1 / 2} Σ_{B} Σ_{W}^{- 1 / 2} a^{*} = λ a^{*},$ $\boldsymbol \Sigma_W^{-1/2} \boldsymbol \Sigma_B \boldsymbol \Sigma_W^{-1/2}\mathbf a^* = \lambda \mathbf a^*,$ $\boldsymbol \Sigma_W^{-1/2}$ $\mathbf a = \boldsymbol \Sigma_W^{-1/2}\mathbf a^*$ $Σ_{W}^{- 1} Σ_{B} a = λ a .$ $\boldsymbol \Sigma_W^{-1} \boldsymbol \Sigma_B \mathbf a = \lambda \mathbf a.$

Zusammenfassend ist LDA gleichbedeutend damit, die Matrix der Klassenmittelwerte in Bezug auf die Kovarianz innerhalb der Klasse aufzuhellen, PCA für die Klassenmittelwerte durchzuführen und die resultierenden Hauptachsen in den ursprünglichen (nicht aufgehellten) Raum zurück zu transformieren.

Dies wird z. B. in den Elementen des statistischen Lernens in Abschnitt 4.3.3 erläutert. In scikit-learndieser Art und Weise ist die Standard - LDA zu berechnen , weil SVD eine Datenmatrix numerisch stabiler als Eigenzerlegung der Kovarianzmatrix ist.

Beachten Sie, dass Sie anstelle von eine beliebige Whitening-Transformation verwenden können, und dass trotzdem alles genauso funktioniert. In verwendet (anstelle von ), und Es funktioniert einwandfrei (im Gegensatz zu dem, was ursprünglich in meiner Antwort geschrieben wurde). $\boldsymbol \Sigma_W^{-1/2}$ scikit-learn $\mathbf{L}^{-1}\mathbf{U}^\top$ $\mathbf{U}\mathbf{L}^{-1}\mathbf{U}^\top$

Amöbe sagt Reinstate Monica
quelle

Danke für diese nette Antwort. Ich weiß es zu schätzen, dass du dir die Zeit genommen hast, es so schön aufzuschreiben. Vielleicht könntest du es in der Diskussion auf GitHub erwähnen; Ich bin mir sicher, dass dies hilfreich sein würde, um die LDA in der nächsten Version von sci-kit

@SebastianRaschka: Ich habe keinen Account auf GitHub. Aber wenn du willst, kannst du dort einen Link zu diesem Thread geben.

Amöbe sagt Reinstate Monica

@amoeba: Lehrbücher beschreiben die LDA normalerweise so wie Sie - eine Eigenwertzerlegung von . Seltsamerweise verfolgen einige der mir bekannten LDA-Implementierungen einen anderen Ansatz. Ihre Achsen sind die Vektoren zu den mit transformierten . Ihre LDA-Lösung ist eine orthonormale Basis dieser Vektoren. Die LDA von Scikit-learn liefert die gleichen Ergebnisse wie diese Implementierungen, daher glaube ich nicht, dass tatsächlich ein Fehler vorliegt.

Σ_{W}^{- 1} Σ_{B}

$\boldsymbol \Sigma_W^{-1} \boldsymbol \Sigma_B$

Σ_{W}^{- 1}

$\boldsymbol \Sigma_W^{-1}$

Kasemakase

Als Referenz hier sind die Implementierungen, über die ich gesprochen habe: sourceforge.net/p/mlpy/code/ci/default/tree/mlpy/da.py#l24 github.com/sccn/BCILAB/blob/master/code/machine_learning /… Mathworks.com/matlabcentral/fileexchange/…

kazemakase

@kazemakase: Nun, natürlich, wenn es nur zwei Klassen gibt, dann hat Rang 1 und alles vereinfacht sich sehr, da der einzige Eigenvektor von durch gegeben ist , wobei Klassenmittel sind. Ich denke, das haben Sie vorher gemeint? Dies wird z. B. in Bishops ML-Lehrbuch, Abschnitt 4.1.4, ausführlich behandelt. Die Verallgemeinerung auf mehrere Klassen erfordert jedoch eine Eigenanalyse (ebd., 4.1.6). Auch scikit Code (das wir hier diskutieren!) Macht Gebrauch SVD, zweimal tatsächlich.

Σ_{B}

$\boldsymbol \Sigma_B$

Σ_{W}^{- 1} Σ_{B}

$\boldsymbol \Sigma_W^{-1}\boldsymbol \Sigma_B$

Σ_{W}^{- 1} (μ_{1} - μ_{2})

$\boldsymbol \Sigma_W^{-1}(\boldsymbol\mu_1 - \boldsymbol\mu_2)$

μ_{i}

$\boldsymbol\mu_i$

Amöbe sagt Reinstate Monica

Um diese Frage zu schließen, wurde das mit der LDA diskutierte Problem in scikit-learn 0.15.2 behoben .

quelle