# $L_1$ or $L_.5$ metrics for clustering?

Does anyone use the $L_1$ or $L_.5$ metrics for clustering, rather than $L_2$ ?
Aggarwal et al., On the surprising behavior of distance metrics in high dimensional space said (in 2001) that

$L_1$ is consistently more preferable then the Euclidean distance metric $L_2$ for high dimensional data mining applications

and claimed that $L_.5$ or $L_.1$ can be better yet.

Reasons for using $L_1$ or $L_.5$ could be theoretical or experimental, e.g. sensitivity to outliers / Kabán's papers, or programs run on real or synthetic data (reproducible please). An example or a picture would help my layman's intuition.

This question is a follow-up to Bob Durrant's answer to When-is-nearest-neighbor-meaningful-today. As he says, the choice of $p$ will be both data and application dependent; nonetheless, reports of real experience would be useful.

I stumbled across "Statistical data analysis based on the L1-norm and related methods", Dodge ed., 2002, 454p, isbn 3764369205 — dozens of conference papers.

Can anyone analyze distance concentration for i.i.d. exponential features ? One reason for exponentials is that $|exp - exp| \sim exp$; another (non-expert) is that it's the max-entropy distribution $\ge$ 0; a third is that some real data sets, in particular SIFTs, look roughly exponential.

• It is important to mention that Aggarwal et al. in that specific article where looking for the behavior of the $L_p$ norms in problems like clustering, nearest neighbor and indexing. – deps_stats Jun 3 '11 at 14:12
• you probably meant $l_p$ metrics for the sequences rather than $L_p$ for functions? In my opinion, if there is any optimization criterion the problem could be solved optimizing it. Rule-of-thumbs usually will be related to the exact solution of such. Anyway, try to think about the k-n-n solution's properties are preferred. After I read the articles probably could say some more on the topic. – Dmitrij Celov Jun 3 '11 at 14:21
• @deps_stats, yes, thanks; changed the title and first line. @Dmitrij, 1) yes little-l is strictly speaking correct, but big-L is common and understandable. 2) yes one can find an optimal p for a given problem, but what's your first choice, and why ? – denis Jun 5 '11 at 14:11

The key here is understanding the "curse of dimensionality" the paper references. From wikipedia: when the number of dimensions is very large,

nearly all of the high-dimensional space is "far away" from the centre, or, to put it another way, the high-dimensional unit space can be said to consist almost entirely of the "corners" of the hypercube, with almost no "middle"

As a result, it starts to get tricky to think about which points are close to which other points, because they're all more or less equally far apart. This is the problem in the first paper you linked to.

The problem with high p is that it emphasizes the larger values--five squared and four squared are nine units apart, but one squared and two squared are only three units apart. So the larger dimensions (things in the corners) dominate everything and you lose contrast. So this inflation of large distances is what you want to avoid. With a fractional p, the emphasis is on differences in the smaller dimensions--dimensions that actually have intermediate values--which gives you more contrast.

• (+1) So @David, in general is there a criterion that describes the quality of contrast? – Dmitrij Celov Jun 3 '11 at 15:32
• It looks like the first paper you linked suggests maximum distance minus minimum distance. There could be better ways, though. – David J. Harris Jun 3 '11 at 17:49
• good clear intuition, +1 (although it's not clear where corners are in distance distributions). Have you used $L_1$ or $L_.5$ on real data ? – denis Jun 7 '11 at 11:45
• @Denis Thanks! I think the corners bit makes the most sense if the data are bounded innmost or all dimensions. Anyway, I'm afraid I don't have enough experience with clustering to have good intuitions about different metrics for you. Annoying as it is, the best approach might be to try a few and see what happens – David J. Harris Jun 7 '11 at 14:43

There is a paper using the Lp metric with p between 1 and 5 that you may wish to take a look:

Amorim, R.C. and Mirkin, B., Minkowski Metric, Feature Weighting and Anomalous Cluster Initialisation in K-Means Clustering, Pattern Recognition, vol. 45(3), pp. 1061-1075, 2012

I don't know whether yours is a problem of inference. If the problem is of inferring a vector from $\mathbb{R}^n$ under certain constraints(which should define a closed convex set) when a prior guess say $u$ is given then the vector is inferred by minimizing $\ell_2$-distance from $u$ over the constraint set (if the prior $u$ is not given then its just by minimizing the $\ell_2$-norm). The above principle is justified as the right thing to do under certain circumstances in this paper http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.aos/1176348385.
• tradition and Csiszar say $L_2$, Aggarwal and a few others $L_1$ or $L_.5$ or ... What to do ? Without solid reasons, I guess it depends on your mindset / your prior beliefs. – denis Jun 6 '11 at 15:43