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