10.3 Other Clustering Algorithms

When k-means is the wrong shape.

These notes walk through the lecture slides. The original deck is unchanged; use (slides) on the course hub if you want that PDF.

Figures and notes follow Géron, Hands-On Machine Learning; Deisenroth, Faisal, and Ong, Mathematics for Machine Learning; and Theodoridis.

1. Spectral clustering

Cluster by similarity of feature representations, not by Euclidean balls in the original space.

Affinity matrix. Pairwise similarities or distances. Points are vertices; edge weights are similarities.
Graph Laplacian. Turn the affinity matrix into a Laplacian. That matrix encodes connectivity.
Eigendecomposition. Eigenvectors of the Laplacian embed the points in a lower-dimensional space.
Cluster the embedding. Take the eigenvectors for the smallest eigenvalues. Run clustering (usually $k$ -means) there.

Benefits: irregular shapes, non-convex clusters, nonlinear geometry. A flexible route on high-dimensional data.

Applications: image segmentation, social networks, gene expression, dimensionality reduction — anywhere the clumps are not round in the raw features.

Pairwise similarity or distance. Euclidean distance of $x_{i}$ and $x_{j}$ :

d (x_{i}, x_{j}) = \sqrt{\sum_{k = 1}^{n} (x_{i k} - x_{j k})^{2}} .

Cosine similarity of $u$ and $v$ :

\frac{u \cdot v}{‖ u ‖ ‖ v ‖} .

Affinity matrix $A$ : entry $a_{i j}$ is the similarity (or distance) of $x_{i}$ and $x_{j}$ .

Graph Laplacian $L = D - A$ , where $D$ is diagonal with the degree of each vertex.

Then eigendecompose $L$ . Those eigenvectors are the embedding.

Family	Idea
Direct	QR, Jacobi, bisection. Straightforward; expensive on large matrices.
Iterative	Power iteration, Lanczos. Better for large sparse $L$ .
Matrix decompositions	SVD or Cholesky, used indirectly.
Graph partitioning	Spectral partitioning or bisection: split the graph using eigenvectors, then work on the pieces.
Sparse libraries	ARPACK and friends: a few eigenpairs of a large sparse Laplacian.