Quiero agrupar un conjunto de datos masivo para el que solo tengo las distancias por pares. Implementé un algoritmo k-medoids, pero está tardando demasiado en ejecutarse, así que me gustaría comenzar reduciendo la dimensión de mi problema aplicando PCA. Sin embargo, la única forma en que sé realizar este método es usando la matriz de covarianza que no tengo en mi situación.
¿Hay alguna manera de aplicar PCA conociendo solo las distancias por pares?
pca
dimensionality-reduction
multidimensional-scaling
árbol grande
fuente
fuente
Respuestas:
Actualización: eliminé por completo mi respuesta original, porque estaba basada 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 por 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 se puede convertir en una matriz de Gram centrada, que se puede usar directamente para realizar PCA mediante descomposición propia. Este procedimiento se conoce como escalamiento multidimensional [clásico] (MDS) .
Si sus distancias por pares no son euclidianas, entonces no puede realizar PCA, pero aún puede realizar MDS, que ya no será equivalente a PCA. Sin embargo, en esta situación, es probable que MDS sea aún mejor para sus propósitos.
fuente
Existe PCA con una matriz de distancia, y se llama escalamiento multidimensional (MDS). Puede obtener más información en wikipedia o en este libro .
Puedes hacerlo
Rcon la función mdscmdscale. Para una muestrax, puede verificar esoprcomp(x)ycmdscale(dist(x))dar el mismo resultado (dondeprcompPCA ydistsolo calcula distancias euclidianas entre elementos de x)fuente
Esto parece un problema al que se podría aplicar la agrupación espectral. Dado que tiene la matriz de distancia por pares, puede definir un gráfico completamente conectado donde cada nodo tiene N conexiones, lo que corresponde a su distancia desde cualquier otro nodo en el gráfico. A partir de esto, puede calcular el gráfico laplaciano (si esto suena aterrador, no se preocupe, es un cálculo fácil) y luego tomar vectores propios de los más pequeños.valores propios (aquí es donde difiere de PCA). Si toma 3 vectores propios, por ejemplo, tendrá una matriz Nx3. En este espacio, los puntos deberían (con suerte) estar bien separados debido a alguna teoría de gráficos clara que sugiere que este es un corte óptimo para maximizar el flujo (o la distancia, en este caso) entre grupos. A partir de ahí, puede usar un algoritmo k-means o similar para agrupar en 3 espacios. Recomiendo revisar este increíble tutorial para obtener más información:
http://arxiv.org/abs/0711.0189
fuente
Las distancias por pares también forman una matriz cuadrada al igual que la matriz de covarianza. PCA es solo SVD ( http://en.wikipedia.org/wiki/Singular_value_decomposition ) aplicado a la matriz de covarianza. Aún debería poder hacer una reducción de dimensión usando SVD en sus datos. No estoy exactamente seguro de cómo interpretar su salida, pero definitivamente es algo para probar. Puede utilizar métodos de agrupación como k-means o agrupación jerárquica. También eche un vistazo a otras técnicas de reducción de dimensiones, como el escalado multidimensional. ¿Qué estás tratando de sacar de tus grupos?
fuente