How to decide if to do dimensionality reduction before clustering?

Is there any agreement on when to reduce data dimension before clustering in order to avoid curse of dimensionality?

My intuition is that if I have say 1000 points and data dimension is 10 then it is OK to cluster. But if dimension is 50 then it is not OK because data points become sparse and hard to cluster (as a result expect to obtain "too much" clusters).

-
add comment

1 Answer

You do dimensionality reduction if it improves results.

You don't do dimensionality reduction if the results become worse.

There is no one size fits all in data mining. You have to do multiple iterations of preprocessing, data mining, evaluating, retry, until your results work for you. Different data sets have different requirements.

Remember how the KDD process looks like:

Notice the grey arrows going back. If the result does not make you happy, try going back and e.g. try to use different preprocessing such as dimensionality reduction.

But 10 dimensions is not high dimensional anyway, probably no need to be afraid of the curse of dimensionality, unless you do some grid based methods.

For the behaviour of high-dimensional data, I can recommend the articles by Houle et al:

• Can Shared-Neighbor Distances Defeat the Curse of Dimensionality?
M. E. Houle, H.-P. Kriegel, P. Kröger, E. Schubert and A. Zimek
SSDBM 2010

They show that there is no direct relationship of the number of dimensions and the ability to cluster the dataset. But it is more a question of the signal-to-noise ratio. A high-dimensional dataset can be very easy and good to cluster if all the dimensions contribute signal. If most of the dimensions are noise, a much smaller dataset will already break down. So in particular, there is no rule of thumb such as "10 is good, 50 is bad", sorry.

-
Can you say what you mean by "improves results" and "results become worse"? –  Macro May 24 '12 at 13:33
Also 10 was picked only for illustration. Say I have $n$ points in $d$ dimensions. Is there any agreement of $n$-to-$d$ ratio? –  danas.zuokas May 24 '12 at 13:39
Joining @Macro, how do I know if I am better of or worse as I am not given the ground truth? –  danas.zuokas May 24 '12 at 13:46
Run it once without dimension reduction. Evalute the result. If it is not good enough, try dimension reduction, evaluate again. Evaluation does not need to be "ground truth". It can be as simple as "are you satisfied". Data mining is exploratory, there may be more than one "solution", or none. –  Anony-Mousse May 24 '12 at 15:51
I like the acknowledgment that a subjective decision is needed re: satisfactoriness of results. Suppose one is evaluating a clustering solution by its eta squareds: how much of the variance in each continuous variable can be explained by the cluster variable. This quantity might reach 80% for variables in one person's clustering problem but would never realistically top 20% in another's. Hence it makes sense that the rule of thumb be stated as generally as Anony-Mousse has. –  rolando2 May 24 '12 at 21:00
show 1 more comment