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 findingthis kind of structure is the spectral clustering which often outperforms traditional clustering algorithms such as k-means. It acts through theeigenvectors 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 graphand 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 criticalitiesby 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.