Spectral clustering with density sensitive similarity function

In recent years, spectral clustering has become quite popular for data analysis because it can be solved efficiently by standard linear algebra tools and do not suffer from the problem of local optima. The clustering effect by using such spectral method, however, depends heavily on the description of similarity between instances of the datasets. In this paper, we defined the adjustable line segment length which can adjust the distance in regions with different density. It squeezes the distances in high density regions while widen them in low density regions. And then a density sensitive distance measure satisfied by symmetric, non-negative, reflexivity and triangle inequality was present, by which we can define a new similarity function for spectral clustering. Experimental results show that compared with conventional Euclidean distance based and Gaussian kernel function based spectral clustering, our proposed algorithm with density sensitive similarity measure can obtain desirable clusters with high performance on both synthetic and real life datasets. (C) 2011 Elsevier B.V. All rights reserved.