65  K-Means Clustering

Introduction to Unsupervised Learning named clustering as the first of the two major unsupervised families, groups of observations formed purely by similarity, with no label guiding the process. K-means (James MacQueen, 1967) is the most widely used clustering algorithm, and its logic is simple enough to state in one sentence: assign every observation to whichever of \(k\) cluster centers it is closest to, then move each center to the average position of the observations now assigned to it, and repeat until nothing changes.

That back-and-forth, assign then recompute, is the entire algorithm. It requires deciding \(k\), the number of clusters, in advance, which is both the method’s main convenience and its main open question, addressed later in this topic.

65.1 How K-Means Works

  1. Choose \(k\), and place \(k\) initial cluster centers, commonly by picking \(k\) observations at random as starting points.
  2. Assignment step: assign every observation to the nearest center, using Euclidean distance (see Introduction to Unsupervised Learning).
  3. Update step: recompute each center as the mean of every observation currently assigned to it, which is where the “means” in k-means comes from.
  4. Repeat the assignment and update steps until cluster assignments stop changing, or a maximum number of iterations is reached.

Because the starting centers are chosen randomly, different runs can converge to different final groupings, especially with a poor initial placement. Running the algorithm several times from different random starts and keeping the best result, measured by the lowest total within-cluster variation, is the standard defense against landing on a mediocre local solution.

65.2 Worked Example

Eighteen farms in a district, described by three features with no label attached: farm size in acres, the share of cultivated area under irrigation, and fertilizer spending per acre. The cooperative extension office wants to segment these farms into meaningful groups before deciding which farms to prioritize for which kind of advisory visit, exactly the farm-segmentation use case flagged in the previous topic.

Farm Size (acres) Irrigation (%) Fertilizer Spend (₹’000/acre)
1 2.5 10 3.5
2 3.0 15 4.0
3 3.5 8 5.0
4 4.0 20 4.5
5 2.8 12 3.8
6 4.5 22 6.0
7 6.5 40 9.5
8 7.0 45 10.0
9 8.0 38 11.0
10 7.5 50 9.8
11 9.0 42 12.5
12 8.5 55 11.5
13 12.0 70 16.0
14 14.0 75 18.0
15 11.5 68 15.5
16 16.0 85 20.0
17 13.0 72 17.0
18 15.5 90 21.0

65.3 Choosing K: The Elbow Method

Before running k-means with a chosen number of clusters, it helps to check whether that number is a reasonable one. The elbow method runs k-means for a range of values of \(k\) and plots the total within-cluster sum of squares (WSS) against \(k\). WSS always decreases as \(k\) grows (more clusters can always fit the data at least as well), but it typically drops sharply up to a point and then flattens out. The value of \(k\) at that bend, the “elbow,” is a reasonable default, the point beyond which adding another cluster buys little additional separation for the added complexity.

65.4 K-Means Clustering in R

65.5 Reading the Result

The WSS values should show a visible bend around \(k = 3\), matching how the eighteen farms were described going in: small rainfed operations, medium mixed farms, and large intensively irrigated holdings. The cluster profile table translates the abstract cluster numbers back into terms an extension officer can act on directly: cluster centers reported in acres, irrigation percentage, and rupees per acre, not standardized units. A farm sitting near a cluster boundary is worth a second look, since k-means forces every observation into exactly one group even when its features genuinely sit between two of them, a limitation the next section addresses directly.

Summary

Concept Description
Foundations
K-Means Clustering Assigns each observation to the nearest of k cluster centers, then updates each center to the mean of its members
The Assign-Update Cycle Alternates assignment and update steps until cluster membership stops changing
Random Initialization and nstart Multiple random starts (nstart) guard against converging to a poor local solution from an unlucky initial placement
The Elbow Method Plots total within-cluster sum of squares against k; the bend in the curve suggests a reasonable number of clusters
Worked Example
Worked Example: Segmenting Eighteen Farms Eighteen farms grouped by size, irrigation share, and fertilizer spend, with no label guiding the grouping
Fitting with kmeans() kmeans() on standardized features, chosen k = 3 based on the elbow in the WSS values
Reading Cluster Centers Cluster centers translated back to original units give a profile an extension officer can act on directly
Boundary Cases and Hard Assignment K-means forces every observation into exactly one cluster, even when it sits genuinely between two groups