A novel clustering algorithm based on the natural reverse nearest neighbor structure. (September 2019)

• Record Type: Journal Article
• Authors: Dai, Qi-Zhu; Xiong, Zhong-Yang; Xie, Jiang; Wang, Xiao-Xia; Zhang, Yu-Fang; Shang, Jia-Xing
• Is Part Of: Information systems. Volume 84(2019)
• Page Start: 1
• Page End: 16
• Publication Date: 2019-09
• Subjects: Clustering -- Density core -- Natural neighbor -- Reverse-nearest neighbor; 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.2019.04.001
• Languages: English
• ISSNs: 0306-4379

Abstract

Abstract: Cluster analysis plays an important role in identifying the natural structure of the target dataset. It has been widely used in many fields, such as pattern recognition, machine learning, image segmentation, document clustering and so on. There are many different methods to conduct cluster analysis. Namely, most real datasets are non-spherical and have complex shapes. Although these methods are widely used to deal with clustering tasks, they are susceptible to noise and arbitrary shapes. Thus, we propose a novel clustering algorithm (called RNN-NSDC) in this paper, which is based on the natural reverse nearest neighbor structure. Firstly, we apply the reverse nearest neighbors in the algorithm to extract core objects. Secondly, our algorithm uses the neighbor structure information of core objects to cluster. And excluding noise effects, core sets can well represent the structure of clusters. Therefore, the RNN-NSDC can obtain the optimal cluster numbers for the datasets which contain clusters of outliers and arbitrary shapes. To verify the efficiency and accuracy of the RNN-NSDC, synthetic datasets and real datasets are used for experiments. The results indicate the superiority of the RNN-NSDC compared with K-means, DBSCAN, DPC, SNNDPC, DCore and NaNLORE. Highlights: The criterion of extracting the core objects is simple and efficient. There is no need to set parameters in RNN-NSDC. RNN-NSDC can be applied to complex patterns with extremely large variations in density. RNN-NSDC is robust to outliers and noises.