A two-phase strategy for nonconvex clusters integrating a spectral clustering with a merging technique

In this paper we address the problem of arbitrarily shaped clustering of points belonging to a linear space. Among the several approaches to clustering proposed in literature, the spectral clustering has become more and more popular for the case of arbitrarily shaped clusters. It depends on parameters whose choice can be critical. In order to reduce these criticalities, in this paper we propose a two-phase strategy that integrates the partitioning obtained by the spectral clustering with a merging technique which makes use only of the information already produced in the first phase by the spectral clustering. The main novelty of this approach is precisely the fact that no geometric tool is exploited in the merging phase. A numerical experimentation on artificial and real-world datasets has been performed to compare the proposed method with the spectral clustering and with two other widely used algorithms for non-convex problems, namely DBSCAN and Chameleon 2.

Automated summary

In this paper, a method for arbitrarily shaped clustering of points in a linear space is proposed. It integrates partitioning obtained by spectral clustering with a merging technique to reduce the criticalities caused by parameter choice. The experimental results show that the proposed method outperforms spectral clustering, DBSCAN, and Chameleon 2 algorithms for non-convex problems on both artificial and real-world datasets.