54  K-Means and K-Medoids

K-Means is the most widely deployed clustering algorithm due to its conceptual simplicity, linear computational scaling per iteration, and interpretable mean-centroid cluster representations (MacQueen 1967; Lloyd 1982).

1 K-Means Objective Function

K-Means partitions \(n\) instances into \(k\) clusters \(C_1,\dots,C_k\) minimizing within-cluster sum-of-squares (WCSS):

Definition. K-Means WCSS Objective: \[ J(C_1,\dots,C_k) = \sum_{j=1}^{k}\sum_{\mathbf{x}\in C_j}\|\mathbf{x}-\boldsymbol{\mu}_j\|^2, \tag{1}\] where \(\boldsymbol{\mu}_j = \frac{1}{|C_j|}\sum_{\mathbf{x}\in C_j}\mathbf{x}\) denotes the centroid vector of cluster \(j\).

2 Lloyd’s Algorithm

Lloyd’s K-Means Algorithm: 1. Initialize: Select \(k\) initial centroids \(\boldsymbol{\mu}_1,\dots,\boldsymbol{\mu}_k\). 2. Assignment Step: Assign each instance \(\mathbf{x}_i\) to nearest centroid: \[\ell(i) = \arg\min_{j} \|\mathbf{x}_i - \boldsymbol{\mu}_j\|^2\] 3. Update Step: Recompute centroids as mean of assigned points: \[\boldsymbol{\mu}_j = \frac{1}{|C_j|}\sum_{\ell(i)=j}\mathbf{x}_i\] 4. Convergence: Repeat steps 2-3 until cluster assignments stabilize.

3 K-Means++ Initialization

Standard random initialization is vulnerable to suboptimal local minima. K-Means++ (Arthur and Vassilvitskii 2007) selects initial centroids using distance-proportional sampling \(P(\mathbf{x}_i) \propto D(\mathbf{x}_i)^2\), bounding expected WCSS within \(O(\log k)\) of global optimum.

K-Means — Step-by-Step Animation
Observe centroid updates and Voronoi partition shifts

k = 3

4 K-Medoids (PAM)

K-Medoids represents clusters using actual exemplar data points (medoids) rather than spatial means, offering robustness against outliers (Kaufman and Rousseeuw 1990).

Definition. Medoid Selection: \[ \mathbf{m}_j = \arg\min_{\mathbf{x}\in C_j}\sum_{\mathbf{x}'\in C_j}d(\mathbf{x},\mathbf{x}'). \tag{2}\]

from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans

X, _ = make_blobs(n_samples=300, centers=4, cluster_std=0.7, random_state=7)

wcss = []
for k in range(1, 7):
    km = KMeans(n_clusters=k, random_state=0, n_init=10)
    km.fit(X)
    wcss.append(km.inertia_)
    print(f"k={k} | WCSS: {km.inertia_:.2f}")

k=1 | WCSS: 21990.36
k=2 | WCSS: 8805.13
k=3 | WCSS: 2236.26
k=4 | WCSS: 279.94
k=5 | WCSS: 250.42
k=6 | WCSS: 223.32

5 Summary

K-Means partitions vector spaces by minimizing squared Euclidean distance from centroids. K-Means++ mitigates initialization sensitivity, while K-Medoids replaces cluster means with actual medoid observations to improve outlier robustness (MacQueen 1967; Arthur and Vassilvitskii 2007; Kaufman and Rousseeuw 1990).

6 References

Arthur, David, and Sergei Vassilvitskii. 2007. “K-Means++: The Advantages of Careful Seeding.” Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1027–35.

Kaufman, Leonard, and Peter J. Rousseeuw. 1990. Finding Groups in Data: An Introduction to Cluster Analysis. Wiley.

Lloyd, Stuart P. 1982. “Least Squares Quantization in PCM.” IEEE Transactions on Information Theory 28 (2): 129–37.

MacQueen, James. 1967. “Some Methods for Classification and Analysis of Multivariate Observations.” Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability 1: 281–97.