16
$\begingroup$

I know there is k-means clustering algorithm and k-median. One that uses the mean as the center of the cluster and the other uses the median. My question is: when/where to use which?

$\endgroup$
1
  • $\begingroup$ You are going to have to define medians (and perhaps calculate them) if you have more than one dimension; if you just take the median in each value then you lose rotational properties. A further possibility is k-medoids $\endgroup$ – Henry Aug 3 '17 at 7:30
17
$\begingroup$

k-means minimizes within-cluster variance, which equals squared Euclidean distances.

In general, the arithmetic mean does this. It does not optimize distances, but squared deviations from the mean.

k-medians minimizes absolute deviations, which equals Manhattan distance.

In general, the per-axis median should do this. It is a good estimator for the mean, if you want to minimize the sum of absolute deviations (that is sum_i abs(x_i-y_i)), instead of the squared ones.

It's not a question about accuracy. It's a question of correctness. ;-)

So here's your decision tree:

  • If your distance is squared Euclidean distance, use k-means
  • If your distance is Taxicab metric, use k-medians
  • If you have any other distance, use k-medoids

Some exceptions: as far as I can tell, maximizing cosine similarity is related to minimizing squared Euclidean distance on L2-normalized data. So if your data is L2 normalized; and you l2-normalize your means each iteration, then you can use k-means again.

$\endgroup$
2
  • $\begingroup$ I somewhat take issue with the statement that the median minimizes manhattan distance, since there is no unique agreed on concept of a median for multidimensional data. It's not false, but I find it a misleading statement to make in a multidimensional context. There are multiple multidimensional generalizations of medians, many of which have no connection to minimizing manhattan distances. $\endgroup$ – Tim Seguine Apr 10 '19 at 8:33
  • 1
    $\begingroup$ I change this to per-axis median. I hope you are happier now. $\endgroup$ – Has QUIT--Anony-Mousse Apr 10 '19 at 23:24
2
$\begingroup$

If you want to make an analysis not regarding of the possible effect of extreme values use k means but if you want to be more accurate use k median

$\endgroup$
3
  • 6
    $\begingroup$ Can you support and/or explain these assertions in any way? $\endgroup$ – jona Jul 27 '14 at 12:55
  • $\begingroup$ Yeah can you elaborate more please? with examples? $\endgroup$ – Jack Twain Jul 27 '14 at 14:15
  • 4
    $\begingroup$ I think that's because "Median" can tolerate the outliers but "Mean" is totally affected by them. For example: if we have the data points{1,2,3,5,78} its obvious that 78 is outlier. The median of these data is 3 and the mean is 17.8. So the median is the best way to summarize these data. $\endgroup$ – Fadwa May 22 '16 at 14:46

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.