Trouver k de n éléments avec le moins de corrélations par paires

J'ai une matrice de corrélations par paires entre n éléments. Maintenant, je veux trouver un sous-ensemble de k éléments avec la moindre corrélation. Il y a donc deux questions:

1. Quelle est la mesure appropriée pour la corrélation au sein de ce groupe?
2. Comment trouver le groupe le moins corrélé?

Ce problème me semble être une sorte d'analyse factorielle inverse et je suis à peu près sûr qu'il existe une solution simple.

Je pense que ce problème est en fait égal au problème de suppression (nk) des nœuds d'un graphique complet afin que les nœuds restants soient connectés avec des poids de bord minimum. Qu'est-ce que tu penses?

Merci pour vos suggestions à l'avance!

[Avertissement: cette réponse est apparue avant que le PO ne décide de reformuler la question, de sorte qu'elle peut avoir perdu sa pertinence. À l'origine, la question portait sur How to rank items according to their pairwise correlations]

Parce que la matrice de corrélations par paires n'est pas un tableau unidimensionnel, il n'est pas très clair à quoi peut ressembler le "classement". Surtout tant que vous n'avez pas élaboré votre idée en détail, comme il semble. Mais vous avez mentionné que l'ACP vous convenait, et cela m'a immédiatement fait penser à la racine Cholesky comme une alternative potentiellement encore plus appropriée.

La racine Cholesky est comme une matrice de chargements laissée par PCA, seulement elle est triangulaire. Je vais vous expliquer les deux avec un exemple.

R, correlation matrix
         V1       V2       V3       V4
V1   1.0000   -.5255   -.1487   -.2790
V2   -.5255   1.0000    .2134    .2624
V3   -.1487    .2134   1.0000    .1254
V4   -.2790    .2624    .1254   1.0000

A, PCA full loading matrix
          I       II      III       IV
V1   -.7933    .2385    .2944    .4767
V2    .8071   -.0971   -.3198    .4867
V3    .4413    .8918    .0721   -.0683
V4    .5916   -.2130    .7771    .0261

B, Cholesky root matrix
          I       II      III       IV
V1   1.0000    .0000    .0000    .0000
V2   -.5255    .8508    .0000    .0000
V3   -.1487    .1589    .9760    .0000
V4   -.2790    .1361    .0638    .9485

A*A' or B*B': both restore R
         V1       V2       V3       V4
V1   1.0000   -.5255   -.1487   -.2790
V2   -.5255   1.0000    .2134    .2624
V3   -.1487    .2134   1.0000    .1254
V4   -.2790    .2624    .1254   1.0000

La matrice de chargement A de l'ACP est la matrice des corrélations entre les variables et les principales composantes. Nous pouvons le dire parce que les sommes des carrés des rangées sont toutes 1 (la diagonale de R) tandis que la somme matricielle des carrés est la variance globale (trace de R). Les éléments de B de la racine de Cholesky sont également des corrélations, car cette matrice a également ces deux propriétés. Les colonnes de B ne sont pas des composants principaux de A, bien qu'elles soient en quelque sorte des "composants".

A et B peuvent tous deux restaurer R et donc tous deux peuvent remplacer R, comme sa représentation. B est triangulaire, ce qui montre clairement qu'il capture les corrélations par paires de R séquentiellement ou hiérarchiquement. La composante de Cholesky est en Icorrélation avec toutes les variables et est l'image linéaire de la première d'entre elles V1. Le composant IIne partage plus V1mais est en corrélation avec les trois derniers ... Enfin, il IVn'est corrélé qu'avec le dernier V4,. Je pensais que ce genre de "classement" est peut - être ce que vous recherchez .

Le problème avec la décomposition de Cholesky, cependant, est que - contrairement à PCA - cela dépend de l'ordre des éléments dans la matrice R. Eh bien, vous pouvez trier les éléments par ordre décroissant ou croissant de la somme des éléments au carré (ou, si vous le souhaitez) , somme des éléments absolus, ou par ordre de coefficient de corrélation multiple - voir ci-dessous). Cet ordre reflète le montant de la corrélation brute d'un article.

R, rearranged
         V2       V1       V4       V3 
V2   1.0000   -.5255    .2624    .2134 
V1   -.5255   1.0000   -.2790   -.1487 
V4    .2624   -.2790   1.0000    .1254 
V3    .2134   -.1487    .1254   1.0000 

Column sum of squares (descending)
     1.3906   1.3761   1.1624   1.0833 

B 
          I       II      III       IV 
V2   1.0000    .0000    .0000    .0000 
V1   -.5255    .8508    .0000    .0000 
V4    .2624   -.1658    .9506    .0000 
V3    .2134   -.0430    .0655    .9738

De la dernière matrice B, nous voyons que V2, l'élément le plus grossièrement corrélé, met en gage toutes ses corrélations dans I. L'élément grossièrement corrélé suivant met en V1gage toute sa corrélation, sauf celui avec V2, dans II; etc.

Une autre décision pourrait être de calculer le coefficient de corrélation multiple pour chaque élément et de classer en fonction de son ampleur. La corrélation multiple entre un élément et tous les autres éléments augmente à mesure que l'élément est plus en corrélation avec chacun d'eux, mais ils sont moins en corrélation les uns avec les autres. Les coefficients de corrélation multiples au carré forment la diagonale de la matrice dite de covariance d'image qui est , où est la matrice diagonale des inverses des diagonales de .$\bf S R^{-1} S - 2S + R$$\bf S$$\bf R^{-1}$

Voici ma solution au problème. Je calcule toutes les combinaisons possibles de k éléments n et calcule leurs dépendances mutuelles en transformant le problème en un graphique-théorique: Quel est le graphique complet contenant tous les k nœuds avec la plus petite somme de bord (dépendances)? Voici un script python utilisant la bibliothèque networkx et une sortie possible. Veuillez vous excuser pour toute ambiguïté dans ma question!

Code:

import networkx as nx
import itertools
import os

#Create new graph
G=nx.Graph()

#Each node represents a dimension
G.add_nodes_from([1,2,3,4,5,6,7,8,9,10,11])

#For each dimension add edges and correlations as weights
G.add_weighted_edges_from([(3,1,0.563),(3,2,0.25)])
G.add_weighted_edges_from([(4,1,0.688),(4,3,0.438)])
G.add_weighted_edges_from([(5,1,0.25),(5,2,0.063),(5,3,0.063),(5,4,0.063)])
G.add_weighted_edges_from([(6,1,0.063),(6,2,0.25),(6,3,0.063),(6,4,0.063),(6,5,0.063)])
G.add_weighted_edges_from([(7,2,0.25),(7,3,0.063),(7,5,0.125),(7,6,0.063)])
G.add_weighted_edges_from([(8,1,0.125),(8,2,0.125),(8,3,0.5625),(8,5,0.25),(8,6,0.188),(8,7,0.125)])
G.add_weighted_edges_from([(9,1,0.063),(9,2,0.063),(9,3,0.25),(9,6,0.438),(9,7,0.063),(9,8,0.063)])
G.add_weighted_edges_from([(10,1,0.25),(10,2,0.25),(10,3,0.563),(10,4,0.125),(10,5,0.125),(10,6,0.125),(10,7,0.125),(10,8,0.375),(10,9,0.125)])
G.add_weighted_edges_from([(11,1,0.125),(11,2,0.063),(11,3,0.438),(11,5,0.063),(11,6,0.1875),(11,7,0.125),(11,8,0.563),(11,9,0.125),(11,9,0.188)])

nodes = set(G.nodes())
combs = set(itertools.combinations(nodes,6))
sumList = []
for comb in combs:
    S=G.subgraph(list(comb))
    sum=0
    for edge in S.edges(data=True):
        sum+=edge[2]['weight']
    sumList.append((sum,comb))

sorted = sorted(sumList, key=lambda tup: tup[0])    

fo = open("dependency_ranking.txt","wb")

for i in range(0,len(sorted)):
    totalWeight = sorted[i][0]
    nodes = list(sorted[i][1])
    nodes.sort()
    out = str(i)+": "+str(totalWeight)+","+str(nodes)
    fo.write(out.encode())
    fo.write("\n".encode())

fo.close()

S=G.subgraph([1,2,3,4,6,7])
sum = 0
for edge in S.edges(data=True):
        sum+=edge[2]['weight']
print(sum)

Exemple de sortie:

0: 1.0659999999999998,[2, 4, 5, 7, 9, 11]
1: 1.127,[4, 5, 7, 9, 10, 11]
2: 1.128,[2, 4, 5, 9, 10, 11]
3: 1.19,[2, 4, 5, 7, 8, 9]
4: 1.2525,[4, 5, 6, 7, 10, 11]
5: 1.377,[2, 4, 5, 7, 9, 10]
6: 1.377,[2, 4, 7, 9, 10, 11]
7: 1.377,[2, 4, 5, 7, 10, 11]

Graphique d'entrée:

Graphique de la solution:

Pour un exemple de jouet, k = 4, n = 6: Graphique d'entrée:

Graphique de la solution:

Meilleur,

Christian

Trouvez de éléments avec la corrélation la moins paire: étant donné qu'une corrélation de explique de la relation entre deux séries, il est plus logique de minimiser la somme des carrés de corrélations pour vos éléments cibles . Voici ma solution simple.$k$$n$$0.6$$0.36$$k$

Réécrivez votre matrice de corrélations en une matrice de carrés de corrélations. Additionnez les carrés de chaque colonne. Éliminez la colonne et la ligne correspondante avec la plus grande somme. Vous avez maintenant une matrice . Répétez jusqu'à ce que vous ayez une matrice . Vous pouvez également conserver les colonnes et les lignes correspondantes avec les plus petites sommes. En comparant les méthodes, j'ai trouvé dans une matrice avec et que seuls deux éléments avec des sommes proches étaient différemment conservés et éliminés.$n \times n$$(n-1) \times (n-1)$$k \times k$$k$$n=43$$k=20$