Normalized Cuts Algorithm

See: Graph Cut Algorithm, Graph Partitioning, Segmentation-based Object Categorization, Normalized Cuts, Spectral Clustering.

References

http://en.wikipedia.org/wiki/Cluster_analysis#Spectral_clustering
- One such technique is the Normalized Cuts algorithm by Shi-Malik, commonly used for image segmentation. It partitions points into two sets [math]\displaystyle{ (S_1,S_2) }[/math] based on the eigenvector [math]\displaystyle{ v }[/math] corresponding to the second-smallest eigenvalue of the Laplacian matrix [math]\displaystyle{ L = I - D^{-1/2}SD^{-1/2} }[/math] of [math]\displaystyle{ S }[/math], where [math]\displaystyle{ D }[/math] is the diagonal matrix [math]\displaystyle{ D_{ii} = \sum_{j} S_{ij}. }[/math] This partitioning may be done in various ways, such as by taking the median [math]\displaystyle{ m }[/math] of the components in [math]\displaystyle{ v }[/math], and placing all points whose component in [math]\displaystyle{ v }[/math] is greater than [math]\displaystyle{ m }[/math] in [math]\displaystyle{ S_1 }[/math], and the rest in [math]\displaystyle{ S_2 }[/math]. The algorithm can be used for hierarchical clustering by repeatedly partitioning the subsets in this fashion. A related algorithm is the Meila-Shi algorithm, which takes the eigenvectors corresponding to the [math]\displaystyle{ k }[/math] largest eigenvalues of the matrix [math]\displaystyle{ P = SD^{-1} }[/math] for some [math]\displaystyle{ k }[/math], and then invokes another algorithm (e.g. k-means) to cluster points by their respective [math]\displaystyle{ k }[/math] components in these eigenvectors.

(Shi & Malik, 1997) ⇒ Jianbo Shi, and Jitendra Malik. (1997). “Normalized Cuts and Image Segmentation.” In: IEEE Conference on Computer Vision and Pattern Recognition (CVPR 1997).