A commute time based spectral clustering algorithm

Spectral clustering which will not gain local optimal solutions and can be well applied to non-convex data sets is a novel clustering algorithm. However, one of the shortcomings of the algorithm is that it requires the eigendecomposition of the graph G Laplacian matrix which is proportional to O(n³). The sampling technique is an effective method to lower the computational complexity. However, the sample points may not completely represent the whole data set. Fortunately, the commute time which is a random walk based metric can capture the geometry structure in the data set accurately. A commute time based spectral clustering algorithm (CTBSC) is designed in this paper. It uses cosine similarity rather than Gaussian kernel to construct the similarity matrix. And it can lower the computational cost of eigendecomposition by incorporating the algebraic transformation and commute time. Experiments in some datasets in UCI database show the effectiveness of the CTBSC.