Centroid Alternatives and Large-Scale Partitioning

The alternatives preserve different parts of the original objective, and each one has a measured price.

K-Medoids is the expensive branch, and the cost has a location: PAM's SWAP phase. Schubert and Rousseeuw rebuilt that phase in 2021 and cut its runtime by a factor of O(k). Their method returns the same result as original PAM. What changes is the arithmetic: “In experiments on real data with k=100,200, we observed a 458x respectively 1191x speedup compared to the original PAM SWAP algorithm, making PAM applicable to larger data sets, and in particular to higher k.” The R `cluster` package ships those exact optimisations and documents them: “pamonce = 3: reduces the runtime by a factor of O(k) by exploiting that points cannot be closest to all current medoids at the same time”, and “'FasterPAM' (Schubert and Rousseeuw, 2021) is implemented via pamonce = 6”. "Can be more expensive than K-Means" is therefore a statement with a version number attached to it.

MiniBatch K-Means has a date, a benchmark and a batch size. Google published it in 2010, in a conference poster by D. Sculley. He tested it on the RCV1 document collection: 781,265 training examples, 23,149 held out for testing, mini-batch size b = 1000. The abstract claims both halves of the trade in one sentence: “This reduces computation cost by orders of magnitude compared to the classic batch algorithm while yielding significantly better solutions than online stochastic gradient descent.” For small values of k the mini-batch methods produced near-best cluster centers for nearly a million documents in a fraction of a CPU second, on a single ordinary 2.4 GHz machine. scikit-learn 1.9.0 implements the method and states the other side of the bargain without softening it: “MiniBatchKMeans converges faster than KMeans, but the quality of the results is reduced”.

Bisecting K-Means changes how much data each step touches. The same scikit-learn guide notes that “BisectingKMeans is more efficient than KMeans when the number of clusters is large since it only works on a subset of the data at each bisection”. It adds that “Picking by largest amount of data points will also likely produce clusters of similar sizes while KMeans is known to produce clusters of different sizes.” The hierarchy is not free decoration. It is the reason the per-step cost falls.

A media platform clusters fifty million item embeddings. Full K-Means exceeds the batch window, while a small sample fit misses fresh content categories. Scaling is not only a runtime problem. The approximation changes optimization, update noise, and the evidence available for comparing versions.

That platform is imagined. The collection on which mini-batch k-means was actually validated is not, and anyone can download it. RCV1-v2 holds 804,414 documents over 47,236 term features. Lewis and colleagues documented it in the Journal of Machine Learning Research in 2004, and its chronological division is the one later work reuses: “The result is a split of the 804,414 RCV1-v2 documents into 23,149 training documents and 781,265 test documents. We call this the LYRL2004 split.” Sculley swapped the two halves so that the training set would be the large one. That is why his mini-batch experiments train on 781,265 documents rather than 23,149. scikit-learn 1.9.0 distributes the same corpus and lists it identically: “Samples total 804414” and “Dimensionality 47236”.

Initialization is a bottleneck of its own. A naive k-means++ initialization “will make k passes over the data” before a single point is assigned. In 2012 Bahmani and colleagues put a parallel version in its place, k-means||, which “obtains a nearly optimal solution after a logarithmic number of passes”. In their words, “in practice a constant number of passes suffices”.

The best choice follows the failure that matters most. For one of these three the choice was settled by measurement rather than preference, and the result is still running in production systems. Apache Spark 3.5.7 documents its MLlib implementation as “A bisecting k-means algorithm based on the paper 'A comparison of document clustering techniques' by Steinbach, Karypis, and Kumar, with modification to fit Spark”, adding that “The bisecting steps of clusters on the same level are grouped together to increase parallelism”.

Each variant changes a different part of the standard K-Means workflow. K-Medoids changes the representative and permits broader distance choices. MiniBatch K-Means changes the update, drawing centroids from small random batches to cut memory and compute. Bisecting K-Means changes the order of construction, splitting an existing cluster repeatedly to build a divisive hierarchy. A reference fit — a smaller trusted full fit, or a sampled audit — is what converts those changes from claims into measured approximation error.

The first of the three is not a matter of taste. Two independent vendors define it in their own manuals. MathWorks documents `kmedoids` and states the distinction directly: “In the k-means algorithm, the center of the subset is the mean of measurements in the subset, often called a centroid. In the k-medoids algorithm, the center of the subset is a member of the subset, called a medoid”. The function “returns medoids which are the actual data points in the data set”. The method is “commonly used in domains that require robustness to outlier data, arbitrary distance metrics, or ones for which the mean or median does not have a clear definition”. R's `cluster` package — the CRAN-distributed successor to Kaufman and Rousseeuw's 1990 Finding Groups in Data — says the same thing from the objective's side: “Compared to the k-means approach in kmeans, the function pam has the following features: (a) it also accepts a dissimilarity matrix; (b) it is more robust because it minimizes a sum of dissimilarities instead of a sum of squared euclidean distances”. Robustness here is a property of the loss, not a hope about the data.

The comparison should use both computational and structural criteria. Record the memory, training window, update frequency and serving latency you must live inside. Fit a trusted method on a representative subset or a shorter period. Measure centroid drift, exemplar quality, partition agreement and downstream outcomes against it. Repeat the incremental fits across shuffled and source-stratified streams. Decide in advance when to refit, warm-start, freeze or retire the cluster version.

Those middle steps have a published worked example. In 2021 Hicks and colleagues clustered 1,232,055 single cells over 11,720 genes with mini-batch k-means, and reported it in PLOS Computational Biology. The resource limits, step 1, came out as a ratio rather than an adjective: “we can cluster 1 million cells with only 1.55GB of RAM, as compared to 39.4 GB for the in-memory version”. That run took 7.8 to 9.8 minutes. In-memory k-means took 36.6 minutes on only 300,000 cells. Steps 2 and 3, the reference and the comparison, name their metrics: at k = 15 and a batch size of b = 500 or larger they found “no loss in accuracy with respect to k-means, based on ARI and WCSS”. ARI and the within-cluster sum of squares are what "compare assignments" means in practice. The batch size is the knob the verdict hangs on — the equivalence was reported at b = 500 or larger, not at any b. Bioconductor ships the software as mbkmeans 1.28.0, which “Implements the mini-batch k-means algorithm for large datasets, including support for on-disk data representation”. So the reference fit and the approximation can be run against each other by anyone.

Large-scale clustering often requires stochastic updates, summaries, or hierarchical shortcuts. Those choices can be entirely appropriate when their errors are measured.

Report quality relative to a reference, not merely wall-clock time. A faster partition that changes decisions unpredictably is not an engineering improvement.

The k-means|| evaluation shows what such a record looks like, and the scale is worth stating: the parallel algorithms “were run using a Hadoop cluster of 1968 nodes”. On quality, “after as little as five rounds, the solution of k-means|| is consistently as good or better than that found by any other method”, and against one baseline the method “typically selects only 10–40% as many centers as Partition”. Those numbers were published in 2012, in a paper anyone can fetch. A claim you can go and check is worth more than one you are asked to accept.