Clustering algorithm using the matrix transformation based commute time embedding

Spectral clustering can perform globally optimized clustering. However, its computational complexity of eigendecomposition is O(n³). The use of the sampling technique may be an effective way to signi_cantly reduce the computational complexity. Unfortunately, a lot of data set information may be lost by using the sampling technique. A clustering algorithm using the matrix transformation based commute time embedding (CMTCE) is designed in this paper. It uses the matrix transformation technique to accelerate the construction of the commute time which is embedded in the Laplacian eigenspace. CMTCE can quickly capture the geometry structure in the data set without involving the sampling technique. Experiments in several data sets with various data size in UCI database show that CMTCE is more accurate and is faster than that of some other clustering algorithms.