0
$\begingroup$

K-means computes cluster centroids differently for each distance metric. I don't know why the way of computing the centroid is dependent of the distance measure.

I don't know how we compute the centroid for manhattan distance and its difference with the computing the centroid for euclidean distance?

Improve this question
$\endgroup$
1
  • $\begingroup$ This question is dubious because you don't say if you mean the distance between data poinrs or the distance between a point and a centroid. Please read a related post stats.stackexchange.com/q/81481/3277 $\endgroup$
    – ttnphns
    Nov 14, 2021 at 19:12

2 Answers 2

Reset to default
3
$\begingroup$

K-means does not work with arbitrary distances, and was originally only formulated with squared errors.

It is for squared Euclidean distance and Bergman divergences.

K-means does not minimize Euclidean distances! It will run, and find an okayish (not obviously wrong) solution; but not even a local optimum. So the simple answer is: don't rely on k-means for other distances. It so not something you can easily fix.

Improve this answer
$\endgroup$
5
  • $\begingroup$ You have an example here ece.northwestern.edu/local-apps/matlabhelp/toolbox/stats/…. It says that kmeans computes centroid clusters differently for the different supported distance measures and it lists the way of computation centroid or center for each distance measure. $\endgroup$
    – curiosus
    Oct 24, 2018 at 8:32
  • 1
    $\begingroup$ Well, is not kmeans but a method known as kmedians if you use the component wise median. And that doesn't just work with some of the fast algorithms for kmeans. $\endgroup$
    – Has QUIT--Anony-Mousse
    Oct 24, 2018 at 20:39
  • 1
    $\begingroup$ For Euclidean distance, you "just" need to solve the Weber problem $\endgroup$
    – Has QUIT--Anony-Mousse
    Oct 24, 2018 at 20:40
  • $\begingroup$ Can you explain more in details the relation between weber problem and k-means and in what that answers the question about why the way of center computation is dependent to the distance measure? $\endgroup$
    – curiosus
    Oct 24, 2018 at 20:47
  • 1
    $\begingroup$ The Weber problem is the difficult problem of finding the most central point for Euclidean distance. That would be what you would need to use instead of the mean if you want to minimize Euclidean distances, essentially a k-weberpoint clustering. $\endgroup$
    – Has QUIT--Anony-Mousse
    Oct 25, 2018 at 1:18
0
$\begingroup$

@curiosus you are right, according to the definition of Kmeans for the Euclidean distance, the centroid whose coordinates are the average of the coordinates of the points of a cluster are simply a local minimum of the inertia, that is the value for which the derivatives of inertia with respect to the centroid are zero. The global minimum is another story.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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