A spectral clustering method combining path with density

Clustering is one of the building blocks of modern data analysis such as image processing, data mining, and pattern recognition. Path-based spectral clustering is an important approach for clustering, which has delivered impressive results in some challenging tasks. However this algorithm has huge time costing due to the number of paths will dramatically rise with the increase of dataset size. For this problem, this paper proposes a novel spectral clustering method that utilizes the density of dataset to limit the scope of paths instead of finding all the paths. Experiments on synthetic as well as real world data sets and the run time of algorithms demonstrate that the proposed method outperforms the path-based algorithm.