why does k-medoids ignore between-cluster distances

Question

The k-medoids algorithm is a popular distance-based clustering algorithm. It uses a heuristic algorithm to assign samples to clusters based on centroids, which are itself samples. It's cost function is simply the sum of within-cluster sample-to-centroid distances.

I have observed unintuitive behaviour of the k-medoids algorithm and have followed it up with a simple experiment: I sampled varying numbers of observations from two-dimensional gaussian distributions with varying between-cluster distances. I used the k-medoids algorithm to assign cluster labels and then used the adjusted RAND-index to compare the ground truth to the assigned labeling. Under circumstances of extreme group size differences, the k-medoids algorithm (arguably) fails to find the obvious clustering:

This is not a convergence issue: The cost of the visualized clustering is 0.9217164, while the cost of the ground truth clustering is 1.434386. Instead, what happens is that it is cheaper for the algorithm to split the prevalent cluster into 2, thus artificially creating two dense, highly prevalent clusters. The cost of putting a very small number of samples far away is mitigated.

Is the k-medoids cost function really as bad as I think it is, i.e. couldn't it be (strictly) improved by taking into account between-cluster distances as well?

Answer 1

The sum of all pairwise distances obviously is a constant.

This sum can be decomposed into a) the sum of distances within each cluster and b) the sum of distances between points in different clusters, such that total=a+b.

Because of that, minimizing the within cluster distances is obviously equivalent to maximizing the sum of distances between clusters.

So it does actually optimize that, too!

The real question is, whether the sum-of-distances is worth minimizing. Or whether you'd rather want to maximize the fit of a Gaussian model as in GMM or fit a density model as in DBSCAN instead.

In your toy example, note that the left cluster has many pairs of points whose distances are almost the entire cluster. Compare this to the few points your smaller cluster has in total - of course it is more important to split the huge cluster than to get the small cluster perfectly right.

Answer 2

If instead of using the raw distance of points to their medioids as the cost function, use the squared distance. Then minimizing the sum of squared distances within clusters is equivalent to maximizing the squared distance between centroids:

K-means: Why minimizing WCSS is maximizing Distance between clusters?