Content deleted Content added
→Relationship with k-means and dbscan: explanation |
Added wikilink Tags: Visual edit Mobile edit Mobile web edit |
||
| (3 intermediate revisions by 3 users not shown) | |||
Line 2:
[[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 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|last1=Zare|first1=Habil |first2=P. |last2=Shooshtari |first3=A. |last3=Gupta |first4=R. |last4=Brinkman|title=Data reduction for spectral clustering to analyze high throughput flow cytometry data|journal=BMC Bioinformatics|date=2010|doi=10.1186/1471-2105-11-403|volume=11|
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
Line 75:
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.
Line 82:
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.
==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>
== Relationship with other clustering methods ==
Line 111:
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
=== Relationship to DBSCAN ===
Spectral clustering is also conceptually related to '''DBSCAN''' (Density-Based Spatial Clustering of Applications with Noise), particularly in the special case where the spectral method is used to identify [[Connected component (graph theory)|'''connected graph components''']] of a graph. In this trivial case—where the goal is to identify subsets of nodes with '''no interconnecting edges''' between them—the spectral method effectively reduces to a connectivity-based clustering approach, much like 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.
| |||