Clustering

Introduction

Clustering is one of the core tasks in unsupervised learning. Unlike supervised learning, where models learn from labeled data, unsupervised learning aims to uncover hidden patterns or structures in data without any predefined labels. Among these tasks, clustering is particularly important. It groups data points into clusters based on their similarity, revealing the underlying structure of the data.

In previous sections, we explored techniques like Principal Component Analysis (PCA) and autoencoders, which reduce the dimensionality of high-dimensional data while preserving meaningful information. These dimensionality reduction methods helped us uncover compact representations of data, often referred to as latent features.

Now that we have the tools to represent complex data in a lower-dimensional space, we turn to the next natural question: Can we identify meaningful groupings within this reduced space? This is the goal of clustering, which allows us to segment data into coherent groups. Examples include grouping similar images, organizing unlabeled documents, and detecting communities in social networks.

K-means Clustering

We begin with K-means clustering, one of the most widely used and intuitive algorithms.

We assume that there are \(K\) cluster centers \(\mu_k \in \mathbb{R}^D\), for \(k = 1, \cdots, K\). Each data point \(x_n \in \mathbb{R}^D\) is assigned to its nearest center: \[ z_n^* = \arg \min_k \| x_n - \mu_k \|_2^2. \]

Given the assignments, the cluster centers are updated as the mean of points in each cluster: \[ \mu_k = \frac{1}{N_k} \sum_{n : z_n =k} x_n, \,\text{where } N_k = \sum_{n=1}^N \mathbb{I}[z_n = k]. \]

These two steps, assignment and update, are repeated until convergence. This process can be viewed as minimizing a cost function known as the distortion, which is equivalent to the squared Frobenius norm of the reconstruction error: \[ \begin{align*} J(M, Z) &= \sum_{n = 1}^N \| x_n - \mu_{z_n} \|_2^2 \\\\ &= \| X - ZM^\top \|_F^2 \end{align*} \] where \(X \in \mathbb{R}^{N \times D}\), \(Z \in \{0, 1\} ^{N \times K}\), and \(M \in \mathbb{R}^{D \times K}\) contains the cluster centers \(\mu_k\) in its columns.
Note. The matrix \(Z\) is the one-hot encoding (or dummy encoding) matrix whose entries are \[ Z_{nk} = \begin{cases} 1, &\text{ if \(x_n\) is assigned to cluster \(k\) } \\\\ 0, &\text{ otherwise}. \end{cases} \]

Vector Quantization (VQ)

A key idea of vector quantization is to compress data by replacing each high-dimensional vector \(x_n \in \mathbb{R}^D\) with a discrete symbol \(z_n \in \{1, \cdots, K\}\). That symbol is an index into a codebook of \(K\) prototype vectors, \(\mu_k \in \mathbb{R}^D\).

Each data point is encoded by finding the index of the closest prototype using Euclidean distance: \[ z_n := f_e (x_n) = \arg \min_k \| x_n - \mu_k \|^2. \]

The corresponding decoder simply maps the index back to the prototype: \[ f_d(k) = \mu_k. \] The reconstruction of each data point is therefore \(\hat{x}_n = f_d(z_n) = \mu_{z_n}\).

The quality of a codebook is measured using the reconstruction error (also called distortion): \[ \begin{align*} J &= \frac{1}{N} \sum_{n =1}^N \| x_n - f_d (f_e (x_n))\|^2 \\\\ &= \frac{1}{N} \sum_{n=1}^N \|x_n - \mu_{z_n} \|^2. \end{align*} \] Indeed, this is equivalent to the cost function minimized by the K-means algorithm, which can be interpreted as a special case of vector quantization where the codebook is learned by minimizing distortion via iterative updates. VQ is more focused on signal compression and encoding, whereas K-means is usually employed for data analysis and clustering tasks.

Spectral Clustering

Traditional clustering methods like K-means assume clusters are linearly separable and spherical in shape. However, many real-world datasets exhibit complex, non-convex structures that are not well-captured by distance alone. Spectral clustering addresses this limitation by transforming the data into a new space that reflects the connectivity structure of the data, often represented as a graph.

The idea is to build a similarity graph where each data point is a node, and edges encode pairwise similarities. Let \(\mathbf{W} \in \mathbb{R}^{N \times N}\) be a symmetric weight matrix for a graph such that \(w_{ij} = w_{ji} \geq 0\) measures the similarity between points \(i\) and \(j\). The degree of node \(i\) is defined as: \[ d_i = \sum_{j=1}^N w_{ij}, \] and we define the degree matrix \(\mathbf{D} \in \mathbb{R}^{N \times N}\) as a diagonal matrix with entries \(D_{ii} = d_i\).

The fundamental object in spectral clustering is the graph Laplacian, \(\mathbf{L} = \mathbf{D} - \mathbf{W}\), where \(\mathbf{D}\) is the diagonal degree matrix and \(\mathbf{W}\) is the weight (similarity) matrix. The entries of \(\mathbf{L}\) are \[ L_{ij} = \begin{cases} d_i & \text{if } i = j \\\\ -w_{ij} & \text{if } i \neq j \end{cases} \] The Laplacian is real symmetric and positive semi-definite, with associated quadratic form \[ \boldsymbol{f}^\top \mathbf{L} \boldsymbol{f} = \frac{1}{2} \sum_{i,j} w_{ij}(f_i - f_j)^2, \] known as the Dirichlet energy. It measures the smoothness of \(\boldsymbol{f}\) on the graph: small when adjacent nodes (those with \(w_{ij} \gt 0\)) have similar values.

The single result that powers spectral clustering is the connection between the Laplacian's nullspace and the graph's component structure:

The intuition for spectral clustering is now immediate. If a graph has \(K\) well-separated clusters joined by weak inter-cluster edges, it is approximately a union of \(K\) connected components, and the bottom \(K\) eigenvectors of \(\mathbf{L}\) approximate the indicator vectors of those clusters. Spectral clustering exploits this by embedding nodes via these eigenvectors and applying K-means in the embedded space.

Since \(\mathbf{L}\) is symmetric and positive semi-definite, it admits a spectral decomposition: \[ \mathbf{L} = \mathbf{V}\boldsymbol{\Lambda}\mathbf{V}^\top, \quad 0 = \lambda_1 \le \lambda_2 \le \cdots \le \lambda_N, \] where \(\boldsymbol{\Lambda}\) contains the real, non-negative eigenvalues, and the columns of \(\mathbf{V}\) form an orthonormal eigenbasis. The smallest eigenvalues correspond to the smoothest variations of a function on the graph. In the cluster setting, they correspond to the indicator structure described above.

In practice, graphs often exhibit irregular structure. Nodes may have highly varying degrees, and clusters are not perfectly block-separated. The raw Laplacian \(\mathbf{L} = \mathbf{D} - \mathbf{W}\) can then be dominated by high-degree nodes, leading to unbalanced or misleading spectral embeddings. To address this, we use the symmetric normalized Laplacian: \[ \begin{align*} \mathbf{L}_{\text{sym}} &= \mathbf{D}^{-\frac{1}{2}} \mathbf{L} \mathbf{D}^{-\frac{1}{2}} \\\\ &= \mathbf{I} - \mathbf{D}^{-\frac{1}{2}} \mathbf{W} \mathbf{D}^{-\frac{1}{2}} \end{align*} \] For \(\mathbf{L}_{\text{sym}}\) the analogous nullspace characterization is that the eigenspace of zero eigenvalue is spanned by \(\mathbf{D}^{1/2} \mathbf{1}_{S_k}\) for \(k = 1, \ldots, K\), where \(\mathbf{1}_{S_k}\) are again the indicator vectors of the connected components.

The spectral clustering algorithm proceeds as follows: