Spectral clustering: Difference between revisions

Revision as of 22:35, 12 February 2014

Revision as of 23:06, 12 February 2014

Line 6:

== Algorithms ==

Given aan enumerated set of data points A, the [[similarity matrix]] may be defined as a symmetric matrix <math>SA</math>, where <math>S_A_{ij}\geq 0</math> represents a measure of the similarity between data points with indexes <math>i,</math> j\inand A<math>j</math>.

One 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>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 normalized [[Laplacian matrix]]

[[Laplacian_matrix#Symmetric_normalized_Laplacian|symmetric normalized Laplacian]] defined as

: <math>L ^{norm}:= I - D^{-1/2}SDAD^{-1/2} \, </math>,

of <math>S</math>, where <math>D</math> is the diagonal matrix

:<math>D_{ii} = \sum_j S_A_{ij}.</math>

A relatedmathematically equivalent algorithm is the '''[[Meila–Shi 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> which takes the [[eigenvector]]s corresponding to the ''k'' largest [[eigenvalue]]s of the [[Laplacian_matrix#Random_walk_normalized_Laplacian|random walk normalized Laplacian]] matrix <math>P = D^{-1}SA</math> for some ''k'', and then invokes another algorithm (e.g. [[k-means clustering]]) to cluster points by their respective ''k'' components in these eigenvectors.

This partitioning may be done in various ways, such as by taking the median <math>m</math> of the components in <math>v</math>, and placing all points whose component in <math>v</math> is greater than <math>m</math> in <math>B_1</math>, and the rest in <math>B_2</math>. The algorithm can be used for hierarchical clustering by repeatedly partitioning the subsets in this fashion.

Another possibility is to use the [[Laplacian matrix]] defined as

A related algorithm is the '''[[Meila–Shi 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> which takes the [[eigenvector]]s corresponding to the ''k'' largest [[eigenvalue]]s of the matrix <math>P = D^{-1}S</math> for some ''k'', and then invokes another algorithm (e.g. [[k-means clustering]]) to cluster points by their respective ''k'' components in these eigenvectors.

: <math>L:=D-A</math>

rather than the [[Laplacian_matrix#Symmetric_normalized_Laplacian|symmetric normalized Laplacian]] matrix.

This partitioningPartitioning may be done in various ways, such as by taking the median <math>m</math> of the components in <math>v</math>, and placing all points whose component in <math>v</math> is greater than <math>m</math> in <math>B_1</math>, and the rest in <math>B_2</math>. The algorithm can be used for hierarchical clustering by repeatedly partitioning the subsets in this fashion.

Alternatively to computiong just one eigenvector, ''k'' [[eigenvector]]s for some ''k'', are computed, and then another algorithm (e.g. [[k-means clustering]]) is used to cluster points by their respective ''k'' components in these eigenvectors.

An efficiency of spectral clustering may be improved if the solve of the corresponding eigenvalue problem is performed in a [[Matrix-free methods|matrix-free fashion]], i.e., without explicitly computing the similarity matrix, as, e.g., in the [[Lanczos algorithm]].