Content deleted Content added
ChromeGames (talk | contribs) m Adding short description: "Clustering methods" |
|||
Line 21:
The goal of normalization is making the diagonal entries of the Laplacian matrix to be all unit, also scaling off-diagonal entries correspondingly. In a weighted graph, a vertex may have a large degree because of a small number of connected edges but with large weights just as well as due to a large number of connected edges with unit weights.
A popular normalized 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 name=":0">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 [[Laplacian matrix#Symmetric normalized Laplacian|symmetric normalized Laplacian]] defined as
: <math>L^\text{norm}:=I-D^{-1/2}AD^{-1/2}.</math>
| |||