A robust strategy based on spectral clustering and a merging technique for the non convex clustering

In this paper we address the problem of arbitrarily shaped clustering of points belonging to a linear space. A powerful method for finding this kind of structure is the spectral clustering which often outperforms traditional clustering algorithms such as k-means. It acts through the eigenvectors of a matrix which describes the similarity between pairs of data points. Two important items contribute to the construction of this similarity matrix: the sparsity of the underlying weighted graph and the similarity function, in general a Gaussian which depends on a scale parameter ? to be selected. Both issues are critical and in this paper we propose a heuristic strategy which reduces these criticalities by performing first a partition, by means of a spectral clustering in a number of convex clusters k sufficiently greater than the target one, and then a merging technique which makes use only of the information already produced. A numerical experimentation on artificial dataset has been carried out to compare the performances of the spectral clustering with the proposed method.