6
$\begingroup$

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

Improve this question
$\endgroup$
1
  • $\begingroup$ There are methods that simultaneously perform dimensionality reduction and clustering. These methods seek an optimally chosen low-dimensional representation so as to facilitate the identification of clusters. For example, see clustrd package in R and the associated references. $\endgroup$
    – Nat
    Oct 3, 2018 at 19:46

1 Answer 1

Reset to default
12
$\begingroup$

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: KDD Process

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.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ Can you say what you mean by "improves results" and "results become worse"? $\endgroup$
    – Macro
    May 24, 2012 at 13:33
  • $\begingroup$ Also 10 was picked only for illustration. Say I have $n$ points in $d$ dimensions. Is there any agreement of $n$-to-$d$ ratio? $\endgroup$
    – danas.zuokas
    May 24, 2012 at 13:39
  • $\begingroup$ Joining @Macro, how do I know if I am better of or worse as I am not given the ground truth? $\endgroup$
    – danas.zuokas
    May 24, 2012 at 13:46
  • $\begingroup$ 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. $\endgroup$
    – Has QUIT--Anony-Mousse
    May 24, 2012 at 15:51
  • $\begingroup$ 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. $\endgroup$
    – rolando2
    May 24, 2012 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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