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.
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.
