# Automated procedure for selecting subset of data points w/ strongest correlation?

Is there some standard procedure (such that one might cite it as a reference) for selecting the subset of data points from a larger pool with the strongest correlation (along just two dimensions)?

For instance, say you have 100 data points. You want a subset of 40 points with the strongest correlation possible along the X and Y dimensions.

I realize that writing code to do this would be relatively straightforward, but I'm wondering if there's any source to cite for it?

-
"I realize that writing code to do this would be relatively straightforward". Ah? And how would you do that? –  user603 Jul 10 '12 at 23:03
I suppose she meant something like "best subset correlation"; select subsets of $k$ ($k=40$ in her example) data points out of your $N$ ($N=100$ in her example) and calculate the estimate of the correlation $\rho(X,Y)$ (assuming that she meant to know a subset of points with the best linear correlation). However, this process seems computationally expensive for large $N$, because you have to calculate $\binom{N}{k}$ times the coefficient. –  Néstor Jul 10 '12 at 23:48
If you're willing to look at linear combinations of the $X$ variables, canonical correlations is what you're looking for. Otherwise, correlation feature selection might be of interest. –  MånsT Jul 11 '12 at 6:15
I think some may be misunderstanding me. @Néstor seems to have it right. There are 100 items, each with an X value and a Y value. I want to find the subset of 40 that have the strongest correlation possible (w/ linear regression) between the X and Y values. I can write code to explore the entire search space, but what would I cite to support such a method? What is it called to find the optimal correlation among all possible subsets? –  Julie Jul 13 '12 at 14:27
Are you interested in maximizing the correlation or getting the best fit regression line as, for example, measured by minimum residual variance? The two are not the same when you get to choose your data points. –  jbowman Jul 13 '12 at 22:10
show 1 more comment

## 3 Answers

I would say that your method fits into the general category described in this wikipedia article which also has other references if you need something more than just wikipedia. Some of the links within that article would also apply.

Other terms that could apply (if you want to do some more searching) include "Data Dredging" and "Torturing the data until it confesses".

Note that you can always get a correlation of 1 if you just choose 2 points that don't have identical x or y values. There was an article in Chance magazine a few years back that showed when you have an x and y variable with essentially no correlation you can find a way to bin the x's and average the y's within the bins to show either an increasing or decreasing trend (Chance 2006, Visual Revelations: Finding What Is Not There through the Unfortunate binning of Results: The Mendel Effect, pp. 49-52). Also with a full dataset showing a moderate positive correlation it is possible to choose a subset that shows a negative correlation. Given these, even if you have a legitimate reason for doing what you propose, you are giving any skeptics a lot of arguments to use against any conclusions that you come up with.

-
Excellent answer! –  rolando2 Jul 14 '12 at 1:00
What's the name of the article from The American Statistician? –  Max Jul 16 '12 at 21:07
I misremembered where I saw the article, it was actually in Chance Magazine rather than The American Statistician. I have corrected that above and included the year, title, and page numbers so that interested parties should be able to find copies easily. –  Greg Snow Jul 17 '12 at 17:03
add comment

The RANSAC algorithm sounds like what you want. Basically, it assumes your data consists of a mix of inliers and outliers, and tries to identify the inliers by repeatedly sampling subsets of the data, fitting a model to it, then trying to fit every other data point to the model. Here's the wikipedia article about it.

In your case, you can just keep repeating the algorithm while saving the current best model that fits at least 40 points, so it won't guarantee you the absolute best correlation, but it should get close.

-
add comment

I have a hard time imagining a context in which this would be good practice, but lets assume for a moment that you indeed have a good reason for doing this.

A brute force algorithm could be something like this:

1. You calculate all possible sub-samples of n out of your overall sample of N. Most statistical packages have functions for calculating combinations without replacements that will do this for you.

2. You estimate the correlation between x and y for each one of the sub-samples and select the maximum out of that set.

I just saw the original poster's comment regarding a reference for this procedure. I am not sure that someone has a specific name for this procedure after all you are simply generating an empirical distribution of all possible correlation in your dataset and selecting the maximum. Similar approaches are used when doing bootstraping, but in that case you are interested in the empirical variability, you DO NOT use them to pick a specific sub-sample associated with the max.

-
I presume you have access to the $10^{32}$ or so CPU cycles needed to solve the problem for $N=100$ and $n=40$? (That would be only around a million years if you could harness every PC in the world full time. :-) –  whuber Jul 16 '12 at 19:54
No need to be snarky about it :-p. Fair point. –  David Jul 16 '12 at 20:15
Sorry... I like those figures, though, because they give us lots of room for an improved algorithm :-). –  whuber Jul 16 '12 at 20:21
add comment