ML//unsupervised learning//spectral clustering
How to turn local relations into coordinates that allow grouping. **Spectral clustering** groups using eigenvectors of a matrix built from relations between samples. It does not avoid defining similarity: it moves that decision into a graph and then represents the graph's connectivity patterns.
How to turn local relations into coordinates that allow grouping. Spectral clustering groups using eigenvectors of a matrix built from relations between samples. It does not avoid defining similarity: it moves that decision into a graph and then represents the graph's connectivity patterns.
Building the graph is part of the model. Each sample xix_ixi is a node. A common affinity for i≠ji\ne ji=j is
wij=exp (−∥xi−xj∥22σ2),wii=0,w_{ij}=\exp\!\left(-\frac{\|x_i-x_j\|^2}{2\sigma^2}\right),\qquad w_{ii}=0,wij=exp(−2σ2∥xi−xj∥2),wii=0,
possibly restricted to nearby neighbors. σ\sigmaσ sets a similarity scale; the number of neighbors sets local connectivity; a neighbor graph needs a symmetrization rule before an undirected Laplacian is used. A large raw distance must not represent a strong affinity (adjacency and degree). Neither KKK nor the number of neighbors has a universal value: too few connections fragment a group, too many merge distinct regions.
One concrete variant, recipes not mixed. For the symmetric normalized variant, form DDD and Lsym=I−D−1/2WD−1/2L_{\mathrm{sym}}=I-D^{-1/2}WD^{-1/2}Lsym=I−D−1/2WD−1/2, after handling isolated nodes (normalized Laplacian). Take KKK orthonormal eigenvectors of the smallest eigenvalues, the trivial mode included, as columns of U∈RN×KU\in\mathbb R^{N\times K}U∈RN×K. Normalize each nonzero row to unit length; a zero row calls for revisiting components and the number of vectors, not dividing by zero. Apply K-means to those rows and carry the labels back to the samples. This is the Laplacian-based form of the Ng, Jordan and Weiss recipe, whose original operator uses the normalized affinity and the largest eigenvalues. Other variants use LrwL_{\mathrm{rw}}Lrw or the problem Lv=λDvLv=\lambda DvLv=λDv; their transformations and row normalizations must not be mixed casually.
Why the modes separate communities. With KKK disconnected components the null space has dimension KKK and its patterns identify the components; in the symmetric version, row normalization removes degree-induced magnitude differences within each component. With weak connections, low-disagreement patterns appear that distinguish regions well connected inside and poorly outside (spectral gap). The random walk supplies the reading of long stays (stationary distribution).
Which partition is favored. For a node set SSS, cut(S,Sˉ)=∑i∈S,j∉Swij\operatorname{cut}(S,\bar S)=\sum_{i\in S,j\notin S}w_{ij}cut(S,Sˉ)=∑i∈S,j∈/Swij and vol(S)=∑i∈Sdi\operatorname{vol}(S)=\sum_{i\in S}d_ivol(S)=∑i∈Sdi. The normalized cut is
Ncut(S,Sˉ)=cut(S,Sˉ)vol(S)+cut(S,Sˉ)vol(Sˉ).\operatorname{Ncut}(S,\bar S)=\frac{\operatorname{cut}(S,\bar S)}{\operatorname{vol}(S)}+\frac{\operatorname{cut}(S,\bar S)}{\operatorname{vol}(\bar S)}.Ncut(S,Sˉ)=vol(S)cut(S,Sˉ)+vol(Sˉ)cut(S,Sˉ).
It favors regions with few external connections relative to their total connectivity. The spectral problem is a relaxation of partition objectives; discretizing through K-means does not guarantee the combinatorial optimum.
Caveats that must travel with the intuition. Normalizing by degree does not remove every density effect. Eigenvectors are not attractors. The diffusion "time" of a data graph is not automatically the physical time of the process. Cutting by the sign of a single vector is a heuristic for some two-group problems, not the general algorithm. spectral coordinates distinguishes columns from rows; two-community graph works an exact case.
References: von Luxburg, A Tutorial on Spectral Clustering (2007), section 6 ; Ng, Jordan and Weiss, On Spectral Clustering: Analysis and an Algorithm (NIPS 2001), section 2 ; Spielman, Spectral Graph Theory, lecture 1, sections 1.5 and 1.6