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?