Une ACP à grande échelle est-elle même possible?

10

La méthode classique de l'analyse en composantes principales (ACP) consiste à le faire sur une matrice de données d'entrée dont les colonnes ont une moyenne nulle (alors l'ACP peut "maximiser la variance"). Ceci peut être réalisé facilement en centrant les colonnes. Cependant, lorsque la matrice d'entrée est clairsemée, la matrice centrée sera désormais plus clairsemée et - si la matrice est très grande - ne rentrera donc plus en mémoire. Existe-t-il une solution algorithmique pour le problème de stockage?

pca algorithms dimensionality-reduction large-data sparse Roy
la source
5
Même si la matrice de données complète ne tient pas en mémoire, il se peut très bien que la covariance ou la matrice de Gram tienne en mémoire. Celles-ci sont suffisantes pour effectuer l'ACP. À quelle taille de la matrice de données d'entrée pensez-vous? Voir aussi stats.stackexchange.com/questions/35185 .
amoeba
1
@amoeba: Je regarde des échantillons de 500K (lignes) et des fonctionnalités de 300K (colonnes)
Roy
En ce qui concerne les logiciels, Apache Spark l'a spark.apache.org/docs/latest/… pour sûr l'implémentation traite des données de mémoire insuffisante
Tim

Réponses:

11

Oui c'est possible.

Si la matrice de données ne rentre pas dans la RAM, ce n'est pas encore la fin du monde: il existe des algorithmes efficaces qui peuvent travailler avec des données stockées sur un disque dur. Voir par exemple l'ACP randomisée comme décrit dans Halko et al., 2010, Un algorithme pour l'analyse en composantes principales de grands ensembles de données .

Dans la section 6.2, les auteurs mentionnent qu'ils ont essayé leur algorithme sur une matrice de données 400k fois 100k et que

L'algorithme du présent document a nécessité 12,3 heures pour traiter les 150 Go de cet ensemble de données stocké sur disque, en utilisant l'ordinateur portable avec 1,5 Go de RAM [...].

Notez que c'était dans l'ancien temps des disques durs magnétiques; aujourd'hui, il existe des disques SSD beaucoup plus rapides, donc je suppose que le même algorithme fonctionnerait beaucoup plus rapidement.

Voir aussi ce vieux fil pour plus de discussion sur la PCA randomisée: Meilleur algorithme PCA pour un grand nombre de fonctionnalités (> 10K)? et cette grande revue de 2011 de Halko et al.: Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions .

amibe
la source