Lesson 4 of 10

Move Centers with K-Means

K-means chooses K groups in advance and searches for their centers. Standard K-means minimizes the sum of squared Euclidean distances between points and assigned centers.

Alternate assignment and update

1. Choose K initial centers.
2. Assign each point to its closest center.
3. Replace each center with the mean of its assigned points.
4. Repeat until assignments or centers change little.

values = [1, 2, 8, 9]
centers = [1, 9]
for _ in range(20):
    groups = [[], []]
    for value in values:
        closest = min(range(2), key=lambda i: (value - centers[i]) ** 2)
        groups[closest].append(value)
    updated = [sum(g) / len(g) if g else centers[i]
               for i, g in enumerate(groups)]
    if updated == centers:
        break
    centers = updated
print(centers)

The result is [1.5, 8.5], grouping 1 with 2 and 8 with 9. This example retains an old center for an empty group and limits execution to 20 iterations. Practical implementations need explicit tolerances and empty-cluster handling.

Match distance and center rules

The mean minimizes squared Euclidean distance. Manhattan-distance objectives instead lead to median-based methods such as K-medians. Changing the distance while claiming the same objective can make the explanation inconsistent.

Initialization can lead K-means to different local minima. Elongated groups or varying densities may also yield unexpected clusters.

Check your understanding

If K equals the number of data points and every point becomes its own center, what is the squared-distance sum? Is that always useful clustering?