# 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?

• 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... Oct 18, 2013 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! Oct 18, 2013 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? Oct 19, 2013 at 9:21
• I've given an approximate solution is suggested in the linked question. Dec 8, 2016 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! Oct 18, 2013 at 13:43
• @Ray, thank you for being attentive to spot a lapse. Oct 18, 2013 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. Nov 20, 2013 at 16:47
• @ttnphns: I added plots of the resulting graphs and a toy example. Jul 23, 2014 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? Jul 26, 2019 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. Jul 27, 2019 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! Jul 27, 2019 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. Aug 23, 2018 at 16:38