Executando PCA com apenas uma matriz de distância

12

Quero agrupar um conjunto de dados massivo para o qual tenho apenas as distâncias aos pares. Eu implementei um algoritmo k-medoids, mas está demorando muito para ser executado, então eu gostaria de começar reduzindo a dimensão do meu problema aplicando o PCA. No entanto, a única maneira que sei executar esse método é usando a matriz de covariância que não tenho na minha situação.

Existe uma maneira de aplicar o PCA conhecendo apenas as distâncias aos pares?

grande árvore
fonte
1
Portanto, você tem uma grande matriz quadrada de distâncias entre os pontos que deseja agrupar. (BTW que distância? Euclidiano?) O que faz você pensar que é o número de dimensões que esses pontos abrangem, e não o número de pontos em si (cardinalidade), que impede o agrupamento?
ttnphns
1
O número de pontos não é "muito grande" (alguns milhares). A distância que estou usando é a correlação de Pearson entre esses pontos
Bigtree
2
Mas minha pergunta era: você realmente deseja reduzir a dimensionalidade (e se sim, por quê?) Ou cardinalidade (o número de pontos)? Porque sua pergunta não é clara .
ttnphns
1
@ttnphns: Oh garoto, é claro que eu simplesmente digitei meu comentário anterior errado. Para remover a possível confusão, agora excluirei esse comentário e repetirei o que disse aqui com a redação correta: "Reduzir a cardinalidade nesse caso significa tornar seuN×N matriz de distância menor (diminuindo N) Reduzir a dimensionalidade significa torná-lo mais baixo, sem alterarN. PCA equivale à última e realmente não ajuda com o ex-objetivo."
ameba diz Reintegrar Monica
1
Eu acho que a maneira mais fácil para você é usar esse (a) método de clustering ou (b) sua implementação ou (c) um computador tão forte (RAM suficiente) que pegue e classifique 6000 objetos (não sei por que seu programa medóide acha difícil. 6000 é grande, mas não muito grande.). Alguns métodos (como K-means) requerem que os objetos X apresentem dados. Você pode criar esses dados a partir da matriz de distância dos objetos via MDS métrico (se, novamente, o seu computador / programa MDS permitir 6.000 objetos).
ttnphns

Respostas:

8

Atualização: removi completamente minha resposta original, porque era baseada em uma confusão entre distâncias euclidianas e produtos escalares. Esta é uma nova versão da minha resposta. Desculpas.

Se por distâncias aos pares você quer dizer distâncias euclidianas, sim, existe uma maneira de executar o PCA e encontrar os componentes principais. Descrevo o algoritmo em minha resposta à seguinte pergunta: Qual é a diferença entre análise de componentes principais e escala multidimensional?

Muito brevemente, a matriz das distâncias euclidianas pode ser convertida em uma matriz Gram centralizada, que pode ser usada diretamente para realizar a PCA via composição automática. Esse procedimento é conhecido como escala clássica multidimensional (MDS) .

Se suas distâncias aos pares não forem euclidianas, você não poderá executar o PCA, mas ainda poderá executar o MDS, que não será mais equivalente ao PCA. No entanto, nessa situação, o MDS provavelmente será ainda melhor para seus propósitos.

ameba diz Restabelecer Monica
fonte
A distância que estou usando é uma correlação (correlação de Pearson) e, portanto, não é a distância euclidiana. Isso funcionaria da mesma forma?
bigTree 25/02
1
@ bigTree: se não for a distância euclidiana, não há como executar o PCA. No entanto, você pode usar o dimensionamento multidimensional, que é uma técnica de redução de dimensionalidade que usa precisamente a matriz de distâncias em pares (pode ser qualquer distância). Outra observação: sob certas suposições sobre os pontos de dados originais (que você não possui), as correlações podem ser transformadas em distâncias euclidianas. As premissas são: (1) tendo média zero, (2) tendo comprimento fixo, por exemplo, unidade. Por acaso, é verdade para seus dados?
ameba diz Restabelecer Monica
Nenhuma dessas informações é verdadeira ou meus dados, mas tentarei agradecer ao MDS
bigTree
1
você não pode usar o PCA do kernel? Imagino que seria necessário apenas aos pares dot produtos, mas eu não sei muito sobre o assunto, então eu não sei se isso faz sentido
rep_ho
4

Existe um PCA com uma matriz de distância e é chamado de escala multidimensional (MDS). Você pode aprender mais na wikipedia ou neste livro .

Você pode fazer isso Rcom a função mds cmdscale. Para uma amostra x, você pode verificar isso prcomp(x)e cmdscale(dist(x))fornecer o mesmo resultado (onde prcompo PCA e distapenas calcula as distâncias euclidianas entre os elementos de x)

Pop
fonte
3

Parece um problema ao qual o agrupamento espectral pode ser aplicado. Como você possui a matriz de distância em pares, é possível definir um gráfico totalmente conectado no qual cada nó tem N conexões, correspondendo à sua distância de todos os outros nós no gráfico. A partir disso, você pode calcular o gráfico Laplaciano (se isso parecer assustador, não se preocupe - é um cálculo fácil) e, em seguida, obter os autovetores dos menoresautovalores (é onde difere do PCA). Se você usar 3 vetores próprios, por exemplo, terá uma matriz Nx3. Nesse espaço, os pontos devem (espero) ser bem separados por causa de alguma teoria dos grafos, que sugere que este é um corte ideal para maximizar o fluxo (ou a distância, neste caso) entre os clusters. A partir daí, você pode usar um k-means ou algoritmo semelhante para agrupar em 3 espaços. Eu recomendo verificar este passo a passo impressionante para obter mais informações:

http://arxiv.org/abs/0711.0189

Christopher Krapu
fonte
0

As distâncias aos pares também formam uma matriz quadrada, assim como a matriz de covariância. O PCA é apenas SVD ( http://en.wikipedia.org/wiki/Singular_value_decomposition ) aplicado à matriz de co-variância. Você ainda deve conseguir reduzir a dimensão usando SVD nos seus dados. Não sei exatamente como interpretar sua saída, mas é definitivamente algo para tentar. Você pode usar métodos de armazenamento em cluster, como k-means ou armazenamento em cluster hierárquico. Veja também outras técnicas de redução de dimensão, como dimensionamento multidimensional. O que você está tentando tirar de seus clusters?

Andrew Cassidy
fonte
A resposta de Andrew Cassidy é realmente válida. Se sua medida de distância é uma correlação de Pearson, você é apenas um fator de padronização "muito longe" de realmente ter uma matriz de covariância. Portanto, aplicar SVD é basicamente a mesma coisa que fazer PCA.
Matthew Anthony