k-means clustering

Overview

k-means splits n points into k clusters. Each cluster is summarised by a centroid. The standard procedure is Lloyd's loop: assign every point to its nearest centroid, then replace each centroid with the mean of its points 1907.05012 alg. 4. The deletion paper seeds the loop with k-means++ and runs it for a fixed number of iterations, T = 10 1907.05012 §5. The output is k centroids and a partition of the points. Most variants change how the centroids are computed, where the computation runs, or what the cluster labels are used for. One uses the k-means centres only as a starting point for a Gaussian mixture.

Variants

Plain Lloyd with k-means++ seeding

The baseline of the deletion work: seed with k-means++, then run Lloyd iterations 1907.05012 alg. 7 §5. Off-the-shelf software differs. The benchmark Clustering Algorithms: A Comparative Approach runs R's kmeans with its defaults, which is Hartigan-Wong, not Lloyd, with one start and K set to the true number of classes 1612.08388 supp. S1 §5.1. Its mean ARI column reads 52.19%, below spectral clustering (65.80%) and the subspace method (58.58%) 1612.08388 tab. 2. The paper does not define that column precisely §5.1, and the defaults use the true K, which a user would not know in practice. Random search over the parameters raised the best ARI on two-class, two-feature data from 48.1 to between 51.9 and 55.0, depending on the selection column 1612.08388 tab. 9. The parameter bounds for that search are not stated §5.3.

Deletion-efficient Q-k-means

Making AI Forget You snaps each centroid to a lattice of spacing ε, with a random phase drawn in each iteration 1907.05012 §4.1 app. B.1.2. Each step is stored. To delete a point, the stored centroids are perturbed by removing the point from its cluster, and the method retrains only if a snapped centroid moves to a different lattice point [arxiv:1907.05012 alg. 5]. Across six datasets, the amortized speedup over k-means++ retraining ranges from 2.2x (MNIST) to 584x (Botnet), and the loss ratio from 1.01 to 1.16 1907.05012 tab. 4 tab. 1. Runs were single-core Numpy code, so the absolute times are hardware-specific app. D.1.

Costs: O(ktd) extra memory 1907.05012 §4.1. Deleting an initial seed always forces a retrain, per the algorithm alg. 5. On MNIST the retrain count grows at a roughly constant rate app. D.3.1. Runtime rises as ε shrinks, and loss worsens as ε approaches 1 1907.05012 fig. 5 fig. 3. The paper says deletion time "may not scale well" in high dimension §4.1.

The authors' code does not follow the algorithm in every respect. Reading it (not running it), the first k-means++ seed is never recorded, so deleting that seed does not trigger a retrain 1907.05012 alg. 5. Read the code notes on the paper card before reusing the code.

Deletion-efficient DC-k-means

The same paper's divide-and-conquer variant. Points go to w random leaves; each leaf runs k-means; the pooled leaf centroids are clustered once more at the root 1907.05012 §4.2 alg. 2. Deleting a point re-clusters its leaf and the root alg. 6. The paper's rule of thumb for the leaf count is w ≈ n^0.3, rounded to a power of two app. D.1.2. Speedups range from 15.6x (Celltype) to 70.9x (Botnet), with a 25.4x gain on MNIST where Q-k-means gains only 2.2x 1907.05012 tab. 4. Loss ratios range from 1.00 to 1.44, with the largest on Celltype 1907.05012 tab. 1.

Dense features in zero-shot vision

Deep ViT Features as Dense Visual Descriptors uses k-means as the only clustering step. It pools the normalised patch keys of all images, clusters them, and picks k by the elbow method 2112.05814 §4. Part co-segmentation runs k-means again on the foreground patches with the requested number of parts 2112.05814 §4. The paper's comparisons are with other co-segmentation, part co-segmentation and correspondence methods, not with other clustering algorithms 2112.05814 tab. 1 tab. 2 tab. 4. So the results show the pipeline works, not that k-means is the best clustering choice for it.

One-shot federated k-means (k-FED)

Heterogeneity for the Win: One-Shot Federated Clustering clusters data held on many devices in one upload round. Each device runs a Lloyd-style local clustering once, with its own cluster count k^(z), and sends only its few local centers 2103.00697 alg. 1 alg. 2. The server seeds k groups with a farthest-point rule, then assigns every device center to its nearest seed in one pass 2103.00697 alg. 2. Each point takes the group of its device's center 2103.00697 §3.2.

The guarantee needs well-separated cluster means and at most √k clusters per device, which the paper calls a heterogeneous network 2103.00697 §3.2. Under that condition, pairs of clusters that never share a device need separation that grows with k^(1/4), against √k for centralized clustering 2103.00697 §3.2. In the synthetic runs, accuracy is 98.4% to 100% 2103.00697 tab. 1. But that data is built to meet the conditions, so it is a best case §4.1. On real data, the paper reports qualitatively that one round gives a cost similar to naive distributed k-means, which needs several rounds 2103.00697 §4.2 fig. 3. In rotated-MNIST personalization with two clusters per device, it reaches 97.1% against 95.6% for IFCA with 100 devices 2103.00697 tab. 2. These are author-reported numbers.

Codebooks and coarse centroids in vector search

The Faiss library uses k-means in two places. A product quantizer splits each vector into M sub-vectors and gives each one its own k-means codebook of K entries 2401.08281 §4.1. An inverted file partitions the database around nlist coarse centroids, and a query scores only its nprobe nearest lists 2401.08281 §5.1. The paper names the plain k-means codebook as the MSE-optimal choice, and says it is impractical beyond codes of about 3 bytes, or 16M centroids 2401.08281 §4.1.

For inner-product search the paper offers spherical k-means, which renormalises the centroids in every iteration. With inner-product assignment it reports less list imbalance than L2 k-means on its Contriever1M test, but the imbalance factors appear only in a figure 2401.08281 §5.1 fig. 6. Spherical k-means is opt-in in the library (Faiss card, Paper vs code). The paper gives no default nprobe. Its rule of thumb puts the best nlist at roughly 15 to 20 times √N, depending on data and target recall 2401.08281 §5.1 fig. 4. At trillion scale, the coarse centroids (10M of them) are searched with an HNSW graph rather than exhaustively 2401.08281 §7.1. The paper does not state how many training vectors each codebook needs; the Faiss card records a subsampling rule from the code.

Class features for a demand forecaster

A Novel Deep Neural Network Architecture for Real-Time Water Demand Forecasting clusters one signal, the demand history, on its own. The one-dimensional values are grouped into m = 4 classes, with m read from an elbow plot of the within-cluster error 2512.06714 §3.3 fig. 3 §4.1. Each reading then carries its class information as extra inputs beside its value, so a 96-reading window becomes 96 rows of m + 1 values §3.3. Initial centres are drawn at random around the data mean, scaled by the standard deviation §3.3 eq. 3. The text ties the class feature to a membership indicator eq. 2 but also calls it a value of the class, and the paper does not settle which one the network receives §3.3. Virtual values added in the expanded model are classified with the same k-means step, and the paper does not say whether the centres are refitted §3.5.

Reported gains are one-step MAPE of 1.26% and 1.31% for the model with class features, against 2.49% and 3.58% for BGRU, a GRU without them tab. 6 §3.7.1. The parameter gap between the two, 4,187 against 3,366, equals the dense block's weight count tab. 5 tab. 6 (derived). So the comparison also changes the dense block, and it does not isolate the class features. All results come from two district metering areas in one city, with training and testing on the same area §2.

Starting point for a mixture model (hypertime)

Warped Hypertime Representations for Long-term Autonomy of Mobile Robots uses k-means only to start its model. HyT-KM begins from k-means centres. It measures distance with cosine on the time coordinates and Euclidean on the rest, then runs EM with the cosine distance on the time coordinates [arxiv:1810.04285 §3.8]. The cluster count is not fixed: the model starts at one cluster and adds one when a rule on a spectral sum over the error is met 1810.04285 §3.8 eq. 8. The card reads that rule as accepting n+1 clusters when the sum for n is larger, which the paper does not justify, so implement it as written and test it. The paper's results are in figures only 1810.04285 fig. 2–fig. 5, so this variant has no number on this page to compare with the others.

Clustering tasks to pick a reduced training set

Optimizing Locomotor Task Sets in Biological Joint Moment Estimation for Hip Exoskeleton Applications clusters recorded activities, not data points. Each subject-task pair becomes one row of joint angle, velocity and moment profiles. PCA keeps three components 2412.07823 §II.B fig. 2a, and k-means groups the tasks in that space. K is the value with the highest silhouette score, which is K = 8 with score 0.38 2412.07823 §II.B fig. 2b §III.A. A task-weight score then picks one representative per cluster eq. 1 tab. 1. The k-means step only groups the tasks. The selection rule comes from the weighted score on top of it §II.B.

A small FCNN trained on the 8 representatives reaches RMSE 0.30 ± 0.05 Nm/kg. That is close to 0.28 ± 0.05 for all 20 tasks, and better than 0.38 ± 0.08 for the 8 cyclic tasks alone 2412.07823 §III.B fig. 4. The authors report no difference from all tasks in RMSE or R² §III.B. These are author-reported results on 11 healthy young adults, evaluated leave-one-subject-out §II.A §III.B. Table 1 names Tire Run as the top task of cluster 1, but the text names lunges for that group tab. 1 §III.A. The paper does not state the range of K it searched §II.B.

Proportional representation of centres (not a k-means variant)

Proportionally Representative Clustering changes the objective rather than the loop. It asks for proportionally representative fairness (PRF): any group of agents at least ℓn/k in size, whose members lie within a radius y of each other, must have at least ℓ centres within distance y of some member 2304.13917 §4. Its SEAR algorithm is a weighted greedy rule, not Lloyd's loop, and it always returns a PRF outcome in polynomial time 2304.13917 alg. 1 [thm. 1]. The paper is theory only; its experiments section is commented out in the source §5.

The paper uses k-means as a reference point. On a three-circle instance, k-means, k-median and k-center can each put two centres in the large circle and one between the two small ones, which violates PRF 2304.13917 §4 fig. 3. The paper gives no threshold for how large the big circle must be. So plain k-means is not PRF-safe when group sizes differ. The paper's approximation bounds for PF are 3 for unconstrained SEAR and 1+√2 for the discrete version 2304.13917 lem. 2 [prop. 2]. Use it when proportional coverage of groups is the requirement; see fair clustering.

When to use which

Implementation sketch

Language-agnostic core of the baseline. Q-k-means changes the centroid update (it quantizes the centroids). DC-k-means runs this loop per leaf and once more at the root. k-FED does not reuse this loop: each device runs a local procedure 2103.00697 alg. 1, and the server clusters the pooled device centers once alg. 2. A Faiss product quantizer runs the same loop once per sub-vector 2401.08281 §4.1. Empty clusters may be re-seeded or left empty 1907.05012 app. B.

# Lloyd iterations with k-means++ seeding  [arxiv:1907.05012 alg. 7] [§5]
# Input:  points (n, d), k clusters, T iterations (the paper uses T = 10)
# Output: centroids (k, d), labels (n)

def kmeans(points, k, T):
    # Seed the k centroids with k-means++  [arxiv:1907.05012 alg. 7]
    centroids = kmeanspp_seeds(points, k)           # (k, d)
    for step in range(T):
        # Assign each point to its nearest centroid  [arxiv:1907.05012 alg. 4]
        labels = assign(points, centroids)          # (n,)
        # Set each centroid to the mean of its points
        centroids = cluster_means(points, labels, k)  # (k, d)
    return centroids, assign(points, centroids)

Contradictions

None known between these nine papers on k-means itself: they measure different things. They differ on how k is set. The benchmark and the deletion paper use the true number of classes in their experiments 1612.08388 §5.1 1907.05012 app. D.2. The vision paper and the water-demand paper pick k with the elbow method 2112.05814 §4 2512.06714 §3.3. The exoskeleton paper picks K by the highest silhouette score [arxiv:2412.07823 §II.B] §III.A. The hypertime paper grows its cluster count with a spectral rule 1810.04285 §3.8 eq. 8. k-FED assumes k is known 2103.00697 §3.2. Faiss treats its centroid count as an index parameter, tuned for the speed and accuracy trade-off rather than for the number of true groups [arxiv:2401.08281 §5.1]. The benchmark's default algorithm is Hartigan-Wong, not Lloyd 1612.08388 supp. S1, so its ARI figures do not measure the Lloyd loop that the deletion paper uses.

Papers

• Clustering Algorithms: A Comparative Approach: benchmark of seven R clustering methods on 270 synthetic datasets; k-means is third-best at defaults.
• Making AI Forget You: Data Deletion in Machine Learning: Q-k-means and DC-k-means, which delete one training point without full retraining.
• Heterogeneity for the Win: One-Shot Federated Clustering: k-FED, one-round federated k-means for heterogeneous devices.
• Deep ViT Features as Dense Visual Descriptors: k-means on self-supervised ViT features for zero-shot co-segmentation and part co-segmentation.
• Warped Hypertime Representations for Long-term Autonomy of Mobile Robots: k-means centres start a Gaussian mixture over time-projected robot data; results in figures only.
• Proportionally Representative Clustering: SEAR, a fairness-driven centre rule that k-means can violate; theory only.
• The Faiss library: k-means codebooks and inverted-file centroids inside an approximate nearest-neighbour search library.
• A Novel Deep Neural Network Architecture for Real-Time Water Demand Forecasting: k-means classes of one demand signal used as extra inputs to a small GRU forecaster.
• Optimizing Locomotor Task Sets in Biological Joint Moment Estimation for Hip Exoskeleton Applications: k-means over PCA-reduced locomotor tasks, with one representative per cluster kept for training a hip-moment estimator.