4
$\begingroup$

I'm a bit confused with concept of K-medoids.

It seems that original algorithm (PAM) describes that swap step should be performed by swaping only one of the medoids with one non-medoid point from the whole dataset (not only in cluster of that medoid), which will lead to smallest error in that moment.

First of all, is my understanding correct?

My original idea (which I implemented) swaps all of the medoids in one iteration, each medoid can be replaced by a point from its cluster, that leads to smallest error in its cluster. Is this a bad approach?

I was mislead by K-means, which calculates its centroid based only on the points from its cluster, but now I'm not sure if the same logic has sense for K-medoids.

Also, just to add, I implemented K-means++ like initialization, to optimize the procedure.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

K-Medoids is the problem of finding a set of K representative objects of the dataset such to minimize the total dissimilarity of each object from its nearest representer.

The PAM is an approximate solution to this problem that falls in the category of local search algorithms. It is made of two phases:

  • the BUILD step in which an initial solution is built. It starts by selecting as the first medoid the object with the lowest mean dissimilarity w.r.t. the whole dataset (i.e., the most central object). Iteratively medoids are selected as the objects that further minimize the overall dissimilarity of each object from its nearest medoid.

  • the SWAP phase in which given the current solution (the set of k medoids) all the neighbour solutions are evaluated. A neighbour solution is constructed by swapping one of the current medoids with one of the non-selected objects. Thus the size of the neighborhood of a given solution is $(n-k)*k$ where $n$ is the total number of objecs of the dataset and $k$ is the number of wanted medoids.

Now, to answer your questions:

  1. Yes, your understanding is correct.
  2. You developed a k-means-like solution to the k-medoids problem. In your case the neighborhood of a given solution varies with the current clustering.

It may be better or worse than PAM, you may compare them evaluating:

  • How much iterations they take to converge;
  • The quality of the final solutions;
  • How long it takes to complete an iteration;
  • How well both scale with respect of the number of objects and of features in the dataset

If memory serves me right there should also be a paper around about a k-means like k-medoids algorithm.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Swapping like > A neighbour solution is constructed by swapping one of the current medoids with one of the non-selected objects. actually doesn't make sense to me, but the way the thread starter mentioned it does. Because first you swap, without reassigning any object to other clusters yet, so if you swap with an object outside of the own cluster you could never further minimize the overall dissimilarity of each object from its nearest medoid, because then the medoid would move outside of the radius of the cluster. Could someone tell me where my misunderstanding would be? $\endgroup$
    – dominic
    Apr 23, 2015 at 5:05
  • $\begingroup$ You are looking for all possible swaps in each single iteration of the algorithm. To evaluate a swap you need to check the assignments and verify that the total dissimilarity is reduced. You take into account also the swaps that destroy the current clustering in the hope of a better solution. If you do not find a better solution, then the algorithm returns the current solution. $\endgroup$
    – Net_Raider
    Apr 23, 2015 at 9:33

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.