Objective Function

In the previous page, we learned that Lloyd's algorithm monotonically decreases some objective function. But what exactly is that objective? Why does minimizing it produce meaningful clusters?

The k-means objective function—the within-cluster sum of squares (WCSS)—is more than just a mathematical convenience. It encodes a specific notion of what makes a "good" clustering: clusters should be compact (points close to their centroid) and homogeneous (points within a cluster are similar to each other).

Understanding this objective function is crucial because:

• It explains when k-means works well and when it fails
• It connects clustering to variance decomposition and information theory
• It reveals the relationship between k-means and probabilistic models like GMMs
• It guides the choice of distance metrics and feature scaling

The k-means objective function is elegantly simple. Given a dataset $\mathcal{X} = {\mathbf{x}_1, \ldots, \mathbf{x}_n}$, cluster assignments ${C_1, \ldots, C_k}$, and centroids ${\boldsymbol{\mu}_1, \ldots, \boldsymbol{\mu}_k}$, the within-cluster sum of squares (WCSS) is:

$$J = \sum_{j=1}^{k} \sum_{\mathbf{x}_i \in C_j} |\mathbf{x}_i - \boldsymbol{\mu}_j|^2$$

Equivalently, using indicator variables $r_{ij} \in {0, 1}$ where $r_{ij} = 1$ iff point $i$ belongs to cluster $j$:

$$J = \sum_{i=1}^{n} \sum_{j=1}^{k} r_{ij} |\mathbf{x}_i - \boldsymbol{\mu}_j|^2$$

subject to $\sum_{j=1}^{k} r_{ij} = 1$ for all $i$ (each point in exactly one cluster).

Decomposing the Objective:

We can rewrite $J$ in a revealing form. For each cluster $j$:

$$J_j = \sum_{\mathbf{x}_i \in C_j} |\mathbf{x}_i - \boldsymbol{\mu}_j|^2 = |C_j| \cdot \text{Var}(C_j)$$

where $\text{Var}(C_j) = \frac{1}{|C_j|} \sum_{\mathbf{x}_i \in C_j} |\mathbf{x}_i - \boldsymbol{\mu}_j|^2$ is the within-cluster variance.

Thus: $$J = \sum_{j=1}^{k} |C_j| \cdot \text{Var}(C_j) = \text{Total within-cluster variance} \times n$$

Interpretation: K-means minimizes the weighted sum of cluster variances. Larger clusters contribute more to the objective, which aligns with the intuition that we care more about the coherence of large clusters.

A beautiful result from statistics provides deep insight into what k-means accomplishes. The total variance of a dataset can be decomposed into within-cluster and between-cluster components.

Total Sum of Squares (TSS): $$\text{TSS} = \sum_{i=1}^{n} |\mathbf{x}_i - \bar{\mathbf{x}}|^2$$

where $\bar{\mathbf{x}} = \frac{1}{n}\sum_{i=1}^n \mathbf{x}_i$ is the global mean.

Within-Cluster Sum of Squares (WCSS): $$\text{WCSS} = \sum_{j=1}^{k} \sum_{\mathbf{x}_i \in C_j} |\mathbf{x}_i - \boldsymbol{\mu}_j|^2$$

Between-Cluster Sum of Squares (BCSS): $$\text{BCSS} = \sum_{j=1}^{k} |C_j| |\boldsymbol{\mu}_j - \bar{\mathbf{x}}|^2$$

Proof of the Decomposition:

For any point $\mathbf{x}_i \in C_j$: $$\mathbf{x}_i - \bar{\mathbf{x}} = (\mathbf{x}_i - \boldsymbol{\mu}_j) + (\boldsymbol{\mu}_j - \bar{\mathbf{x}})$$

Squaring both sides and summing over all points: $$\sum_{i=1}^n |\mathbf{x}i - \bar{\mathbf{x}}|^2 = \sum{j=1}^{k} \sum_{\mathbf{x}_i \in C_j} \left[ |\mathbf{x}_i - \boldsymbol{\mu}_j|^2 + |\boldsymbol{\mu}_j - \bar{\mathbf{x}}|^2 + 2(\mathbf{x}_i - \boldsymbol{\mu}_j)^T(\boldsymbol{\mu}_j - \bar{\mathbf{x}}) \right]$$

The cross term vanishes because $\sum_{\mathbf{x}_i \in C_j}(\mathbf{x}_i - \boldsymbol{\mu}_j) = \mathbf{0}$ (the mean is the point where deviations sum to zero). This yields:

$$\text{TSS} = \text{WCSS} + \text{BCSS}$$

Explained Variance Ratio:

We can define the explained variance ratio or R-squared for clustering:

$$R^2 = \frac{\text{BCSS}}{\text{TSS}} = 1 - \frac{\text{WCSS}}{\text{TSS}}$$

• $R^2 \to 0$: Clustering explains little variance; clusters are not meaningful
• $R^2 \to 1$: Clustering explains most variance; clusters are well-separated

This provides a normalized measure of clustering quality that's invariant to the overall scale of the data.

K-means specifically uses squared Euclidean distance $|\mathbf{x} - \boldsymbol{\mu}|^2$, not other distance measures. This isn't arbitrary—it's mathematically essential for the algorithm to work.

The Critical Property: The Mean Minimizes Squared Distances

For any set of points $S = {\mathbf{x}_1, \ldots, \mathbf{x}m}$, the point $\boldsymbol{\mu}$ that minimizes $\sum{\mathbf{x} \in S} |\mathbf{x} - \boldsymbol{\mu}|^2$ is the arithmetic mean:

$$\boldsymbol{\mu}^* = \frac{1}{m}\sum_{\mathbf{x} \in S} \mathbf{x}$$

Proof: $$\frac{\partial}{\partial \boldsymbol{\mu}} \sum_{\mathbf{x} \in S} |\mathbf{x} - \boldsymbol{\mu}|^2 = -2\sum_{\mathbf{x} \in S}(\mathbf{x} - \boldsymbol{\mu}) = 0$$ $$\Rightarrow \sum_{\mathbf{x} \in S} \mathbf{x} = m \boldsymbol{\mu} \Rightarrow \boldsymbol{\mu} = \frac{1}{m}\sum_{\mathbf{x} \in S} \mathbf{x}$$

Geometric Interpretation:

Squared Euclidean distance creates spherical clusters—all points equidistant from a centroid form a hypersphere. The Voronoi cells (regions assigned to each centroid) are convex polytopes.

This has important implications:

1. K-means finds convex clusters — It cannot discover non-convex shapes
2. Clusters are axis-aligned ellipsoids at best — Due to isotropic distance
3. Scale matters — Features on different scales contribute unequally

Feature Scaling is Essential:

If feature 1 ranges [0, 1] and feature 2 ranges [0, 1000], the squared distance is dominated by feature 2: $$|\mathbf{x} - \boldsymbol{\mu}|^2 = (x_1 - \mu_1)^2 + (x_2 - \mu_2)^2 \approx (x_2 - \mu_2)^2$$

Standardizing features (z-scores) or min-max scaling ensures all features contribute equally.

K-means has a fascinating interpretation in signal processing and information theory as vector quantization (VQ)—a technique for lossy data compression.

The VQ Problem:

Given $n$ vectors ${\mathbf{x}_1, \ldots, \mathbf{x}_n}$, find $k$ codebook vectors ${\boldsymbol{\mu}_1, \ldots, \boldsymbol{\mu}_k}$ (also called codewords or prototypes) that best represent the data. Each data point is then quantized by replacing it with its nearest codeword.

The distortion is exactly the k-means objective: $$D = \frac{1}{n}\sum_{i=1}^{n} \min_j |\mathbf{x}_i - \boldsymbol{\mu}_j|^2$$

Lloyd's algorithm is also known as the Lloyd-Max algorithm in the VQ literature.

Information-Theoretic View:

From an information theory perspective, the k-means codebook enables a simple coding scheme:

• Encoding: Map each data point to its nearest centroid index (requires $\log_2 k$ bits)
• Decoding: Replace the index with the centroid
• Reconstruction error: The distortion/WCSS

This connects to rate-distortion theory: the tradeoff between bits used (rate) and reconstruction error (distortion). K-means finds the optimal codebook for a fixed number of codewords.

Comparison with Other Quantizers:

K-means has a deep connection to Gaussian Mixture Models (GMMs)—specifically, k-means is the limit of GMM when cluster variances go to zero.

The GMM Model:

A Gaussian Mixture Model assumes data is generated from $k$ Gaussian distributions: $$p(\mathbf{x}) = \sum_{j=1}^{k} \pi_j \mathcal{N}(\mathbf{x} | \boldsymbol{\mu}_j, \Sigma_j)$$

where $\pi_j$ are mixing weights and $\mathcal{N}(\mathbf{x}|\boldsymbol{\mu}, \Sigma)$ is the Gaussian density.

K-Means as a Limiting Case:

Consider GMM with:

• Equal mixing weights: $\pi_j = 1/k$
• Spherical covariances: $\Sigma_j = \sigma^2 I$ for all $j$
• Taking the limit $\sigma^2 \to 0$

Derivation:

The probability of point $\mathbf{x}$ belonging to cluster $j$ is: $$p(z = j | \mathbf{x}) = \frac{\pi_j \mathcal{N}(\mathbf{x}|\boldsymbol{\mu}j, \sigma^2 I)}{\sum{j'} \pi_{j'} \mathcal{N}(\mathbf{x}|\boldsymbol{\mu}_{j'}, \sigma^2 I)}$$

For spherical Gaussians: $$\mathcal{N}(\mathbf{x}|\boldsymbol{\mu}_j, \sigma^2 I) \propto \exp\left(-\frac{|\mathbf{x} - \boldsymbol{\mu}_j|^2}{2\sigma^2}\right)$$

As $\sigma^2 \to 0$, the exponential becomes sharply peaked around the nearest centroid. The posterior becomes a hard assignment:

$$\lim_{\sigma^2 \to 0} p(z = j|\mathbf{x}) = \begin{cases} 1 & \text{if } j = \arg\min_{j'} |\mathbf{x} - \boldsymbol{\mu}_{j'}|^2 \ 0 & \text{otherwise} \end{cases}$$

This is exactly k-means assignment!

While Lloyd's algorithm is computationally efficient, finding the globally optimal k-means solution is computationally intractable.

Formal Result:

The k-means clustering problem (minimize WCSS) is NP-hard, even for:

• $k = 2$ clusters (Aloise et al., 2009)
• $d = 2$ dimensions (Mahajan et al., 2009)

The problem remains NP-hard even when either $k$ or $d$ is fixed at 2.

What This Means:

• No known polynomial-time algorithm can guarantee the global optimum
• Lloyd's algorithm finds a local minimum, not necessarily the global one
• Multiple restarts with different initializations are necessary
• Approximation algorithms (like k-means++) provide theoretical guarantees

Approximation Guarantees:

Despite NP-hardness, good approximations are achievable:

• K-means++: Achieves $O(\log k)$ approximation in expectation
• D2-sampling: Similar guarantees with different analysis
• Local search methods: $1 + \epsilon$ approximation for any $\epsilon > 0$ (PTAS), but exponential in $1/\epsilon$

For most practical applications, Lloyd's algorithm with good initialization (k-means++) provides solutions within a few percent of optimal.

What's Next:

We now understand what k-means is optimizing and why. But the algorithm's success heavily depends on initialization—different starting points can lead to wildly different solutions. In the next page, we'll study initialization strategies, especially the k-means++ algorithm that provides theoretical guarantees on solution quality.