AI, machine learning and deep learning · Introductory

k-means clustering

Written by SignalsLab

Early edition: these lessons are being reviewed.

Content

Summary

k-means clustering partitions unlabeled data points into k groups by repeatedly assigning each point to its nearest cluster center and then moving each center to the mean of its assigned points. It stops when assignments no longer change. It is a simple way to find structure in data such as patient subgroups or gene expression patterns.

Intuition

Imagine scattering k pins on a map of data points. Each point joins the group of the nearest pin. Then each pin slides to the center of mass of its group. Because pins moved, some points are now closer to a different pin, so groups are redrawn, and the pins slide again. This back-and-forth always reduces the total squared distance from points to their pins, until nothing changes. The result is compact groups, but it depends on where the pins started, so it may settle on a local rather than global optimum.

Key equations

ci=arg⁡minj⁡‖xi−μj‖2
(1)

Assignment step: point x_i joins the cluster whose center mu_j is nearest.

μj=1|Sj|∑xi∈Sjxi
(2)

Update step: each center becomes the mean of the points S_j assigned to it.

J=∑j=1k∑xi∈Sj‖xi−μj‖2
(3)

Objective: within-cluster sum of squared distances, which k-means decreases at every step.

Derivation

  1. Goal: choose centers and assignments that minimize J.
  2. Fix the centers. J is minimized by giving each point to its nearest center, since each point's term is smallest there. This is the assignment step.
  3. Fix the assignments. For one cluster, set the derivative of the sum of squared distances with respect to mu_j to zero: -2 times the sum of (x_i - mu_j) equals 0.
  4. Solving gives mu_j equal to the average of the points in S_j. This is the update step.
  5. Each step cannot increase J, and there are finitely many possible assignments, so the algorithm converges, though possibly to a local minimum.

Worked example

Problem

One-dimensional data: 1, 2, 3, 10, 11, 12. Use k=2 with initial centers 1 and 2. Run k-means to convergence.

  1. Iteration 1 assignment: 1 goes to center 1. 2 goes to center 2. 3 is nearer 2 (distance 1 versus 2). 10, 11, 12 go to center 2.
  2. Update: cluster A = {1}, mean 1. Cluster B = {2,3,10,11,12}, mean 38/5 = 7.6.
  3. Iteration 2 assignment: 1 goes to A. 2 is 1 from A and 5.6 from B, so A. 3 is 2 from A and 4.6 from B, so A. 10, 11, 12 go to B.
  4. Update: A = {1,2,3}, mean 2. B = {10,11,12}, mean 11.
  5. Iteration 3: assignments are unchanged, so the algorithm stops.

Answer Clusters {1,2,3} and {10,11,12} with centers 2 and 11.

Common mistakes

  • Forgetting that results depend on the initial centers; run several random starts or use k-means++.
  • Not scaling features, so a variable with large units dominates the distance.
  • Assuming k-means finds non-spherical or very unequal-sized clusters correctly.
  • Treating the chosen k as known; it must be selected, for example with the elbow method or silhouette score.
  • Believing convergence means the global best solution.

Animation

Animation coming soon

The animated version of this lesson is being prepared for the web. In the Signals AI app, lessons are drawn step by step.

Code

scene.py(75 lines)
import sys
import numpy as np
from manim import *
from blocks import *

COLORS = [C_MAIN, C_ACCENT, C_GOOD]


def make_data():
    """Fixed-seed 2D points around three centres."""
    rng = np.random.RandomState(3)
    centres = np.array([[-3.0, 1.0], [2.5, 1.8], [0.0, -1.8]])
    pts = np.vstack([c + 0.55 * rng.randn(8, 2) for c in centres])
    return pts


def kmeans_trace(pts, init, iters=6):
    """Run k-means, recording (centroids, labels) after each assign and update step."""
    cent = np.array(init, dtype=float)
    trace = []
    for _ in range(iters):
        d = np.linalg.norm(pts[:, None, :] - cent[None, :, :], axis=2)
        lab = d.argmin(axis=1)
        trace.append(("assign", cent.copy(), lab.copy()))
        new = np.array([pts[lab == k].mean(axis=0) if np.any(lab == k) else cent[k]
                        for k in range(len(cent))])
        trace.append(("update", new.copy(), lab.copy()))
        if np.allclose(new, cent):
            break
        cent = new
    return trace


PTS = make_data()
TRACE = kmeans_trace(PTS, [PTS[0], PTS[1], PTS[2]])


class Main(Scene):
    def construct(self):
        TitleCard(self, "k-means clustering", "assign, then update")
        plane = lambda p: np.array([p[0] * 0.9, p[1] * 0.9 - 0.2, 0])
        dots = VGroup(*[Dot(plane(p), radius=0.08, color=WHITE) for p in PTS])
        self.play(FadeIn(dots))
        cent0 = TRACE[0][1]
        cents = VGroup(*[Star(n=5, outer_radius=0.22, color=COLORS[k], fill_opacity=1)
                         .move_to(plane(cent0[k])) for k in range(3)])
        for c in cents:
            c.set_stroke(WHITE, 1.5)
        self.play(FadeIn(cents))
        StepCaption(self, "Start with 3 centroids picked from the data")
        shown = 0
        for kind, cent, lab in TRACE[:6]:
            if kind == "assign":
                self.play(*[dots[i].animate.set_color(COLORS[lab[i]]) for i in range(len(PTS))],
                          run_time=0.8)
                if shown == 0:
                    StepCaption(self, "Assign each point to its nearest centroid")
            else:
                self.play(*[cents[k].animate.move_to(plane(cent[k])) for k in range(3)],
                          run_time=0.8)
                if shown == 0:
                    StepCaption(self, "Move each centroid to its cluster mean")
                shown += 1
        StepCaption(self, "Repeat until assignments stop changing")

if __name__ == "__main__" and "--selftest" in sys.argv:
    assert len(TRACE) >= 2 and len(TRACE) % 2 == 0
    final_c, final_l = TRACE[-1][1], TRACE[-1][2]
    for k in range(3):
        assert np.allclose(final_c[k], PTS[final_l == k].mean(axis=0))
    assert set(final_l) == {0, 1, 2}
    assert np.allclose(TRACE[-1][1], TRACE[-2][1]) or len(TRACE) == 12
    inertia = lambda c, l: sum(np.sum((PTS[l == k] - c[k]) ** 2) for k in range(3))
    assert inertia(TRACE[-1][1], final_l) <= inertia(TRACE[1][1], TRACE[0][2]) + 1e-9
    print("ok")

The Manim scene code that draws this lesson's animation in the Signals AI app (Python, Manim Community).

ccBYNC© 2026 SignalsLab. Lesson text shared as is under CC BY-NC 4.0.