Exécution de PCA avec seulement une matrice de distance

12

Je veux regrouper un ensemble de données massif pour lequel je n'ai que les distances par paire. J'ai implémenté un algorithme k-medoids, mais cela prend trop de temps à exécuter, donc je voudrais commencer par réduire la dimension de mon problème en appliquant PCA. Cependant, la seule façon que je connaisse pour exécuter cette méthode est d'utiliser la matrice de covariance que je n'ai pas dans ma situation.

Existe-t-il un moyen d'appliquer l'APC en connaissant uniquement les distances par paires?

grand arbre
la source
1
Donc, vous avez une grande matrice carrée de distances entre les points que vous souhaitez regrouper. (BTW quelle distance? Euclidienne?) Qu'est-ce qui vous fait penser que c'est le nombre de dimensions que ces points s'étendent, et non le nombre de points eux-mêmes (cardinalité), qui entrave le regroupement?
ttnphns
1
Le nombre de points n'est pas "très grand" (quelques milliers). La distance que j'utilise est la corrélation de Pearson entre ces points
bigTree
2
Mais ma question était: voulez-vous vraiment réduire la dimensionnalité (et si oui, pourquoi?) Ou la cardinalité (le nombre de points)? Parce que votre question n'est pas claire .
ttnphns
1
@ttnphns: Oh mon garçon, bien sûr, j'ai simplement mal saisi mon commentaire précédent. Afin d'éliminer la confusion possible, je vais maintenant supprimer ce commentaire et répéter ce que j'ai dit ici avec une formulation correcte: "Réduire la cardinalité dans ce cas signifie rendre votre matrice de distance plus petite (diminuer ). Réduire la dimensionnalité signifie la rendre rang inférieur, sans changer PCA revient à ce dernier et n'aide pas vraiment avec l'ancien objectif ". N NN×NNN
amibe dit Réintégrer Monica le
1
Je pense que la façon la plus simple pour vous est d'utiliser une telle (a) méthode de clustering ou (b) telle sa mise en œuvre ou (c) un ordinateur aussi puissant (assez de RAM) qui prendra et classera 6000 objets (je ne sais pas pourquoi votre le programme médoïde a du mal. 6000 est grand, mais pas très grand.). Certaines méthodes (telles que K-means) requièrent des objets X données d'entités. Vous pouvez créer ces données à partir de la matrice de distance des objets via MDS métrique (si, encore une fois, votre programme informatique / MDS autorise 6000 objets).
ttnphns

Réponses:

8

Mise à jour: j'ai entièrement supprimé ma réponse d'origine, car elle était basée sur une confusion entre les distances euclidiennes et les produits scalaires. Ceci est une nouvelle version de ma réponse. Mes excuses.

Si par distances par paires, vous voulez dire les distances euclidiennes, alors oui, il existe un moyen d'effectuer l'ACP et de trouver les principaux composants. Je décris l'algorithme dans ma réponse à la question suivante: Quelle est la différence entre l'analyse des composants principaux et la mise à l'échelle multidimensionnelle?

Très brièvement, la matrice des distances euclidiennes peut être convertie en une matrice de Gram centrée, qui peut être directement utilisée pour effectuer l'ACP via la composition par eigendec. Cette procédure est connue sous le nom de mise à l'échelle multidimensionnelle [MDS] .

Si vos distances par paires ne sont pas euclidiennes, vous ne pouvez pas effectuer PCA, mais vous pouvez toujours effectuer MDS, qui ne sera plus équivalent à PCA. Cependant, dans cette situation, MDS est susceptible d'être encore meilleur pour vos besoins.

amibe dit réintégrer Monica
la source
La distance que j'utilise est une corrélation (corrélation de Pearson) et n'est donc pas la distance euclidienne. Cela fonctionnerait-il de la même manière?
bigTree
1
@bigTree: Si ce n'est pas la distance euclidienne, il n'y a aucun moyen d'exécuter PCA. Cependant, vous pouvez utiliser une mise à l'échelle multidimensionnelle qui est une technique de réduction de dimensionnalité qui utilise précisément la matrice de distances par paires (il peut s'agir de n'importe quelle distance). Autre remarque: sous certaines hypothèses sur les points de données d'origine (que vous n'avez pas), les corrélations peuvent être transformées en distances euclidiennes. Les hypothèses sont: (1) ayant une moyenne nulle, (2) ayant une longueur fixe, par exemple unitaire. Est-ce par hasard vrai pour vos données?
amibe dit Réintégrer Monica le
Rien de tout cela n'est vrai ou mes données, mais je vais essayer MDS merci
bigTree
1
ne pouvez-vous pas utiliser le noyau PCA? J'imagine qu'il faudrait que des produits point par paires, mais je ne sais pas beaucoup sur la question, donc je ne sais pas s'il est logique
rep_ho
4

Il existe une ACP avec une matrice de distance, et elle est appelée mise à l'échelle multidimensionnelle (MDS). Vous pouvez en savoir plus sur wikipedia ou dans ce livre .

Vous pouvez le faire Ravec la fonction mds cmdscale. Pour un exemple x, vous pouvez vérifier cela prcomp(x)et cmdscale(dist(x))donner le même résultat (d'où prcompvient l'ACP et distcalcule simplement les distances euclidiennes entre les éléments de x)

Pop
la source
3

Cela ressemble à un problème auquel le clustering spectral pourrait être appliqué. Étant donné que vous avez la matrice de distance par paire, vous pouvez définir un graphique entièrement connecté où chaque nœud a N connexions, correspondant à sa distance par rapport à tous les autres nœuds du graphique. À partir de cela, vous pouvez calculer le graphique laplacien (si cela vous semble effrayant, ne vous inquiétez pas - c'est un calcul facile), puis prendre des vecteurs propres des plus petitsvaleurs propres (c'est là qu'il diffère de l'ACP). Si vous prenez 3 vecteurs propres, par exemple, vous aurez alors une matrice Nx3. Dans cet espace, les points devraient (espérons-le) être bien séparés en raison d'une théorie des graphes soignée qui suggère qu'il s'agit d'une coupe optimale pour maximiser le flux (ou la distance, dans ce cas) entre les grappes. De là, vous pouvez utiliser un k-means ou un algorithme similaire pour regrouper en 3 espaces. Je recommande de consulter cette procédure pas à pas pour plus d'informations:

http://arxiv.org/abs/0711.0189

Christopher Krapu
la source
0

Les distances par paire forment également une matrice carrée, tout comme la matrice de co-variance. PCA est juste SVD ( http://en.wikipedia.org/wiki/Singular_value_decomposition ) appliqué à la matrice de co-variance. Vous devriez toujours être en mesure de réduire les dimensions à l'aide de SVD sur vos données. Je ne sais pas exactement comment interpréter votre sortie, mais c'est certainement quelque chose à essayer. Vous pouvez utiliser des méthodes de clustering telles que k-means ou clustering hiérarchique. Jetez également un œil à d'autres techniques de réduction de dimension telles que la mise à l'échelle multidimensionnelle. Qu'essayez-vous de retirer de vos grappes?

Andrew Cassidy
la source
La réponse d'Andrew Cassidy est en fait valide. Si votre mesure de distance est une corrélation de Pearson, vous êtes juste un facteur de normalisation "trop ​​loin" d'avoir réellement une matrice de covariance. Ainsi, appliquer SVD est fondamentalement la même chose que faire PCA.
Matthew Anthony