5
$\begingroup$

I have a question regarding Partitioning Around Medoids (PAM) clustering algorithm, because everywhere I look, it is described differently. In every step of the algorithms do I swap only one medoid or more?

I mean, does the swapping step look like:

For each cluster medoid m in 1..K
    Find the non-medoid point p in this cluster which, after swapping with medoid m, maximizes total similarity in this cluster (minimizes total distance)
    Do the swap

Or is it like - find the swap between one of the medoids and non-medoid point (not-necessary inside that cluster) that maximizes total similarity in all dataset (minimizes total distance) and do the swap?

I will be very grateful for a reply

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

It depends on how literal you want your implementation to be.

Note that in the original PAM algorithm, the initialization BUILD is the most important part. The optimization phase, SWAP is expected to not require many iterations then.

From the original book, emphasis and comments added:

Note that as all potential swaps are considered [in each iteration], the results of the algorithm do not depend on the order of the objects in the input file [except for ties]

It was a conscious decision by the authors of the algorithm to search for the optimum swap, in order to become (mostly) order independent. A "greedy" variation (no longer PAM though) would do the first swap that yields an improvement; this will likely be faster but no longer order independent.

As far as I can tell, ELKI includes such a variant by the name KMedoidsEM:

Provides the k-medoids clustering algorithm, using a "bulk" variation of the "Partitioning Around Medoids" approach. In contrast to PAM, which will in each iteration update one medoid with one (arbitrary) non-medoid, this implementation follows the EM pattern. In the expectation step, the best medoid from the cluster members is chosen; in the M-step, the objects are reassigned to their nearest medoid. We do not have a reference for this algorithm. It borrows ideas from EM and PAM. If needed, you are welcome cite it using the latest ELKI publication (this variation is likely not worth publishing on its own).

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for the answer. So, just to make sure, in the original PAM, in each iteration I choose one swap that maximizes the total medoid similarity for whole dataset (sum of similarities between all points and their clossest medoids). Is that correct? $\endgroup$
    – user1315305
    Aug 12, 2013 at 9:10
  • $\begingroup$ Yes, from my understanding you search for the maximum improvement in each iteration and do this one single swap, then repeat (as long as there is any improvement possible). $\endgroup$
    – Has QUIT--Anony-Mousse
    Aug 12, 2013 at 10:43
  • $\begingroup$ @Anony-Mousse I have to partly reformulate the question,since I'm confused by discussion. Would this be a bad approach - in each iteration, after assigning points to clusters, for each cluster swap its medoid with each of the points in that cluster, to find best new medoid in each cluster? $\endgroup$
    – Kobe-Wan Kenobi
    Mar 16, 2015 at 14:23
  • $\begingroup$ Isn't that close to what PAM is doing? But beware that it is fairly expensive to find the best medoid. $\endgroup$
    – Has QUIT--Anony-Mousse
    Mar 18, 2015 at 4:03

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.