Computer Engineering and Applications ›› 2021, Vol. 57 ›› Issue (23): 200-210.DOI: 10.3778/j.issn.1002-8331.2107-0529

• Pattern Recognition and Artificial Intelligence • Previous Articles     Next Articles

Natural Neighbor Density Extremum Clustering Algorithm

ZHANG Zhonglin, ZHAO Yu, YAN Guanghui   

  1. School of Electronics and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730000, China
  • Online:2021-12-01 Published:2021-12-02



  1. 兰州交通大学 电子与信息工程学院,兰州 730000


The density peak algorithm can find non-spherical clusters of any shape, but there are problems that the cluster centers of low-density regions are difficult to detect and the parameters are sensitive when the density of the data set is large, a new density extreme value algorithm is proposed. First, the concept of natural neighbors is introduced to find the natural neighbors of the data object, and the ellipse model is defined to calculate the local density of the data in the natural stable state. Second, it calculates the cosine similarity value of the data object, uses the cosine similarity value to update the connected value of the data object, and uses the connected value to divide the high and low density regions and outliers. Then, it uses the construction density extreme value function to find the different density regions. Finally, it merges the non-cluster center points of different regions into the cluster where the nearest cluster center is located. Through experimental analysis on the synthetic data set and UCI public data set, this algorithm has achieved better results than other comparison algorithms in processing data sets with large differences in density distribution.

Key words: clustering, natural neighbor, density adaptive distance, anchor points, connected value, density extreme



关键词: 聚类, 自然邻居, 密度自适应距离, 锚点, 连通值, 密度极值