Realización de PCA con sólo una matriz de distancias

Question

Quiero agrupar un conjunto de datos masivo del que sólo tengo las distancias entre pares. He implementado un algoritmo k-medoids, pero tarda demasiado en ejecutarse, así que me gustaría empezar por reducir la dimensión de mi problema aplicando PCA. Sin embargo, la única forma que conozco de realizar este método es utilizando la matriz de covarianza, que no tengo en mi situación.

¿Hay alguna forma de aplicar el ACP conociendo sólo las distancias entre pares?

Answer 1

Actualización: He eliminado por completo mi respuesta original, porque se basaba en una confusión entre las distancias euclidianas y los productos escalares. Esta es una nueva versión de mi respuesta. Disculpas.

Si por distancias entre pares te refieres a distancias euclidianas, entonces sí, hay una manera de realizar PCA y encontrar componentes principales. Describo el algoritmo en mi respuesta a la siguiente pregunta: ¿Cuál es la diferencia entre el análisis de componentes principales y el escalado multidimensional?

Muy brevemente, la matriz de distancias euclidianas puede convertirse en una matriz de Gram centrada, que puede utilizarse directamente para realizar el ACP mediante eigendecomposición. Este procedimiento se conoce como escalado multidimensional [clásico] (MDS) .

Si las distancias entre pares no son euclidianas, no podrá realizar el ACP, pero podrá realizar el MDS, que ya no será equivalente al ACP. Sin embargo, en esta situación es probable que MDS sea incluso mejor para sus propósitos.

Answer 2

El PCA con una matriz de distancias existe, y se denomina escalado multidimensional (MDS). Puede obtener más información en wikipedia o en este libro .

Puede hacerlo en R con función mds cmdscale . Para una muestra x puede comprobar que prcomp(x) y cmdscale(dist(x)) dan el mismo resultado (donde prcomp hace PCA y dist sólo calcula distancias euclidianas entre elementos de x)

Answer 3

Parece un problema al que podría aplicarse la agrupación espectral. Dado que disponemos de la matriz de distancias por pares, podemos definir un grafo totalmente conectado en el que cada nodo tiene N conexiones, correspondientes a su distancia a cualquier otro nodo del grafo. A partir de ahí, se puede calcular el laplaciano del grafo (si esto le asusta, no se preocupe, es un cálculo sencillo) y, a continuación, tomar los vectores propios del grafo. el más pequeño valores propios (en esto se diferencia del ACP). Si se toman 3 vectores propios, por ejemplo, se obtiene una matriz Nx3. En este espacio, los puntos deberían (con suerte) estar bien separados debido a la teoría de grafos, que sugiere que se trata de un corte óptimo para maximizar el flujo (o la distancia, en este caso) entre conglomerados. A partir de ahí, se podría utilizar un k-means o algoritmo similar para agrupar en 3-espacio. Te recomiendo que eches un vistazo a este impresionante tutorial para obtener más información:

http://arxiv.org/abs/0711.0189

Answer 4

Las distancias entre pares también forman una matriz cuadrada, al igual que la matriz de covarianza. PCA no es más que SVD ( http://en.wikipedia.org/wiki/Singular_value_decomposition ) aplicada a la matriz de covarianza. Usted todavía debe ser capaz de hacer la reducción de dimensión utilizando SVD en sus datos. No estoy exactamente seguro de cómo interpretar su salida, pero es definitivamente algo para probar. Podrías utilizar métodos de clustering como k-means o clustering jerárquico. Eche un vistazo también a otras técnicas de reducción de dimensiones, como el escalado multidimensional. ¿Qué intenta obtener de sus conglomerados?