21
$\begingroup$

In 1999, Beyer et al. asked, When is "Nearest Neighbor" meaningful?

Are there better ways of analyzing and visualizing the effect of distance flatness on NN search since 1999?

Does [a given] data set provide meaningful answers to the 1-NN problem? The 10-NN problem? The 100-NN problem?

How would you experts approach this question today?

Edits Monday 24 Jan:

How about "distance whiteout" as a shorter name for "distance flatness with increasing dimension" ?

An easy way to look at "distance whiteout" is to run 2-NN, and plot distances to the nearest neighbor and second-nearest neighbors. The plot below shows dist1 and dist2 for a range of nclusters and dimensions, by Monte Carlo. This example shows pretty good distance contrast for the scaled absolute difference |dist2 - dist1|. (The relative differences |dist2 / dist1| → 1 as dimension → ∞, so become useless.)

Whether absolute errors or relative errors should be used in a given context depends of course on the "real" noise present: difficult.

Suggestion: always run 2-NN; 2 neighbors are useful when they're close, and useful when not.

enter image description here

Improve this question
$\endgroup$
5
  • 7
    $\begingroup$ Beyer et al. seem to be addressing a little bit different aspect of the NN problem. But, for (binary) classification purposes, under mild conditions, it is a classical result that 1-NN classification has, in the worst case, twice the probability of error of the Bayes (i.e., optimal) classifier asymptotically. In other words, the first nearest neighbor contains "at least half the information" about the label of the target as the best classifier does. In this sense, the 1-NN seems quite relevant. (See Cover & Hart (1967) for more. I'm surprised Beyer et al. doesn't cite it.) $\endgroup$
    – cardinal
    Feb 5 '11 at 23:13
  • $\begingroup$ @cardinal, the Cover-Hart bound seems not to depend on dimension at all, as you say a different aspect ? $\endgroup$
    – denis
    Feb 8 '11 at 11:53
  • $\begingroup$ yes I believe this is true and this was, in large part, my point in bringing it up. 1-NN seems pretty relevant in that sense, i.e., the fact that it works (so) well (theoretically) uniformly in the dimension of the feature space seems to help it stand on it's own, regardless of what the behavior of the nearest and farthest neighbors is in a large dimensional space. It makes me wonder if Beyer was aware at all of this (classical) result. $\endgroup$
    – cardinal
    Feb 8 '11 at 13:08
  • $\begingroup$ @cardinal The top of page 24 in Cover and Hart looks like a place where an issue may potentially arise in their proof, in the step where Cover and Hart argue that every RV x \in X has the property that every open sphere about x has non-zero measure. If we consider the geometry of the hypersphere we see that the volume of the interior of the hypersphere shrinks with increasing dimension so, in the limit, the open ball about x contains only x in its interior. Alternatively, via the SLLN, the iid RVs x in the metric space X all lie in the surface of the hypersphere with probability one. $\endgroup$
    – Bob Durrant
    May 20 '11 at 9:47
  • $\begingroup$ See also L1 or L.5 metrics for clustering. $\endgroup$
    – denis
    Jun 5 '11 at 14:17
13
$\begingroup$

I don't have a full answer to this question, but I can give a partial answer on some of the analytical aspects. Warning: I've been working on other problems since the first paper below, so it's very likely there is other good stuff out there I'm not aware of.

First I think it's worth noting that despite the title of their paper "When is `nearest neighbor' meaningful", Beyer et al actually answered a different question, namely when is NN not meaningful. We proved the converse to their theorem, under some additional mild assumptions on the size of the sample, in When Is 'Nearest Neighbor' Meaningful: A Converse Theorem and Implications. Journal of Complexity, 25(4), August 2009, pp 385-397. and showed that there are situations when (in theory) the concentration of distances will not arise (we give examples, but in essence the number of non-noise features needs to grow with the dimensionality so of course they seldom arise in practice). The references 1 and 7 cited in our paper give some examples of ways in which the distance concentration can be mitigated in practice.

A paper by my supervisor, Ata Kaban, looks at whether these distance concentration issues persist despite applying dimensionality reduction techniques in On the Distance Concentration Awareness of Certain Data Reduction Techniques. Pattern Recognition. Vol. 44, Issue 2, Feb 2011, pp.265-277.. There's some nice discussion in there too.

A recent paper by Radovanovic et al Hubs in Space: Popular Nearest Neighbors in High-Dimensional Data. JMLR, 11(Sep), September 2010, pp:2487−2531. discusses the issue of "hubness", that is when a small subset of points belong to the $k$ nearest neighbours of many of the labelled observations. See also the first author's PhD thesis, which is on the web.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks Bob, +1. A related question, would you have a rule of thumb for choosing a value of fractional-metric q (or should I ask that as a separate question) ? $\endgroup$
    – denis
    May 22 '11 at 15:31
  • $\begingroup$ @Denis Probably merits a question of its own as I think it's both data and application dependent. These fractional metrics with $q=1/p$ aren't really metrics in the formal sense for $p>1$ (the sense of the triangle inequality gets reversed for example, so they are non-convex) and as $p$ increases you're converging on the $l_0$ `metric'. I'd start with $p=1$ since $l_{1}$ is not as problematic to work with as $l_{q=1/p}$ when $p>1$, and fit the parameter $p$ from data. Possibly someone has found an automated way to do this by now, but I don't know. $\endgroup$
    – Bob Durrant
    May 23 '11 at 9:14
  • $\begingroup$ Bob, isn't $\sum |a_j - b_j|^q$ (without the outer $1/q$) a metric for 0 $< q <$ 1, satisfying the triangle inequality ? $\endgroup$
    – denis
    May 24 '11 at 15:31
  • $\begingroup$ That's just the regular $\ell_{p}$ norm in disguise though then, isn't it? $\endgroup$
    – Bob Durrant
    Jun 1 '11 at 9:08
3
$\begingroup$

You might as well be interested in neighbourhood components analysis by Goldberger et al.

Here, a linear transformation is learned to maximize the expected correctly classified points via a stochastic nearest neighbourhood selection.

As a side effect the (expected) number of neighbours is determined from the data.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks bayer. It seems that "distance metric learning" is booming -- scholar.goo has 50 titles since 2008. But is the boom paper, or real use ? Footnote, the code for nca says "iterations ... at least 100000 for good results". Footnote 2, most of the work on distance metric learning seems to model a Mahalanobis distance; would you know of other distance models ? $\endgroup$
    – denis
    May 24 '11 at 15:00
  • $\begingroup$ I have different experiences with NCA -- it usually converges quite qickly for me. Checkout "dimensionality reduction via learning an invariant mapping" by LeCun and "Minimal Loss Hashing for Compact Binary Codes" by Norouzi. $\endgroup$
    – bayerj
    May 26 '11 at 11:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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