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?
pca
dimensionality-reduction
multidimensional-scaling
grande árvore
fonte
fonte
Respostas:
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.
fonte
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 mdscmdscale. Para uma amostrax, você pode verificar issoprcomp(x)ecmdscale(dist(x))fornecer o mesmo resultado (ondeprcompo PCA edistapenas calcula as distâncias euclidianas entre os elementos de x)fonte
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
fonte
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?
fonte