Cost Minimization Clustering Objectives
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…
Why a Clustering Needs a Score
A clustering is a collection of groups, but the groups still need to be judged. The k-Means objective supplies that judgment as a numerical score. It measures how far each data point is from the centroid of the cluster containing that point, using squared distances. The k-Means goal is to minimize the total score.
From Points to Total Cost
The evaluation follows a fixed sequence. First, divide the data into clusters. Next, determine the centroid of each cluster. Then pair every point with the centroid of its own cluster, calculate that point's distance to the centroid, square the distance, and add all the squared distances together. The resulting sum is the k-Means objective value for that partition.
For clusters C₁ through Cₖ with centroids μ₁ through μₖ, the objective is the sum of the squared distances from every point in each cluster Cᵢ to that cluster's centroid μᵢ. The notation emphasizes that a point is evaluated against the centroid of its own cluster, not automatically against one centroid for the entire dataset.
Finding a Cluster Centroid
A cluster centroid is the mean of all points in that cluster. The centroid therefore belongs to a particular cluster. If the data is divided into several clusters, each cluster receives its own centroid; the centroid of one cluster is not automatically the centroid of the complete dataset.
A centroid from three points
A one-dimensional cluster contains the points 2, 4, and 6. Determine its centroid and the cluster's sum of squared distances to that centroid.
- 1Calculate the mean
Add the points and divide by their count: (2 + 4 + 6) ÷ 3 = 4. The cluster centroid is 4.
- 2Measure each distance
The distances from the points to the centroid are 2, 0, and 2.
- 3Square and add
The squared distances are 4, 0, and 4. Their sum is 8.
The centroid is 4, and this cluster contributes 8 to the k-Means objective.
Tracing a Changed Partition
A partition is the division of the data into clusters. When points are reassigned, the affected clusters may receive new means. Those new centroids change the point-to-centroid distances, and the squared contributions may change the total objective. The objective is therefore evaluated again for each candidate partition rather than being treated as a permanent property of the data alone.
Comparing two partitions
Evaluate two partitions of the one-dimensional points 1, 2, 7, and 8. Partition A is {1, 2} and {7, 8}. Partition B is {1, 7} and {2, 8}.
- 1Evaluate Partition A
The centroids are 1.5 for {1, 2} and 7.5 for {7, 8}. Each point is 0.5 from its assigned centroid, so each squared contribution is 0.25. The total objective is 0.25 + 0.25 + 0.25 + 0.25 = 1.
- 2Evaluate Partition B
The centroids are 4 for {1, 7} and 5 for {2, 8}. Each point is 3 from its assigned centroid, so each squared contribution is 9. The total objective is 9 + 9 + 9 + 9 = 36.
- 3Compare the totals
The two partitions use the same data and the same number of clusters, but their memberships produce different centroids and different squared-distance totals.
Partition A has objective 1, while Partition B has objective 36. Under the k-Means minimization objective, Partition A has the smaller score.
Function Versus Partition
The objective function is the general scoring rule: assign each point to its cluster centroid, square the distance, and sum the results. A particular partition is one candidate division of the data into clusters. To evaluate that partition, calculate its centroids and apply the general rule. Thus, the function is the method of scoring, while the partition is the specific arrangement being scored.
| Item | Role |
|---|---|
| Objective function | The general rule for calculating total squared distance |
| Partition | The particular grouping of points submitted to that rule |
| Centroids | The means determined separately for the clusters in that partition |
| Objective value | The numerical result produced after evaluating that partition |
Keep the scoring rule separate from the candidate clustering it evaluates.
Mistakes in Cost Evaluation
Common mistake Using one centroid for the entire dataset automatically
What it looks likeTreating all points as if they must be compared with one overall mean even when the data has several clusters
Why it failsEach cluster has its own centroid, and a point is compared with the centroid of the cluster to which it belongs.
Do this insteadDetermine the mean separately for every cluster in the partition.
Common mistake Adding distances without squaring them
What it looks likeAdding 2, 0, and 2 as the contribution of the cluster {2, 4, 6}
Why it failsThe k-Means objective uses squared distances, not unsquared distances.
Do this insteadSquare each point-to-centroid distance before adding the contributions.
Common mistake Changing memberships without recalculating affected centroids
What it looks likeMoving a point to another cluster but continuing to use the old cluster means
Why it failsA changed partition can produce a different set of cluster means.
Do this insteadAfter changing the partition, recompute the relevant cluster centroids and then reevaluate the squared distances.
Common mistake Confusing the objective function with one objective value
What it looks likeCalling the value 1 the objective function rather than the result for Partition A
Why it failsThe objective function is the general scoring rule; 1 is the value obtained when that rule evaluates a particular partition.
Do this insteadDescribe the rule separately from the partition and its computed score.
Evaluate a Candidate Partition
A one-dimensional cluster contains the points 3, 5, and 10. Determine its centroid and its contribution to the k-Means objective. Show the distance from each point to the centroid, square each distance, and add the squared values.
Hints
- Find the mean by adding the three points and dividing by 3.
- Pair every point with that cluster's centroid.
- Square the distances before adding them.
What do you think happens?
If a point is reassigned to another cluster, can the objective value remain unchanged?
Reveal answer
Yes, it can remain unchanged, although it can also change.
The source establishes that changing a partition can change the centroids, squared-distance contributions, and total objective. It does not state that every possible partition change must produce a different numerical total.
Key Takeaways
- 1The k-Means objective is the sum of squared distances from every point to the centroid of its assigned cluster.
- 2Each cluster centroid is the mean of the points in that cluster.
- 3Evaluating a partition requires finding its centroids, calculating point-to-centroid distances, squaring them, and summing the results.
- 4Changing a partition can change the centroids, individual contributions, and total objective value.
- 5The objective function is the general scoring rule; an objective value is the result of applying that rule to one particular partition.
At a glance
- k-Means judges a partition by summing squared distances from points to their assigned cluster centroids.
- A cluster centroid is the mean of the points assigned to that cluster.
- Reassigning points can alter centroids and therefore alter the total objective.
- The objective function is the scoring rule, while a partition is a candidate grouping evaluated by that rule.