3
$\begingroup$

I have a set of variables, some of which are very similar to one another. I am seeking to break these variables into subsets, each of which only contains variables whose pairwise correlation coefficients are all above a certain threshold.

For example, with a minimum threshold of 0.85 and this matrix of correlation coefficients: $$ \begin{matrix} & v_1 & v_2 & v_3 & v_4 & v_5 & v_6 & v_7 & v_8\\ v_1 & \color{green}{1.0} & \color{green}{.92} & \color{green}{.87} & .07 & \color{green}{.88} & .56 & .47 & .39\\ v_2 & \color{green}{.92} & \color{green}{1.0} & \color{green}{.93} & .12 & \color{green}{.89} & .61 & .51 & .48\\ v_3 & \color{green}{.87} & \color{green}{.93} & \color{green}{1.0} & .10 & \color{green}{.90} & .60 & .52 & .55\\ v_4 & .07 &.12 &.10 & \color{green}{1.0} & .09 & .12 & .10 & .11\\ v_5 & \color{green}{.88} & \color{green}{.89} & \color{green}{.90}& .09 & \color{green}{1.0} & .61 & .58 & .44\\ v_6 & .56 & .61 & .60& .12& .61& \color{green}{1.0} & \color{green}{.91} & \color{green}{.90}\\ v_7 & .47 &.51 &.52 & .10& .58&\color{green}{.91} & \color{green}{1.0} & \color{green}{.92}\\ v_8 & .39 & .48& .55& .11&.44 &\color{green}{.90} &\color{green}{.92} & \color{green}{1.0}\\ \end{matrix} $$

The resulting sets of variables would be: $$ \{v_1,v_2,v_3,v_5\},\{v_4\},\{v_6,v_7,v_8\} $$

Obviously, this can be reduced to a Boolean matrix; I have described the problem in this way because my particular use-case involves correlation coefficients.

Is there a way to obtain the sets of variables in a way that is more trivial than brute-force?

Edit:

Thank you all for your detailed and informative comments and answers. You provided with a lot to think about for this particular problem as well as some situations I'm bound to encounter down the road. Perhaps I should have further specified my use-case for this particular problem.

My specific application is genome sequencing, where I am hoping to maximize the amount of data I can use from an experiment. Essentially, each genomic locus in my dataset has a number of binary ($0/1$) measurements from many biological samples. Let's say that locus $x$ has $n_{x,s}$ measurements from sample $s$, and $m_{x,s}$ of those measurements are $1$. Then $v_{x,s}=m_{x,s}/n_{x,s}$, and the correlation coefficient between the measurements at, say, loci $2$ and $4$ across all samples is given in the above matrix ($\mathrm{Cor}(v_2,v_4)=.12$). Note that, when $n_{x,s}$ is small, the resolution of $v_{x,s}$ is very low, and so I need to exclude sample $s$ from consideration at locus $x$.

In the example above, $v_1,v_2,v_3,v_5$ are all highly correlated with one another. In my downstream analysis, I would aim to either use one of those four loci from that set (i.e., $1,2,3,$ or $5$) as a representative for the other three (choosing the one with the highest $n$ in each sample), or more likely, I would combine the measurements across all the loci in that set in each sample to create a single measurement from all four loci, i.e. $v_{combined,s} = m_{combined,s}/n_{combined,s} = (\sum\limits_{i=\{1,2,3,5\}}{m_{i,s}}) / (\sum\limits_{i=\{1,2,3,5\}}{n_{i,s}})$. Ultimately, I will be focusing the rest of my experiments on loci with population-level variance (i.e. where $\mathrm{Var}(v_{locus})$ is high). The latter approach allows me to make use of all of the (expensive) data that I have (so long as $n_{combined,s}$ is sufficiently large).

There are several thousand genomic regions I am investigating, and each region contains anywhere from two to dozens (in some cases hundreds) of loci. For each region, I want to maximize the number of loci that I can 'combine'. I can obtain more sequencing data from these samples, and am hoping to order (and pay for) more data from some samples that are currently underpowered. If I can combine data from multiple loci as described above, then I can potentially order less sequencing per sample at a substantial cost savings.

$\endgroup$
  • $\begingroup$ Maybe you can try cluster analysis. $\endgroup$ – user158565 Aug 2 '19 at 16:47
  • $\begingroup$ @user158565 Good point - Though I suppose the gist of my question is whether there is a fast (possibly completely matrix-based) way to do this, as I am seeking to do this on thousands of sets of variables $\endgroup$ – knowah Aug 2 '19 at 16:50
  • 1
    $\begingroup$ What do you imagine by a non brute-force method? Some formula/algorithm that spits out these sets of variables with minimal effort? It is not a partition of the vectors into sets for which such an straighforward algorithm might be imaginable, but you might have awkward matrices like $$\begin{array}{} &v_1&v_2&v_3 \\ v_1&1&1& 0 \\ v_2&1&1&1 \\ v_3&0&1&1 \end{array}$$ which are not nice blocks and sets of vectors are overlapping (ie it will be $\{v_1,v_2\},\{v_2,v_3\}$). So it will be most likely some sort of algorithm that looks up the accompanying lines with each row/column. $\endgroup$ – Sextus Empiricus Aug 3 '19 at 1:31
  • $\begingroup$ Do you look for a solution to this exact problem, or are you looking for ways to alternatively partition the variables into sets (e.g. by using pca)? What is the underlying problem/use-case? $\endgroup$ – Sextus Empiricus Aug 3 '19 at 1:35
5
$\begingroup$

This sounds like a clique detection problem. To get there, we will frame the problem as one of graph theory.

First, set all elements above your threshold to 1 and all other elements to 0. This is a symmetric adjacency matrix.

In your example, the subsets are all either cliques or singletons. A clique is a complete subgraph, so the task reduces to discovering all maximal cliques; that is, find all sets of variables such that all pairs of variables in the set have correlation coefficients above some threshold and such that set cannot be enlarged. (The second condition is necessary because a 4-clique contains several 3-cliques, and you want the largest such groupings.)

https://en.wikipedia.org/wiki/Clique_problem

Your question is a bit ambiguous when you consider what happens for cliques that overlap: do you relax the clique requirement, and group all of the overlapping cliques together, or do you disregard them because the union of vertices in overlapping cliques do not themselves form a single clique?

If we relax the clique requirement, then we could do something like community detection, which recursively divides the graph into partitions which have tighter affiliation among itself than expected by random affiliations. (But you probably want to use the Louvian algorithm which has the nicer $O(n \log n)$ complexity.)

M. E. J. Newman. "Modularity and community structure in networks" https://www.pnas.org/content/103/23/8577


After @whuber's comment and re-reading the question, it seems this is about clique detetion. Originally, my answer focused on connected components, but that does not respect the requirement that all nodes in a partition have high correlation with each other. Previous versions of this answer are visible in the edit history.

$\endgroup$
  • $\begingroup$ The question is not that of finding connected components: it's that of finding a partition of nodes into universal subgraphs. The distinction is that in a connected component, a pair of variables may have zero correlation, but lie in the component due to a chain of sufficiently high correlations with intermediate variables. $\endgroup$ – whuber Aug 2 '19 at 21:16
  • 1
    $\begingroup$ @whuber Upon re-reading the question, I think you're correct. So OP is looking for cliques, not connected components. $\endgroup$ – Sycorax says Reinstate Monica Aug 2 '19 at 21:20
  • $\begingroup$ Although finding all maximal cliques would be a great first step, it wouldn't constitute a solution. A useful example to bear in mind is a Toeplitz correlation matrix $a_{ij}=\rho^{|i-j|}$ ($\rho\gt 0$) where for some integer $1\le s \lt n,$ $\rho^s$ is the threshold correlation. The maximal cliques are all the subsets $\{i,i+1,\ldots, i+s\}$ for $i=1,2,\ldots, n+1-s,$ but they overlap. When $n$ is not a multiple of $s+1,$ any solution will include at least one non-maximal clique. $\endgroup$ – whuber Aug 2 '19 at 21:29
  • $\begingroup$ This is true, but it seems to be a reason that the problem is under-specified; that is, it seems OP has an intuition in mind that the problem must collapse to disjoint cliques but answer writers don't have guidance about what to do in any case where cliques overlap. If we weaken the clique requirement, then we could do things like community detection, but that's a bit of a leap since it goes against the express intent of the question. $\endgroup$ – Sycorax says Reinstate Monica Aug 2 '19 at 21:34
  • 2
    $\begingroup$ @Sycorax The clique problem is an abstraction of exactly what I am describing. Thank you (and @whuber) for realizing this and pointing me in this direction. I have edited the question to provide more details about my particular use case, but identifying maximal cliques appears to be what I need. $\endgroup$ – knowah Aug 5 '19 at 14:20
1
$\begingroup$

To me, this question sounds like a constrained, dynamic, real-time dimension reduction problem. There are many possible methods which would address this and the choice is a matter for subjective judgement, predisposition, skill and training. Basing that choice on pairwise correlations alone would not be on my list of options.

PCA (principal components analysis) is a classic approach to dimension reduction although it doesn't scale well to lots and lots of features (thousands? you didn't specify the quantity).

Vowpal Wabbit is a machine learning method for fast, real-time, scalable analysis. It is worth a look as it is open-source and free to use. https://en.wikipedia.org/wiki/Vowpal_Wabbit

Another approach would be to employ partial differential equations, an area which has seen a huge amount of developmental work, particularly wrt real-time, big data. One person doing some of the best work using PDEs is Nathan Kutz at the Univ of Washington. His published work is voluminous (see his Google Scholar citations) but this article is recent and looks like it would be relevant to your question, Data-driven multiscale decompositions for forecasting and model discovery https://arxiv.org/pdf/1903.12480.pdf Along with his articles, he also has many tutorial videos posted on Youtube, e.g., https://www.youtube.com/watch?feature=youtu.be&v=Oifg9avnsH4&app=desktop

Tensors can be described as matrices of matrices, i.e., matrices which compress a larger set of matrices, a classic objective of dimension reduction. Google's Tensorflow is one open-source algorithm for implementing tensors. Their evangelists tout TF as being 'so easy to use, it frees you up from worrying about the details of programming, allowing you to think more about what the results mean' -- a questionable claim. Regardless, TF algorithms scale well. For instance, I've heard about a TF algorithm with 5 billion parameters but that would probably not be necessary for your purposes. Not having used TF for your specific objectives, I don't know how well it integrates with dynamic, real-time analysis but it should be on your list of options. Like Kutz, there is a TF Youtube channel with tutorials.

Finally, you mention an issue with boundary conditions or constraints on the strength of the association. I foresee only problems with this rule. Why are you imposing it? First of all, correlation usually means Pearson correlation -- a measure of strictly linear association which is not at all representative of nonlinear relationships. Other metrics are available which do capture nonlinear dependence such as entropy, maximal mutual information criterion, distance correlations, and so on.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.