Clustering and principal components

Prerequisites: Vectors, distances, means, and variance.

Learning objectives

• Perform a k-means assignment and update.
• Interpret a principal direction.
• Explain sensitivity to scale and initialization.

Unsupervised does not mean assumption-free

K-means represents each example by a vector and chooses k centers to minimize the sum of squared Euclidean distances from examples to their assigned centers. The algorithm alternates between assigning each example to its nearest center and replacing each center with the mean of its assigned examples. Nearest-center assignment and replacing each nonempty cluster’s center by its mean cannot increase the objective. An empty center has no assigned contribution; its handling must preserve that guarantee. The procedure can still stop at a local optimum.

For points 0, 2, 8, and 10 on a line, start with centers 0 and 8. The first two points join the first center, and the last two join the second. Updating gives centers 1 and 9. The squared-error objective is 1+1+1+1=4. The next assignments are unchanged, so this run has converged.

Choosing k is part of the modeling decision. More centers cannot worsen the optimal training objective; that fact alone cannot justify a larger k. Evaluate whether the grouping is stable, useful for a specified task, and appropriate for the data geometry. Elongated or unequal-density groups need not match the partitions preferred by Euclidean k-means.

Principal components choose directions

Principal component analysis centers the data and finds orthogonal directions that explain decreasing amounts of variance. Projecting onto the first r directions gives the best rank-r reconstruction under squared Euclidean error, with the usual centered-data formulation. This is a geometric statement about reconstruction, not a promise that the retained directions are the best predictors of a label.

For centered two-dimensional points lying on the line y=x, the first principal direction is proportional to (1,1). Projection onto that direction preserves the variation along the line. Projection onto (1,-1) gives zero for every point. Noise or rescaling a feature, such as converting meters to millimeters changes the covariance structure and can change which direction dominates. Changing only the origin does not change covariance after centering.

Representation determines the result

If one feature is annual income measured in currency units and another is age in years, raw distances may be dominated by income. Standardization can change that, but it also makes a substantive choice about relative importance. A categorical identifier encoded as an integer usually should not be interpreted as a meaningful Euclidean distance.

Neither a cluster nor a high-variance component is automatically a real social category or causal factor. Name the objective, inspect representative examples, test stability, and document preprocessing. When an unsupervised transform is part of a predictive pipeline, fit it on training data only and apply the fitted transform to held-out observations.

Practice problem

Run one k-means iteration on 1, 3, 9, 11 with initial centers 1 and 11. Compute the updated centers and squared error. Explain why adding a customer identifier as a numeric feature could invalidate the interpretation.

Worked solution

The assignments are {1,3} and {9,11}; their means are 2 and 10. The squared error is (1-2)²+(3-2)²+(9-10)²+(11-10)²=4. An arbitrary customer number has no justified distance geometry: identifiers 100 and 101 need not represent more similar people than 100 and 900. Its numeric magnitude can dominate the distance while encoding only an administrative ordering. Remove such identifiers or replace them with features whose distances have a defensible meaning.

Check your understanding

What does a decreasing k-means objective guarantee?

• A globally optimal clustering.
• A causal classification of the data.
• The current run is improving or preserving its stated fit objective.
• The chosen k is correct.

Explanation

Alternating steps improve the objective but can converge to a local optimum.

Does the first principal component necessarily best predict a target?

• Yes, because it has most variance.
• No, variance and predictive information are different criteria.
• Only when labels are hidden.
• Yes, after centering.

Explanation

PCA optimizes reconstruction of inputs, not supervised predictive loss.

Primary reading

• Machine Learning course materials: Stanford CS229

Open the study and save your work →