The k-means algorithm is an iterative clustering algorithm that partitions the data points into K clusters (with centroids {$\mu_1, ... , \mu_k$}, minimizing the Sum-of-Squared-Error:

$$ SSE = \sum_{i=1}^K \sum_{x \in S_i} ||x -\mu_i ||^2 $$

K-means uses Euclidean distance (L2 norm) as the distance function , that is $D_{euclidean}= \|(X-Y)\|^2=\sqrt{(x_1-y_1)^2 + ... + (x_n-y_n)^2}$.

My question: If I use Manhattan distance (L1 norm) is used instead of euclidean, is there any guarantee that the algorithm still minimizes SSE? If not, which function is minimized if L1 norm is used?

EDIT: Below is a picture that demonstrates how a 2-D space is partitioned using L1 and L2 norms:

enter image description here



The $L_1$ norm has a big flaw:

try to apply $K$-clustering in a 2d space, with 2 centroids. When you have to say which points are near to which centroid there's a high grade of uncertainty, since the surface wiht the same distance from both centroids has infinite (lebesgue) measure. (on the contrary, euclidean distance has only a line, so a 0-measure set).

So the algorithm isn't really well-defined, and it could not finish with any function

  • $\begingroup$ Thanks. As far as I know, the distance of each point to each of the centroids is not uncertain, as long as the axes are fixed (and not rotated). Is it right? ( Sorry, I am not a mathematician :( ) $\endgroup$ – AliHadian Nov 8 '14 at 20:29
  • $\begingroup$ Once you fix the axes, the distance is not uncertain, but if you have a point that has the same dstance from both centroid, in which cluster do you put it? I'm saying that with L1 norm, there are a lot of point that are at the same distance from both centroids $\endgroup$ – Exodd Nov 8 '14 at 20:54
  • $\begingroup$ I edited the post to show an example. As you see in the picture, bot L2 and L1 norms will partition the space like a Voronoi diagram. Is there any difference between the two metrics? As I see in the picture, the probability that a point drops exactly on the border of two clusters in L1 voronoi seems to be equal to that of L2 norm. Isn't it? $\endgroup$ – AliHadian Nov 9 '14 at 9:11
  • $\begingroup$ try to colour with black all the points that has more then one minimum, end expand the domain $\endgroup$ – Exodd Nov 9 '14 at 10:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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