# Is there a situation when one would use L1 norm over L2 norm in k-means algorithm? [duplicate]

Is there a situation when one would use L1 norm over L2 norm in k-means algorithm?

In most of the articles online, k-means all deal with l2-norm. L1 norm does not seem to be useful because it is not differentiable. However, when looking at only places where the norm is differentiable, is there a case for one to use l1 norm in k-means algorithm?

I cannot think of a general case where this would consistently prove to be better/worse. Data-specific cases may arise, but the only thing required to make the k-means algorithm work is any kind of metric.

In general, for $L_p$ being the norm of choice, the higher you choose $p$, the more important the largest single feature/variable distance becomes. Taking this to the extreme, for $p \rightarrow \infty$ and observations $x_{1}$ and $x_{2}$, $distance(L_p, x_1, x_2) = max_i\{x_{1,i} - x_{2,i}\}$. (Here, we assume we have $x_{1} \in \mathbb{R}^n$ and $1 \leq i \leq n$, so $i$ indexes the features).

Building on this, you could say that the larger you choose $p$, the more weight your metric will put on the largest distance between two observations when clustering. The opposite counter-extreme is $p=1$, where all distances receive the same weight and the combination of the absolute valued differences is linear.

I hope this helps you - let me know if I have not been clear enough.

• No. It is not sufficient to provide "any kind of metric". Because of the mean in k-means. You can find some counterexamples here on Stackoverflow e.g. for Pearson Correlation. Only for Bregman divergences, k-means is proven to converge. Jan 20, 2016 at 13:20
• Dang! Thanks for pointing this out - learnt something today! :) Jan 20, 2016 at 14:03

If you use the L1 norm, you also need to use the median instead of the mean. Because the median is the L1 estimator of location, whereas the mean is the L2 estimator.

That is known as the k-medians algorithm.

P. S. Bradley, O. L. Mangasarian, and W. N. Street, "Clustering via Concave Minimization," in Advances in Neural Information Processing Systems, vol. 9, M. C. Mozer, M. I. Jordan, and T. Petsche, Eds. Cambridge, MA: MIT Press, 1997, pp. 368–374.

I think one reason is that, the "mean" procedure minimizes sum of L2 norms but not L1 norms.

• But given that the standard algorithm is just heuristic search, couldn't it easily be modified to minimize the sum of L1 norms as well? I think a bigger concern is what would happen to the properties of the solution under L1 minimization Jan 20, 2016 at 12:08
• maybe... I do not know how most packages implement kmeans. I thought they just use "means". But at least, L2 norm is related to variances but L1 norm does not. Jan 20, 2016 at 12:12
• The standard algorithm is not just "heuristic search". It's a L2 optimizarion. Jan 20, 2016 at 13:16
• @Anony-Mousse ok, but all the same couldn't you swap out WSS with an L1 equivalent? Or does Lloyd use math specific to thr L2 norm? Jan 20, 2016 at 13:30
• Yes: the mean is specific to minimizing L2. It does not minimize other distances. See my answer, and the linked duplicate questions answers for more details. Jan 20, 2016 at 13:37