machine-learning clustering graph-theory
Definition
Spectral Clustering
Spectral clustering is a distance-based clustering technique that utilises the eigenvalues and eigenvectors of similarity matrices to identify clusters in non-linearly separable data. Formally, given a dataset , the algorithm constructs a similarity graph where edges reflect local proximity and identifies partitions by performing dimensionality reduction on the graph Laplacian.
Structural Capability
Non-Convex Geometries: Unlike k-means, which is restricted to identifying spherical clusters, spectral clustering can identify complex, interlaced, or non-convex structures such as the two-moon dataset. By projecting the data into a space defined by the leading eigenvectors, the algorithm transforms non-linearly separable points into distinct, easily separable clusters.
Connectivity Focus: The method prioritises the connectivity of data points rather than their direct spatial distance, allowing it to capture the intrinsic topological structure of the data distribution.