Comment faire SVD et PCA avec gros volumes de données?

Question

J'ai un grand ensemble de données (environ 8 Go). Je voudrais utiliser l'apprentissage de la machine pour l'analyser. Donc, je pense que je devrais utiliser SVD alors PCA pour réduire la dimensionnalité des données d'efficacité. Cependant, MATLAB et Octave ne peut pas charger un grand ensemble de données.

Quels sont les outils que je peux utiliser pour faire SVD avec une si grande quantité de données?

Answer 1

D'abord, Réduction de dimensionnalité est utilisé lorsque vous avez de nombreuses dimensions covariés et que vous voulez réduire la taille du problème en rotation des points de données dans la nouvelle base orthogonale et en prenant des axes seulement la plus grande variance. Avec 8 variables (colonnes) votre espace est déjà faible dimension, réduction du nombre de variables plus est peu probable que de résoudre les problèmes techniques avec la taille de la mémoire, mais peut affecter beaucoup ensemble de données de qualité. Dans votre cas concret, il est plus prometteur de jeter un oeil à l'apprentissage en ligne méthodes. Grosso modo, au lieu de travailler avec l'ensemble des données, ces méthodes prennent une petite partie d'entre eux (souvent appelés « mini-lots ») à la fois et construire un modèle progressivement. (Personnellement, je aime à interpréter mot « en ligne » comme une référence à une source infiniment longue des données à partir d'Internet comme un flux Twitter, où vous ne pouvez pas charger tout le jeu de données à la fois).

Mais si vous vouliez vraiment appliquer la technique de réduction de dimensionnalité comme PCA à un ensemble de données qui ne rentre pas dans une mémoire? Normalement, un ensemble de données est représenté comme une matrice de données X de taille n x m , où n est le nombre d'observations (lignes) et m est un nombre de variables (colonnes). En règle générale des problèmes de mémoire viennent d'un seul de ces deux nombres.

Trop d'observations (n ??>> m)

Quand vous avez trop d'observations , mais le nombre de variables est de faible à modérée, vous pouvez construire la matrice de covariance incrémentale . En effet, l'APC typique consiste à construire une matrice de covariance de taille m x m et appliquer la décomposition de la valeur singulière à elle. Avec m = 1000 variables de type float64, une matrice de covariance a une taille 1000 * 1000 * 8 ~ 8Mo, qui se glisse facilement dans la mémoire et peut être utilisé avec SVD. Donc, il vous suffit de construire la matrice de covariance sans charger l'ensemble jeu de données en mémoire - jolie tâche tractable .

Vous pouvez sélectionner un petit échantillon représentatif de votre ensemble de données et une approximation de la matrice de covariance . Cette matrice aura tous les mêmes propriétés que la normale, juste un peu moins précis.

Trop de variables (n << m)

D'un autre côté, parfois, quand vous avez trop de variables , la matrice de covariance elle-même ne rentre pas dans la mémoire. Par exemple. si vous travaillez avec des images 640x480, chaque observation a 640 * 480 = 307200 variables, dont les résultats dans une matrice de covariance 703Gb! C'est certainement pas ce que vous voulez garder à la mémoire de votre ordinateur, ou même dans la mémoire de votre cluster. Nous devons donc réduire les dimensions sans construire une matrice de covariance du tout.

Ma méthode préférée pour le faire est Projection aléatoire . En bref, si vous avez ensemble de données X de la taille n x m , vous pouvez multiplier par une matrice aléatoire clairsemée R de taille m x k (avec k << m ) et obtenir une nouvelle matrice X « d'une taille beaucoup plus petite n x k avec approximativement les mêmes propriétés que celui d'origine. Pourquoi ça marche? Eh bien, vous devez savoir que les objectifs PCA pour trouver ensemble d'axes orthogonaux (composants principaux) et projeter vos données sur la première k d'entre eux. Il se avère que des vecteurs aléatoires sont rares presque orthogonaux et ainsi peuvent également être utilisés comme une nouvelle base.

Et, bien sûr, vous n'avez pas de multiplier l'ensemble des données X par R - vous pouvez traduire toutes les observations x en la nouvelle base séparément ou en mini-lots.

Il y a aussi un peu simalgorithme ilar appelé SVD aléatoire . Je n'ai aucune expérience réelle avec, mais vous pouvez trouver un exemple de code avec des explications .

---

En bout de ligne, voici une liste de contrôle courte pour la réduction de la dimensionnalité des grands ensembles de données:

1. Si vous n'êtes pas que beaucoup de dimensions (variables), il suffit d'utiliser des algorithmes d'apprentissage en ligne.
2. S'il y a beaucoup d'observations, mais un nombre modéré de variables (matrice de covariance fits en mémoire), construire la matrice progressivement et utiliser SVD normale.
3. Si nombre de variables est trop élevé, utiliser des algorithmes supplémentaires.

Answer 2

Ne pas déranger.

Première règle de ce qui s'applique également témoin de programmation à la science des données. Tout se travailler sur un petit problème de test

afin de prendre un échantillon aléatoire de données de 100.000 disons lignes. essayer différents algorithmes, etc. une fois que vous avez tout travail à votre satisfaction, vous pouvez essayer de grands ensembles de données (et plus) -. et voir comment l'erreur de test diminue à mesure que vous ajoutez des données

En outre, vous ne voulez pas appliquer SVD à seulement 8 colonnes: vous l'appliquez quand vous avez beaucoup de colonnes

.

Answer 3

APC est généralement mis en oeuvre en calculant SVD sur la matrice de covariance.

Le calcul de la matrice de covariance est un honteusement parallèle tâche, il adapte linéaire avec le nombre d'enregistrements, et il est trivial de distribuer sur plusieurs machines!

Il suffit de faire une passe sur vos données pour calculer les moyens. Puis un second passage pour calculer la matrice de covariance. Cela peut être fait avec carte-réduire facilement - essentiellement, il est le même que le calcul des moyens à nouveau. Somme des termes comme dans covariance sont insignifiants à paralléliser! Vous pouvez seulement besoin de faire attention à la somme des valeurs numériques quand beaucoup de valeurs de grandeur similaire.

Les choses se différent quand vous avez un grand nombre de Variables . Mais sur un système de 8 Go, vous devriez être en mesure d'exécuter PCA sur un maximum de dimensions en-20,000 mémoire avec les bibliothèques BLAS. Mais alors vous pouvez rencontrer le problème que l'APC est pas tout ce qui est plus fiable, car il a trop de degrés de liberté. En d'autres termes: il overfits facilement. Je l'ai vu la recommandation d'avoir au moins 10 * d * d enregistrements (ou était-ce d ^ 3). Donc, pour 10000 dimensions, vous devez avoir au moins un milliard d'enregistrements (de 10000 dimensions ... qui est beaucoup!) Pour que le résultat soit statistiquement fiable.

Answer 4

Bien que vous pouvez probablement trouver des outils qui vous permettront de le faire sur une seule machine, vous obtenez dans la plage où il judicieux de considérer « big data » des outils tels que Spark, surtout si vous pensez que votre puissance de jeu de données grandir. Spark a un composant appelé MLlib qui prend en charge les PCA et SVD. La documentation a des exemples .

Answer 5

Nous avons mis SVD à un ensemble de données plus en utilisant PySpark. Nous comparons également la cohérence entre les différents paquets. Voici le lien .

Answer 6

Je recommande python si vous évaluez paresseusement le fichier que vous aurez une empreinte mémoire minuscule et numpy / scipy vous donnent accès à tous les outils Octave feriez / Matlab.