Abstract
This paper establishes the first formal proof that $K$-medoids clustering is "consistent"—meaning it converges to the optimal population clustering as sample sizes grow—across both standard metric spaces and "ordinal" settings where only the relative order of distances is known. By proving that $K$-medoids is asymptotically equivalent to $K$-means restricted to the data's support, the authors bridge a decades-old gap in clustering theory.
Introduction
While $K$-means is the standard for clustering, it has a significant limitation: it requires calculating centroids (means), which might not be well-defined in non-Euclidean spaces or may be overly sensitive to outliers. $K$-medoids offers a more robust alternative by restricting cluster centers to be actual data points from the sample. Despite its popularity since the 1980s, the theoretical consistency of $K$-medoids—the guarantee that it will find the "true" clusters given enough data—had not been established for general metric spaces or ordinal data scenarios.
Methodology
The authors employ a "bridge" strategy to prove their theorems. First, they establish Asymptotic Equivalence, proving that as the number of samples $n$ goes to infinity, the $K$-medoids problem becomes equivalent to a $K$-means problem where the centers are restricted to the support of the underlying probability distribution. This allows them to leverage powerful existing consistency results for $K$-means.
Furthermore, they extend this framework to Ordinal Data, specifically:
- Triple Comparisons: Knowing if $x_i$ is closer to $x_j$ or $x_l$.
- Quadruple Comparisons: Knowing if $d(x_i, x_j) < d(x_l, x_m)$.
They show that by treating these ranks as a new kind of distance function, the same consistency logic applies, demonstrating that numerical distances are not strictly necessary for reliable clustering.
Empirical Results
The paper validates these theoretical findings using synthetic simulations. Performance was evaluated across various norms ($L_1, L_2, L_\infty$) using Average Center Error and the Adjusted Rand Index (ARI).
Metric Parity
As shown in the following table, $K$-medoids performs nearly identically to $K$-means in terms of both error and ARI across different distance metrics. This confirms that the restriction to sample points does not hinder the algorithm's ability to find optimal clusters in the limit.
Ordinal Efficiency
One of the most striking results is the efficiency of ordinal-based clustering. As illustrated below, $K$-medoids using only triple comparisons (TC) or quadruple comparisons (QC) achieved performance parity with $K$-medoids using exact distances (KM). For example, in the $L_2^2$ setting, the ARI for Triple Comparisons (0.931) was nearly identical to using actual distances (0.930).
Discussion and Limitations
The fundamental insight is that as data density increases, the discrete set of available medoids eventually fills the entire support of the distribution, making the distinction between $K$-means and $K$-medoids vanish. This work highlights a path toward clustering that is naturally resistant to outliers and "meaningless" numerical distance values.
However, some limitations remain. The strongest consistency results assume the population problem has a unique global minimum. Additionally, while the paper proves theoretical consistency, finding the global minimum for $K$-medoids remains an NP-hard computational challenge for large-scale practical applications.
Summary updated