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?


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.

  • $\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$ – nabiltos Oct 24 '18 at 8:32
  • $\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$ – Anony-Mousse Oct 24 '18 at 20:39
  • $\begingroup$ For Euclidean distance, you "just" need to solve the Weber problem $\endgroup$ – Anony-Mousse Oct 24 '18 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$ – nabiltos Oct 24 '18 at 20:47
  • $\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$ – Anony-Mousse Oct 25 '18 at 1:18

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.