Content deleted Content added
m Correcting the format of the scikit-learn library name to all lowercase. |
Tweak cites | Add: authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this tool. Report bugs. | #UCB_Gadget |
||
Line 12:
===[[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
: <math>L:=D-A</math>,
where <math>D</math> is the [[diagonal matrix]]
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|
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 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|s2cid=2384316}}</ref> can be used to approximate the similarity matrix, but the approximate matrix is not elementwise positive,<ref>{{Cite journal|
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 90:
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 105 ⟶ 104:
=== Relationship with ''k''-means ===
The weighted kernel ''k''-means problem<ref name="dhillon2004kernel">{{cite conference
|
| year = 2004
| title = Kernel ''k''-means: spectral clustering and normalized cuts
| book-title = Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining
| pages =
| url = https://www.cs.utexas.edu/users/inderjit/public_papers/kdd_spectral_kernelkmeans.pdf
}}</ref>
shares the objective function with the spectral clustering problem, which can be optimized directly by multi-level methods.<ref>{{cite journal|
=== Relationship to DBSCAN ===
Line 121 ⟶ 120:
== 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 ==
| |||