# How k-means Works

k-means finds k groups with a short loop you can run by hand, place k centers, give each example to its nearest center, move each center to the mean of its examples, and repeat until nothing moves, and because it only ever improves from where it starts, different starting centers can end in different groups.

Journeyman · AI Basics · Python · Updated November 19, 2026

By Gregor Dzierzon

## After this lesson you can

- Run one round of k-means by hand, assigning each point to its nearest center and moving each center to the mean of its points
- Explain why k-means repeats until nothing moves, and why different starting centers can end in different groups

## Key takeaways

- k is the number of groups you ask for. k-means starts with k centers, often k of the examples themselves.
- Each round gives every example to its nearest center, then moves each center to the mean of the examples it was given.
- The rounds repeat until the centers stop moving. Each center then sits in the middle of its group.
- Different starting centers can end in different groups, and one ending can be worse than another, so k-means is usually run from several starts.

Clustering 600 café members sounds like it needs something clever. The method this chapter uses, **k-means**, is a short loop you could run with a pencil: two steps, repeated. Do one round by hand here, and scikit-learn's `KMeans` in the next lesson holds no mystery; you'll also know why it can give a different answer when it starts somewhere else.

The example is six members of the Cozy Corner Café, each a point of two numbers: visits a month and average spend in dollars. Three come early and often and spend little; three come rarely and spend a lot. This lesson is plain Python.

## Start with k centers

The *k* in k-means is the number of groups you ask for, read "k". Here k is 2. Each group gets a **center**, a point that stands for the middle of the group, and k-means has to start somewhere, so the simplest start uses k of the members themselves as the first centers. Here they're the first two members, both early regulars: a poor start on purpose, to watch k-means fix it.

The first step gives each member to its nearest center, by the straight-line distance from *Distance Between Examples*:

```python
import math

members = [(18, 5), (16, 6), (20, 4), (4, 20), (2, 22), (6, 18)]
centers = [(18, 5), (16, 6)]

for member in members:
    distances = [math.dist(member, center) for center in centers]
    nearest = distances.index(min(distances))
    print(member, "is nearest center", nearest, [round(d, 1) for d in distances])
```

```text
(18, 5) is nearest center 0 [0.0, 2.2]
(16, 6) is nearest center 1 [2.2, 0.0]
(20, 4) is nearest center 0 [2.2, 4.5]
(4, 20) is nearest center 1 [20.5, 18.4]
(2, 22) is nearest center 1 [23.3, 21.3]
(6, 18) is nearest center 1 [17.7, 15.6]
```

`distances.index(min(distances))` finds the position of the smallest distance: 0 for the first center, 1 for the second. The three big spenders are far from both centers, but center 1 is a little nearer, so they go to it, with one early regular.

## Move each center to the middle

The second step moves each center to the **mean** of its members: the average of their visits and the average of their spends.

| Center | Its members | Mean visits | Mean spend | New center |
|---|---|---|---|---|
| 0 | (18, 5), (20, 4) | (18 + 20) ÷ 2 = 19 | (5 + 4) ÷ 2 = 4.5 | (19, 4.5) |
| 1 | (16, 6), (4, 20), (2, 22), (6, 18) | (16 + 4 + 2 + 6) ÷ 4 = 7 | (6 + 20 + 22 + 18) ÷ 4 = 16.5 | (7, 16.5) |

Center 1 jumped toward the big spenders. A center that is the mean of its group's points is called a **centroid** in your textbook and in scikit-learn's guide.

## Repeat until nothing moves

Those two steps are one round. Run another, and the early regular at (16, 6) is now much nearer center 0, so it changes groups. The loop below runs rounds until the new centers equal the old ones (`fmean` is the `statistics` module's mean):

```python
import math
from statistics import fmean

members = [(18, 5), (16, 6), (20, 4), (4, 20), (2, 22), (6, 18)]
centers = [(18, 5), (16, 6)]

for round_number in range(1, 10):
    groups = []
    for member in members:
        distances = [math.dist(member, center) for center in centers]
        groups.append(distances.index(min(distances)))

    new_centers = []
    for number in range(len(centers)):
        mine = [member for member, group in zip(members, groups) if group == number]
        new_centers.append((fmean(m[0] for m in mine), fmean(m[1] for m in mine)))

    print("Round", round_number, "groups:", groups, "centers:", new_centers)
    if new_centers == centers:
        break
    centers = new_centers
```

```text
Round 1 groups: [0, 1, 0, 1, 1, 1] centers: [(19.0, 4.5), (7.0, 16.5)]
Round 2 groups: [0, 0, 0, 1, 1, 1] centers: [(18.0, 5.0), (4.0, 20.0)]
Round 3 groups: [0, 0, 0, 1, 1, 1] centers: [(18.0, 5.0), (4.0, 20.0)]
```

In round 3 no member changed groups, so no center moved, and the loop stops: the early regulars around (18, 5), the big spenders around (4, 20). Neither step can make the members' total squared distance to their centers bigger (a member only moves to a nearer center, and the mean is the point with the smallest squared distances to its group), which is why the loop settles. scikit-learn's guide calls stopping here *convergence*: it repeats until the centers don't move significantly.

![Three panels side by side, one per round, each a small chart of the same six café members, visits across the bottom and spend up the side: in round 1 the two starting centers, drawn as stars, both sit among the three early regulars at the lower right, and lines join each member to its nearest star; in round 2 one star has moved up toward the big spenders, to (7, 16.5), the other to (19, 4.5), and the member at (16, 6) switches to the star at (19, 4.5); in round 3 the stars sit at (18, 5) and (4, 20), in the middle of each group of three, and nothing changes](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/f18ecab830384183be26f5b5bc53202e.webp)

## Different starts, different ends

k-means only improves from where it starts, so where it starts matters. Four members sit at the corners of a rectangle, and two runs start from different pairs of them:

```python
import math
from statistics import fmean


def k_means(members, centers):
    while True:
        groups = []
        for member in members:
            distances = [math.dist(member, center) for center in centers]
            groups.append(distances.index(min(distances)))
        new_centers = []
        for number in range(len(centers)):
            mine = [member for member, group in zip(members, groups) if group == number]
            new_centers.append((fmean(m[0] for m in mine), fmean(m[1] for m in mine)))
        if new_centers == centers:
            spread = sum(math.dist(member, centers[group]) ** 2 for member, group in zip(members, groups))
            return groups, centers, spread
        centers = new_centers


members = [(2, 8), (2, 12), (12, 8), (12, 12)]
print("Start A:", k_means(members, [(2, 8), (12, 8)]))
print("Start B:", k_means(members, [(2, 8), (2, 12)]))
```

```text
Start A: ([0, 0, 1, 1], [(2.0, 10.0), (12.0, 10.0)], 16.0)
Start B: ([0, 1, 0, 1], [(7.0, 8.0), (7.0, 12.0)], 100.0)
```

Start A splits the members by visits (left and right), and each member ends 2 from its center. Start B splits them by spend (bottom and top), each member 5 from its center, and it's stuck there: no single member is nearer the other center, so nothing moves. The last number is the total of each member's squared distance to its center, 4 × 2² = 16 against 4 × 5² = 100: smaller is tighter. Both runs stopped, but B's ending is worse. In your textbook, an ending that no small step improves but that isn't the best is a **local minimum**. scikit-learn's guide says k-means always converges, possibly to a local minimum, depending on the starting centers, so it's usually run from several starts, keeping the tightest. *k-means with scikit-learn* shows the setting that does it, and a smarter way to pick the starts.

## Do it: one round of k-means

You're grouping a few café members by hand, and you want a function that does one round of k-means: assign, then move.

The inputs:

- `points`: the members, each a pair `(visits, spend)`.
- `centers`: the current centers, each a pair `(visits, spend)`; center 0 is the first.

For example, with four members and two centers:

```python
points = [(10, 7), (12, 6), (3, 20), (5, 22)]
centers = [(10, 7), (3, 20)]
```

| Member | Distance to center 0, (10, 7) | Distance to center 1, (3, 20) | Nearest |
|---|---|---|---|
| (10, 7) | 0 | 14.76 | 0 |
| (12, 6) | 2.24 | 16.64 | 0 |
| (3, 20) | 14.76 | 0 | 1 |
| (5, 22) | 15.81 | 2.83 | 1 |

Center 0 moves to the mean of (10, 7) and (12, 6), which is (11, 6.5); center 1 moves to the mean of (3, 20) and (5, 22), which is (4, 21). So `one_round(points, centers)` returns `[(11.0, 6.5), (4.0, 21.0)]`.

**Your job:** write `one_round(points, centers)`.

- Give each point to its nearest center, by the straight-line distance (`math.dist` is fine).
- If a point is equally near two centers, give it to the one that comes first in `centers`.
- Return a list with one new center per old center, in the same order: each a pair, the mean visits and the mean spend of the points given to it.
- A center that no point was given to stays where it is.

Practiced live on the lesson page: write the Python right there and check it.

## Check yourself

2 questions to try on the lesson page.

## So what

k-means is two steps on repeat, nearest center, then the mean, until nothing moves; it always settles, but where it settles depends on where it started.

## Sources

- scikit-learn 1.9.1, [Clustering: K-means](https://scikit-learn.org/stable/modules/clustering.html#k-means), User Guide: the algorithm chooses initial centroids (most basically, k samples from the dataset), then loops between assigning each sample to its nearest centroid and creating new centroids from the mean of the samples assigned to each, until the centroids don't move significantly; given enough time it always converges, possibly to a local minimum that depends on the initial centroids, so it's often run several times with different initializations.
- scikit-learn 1.9.1, [KMeans](https://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html), API reference: in practice k-means is very fast but falls in local minima, which is why it can be useful to restart it several times.
- Python documentation, [math.dist](https://docs.python.org/3/library/math.html#math.dist): the Euclidean distance between two points; [statistics.fmean](https://docs.python.org/3/library/statistics.html#statistics.fmean): the arithmetic mean of the data, as a float.

## Key terms

- [K-Means Clustering](https://www.ask-codey.com/glossary/k-means-clustering)
- [Centroid](https://www.ask-codey.com/glossary/centroid)
- [Euclidean Distance](https://www.ask-codey.com/glossary/euclidean-distance)
- [Local Minimum](https://www.ask-codey.com/glossary/local-minimum)

## Related

- [Learning Without Labels](https://www.ask-codey.com/lessons/ml-unsupervised-learning)
- [k-means with scikit-learn](https://www.ask-codey.com/lessons/ml-k-means-with-scikit-learn)
- [Exercise: Café Regulars](https://www.ask-codey.com/lessons/exercise-ml-cafe-regulars)

Source: https://www.ask-codey.com/lessons/ml-how-k-means-works
