Cost Minimization Clustering Objectives
The k-Means objective measures the sum of squared distances from each point to the centroid of its cluster.
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.
Calculate the mean: Add the points and divide by their count: (2 + 4 + 6) ÷ 3 = 4. The cluster centroid is 4.
Measure each distance: The distances from the points to the centroid are 2, 0, and 2.
Square 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}.
Evaluate 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.
Evaluate 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.
Compare 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 |
Mistakes in Cost Evaluation
Using one centroid for the entire dataset automatically
Each cluster has its own centroid, and a point is compared with the centroid of the cluster to which it belongs.
Fix:
Determine the mean separately for every cluster in the partition.Adding distances without squaring them
The k-Means objective uses squared distances, not unsquared distances.
Fix:
Square each point-to-centroid distance before adding the contributions.Changing memberships without recalculating affected centroids
A changed partition can produce a different set of cluster means.
Fix:
After changing the partition, recompute the relevant cluster centroids and then reevaluate the squared distances.Confusing the objective function with one objective value
The objective function is the general scoring rule; 1 is the value obtained when that rule evaluates a particular partition.
Fix:
Describe 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
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
- The k-Means objective is the sum of squared distances from every point to the centroid of its assigned cluster.
- Each cluster centroid is the mean of the points in that cluster.
- Evaluating a partition requires finding its centroids, calculating point-to-centroid distances, squaring them, and summing the results.
- Changing a partition can change the centroids, individual contributions, and total objective value.
- The objective function is the general scoring rule; an objective value is the result of applying that rule to one particular partition.
Key Takeaways
- 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.