# When does pam (partition around medoids) fails to find the optimal solution? (counter example?!)

If I understand correctly, the pam algorithm is a greedy search for a set of medoids such that no other set offers a lower cost (i.e.: the sum of distances of points to their nearest medoid).

However, when does the pam algorithm fail? Are there general cases for which it is known to reach the global optimum? (say, for some ratio of k and n?)

Are there nice counter examples demonstrating when some set of medoid is stable (i.e.: would lead pam to converge), but sub optimal?

• How do you distinguish a local instead of a local optimum in this case? For a fixed $k$ some runs will be bad and outliers will always be an issue and the failure would be related to bad initial values and/or strongly non-spherical data structures. Feb 13, 2016 at 6:55
• For example: the clustering shown in MATLAB's k-medoids implementation while "visually" optimal, is not a perfect characterization. If you check the idx vectors it is not a bunch of 2 followed by a bunch of 1's. Some mischaracterization took place but for all intended purposes that clustering is great. Feb 13, 2016 at 6:59
• pam optimizes the sum of distances of all observations to their medoid (let's call this number A). If you can find me a dataset with initial values that would lead to some medoids who's value is A, and another set of medoids for which the value would be A' (smaller than A), then you found me a sub optimal solution of pam... Feb 13, 2016 at 11:43
• Have you attempted to construct a counterexample yet? Feb 27, 2016 at 22:22

Try to build one!

We need a cluster assignment that is stable, but not optimal. So the medoids bust be the medoids of their clusters, and every object is assigned to its closest medoid. But there is a solution that is a lot better.

Lets start simple. One dimensional, three points per cluster, stars indicate the cluster centers.

Data: 1 2 3     6 7 8
Sol1:   *         *


Now let's modify this by moving one object away from the center.

Data:1 2 3     6 7                 15
Sol1:  *         *
Sol2:    *                         *


The cost of Sol2 is 2+1+0+3+4+0=10. But it's hard to get there. Most likely PAM will get stuck in the first solution, which costs 1+0+1+1+0+8=11. If it doesn't, you may need to increase the spacing of the clusters, or move the outlier.

Example of R code for the above example:

> pam(c(1:3,6,7,15), k = 2, medoids = c(2,5))$med [,1] [1,] 2 [2,] 7 > pam(c(1:3,6,7,15), k = 2, medoids = c(2,6))$med
[,1]
[1,]    3
[2,]   15


Clustering is an NP-complete problem - see proof fo the one definition of clustering and another definition of clustering.

The question of whether P=NP wasn't answered yet but is seems as if the complexity classes are different.

If it is so, then no polynomial time algorithm, like the pam algorithm can solve the problem.

When facing an NP-complete problem we can cope with it by looking for approximation algorithms. The one bellow has approximation ratio of 2.

Gonzalez, T. F. (1985), Clustering to minimize the maximum intercluster distance'', Theoretical Comput. Sci. 38, 293-306.

However, pam goes in a different direction and it is a randomized greedy algorithm. Hence, it looks for an optimal solution but I guess that usually it fails and finds a local optimum.

It seems that pam fails on the regular cases that are hard to k-means. On slide 24 there is a example that is hard for k-means like algorithms but DBSCAN clusters well.

• Thanks Dan, but I am looking to see data (and maybe some starting point) for which pam finds a local optimum. The example of kmeans/pam failing has to do with the detection of the cluster structure - not of finding the global optimum (given the type of cluster structure it could be that pam found the best medoid possible) Feb 11, 2016 at 14:11
• Yes, you are right. I also felt that the argument based on complexity classes is not constructive. I also looked for a case for which pam get stuck in a local optimum though it could have reach a global one but didn't find one. Of course, since the algorithm is random, there will be runs that will be unsuccessful. However, I was also looking for a stronger example.
– DaL
Feb 11, 2016 at 14:38
• Thanks Dan. Indeed, what I wish to see is one counter example. Feb 11, 2016 at 19:50