Spectral Clustering Algorithm: Difference between revisions

From GM-RKB
Jump to navigation Jump to search
m (Text replacement - ". ----" to ". ----")
m (Text replacement - "sions]]" to "sion]]s")
 
Line 18: Line 18:
* ([[Sammut & Webb, 2011]]) ⇒ [[Claude Sammut]], and [[Geoffrey I. Webb]]. ([[2011]]). “Spectral Clustering.” In: ([[Sammut & Webb, 2011]]) p.907
* ([[Sammut & Webb, 2011]]) ⇒ [[Claude Sammut]], and [[Geoffrey I. Webb]]. ([[2011]]). “Spectral Clustering.” In: ([[Sammut & Webb, 2011]]) p.907
* (Wikipedia - Spectral Clustering, 2011-Jun-13) ⇒ http://en.wikipedia.org/wiki/Cluster_analysis#Spectral_clustering
* (Wikipedia - Spectral Clustering, 2011-Jun-13) ⇒ http://en.wikipedia.org/wiki/Cluster_analysis#Spectral_clustering
** QUOTE: Given a set of [[data point]]s A, the [[Affinity Matrix|similarity matrix]] may be defined as a [[matrix]] <math>S</math> where <math>S_{ij}</math> represents a [[measure of the similarity]] between points <math>i, j\in A</math>. [[Spectral Clustering Algorithm|Spectral clustering technique]]s make use of the [[Spectrum of a matrix|spectrum]] of the [[Affinity Matrix|similarity matrix]] of the data to perform [[Dimensionality Reduction Task|dimensionality reduction]] for clustering in fewer [[dimensions]]. One such [[Spectral Clustering Algorithm|technique]] is the ''[[Segmentation_based_object_categorization#Normalized_Cuts|Normalized Cuts algorithm]]'' by Shi-Malik, commonly used for [[segmentation (image processing)|image segmentation]]. It partitions points into two sets <math>(S_1,S_2)</math> based on the [[eigenvector]] <math>v</math> corresponding to the second-smallest [[eigenvalue]] of the [[Laplacian matrix]] <math>L = I - D^{-1/2}SD^{-1/2}</math> of <math>S</math>, where <math>D</math> is the [[diagonal matrix]] <math>D_{ii} = \sum_{j} S_{ij}.</math> 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>S_1</math>, and the rest in <math>S_2</math>. [[The algorithm]] can be used for [[hierarchical clustering]] by repeatedly partitioning the subsets in this fashion. A related [[Spectral Clustering Algorithm|algorithm]] is the ''[[Meila-Shi algorithm]]'', which takes the [[eigenvector]]s corresponding to the <math>k</math> largest [[eigenvalue]]s of the matrix <math>P = SD^{-1}</math> for some <math>k</math>, and then invokes another algorithm (e.g. <i>k</i>-means) to cluster points by their respective <math>k</math> components in these eigenvectors.
** QUOTE: Given a set of [[data point]]s A, the [[Affinity Matrix|similarity matrix]] may be defined as a [[matrix]] <math>S</math> where <math>S_{ij}</math> represents a [[measure of the similarity]] between points <math>i, j\in A</math>. [[Spectral Clustering Algorithm|Spectral clustering technique]]s make use of the [[Spectrum of a matrix|spectrum]] of the [[Affinity Matrix|similarity matrix]] of the data to perform [[Dimensionality Reduction Task|dimensionality reduction]] for clustering in fewer [[dimension]]s. One such [[Spectral Clustering Algorithm|technique]] is the ''[[Segmentation_based_object_categorization#Normalized_Cuts|Normalized Cuts algorithm]]'' by Shi-Malik, commonly used for [[segmentation (image processing)|image segmentation]]. It partitions points into two sets <math>(S_1,S_2)</math> based on the [[eigenvector]] <math>v</math> corresponding to the second-smallest [[eigenvalue]] of the [[Laplacian matrix]] <math>L = I - D^{-1/2}SD^{-1/2}</math> of <math>S</math>, where <math>D</math> is the [[diagonal matrix]] <math>D_{ii} = \sum_{j} S_{ij}.</math> 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>S_1</math>, and the rest in <math>S_2</math>. [[The algorithm]] can be used for [[hierarchical clustering]] by repeatedly partitioning the subsets in this fashion. A related [[Spectral Clustering Algorithm|algorithm]] is the ''[[Meila-Shi algorithm]]'', which takes the [[eigenvector]]s corresponding to the <math>k</math> largest [[eigenvalue]]s of the matrix <math>P = SD^{-1}</math> for some <math>k</math>, and then invokes another algorithm (e.g. <i>k</i>-means) to cluster points by their respective <math>k</math> components in these eigenvectors.


=== 2003 ===
=== 2003 ===

Latest revision as of 03:27, 28 April 2024

A Spectral Clustering Algorithm is a clustering algorithm that performs dimensionality reduction (for clustering in fewer dimensions) by means of the spectrum of the affinity matrix.



References

2011

2003

2001