# Find k of n items with least pairwise correlations

I have a matrix of pairwise correlations between n items. Now I want to find a subset of k items with the least correlation. Thus there are two questions:

1. Which is the appropriate measure for the correlation within that group?
2. How to find the group with the least correlation?

This problem appears like a kind of inverse factor analysis to me and I'm pretty sure that there is a straight-forward solution.

I think this problem actually equals the problem to remove (n-k) nodes from a complete graph so the remaining nodes are connected with minimum edge weights. What do you think?

• This page might help: stackoverflow.com/questions/6782070/… – Timothée HENRY Oct 18 '13 at 12:30
• That now looks somewhat more a graph theory than a statistical question (because correlations are not seen as interdependent anymore). Maybe StackOverflow can yield better answers. Some sort of constrained minimal spanning tree... – ttnphns Oct 18 '13 at 14:21
• @ttnphs: a minimal spanning tree is just the thing I don't want, since pairwise correlations imply a complete graph. Nevertheless, you're right that this question might fit the mathematics-site better. Thanks! – Chris Oct 18 '13 at 16:09
• I'm not clear on what you want. If you were to check all $\binom{n}{k}$ subsets, would you pick the subset with the smallest sum of squared correlations, where the sum is over the $k(k-1)/2$ within-subset correlations? Do the $k(n-k)$ correlations with the remaining $n-k$ items matter? – Ray Koopman Oct 19 '13 at 9:21
• I've given an approximate solution is suggested in the linked question. – Uri Cohen Dec 8 '16 at 9:38

[Forewarning: this answer appeared before the OP decided to reformulate the question, so it may have lost relevance. Originally the question was about How to rank items according to their pairwise correlations]

Because matrix of pairwise correlations isn't a unidimensional array it is not quite clear what "ranking" may look like. Especially as long as you haven't worked out your idea in detail, as it seems. But you mentioned PCA as suitable for you, and that immediately made me to think of Cholesky root as potentially even more suitable alternative.

Cholesky root is like a matrix of loadings left by PCA, only it is triangular. I'll explain both with an example.

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

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


PCA's loading matrix A is the matrix of correlations between the variables and the principal components. We may say it because row sums of squares are all 1 (the diagonal of R) while matrix sum of squares is the overall variance (trace of R). Cholesky root's elements of B are correlations too, because that matrix also has these two properties. Columns of B are not principal components of A, although they are "components", in a sense.

Both A and B can restore R and thus both can replace R, as its representation. B is triangular which clearly shows the fact that it captures the pairwise correlations of R sequentially, or hierarhically. Cholesky's component I correlates with all the variables and is the linear image of the first of them V1. Component II no more shares with V1 but correlates with the last three... Finally IV is correlated only with the last, V4. I thought such sort of "ranking" is perhaps what you seek for?.

The problem with Cholesky decomposition, though, is that - unlike PCA - it depends on the order of items in the matrix R. Well, you might sort the items is descending or ascending order of the sum of squared elements (or, if you like, sum of absolute elements, or in order of multiple correlarion coefficient - see about it below). This order reflects the how much an item is gross correlated.

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


From last B matrix we see that V2, most grossly correlated item, pawns all its correlations in I. Next grossly correlated item V1 pawns all its correlatedness, except that with V2, in II; and so on.

Another decision could be computing Multiple correlation coefficient for every item and ranking based on its magnitude. Multiple correlation between an item and all the other items grows as the item correlates more with all of them but them correlate less with each other. The squared multiple correlation coefficients form the diagonal of the so called image covariance matrix which is $\bf S R^{-1} S - 2S + R$, where $\bf S$ is the diagonal matrix of the reciprocals of the diagonals of $\bf R^{-1}$.

• Thank you so much for this elaborate response, but I'm afraid that I've stated my problem wrong. I am very sure that your post is of use for others and thus vote it up! Thanks! – Chris Oct 18 '13 at 13:43
• @Ray, thank you for being attentive to spot a lapse. – ttnphns Oct 18 '13 at 19:04

Here's my solution to the problem. I calculate all possible combinations of k of n items and calculate their mutual dependencies by transforming the problem in a graph-theoretical one: Which is the complete graph containing all k nodes with the smallest edge sum (dependencies)? Here's a python script using the networkx library and one possible output. Please apologize for any ambiguity in my question!

Code:

import networkx as nx
import itertools
import os

#Create new graph
G=nx.Graph()

#Each node represents a dimension

#For each dimension add edges and correlations as weights

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)


Sample output:

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]


Input graph:

Solution graph:

For a toy example, k=4, n=6: Input graph:

Solution graph:

Best,

Christian

• This might be a good solution. But to appreciate it, one would like to see the graph (the matrix) itself and the solution as graph. Not just the code and and the output. – ttnphns Nov 20 '13 at 16:47
• @ttnphns: I added plots of the resulting graphs and a toy example. – Chris Jul 23 '14 at 8:33
• @Chris Thanks for documenting your solution. Could you add a sentence or two about how long this took to run and how it scales with the number of nodes/dimensions? – Casimir Jul 26 '19 at 18:09
• @Casimir: my apologies for not including this information upfront. However, at this point this post is > 5 years old and I don't have the information at hand anymore. Please feel free to copy & paste the code and do applied or theoretical runtime estimates - I'd appreciate the addition to the post. – Chris Jul 27 '19 at 7:35
• So it might be worth mentioning that in cases where the number of dimensions is in the hundreds or even thousands, this approach is not feasible. But still a cool way to solve this for small problem sizes! – Casimir Jul 27 '19 at 11:35

Find $k$ of $n$ items with the least pairwise correlation: Since a correlation of say $0.6$ explains $0.36$ of the relation between two series it makes more sense to minimize the sum of the squares of correlations for your target $k$ items. Here is my simple solution.

Rewrite your $n \times n$ matrix of correlations to a matrix of squares of correlations. Sum the squares of each column. Eliminate the column and corresponding row with the greatest sum. You now have a $(n-1) \times (n-1)$ matrix. Repeat until you have a $k \times k$ matrix. You could also just keep the columns and corresponding rows with the $k$ smallest sums. Comparing the methods, I found in a matrix with $n=43$ and $k=20$ that only two items with close sums were differently kept and eliminated.

• I tried this method and compared to the graph method of looking up every subgraph and while this method didn't provide the most optimum answer it provided one of the 5 best combinations and of course it is much faster. – SamFisher83 Aug 23 '18 at 16:38