Appliquer l'APC sur une très grande matrice clairsemée

16

Je fais une tâche de classification de texte avec R, et j'obtiens une matrice de termes de document avec la taille 22490 par 120 000 (seulement 4 millions d'entrées non nulles, moins de 1% d'entrées). Maintenant, je veux réduire la dimensionnalité en utilisant PCA (analyse en composantes principales). Malheureusement, R ne peut pas gérer cette énorme matrice, donc je stocke cette matrice clairsemée dans un fichier au "Matrix Market Format", en espérant utiliser d'autres techniques pour faire de l'ACP.

Alors, quelqu'un pourrait-il me donner quelques conseils pour des bibliothèques utiles (quel que soit le langage de programmation), qui pourraient facilement faire PCA avec cette matrice à grande échelle, ou faire moi-même une PCA à long terme, en d'autres termes, calculer la matrice de covariance dans un premier temps, et puis calculez les valeurs propres et les vecteurs propres pour la matrice de covariance .

Ce que je veux, c'est calculer tous les PC (120 000), et choisir uniquement les N meilleurs PC, qui représentent une variance de 90% . Évidemment, dans ce cas, je dois donner un seuil a priori pour définir des valeurs de variance très minimes à 0 (dans la matrice de covariance), sinon, la matrice de covariance ne sera pas clairsemée et sa taille serait de 120 000 par 120 000, ce qui est impossible à manipuler avec une seule machine. De plus, les chargements (vecteurs propres) seront extrêmement importants et devraient être stockés dans un format épars.

Merci beaucoup pour toute aide !

Remarque: J'utilise une machine avec 24 Go de RAM et 8 cœurs de processeur.

Ensom Hodder
la source
Quelle est la densité de la matrice? Comment utilisez-vous le SVD résultant? Si vous n'en avez besoin que d'une partie, vous pourriez probablement l'approcher beaucoup moins cher.
Arnold Neumaier
@ArnoldNeumaier Excusez-moi, j'ai oublié d'ajouter les informations rares. J'ai mis à jour le message, ainsi que mon idée complète.
Ensom Hodder
chacun des SLEPc, mahout et irlba suggérés dans les réponses jusqu'à présent semble adapté à votre problème.
Arnold Neumaier
1
Pourquoi voulez-vous calculer tous les 120k? Il semble que vous vouliez simplement que ceux qui représentent 90% de la variance, ce qui devrait être beaucoup moins cher à calculer.
Jed Brown
@JedBrown Hé Jed, tu as tout à fait raison! Je ne m'intéresse qu'à ceux qui expliquent la variance de 90%, ainsi qu'aux vecteurs propres correspondants (pour transformer ensuite l'ensemble de données de test). Pourriez-vous s'il vous plaît laissez-moi savoir vos méthodes moins chères ?
Ensom Hodder

Réponses:

4

Je suggère le package irlba - il produit pratiquement les mêmes résultats que svd, mais vous pouvez définir un plus petit nombre de valeurs singulières à résoudre. Un exemple, utilisant des matrices clairsemées pour résoudre le prix Netflix, peut être trouvé ici: http://bigcomputing.blogspot.de/2011/05/bryan-lewiss-vignette-on-irlba-for-svd.html

Marc dans la boîte
la source
Merci pour vos commentaires. En fait, j'avais regardé cette vidéo et essayé le package irlba hier, mais il semblait qu'il ne pouvait être utilisé que pour calculer quelques valeurs singulières. Cependant, comme indiqué dans la publication, je veux calculer TOUTES les valeurs singulières (120 000), afin de choisir le nombre approprié de PC en fonction des variances qu'ils représentent. Dans ce cas, je suppose que l' irlba ne convient plus.
Ensom Hodder
Pouvez-vous utiliser les résultats de SVD d'une manière similaire à PCA? N'avez-vous pas besoin de centrer les données AVANT de faire le SVD, afin d'effectuer l'ACP?
Zach
@Zach - SVD est l'algorithme principal derrière PCA (voir prcomp - stat.ethz.ch/R-manual/R-patched/library/stats/html/prcomp.html ). Le centrage des données est également une procédure standard avant de soumettre à l'ACP, bien qu'il existe une grande variété d'options en fonction de votre question (par exemple, différents types de mise à l'échelle peuvent également être appliqués).
Marc dans la case
Quelle importance cela représente-t-il si je ne centre pas les données avant SVD? J'ai une matrice clairsemée qui tient dans la mémoire, mais le centrage la rendrait dense et trop grande pour tenir dans la mémoire.
Zach
@Zach - Cela dépend vraiment de la façon dont vous voulez relier vos échantillons les uns aux autres. Si vous ne pouvez pas travailler avec des données centrées en raison de limites de mémoire, alors je suppose que la décision a été prise pour vous. Généralement, le centrage des données fait fonctionner le PCA sur une matrice de covariance des échantillons tandis que le centrage et la mise à l'échelle des données font fonctionner le PCA sur une matrice de corrélation. Pour plus d'informations sur ces décisions, vous pouvez envisager de poser une question sur stats.stackexchange.com ou de rechercher parmi les réponses existantes concernant PCA.
Marc dans la case du
8

Je suggère d'utiliser SLEPc pour calculer une SVD partielle. Voir le chapitre 4 du manuel de l'utilisateur et les pages de manuel SVD pour plus de détails.

Jed Brown
la source
1
Puisqu'il veut PCA, il doit centrer les données avant de calculer le SVD. Cela détruira la rareté. Y a-t-il un moyen pour que SLEPc s'adapte à cela?
dranxo
3
C'est juste clairsemé + bas rang. SLEPc n'a pas besoin d'entrées de matrice, juste un opérateur linéaire, qui peut être appliqué comme une matrice clairsemée plus une correction.
Jed Brown
2

Je vote pour mahout qui est également bon pour d'autres tâches NLP / TA et implémente map / Reduce.

danas.zuokas
la source
Oui, vous avez raison, le mahout est exactement dans ma feuille de route. Mais je préfère créer un prototype avec quelques techniques "simples" (je suppose) à l'avance.
Ensom Hodder
1

Je suggère d'utiliser une décomposition incrémentielle de valeurs singulières, dont il existe de nombreux dans la littérature. Par exemple:

  • les rapports techniques de Matthew Brand 1 et 2 sont assez faciles à suivre
  • La thèse de maîtrise de Chris Baker , son logiciel IncPACK et son article ultérieur sur la méthode SVD incrémentale
  • Bunch et Nielsen ont publié le premier article connu
  • Documents de Hall sur la mise à jour des problèmes de valeurs propres 1 et 2
  • Analyse séquentielle de Karhunen-Loeve par Levy et al., Qui est fondamentalement la même chose

Toutes ces approches se réduisent à ce qui suit:

  • commencer par un petit ensemble de données
  • calculer une SVD en quelque sorte (cette étape est triviale pour une matrice à colonne unique)
  • répéter jusqu'à la fin:
    • ajouter un nouvel ensemble de données
    • utiliser les règles SVD et de mise à jour existantes pour calculer la SVD du nouvel ensemble de données

Dans votre application, si vous avez une idée d'où votre seuil de valeur singulier pour le haut Nvaleurs seront, vous pouvez utiliser cette valeur pour calculer un SVD tronqué; si la valeur de seuil est suffisamment petite, alors la matrice que vous devez garder en mémoire sera également petite (seules les valeurs singulières au-dessus de la valeur de seuil sont conservées, ainsi que leurs vecteurs singuliers; il n'est même pas nécessaire de garder les singuliers gauche et droit vecteurs, dans l'algorithme de Brand).

Geoff Oxberry
la source
0

Vous pouvez toujours utiliser R.

Revolution Rest une version de R qui gère des ensembles de données plus volumineux que la RAM. Utilisez la fonction princomp.

Il dispose également d'une gamme complète de fonctions de statistiques spécialement conçues pour les problèmes de style Big Data qui ne rentrent pas dans la RAM, par exemple la régression linéaire, la régression logistique, les quantiles, etc.

Vous pouvez télécharger gratuitement la version académique complète en cochant la case "Je suis un universitaire".

Contango
la source