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?
$\begingroup$
$\endgroup$
1
asked Jul 27, 2014 at 10:37
-
$\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$– HenryAug 3, 2017 at 7:30
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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.
answered Jul 28, 2014 at 7:57
-
$\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$ Apr 10, 2019 at 8:33
-
1$\begingroup$ I change this to per-axis median. I hope you are happier now. $\endgroup$ Apr 10, 2019 at 23:24
$\begingroup$
$\endgroup$
3
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
-
6$\begingroup$ Can you support and/or explain these assertions in any way? $\endgroup$– jonaJul 27, 2014 at 12:55
-
$\begingroup$ Yeah can you elaborate more please? with examples? $\endgroup$ Jul 27, 2014 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$– FadwaMay 22, 2016 at 14:46