9
$\begingroup$

Some where I read a note that if you have many parameters $(x_1, x_2, \ldots, x_n)$ and you try to find a "similarity metric" between these vectors, you may have a "curse of dimensioality". I believe it meant that most similarity scores will be equal and not giving you any useful information. In other words almost all partner vectors will have some medium distance score which isn't useful for categorisation or clustering etc.

Do you know where I can learn more in detail about that?

Are there metrics which suffer less from this effect?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
13
$\begingroup$

Some classic observations on distances in high-dimensional data:

  • K. Beyer, J. Goldstein, R. Ramakrishnan, and U. Shaft, ICDT 1999: "When is Nearest Neighbors Meaningful?"
  • C. C. Aggarwal, A. Hinneburg, and D. A. Keim, ICDT 2001: "On the Surprising Behavior of Distance Metrics in High Dimensional Space"

A couple more recent research on this, which involves shared-nearest neighbors and hubness:

  • M. E. Houle, H.-P. Kriegel, P. Kröger, E. Schubert and A. Zimek, SSDBM 2010: "Can Shared-Neighbor Distances Defeat the Curse of Dimensionality?"
  • T. Bernecker, M. E. Houle, H.-P. Kriegel, P. Kröger, M. Renz, E. Schubert and A. Zimek, SSTD 2011: "Quality of Similarity Rankings in Time Series"
  • N. Tomašev, M. Radovanović, D. Mladenić, and M. Ivanović. Adv. KDDM 2011: "The role of hubness in clustering high-dimensional data"
  • Don't remember the others, search for "Hubness", that was their high-dimensional observation

These are interesting, as they point out some popular misunderstandings about the curse of dimensionality. In essence they show that the theoretical results - which assume the data to be i.i.d. - may not be generally true for data that has more than one distribution. The curse leads to numerical problems, and a loss of discrimination within a single distribution, while it can make it even easier to differentiate two distributions that are well separated.

Some of this should be rather obvious. Say you have objects which are $A_i\sim \mathcal{N}(0;1)$ i.i.d. in each dimension and another set of objects that are $B_i\sim \mathcal{N}(100;1)$ i.i.d. in each dimension. The difference between objects from two different sets will always be magnitudes larger than a distance within a single set, and the problem will even get easier with increasing dimensionality.

I recommend reading this work by Houle et al., largely because it shows that by claiming "this data is high-dimensional, and because of the curse of dimensionality it cannot be analyzed" you might be making things a bit too easy. Still that is a line that is being used all over the place. "Our algorithm only works only for low dimensional data, because of the curse of dimensionality." "Our index only works for up to 10 dimensions, because of the curse of dimensionality." Yadda yadda yadda. Many of these statements apparently just show that such authors have not understood what happens at high dimensionality in their data and algorithm (or needed an excuse). Houle et al. don't completely solve the puzzle (yet? this is fairly recent), but they at least reconsider many of the popular statements.

After all, if high dimensionality were this big a problem, how come that in text mining people happily use dimensionalities on the order of 10000-100000, while in other domains people give up at just 10 dimensions?!?

As for the second part of your question: cosine similarity seems to suffer less from the dimensionality. Apart from that, as long as you want to differentiate different distributions, control numerical precision and do not rely on hand-chosen thresholds (as you might need to give them with lots of significant digits), classic $L_p$-Norms should still be fine.

However, Cosine is also affected from the curse of dimensionality, as discussed in:

  • M. Radovanović, A. Nanopoulos, and M. Ivanović, SIGIR 2010. "On the existence of obstinate results in vector space models."
Improve this answer
$\endgroup$
10
$\begingroup$
  • Aggarwal C. C., Hinneburg A., Keim, D. A. (2001), ”On the Surprising Behavior of Distance Metrics in High Dimensional Space”
  • Beyer K., Goldstein J., Ramakrishnan R., Shaft U. (1999), ”When is Nearest Neighbors Meaningfull?”, ICDE Conference Procedings.
Improve this answer
$\endgroup$
6
  • $\begingroup$ Sounds interesting :) I hope I can get a copy of these. Do you know whether resolutions exist to this problem with ordinary metrics? $\endgroup$
    – Gere
    Jan 23, 2012 at 13:06
  • $\begingroup$ (+1) this looks very interesting. $\endgroup$
    – Elvis
    Jan 23, 2012 at 13:35
  • $\begingroup$ @Gerenuk: what do you mean by 'ordinary' metrics? Also, both papers are avail. online, ungated, as pdfs $\endgroup$
    – user603
    Jan 23, 2012 at 14:09
  • $\begingroup$ Thanks. I think I found them by title name. By ordinary metric (I think) I mean $L_k$ norms. So the question is if there is some simple similarity finder which does a better job than $L_k$ norms. $\endgroup$
    – Gere
    Jan 23, 2012 at 14:18
  • 1
    $\begingroup$ Fractional L_p norms only hide the problem. I believe the result then tends towards something like the minimum attribute difference, which for a high number of dimensions becomes just as meaningless in practise. It only solves the problem of the numbers getting larger and larger. Dimension reduction works in some cases, but consider the case when it doesn't get you any further. What then? Plus, dimension reduction essentially is "640k dimensions ought to be enough for anybody". Text is commonly in the 10^5 range. What about video? $\endgroup$
    – Has QUIT--Anony-Mousse
    Jan 27, 2012 at 17:58
2
$\begingroup$

Also:

  • Robert J. Durrant, Ata Kabán: When is 'nearest neighbour' meaningful: A converse theorem and implications. J. Complexity 25(4): 385-397 (2009)

  • Ata Kabán: On the distance concentration awareness of certain data reduction techniques. Pattern Recognition 44(2): 265-277 (2011)

  • Ata Kabán: Non-parametric detection of meaningless distances in high dimensional data. Statistics and Computing 22(2): 375-385 (2012)

Improve this answer
$\endgroup$

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.