Clustering Methods

Why This Matters

Clustering sits at the heart of unsupervised learning—you're being tested on your ability to choose the right algorithm for a given data structure and justify that choice mathematically. The methods you'll encounter differ fundamentally in how they define "similarity," whether they assume specific geometric shapes, and how they handle noise. Understanding these distinctions means you can answer questions about convergence guarantees, computational complexity, and parameter sensitivity—all frequent exam topics.

Don't just memorize algorithm names and steps. Know what optimization objective each method minimizes, what assumptions it makes about cluster geometry, and when those assumptions break down. The concepts here—distance metrics, density estimation, probabilistic modeling, and dimensionality reduction—connect directly to broader numerical analysis principles you'll see throughout the course.

---

Centroid-Based Methods

These algorithms define clusters by their center points and assign data based on distance to those centers. The core mechanism involves iteratively updating centroid positions to minimize within-cluster variance.

K-Means Clustering

• Minimizes within-cluster sum of squares—the objective function is $J = \sum_{i=1}^{K} \sum_{x \in C_i} \|x - \mu_i\|^2$ where $\mu_i$ is the centroid of cluster $C_i$
• Lloyd's algorithm iterates between assignment and update steps, converging to a local minimum (not guaranteed to find global optimum)
• Requires $K$ specified in advance and assumes spherical clusters of similar size—performance degrades with elongated or uneven clusters

Fuzzy C-Means Clustering

• Soft clustering via membership degrees—each point $x$ has membership $u_{ij} \in [0,1]$ for cluster $j$, with $\sum_j u_{ij} = 1$
• Fuzziness parameter $m$ controls how soft the boundaries are; as $m \to 1$, assignments become hard like K-means
• Useful when cluster boundaries overlap—common in image segmentation and pattern recognition where crisp assignments are unrealistic

---

Density-Based Methods

These algorithms identify clusters as regions of high point density separated by low-density areas. The key insight: clusters can have arbitrary shapes as long as dense regions are connected.

DBSCAN

• Two parameters define density—$\varepsilon$ (neighborhood radius) and $\text{minPts}$ (minimum points to form a core point)
• Classifies points as core, border, or noise—core points have $\geq \text{minPts}$ neighbors within $\varepsilon$; noise points belong to no cluster
• No cluster count required and naturally handles outliers—ideal when you expect irregular cluster shapes or contaminated data

OPTICS

• Produces a reachability plot instead of explicit clusters—visualizes clustering structure across multiple density thresholds simultaneously
• Handles varying densities that break DBSCAN; the reachability distance $r(p)$ captures local density information
• Extract clusters post-hoc by choosing thresholds on the reachability plot—more flexible than committing to single $\varepsilon$ value upfront

Mean Shift Clustering

• Kernel density estimation drives the algorithm—points iteratively shift toward the mode of their local density estimate
• Bandwidth parameter $h$ controls smoothing; larger $h$ merges nearby modes, smaller $h$ preserves fine structure
• Converges to local density maxima—no cluster count needed, but computational cost is $O(Tn^2)$ for $T$ iterations

---

Probabilistic Methods

These methods model clusters as probability distributions and use statistical inference for assignments. Data points are assumed to be generated from a mixture of underlying distributions.

Gaussian Mixture Models (GMM)

• Assumes data comes from $K$ Gaussian distributions—each cluster has mean $\mu_k$, covariance $\Sigma_k$, and mixing weight $\pi_k$
• EM algorithm alternates E and M steps—E-step computes posterior probabilities $\gamma_{ik}$, M-step updates parameters to maximize likelihood
• Soft assignments with full covariance allow elliptical clusters of different sizes and orientations—more flexible than K-means' spherical assumption

---

Hierarchical Methods

These algorithms build a tree structure (dendrogram) representing nested cluster relationships. No single partition is produced—you choose a level to "cut" the tree.

Agglomerative Clustering

• Bottom-up merging starts with $n$ singleton clusters and repeatedly merges the closest pair until one cluster remains
• Linkage criterion determines "closest"—single linkage (min distance), complete linkage (max), average linkage, or Ward's method (minimum variance)
• Dendrogram visualization reveals hierarchical structure; cut at different heights to obtain different numbers of clusters

Hierarchical Clustering (General)

• Divisive (top-down) approach starts with one cluster and recursively splits—less common due to higher computational cost
• No $K$ required upfront—the dendrogram lets you explore multiple granularities without re-running the algorithm
• $O(n^2)$ space and $O(n^3)$ time for naive implementations—limits scalability to moderate dataset sizes

---

Graph and Manifold Methods

These algorithms leverage similarity graphs and linear algebra to find clusters in complex, non-convex structures. The key idea: transform the data representation before applying simpler clustering.

Spectral Clustering

• Constructs a similarity graph with adjacency matrix $W$ and computes the graph Laplacian $L = D - W$ where $D$ is the degree matrix
• Eigendecomposition reveals structure—the $K$ smallest eigenvectors of $L$ embed data into a space where K-means works well
• Excels on non-convex clusters that defeat centroid methods—the graph structure captures connectivity rather than just distance

Self-Organizing Maps (SOM)

• Neural network for dimensionality reduction—maps high-dimensional data onto a 2D grid while preserving topological relationships
• Competitive learning updates the best matching unit (BMU) and its neighbors; learning rate and neighborhood size decay over training
• Visualization and clustering combined—the trained map reveals cluster structure through the organization of grid nodes

---

Quick Reference Table

---

Self-Check Questions

1. Which two methods both provide soft cluster assignments, and how do their underlying models differ?

2. You have a dataset with clusters of varying densities and irregular shapes. Which method would you choose over DBSCAN, and why does it handle this case better?

3. Compare and contrast K-Means and GMM: what assumption does GMM relax, and what additional parameters must be estimated as a result?

4. An FRQ asks you to cluster data where you don't know the number of groups in advance. Name three methods that don't require specifying $K$ and explain what parameter(s) each requires instead.

5. Why does spectral clustering outperform K-means on non-convex clusters? Describe the role of the graph Laplacian in transforming the problem.