Centroids and Cluster Representatives
The k-Means objective measures the sum of squared distances from each point to the centroid of its cluster.
Try it: k-Means (Lloyd's Algorithm)
How Lloyd's algorithm lowers the k-means objective (the sum of squared distances from each point to its cluster's centroid) by alternating nearest-centroid assignment and mean updates, and why a different start can end in a different local optimum.
How it works
- Place K initial centroids.
- Assignment: send every point to its nearest centroid (squared Euclidean distance; a tie goes to the lower-numbered centroid).
- Update: move every centroid to the mean of the points assigned to it (a centroid with no points stays where it is).
- Recompute the objective after each step — neither step can increase it.
- Stop when an assignment step changes nothing; the result is a local optimum that depends on the initial centroids.
Default run (8 steps): 12 points, K = 3. Initial centroids: c1 (1, 1), c2 (1.5, 2), c3 (9, 9). … Iteration 4, assignment: no point changes cluster, so the centroids would not move either. Lloyd's algorithm has converged with cost 7.9375.
Simplified: Toy 2-D data (3–16 points on a 0–10 board, K = 2–5). Lloyd's algorithm is a heuristic: it is not guaranteed to reach the minimum-cost clustering, and real data has many more points and dimensions.
Loading the simulation…
A Score for a Clustering
A clustering is more than a collection of groups. We also need a way to judge how well those groups represent the data. The k-Means objective supplies that score. It measures the squared distance from every data point to the centroid of the cluster containing that point, then adds all of those contributions. The k-Means goal is to minimize this total.
The important chain is: choose a partition, compute one centroid for each cluster, pair every point with its own cluster's centroid, square each distance, and add the results. A change to the partition can change every stage after the first one: the centroids may move, individual squared-distance contributions may change, and the total objective may become larger or smaller.
From Points to One Objective Value
Here, C_i names one cluster, μ_i is that cluster's centroid, and d(x, μ_i) is the distance from point x to that centroid. The square is applied to the distance before the contributions are added. Each point is paired with the centroid of its own cluster, not with one automatically chosen centroid for the entire dataset.
Finding a Cluster Centroid
A cluster centroid is the mean of all points assigned to that cluster. Each cluster has its own centroid. The centroid belongs to the cluster representation; it is not automatically the centroid of the entire dataset.
A Mean Represents One Cluster
Suppose one cluster contains the one-dimensional points 2, 4, and 6. Determine its centroid and describe the objective contributions.
- 1Identify the cluster
The assigned cluster is the group containing 2, 4, and 6.
- 2Calculate the mean
The centroid is the mean of the points in the cluster: (2 + 4 + 6) divided by 3, which is 4.
- 3Pair points with the centroid
Each point is evaluated against 4 because 4 is the centroid of its own cluster.
- 4Form the contributions
The distances from the points to 4 are 2, 0, and 2. The objective uses their squared distances, so the contributions are 4, 0, and 4.
- 5Combine the contributions
Adding the squared-distance contributions gives 8 for this cluster.
The cluster centroid is 4, and this cluster contributes 8 to the total k-Means objective.
When the Partition Changes
The objective function itself does not change when we compare candidate clusterings. What changes is the partition supplied to that function. A new partition can assign points to different clusters. That changes which points are averaged together, so it can change the cluster centroids. Because the point-to-centroid pairings then change, the squared-distance contributions and total objective can change as well.
Comparing Two Partitions
Use the points 2, 4, and 6 to compare two possible one-dimensional partitions into two clusters. Partition A assigns {2, 4} to one cluster and {6} to the other. Partition B assigns {2} to one cluster and {4, 6} to the other.
- 1Evaluate Partition A
The centroid of {2, 4} is 3, and the centroid of {6} is 6. The squared-distance contributions are 1 and 1 for the first cluster, and 0 for the second cluster. The total objective is 2.
- 2Evaluate Partition B
The centroid of {2} is 2, and the centroid of {4, 6} is 5. The squared-distance contributions are 0 for the first cluster, and 1 and 1 for the second cluster. The total objective is also 2.
- 3Interpret the comparison
The partitions are different, and their cluster centroids are different, but these particular partitions produce the same total objective value.
The same objective function can evaluate different partitions. It produces a value for each partition, and the values need not always differ.
Evaluation Checklist
- 1Identify the points assigned to each cluster.
- 2Calculate the mean of the points in each cluster to obtain its centroid.
- 3For every point, use the centroid of the cluster containing that point.
- 4Calculate each point-to-centroid distance.
- 5Square each distance.
- 6Add the squared contributions across every cluster.
Common Evaluation Errors
Common mistake Using one centroid for the entire dataset automatically.
What it looks likeComparing every point with one overall mean even though the data has been divided into several clusters.
Why it failsEach cluster has its own centroid, and each point must be compared with the centroid of its own cluster.
Do this insteadCompute a separate mean for every cluster and use the matching centroid for each point.
Common mistake Adding ordinary distances instead of squared distances.
What it looks likeSumming d(x, μ_i) rather than summing d(x, μ_i)^2.Why it failsThe k-Means objective is defined using squared distances.
Do this insteadSquare every point-to-centroid distance before adding the contributions.
Common mistake Treating a partition as if it were the objective function.
What it looks likeCalling a grouping of points the objective value.
Why it failsThe grouping is the candidate partition; the objective is the numerical score produced after evaluating it.
Do this insteadDescribe the partition first, then calculate its centroids and objective value.
Common mistake Assuming that changing a partition changes only group labels.
What it looks likeReassigning a point but keeping the old centroid without recomputing the cluster means.
Why it failsA different partition produces a different set of cluster means, which can change point-to-centroid distances and the total objective.
Do this insteadRecompute the affected cluster centroids before evaluating the new partition.
Check Your Understanding
A cluster contains the one-dimensional points 1, 3, and 8. Find its centroid, calculate each squared distance to that centroid, and add the contributions. Then explain what would need to be recomputed if the point 8 were moved to another cluster.
Hints
- Begin by calculating the mean of 1, 3, and 8.
- Pair every point with that cluster's centroid.
- Square each distance before adding.
- If the partition changes, reconsider the means of the affected clusters.
Key Takeaways
- The k-Means objective is the sum of squared distances from each point to the centroid of its assigned cluster.
- A cluster centroid is the mean of all points in that cluster.
- Changing a partition can change the cluster means, point contributions, and total objective value.
- The objective function is the scoring rule; a partition is the particular grouping being scored.
- To evaluate a partition, compute cluster means, pair each point with its own mean, square the distances, and add them.