15
$\begingroup$

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.

Notes added Tuesday 7 June:

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.

Improve this question
$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – deps_stats
    Commented Jun 3, 2011 at 14:12
  • $\begingroup$ 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. $\endgroup$
    – Dmitrij Celov
    Commented Jun 3, 2011 at 14:21
  • $\begingroup$ @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 ? $\endgroup$
    – denis
    Commented Jun 5, 2011 at 14:11
  • $\begingroup$ @denis, In stats.stackexchange.com/a/6409 you shared something really interesting. Do you have the code to replicate this? The link is broken. $\endgroup$
    – Royi
    Commented Jul 14, 2023 at 11:13
  • $\begingroup$ @denis, I am after searching for the optimal K using MST as you posted. Do you have the code to replicate it? $\endgroup$
    – Royi
    Commented Jul 16, 2023 at 12:50

3 Answers 3

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ (+1) So @David, in general is there a criterion that describes the quality of contrast? $\endgroup$
    – Dmitrij Celov
    Commented Jun 3, 2011 at 15:32
  • $\begingroup$ It looks like the first paper you linked suggests maximum distance minus minimum distance. There could be better ways, though. $\endgroup$
    – David J. Harris
    Commented Jun 3, 2011 at 17:49
  • $\begingroup$ 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 ? $\endgroup$
    – denis
    Commented Jun 7, 2011 at 11:45
  • 1
    $\begingroup$ @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 $\endgroup$
    – David J. Harris
    Commented Jun 7, 2011 at 14:43
1
$\begingroup$

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

Download, https://www.researchgate.net/publication/232282003_Author's_personal_copy_Minkowski_metric_feature_weighting_and_anomalous_cluster_initializing_in_K-Means_clustering/file/d912f508115a040b45.pdf

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – denis
    Commented Jun 6, 2011 at 15:43

Your Answer

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

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