A new spectral clustering algorithm for large training sets
R. Prieto, Jing Bo Jiang, Chi-Ho Choi · 2004
A new algorithm for spectral clustering is depicted. This algorithm can cluster a large number of samples (in the order of 50000 samples) that would be impossible to cluster with current approaches. It is characterized by a complexity that is significantly lower than the cubic complexity that characterizes the calculation of the eigenvectors of a matrix. It's based on a "clustering of clusters" technique, that combines the use of k-means and spectral clustering. Additionally, this method includes the use of expectation maximization (EM) clustering with axis smoothing that is shown to improve the separation in the spectral domain for high values of the scaling parameter /spl sigma//sup 2/.