A novel graph-based clustering method using noise cutting. (July 2020)

• Record Type: Journal Article
• Authors: Li, Lin-Tao; Xiong, Zhong-Yang; Dai, Qi-Zhu; Zha, Yong-Fang; Zhang, Yu-Fang; Dan, Jing-Pei
• Is Part Of: Information systems. Volume 91(2020)
• Publication Date: 2020-07
• Subjects: Graph-based clustering -- Natural neighbors -- Noise cutting; Database management -- Periodicals; Electronic data processing -- Periodicals; Bases de données -- Gestion -- Périodiques; Informatique -- Périodiques; Database management; Electronic data processing; Periodicals; 005.7
• DOI: 10.1016/j.is.2020.101504
• Languages: English
• ISSNs: 0306-4379

Abstract

Abstract: Recently, many methods have appeared in the field of cluster analysis. Most existing clustering algorithms have considerable limitations in dealing with local and nonlinear data patterns. Algorithms based on graphs provide good results for this problem. However, some widely used graph-based clustering methods, such as spectral clustering algorithms, are sensitive to noise and outliers. In this paper, a cut-point clustering algorithm (CutPC) based on a natural neighbor graph is proposed. The CutPC method performs noise cutting when a cut-point value is above the critical value. Normally, the method can automatically identify clusters with arbitrary shapes and detect outliers without any prior knowledge or preparatory parameter settings. The user can also adjust a coefficient to adapt clustering solutions for particular problems better. Experimental results on various synthetic and real-world datasets demonstrate the obvious superiority of CutPC compared with k-means, DBSCAN, DPC, SC, and DCore. Highlights: The strategy of detecting out the noise points is straightforward and efficient. It is able to detect clusters with arbitrary shapes and outliers automatically. The proposed approach does not require any parameters from users. The method has the superiority compared with the other described in the paper.