Como executar o PCA para dados de dimensionalidade muito alta?

Para executar a análise de componentes principais (PCA), é necessário subtrair os dados de cada coluna, calcular a matriz do coeficiente de correlação e, em seguida, localizar os vetores próprios e os valores próprios. Bem, pelo contrário, foi o que fiz para implementá-lo no Python, exceto que funciona apenas com matrizes pequenas, porque o método para encontrar a matriz do coeficiente de correlação (corrcoef) não me permite usar uma matriz com alta dimensionalidade. Desde que eu tenho que usá-lo para imagens, minha implementação atual realmente não me ajuda.

Eu li que é possível apenas pegar sua matriz de dados e calcular vez de , mas isso não funciona para mim. Bem, não sei exatamente se entendi o que isso significa, além do fato de ser uma matriz vez de (no meu caso, ). Eu li sobre os tutoriais de autofaces, mas nenhum deles parecia explicar isso de uma maneira que eu realmente conseguia entender.D D ⊤ / n D ⊤ D / n n × n p × p p ≫ $D$$DD^\top/n$$D^\top D/n$$n \times n$$p\times p$$p\gg n$

Em resumo, existe uma descrição algorítmica simples desse método para que eu possa segui-lo?

A maneira mais fácil de executar o PCA padrão é centralizar as colunas da sua matriz de dados (supondo que as colunas correspondam a variáveis ​​diferentes) subtraindo os meios da coluna e, em seguida, executando um SVD. Os vetores singulares esquerdos, multiplicados pelo valor singular correspondente, correspondem aos componentes principais (estimados). Os vetores singulares à direita correspondem às direções (estimadas) dos principais componentes - são os mesmos que os vetores próprios fornecidos pelo PCA. Os valores singulares correspondem aos desvios padrão dos componentes principais (multiplicados por um fator de raiz n, em que n é o número de linhas em sua matriz de dados) - o mesmo que a raiz quadrada dos valores próprios fornecidos pelo PCA.

Se você deseja executar o PCA na matriz de correlação, precisará padronizar as colunas da sua matriz de dados antes de aplicar o SVD. Isso significa subtrair os meios (centralizar) e depois dividir pelos desvios padrão (dimensionar).

Essa será a abordagem mais eficiente se você desejar o PCA completo. Você pode verificar com alguma álgebra que isso fornece a mesma resposta que a decomposição espectral da matriz de covariância da amostra.

Também existem métodos eficientes para calcular um SVD parcial, quando você precisa apenas de alguns PCs. Algumas dessas são variantes da iteração de energia. O algoritmo de Lanczos é um exemplo também relacionado a mínimos quadrados parciais. Se sua matriz é enorme, você pode se sair melhor com um método aproximado. Também existem razões estatísticas para regularizar o PCA quando este for o caso.

O que você está fazendo agora está próximo, mas você precisa multiplicar os vetores próprios (data . data.T) / linesà esquerda por data.T, para obter os vetores próprios de (data.T . data) / lines. Isso às vezes é chamado de "truque de transposição".

Aqui estão mais alguns detalhes. Suponha que você tenha uma matriz qual deseja executar o PCA; por simplicidade, suponha que as colunas de já tenham sido normalizadas com média zero, de modo que apenas precisamos calcular os vetores próprios da matriz de covariância .$A$$A$$A^T A$

Agora, se é uma matriz , com , então é uma matriz muito grande . Portanto, em vez de calcular os vetores próprios de , gostaríamos de calcular os vetores próprios da matriz muito menor - supondo que possamos descobrir uma relação entre os dois. Então, como os autovetores de relacionados aos autovetores de ?$A$$m \times n$$n >> m$$A^T A$$n \times n$$A^T A$$m \times m$$A A^T$$A^T A$$A A^T$

Seja um vetor próprio de com valor próprio . Então$v$$A A^T$$\lambda$

• $AA^T v = \lambda v$
• $A^T(A A^T v) = A^T(\lambda v)$
• $(A^T A)(A^T v) = \lambda (A^T v)$

Em outras palavras, se é um vetor próprio de , então é um vetor próprio de , com o mesmo valor próprio. Portanto, ao executar um PCA em , em vez de encontrar diretamente os vetores próprios de (que podem ser muito caros), é mais fácil encontrar os vetores próprios de e multiplicá-los à esquerda por para obter os autovetores de .A A T A T v A T A A A T A v A A T A T A T$v$$A A^T$$A^T v$$A^T A$$A$$A^T A$$v$$AA^T$$A^T$$A^T v$$A^T A$

Parece que o que você deseja é o algoritmo NIPALS para executar o PCA. É um algoritmo muito popular entre estatísticos. Tem muitas vantagens:

• Computacionalmente mais barato que os métodos de decomposição SVD ou autovalor, se apenas os primeiros componentes forem necessários.
• Tem requisitos de armazenamento mais modestos em geral, porque a matriz de covariância nunca é formada. Esta é uma propriedade muito importante para conjuntos de dados muito grandes.
• Pode lidar com dados ausentes no conjunto de dados (embora isso não seja um problema no seu problema, pois você está lidando com imagens).

Descrição
http://en.wikipedia.org/wiki/Non-linear_iterative_partial_least_squares

Algoritmo
Aqui está uma descrição simples e excelente do algoritmo (na seção 1.2)
http://stats4.eng.mcmaster.ca/w/mediafiles/mediawiki/f/f7/Section-Extra-Class-1.pdf

Lembre-se de dimensionar a média do centro antes de executar o PCA, pois é sensível à escala.

Para adicionar a resposta de Gilead, eles são algoritmos computacionalmente mais baratos para PCAs truncados. O NIPALS é realmente muito popular, mas tive muito sucesso com métodos aproximados que realizam uma sucessão de ajustes em dados parciais (o que geralmente é chamado de PCA por projeção aleatória). Isso foi discutido em um thread de metaoptimização .

Como você mencionou Python, deixe-me salientar que o algoritmo é implementado no scikit-learn : a classe PCA . Em particular, é usado em um exemplo demonstrando autofaces .