A local mean-based distance measure for spectral clustering

Spectral clustering has become very popular in recent years, due to the simplicity of its implementation and good performance in clustering non-convex data. Constructing a similarity graph based on an appropriate distance measure for modeling the local neighborhood relations among data samples is crucial for achieving an acceptable performance in spectral clustering. In this paper, we propose a fuzzy spectral clustering algorithm for poorly separated data with arbitrary shapes. Distinguishing poorly separated clusters is a challenging issue since a border point of a cluster may be more similar to the border points of the adjacent cluster than to the points in its own cluster. We propose a local mean-based distance measure which helps in separating points in cluster borders. The distance between a pair of points, in the proposed distance measure, is defined as the distance between the mean of their k nearest neighbors. We also propose a new transitive-based method for computing the membership degrees of points to clusters. Our evaluation results on both artificial and real data show that both the proposed local mean-based distance measure and the proposed membership computation method have significant impacts in obtaining performance improvement over the existing methods.