K-Means and Hierarchical Clustering

You hand the algorithm unlabeled customer data and ask it to find groups. K-means wants you to declare the number of groups up front. Hierarchical clustering builds every possible grouping at once and lets you cut later.

You fix $K$, the target number of clusters, then iterate:

• Initialize. Randomly place $K$ centroids in feature space (or use k-means++ smart seeding).
• Assign. Send each observation to the nearest centroid by Euclidean distance.
• Update. Move each centroid to the mean of its assigned points.
• Repeat steps 2 and 3 until assignments stop changing.

The objective is to minimize within-cluster sum of squares (WCSS):

$$\text{WCSS} = \sum_{k=1}^{K} \sum_{i \in C_k} \| x_i - \mu_k \|^2$$

KEY: Each iteration weakly decreases WCSS, so the algorithm converges. But it converges to a local minimum, not the global one. Re-run with multiple random starts and keep the lowest WCSS.

Two within-cluster conventions. WCSS sums squared distances to each centroid and is the quantity R's kmeans reports as tot.withinss.

Common mistakes

• Forgetting to standardize features. A feature ranging 0 to 100,000 crushes a feature ranging 0 to 80 in Euclidean distance. Standardize first.
• Reporting one K-means run. A single random initialization can land in a poor local minimum. Always do at least 20 random starts and keep the lowest WCSS.
• Confusing the elbow with a hard rule. The elbow at $K=3$ is a suggestion, not a proof. Cross-check with silhouette or business sense.

Bottom line

• K-means partitions n observations into a pre-specified K clusters by minimizing within-cluster sum of squares (WCSS). You must choose K before running it.
• K-means alternates assignment and centroid updates and converges only to a local minimum, so run at least 20 random starts and keep the lowest WCSS.
• Agglomerative hierarchical clustering starts with n singletons and merges the two closest clusters at each step, producing a dendrogram. No K is required up front.
• Linkage method controls "closest" in hierarchical: complete (max), single (min), average, centroid, and Ward's. Single linkage chains; complete linkage produces compact balls.

Exam shortcut

If the question fixes K and asks you to iterate centroids, it is K-means. If it mentions a dendrogram or linkage, it is hierarchical. The word "chaining" almost always points to single linkage. With tens of thousands of rows and both methods offered, pick K-means on complexity alone.

The full lesson (about 3,807 words, 25 min read) adds 6 worked examples, all 8 common mistakes, a self-check, free in the app.

Learning objectives

• 5c

Browse all free Exam SRM lessons or jump into free Exam SRM practice questions.