O PCA em grande escala é possível?

10

O método clássico de análise de componentes principais (PCA) é fazê-lo em uma matriz de dados de entrada cujas colunas têm média zero (o PCA pode "maximizar a variação"). Isso pode ser alcançado facilmente centralizando as colunas. No entanto, quando a matriz de entrada for esparsa, a matriz centralizada será mais esparsa e, se a matriz for muito grande, não se ajustará mais à memória. Existe uma solução algorítmica para o problema de armazenamento?

Roy
fonte
5
Mesmo que a matriz de dados completa não se encaixe na memória, pode muito bem ser que a covariância ou a matriz Gram se encaixe na memória. Esses são suficientes para executar o PCA. Qual é o tamanho da matriz de dados de entrada? Consulte também stats.stackexchange.com/questions/35185 .
Ameba
11
@amoeba: Estou vendo 500K amostras (linhas) e 300K recursos (colunas)
Roy
Como cerca de software, Apache faísca tem spark.apache.org/docs/latest/... ao certo a implementação lida com dados out-of-memory
Tim

Respostas:

11

Sim, é possível.

Se a matriz de dados não se encaixa na RAM, ainda não é o fim do mundo: existem algoritmos eficientes que podem trabalhar com dados armazenados em um disco rígido. Veja, por exemplo, PCA randomizado, conforme descrito em Halko et al., 2010, Um algoritmo para a análise de componentes principais de grandes conjuntos de dados .

Na Seção 6.2, os autores mencionam que tentaram seu algoritmo na matriz de dados 400k vezes 100k e que

O algoritmo do presente trabalho levou 12,3 horas para processar todos os 150 GB desse conjunto de dados armazenados em disco, usando o laptop com 1,5 GB de RAM [...].

Observe que isso acontecia nos velhos tempos dos discos rígidos magnéticos; hoje existem unidades de estado sólido muito mais rápidas disponíveis, então acho que o mesmo algoritmo teria um desempenho consideravelmente mais rápido.

Veja também este tópico antigo para obter mais discussões sobre o PCA aleatório: o melhor algoritmo do PCA para um grande número de recursos (> 10K)? e esta grande revisão de 2011 de Halko et al .: Encontrando estrutura com aleatoriedade: algoritmos probabilísticos para a construção de decomposições aproximadas de matrizes .

ameba
fonte