Find k of n items with least pairwise correlations

Question

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?

Thanks for your suggestions in advance!

Answer 1

[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

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

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}$.

Answer 2

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
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)

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

Answer 3

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.