Différence entre les implémentations scikit-learn de PCA et TruncatedSVD

12

Je comprends la relation entre l'analyse en composantes principales et la décomposition en valeurs singulières à un niveau algébrique / exact. Ma question concerne l' implémentation de scikit-learn .

La documentation dit: " [TruncatedSVD] est très similaire à l'ACP, mais fonctionne directement sur des vecteurs d'échantillonnage, plutôt que sur une matrice de covariance. ", Ce qui refléterait la différence algébrique entre les deux approches. Cependant, il dit plus tard: " Cet estimateur [TruncatedSVD] prend en charge deux algorithmes: un solveur SVD aléatoire rapide et un algorithme" naïf "qui utilise ARPACK comme solveur sur (X * XT) ou (XT * X), ​​selon le plus élevé des deux. efficace. ". Concernant PCA, il dit: "Réduction de dimensionnalité linéaire en utilisant la décomposition en valeur singulière des données pour les projeter ...". Et l'implémentation PCA prend en charge les deux mêmes algorithmes (randomisés et ARPACK) solveurs plus un autre, LAPACK. En examinant le code, je peux voir que les deux ARPACK et LAPACK dans PCA et TruncatedSVD font svd sur des exemples de données X, ARPACK étant capable de traiter des matrices clairsemées (en utilisant svds).

Ainsi, mis à part les différents attributs et méthodes et que PCA peut en outre effectuer une décomposition complète des valeurs singulières en utilisant les implémentations scapkit-learning LAPACK, PCA et TruncatedSVD, il semble que ce soit exactement le même algorithme. Première question: est-ce correct?

Deuxième question: même si LAPACK et ARPACK utilisent scipy.linalg.svd (X) et scipy.linalg.svds (X), étant X la matrice d'échantillon, ils calculent la décomposition en valeurs singulières ou la décomposition propre de ou X X T en interne. Le solveur "randomisé" n'a pas besoin de calculer le produit. (Ceci est pertinent en relation avec la stabilité numérique, voir Pourquoi l'ACP des données au moyen de la SVD des données? ). Est-ce correct?XTXXXT

Code pertinent: PCA ligne 415. TruncatedSVD ligne 137.

canard
la source
1
pourriez-vous ajouter un lien vers le code
seanv507
1
Drake - Je pense que je suis d'accord avec vous sur le premier Q. Je ne comprends pas le second. que voulez-vous dire 'ils calculent la décomposition en valeurs singulières ou la décomposition propre de XT ∗ XXT ∗ X ou X ∗ XTX ∗ XT en interne' - vous venez de montrer le code où tout est fait en utilisant SVD sur X? - les problèmes numériques se réfèrent d'abord au calcul de la matrice de covariance (appelez-le C) puis à la recherche des vecteurs propres de C
seanv507
XTXXXT
1
XXtimes()Xt_times()
@ GeoMatt22 Pouvez-vous développer votre commentaire? Voulez-vous dire que les approches ARPACK ou LAPACK ne souffrent pas d'instabilités numériques parce qu'elles n'ont pas besoin de calculer la matrice de covariance?
drake

Réponses:

13

Les implémentations PCA et TruncatedSVD scikit-learn semblent être exactement le même algorithme.

Non: PCA est SVD (tronqué) sur des données centrées (par soustraction moyenne par caractéristique). Si les données sont déjà centrées, ces deux classes feront de même.

En pratique, TruncatedSVDest utile sur les grands ensembles de données clairsemés qui ne peuvent pas être centrés sans faire exploser l'utilisation de la mémoire.

  • numpy.linalg.svdet les scipy.linalg.svddeux s'appuient sur LAPACK _GESDD décrit ici: http://www.netlib.org/lapack/lug/node32.html (pilote de division et de conquête)

  • scipy.sparse.linalg.svdss'appuie sur ARPACK pour effectuer une décomposition en valeurs propres de XT. X ou X. XT (selon la forme des données) via la méthode d'itération Arnoldi. Le guide de l'utilisateur HTML d'ARPACK a un formatage cassé qui cache les détails de calcul mais l'itération Arnoldi est bien décrite sur wikipedia: https://en.wikipedia.org/wiki/Arnoldi_iteration

Voici le code du SVD basé sur ARPACK dans scipy:

https://github.com/scipy/scipy/blob/master/scipy/sparse/linalg/eigen/arpack/arpack.py#L1642 (recherchez la chaîne pour "def svds" en cas de changement de ligne dans le code source ).

ogrisel
la source
2
L'un peut prendre en charge efficacement des données éparses (TruncatedSVD), l'autre non (PCA). C'est pourquoi nous avons 2 classes.
ogrisel
1
Si c'est la raison, je les appellerais SVD et SparseSVD (ou similaire) pour éviter toute confusion.
drake du
2
Mais les gens veulent PCA et ils ne savent peut-être pas que PCA est juste SVD sur des données centrées.
ogrisel
5
@drake Je ne suis pas d'accord sur le fait que "les procédures sont différentes (PCA utilise une matrice de covariance et SVD utilise une matrice de données)". PCA est un nom pour le type d'analyse. On peut utiliser différents algorithmes et implémentations pour le réaliser. Le GIE de la matrice cov est une méthode, le SVD de la matrice de données centrée est une autre méthode, puis le GIE et le SVD peuvent également être effectués par diverses méthodes. Peu importe - tout cela est PCA.
amibe dit Réintégrer Monica
1
@amoeba Merci pour la clarification / correction de la terminologie. Ce que vous dites est plus logique pour moi, étant donné que SVD et EIG sont des théorèmes / méthodes algébriques avec une portée plus large que PCA
drake