Multi-granularity principal curves extraction based on improved spectral clustering of complex distribution data

Abstract In order to address the problem of instability of existing principal curve algorithms and their difficulties to deal with complex distribution data, in this study, invoking the ideas of information granulation, we propose a local-to-global multi-granularity principal curves extraction approach based on improved spectral clustering. Firstly, we propose an improved spectral clustering algorithm based on inflection point estimation to granulate complex distribution data into several granular data, and develop techniques of an automatic selection of a parameter, which determines the number of clusters (granular data). Secondly, PL (polygonal line) principal curves algorithm proposed by Kegl is utilized to extract the local principal curves of each granular data. Finally, with the use of the shortest Hamiltonian path algorithm and noise variance, the local principal curves are gradually connected together to form a global curve. A number of numeric studies completed for synthetic and publicly available data sets provide a useful quantifiable insight into the effectiveness of the proposed algorithm.