7
$\begingroup$

I've been doing a lot of clustering work lately and have been using the PAM algorithm.

Based on my research it appears to be deterministic because the initialization of medoids are selected from items in the dataset (selected randomly). Further, subsequent medoids in the SWAP stage are also items from the dataset. Therefore, for any given dataset there is only one correct answer that minimizes the sum of the absolute distances to their cluster medoid.

Thus, PAM is an exhaustive search of every element for the optimal k medoids.

In comparison the k-means algorithm picks an arbitrary synthetic starting point for the cluster centers. The centers move until until the error is optimally reduced.

Am I correct in this assumption?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
6
$\begingroup$

PAM is close to being deterministic, but there may be ties.

In particular, PAM does not use a random generator.

The heart of PAM is the BUILD phase that tries to smartly choose the initial settings (there exist variations that use a random sample, but IIRC that is not the original PAM algorithm). If I remember correctly, the authors even claimed that you don't really need the iterative refinement (SWAP phase), and it will finish in very few iterations because of the good starting conditions.

Nevertheless, if you have, e.g., a symmetric data set, you are likely to have more than one choice as "best medoid" at some point. Because of these "ties", it cannot be fully deterministic (most implementations will be deterministic because they do not randomly break these ties; but if you permute the data and have such ties, you may occasionally see different results).

PAM also is not exhaustive search. It is a steepest descent approach, but it will consider nearby solutions only. The hypergraph interpretation in the CLARANS article outlines this. But it easy to see that there are (n choose k) possible medoids, but PAM at any time only considers (n-k)*k alternatives in each SWAP step.

Improve this answer
$\endgroup$
1
$\begingroup$

Short answer no. It is sensitive to the starting medoids. There could be multiple correct combinations of medoids that minimize the objective function.

Some software packages implement a smart building stage where the starting medoids are selected in a deterministic way. If the starting medoids are a deterministic the PAM results will be also.

This paper helped me tie it all together Amorim et al. The paper presents a weighted version of PAM.

Improve this answer
$\endgroup$
7
  • $\begingroup$ That source does not correctly present PAM. $\endgroup$
    – Has QUIT--Anony-Mousse
    Commented Jan 7, 2017 at 12:01
  • $\begingroup$ @Anony-Mousse Let's discuss this further. I'll make a chat room. chat.stackexchange.com/rooms/51407/… $\endgroup$
    – Matt L.
    Commented Jan 8, 2017 at 17:05
  • $\begingroup$ Can you share the paper again? The link seems to have expired. It might be interesting to send the name of the paper too. Thanks $\endgroup$
    – André Costa
    Commented Oct 18, 2018 at 15:04
  • $\begingroup$ It's easy to figure out what paper that was - but it's still pretty bad... To quote "the partition around medoids algorithm attempts to minimise the K-Means criterion:" no, and no. PAM does not minimize the k-means criterion, and no. The equation presented is neither the objective of k-means nor of PAM. I suggest to read the book by Kaufman and Rousseeuw where they introduced PAM. $\endgroup$
    – Has QUIT--Anony-Mousse
    Commented Oct 19, 2018 at 8:25
  • $\begingroup$ @Anony-Mousse Can you provide a little more detail here. I still don't see what you are seeing. The objective looks the same to me in both Kafman's work and the paper I referenced. There might be variations in the distance metric used, but the goal is still to minimize the sum of squares of a distance metric to either centers or medoids. $\endgroup$
    – Matt L.
    Commented Oct 20, 2018 at 13:54

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.