Compreendendo como o PCA distribuído funciona

7

Como parte do projeto de análise de big data, estou trabalhando,

Preciso executar o PCA em alguns dados, usando o sistema de computação em nuvem.

No meu caso, estou usando o Amazon EMR para o trabalho e o Spark em particular.

Deixando de lado a questão "Como executar o PCA na faísca", quero entender como as coisas funcionam nos bastidores quando se trata de calcular PCs na arquitetura baseada em nuvem.

Por exemplo, um dos meios para determinar PCs de um dado é calcular a matriz de covariância dos recursos.

Ao usar a arquitetura baseada em HDFS, por exemplo, os dados originais são distribuídos por vários nós, acho que cada nó recebe registros X.

Como, então, é calculada a matriz de covariância nesse caso, quando cada nó tem apenas dados parciais?

Este é apenas um exemplo. Estou tentando encontrar algum documento ou documentação explicando todo esse vodu nos bastidores e não consegui encontrar nada bom o suficiente para minhas necessidades (provavelmente minhas poucas habilidades no Google).

Então, basicamente, posso resumir minhas perguntas \ precisa ser o seguinte:

1. Como o PCA distribuído na arquitetura em nuvem funciona

De preferência algum trabalho acadêmico ou outro tipo de explicação que também contenha alguns recursos visuais

2. Implementação Spark do D-PCA

Como o Spark faz isso? Eles têm alguma 'torção' em sua arquitetura para fazê-lo com mais eficiência, ou como o uso de objetos RDD contribui para melhorar a eficiência? etc.

Uma apresentação de até uma lição on-line seria ótima.

Agradecemos antecipadamente a quem puder fornecer algum material de leitura.

Adiel
fonte

Respostas:

4

A questão está mais relacionada à arquitetura do Apache Spark e à redução de mapa; existem mais de uma pergunta aqui, no entanto, a parte central da sua pergunta talvez seja

Por exemplo, um dos meios para determinar PCs de um dado é calcular a matriz de covariância dos recursos.

Ao usar a arquitetura baseada em HDFS, por exemplo, os dados originais são distribuídos por vários nós, acho que cada nó recebe registros X.

Como, então, é calculada a matriz de covariância nesse caso, quando cada nó tem apenas dados parciais?

Vou abordar isso, o que espero esclarecer a questão até certo ponto.

Vejamos uma forma comum de cálculo de covariância,1 1n(x-x¯)(y-y¯)

Isso requer que você calcule o seguinte:

  • x¯
  • y¯
  • x-x¯ ey-y¯
  • Multiplique o e(x-x¯)(y-y¯)

de maneira distribuída. O resto é simples, digamos que tenho 100 pontos de dados (x, y), que são distribuídos para 10 trabalhadores do Apache Spark, cada um recebendo 10 pontos de dados.

Calculando ex¯y¯ : Cada trabalhador adicionará valores de 10 pontos de dados e o dividirá por 10 para chegar à média parcial de (esta é a função do mapa). Em seguida, o mestre do Spark executará a etapa de agregação (no Spark DAG do trabalho) em que as médias parciais de todos os 10 trabalhadores são obtidas e adicionadas novamente, depois divididas por 10 para chegar à ou final (a operação agregada / redução)x/yx/yx¯y¯

Cálculo dos(x-x¯)(y-y¯) : Da mesma forma, distribua os pontos de dados, transmita os valores e a todos os trabalhadores e calcule o parcial , execute novamente a agregação para obterx¯y¯(x-x¯)(y-y¯)(x-x¯)(y-y¯)

O método acima é usado para o cálculo distribuído, você deve obter a covariância, para dados multidimensionais, você pode obter a matriz de covariância.

O objetivo é distribuir o cálculo para as etapas que podem ser distribuídas e, em seguida, centralizar as etapas de cálculo que não podem ser distribuídas. Esse é, de fato, um dos aspectos importantes da arquitetura Spark.

Espero que isto ajude.

Ironluca
fonte
Isso ajuda bastante. Estou um pouco confuso com suas definições, você poderia explicar o que xBar, yBarsignifica exatamente? e também a fórmula que você usou não me é familiar (talvez eu esteja lendo errado). Estou mais familiarizado com cálculos de covariância, como descrito aqui: onlinecourses.science.psu.edu/stat414/node/109
Adiel
@ Adiel, na verdade é o mesmo, consulte: seção en.wikipedia.org/wiki/Covariância 'Variáveis ​​discretas'. xBar e yBar são meios de x e y, eu não estou familiarizado com escrever equações em posts, então as fórmulas parecem um pouco distorcidas.
Ironluca
2

Se você quiser ver como faísca faz isso, olhar para a org.apache.spark.mllib.linalg.distributed.RowMatrixclasse, começando com o computePrincipalComponentsAndExplainedVariancemétodo .

A parte dela que é realmente distribuído é no computeGramianMatrixmétodo , que acumula cada vector de entrada numa matriz Gramian usando BLAS.spr(1.0, v, U.data)onde v é um vector de entrada, e L representa a parte triangular superior da matriz. Isso pode ser executado simultaneamente em muitos executores e, em seguida, as matrizes parcialmente agregadas podem ser combinadas adicionando as matrizes.

Uma vez que todos os vetores foram agregados na matriz Gramian, ele converte a matriz em uma matriz de covariância e, em seguida, usa SVD para produzir a matriz / vetor PCA. No entanto, esta etapa final não é distribuída.

Matt
fonte