Centroids and Cluster Representatives
The k-Means objective measures the sum of squared distances from each point to the centroid of its cluster.
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
Objective = sum over every cluster C_i and every point x in C_i of d(x, μ_i)^2Here, 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.
Identify the cluster: The assigned cluster is the group containing 2, 4, and 6.
Calculate the mean: The centroid is the mean of the points in the cluster: (2 + 4 + 6) divided by 3, which is 4.
Pair points with the centroid: Each point is evaluated against 4 because 4 is the centroid of its own cluster.
Form 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.
Combine 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.
Evaluate 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.
Evaluate 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.
Interpret 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
- Identify the points assigned to each cluster.
- Calculate the mean of the points in each cluster to obtain its centroid.
- For every point, use the centroid of the cluster containing that point.
- Calculate each point-to-centroid distance.
- Square each distance.
- Add the squared contributions across every cluster.
Common Evaluation Errors
Using one centroid for the entire dataset automatically.
Each cluster has its own centroid, and each point must be compared with the centroid of its own cluster.
Fix:
Compute a separate mean for every cluster and use the matching centroid for each point.Adding ordinary distances instead of squared distances.
The k-Means objective is defined using squared distances.
Fix:
Square every point-to-centroid distance before adding the contributions.Treating a partition as if it were the objective function.
The grouping is the candidate partition; the objective is the numerical score produced after evaluating it.
Fix:
Describe the partition first, then calculate its centroids and objective value.Assuming that changing a partition changes only group labels.
A different partition produces a different set of cluster means, which can change point-to-centroid distances and the total objective.
Fix:
Recompute 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.