9

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.

Kobe-Wan Kenobi
  • 2,437
  • 3
  • 20
  • 33

1 Answers1

11

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.

Has QUIT--Anony-Mousse
  • 39,639
  • 7
  • 61
  • 96
  • 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? – Kobe-Wan Kenobi Mar 11 '15 at 08:34
  • Do you have a reference for this "original K-medoids"? The original one that I know is PAM... – Has QUIT--Anony-Mousse Mar 11 '15 at 12:13
  • 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. :) – Kobe-Wan Kenobi Mar 11 '15 at 14:01
  • I have edited my question, please take a look. – Kobe-Wan Kenobi Mar 11 '15 at 14:29
  • 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... – Has QUIT--Anony-Mousse Mar 11 '15 at 20:03
  • I cannot, I'm not sure if I found one, I went through a lot of literature these days, so maybe I just got an impression of it from Wikipedia page. Thanks anyway, I've understood the important thing, K-medoids is a problem, PAM is one of the approaches (algorithms) that can be used to solve it. And when people say K-medoids, they mostly think PAM. :) – Kobe-Wan Kenobi Mar 12 '15 at 08:20