2
$\begingroup$

Does it make sense to use initialization in K-medoids like in the case of K-means++?

To be precise - is it good to select "farthest" points as initial medoids? (farthest in sense that points that are further from each other have greater probability to be selected as initial medoids).

I think that it makes sense, but I would like a confirmation.

$\endgroup$
5
  • $\begingroup$ Yes, that is what I mean - en.wikipedia.org/wiki/K-means%2B%2B. Which approach would you recommend then (since you said that this is not universally the best approach)? $\endgroup$ Commented Mar 16, 2015 at 14:00
  • 1
    $\begingroup$ ELKI allows you to test this variant, IIRC. But k-medoids initialization is already half of the algorithm. I think Kaufman&Rousseeuw designed their BUILD very carefully, because you cannot afford man iterations of the SWAP steps, they are very expensive. Please study the PAM algorithm carefully, it is much less similar to Lloyd kmeans than one assumes at first. $\endgroup$ Commented Mar 19, 2015 at 12:50
  • $\begingroup$ So essentially, it then isn't k-medoids anymore. $\endgroup$ Commented Mar 19, 2015 at 12:50
  • $\begingroup$ Thanks for your answer, but can you give me a reference to the original paperwork for PAM? I've been trying to find it for a while, but I did not succeed, for some reason... And can you please check my other question stats.stackexchange.com/questions/142121/…? Feel free to post you comment as an answer, so I could accept it. $\endgroup$ Commented Mar 19, 2015 at 13:38
  • $\begingroup$ If anyone is still looking for the original paperwork for PAM look for: Leonard Kaufmann and Peter Rousseeuw - Clustering by Means of Medoids researchgate.net/publication/… $\endgroup$ Commented Oct 18, 2018 at 14:39

1 Answer 1

1
$\begingroup$

If you are talking about the PAM algorithm remember that it has a BUILD phase already implemented, and as said by Anony-Mousse in comments it is the major part of the algorithm. The SWAP phase is a refinement of the initial solution that scales badly with the number of objects.

You nevertheless can try to implement a randomized version of the BUILD step in which instead of selecting the objects that minimize the total dissimilarity of each object from its nearest representer you randomly sample them according to a probability distribution proportional to that total dissimilarity.

Anyway it is hard to tell a priori if this can be a better initialization step. You should test both initializations, or try to develop a proof (if you dare!) that the random initializations lead on average to better solutions, or construct lower bounds as in k-means++

$\endgroup$

Your Answer

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

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