7.6. Zufällige Projektion#

Das Modul sklearn.random_projection implementiert eine einfache und rechnerisch effiziente Methode zur Reduzierung der Dimensionalität von Daten, indem ein kontrollierter Genauigkeitsverlust (als zusätzliche Varianz) gegen schnellere Verarbeitungszeiten und kleinere Modellgrößen eingetauscht wird. Dieses Modul implementiert zwei Arten von unstrukturierten Zufallsmatrizen: Gaußsche Zufallsmatrizen und dünnbesetzte Zufallsmatrizen.

Die Dimensionen und die Verteilung von Zufallsprojektionsmatrizen werden so gesteuert, dass die paarweisen Abstände zwischen beliebigen zwei Stichproben des Datensatzes erhalten bleiben. Daher ist die Zufallsprojektion eine geeignete Approximationstechnik für distanzbasierte Methoden.

Referenzen

7.6.1. Das Johnson-Lindenstrauss-Lemma#

Das wichtigste theoretische Ergebnis hinter der Effizienz der Zufallsprojektion ist das Johnson-Lindenstrauss-Lemma (Zitat Wikipedia)

In der Mathematik ist das Johnson-Lindenstrauss-Lemma ein Ergebnis bezüglich der Einbettung von Punkten aus einem hochdimensionalen in einen niedrigdimensionalen Euklidischen Raum mit geringer Verzerrung. Das Lemma besagt, dass eine kleine Menge von Punkten in einem hochdimensionalen Raum in einen Raum viel geringerer Dimension eingebettet werden kann, so dass die Abstände zwischen den Punkten nahezu erhalten bleiben. Die für die Einbettung verwendete Abbildung ist mindestens Lipschitz, und kann sogar als orthogonale Projektion genommen werden.

Nur anhand der Anzahl der Stichproben schätzt die Funktion johnson_lindenstrauss_min_dim konservativ die minimale Größe des Zufallsunterraums ab, um eine begrenzte Verzerrung durch die Zufallsprojektion zu gewährleisten.

>>> from sklearn.random_projection import johnson_lindenstrauss_min_dim
>>> johnson_lindenstrauss_min_dim(n_samples=1e6, eps=0.5)
np.int64(663)
>>> johnson_lindenstrauss_min_dim(n_samples=1e6, eps=[0.5, 0.1, 0.01])
array([    663,   11841, 1112658])
>>> johnson_lindenstrauss_min_dim(n_samples=[1e4, 1e5, 1e6], eps=0.1)
array([ 7894,  9868, 11841])
../_images/sphx_glr_plot_johnson_lindenstrauss_bound_001.png
../_images/sphx_glr_plot_johnson_lindenstrauss_bound_002.png

Beispiele

Referenzen

7.6.2. Gaußsche Zufallsprojektion#

Die GaussianRandomProjection reduziert die Dimensionalität, indem der ursprüngliche Eingangsraum auf eine zufällig erzeugte Matrix projiziert wird, deren Komponenten aus der folgenden Verteilung gezogen werden: \(N(0, \frac{1}{n_{components}})\).

Hier ist ein kleines Beispiel, das zeigt, wie der Gaußsche Zufallsprojektions-Transformer verwendet wird.

>>> import numpy as np
>>> from sklearn import random_projection
>>> X = np.random.rand(100, 10000)
>>> transformer = random_projection.GaussianRandomProjection()
>>> X_new = transformer.fit_transform(X)
>>> X_new.shape
(100, 3947)

7.6.3. Dünnbesetzte Zufallsprojektion#

Die SparseRandomProjection reduziert die Dimensionalität, indem der ursprüngliche Eingangsraum mithilfe einer dünnbesetzten Zufallsmatrix projiziert wird.

Dünnbesetzte Zufallsmatrizen sind eine Alternative zur dichten Gaußschen Zufallsprojektionsmatrix, die eine ähnliche Einbettungsqualität garantieren, während sie wesentlich speichereffizienter sind und eine schnellere Berechnung der projizierten Daten ermöglichen.

Wenn wir s = 1 / density definieren, werden die Elemente der Zufallsmatrix gezogen aus:

\[\begin{split}\left\{ \begin{array}{c c l} -\sqrt{\frac{s}{n_{\text{components}}}} & & 1 / 2s\\ 0 &\text{mit Wahrscheinlichkeit} & 1 - 1 / s \\ +\sqrt{\frac{s}{n_{\text{components}}}} & & 1 / 2s\\ \end{array} \right.\end{split}\]

wobei \(n_{\text{components}}\) die Größe des projizierten Unterraums ist. Standardmäßig ist die Dichte der Nicht-Null-Elemente auf die minimale Dichte eingestellt, wie von Ping Li et al. empfohlen: \(1 / \sqrt{n_{\text{features}}}\).

Hier ist ein kleines Beispiel, das zeigt, wie der dünnbesetzte Zufallsprojektions-Transformer verwendet wird.

>>> import numpy as np
>>> from sklearn import random_projection
>>> X = np.random.rand(100, 10000)
>>> transformer = random_projection.SparseRandomProjection()
>>> X_new = transformer.fit_transform(X)
>>> X_new.shape
(100, 3947)

Referenzen

7.6.4. Inverse Transformation#

Die Zufallsprojektions-Transformer haben den Parameter compute_inverse_components. Wenn dieser auf True gesetzt ist, berechnet der Transformer nach dem Erzeugen der zufälligen Matrix components_ während des Fits die Pseudoinverse dieser Matrix und speichert sie als inverse_components_. Die Matrix inverse_components_ hat die Form \(n_{features} \times n_{components}\) und ist immer eine dichte Matrix, unabhängig davon, ob die Komponentmatrix dünnbesetzt oder dicht ist. Je nach Anzahl der Merkmale und Komponenten kann sie viel Speicher verbrauchen.

Wenn die Methode inverse_transform aufgerufen wird, berechnet sie das Produkt des Eingangs X mit der Transponierten der inversen Komponenten. Wenn die inversen Komponenten während des Fits berechnet wurden, werden sie bei jedem Aufruf von inverse_transform wiederverwendet. Andernfalls werden sie jedes Mal neu berechnet, was kostspielig sein kann. Das Ergebnis ist immer dicht, auch wenn X dünnbesetzt ist.

Hier ist ein kleines Codebeispiel, das zeigt, wie die inverse Transformationsfunktion verwendet wird.

>>> import numpy as np
>>> from sklearn.random_projection import SparseRandomProjection
>>> X = np.random.rand(100, 10000)
>>> transformer = SparseRandomProjection(
...   compute_inverse_components=True
... )
...
>>> X_new = transformer.fit_transform(X)
>>> X_new.shape
(100, 3947)
>>> X_new_inversed = transformer.inverse_transform(X_new)
>>> X_new_inversed.shape
(100, 10000)
>>> X_new_again = transformer.transform(X_new_inversed)
>>> np.allclose(X_new, X_new_again)
True