Comprendre comment fonctionne PCA distribués

Question

Dans le cadre du grand projet d'analyse de données, je travaille,

Je dois effectuer des PCA sur certaines données, en utilisant le système de cloud computing.

Dans mon cas, j'utilise Amazon EMR pour le travail et Spark en particulier.

Quitter la question « How-to-Perform-PCA en étincelle » de côté, je veux comprendre comment les choses fonctionnent dans les coulisses en matière de calcul des PC sur l'architecture en nuage.

Par exemple, l'un des moyens pour déterminer les PC d'une donnée consiste à calculer la matrice de covariance des caractéristiques.

Lors de l'utilisation HDFS architecture par exemple, les données d'origine est répartie sur plusieurs nœuds, je devine chaque nœud reçoit des enregistrements X.

Quelle est alors la matrice de covariance calculée dans ce cas, lorsque chaque noeud possède seulement des données partielles?

Ceci est juste un exemple. Je suis en train de trouver un papier ou une documentation expliquant tout cela derrière les coulisses voodoo, et ne pouvait pas trouver quoi que ce soit assez de bon pour mes besoins (probablement mes pauvres compétences de Google).

Je peux donc essentiellement résumer ma question (s) \ doit être le suivant:

1. Comment distribué PCA sur une architecture cloud fonctionne

De préférence du papier académique ou d'autres types d'explication qui contient également quelques visuels

2. la mise en œuvre Spark de D-PCA

Comment faire Spark? Est-ce qu'ils ont une « twist » dans leur architecture pour le faire de manière plus efficace, ou comment le RDD objets d'utilisation contribuent à l'amélioration de l'efficacité? etc.

Une présentation de même une leçon en ligne en ce qui concerne ce serait bien.

Merci d'avance à tous ceux qui peuvent fournir du matériel de lecture.

Answer 1

La question est plus liée à Apache architecture Spark et carte réduire; il y a plus d'une question ici, cependant, la pièce centrale de votre question est peut-être

Par exemple, l'un des moyens pour déterminer les PC d'une donnée consiste à calculer la matrice de covariance des caractéristiques.

Lors de l'utilisation HDFS architecture par exemple, les données d'origine est répartie sur plusieurs nœuds, je devine chaque nœud reçoit des enregistrements X.

Quelle est alors la matrice de covariance calculée dans ce cas, lorsque chaque noeud possède seulement des données partielles?

Je vais répondre à cette question, qui nous l'espérons dégager la question à un degré.

Regardons une forme commune de calcul de covariance, $ \ frac {1} {n} \ sum (x \ bar {x}) (y- \ bar { y}) $

Cela vous oblige à calculer les éléments suivants:

• $ \ bar {x} $
• $ \ bar {y} $
• $ X- \ bar {x} $ et $ y- \ bar {y} $
• Multiplier la $ (X- \ bar {x}) $ et $ (y- \ bar {y} ) $

d'une manière répartie. Le reste est simple, laissez-nous dire que j'ai 100 points datat (x, y), qui est distribué à 10 Apache travailleurs Spark, chacun obtenant 10 points de données.

Calcul de la $ \ bar {x} $ et $ bar \ {y} $ : Chaque travailleur ajoutera $ x / y $ valeurs de 10 points de données et diviser par 10 pour arriver à moyenne partielle de $ x / y $ (ce qui est la fonction de la carte). Alors le maître Spark se déroulera l'étape d'agrégation (en DAG Spark du travail) où les moyens partiels de l'ensemble des 10 travailleurs sont pris et encore ajoutés, puis divisé par 10 pour arriver à la finale $ \ bar {x} $ ou $ \ bar {y} $ (l'agrégat / réduire le fonctionnement)

Calcul de la $ (X- \ bar {x}) \ cdot (y- \ bar {y}) $ : même ainsi, répartir les points de données, la diffusion de la $ bar \ {x} $ et $ \ bar {y} $ valeurs à tous les travailleurs et calculer la partie $ (X- \ bar {x}) \ cdot (y- \ bar {y}) $ , encore une fois exécuter l'agrégation pour obtenir $ \ sum (x \ bar {x}) (y- \ bar {y}) $

La méthode ci-dessus est utilisé pour le calcul distribué, vous obtiendrai la covariance, pour les données multidimensionnelles, vous pouvez obtenir la matrice de covariance.

Le but est de distribuer le calcul des étapes qui peuvent être distribués et centralisent les étapes de calcul qui ne peuvent pas être distribués. C'est en effet l'un des aspects importants de l'architecture Spark.

Hope this helps.

Answer 2

Si vous voulez voir comment Spark fait, regardez la classe org.apache.spark.mllib.linalg.distributed.RowMatrix, en commençant par la méthode computePrincipalComponentsAndExplainedVariance .

La partie qui est effectivement distribué est en la méthode de computeGramianMatrix , qui accumule chaque vecteur d'entrée en un déterminant de gram utilisant BLAS.spr(1.0, v, U.data) où v est un vecteur d'entrée, et U représente la partie supérieure une partie triangulaire de la matrice. Cela peut être exécuté simultanément sur plusieurs exécuteurs, puis les matrices partiellement agrégées peuvent être combinés en ajoutant les matrices ensemble.

Une fois que tous les vecteurs ont été regroupés dans la déterminant de gram, il convertit la matrice à une matrice de covariance, et utilise ensuite SVD pour produire la matrice / vecteur PCA. Cependant, cette dernière étape n'est pas distribué.