Distance Measures in Clustering

The k-Means objective measures the sum of squared distances from each point to the centroid of its cluster.

Programming

Interactive lab

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.

Educational simulation

Loading the simulation…

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.

Definition

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.

How does each point contribute its squared distance to its cluster centroid, and how are those contributions combined into the objective?

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.

Worked example

Finding a Cluster Centroid

Suppose one cluster contains the one-dimensional points 2, 4, and 6. Determine its centroid.

1
Identify the assigned points
The cluster contains 2, 4, and 6.
2
Calculate their mean
Add the points and divide by the number of points: (2 + 4 + 6) / 3 = 4.
3
Assign the centroid
The centroid of this cluster is 4.

Result

The cluster centroid is 4.

How do the points assigned to a cluster determine the location of its centroid?

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.

Worked example

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.

1
Calculate the first centroid
The mean of C_1 is (2 + 4) / 2 = 3.
2
Calculate the second centroid
The mean of C_2 is (10 + 12) / 2 = 11.
3
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.
4
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.
5
Combine the subtotals
Add the contributions from both clusters: 2 + 2 = 4.

Result

The objective value for this partition is 4.

What sequence turns a chosen partition into one k-Means objective value?

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.

Before

Partition A: C_1 = {2, 4}, C_2 = {10, 12} Centroids: 3 and 11 Objective: 4

Each cluster contains nearby points; the total squared-distance objective is 4.

After

Partition B: C_1 = {2, 4, 10}, C_2 = {12} Centroids: 16/3 and 12 Objective: 128/3

One cluster contains the reassigned point 10, changing its centroid and increasing the total objective to 128/3.

What happens to the total squared-distance objective when points are reassigned to different clusters?

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

The objective function is the measuring rule; a partition is one candidate grouping that the rule evaluates.

How can the same objective function evaluate different partitions and produce different objective values?

Checking Your Reasoning

EASY

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.

Your attempt (not saved)

Common mistake
Using one centroid for every cluster
What it looks like
Comparing every point with a single overall center instead of the centroid of its assigned cluster.
Why it fails
The k-Means objective pairs each point with the centroid of the cluster containing that point.
Do this instead
Determine a separate mean for each cluster and use that cluster's centroid for its points.
Common mistake
Adding distances without squaring them
What it looks like
Adding point-to-centroid distances directly.
Why it fails
The k-Means objective uses squared distances.
Do this instead
Calculate each distance, square it, and then add the squared contributions.
Common mistake
Keeping the old centroid after changing a partition
What it looks like
Moving a point to another cluster but continuing to use the old cluster means.
Why it fails
Changing a partition can change the cluster centroids and therefore the contributions.
Do this instead
Recalculate the affected cluster means and then recompute the objective.
Common mistake
Confusing the objective function with one objective value
What it looks like
Treating the total for one partition as if it were the objective function itself.
Why it fails
The function is the evaluation rule; the value is the result for a particular partition.
Do this instead
Describe the partition separately from the rule used to evaluate it.

Key Takeaways

1
The k-Means objective is the sum of squared distances from each point to the centroid of its own cluster.
2
A cluster centroid is the mean of the points assigned to that cluster.
3
Evaluating a partition requires finding centroids, pairing points with their own centroids, squaring distances, and summing the contributions.
4
Changing a partition can change centroids, squared-distance contributions, and the total objective value.
5
The objective function is the common evaluation rule, while a partition is one candidate grouping evaluated by that rule.

At a glance

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.

More concepts starting with D