Claim: Distance metrics are dubious in high-dimensional space

[Lance Norskog <go...@gmail.com>]

Is this interesting for Mahout?

On the Surprising Behavior of Distance Metrics in High Dimensional Space
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23.7409&rep=rep1&type=pdf
Aggarwal, Hinneburg, Klein

Short story: defines fractional 'L' for l1/l2 etc. norms, claims that
norms 0.0 < L < 1.0 are needed for super-high-dimensional distances.

-- 
Lance Norskog
goksron@gmail.com

Re: Claim: Distance metrics are dubious in high-dimensional space

[Ted Dunning <te...@gmail.com>]

It certainly isn't news that distance metrics mess up in high dimensions.
 The fact that lots of data seems to embed in a lower dimensional manifold
helps.

Fractional norms are occasionally useful (even L_0) but for use with
clustering and as a prior for classification models you have have serious
problems with non-convex optimization problems.  Variable selection is
equivalent to using an L_0 prior and is a classically difficult problem.
 Mahout's SGD typically uses L_1 to avoid these problems.

On Sun, Dec 12, 2010 at 5:46 PM, Lance Norskog <go...@gmail.com> wrote:

> Is this interesting for Mahout?
>
> On the Surprising Behavior of Distance Metrics in High Dimensional Space
>
> http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23.7409&rep=rep1&type=pdf
> Aggarwal, Hinneburg, Klein
>
> Short story: defines fractional 'L' for l1/l2 etc. norms, claims that
> norms 0.0 < L < 1.0 are needed for super-high-dimensional distances.
>
> --
> Lance Norskog
> goksron@gmail.com
>