---
kind: concept
slug: k-means-clustering
title: k-means clustering
summary: >-
  Partition points into k groups by alternating nearest-centroid assignment and mean updates (Lloyd). Trails spectral clustering at default settings on synthetic benchmarks. Deletion variants drop one point at 2.2x to 584x lower amortized cost (loss ratio up to 1.44); a one-shot federated variant needs one upload per device. Author-reported.
tags: [clustering, unsupervised-learning, data-deletion, federated-learning, zero-shot-vision, vector-search, time-series, fairness, task-selection]
papers: ["1612.08388", "1810.04285", "1907.05012", "2103.00697", "2112.05814", "2304.13917", "2401.08281", "2412.07823", "2512.06714"]
related: [clustering-evaluation, spectral-clustering, hyperparameter-optimization, ensemble-clustering, part-based-features, vision-transformer, machine-unlearning, federated-learning, clustered-federated-learning, nearest-neighbor-search, vector-quantization, time-series-forecasting, fair-clustering, dimensionality-reduction, gaussian-mixture-model, expectation-maximization]
status: draft
updated_at: 2026-11-01
---

## 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
[arxiv:1907.05012 alg. 4]. The deletion paper seeds the loop with k-means++ and
runs it for a fixed number of iterations, T = 10 [arxiv: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 [arxiv:1907.05012 alg. 7] [§5]. Off-the-shelf software differs. The
benchmark [Clustering Algorithms: A Comparative Approach](/papers/1612.08388)
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 [arxiv:1612.08388 supp. S1]
[§5.1]. Its mean ARI column reads 52.19%, below spectral clustering (65.80%)
and the subspace method (58.58%) [arxiv: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 [arxiv:1612.08388 tab. 9]. The parameter
bounds for that search are not stated [§5.3].

### Deletion-efficient Q-k-means

[Making AI Forget You](/papers/1907.05012) snaps each centroid to a lattice of
spacing ε, with a random phase drawn in each iteration [arxiv: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
[arxiv: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 [arxiv: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 [arxiv: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 [arxiv:1907.05012 alg. 5]. Read the code notes on
the [paper card](/papers/1907.05012) 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
[arxiv: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
[arxiv:1907.05012 tab. 4]. Loss ratios range from 1.00 to 1.44, with the largest
on Celltype [arxiv:1907.05012 tab. 1].

### Dense features in zero-shot vision

[Deep ViT Features as Dense Visual Descriptors](/papers/2112.05814) 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 [arxiv:2112.05814 §4]. Part
co-segmentation runs k-means again on the foreground patches with the requested
number of parts [arxiv:2112.05814 §4]. The paper's comparisons are with other
co-segmentation, part co-segmentation and correspondence methods, not with other
clustering algorithms [arxiv: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](/papers/2103.00697)
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 [arxiv: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 [arxiv:2103.00697 alg. 2]. Each point takes the group
of its device's center [arxiv: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 [arxiv: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
[arxiv:2103.00697 §3.2]. In the synthetic runs, accuracy is 98.4% to 100%
[arxiv: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 [arxiv: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 [arxiv:2103.00697 tab. 2]. These are author-reported numbers.

### Codebooks and coarse centroids in vector search

[The Faiss library](/papers/2401.08281) 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 [arxiv:2401.08281 §4.1]. An inverted file
partitions the database around nlist coarse centroids, and a query scores only
its nprobe nearest lists [arxiv: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 [arxiv: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 [arxiv:2401.08281 §5.1] [fig. 6]. Spherical
k-means is opt-in in the library ([Faiss card](/papers/2401.08281), 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
[arxiv:2401.08281 §5.1] [fig. 4]. At trillion scale, the coarse centroids
(10M of them) are searched with an HNSW graph rather than exhaustively
[arxiv:2401.08281 §7.1]. The paper does not state how many training vectors each
codebook needs; the [Faiss card](/papers/2401.08281) 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](/papers/2512.06714)
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 [arxiv: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](/papers/1810.04285)
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 [arxiv: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 [arxiv: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](/papers/2412.07823)
clusters recorded activities, not data points. Each subject-task pair becomes
one row of joint angle, velocity and moment profiles. PCA keeps three
components [arxiv: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 [arxiv: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 [arxiv: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](/papers/2304.13917) 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 [arxiv: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
[arxiv: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 [arxiv: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
[arxiv:2304.13917 lem. 2] [prop. 2]. Use it when proportional coverage of
groups is the requirement; see [fair clustering](/concepts/fair-clustering).

## When to use which

| Situation | Use | Why |
|---|---|---|
| Quick baseline on one machine, no deletion requirement | Plain Lloyd with k-means++, or R's default `kmeans` | Cheapest to run. Off the shelf, the benchmark reports mean ARI 52.19%, below spectral's 65.80% [arxiv:1612.08388 tab. 2]. Tuning helps, but the search space has to be chosen by the user [arxiv:1612.08388 §5.3]. |
| Training points must be deletable, low to moderate d | Q-k-means | Largest measured speedups: 163x on Celltype (d = 10), 525x on Gaussian (d = 25), 584x on Botnet (d = 115) [arxiv:1907.05012 tab. 4]. Costs O(ktd) memory [§4.1]. |
| Training points must be deletable, high d (MNIST, d = 784) | DC-k-means | 25.4x on MNIST against 2.2x for Q-k-means [arxiv:1907.05012 tab. 4]. |
| Loss matters more than deletion speed | Plain retraining | Both variants have loss ratios above 1 on some datasets, up to 1.44 [arxiv:1907.05012 tab. 1]. |
| Deletions may be chosen by an adversary | Plain retraining, or a stronger method | Deleting initial seeds forces a Q-k-means retrain each time [arxiv:1907.05012 app. A.1]. Deletions from chosen leaves can break DC-k-means' correctness [app. A.1]. |
| k is unknown | Scan k and check the results | Underestimating the number of classes was worse than overestimating it, for all methods tested [arxiv:1612.08388 §5.2] [§6]. |
| Clustering dense features with no training | k-means on normalised descriptors, elbow for k | This is the pipeline of [arxiv:2112.05814 §4]. Its settings are not a general recommendation. |
| Data split across devices, each device sees few clusters, one upload round wanted | k-FED | The guarantee needs heterogeneity, √k or fewer clusters per device [arxiv:2103.00697 §3.2]. k and k^(z) must be known [§3.2]. |
| Data split across devices, IID-like | Centralized k-means, or a multi-round distributed method | k-FED's advantage rests on heterogeneity [arxiv:2103.00697 §3.2]. On structured partitions, cost sits closer to the oracle than on random IID ones [§4.2] [fig. 2]. |
| Compressed vector search over many embeddings | Product quantizer with k-means sub-codebooks, inside an inverted file | Stores codes of a few bytes and scans only the nearest lists [arxiv:2401.08281 §4.1] [§5.1]. The paper gives no default nprobe; tune it on your own data [§5.1]. |
| Codes of about 3 bytes or less, exact codebook wanted | Plain k-means quantizer | The MSE-optimal codebook, impractical beyond about 16M centroids [arxiv:2401.08281 §4.1]. |
| Inner-product search with an inverted file | Spherical k-means with inner-product assignment | Less list imbalance in the paper's test, factors shown only in a figure [arxiv:2401.08281 §5.1] [fig. 6]. Must be enabled explicitly in the library ([Faiss card](/papers/2401.08281)). |
| Sequence model needs a coarse regime feature from one signal, with no labels | k-means on the signal values, m chosen by elbow | The water-demand paper does this with m = 4 and feeds the classes to a GRU [arxiv:2512.06714 §3.3] [§4.1]. Its gain is measured on two series only [§2], and the feature encoding is ambiguous [§3.3]. |
| Recurring time-of-day or weekly patterns at a fixed place, and a full distribution p(value given place and time) is wanted | Hypertime model with HyT-KM: k-means start, then a Gaussian mixture on time-projected features | Adds sine and cosine time features for each detected period. The paper reports gains over static, histogram and FreMEn baselines on four robot datasets, in figures only [arxiv:1810.04285 §4] [fig. 2]–[fig. 5]. Sampling bias and irregular data gaps shape the result [§4.3] [§5]. |
| Many recorded tasks or conditions, and a smaller set must be chosen for training | k-means on PCA-reduced task profiles, K by silhouette, one representative per cluster | Reduced 8-task set came within 0.02 Nm/kg of all 20 tasks on the paper's data [arxiv:2412.07823 §III.B] [fig. 4]. Gains are from one dataset of 11 healthy adults [§II.A]. |
| Each group must get centres in proportion to its size | SEAR (proportionally representative clustering), not k-means | Plain k-means can violate the proportionality axiom on the paper's three-circle example [arxiv:2304.13917 §4] [fig. 3]. SEAR always returns a PRF outcome, with no experiments reported [§5]. |

## 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
[arxiv: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 [arxiv:2401.08281 §4.1]. Empty clusters may be re-seeded or left empty
[arxiv:1907.05012 app. B].

```pseudocode
# 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 [arxiv:1612.08388 §5.1]
[arxiv:1907.05012 app. D.2]. The vision paper and the water-demand paper pick k
with the elbow method [arxiv:2112.05814 §4] [arxiv: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
[arxiv:1810.04285 §3.8] [eq. 8]. k-FED assumes k is known [arxiv: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
[arxiv: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](/papers/1612.08388): 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](/papers/1907.05012): Q-k-means and DC-k-means, which delete one training point without full retraining.
- [Heterogeneity for the Win: One-Shot Federated Clustering](/papers/2103.00697): k-FED, one-round federated k-means for heterogeneous devices.
- [Deep ViT Features as Dense Visual Descriptors](/papers/2112.05814): 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](/papers/1810.04285): k-means centres start a Gaussian mixture over time-projected robot data; results in figures only.
- [Proportionally Representative Clustering](/papers/2304.13917): SEAR, a fairness-driven centre rule that k-means can violate; theory only.
- [The Faiss library](/papers/2401.08281): 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](/papers/2512.06714): 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](/papers/2412.07823): k-means over PCA-reduced locomotor tasks, with one representative per cluster kept for training a hip-moment estimator.