Clustering Algorithms: K-Means, K-Medoids & Hierarchical Linkages
“Lloyd's WCSS convergence, K-means++ initialization, PAM medoids, and single/complete linkage dendrograms.”
1.The Geometry of Partitional & Hierarchical Clustering
§ 6.1.Clustering partitions an unlabeled dataset X into K groups such that points within the same cluster have high similarity, while points across different clusters are dissimilar.
K-Means++ Initialization:
Standard K-Means picks initial centroids purely at random, which often traps the model in bad local minima. K-means++ chooses the first centroid uniformly at random, and then picks subsequent centroids with probability proportional to their squared distance to the closest existing centroid: P(x) = D(x)^2 / Sum D(z)^2, ensuring widely spaced initial seeds.
2. Worked Practice Problem: 1D K-Means Centroid Iteration
Recompute cluster membership immediately based on nearest centroid before taking the new mean.
Problem: Given 1D points [2, 4, 10, 12, 20] and initial centroids mu1 = 3 and mu2 = 15. Perform one iteration of K-Means and find the updated centroids.
Step 1: Assign each point to nearest centroid (tie-breaker to lower index):
Point 2: |2-3|=1 vs |2-15|=13 => Cluster 1
Point 4: |4-3|=1 vs |4-15|=11 => Cluster 1
Point 10: |10-3|=7 vs |10-15|=5 => Cluster 2
Point 12: |12-3|=9 vs |12-15|=3 => Cluster 2
Point 20: |20-3|=17 vs |20-15|=5 => Cluster 2
Step 2: Compute new centroid means:
Cluster 1 = {2, 4} => mu1_new = (2 + 4) / 2 = 6 / 2 = 3.0
Cluster 2 = {10, 12, 20} => mu2_new = (10 + 12 + 20) / 3 = 42 / 3 = 14.0
Conclusion: After 1 iteration, centroids update to mu1 = 3.0 and mu2 = 14.0.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.