Path-Based Relative Similarity Spectral Clustering

Spectral clustering shows promising clustering results on many computer applications. But it will greatly affected by its scale parameter used in Gaussian kernel. Path-based spectral can alleviate the problem in some extend, but it will still be some shortcoming in the algorithm. In this paper, we propose a new kind of path-based spectral clustering, called path-based relative similarity spectral clustering. Inspired by LLE(Locally Linear Embedding), the proposed novel algorithm uses linear reconstruction weights to measure the similarity between adjacent points. Then based on the constructed connected graph, the new path-based similarity can be got. Experiments prove the algorithm´s efficiency. Also, we naturally extend the clustering method to semi-supervised clustering.