6
$\begingroup$

I understood that PAM is just one kind of K-medoids algorithm. The difference is in new medoid selection (per iteration):

  • K-medoids selects object that is closest to the medoid as a next medoid

  • PAM tries out all of the objects in the cluster as a new medoid that will lead to lower SSE.

If I understood well, PAM gives better results, but takes up much more time. Is that so?

Which one is better and why?


Here is what confused me, this is a list of software that implements K-medoids, from Wikipedia

  • ELKI includes several k-means variants, including k-medoids and PAM.
  • Julia contains a k-medoid implementation in the Clustering package[5]
  • R includes in the "flexclust" package variants of k-means and in the "cluster" package.
  • Gap An embrional open source library on distance based clustering.
  • Java-ML. Includes a k-medoid implementation.

For example, it says that ELKI contains both variants, k-medoids and PAM?

And for example first look on K-medoids implementation in javaml looks like it finds the object closest to medoid and tries it out.

$\endgroup$
9
$\begingroup$

k-medoids is the problem specification. It may be a np-hard problem.

PAM is one algorithm to find a local minimum for the k-medoids problem. Maybe not the optimum, but faster than exhaustive search.

PAM is to k-medoids as Lloyd's algorithm is to k-means. Lloyd's algorithm is a fast heuristic to find a good solution to k-means, but it may fail to find the best.

$\endgroup$
6
  • $\begingroup$ Thank you for your answer. But besides of PAM there also exists an original K-medoids algorithm (similar thing with Lloyd's K-means, which everyone calls just K-means), that selects object closest to medoid as next medoid? But PAM is a better solution since it takes less iterations to get to local minimum? Is my understanding correct? $\endgroup$ – Kobe-Wan Kenobi Mar 11 '15 at 8:34
  • $\begingroup$ Do you have a reference for this "original K-medoids"? The original one that I know is PAM... $\endgroup$ – Has QUIT--Anony-Mousse Mar 11 '15 at 12:13
  • $\begingroup$ I am pretty sure that I saw that version of algorithm somewhere, but I cannot find it at the moment. If I do, I'll share it. Thanks anyway for clarification. :) $\endgroup$ – Kobe-Wan Kenobi Mar 11 '15 at 14:01
  • $\begingroup$ I have edited my question, please take a look. $\endgroup$ – Kobe-Wan Kenobi Mar 11 '15 at 14:29
  • $\begingroup$ Probably an imprecise statement. Can you find a paper introducing this other k-medians? The javaml approach will not work with arbitrary data types or distances. It's more of a k-means with centroids moved to the nearest real data point, but as it uses the centroid, it assumes squared Euclidean distance and a numerical vector space, might just use k-means then... $\endgroup$ – Has QUIT--Anony-Mousse Mar 11 '15 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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