# k-Means

> Alternate assigning points to the nearest centroid and moving centroids to the mean, until nothing changes.

Source: https://www.mlfoundry.in/learn/k-means  
Section: ML Algorithms › Unsupervised · Clustering  
Level: core · 17 min read · updated 2026-10-07

**k-means:** partitions $n$ points into $k$ clusters, each summarized by a **centroid** (its mean). It alternates two steps — assign every point to its nearest centroid, then move every centroid to the mean of its points — until the assignments stop changing. This is coordinate descent on the **within-cluster sum of squares** $J=\sum_i\lVert x_i-\mu_{c(i)}\rVert^2$.

- **Task:** Clustering (unsupervised): hard partition into exactly $k$ groups
- **Input → output:** points $x_1,\dots,x_n\in\mathbb{R}^d$ and $k$ → a label $c(i)\in\{1,\dots,k\}$ per point and $k$ centroids
- **Learns:** $k$ centroids $\mu_1,\dots,\mu_k$ — nothing else; the clusters are the Voronoi cells of the centroids
- **Training:** $O(nkd)$ per iteration, usually 5–50 iterations; times the number of restarts
- **Prediction:** nearest centroid: $O(kd)$ per point
- **Hyperparameters:** `n_clusters` $k$, `init` (k-means++ or random), `n_init` restarts, `max_iter`, `tol`
- **Assumes:** Euclidean distance is meaningful (features scaled); clusters are compact, convex, roughly spherical and of similar spread

## The problem

You have unlabeled data — customers described by visit frequency and basket size, pixels by colour, documents by embedding — and suspect it falls into groups. You want to **find** those groups without being told what they are, and to describe each one by a single representative that you can inspect, store and compare new points against.

Searching over partitions directly is hopeless: the number of ways to split $n$ points into $k$ non-empty groups (a Stirling number of the second kind) is about $k^n/k!$ — for 100 points and 3 groups that is over $10^{46}$. Even the clean question "which partition minimizes squared distance to the group means?" is NP-hard in general. We need a fast method that finds a *good* partition, accepting that it may not be the best one.

Hierarchical methods (see **hierarchical clustering** and **agglomerative clustering**) build a whole tree of merges but cost $O(n^2)$ memory; k-means scales linearly in $n$, which is why it is the default first clustering for large data.

## The idea

It is a chicken-and-egg problem with an easy solution on each side. **If you knew the centres**, the obvious clustering would be: put each point with its nearest centre. **If you knew the clusters**, the obvious centre of each would be its average point. You know neither, so guess the centres, then alternate the two obvious moves. Each move can only make the clustering tighter, and there are finitely many clusterings, so the process must stop.

**Vocabulary**

- **Centroid:** $\mu_j$, the mean of the points in cluster $j$ — a point in feature space that need not be a data point (contrast the **medoid** of k-medoids, which must be one)
- **Assignment:** $c(i)$, the index of the cluster point $i$ belongs to; k-means is a **hard** assignment (each point in exactly one cluster)
- **Inertia / WCSS:** within-cluster sum of squares $J$, the objective; scikit-learn reports it as "inertia_"
- **Voronoi cell:** the region of space closer to $\mu_j$ than to any other centroid; the cells tile the space and their borders are straight lines (hyperplanes)
- **Lloyd's algorithm:** the assign / update loop itself (Lloyd 1957, published 1982); "k-means" usually means this
- **Seeding:** how the first centroids are chosen: random data points, or k-means++
- **Restart:** one full run from a fresh seeding; keep the run with the lowest $J$
- **Local minimum:** a clustering where neither step can lower $J$, though a different clustering has lower $J$

## The math

Encode the clustering as an assignment $c$ and centroids $\mu$. k-means minimizes

$$
J(c,\mu)=\sum_{i=1}^{n}\lVert x_i-\mu_{c(i)}\rVert^2=\sum_{j=1}^{k}\sum_{i:\,c(i)=j}\lVert x_i-\mu_j\rVert^2
$$

- $x_i$: the $i$-th data point, a vector in $\mathbb{R}^d$
- $c(i)$: cluster index assigned to point $i$
- $\mu_j$: centroid of cluster $j$
- $\lVert\cdot\rVert^2$: squared Euclidean distance: sum over features of squared differences
- $J$: within-cluster sum of squares (inertia); lower = tighter clusters

$J$ is hard to minimize jointly — $c$ is discrete — but easy to minimize in each block of variables with the other held fixed. That is exactly what the two steps do.

**Assign step (fix $\mu$, optimize $c$).** $J$ is a sum of independent terms, one per point, and point $i$ only affects its own term. So each point independently picks the centroid that makes its term smallest:

$$
c(i)\leftarrow\arg\min_{j}\ \lVert x_i-\mu_j\rVert^2
$$

- $\arg\min_j$: the index j that minimizes the expression (ties: lowest index)

The border between two cells is where $\lVert x-\mu_a\rVert^2=\lVert x-\mu_b\rVert^2$. Expanding, the $\lVert x\rVert^2$ terms cancel and we get $2(\mu_b-\mu_a)^\top x=\lVert\mu_b\rVert^2-\lVert\mu_a\rVert^2$ — a **straight line** (hyperplane), the perpendicular bisector of the two centroids. So k-means can only ever carve space into convex polygons.

**Update step (fix $c$, optimize $\mu$).** Now $J$ splits into one term per cluster. For cluster $j$ with point set $S_j$, set the gradient to zero:

$$
\frac{\partial}{\partial\mu_j}\sum_{i\in S_j}\lVert x_i-\mu_j\rVert^2=-2\sum_{i\in S_j}(x_i-\mu_j)=0\ \Longrightarrow\ \mu_j=\frac{1}{|S_j|}\sum_{i\in S_j}x_i
$$

- $S_j$: the set of points currently assigned to cluster $j$
- $|S_j|$: number of points in cluster j

The function is a convex quadratic in $\mu_j$, so this stationary point is the global minimum: **the mean is the point that minimizes the sum of squared distances**. That is why the method is called k-*means*. (With absolute distances the minimizer would be the median — the idea behind k-medians; restricting centres to data points gives **k-medoids**.)

> **Why it always stops:** Each step minimizes $J$ over one block exactly, so $J$ never increases: $J(c^{t+1},\mu^{t+1})\le J(c^{t+1},\mu^{t})\le J(c^{t},\mu^{t})$. The centroids are a function of the assignment, so the algorithm visits a sequence of partitions with non-increasing $J$; with ties broken consistently no partition can repeat, and there are finitely many. Hence Lloyd's algorithm **terminates in finitely many steps — at a local minimum**, not necessarily the global one.

**Variance decomposition.** The total sum of squares around the grand mean $\bar x$ splits exactly into a within-cluster and a between-cluster part:

$$
\underbrace{\sum_i\lVert x_i-\bar x\rVert^2}_{\text{TSS}}=\underbrace{\sum_j\sum_{i\in S_j}\lVert x_i-\mu_j\rVert^2}_{J=\text{WSS}}+\underbrace{\sum_j|S_j|\,\lVert\mu_j-\bar x\rVert^2}_{\text{BSS}}
$$

- $\bar x$: mean of all n points
- $\text{BSS}$: between-cluster sum of squares: how far apart the centroids are, weighted by cluster size

TSS is fixed by the data, so minimizing $J$ is the same as **maximizing the separation between clusters**. The ratio $\text{BSS}/\text{TSS}$ is the fraction of variance "explained" by the clustering.

**What each hyperparameter does to the objective**

- **k:** The optimum $J^*(k)$ is non-increasing in $k$ (adding a centroid can never hurt) and reaches 0 at $k=n$. So $J$ cannot choose $k$ by itself — look for the **elbow** where the drop flattens, or use silhouette / gap statistic.
- **init:** Chooses the starting point of the descent, and therefore which local minimum you land in. k-means++ seeding gives $\mathbb{E}[J]\le 8(\ln k+2)\,J^*$ before any Lloyd iteration.
- **n_init:** Number of independent restarts; the final $J$ is the minimum over runs, so it can only go down as `n_init` grows, at linear cost.
- **max_iter, tol:** Stop after a fixed number of iterations or when the centroids move less than `tol` (relative to feature variance). Too loose a tolerance stops before the assignments settle.

**k-means++ seeding.** Pick the first centre uniformly from the data. Then pick each next centre with probability proportional to $D(x)^2$, the squared distance from $x$ to the nearest centre already chosen. Far-away, not-yet-covered regions are very likely to get a centre; points next to an existing centre almost never are.

$$
P(\text{next centre}=x_i)=\frac{D(x_i)^2}{\sum_{l=1}^{n}D(x_l)^2},\qquad D(x)=\min_{\text{chosen }\mu}\lVert x-\mu\rVert
$$

- $D(x)$: distance from x to its nearest already-chosen centre (0 for chosen points)

> **Connection to Gaussian mixtures:** k-means is the limit of EM for a Gaussian mixture with equal weights and shared spherical covariance $\sigma^2 I$ as $\sigma\to 0$: the soft responsibilities harden into 0/1 assignments, and the M-step becomes the mean. This is why k-means prefers round clusters of similar size — a GMM relaxes exactly those assumptions.

## Worked example: 12 customers, k = 3

Twelve customers described by two already-scaled features. By eye there are three groups — bottom-left (1–4), top (5–8) and bottom-right (9–12) — but the algorithm doesn't know that. We start from a deliberately poor seeding: $\mu_1=(1,2)$ and $\mu_2=(2,1)$ both inside the bottom-left group and $\mu_3=(6,8)$ in the top group, so the bottom-right group has no centroid at all.

The data with the squared distances to the starting centroids. Highlighted: points 9–12, which have no centroid of their own and get split between $\mu_2$ and $\mu_3$.

| # | $x_1$ | $x_2$ | $d^2$ to $\mu_1=(1,2)$ | $d^2$ to $\mu_2=(2,1)$ | $d^2$ to $\mu_3=(6,8)$ | assigned |
| --- | --- | --- | --- | --- | --- | --- |
| 1 | 1 | 2 | **0** | 2 | 61 | $\mu_1$ |
| 2 | 2 | 1 | 2 | **0** | 65 | $\mu_2$ |
| 3 | 2 | 3 | **2** | 4 | 41 | $\mu_1$ |
| 4 | 3 | 2 | 4 | **2** | 45 | $\mu_2$ |
| 5 | 6 | 8 | 61 | 65 | **0** | $\mu_3$ |
| 6 | 7 | 7 | 61 | 61 | **2** | $\mu_3$ |
| 7 | 7 | 9 | 85 | 89 | **2** | $\mu_3$ |
| 8 | 8 | 8 | 85 | 85 | **4** | $\mu_3$ |
| 9 | 8 | 2 | 49 | **37** | 40 | $\mu_2$ |
| 10 | 9 | 1 | 65 | **49** | 58 | $\mu_2$ |
| 11 | 9 | 3 | 65 | 53 | **34** | $\mu_3$ |
| 12 | 10 | 2 | 81 | 65 | **52** | $\mu_3$ |

**Lloyd's algorithm by hand**

1. **Iteration 1 · assign.** Each row takes its smallest $d^2$ (bold). Clusters: $\mu_1\{1,3\}$, $\mu_2\{2,4,9,10\}$, $\mu_3\{5,6,7,8,11,12\}$. Summing the bold column: $J=0+0+2+2+0+2+2+4+37+49+34+52=184$.
2. **Iteration 1 · update.** Means: $\mu_1=\tfrac12[(1,2)+(2,3)]=(1.5,2.5)$; $\mu_2=\tfrac14[(2,1)+(3,2)+(8,2)+(9,1)]=(5.5,1.5)$; $\mu_3=\tfrac16(47,37)=(7.833,6.167)$. With the same clusters, $J$ drops to $92.667$. $\mu_2$ has been dragged halfway across the plot by points 9 and 10.
3. **Iteration 2 · assign.** Points 2 and 4 are now closer to $\mu_1$ ($d^2=2.5$ vs 12.5 and 6.5) and point 12 is closer to $\mu_2$ ($20.5$ vs $22.056$). Clusters: $\mu_1\{1,2,3,4\}$, $\mu_2\{9,10,12\}$, $\mu_3\{5,6,7,8,11\}$; $J=77.111$.
4. **Iteration 2 · update.** $\mu_1=(2,2)$, $\mu_2=\tfrac13(27,5)=(9,1.667)$, $\mu_3=\tfrac15(37,35)=(7.4,7)$; $J=33.867$.
5. **Iteration 3 · assign.** Only point 11 moves: $d^2=1.778$ to $\mu_2$ vs $18.56$ to $\mu_3$. Clusters are now the three visual groups; $J=17.084$.
6. **Iteration 3 · update.** $\mu_1=(2,2)$, $\mu_2=(9,2)$, $\mu_3=(7,8)$; $J=12$ — every point is at squared distance 1 from its centroid.
7. **Iteration 4 · assign.** No point changes cluster, so the centroids would not move either: **converged** after 3 updates. $J=12$, and TSS $=212$ around the grand mean $(6,4)$, so $\text{BSS}=200$ and the clustering explains $200/212=94.3\%$ of the variance.
8. **Predict a new customer** $q=(6,3)$: $d^2$ to $(2,2),(9,2),(7,8)$ is $17,\ 10,\ 26$. Nearest is $\mu_2$, so $q$ joins the **bottom-right** cluster.

$J$ after every half-step. It never increases — 184 → 12 — which is the convergence argument in action.

| Iteration | Step | $\mu_1$ | $\mu_2$ | $\mu_3$ | Points that moved | $J$ |
| --- | --- | --- | --- | --- | --- | --- |
| 1 | assign | (1, 2) | (2, 1) | (6, 8) | all 12 | 184.000 |
| 1 | update | (1.5, 2.5) | (5.5, 1.5) | (7.833, 6.167) | — | 92.667 |
| 2 | assign |  |  |  | 2, 4, 12 | 77.111 |
| 2 | update | (2, 2) | (9, 1.667) | (7.4, 7) | — | 33.867 |
| 3 | assign |  |  |  | 11 | 17.084 |
| 3 | update | (2, 2) | (9, 2) | (7, 8) | — | **12.000** |
| 4 | assign |  |  |  | none → stop | 12.000 |

> Figure: The 12 customers from the table. Press Next step to alternate assign and update from the article's start: J falls 184 → 92.667 → 77.111 → 33.867 → 17.084 → 12. Dashed arrows show where each centroid will jump (its cluster mean); dashed rings mark points about to switch cluster. Drag any centroid to re-seed by hand, try the stuck start (it ends at J = 90, a local minimum), re-seed with k-means++, change k and watch your J against the elbow curve (best J = 212, 92, 12, 10, 8, 6 for k = 1…6), and drag the diamond to classify a new point — once converged, (6, 3) joins μ₂ = (9, 2) with d² = 10.

## Local minima and seeding

Start instead from $\mu=(1,2),(2,1),(3,2)$ — all three centroids in the bottom-left group. After two iterations Lloyd settles on $\mu_1=(1.5,2.5)$, $\mu_2=(2.5,1.5)$, $\mu_3=(8,5)$: the bottom-left group is split in two and the top and bottom-right groups are merged into one cluster. $J=90$, seven and a half times the optimum, and **neither step can improve it**: no point is closer to another centroid, and every centroid is at its mean.

How often does a random start fail here? Of the $\binom{12}{3}=220$ ways to seed with three data points, 183 (83.2%) reach $J=12$. **k-means++** does much better: from a first centre at $(1,2)$, the squared distances sum to 560, and only $8/560=1.4\%$ of that mass is in the bottom-left group, versus 52.1% in the top and 46.4% in the bottom-right. Using scikit-learn's k-means++ with a single run, all 1000 seeds we tried reached $J=12$. Restarts (`n_init`) handle the remaining bad luck.

> Figure: Lloyd's algorithm on 54 points in three blobs, from a poor start with two centroids in one blob. Shaded regions are the Voronoi cells of the current centroids; dashed lines show each update's move.

## The algorithm, step by step

**KMeans(X, k)**

1. **Scale** the features (standardize) so that no feature dominates the distance.
2. **Seed** $k$ centroids with k-means++: first uniformly at random, each next one with probability $\propto D(x)^2$.
3. **Assign** each point to its nearest centroid: compute the $n\times k$ matrix of squared distances and take the row-wise arg-min.
4. **Update** each centroid to the mean of its points. If a cluster is empty, re-seed it (e.g. at the point farthest from its centroid).
5. **Repeat** assign and update until no assignment changes, the centroids move less than `tol`, or `max_iter` is reached.
6. **Restart** `n_init` times and keep the run with the lowest $J$.
7. **Predict** a new point by its nearest centroid.

**Complexity**

- **Per iteration:** $O(nkd)$ for the distances, $O(nd)$ for the means
- **Total:** $O(nkd\cdot T\cdot \text{n\_init})$ with $T$ iterations; $T$ is small in practice although the worst case is exponential
- **Memory:** $O(nd+kd)$ — no pairwise distance matrix, unlike hierarchical clustering or affinity propagation
- **Prediction:** $O(kd)$ per point

## Variants and practical tuning

The k-means family. The first three are drop-in speedups of the same objective; the rest change the objective or the centres.

| Variant | What changes | When to use |
| --- | --- | --- |
| Elkan's algorithm | triangle inequality bounds skip most distance computations | dense data, moderate k (scikit-learn `algorithm="elkan"`) |
| Mini-batch k-means | updates centroids from small random batches with a decaying learning rate | millions of points or streaming data; slightly higher J |
| Bisecting k-means | repeatedly splits the cluster with the largest J in two | large k; gives a hierarchy and more even cluster sizes |
| k-medoids (PAM) | centres must be data points; any distance | non-Euclidean distances, robustness to outliers — see **k-medoids** |
| Spherical k-means | cosine similarity, centroids normalized to unit length | text / embedding vectors |
| Kernel k-means | distances in a kernel feature space | non-convex clusters; closely related to spectral clustering |
| Fuzzy c-means | soft memberships with fuzzifier m | points can belong partly to several groups (or use a GMM) |

Choosing $k$ on the worked example: the best $J$ for each $k$ and the silhouette score of that clustering. Both point to $k=3$.

| k | best $J$ | drop from $k-1$ | silhouette |
| --- | --- | --- | --- |
| 1 | 212 | — | — |
| 2 | 92 | 120 | 0.536 |
| **3** | **12** | **80** | **0.753** |
| 4 | 10 | 2 | 0.547 |
| 5 | 8 | 2 | 0.365 |

The **elbow**: going from 2 to 3 clusters removes 80 units of $J$, going from 3 to 4 removes only 2. The **silhouette** of a point is $(b-a)/\max(a,b)$, where $a$ is its mean distance to its own cluster and $b$ to the nearest other cluster; the average is highest (0.753) at $k=3$.

> **Feature scale decides the clusters:** k-means uses raw Euclidean distance, so a feature in larger units dominates. Multiply $x_2$ in the worked example by 10 (say, dollars instead of tens of dollars) and the best 3-clustering changes completely: points 3 $(2,3)$ and 11 $(9,3)$ — on opposite sides of the plot — end up in the same cluster, because they share $x_2=3$. Standardize first, or weight features on purpose.

> **Wrong shapes, wrong answer:** Because cells are bounded by perpendicular bisectors, k-means cannot find elongated, curved, nested or very unequal-sized clusters: it will slice a long cluster in half and swallow a small one into a big neighbour. Use a Gaussian mixture (elliptical clusters), DBSCAN / HDBSCAN (arbitrary shapes, noise) or spectral clustering instead.

## In code

```python
import numpy as np

def kmeans_pp(X, k, rng):
    centres = [X[rng.integers(len(X))]]
    for _ in range(k - 1):
        d2 = ((X[:, None] - np.array(centres)[None]) ** 2).sum(-1).min(1)
        centres.append(X[rng.choice(len(X), p=d2 / d2.sum())])   # D² sampling
    return np.array(centres, float)

def lloyd(X, mu, max_iter=100):
    mu = np.array(mu, float)
    labels = None
    for it in range(1, max_iter + 1):
        d2 = ((X[:, None] - mu[None]) ** 2).sum(-1)               # n × k squared distances
        new = d2.argmin(1)                                        # assign
        if labels is not None and (new == labels).all():
            break                                                 # converged
        labels = new
        for j in range(len(mu)):                                  # update
            if (labels == j).any():
                mu[j] = X[labels == j].mean(0)
        J = ((X - mu[labels]) ** 2).sum()
        print(f"iter {it}: J = {J:.3f}  centroids = {np.round(mu, 3).tolist()}")
    return labels, mu, ((X - mu[labels]) ** 2).sum()

def kmeans(X, k, n_init=10, seed=0):
    rng = np.random.default_rng(seed)
    runs = [lloyd(X, kmeans_pp(X, k, rng)) for _ in range(n_init)]
    return min(runs, key=lambda r: r[2])                          # keep the lowest J

X = np.array([[1, 2], [2, 1], [2, 3], [3, 2], [6, 8], [7, 7],
              [7, 9], [8, 8], [8, 2], [9, 1], [9, 3], [10, 2]], float)

labels, mu, J = lloyd(X, [[1, 2], [2, 1], [6, 8]])               # the article's start
print(labels, J)                  # [0 0 0 0 2 2 2 2 1 1 1 1] 12.0
x_new = np.array([6, 3])
print("new point ->", ((mu - x_new) ** 2).sum(1).argmin())       # 1
```

From scratch: k-means++ seeding, Lloyd's loop and restarts. Run on the article's start, it prints J = 92.667, 33.867, 12.000 and assigns (6, 3) to cluster 1 (μ₂).

```python
import numpy as np
from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score

X = np.array([[1, 2], [2, 1], [2, 3], [3, 2], [6, 8], [7, 7],
              [7, 9], [8, 8], [8, 2], [9, 1], [9, 3], [10, 2]], float)

# 1) Reproduce the hand computation: fixed start, a single run.
km = KMeans(n_clusters=3, init=np.array([[1, 2], [2, 1], [6, 8]]), n_init=1).fit(X)
print(km.labels_, km.cluster_centers_.tolist(), km.inertia_, km.n_iter_)
# [0 0 0 0 2 2 2 2 1 1 1 1] [[2.0, 2.0], [9.0, 2.0], [7.0, 8.0]] 12.0 4
print(km.predict([[6, 3]]))                       # [1]

# 2) The poor start gets stuck in a local minimum.
bad = KMeans(n_clusters=3, init=np.array([[1, 2], [2, 1], [3, 2]]), n_init=1).fit(X)
print(bad.inertia_)                               # 90.0

# 3) In practice: k-means++ with restarts, and choosing k.
for k in range(2, 6):
    m = KMeans(n_clusters=k, init="k-means++", n_init=10, random_state=0).fit(X)
    print(k, round(m.inertia_, 3), round(silhouette_score(X, m.labels_), 3))
# 2 92.0 0.536 | 3 12.0 0.753 | 4 10.0 0.547 | 5 8.0 0.365
```

scikit-learn on the same data: the fixed start reproduces the hand computation (n_iter_ = 4 counts the final, unchanged assignment), the stuck start ends at 90, and k-means++ with restarts picks out the elbow.

> **Scale and speed in practice:** Put `StandardScaler()` before `KMeans` in a `Pipeline`. For more than about 100k points use `MiniBatchKMeans`; for nearest-centroid search over many centroids (vector databases), FAISS implements k-means on GPU.

**Strengths**

- You need a fast, scalable clustering: linear in n, millions of points, mini-batch for streams.
- Clusters are compact, round-ish and similar in size, and a mean is a meaningful prototype.
- You want a codebook: vector quantization, colour quantization, coarse indexes for nearest-neighbour search, or to initialize a Gaussian mixture.
- You need to assign new points cheaply — one distance per centroid.

**Limitations**

- Clusters are elongated, nested, non-convex or very different in size or density — use GMM, DBSCAN/HDBSCAN or spectral clustering.
- There are strong outliers: one far point drags a mean — use k-medoids or remove outliers first.
- Features are categorical or distance is not Euclidean — use k-modes or k-medoids.
- You have no idea what k is and want a hierarchy instead — use agglomerative clustering or HDBSCAN.

- **Customer segmentation:** Group customers by recency, frequency and spend; each centroid is a readable "typical customer" for a marketing persona.
- **Colour quantization & compression:** Cluster pixel colours into $k$ centroids (say 16) and store each pixel as a 4-bit index into that palette.
- **Vector search indexes:** Inverted-file (IVF) indexes in FAISS and similar libraries use k-means centroids as coarse buckets, so a query only scans the few nearest buckets.
- **Bag of visual words / features:** Cluster local image descriptors or embeddings; the cluster index becomes a discrete token or a feature for a downstream model.

**Question:** Why is a centroid updated to the mean of its cluster's points?

- A. It is robust to outliers
- B. The mean minimizes the sum of squared distances to the points
- C. It is always a data point
- D. It guarantees the global optimum of J

**Answer:** B. The mean minimizes the sum of squared distances to the points — $\frac{\partial}{\partial\mu}\sum_i\lVert x_i-\mu\rVert^2=-2\sum_i(x_i-\mu)=0\Rightarrow\mu=\bar x$, and the function is convex, so this is the minimum. The mean is *not* robust to outliers (that is the median / medoid).

**Question:** With centroids (2, 2), (9, 2) and (7, 8), which centroid does the new point (6, 3) join?

- A. (2, 2)
- B. (9, 2)
- C. (7, 8)
- D. It is a tie

**Answer:** B. (9, 2) — Squared distances: $(4^2+1^2)=17$, $(3^2+1^2)=10$, $(1^2+5^2)=26$. The smallest is 10, so $(9,2)$.

**Question:** k-means++ has placed its first centre at (1, 2) in the worked example (squared distances sum to 560). What is the probability that the second centre lands in the bottom-left group (points 1–4)?

- A. 25%
- B. 33%
- C. 1.4%
- D. 0%

**Answer:** C. 1.4% — The bottom-left points have $D^2=0,2,2,4$, summing to 8, so the probability is $8/560\approx1.4\%$. The top group gets $292/560=52.1\%$ and the bottom-right $260/560=46.4\%$.

**Question:** Why can't you choose k by picking the value with the lowest inertia J?

- A. J is not defined for k > 3
- B. The best J never increases with k and is 0 when k = n
- C. J is random
- D. J increases with k

**Answer:** B. The best J never increases with k and is 0 when k = n — Adding a centroid can only lower the optimum (on the example: 212, 92, 12, 10, 8, 6 for k = 1…6), so the lowest J is always the largest k. Look for the elbow, or use the silhouette score.

**Key points**

- k-means minimizes the within-cluster sum of squares $J$ by coordinate descent: assign each point to its nearest centroid, move each centroid to its mean.
- Each step can only lower $J$, so the algorithm always terminates — but at a local minimum (on the example, $J=90$ versus the optimum 12).
- Seed with k-means++ (D² sampling) and run several restarts; keep the lowest J.
- Standardize features: Euclidean distance lets large-unit features decide the clusters.
- Choose k by the elbow, silhouette or gap statistic — J alone always prefers more clusters.
- Cells are convex (perpendicular bisectors), so k-means suits compact, round, similar-sized clusters; otherwise use GMM, DBSCAN or spectral clustering.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
