Spectral clustering: Difference between revisions

Revision as of 13:59, 3 April 2025

Revision as of 23:50, 24 April 2025

Line 103:

=== Relationship with ''k''-means ===

Spectral clustering is closely related to the '''k-means''' algorithm, especially in how cluster assignments are ultimately made. Although the two methods differ fundamentally in their initial formulations—spectral clustering being graph-based and k-means being centroid-based—the connection becomes clear when spectral clustering is viewed through the lens of '''kernel methods'''.

The weighted kernel ''k''-means problem<ref name="dhillon2004kernel">{{cite conference

| last1 = Dhillon |first1=I.S. |last2=Guan |first2=Y. |last3=Kulis |first3=B.

In particular, '''weighted kernel k-means''' provides a key theoretical bridge between the two. Kernel k-means is a generalization of the standard k-means algorithm, where data is implicitly mapped into a high-dimensional feature space through a kernel function, and clustering is performed in that space. Spectral clustering, especially the normalized versions, performs a similar operation by mapping the input data (or graph nodes) to a lower-dimensional space defined by the '''eigenvectors of the graph Laplacian'''. These eigenvectors correspond to the solution of a '''relaxation''' of the '''normalized cut''' or other graph partitioning objectives.

| year = 2004

| title = Kernel ''k''-means: spectral clustering and normalized cuts

Mathematically, the objective function minimized by spectral clustering can be shown to be equivalent to the objective function of weighted kernel k-means in this transformed space. This was formally established in works such as <ref name="dhillon2004kernel">{{cite conference |last1=Dhillon |first1=I.S. |last2=Guan |first2=Y. |last3=Kulis |first3=B. |year=2004 |title=Kernel ''k''-means: spectral clustering and normalized cuts |url=https://www.cs.utexas.edu/users/inderjit/public_papers/kdd_spectral_kernelkmeans.pdf |pages=551–6 |book-title=Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining}}</ref> where they demonstrated that normalized cuts are equivalent to a weighted version of kernel k-means applied to the rows of the normalized Laplacian’s eigenvector matrix.

| book-title = Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining

| pages = 551–6

Because of this equivalence, '''spectral clustering can be viewed as performing kernel k-means in the eigenspace defined by the graph Laplacian'''. This theoretical insight has practical implications: the final clustering step in spectral clustering typically involves running the '''standard k-means algorithm''' on the rows of the matrix formed by the first k eigenvectors of the Laplacian. These rows can be thought of as embedding each data point or node in a low-dimensional space where the clusters are more well-separated and hence, easier for k-means to detect.

| url = https://www.cs.utexas.edu/users/inderjit/public_papers/kdd_spectral_kernelkmeans.pdf

}}</ref>

sharesAdditionally, the'''multi-level methods''' have been developed to directly optimize this shared objective function. withThese methods work by iteratively '''coarsening''' the spectralgraph clusteringto reduce problem size, whichsolving canthe beproblem optimizedon directlya bycoarse multi-levelgraph, methodsand then '''refining''' the solution on successively finer graphs. This leads to more efficient optimization for large-scale problems, while still capturing the global structure preserved by the spectral embedding <ref>{{cite journal |last1=Dhillon |first1=Inderjit |last2=Guan |first2=Yuqiang |last2last3=GuanKulis |first3=Brian |last3date=KulisNovember 2007 |title=Weighted Graph Cuts without Eigenvectors: A Multilevel Approach |journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|date=November 2007|volume=29 |issue=11 |pages=1944–1957 |citeseerx=10.1.1.131.2635 |doi=10.1109/tpami.2007.1115 |pmid=17848776|citeseerx=10.1.1.131.2635 |s2cid=9402790}}</ref>.

=== Relationship to DBSCAN ===

InSpectral clustering is also conceptually related to '''DBSCAN''' (Density-Based Spatial Clustering of Applications with Noise), particularly in the trivialspecial case ofwhere the spectral method is used to determiningidentify [[Connected component (graph theory)|'''connected graph components''']] — of a graph. In this trivial case—where the optimalgoal clustersis to identify subsets of nodes with '''no interconnecting edges''' cutbetween —them—the spectral clusteringmethod iseffectively also relatedreduces to a spectral version of [[DBSCAN]]connectivity-based clustering thatapproach, findsmuch density-connectedlike components.DBSCAN<ref>{{Cite conference |last1=Schubert |first1=Erich |last2=Hess |first2=Sibylle |last3=Morik |first3=Katharina |date=2018 |title=The Relationship of DBSCAN to Matrix Factorization and Spectral Clustering |url=http://ceur-ws.org/Vol-2191/paper38.pdf |conference=LWDA |pages=330–334}}</ref>.

DBSCAN operates by identifying '''density-connected regions''' in the input space: points that are reachable from one another via a sequence of neighboring points within a specified radius (ε), and containing a minimum number of points (minPts). The algorithm excels at discovering clusters of arbitrary shape and separating out noise without needing to specify the number of clusters in advance.

In spectral clustering, when the similarity graph is constructed using a '''hard connectivity criterion''' (i.e., binary adjacency based on whether two nodes are within a threshold distance), and no normalization is applied to the Laplacian, the resulting eigenstructure of the graph Laplacian directly reveals '''disconnected components''' of the graph. This mirrors DBSCAN's ability to isolate '''density-connected components'''. The zeroth eigenvectors of the unnormalized Laplacian correspond to these components, with one eigenvector per connected region.

This connection is most apparent when spectral clustering is used not to optimize a soft partition (like minimizing the normalized cut), but to '''identify exact connected components'''—which corresponds to the most extreme form of “density-based” clustering, where only directly or transitively connected nodes are grouped together. Therefore, spectral clustering in this regime behaves like a '''spectral version of DBSCAN''', especially in sparse graphs or when constructing ε-neighborhood graphs.

While DBSCAN operates directly in the data space using density estimates, spectral clustering transforms the data into an eigenspace where '''global structure and connectivity''' are emphasized. Both methods are non-parametric in spirit, and neither assumes convex cluster shapes, which further supports their conceptual alignment.

== Measures to compare clusterings ==