How to reduce the number of variables in cluster analysis?

Question

I've got 10 (yes, only 10) cases over 1000 variables (e.g. measurements of concentrations of 1000 different compounds at 10 different time points). I can group these cases into 3 clusters in 1000-dimensional space (complete linkage, cluster sizes 3, 3, and 4). This partitioning agrees with my expectations, but the clusters are not very well-defined. I suspect that some variables give no or little information, some are noise, and some others are responsible for this particular partitioning. I would like to find out the latter ones, that is, to reduce the number of variables (e.g. to 100-200), so that the cases are partitioned into the same 3 clusters, and these clusters are significantly better defined than the original ones (e.g. by silhouette coefficient). This should be a subset of the original variables, not some new unobserved ones.

I have the following ideas:

• Go through the variables one-by-one and compare cluster solutions in each 1-dimensional space to the original solution. Keep only those variables which produce similar results. Not sure if this would work.
• Go through all the variables in original solution and remove one whose deletion results in the maximum increase in some kind of goodness measure like silhouette coefficient, repeat.
• Attempt to find out those variables which are responsible for most of the variation, e.g. by doing a multidimensional scaling into a few dimensions, and then fit this back into original 1000 dimensions using procrustes rotation, keeping the ones which fit better. This would only work if only a few variables are responsible for the variation, as I understand.
• Delete variables with lowest predictor importance?

Would any of this work? Should I try anything else?

Answer 1

The problem with dimensionality reduction and number of variables >> number of observations is that the $k$ observations that you have define an at most $k-1$ dimensional hyperplane on which the objects perfectly are located on.

So yes, anything more than 9 dimensions still has proven redundancies.

Many dimension reduction techniques - in particular PCA, SVD, but probably also MDS etc. - will essentially try to preserve this hyperplane.

Don't you have a way to reduce the number of dimensions that uses domain information that you have? I.e. if you know that your dimensions are expected to be highly correlated, remove dimensions that are the most correlated (pairwise is probably best). But note that even correlation is not very stable to compute when you have just 10 observations. You lose one degree of freedom for the mean, for example, which you can't really afford.

Answer 2

Here's something else you can try.

This data is similar to what they see in genomics, so you could look to that field for ideas of analysis. In genomics there are lots of variables (20,000+), many of which are highly correlated with each other, and a relatively small number of rows.

If this were a genomics problem, 5 of your rows would be healthy controls and 5 would have some kind of malady and you'd want to find the genes (variables) which help you identify the disease - i.e. feature selection is the main problem.

In your case if you don't know that some of your rows are "good" and some is "bad", you could still use a technique that is good for datasets like this - a random forest.

R's randomForest library does unsupervised clustering. In a nutshell, it will combine your 10x1000 matrix with another 10x1000 matrix consisting of random noise. It then tries to build a model to differentiate between your matrix and the noise.

If you do know some of the rows are "good", then you could still use randomForest - just use it in "supervised" mode.

Regardless, a nice "side effect" of a random forest is you could then examine the importance() of each variable - a variable's importance is measured by averaging its performance across all the trees in used in the random forest.

You could sort this list in descending order of importance, take the top x number of variables, and consider these to be the ones accounting for the most variance in your matrix.

You'd also want to check out the importance metric itself - plot it maybe. If it's flat across the entire range of variables, then no one variable(s) is more predictive than any other. But if, as you suspect, some variables account for more variance, you should see a scree type plot.

I love Random Forests. They are really fast and "embarassingly parallel". They have a weakness of over emphasizing discrete variables with lots of values (e.g. State). That doesn't seem to apply here.

EDIT: Link to Breiman's site. A pretty good explanation.

Answer 3

You could try transposing the data and computing principal components to see which cases load on which components. It might be necessary to rotate the results to get clearer clusters, but ideally you could end up with three good components with each representing the groups you are expecting. Even if that doesn't work, you could then use the principal component scores to cluster your compounds into a smaller number of groups and select the compound closest to the centroid in that group to represent the group.