11
$\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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
12
$\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.

Improve this answer
$\endgroup$
5
  • $\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
    Commented Mar 11, 2015 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
    Commented Mar 11, 2015 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
    Commented Mar 11, 2015 at 14:01
  • $\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
    Commented Mar 11, 2015 at 20:03
  • $\begingroup$ 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. :) $\endgroup$
    – Kobe-Wan Kenobi
    Commented Mar 12, 2015 at 8:20
1
$\begingroup$

A way to look at it found in the literature is that K-medoids algorithms is a common name for all algorithms solving an optimization problem of partitioning a set with respect to so called medoids (cluster centers being members of the cluster). Same for K-means algorithms - we can say it's a family of algorithms solving an optimization problem of partitioning a set with respect to so called centroids (cluster means).

The most popular algorithms of K-medoids family (e.g. PAM) and K-means family apply a similar general approach: iteratively alternating between minimization with respect to cluster centers and minimization with respect to whole partition.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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