[Reading] On Spectral Clustering: Analysis and an algorithm

Spectrual clustering methods are algorithms that cluster points using eigenvectors of matrices derived from the data. Essentially, it is K means in the eigenvector space of the affinity matrix.

This paper present a simple spectral clustering algorithm and analyze it. It provides a theoretical analysis unlike previous works are empirical.

This method provides 4 elasticities for user to control the clustering:
(1) Affinity matrix construction (usually Gaussian kernel)
(2) Choice of scaling factor (it can be done by search over and pick value that gives the tightest clusters)
(3) Choice of k, the number of clusters
(4) Choice of clustering method