Suppose each recorded signal has been turned into a feature vector. We want to group vectors that lie near one another, without being given the correct group labels in advance. A centroid-based method represents each group by a center and assigns observations according to their distances from those centers. This sounds simple, but the choice of distance, the meaning of a center and the criterion being improved all need to be stated.
For k-means, the criterion is the total squared Euclidean distance from each observation to its assigned center. The usual iteration alternates between two problems that are easy separately: choose labels for fixed centers, then choose centers for fixed labels. Their combination does not increase the criterion, but does not automatically solve the joint optimization problem globally.
State the data and the objective
Definition 1.1.1
(Assignments, centers and squared-error objective)
Let be fixed observations, with , and choose centers . An assignment gives observation to one group. Define
The group contains the indices assigned to . These assignment labels are computed by the algorithm; they are not supplied correct class labels. A center need not be one of the observations.
The square is part of the model, not a harmless formatting choice. Minimizing squared distances gives means as centers. Replacing squared distance by another loss can require a different update, so the word “center” alone does not determine the algorithm.
One iteration uses these rules:
- For fixed centers, give each observation to a nearest center. If distances tie, choose the lower center index.
- For each nonempty group, replace its center by the arithmetic mean of its members.
- For an empty group, retain its previous center in the examples here. Repeat assignment and update until the chosen stopping condition is met.
The empty-group rule is an explicit policy: an empty group's mean is undefined, and silently treating it as zero would introduce an unrelated position into the feature space. Keeping the old center is not the only possible policy, but it makes the procedure specified.
Why the arithmetic mean is the correct update
Proposition 1.1.2
(Squared error about a center)
Let with , and let . Then for every
Consequently is the unique minimizer of .
Proof
(Expand around the mean)
Write and expand the squared length. The cross term is , and it vanishes because . This leaves the stated identity. The first term does not depend on ; the second is nonnegative and, since , is zero exactly when . Hence the mean is the unique minimizer for this fixed nonempty group.
Proof X-ray
Where the identity uses the group, and where it stops
The one non-routine move is to insert between and . It is chosen because it turns the cross term into an inner product against , which is zero by the definition of ; any other intermediate point would leave a cross term that still depends on .
Nonemptiness is used twice: to define at all, and to make the coefficient positive, which is what gives uniqueness. The identity also prices a misplaced center exactly: the extra loss grows with the group size and with the squared displacement.
The cancellation depends on squared Euclidean loss. For unsquared distances there is no such identity, and the minimizer need not be the mean: in one dimension, has absolute-deviation sum at but at the mean . An empty group has no and no positive coefficient, which is why it needs its own policy.
For fixed centers, the assignment rule also has a direct justification. Each observation contributes one term to , independently of the other assignment choices. Choosing a center with the smallest squared distance minimizes that term. The mean update then minimizes each nonempty group's contribution with those assignments held fixed.
Concept lensAlgebraic
The objective without any centers
For a group of size , the mean identity gives . Thus each group contributes the sum of its squared distances over unordered pairs, divided by its size, and k-means seeks groups whose members are mutually close. Check with : the pairwise squares sum to over unordered pairs, and is the within-group error.
Trace two alternating rounds with exact values
Worked example 1.1.3
(Assignments can move after the centers are updated)
Use one-dimensional observations and two initial centers and . The groups in the table list observation values, not their indices. For two distinct centers on a line, their midpoint separates the nearest-center regions. Initially that boundary is , so only observation 0 belongs to the first group.
| Stage | Centers | First group | Second group | Objective |
|---|---|---|---|---|
| First assignment | ||||
| First mean update | ||||
| Second assignment | ||||
| Second mean update |
For the first row, the nonzero squared errors are . The second group's mean is , reducing its fixed-membership error to .
That update moves the boundary to . Observations 2 and 3 are now closer to the first center, so the next assignment changes the groups and gives . Their new means are and . The final within-group error is
The new boundary is , between 3 and 10, so a further assignment leaves both groups unchanged. Updating their means again changes nothing. This example has reached a fixed point. The table distinguishes assignment and update because they change different variables; one recorded objective should not mix old labels with an unreported set of new centers.
Worked example 1.1.4
(A distance tie, resolved by the lower-index rule)
Take observations and initial centers and . Observation 1 has squared distance from both centers, so the stated rule gives it to the first group.
| Stage | Centers | First group | Second group | Objective |
|---|---|---|---|---|
| First assignment | ||||
| Mean update |
The first group's mean is , and a singleton group's mean is its own member, so the second center stays at . The boundary is now ; observation 1 is at distance from the first center and from the second, so no label changes and the state is a fixed point with .
Had the tie been resolved the other way, the groups would be and with , then centers with , boundary , and again no change. The two runs end at different fixed points with the same objective. A tie rule is therefore part of the specification of a reproducible run.
Worked example 1.1.5
(Two groups in the plane)
Take with initial centers and . The squared distances from the four observations to the centers are , , and . The first observation therefore stays with the first center and the other three go to the second, giving .
| Stage | Centers | First group | Second group | Objective |
|---|---|---|---|---|
| First assignment | ||||
| First mean update | same | same | ||
| Second assignment | ||||
| Second mean update | same | same |
The second group's mean is . Its fixed-membership error falls by , from to . At the new centers, the squared distances to the nearest center are for the four observations, so switches group and . The new means are and , and every observation is at squared distance from its center, so . A further assignment keeps every label, so this is a fixed point. The singleton group in the first round has zero error and its center does not move.
What descent proves, and what it does not
Theorem 1.1.6
(A Lloyd round does not increase the objective)
Let be an assignment and a list of centers. A round gives each observation to a nearest center of (with any rule for ties), producing , then replaces the center of each nonempty group by its mean and keeps the center of each empty group, producing . Then
so does not increase during a round, and .
Suppose in addition that the centers begin as the means of the groups of , the arithmetic is exact, no distance ties occur and no group is empty. Then the assignment stops changing after finitely many rounds.
Proof
(Two half-steps, then strict descent)
The first inequality follows point by point from nearest-center assignment: each observation contributes one term to , and its new term is the smallest available. The second follows group by group from the mean identity; an empty group contributes zero, so retaining its old center cannot increase its contribution.
For finite termination, suppose an assignment changes. At least one observation moves to a strictly nearer center, so the first inequality is strict. After each update the means are determined by the assignment, so, writing for the group means of , the value depends only on and strictly decreases while assignments change. The same assignment therefore cannot recur. There are only labeled assignments, so the assignment eventually stops changing, after which its means also stay fixed.
Proof X-ray
What each inequality uses, and what the argument leaves open
The first inequality uses only that is a sum of independent terms, one per observation, so changing labels with the centers fixed can be done term by term. The second uses the mean identity for each nonempty group with the labels fixed. The two half-steps change different variables, which is why neither can undo the other.
Strictness is the delicate hypothesis. With a distance tie an observation may change label at equal distance, so only is available and the finiteness argument above does not apply; the nonincrease claim still does. Exactness is also needed, since rounding could break the equality that the mean identity delivers.
The argument closes by a counting step: a strictly decreasing sequence of values attached to a finite set of assignments must stop. It concludes that the iteration stops, and says nothing about how the final value compares with other clusterings.
The guarantee concerns the value of along the iteration, not the quality of the limit.
Counterexample mode
A stable clustering can have a worse objective
Use a different dataset: , with centers and . The midpoint is , so nearest-center assignment gives groups and . Their means are exactly those same centers, making this a fixed point with no distance ties.
Its objective is
But the alternative groups and have means and and objective
Because , the fixed point is not globally optimal. We do not need to prove that 87 is itself the global minimum to refute the claim that every fixed point is globally best. Initial centers can therefore affect the result; an unchanged assignment is a stopping condition, not a certificate of global optimality.
The stepper follows the exact worked and stable-but-worse examples above. Its empty-cluster scenario continues beyond the first round of Exercise 2 below: a cluster without assigned points has no mean, and this example keeps its previous center by explicit convention.
Common mistake
(A smaller objective does not select a better number of groups)
The smallest attainable value of does not increase when grows, because an extra center can always be placed where it is not needed. Comparing across different and choosing the smallest therefore selects the largest . For the observations , taking gives every observation its own center and , although nothing about the data has been learned. Objective values compare runs with the same , such as the two clusterings with and above; a choice of needs a different criterion.
Feature units change the geometry being optimized
Counterexample mode
A unit conversion can reverse a nearest-center decision
Take observation and fixed centers and . Their squared distances from are 9 and 16, so the nearest center is .
Now multiply the second feature by 10 for every observation and center, leaving the first feature unchanged. The same records have coordinates , and . The squared distances are now 900 and 16, and the chosen center is .
Unweighted Euclidean distance in the new coordinates is a different weighting of the old features. If coordinate is scaled by , its contribution becomes . Preprocessing is therefore part of the clustering model. Scaling may be appropriate when comparing features with different units, but it should express which differences matter for the task, rather than be described as leaving the objective unchanged.
Reproduce the calculation without rounding
This one-dimensional Python example uses rational numbers to reproduce the table exactly. The implementation uses center indices 0 and 1 for the first and second groups. assign breaks distance ties by index, and update keeps an old center if its group is empty.
from fractions import Fraction as F
def assign(points, centers):
return [
min(range(len(centers)), key=lambda j: ((x - centers[j]) ** 2, j))
for x in points
]
def update(points, labels, old_centers):
result = []
for j, old in enumerate(old_centers):
group = [x for x, label in zip(points, labels) if label == j]
result.append(sum(group) / len(group) if group else old)
return result
def objective(points, labels, centers):
return sum((x - centers[label]) ** 2 for x, label in zip(points, labels))
points = list(map(F, [0, 2, 3, 10, 11]))
centers = [F(0), F(3)]
for _ in range(2):
labels = assign(points, centers)
print("assignment", objective(points, labels, centers))
centers = update(points, labels, centers)
print("update", objective(points, labels, centers))
assert assign(points, centers) == labels
The four printed objective values are 114, 65, 91/2 and 31/6. Two rounds suffice for these chosen data and initial centers; that fixed round count is not a general stopping rule. The final assertion checks that another assignment would be unchanged. To study a different example, follow assignments, centers and objective together, and identify which half-step changed each quantity.
Exercises
Quick check
(1. Quantify the cost of a displaced center)
A fixed group has values . Find its mean and minimum sum of squared errors. Use the mean identity to find the error at center 5 without recomputing all three squared distances separately.
Solution · Solution 1
The mean is 4 and the minimum error is . Moving the center to 5 adds , so the new error is . The group's members are held fixed during this comparison.
Quick check
(2. Separate a tie policy from an averaging formula)
For observations and initial centers , use the stated lower-index tie rule. What are the first labels and the next centers? Why is the second center not the mean of an empty group?
Solution · Solution 2
Both observations choose center index 0. That group's mean is 1, while group index 1 is empty and retains its old center 0. Thus the next centers are . Retaining 0 follows the explicit policy; an empty-group mean has not been defined as 0.
Quick check
(3. Test a global-optimality claim with the right evidence)
An implementation reports an unchanged assignment and a nonincreasing objective. Does that establish global optimality? In the counterexample above, what is sufficient evidence to disprove global optimality of the fixed point, and what stronger claim has not been proved?
Solution · Solution 3
No. The fixed point with objective 127 satisfies both observations. Producing a valid clustering with objective 87 is enough to show that 127 is not globally minimal. It does not by itself establish that 87 is the best possible objective; that would require ruling out all better clusterings.
Quick check
(4. Predict the effect of changing a feature's scale)
If one feature is multiplied by 100 for all observations and centers, by what factor is that feature's contribution to squared Euclidean distance multiplied? Does a common positive scaling of every feature preserve nearest-center decisions, and why is that different from scaling just one feature?
Solution · Solution 4
The selected feature's contribution is multiplied by . Scaling every feature by the same positive factor multiplies every squared distance by the same positive constant, so nearest-center comparisons, including ties, are unchanged when centers are scaled too. Scaling only one feature changes its weight relative to the others and can reverse a comparison, as the two-dimensional example shows.