K-Means: Full AlgorithmOpen in Colab

K-Means: Full Algorithm

K-Means partitions nn points into KK clusters by minimizing the within-cluster sum of squared distances to centroids:

J=∑k=1K∑xi∈Ck∥xi−μk∥2J = \sum_{k=1}^{K}\sum_{\mathbf{x}_i \in C_k} \|\mathbf{x}_i - \boldsymbol{\mu}_k\|^2

The algorithm alternates two steps, each of which provably decreases JJ.

The algorithm steps and why each decreases J

Step 0: Initialize KK centroids μ1,…,μK\boldsymbol{\mu}_1, \ldots, \boldsymbol{\mu}_K (random pick from data, or K-Means++).

Step 1: Assign. Assign every point to its nearest centroid:

Ck={xi:∥xi−μk∥2≤∥xi−μj∥2  ∀j≠k}C_k = \{\mathbf{x}_i : \|\mathbf{x}_i - \boldsymbol{\mu}_k\|^2 \le \|\mathbf{x}_i - \boldsymbol{\mu}_j\|^2 \;\forall j \ne k\}

With centroids fixed, JJ decomposes into per-point terms; assigning each to the nearest centroid minimizes its term and therefore minimizes JJ overall.

Step 2: Update. Move each centroid to the mean of its assigned points:

μk=1∣Ck∣∑xi∈Ckxi\boldsymbol{\mu}_k = \frac{1}{|C_k|}\sum_{\mathbf{x}_i \in C_k}\mathbf{x}_i

With assignments fixed, cluster kk's contribution to JJ is ∑xi∈Ck∥xi−μk∥2\sum_{\mathbf{x}_i \in C_k}\|\mathbf{x}_i - \boldsymbol{\mu}_k\|^2. Setting its gradient to zero:

∇μk∑xi∈Ck∥xi−μk∥2=∑xi∈Ck−2(xi−μk)=0  ⇒  μk=1∣Ck∣∑xi∈Ckxi\nabla_{\boldsymbol{\mu}_k}\sum_{\mathbf{x}_i \in C_k}\|\mathbf{x}_i - \boldsymbol{\mu}_k\|^2 = \sum_{\mathbf{x}_i \in C_k} -2(\mathbf{x}_i - \boldsymbol{\mu}_k) = \mathbf{0} \;\Rightarrow\; \boldsymbol{\mu}_k = \frac{1}{|C_k|}\sum_{\mathbf{x}_i \in C_k}\mathbf{x}_i

The mean is the unique minimizer of within-cluster squared distance — that is why the update uses the mean.

Step 3: Repeat Steps 1–2 until no point changes cluster (convergence).

Guaranteed convergence, local optimum

Both steps only decrease JJ, and there are finitely many possible assignment configurations, so K-Means must terminate. But it converges to a local minimum — different initializations can give different final clusters. Use K-Means++ and n_init ≥ 10 in practice.

Watch it run

Step through the loop on five points with K=2K = 2 — every distance calculation as each point picks its centroid, and JJ reported before and after each update so you can watch both steps drive it down. The arithmetic is worked out by hand in the section below if you want to check any number.

K-Means — assign, update, converge (and land in a local optimum)

1/11

Five points, K = 2, with the centroids initialized on top of A and E. K-Means alternates two steps — assign, then update — and both are guaranteed to lower the objective J, the total squared distance from each point to its centroid.

python
1def kmeans(X, mu):
2 while True:
3 # assign: nearest centroid wins
4 labels = [argmin([d2(x, m) for m in mu])
5 for x in X]
6 # update: centroid = mean of members
7 new_mu = [mean([x for x, l in
8 zip(X, labels) if l == k])
9 for k in range(K)]
10 if new_mu == mu:
11 return labels, mu # converged
12 mu = new_mu
state
points and initial centroids
0680ABCDEμ1μ2

J = Σ ‖x − μ‖² over all points. Watch it fall at every step, and watch it stop falling exactly when no point changes cluster.

The full assign/update loop on five points with K = 2, matching the hand-worked iteration above. Every distance calculation is shown as each point picks its centroid, and the objective J is reported before and after each update so you can watch both steps decrease it. The final step re-runs the identical algorithm from a different initialization and converges to a worse partition — the local-optimum caveat, demonstrated rather than asserted.

What to notice as you step:

  • The update never changes an assignment, and the assignment never moves a centroid. That strict alternation is why each step can be proved to decrease JJ separately, and why the proof is so short.
  • Convergence is detected by nothing happening. The loop ends when the recomputed centroids equal the old ones, which happens exactly when no point changed cluster.
  • The final step re-runs the identical code from a different initialization and converges just as confidently to a worse partition (J=9.96J = 9.96 against 7.467.46). Nothing went wrong — JJ simply has more than one basin, and the starting point decides which one you fall into.

A full worked iteration on 5 points

Here K=2K = 2.

Points: A(1,1)A(1,1), B(1.5,2)B(1.5,2), C(3,4)C(3,4), D(5,7)D(5,7), E(3.5,5)E(3.5,5).

Initialize: μ1=(1,1)\boldsymbol{\mu}_1 = (1,1), μ2=(3.5,5)\boldsymbol{\mu}_2 = (3.5,5).

Iteration 1: Assign

Compute squared Euclidean distance from each point to each centroid (closer one wins):

Point∥x−μ1∥2\|\mathbf{x}-\boldsymbol{\mu}_1\|^2∥x−μ2∥2\|\mathbf{x}-\boldsymbol{\mu}_2\|^2Assigned
A(1,1)A(1,1)00(1−3.5)2+(1−5)2=6.25+16=22.25(1-3.5)^2+(1-5)^2=6.25+16=22.25C1C_1
B(1.5,2)B(1.5,2)0.25+1=1.250.25+1=1.254+9=134+9=13C1C_1
C(3,4)C(3,4)4+9=134+9=130.25+1=1.250.25+1=1.25C2C_2
D(5,7)D(5,7)16+36=5216+36=522.25+4=6.252.25+4=6.25C2C_2
E(3.5,5)E(3.5,5)6.25+16=22.256.25+16=22.2500C2C_2

C1={A,B}C_1 = \{A, B\}, C2={C,D,E}C_2 = \{C, D, E\}.

Objective with old centroids: J=(0+1.25)+(1.25+6.25+0)=8.75J = (0 + 1.25) + (1.25 + 6.25 + 0) = 8.75.

Iteration 1: Update

μ1=(1,1)+(1.5,2)2=(1.25, 1.5)\boldsymbol{\mu}_1 = \frac{(1,1)+(1.5,2)}{2} = (1.25,\ 1.5) μ2=(3,4)+(5,7)+(3.5,5)3=(11.53, 163)=(3.83, 5.33)\boldsymbol{\mu}_2 = \frac{(3,4)+(5,7)+(3.5,5)}{3} = \left(\frac{11.5}{3},\ \frac{16}{3}\right) = (3.83,\ 5.33)

Recomputing JJ with new centroids:

Jafter=[(1.25−1)2+(1.5−1)2+(1.25−1.5)2+(1.5−2)2]+[⋯ ]≈7.46J_{\text{after}} = \bigl[(1.25-1)^2+(1.5-1)^2 + (1.25-1.5)^2+(1.5-2)^2\bigr] + \bigl[\cdots\bigr] \approx 7.46

7.46<8.757.46 < 8.75 — the update step lowered JJ exactly as the derivation guarantees.

Iteration 2: Reassign

Check whether any point is closer to the other cluster's new centroid:

Point∥x−μ1(1)∥2\|\mathbf{x}-\boldsymbol{\mu}_1^{(1)}\|^2∥x−μ2(1)∥2\|\mathbf{x}-\boldsymbol{\mu}_2^{(1)}\|^2Same cluster?
A(1,1)A(1,1)0.0625+0.25=0.31250.0625+0.25=0.31258.05+19.15=27.28.05+19.15=27.2✓ C1C_1
B(1.5,2)B(1.5,2)0.0625+0.25=0.31250.0625+0.25=0.31255.38+11.09=16.55.38+11.09=16.5✓ C1C_1
C(3,4)C(3,4)3.06+6.25=9.313.06+6.25=9.310.69+1.78=2.470.69+1.78=2.47✓ C2C_2
D(5,7)D(5,7)13.69+30.25=43.913.69+30.25=43.91.37+2.79=4.161.37+2.79=4.16✓ C2C_2
E(3.5,5)E(3.5,5)5.06+12.25=17.35.06+12.25=17.30.07+0.44=0.510.07+0.44=0.51✓ C2C_2

No point changes assignment. Converged after 2 iterations.

Final clusters: C1={A,B}C_1 = \{A, B\}, C2={C,D,E}C_2 = \{C, D, E\}.

Implementing K-Means from scratch in NumPy

Python
import numpy as np

def kmeans(X, K, n_iter=100, seed=42):
    rng = np.random.default_rng(seed)
    # Random initialization
    mu = X[rng.choice(len(X), K, replace=False)]

    for _ in range(n_iter):
        # Step 1 — assign
        dists = np.linalg.norm(X[:, None] - mu[None], axis=2)  # (n, K)
        labels = dists.argmin(axis=1)

        # Step 2 — update
        new_mu = np.array([X[labels == k].mean(axis=0) for k in range(K)])

        if np.allclose(new_mu, mu):   # converged
            break
        mu = new_mu

    J = sum(np.sum((X[labels == k] - mu[k])**2) for k in range(K))
    return labels, mu, J

X = np.array([[1,1],[1.5,2],[3,4],[5,7],[3.5,5]], dtype=float)
labels, centroids, inertia = kmeans(X, K=2)
print("labels   :", labels)       # [0 0 1 1 1]
print("centroids:", centroids.round(2))
print("inertia  :", round(inertia, 2))

Related concepts

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

RelatedReferenced by
K-Means: Full AlgorithmDBSCAN: Core, Border, Noi…Hierarchical Clustering L…Minkowski Distance FamilyK-Means ClusteringGaussian Mixture ModelsHierarchical Clustering &…