K-Means Clustering

Source: Unit 4 §3

K-Means partitions data into K distinct, non-overlapping clusters - it is the canonical partitional method. You must specify K up front, and each observation is assigned to exactly one cluster.

The algorithm

With clusters $C_1, \dots, C_K$, two properties always hold:

$$C_1 \cup C_2 \cup \dots \cup C_K = \{1, \dots, n\} \qquad C_k \cap C_{k'} = \varnothing \;\; \text{for } k \neq k'$$

The first says every point belongs to some cluster; the second says the clusters are non-overlapping.

Two steps in a loop. Assignment freezes the centroids and moves the points; update freezes the points and moves the centroids.

Worked example: 4 medicines

Four medicines with features (pH, weight index): A(1,1), B(2,1), C(4,3), D(5,4), to be grouped into K = 2.

Step 1 - initial centroids: use A and B, so c1 = (1,1) and c2 = (2,1).

Iteration 0 - Euclidean distances and assignment:

Point	dist to c1(1,1)	dist to c2(2,1)	→ Cluster
A(1,1)	0	1	1
B(2,1)	1	0	2
C(4,3)	√13 = 3.61	√8 = 2.83	2
D(5,4)	√25 = 5	√18 = 4.24	2

→StepsThe full run to convergence

1. Recompute centroids after iteration 0. group1 = {A} so c1 = (1,1); group2 = {B,C,D} so c2 = ((2+4+5)/3, (1+3+4)/3) = (11/3, 8/3) = (3.67, 2.67).
2. Iteration 1 - reassign with c1=(1,1), c2=(3.67, 2.67): A → c1 (0 vs 3.15), B → c1 (1 vs 2.36), C → c2 (3.61 vs 0.47), D → c2 (5 vs 1.88). New clusters: group1 = {A,B}, group2 = {C,D}. Recompute: c1 = (1.5, 1), c2 = (4.5, 3.5).
3. Iteration 2 - reassign with c1=(1.5,1), c2=(4.5,3.5): the clusters come back unchanged as {A,B} and {C,D}, so the centroids will not move again. Converged.
4. Final clusters: {A, B} and {C, D}.

Two iterations move c2 from (2,1) to (4.5,3.5) and pull B back across the boundary. Once no point changes hands, the run is over.

Evaluation: sum of squared error (SSE)

The most common measure. For each point the error is its distance to the nearest cluster centroid; square those and sum them:

$$\text{SSE} = \sum_{i=1}^{K} \; \sum_{x \in C_i} \text{dist}^2(m_i, x)$$

Here $m_i$ is the representative (centroid) of cluster $C_i$, and it can be shown that $m_i$ is the mean of the cluster. Given two clusterings, pick the one with smaller SSE.

⚠GotchaA lower SSE does not mean a better clustering if K changed

Increasing K always reduces SSE - at $K = n$ every point is its own centroid and SSE = 0, which explains nothing. A good clustering with small K can beat a poor clustering with large K, so never compare SSE across different K without accounting for K.

Summary: pros, cons, complexity

Aspect	Detail
Pros	Easy to implement
Cons	Can converge to a local minimum; slow on very large datasets
Works with	Numeric values (nominal attributes get mapped to binary so distances work)
Centroid	typically the mean of the cluster's points
Closeness	Euclidean distance, cosine similarity, correlation, …
Convergence	most of it happens in the first few iterations, so a common stopping rule is "until few points change"
Complexity	**O(n · K · I · d)** - n points, K clusters, I iterations, d attributes

⚠GotchaThe same data can give you two different answers

Initial centroids are chosen randomly, so results vary from run to run. This is not a bug in your implementation, and it is the reason the next page exists.