Distance Measures in Clustering
The k-Means objective measures the sum of squared distances from each point to the centroid of its cluster.
From Groups to a Score
A clustering is not only a collection of groups. It also needs a way to judge whether those groups represent the data well. The k-Means objective function provides that score. It measures the squared distance from every data point to the centroid of the cluster containing that point, then adds those squared distances together. The k-Means goal is to minimize this total.
The k-Means objective is the sum of squared distances from every point to the centroid of its own cluster. If the clusters are C_1 through C_k and their centroids are μ_1 through μ_k, the distance for a point x in cluster C_i is measured to μ_i, not automatically to a centroid for the entire dataset.
Centroids from Assigned Points
A centroid belongs to a particular cluster. It is the mean of all points assigned to that cluster. Therefore, the centroid cannot be determined independently of the partition: first identify which points belong to the cluster, then calculate the mean of those points. Each cluster has its own centroid.
Finding a Cluster Centroid
Suppose one cluster contains the one-dimensional points 2, 4, and 6. Determine its centroid.
Identify the assigned points: The cluster contains 2, 4, and 6.
Calculate their mean: Add the points and divide by the number of points: (2 + 4 + 6) / 3 = 4.
Assign the centroid: The centroid of this cluster is 4.
The cluster centroid is 4.
Evaluating One Partition
To evaluate a partition, follow the same sequence every time. Identify each cluster, calculate its mean, pair every point with the centroid of its own cluster, calculate each point-to-centroid distance, square those distances, and add all contributions. The resulting total is the objective value for that partition.
Computing a Partition's Objective
Use the partition C_1 = {2, 4} and C_2 = {10, 12}. Calculate the centroids and the total squared-distance objective.
Calculate the first centroid: The mean of C_1 is (2 + 4) / 2 = 3.
Calculate the second centroid: The mean of C_2 is (10 + 12) / 2 = 11.
Calculate contributions for C_1: The distances to 3 are 1 and 1. Their squared contributions are 1 and 1, giving a subtotal of 2.
Calculate contributions for C_2: The distances to 11 are 1 and 1. Their squared contributions are 1 and 1, giving a subtotal of 2.
Combine the subtotals: Add the contributions from both clusters: 2 + 2 = 4.
The objective value for this partition is 4.
Changing the Partition
A partition determines which points are grouped together. If points are reassigned, the cluster means may change. Once the means change, the point-to-centroid distances and their squared contributions may change as well. The objective must then be recomputed for the new partition; it is not carried over from the old grouping.
Function Versus Partition
The objective function is the evaluation rule: pair every point with the centroid of its own cluster, square each distance, and add the results. A partition is one particular assignment of points to clusters. The same objective function can evaluate many different partitions. Each partition can produce different centroids, contributions, and total objective values.
| Item | What it represents | What can change |
|---|---|---|
| Objective function | The rule for summing squared point-to-centroid distances | The rule itself remains the common basis for evaluation |
| Partition | A particular division of the data into clusters | Point assignments, cluster centroids, contributions, and total value |
| Objective value | The number produced when the function evaluates a partition | The value can differ between partitions |
Checking Your Reasoning
A cluster contains the one-dimensional points 1, 5, and 9. Determine its centroid, then calculate the sum of squared distances from those points to the centroid.
Hints
- Start by calculating the mean of 1, 5, and 9.
- Pair every point with that mean.
- Square each distance before adding the contributions.
Using one centroid for every cluster
The k-Means objective pairs each point with the centroid of the cluster containing that point.
Fix:
Determine a separate mean for each cluster and use that cluster's centroid for its points.Adding distances without squaring them
The k-Means objective uses squared distances.
Fix:
Calculate each distance, square it, and then add the squared contributions.Keeping the old centroid after changing a partition
Changing a partition can change the cluster centroids and therefore the contributions.
Fix:
Recalculate the affected cluster means and then recompute the objective.Confusing the objective function with one objective value
The function is the evaluation rule; the value is the result for a particular partition.
Fix:
Describe the partition separately from the rule used to evaluate it.
Key Takeaways
- The k-Means objective is the sum of squared distances from each point to the centroid of its own cluster.
- A cluster centroid is the mean of the points assigned to that cluster.
- Evaluating a partition requires finding centroids, pairing points with their own centroids, squaring distances, and summing the contributions.
- Changing a partition can change centroids, squared-distance contributions, and the total objective value.
- The objective function is the common evaluation rule, while a partition is one candidate grouping evaluated by that rule.
Key Takeaways
- The k-Means objective measures the total of squared distances from points to their assigned cluster centroids.
- Each cluster centroid is the mean of the points in that cluster.
- A new partition requires new centroid and contribution calculations because reassignment can change the objective value.
- The objective function is the scoring rule, whereas a partition is a particular grouping that receives a score.
- Because k-Means minimizes the objective, a smaller sum of squared distances is preferred.