Abstract: Spectral clustering algorithms are influenced by the mesoscale factors of metrics, and similarity measured by Euclidean distance is not always accurate. In view of this situation, a spectral clustering algorithm based on transitive distance is proposed. The main idea contains three steps. First, a minimum spanning tree is constructed to do a similarity transformation, as a result a transfer matrix is generated. Second, we construct a Laplacian matrix by the transfer matrix of the first step. Data is projected into the eigen-space of this Laplacian matrix. Lastly, the clustering in the space of the second step is done. The experimental results on artificial data sets and UCI data sets show that the spectral clustering algorithm based on the transitive distance has good robustness and effectiveness.

Key words: spectral clustering, mesoscale factors, transitive distance, transitive matrix