Solved – Partitioning Around Medoids

clusteringk medoidsk-meanspartitioning

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

Best Answer

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).

Related Question