4
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

marked as duplicate by Anony-Mousse clustering Jan 20 '16 at 13:17

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Anony-Mousse Jan 20 '16 at 13:20
  • $\begingroup$ Dang! Thanks for pointing this out - learnt something today! :) $\endgroup$ – Jeremias K Jan 20 '16 at 14:03
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – shadowtalker Jan 20 '16 at 12:08
  • $\begingroup$ 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. $\endgroup$ – user112758 Jan 20 '16 at 12:12
  • $\begingroup$ The standard algorithm is not just "heuristic search". It's a L2 optimizarion. $\endgroup$ – Anony-Mousse Jan 20 '16 at 13:16
  • $\begingroup$ @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? $\endgroup$ – shadowtalker Jan 20 '16 at 13:30
  • $\begingroup$ 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. $\endgroup$ – Anony-Mousse Jan 20 '16 at 13:37

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