3
$\begingroup$

K-medians is typically used with Manhattan distance rather than Euclidean distance. Why is this?

$\endgroup$
6
  • 1
    $\begingroup$ Do you have a source for this extraordinary claim? $\endgroup$
    – user603
    Nov 12 '14 at 22:35
  • 1
    $\begingroup$ books.google.com/… $\endgroup$
    – eagle34
    Nov 12 '14 at 22:39
  • $\begingroup$ At "When folks ..." $\endgroup$
    – eagle34
    Nov 12 '14 at 22:40
  • $\begingroup$ One of the benefit of using PAM (K median/K means are not algorithms) is that we can use arbitrary distance metric. That doesn't mean we need to use Manhattan distance. $\endgroup$
    – rivu
    Nov 12 '14 at 22:43
  • $\begingroup$ So, in a way, K median might be used instead of K means when we know Manhattan distance is suitable in our problem. Because, I don't think LLyods algorithm for K means is guaranteed to converge for Manhattan distance. But there might be other reasons for choosing K medoids too. $\endgroup$
    – rivu
    Nov 12 '14 at 22:46
3
$\begingroup$

The mean is a least squares estimator of location. It is appropriate to use with squared deviations (i.e. squared Euclidean distance, k-means algorithm)

The median is the best absolute deviation estimator or location. It is appropriate to use with absolute deviations (i.e. Manhattan distance, k-medians algorithm)

The medoid (c.f. PAM) is a smallest-distance estimator, it works with arbitrary distances. (K-medoids algorithm = PAM).

$\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.