Content deleted Content added
m reshape one sentence |
Added wikilink Tags: Visual edit Mobile edit Mobile web edit |
||
| (43 intermediate revisions by 23 users not shown) | |||
Line 1:
{{Short description|Clustering methods}}
[[Image:6n-graf.svg|thumb|150px|An example connected graph, with 6 vertices.]]
[[File:6n-graf2.svg|thumb|150px|Partitioning into two connected graphs]]
In [[multivariate statistics]], '''spectral clustering''' techniques make use of the [[Spectrum of a matrix|spectrum]] ([[eigenvalues]]) of the [[similarity matrix]] of the data to perform [[dimensionality reduction]] before [[Cluster analysis|clustering]] in fewer dimensions. The similarity [[Matrix (mathematics)|matrix]] is provided as an input and consists of a quantitative assessment of the relative similarity of each pair of points in the dataset.
In application to image segmentation, spectral clustering is known as [[segmentation-based object categorization]].
Line 6 ⟶ 8:
== Definitions ==
Given an enumerated set of data points, the [[similarity matrix]] may be defined as a symmetric matrix <math>A</math>, where <math>A_{ij}\geq 0</math> represents a measure of the similarity between data points with indices <math>i</math> and <math>j</math>. The general approach to spectral clustering is to use a standard [[Cluster analysis|clustering]] method (there are many such methods, ''k''-means is discussed [[#Relationship with k-means|below]]) on relevant [[eigenvector]]s of a [[Laplacian matrix]] of <math>A</math>. There are many different ways to define a Laplacian which have different mathematical interpretations, and so the clustering will also have different interpretations. The eigenvectors that are relevant are the ones that correspond to
===[[Laplacian matrix]]===
[[Image:elastic network model.png|thumb|A 2-dimensional spring system.]]
Spectral clustering is well known to relate to partitioning of a mass-spring system, where each mass is associated with a data point and each spring stiffness corresponds to a weight of an edge describing a similarity of the two related data points, as in the [[spring system]]. Specifically, the classical reference <ref>{{cite web |first=J. |last=Demmel |url=https://people.eecs.berkeley.edu/~demmel/cs267/lecture20/lecture20.html |title=CS267: Notes for Lecture 23, April 9, 1999, Graph Partitioning, Part 2}}</ref> explains that the eigenvalue problem describing transversal vibration modes of a mass-spring system is exactly the same as the eigenvalue problem for the graph [[Laplacian matrix]] defined as
: <math>L:=D-A</math>,
where <math>D</math> is the [[diagonal matrix]]
:<math>D_{ii} = \sum_j A_{ij}
and A is the [[adjacency matrix]].
The masses that are tightly connected by the springs in the mass-spring system evidently move together from the equilibrium position in low-frequency vibration modes, so that the components of the eigenvectors corresponding to the smallest eigenvalues of the graph Laplacian can be used for meaningful clustering of the masses. For example, assuming that all the springs and the masses are identical in the 2-dimensional spring system pictured, one would intuitively expect that the loosest connected masses on the right-hand side of the system would move with the largest amplitude and in the opposite direction to the rest of the masses when the system is shaken — and this expectation will be confirmed by analyzing components of the eigenvectors of the graph Laplacian corresponding to the smallest eigenvalues, i.e., the smallest [[Vibration#Multiple_degrees_of_freedom_systems_and_mode_shapes|vibration frequencies]].
===[[Laplacian_matrix#Laplacian_matrix_normalization_2|Laplacian matrix normalization]]===
The goal of normalization is making the diagonal entries of the Laplacian matrix to be all unit, also scaling off-diagonal entries correspondingly. In a weighted graph, a vertex may have a large degree because of a small number of connected edges but with large weights just as well as due to a large number of connected edges with unit weights.
A popular normalized spectral clustering technique is the '''[[Segmentation based object categorization#Normalized cuts|normalized cuts algorithm]]''' or ''Shi–Malik algorithm'' introduced by Jianbo Shi and [[Jitendra Malik]],<ref name=":0">Jianbo Shi and Jitendra Malik, [http://www.cs.berkeley.edu/~malik/papers/SM-ncut.pdf "Normalized Cuts and Image Segmentation"], IEEE Transactions on PAMI, Vol. 22, No. 8, Aug 2000.</ref> commonly used for [[segmentation (image processing)|image segmentation]]. It partitions points into two sets <math>(B_1,B_2)</math> based on the [[eigenvector]] <math>v</math> corresponding to the second-smallest [[eigenvalue]] of the [[Laplacian matrix#Symmetric normalized Laplacian|symmetric normalized Laplacian]] defined as
: <math>L^\text{norm}:=I-D^{-1/2}AD^{-1/2}.</math>
The vector <math>v</math> is also the [[eigenvector]] corresponding to the second-largest [[eigenvalue]] of the symmetrically normalized [[adjacency matrix]] <math>D^{-1/2}AD^{-1/2}.</math>
The '''random walk (or left) normalized Laplacian''' is defined as
: <math>L^\text{rw} := D^{-1} L = I - D^{-1} A</math>
and can also be used for spectral clustering. A mathematically equivalent algorithm <ref>Marina Meilă & Jianbo Shi, "[http://www.citeulike.org/user/mpotamias/article/498897 Learning Segmentation by Random Walks]", Neural Information Processing Systems 13 (NIPS 2000), 2001, pp. 873–879.</ref> takes the [[eigenvector]] <math>u</math> corresponding to the largest [[eigenvalue]] of the [[adjacency matrix|random walk normalized adjacency]] matrix <math>P = D^{-1}A</math>.
The eigenvector <math>v</math> of the symmetrically normalized Laplacian and the eigenvector <math>u</math> of the left normalized Laplacian are related by the identity <math>D^{-1/2} v = u.</math>
===[[Cluster analysis]] via Spectral Embedding===
Knowing the <math>n</math>-by-<math>k</math> matrix <math>V</math> of selected eigenvectors, mapping — called spectral embedding — of the original <math>n</math> data points is performed to a <math>k</math>-dimensional vector space using the rows of <math>V</math>. Now the analysis is reduced to clustering vectors with <math>k</math> components, which may be done in various ways.
In the simplest case <math>k=1</math>, the selected single eigenvector <math>v</math>, called the [[Fiedler vector]], corresponds to the second smallest eigenvalue. Using the components of <math>v,</math> one can place all points whose component in <math>v</math> is positive in the set <math>B_+</math> and the rest in <math>B_-</math>, thus bi-partitioning the graph and labeling the data points with two labels. This sign-based approach follows the intuitive explanation of spectral clustering via the mass-spring model — in the low frequency vibration mode that the [[Fiedler vector]] <math>v</math> represents, one cluster data points identified with mutually strongly connected masses would move together in one direction, while in the complement cluster data points identified with remaining masses would move together in the opposite direction. The algorithm can be used for [[hierarchical clustering]] by repeatedly partitioning the subsets in the same fashion.
In the general case <math>k>1</math>, any vector clustering technique can be used, e.g., [[DBSCAN]].
== Algorithms ==
Line 33 ⟶ 54:
If the similarity matrix <math>A</math> has not already been explicitly constructed, the efficiency of spectral clustering may be improved if the solution to the corresponding eigenvalue problem is performed in a [[Matrix-free methods|matrix-free fashion]] (without explicitly manipulating or even computing the similarity matrix), as in the [[Lanczos algorithm]].
For large-sized graphs, the second eigenvalue of the (normalized) graph [[Laplacian matrix]] is often [[ill-conditioned]], leading to slow convergence of iterative eigenvalue solvers. [[Preconditioner#Preconditioning for eigenvalue problems|Preconditioning]] is a key technology accelerating the convergence, e.g., in the matrix-free [[LOBPCG]] method. Spectral clustering has been successfully applied on large graphs by first identifying their [[community structure]], and then clustering communities.<ref>{{cite journal|
Spectral clustering is closely related to [[nonlinear dimensionality reduction]], and dimension reduction techniques such as locally-linear embedding can be used to reduce errors from noise or outliers.<ref>{{Citation
|
| title = Spectral clustering based on local linear approximations.
| journal = Electronic Journal of Statistics | volume = 5 | pages =
| year = 2011
| doi=10.1214/11-ejs651| arxiv = 1001.1323
Line 44 ⟶ 65:
}}</ref>
==Costs==
Denoting the number of the data points by <math>n</math>, it is important to estimate the [[memory footprint]] and compute time, or number of arithmetic operations (AO) performed, as a function of <math>n</math>. No matter the algorithm of the spectral clustering, the two main costly items are the construction of the graph Laplacian and determining its <math>k</math> eigenvectors for the spectral embedding. The last step — determining the labels from the <math>n</math>-by-<math>k</math> matrix of eigenvectors — is typically the least expensive requiring only <math>kn</math> AO and creating just a <math>n</math>-by-<math>1</math> vector of the labels in memory.
The need to construct the graph Laplacian is common for all distance- or correlation-based clustering methods. Computing the eigenvectors is specific to spectral clustering only.
===Constructing graph Laplacian===
The graph Laplacian can be and commonly is constructed from the adjacency matrix. The construction can be performed matrix-free, i.e., without explicitly forming the matrix of the graph Laplacian and no AO. It can also be performed in-place of the adjacency matrix without increasing the memory footprint. Either way, the costs of constructing the graph Laplacian is essentially determined by the costs of constructing the <math>n</math>-by-<math>n</math> graph adjacency matrix.
Moreover, a normalized Laplacian has exactly the same eigenvectors as the normalized adjacency matrix, but with the order of the eigenvalues reversed. Thus, instead of computing the eigenvectors corresponding to the smallest eigenvalues of the normalized Laplacian, one can equivalently compute the eigenvectors corresponding to the largest eigenvalues of the normalized adjacency matrix, without even talking about the Laplacian matrix.
Naive constructions of the graph [[adjacency matrix]], e.g., using the RBF kernel, make it dense, thus requiring <math>n^2</math> memory and <math>n^2</math> AO to determine each of the <math>n^2</math> entries of the matrix. Nystrom method<ref>{{Cite journal|last=Fowlkes|first=C|date=2004|title=Spectral grouping using the Nystrom method.|url=https://escholarship.org/uc/item/29z29233|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|volume=26|issue=2|pages=214–25|doi=10.1109/TPAMI.2004.1262185|pmid=15376896|bibcode=2004ITPAM..26..214F|s2cid=2384316}}</ref> can be used to approximate the similarity matrix, but the approximate matrix is not elementwise positive,<ref>{{Cite journal|first1=S. |last1=Wang |first2=A. |last2=Gittens |first3=M.W. |last3=Mahoney|year=2019|title=Scalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error Bounds|journal=Journal of Machine Learning Research|volume=20|pages=1–49|arxiv=1706.02803}}</ref> i.e. cannot be interpreted as a distance-based similarity.
Algorithms to construct the graph adjacency matrix as a [[sparse matrix]] are typically based on a [[nearest neighbor search]], which estimate or sample a neighborhood of a given data point for nearest neighbors, and compute non-zero entries of the adjacency matrix by comparing only pairs of the neighbors. The number of the selected nearest neighbors thus determines the number of non-zero entries, and is often fixed so that the memory footprint of the <math>n</math>-by-<math>n</math> graph adjacency matrix is only <math>O(n)</math>, only <math>O(n)</math> sequential arithmetic operations are needed to compute the <math>O(n)</math> non-zero entries, and the calculations can be trivially run in parallel.
===Computing eigenvectors===
The cost of computing the <math>n</math>-by-<math>k</math> (with <math>k\ll n</math>) matrix of selected eigenvectors of the graph Laplacian is normally proportional to the cost of multiplication of the <math>n</math>-by-<math>n</math> graph Laplacian matrix by a vector, which varies greatly whether the graph Laplacian matrix is dense or sparse. For the dense case the cost thus is <math>O(n^2)</math>. The very commonly cited in the literature cost <math>O(n^3)</math> comes from choosing <math>k=n</math> and is clearly misleading, since, e.g., in a hierarchical spectral clustering <math>k=1</math> as determined by the [[Fiedler vector]].
In the sparse case of the <math>n</math>-by-<math>n</math> graph Laplacian matrix with <math>O(n)</math> non-zero entries, the cost of the matrix-vector product and thus of computing the <math>n</math>-by-<math>k</math> with <math>k\ll n</math> matrix of selected eigenvectors is <math>O(n)</math>, with the memory footprint also only <math>O(n)</math> — both are the optimal low bounds of complexity of clustering <math>n</math> data points. Moreover, matrix-free eigenvalue solvers such as [[LOBPCG]] can efficiently run in parallel, e.g., on multiple [[GPUs]] with distributed memory, resulting not only in high quality clusters, which spectral clustering is famous for, but also top performance.<ref name="msw2014">{{Cite journal|last1=Acer|first1=Seher|last2=Boman|first2=Erik G.|last3=Glusa|first3=Christian A.|last4=Rajamanickam|first4=Sivasankaran|year=2021|title=Sphynx: A parallel multi-GPU graph partitioner for distributed-memory systems|journal=Parallel Computing|volume=106|article-number=102769 |doi=10.1016/j.parco.2021.102769|s2cid=233481603 |arxiv=2105.00578}}</ref>
==Software==
Free software implementing spectral clustering is available in large open source projects like [[scikit-learn]]<ref>{{Cite web|url=http://scikit-learn.org/stable/modules/clustering.html#spectral-clustering|title = 2.3. Clustering}}</ref> using [[LOBPCG]]<ref>{{Cite conference | url = https://www.researchgate.net/publication/343531874 | title = Modern preconditioned eigensolvers for spectral image segmentation and graph bisection | conference = Clustering Large Data Sets; Third IEEE International Conference on Data Mining (ICDM 2003) Melbourne, Florida: IEEE Computer Society| editor = Boley| editor2 = Dhillon| editor3 = Ghosh| editor4 = Kogan | pages = 59–62| year = 2003| last1 = Knyazev| first1 = Andrew V.}}</ref> with [[multigrid]] [[preconditioning]]<ref name="spectralmultigrid2006">{{Cite conference | url = https://www.researchgate.net/publication/354448354 | title = Multiscale Spectral Image Segmentation Multiscale preconditioning for computing eigenvalues of graph Laplacians in image segmentation | conference = Fast Manifold Learning Workshop, WM Williamburg, VA| year = 2006| last1 = Knyazev| first1 = Andrew V. | doi=10.13140/RG.2.2.35280.02565}}</ref><ref>{{Cite conference | url = https://www.researchgate.net/publication/343531874 | title = Multiscale Spectral Graph Partitioning and Image Segmentation | conference = Workshop on Algorithms for Modern Massive Datasets Stanford University and Yahoo! Research| year = 2006| last1 = Knyazev| first1 = Andrew V.}}</ref> or [[ARPACK]], [[Apache Spark#MLlib Machine Learning Library|MLlib]] for pseudo-eigenvector clustering using the [[power iteration]] method,<ref>{{Cite web|url=http://spark.apache.org/docs/latest/mllib-clustering.html#power-iteration-clustering-pic|title = Clustering - RDD-based API - Spark 3.2.0 Documentation}}</ref> and [[R (programming language)|R]].<ref>{{Cite web|url=https://cran.r-project.org/web/packages/kernlab|title = Kernlab: Kernel-Based Machine Learning Lab|date = 12 November 2019}}</ref>
== Relationship with other clustering methods ==
The ideas behind spectral clustering may not be immediately obvious. It may be useful to highlight relationships with other methods. In particular, it can be described in the context of kernel clustering methods, which reveals several similarities with other approaches.<ref name="filippone2008survey">{{cite journal
|
| title = A survey of kernel and spectral methods for clustering
|journal = Pattern Recognition
Line 71 ⟶ 99:
|doi=10.1016/j.patcog.2007.05.018
| bibcode = 2008PatRe..41..176F
| url = http://eprints.whiterose.ac.uk/8536/2/Filippone_spectral_methodspr08.pdf
}}</ref>
=== 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'''.
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.
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.
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.
Additionally, '''multi-level methods''' have been developed to directly optimize this shared objective function. These methods work by iteratively '''coarsening''' the graph to reduce problem size, solving the problem on a coarse graph, and 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 |last3=Kulis |first3=Brian |date=November 2007 |title=Weighted Graph Cuts without Eigenvectors: A Multilevel Approach |journal=IEEE Transactions on Pattern Analysis and Machine Intelligence |volume=29 |issue=11 |pages=1944–1957 |citeseerx=10.1.1.131.2635 |doi=10.1109/tpami.2007.1115 |pmid=17848776 |bibcode=2007ITPAM..29.1944D |s2cid=9402790}}</ref>
=== Relationship to DBSCAN ===
Spectral clustering is also conceptually related to
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 ==
Ravi Kannan, Santosh Vempala and Adrian Vetta<ref>{{cite journal|last1=Kannan|first1=Ravi|last2=Vempala|first2=Santosh|last3=Vetta|first3=Adrian|title=On Clusterings : Good, Bad and Spectral|journal=Journal of the ACM|volume= 51|issue=3|doi=10.1145/990308.990313|pages=497–515|year=2004|s2cid=207558562}}</ref> proposed a bicriteria measure to define the quality of a given clustering. They said that a clustering was an (α, ε)-clustering if the [[Conductance (graph)|conductance]] of each cluster (in the clustering) was at least α and the weight of the inter-cluster edges was at most ε fraction of the total weight of all the edges in the graph. They also look at two approximation algorithms in the same paper.
== History and related literatures==
Spectral clustering has a long history.<ref>{{Cite journal|last=Cheeger|first=Jeff|date=1969|title=A lower bound for the smallest eigenvalue of the Laplacian|journal=Proceedings of the Princeton Conference in Honor of Professor S. Bochner}}</ref><ref>{{Cite journal|
Ideas and network measures related to spectral clustering also play an important role in a number of applications apparently different from clustering problems. For instance, networks with stronger spectral partitions take longer to converge in opinion-updating models used in sociology and economics.<ref name="DeMarzo Vayanos Zwiebel pp. 909–968">{{cite journal | last1=DeMarzo | first1=P. M. | last2=Vayanos | first2=D. | last3=Zwiebel | first3=J. | title=Persuasion Bias, Social Influence, and Unidimensional Opinions | journal=The Quarterly Journal of Economics | publisher=Oxford University Press
== See also ==
| |||