Eu perguntei isso anteriormente no StackOverflow, mas parece que pode ser mais apropriado aqui, já que não obteve respostas no SO. É uma espécie de cruzamento entre estatística e programação.
Preciso escrever algum código para fazer o PCA (Principal Component Analysis). Naveguei pelos algoritmos conhecidos e implementei este , que, até onde sei, é equivalente ao algoritmo NIPALS. Ele funciona bem para encontrar os dois ou três primeiros componentes principais, mas depois fica muito lento para convergir (da ordem de centenas a milhares de iterações). Aqui estão os detalhes do que eu preciso:
O algoritmo deve ser eficiente ao lidar com um grande número de recursos (ordem de 10.000 a 20.000) e tamanhos de amostra da ordem de algumas centenas.
Ele deve ser razoavelmente implementável sem uma biblioteca de álgebra / matriz linear decente, pois a linguagem de destino é D, que ainda não possui uma, e mesmo que tivesse, eu preferiria não adicioná-la como uma dependência do projeto em questão. .
Como uma observação lateral, no mesmo conjunto de dados R parece encontrar todos os componentes principais muito rapidamente, mas ele usa decomposição de valor singular, o que não é algo que eu queira codificar sozinho.
Respostas:
Eu implementei o SVD aleatório, conforme indicado em "Halko, N., Martinsson, PG, Shkolnisky, Y. e Tygert, M. (2010). Um algoritmo para a análise de componentes principais de grandes conjuntos de dados. Arxiv preprint arXiv: 1007.5510, 0526. Recuperado em 1 de abril de 2011, em http://arxiv.org/abs/1007.5510 . ". Se você deseja obter SVD truncado, ele realmente funciona muito mais rapidamente do que as variações de DVD no MATLAB. Você pode obtê-lo aqui:
Para testá-lo, basta criar uma imagem na mesma pasta (assim como uma grande matriz, você mesmo pode criar a matriz)
Quando o executo na área de trabalho para obter uma imagem de tamanho 635 * 483, recebo
Como você pode ver, para valores baixos de
k
, é mais de 10 vezes mais rápido que o uso do Matlab SVD. A propósito, você pode precisar da seguinte função simples para a função de teste:Não adicionei o método PCA, pois é simples de implementar usando SVD. Você pode verificar este link para ver o relacionamento deles.
fonte
você pode tentar usar algumas opções.
1- Decomposição da matriz penalizada . Você aplica algumas restrições de penalidade nos u e nos v para obter alguma escarsidade. Algoritmo rápido usado em dados genômicos
Veja Tibshirani Whitten. Eles também têm um R-pkg. "Uma decomposição de matriz penalizada, com aplicações para componentes principais esparsos e análise de correlação canônica".
2- SVD randomizado . Como o SVD é um algoritmo mestre, pode ser desejável uma aproximação muito rápida, especialmente para análises exploratórias. Usando SVD aleatório, você pode executar o PCA em grandes conjuntos de dados.
Veja Martinsson, Rokhlin e Tygert "Um algoritmo aleatório para a decomposição de matrizes". Tygert possui código para uma implementação muito rápida do PCA.
Abaixo está uma implementação simples de SVD aleatório em R.
fonte
Parece que talvez você queira usar o algoritmo Lanczos . Caso contrário, convém consultar a Golub & Van Loan. Certa vez, codifiquei um algoritmo SVD (em SML, de todas as línguas) a partir de seu texto, e funcionou razoavelmente bem.
fonte
Sugiro tentar o PCA do kernel, que tem uma complexidade de tempo / espaço dependente do número de exemplos (N) em vez do número de recursos (P), que eu acho que seriam mais adequados para a sua configuração (P >> N)). O Kernel PCA basicamente trabalha com a matriz NxN do kernel (matriz de semelhanças entre os pontos de dados), em vez da matriz de covariância PxP, que pode ser difícil de lidar com P. grande. Outra coisa boa do kernel PCA é que ele pode aprender projeções não lineares também se você o usar com um kernel adequado. Consulte este documento no PCA do kernel .
fonte
Parece-me que me lembro que é possível executar o PCA calculando a decomposição autônoma de X ^ TX em vez de XX ^ T e depois transformar para obter os PCs. No entanto, não me lembro dos detalhes imediatamente, mas está no (excelente) livro de Jolliffe e procurarei quando for o próximo no trabalho. Eu transliteraria as rotinas de álgebra linear de, por exemplo, Métodos Numéricos em C, em vez de usar qualquer outro algoritmo.
fonte
Existe também o método de inicialização de Fisher et al , projetado para várias centenas de amostras de alta dimensão.
A idéia principal do método é formulada como "a reamostragem é uma transformação de baixa dimensão". Portanto, se você tiver um número pequeno (várias centenas) de amostras de alta dimensão, não poderá obter mais componentes principais do que o número de suas amostras. Portanto, faz sentido considerar as amostras como uma base parcimoniosa, projetar os dados no subespaço linear estendido por esses vetores e calcular o PCA dentro desse subespaço menor. Eles também fornecem mais detalhes sobre como lidar com o caso, quando nem todas as amostras podem ser armazenadas na memória.
fonte
Veja o artigo de Sam Roweis, EM Algorithms for PCA e SPCA .
fonte