Spectral clustering: Difference between revisions

Revision as of 21:22, 28 March 2021

Revision as of 16:39, 30 March 2021

Line 6:

== 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 [[Spectral clustering#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 smallest several eigenvalues of the Laplacian except for the smallest eigenvalue which will have a value of 0. For computational efficiency, these eigenvectors are often computed as the eigenvectors corresponding to the largest several eigenvalues of a function of the Laplacian.

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. Specifically, the classical reference <ref>J. Demmel, [https://people.eecs.berkeley.edu/~demmel/cs267/lecture20/lecture20.html], 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

Line 60:

== 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

| author = Filippone M., Camastra F., Masulli, F., Rovetta, S.

| year = 2008

Line 70:

|pages = 176–190

|doi=10.1016/j.patcog.2007.05.018

}}</ref>.

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