Other meanings of Spectral Clustering
Machine Learning
Spectral clustering is a machine learning technique that partitions data points into clusters using the eigenvalues and eigenvectors of a similarity matrix derived from the data. Unlike centroid-based methods such as k-means, it can identify clusters of arbitrary shape, including non-convex and nested structures, by embedding the data in a lower-dimensional eigenspace before applying a simple clustering algorithm. The method has become a cornerstone of modern unsupervised learning, with applications ranging from image segmentation to community detection in networks.
Spectral clustering transforms the clustering problem into a graph partitioning problem. Given data points, one constructs a similarity graph where nodes are points and edge weights reflect pairwise similarities, often using a Gaussian kernel. The graph Laplacian matrices (unnormalized, normalized, or random-walk) are then computed, and the eigenvectors corresponding to the smallest eigenvalues provide a low-dimensional embedding that reveals cluster structure. The standard algorithm, as formalized by Ng, Jordan, and Weiss in 2002, uses the first k eigenvectors of the normalized Laplacian to form a new feature matrix, which is then clustered with k-means.1
The choice of Laplacian and similarity measure critically affects performance. The normalized Laplacian often yields better results for unbalanced clusters, while the random-walk version has a natural interpretation in terms of Markov chains. The number of clusters k is typically chosen by inspecting the eigenvalue gap (the "eigengap") or using heuristics like the silhouette score.2
The roots of spectral clustering lie in graph theory and linear algebra. In 1973, Donath and Hoffman used eigenvectors of adjacency matrices for graph partitioning, and Fiedler's work on algebraic connectivity introduced the concept of the Fiedler vector, the eigenvector corresponding to the second smallest Laplacian eigenvalue, which is still used for bipartitioning.3 In the 1990s, researchers like Shi and Malik applied spectral methods to image segmentation, leading to the normalized cuts criterion. The theoretical foundations were solidified by von Luxburg's comprehensive tutorial in 2007, which analyzed consistency and convergence properties.2
Early work was largely ignored by the machine learning community until the late 1990s, when the connection to kernel methods and manifold learning became clear. The method's ability to handle non-linear boundaries made it attractive for real-world data, and it has since become a standard tool in the scikit-learn library and other software packages.
Spectral clustering is widely used in computer vision for image segmentation, where pixels are grouped based on color and spatial proximity, as in the normalized cuts algorithm.4 In network science, it detects communities in social and biological networks by treating the adjacency matrix as a similarity matrix. It also underpins dimensionality reduction techniques like Laplacian eigenmaps, which are used for manifold learning and data visualization.
Variations include the use of different similarity functions (e.g., cosine similarity for text), sparse approximations for large-scale data, and the Nyström method to approximate eigenvectors for massive datasets. Spectral clustering has been extended to handle multi-view data and to incorporate constraints, such as must-link and cannot-link pairs. In bioinformatics, it helps cluster gene expression data and protein sequences, revealing functional groups that are not apparent with other methods.
One lesser-known fact is that spectral clustering is closely related to the concept of random walks: the normalized Laplacian's eigenvectors correspond to the slowest-mixing modes of a Markov chain on the graph, which is why it can separate clusters that are only weakly connected. Another edge case is that the method can fail when clusters have very different sizes or densities, leading to the "spectral clustering bias" toward balanced clusters.
Historically, the Fiedler vector was used in the 1970s for circuit partitioning in VLSI design, a niche application that predates its use in machine learning. Also, spectral clustering has been applied to the segmentation of medical images, such as MRI brain scans, to identify anatomical structures. A surprising detail is that the eigenvectors of the graph Laplacian are related to the heat equation on the graph, providing a physical interpretation of the embedding.
Spectral clustering is a powerful yet computationally intensive method; its performance depends heavily on the choice of similarity measure and the number of clusters.
Help improve the encyclopedia. Reports go straight to the site manager.