1
$\begingroup$

The representative point of a cluster or cluster center for the k-means algorithm is the component-wise mean of the points in its cluster. The mean is chosen because it helps to minimize the within cluster variances (which is to say that it is minimizing within cluster squared Euclidean distance, since its the same). Now, when I want to use a different distance metric, like L1 (Manhattan distance), I would be minimizing the within cluster absolute deviations (if I choose to). I was looking at what the centers calculation would be like, because the mean won't reduce the new objective function, and I found this on the Matlab documentation of their kmeans function for the distance parameter

cityblock - Sum of absolute differences, i.e., the L1 distance. Each centroid is the component-wise median of the points in that cluster.

Now, how did they come up with the component-wise median? How does a median minimize absolute deviations?

$\endgroup$
  • 1
    $\begingroup$ See stats.stackexchange.com/questions/34613/… for most of the answer. $\endgroup$ – Nick Cox Aug 19 '13 at 12:14
  • $\begingroup$ @NickCox : Fantastic. Thank you for such a quick response. $\endgroup$ – Prateek Kulkarni Aug 19 '13 at 12:16
  • $\begingroup$ @user603: I see that the geometric median is quiet different from the component-wise median. What were you implying? $\endgroup$ – Prateek Kulkarni Aug 19 '13 at 12:17
  • $\begingroup$ The geometric median is AFAICT known as medoid in clustering, as in k-medoids and PAM. For L1, use the component wise median, as the distance is separable in individual components. $\endgroup$ – Anony-Mousse Aug 19 '13 at 20:25
3
$\begingroup$

The component-wise median can be used.

This is known as k-medians in clustering literature.

If you instead take the most central instance, you can use arbitrary distance functions. This is then known as k-medoids - where the medoid is the most central object of a cluster.

$\endgroup$

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.