Natural Neighbor Density Extremum Clustering Algorithm

doi:10.3778/j.issn.1002-8331.2107-0529

Abstract

Abstract:

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

摘要：

针对密度峰值聚类算法存在数据集密度差异较大时，低密度区域聚类中心难以检测和参数敏感的问题，提出了一种新型密度极值算法。引入自然邻居概念寻找数据对象自然近邻，定义椭圆模型计算自然稳定状态下数据局部密度；计算数据对象余弦相似性值，用余弦相似性值来更新数据对象连通值，采用连通值划分高低密度区域和离群点；构造密度极值函数找到高低密度不同区域聚类中心点；将不同区域非聚类中心点归并到离其最近的聚类中心所在簇中。通过在合成数据集和UCI公共数据集实验分析：该算法比其他对比算法在处理密度分布差异较大数据集上取得了更好的结果。

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

ZHANG Zhonglin, ZHAO Yu, YAN Guanghui. Natural Neighbor Density Extremum Clustering Algorithm[J]. Computer Engineering and Applications, 2021, 57(23): 200-210.

张忠林，赵昱，闫光辉. 自然邻居密度极值聚类算法[J]. 计算机工程与应用, 2021, 57(23): 200-210.

References

[1] 王洋，张桂珠.自动确定聚类中心的密度峰值算法[J].计算机工程与应用，2018，54（8）：137-142.
WANG Y，ZHANG G Z.Automatically determine density of cluster center of peak algorithm[J].Computer Engineering and Applications，2018，54（8）：137-142.
[2] DUTTA S，SENGUPTA S.Implementation of K-means clustering in ECB framework of cloud computing environment[C]//2017 7th International Conference on Cloud Computing，Data Science & Engineering-Confluence IEEE，2017：293-297.
[3] KHAN S S，AHMAD A.Cluster center initialization algorithm for K-means clustering[J].Pattern Recognition Letters，2004，25（11）：1293-1302.
[4] PAL S，BALAKRISHNAN N.Likelihood inference based on EM algorithm for the destructive length-biased Poisson cure rate model with Weibull lifetime[J].Commun Stat Simul Comput，2018，47（3）：644-660.
[5] ESTER M，KRIEGEL H P，SANDER J，et al.A density-based algorithm for discovering clusters in large spatial databases with noise[C]//Proceedings of the 2nd International Conference on Knowledge Discovery and Data，1996：226-231.
[6] BRYANT A，CIOS K.RNN-DBSCAN：a density-based clustering algorithm using reverse nearest neighbor density estimates[J].IEEE Transactions on Knowledge and Data Engineering，2018，30（6）：1109-1121.
[7] AGRAWAL R，GEHRKE J，GUNOPULOS D，et al.Automatic subspace clustering of high dimensional data for data mining applications[C]//Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data，1998：94-105.
[8] BEZDEK J C，EHRLICH R，FULL W.FCM：the fuzzy c-means clustering algorithm[J].Computers & Geosciences，1984，10（2/3）：191-203.
[9] RODRIGUEZ A，LAIO A.Clustering by fast search and find of density peaks[J].Science，2014，344（6191）：1492-1496.
[10] 陈叶旺，申莲莲，钟才明，等.密度峰值聚类算法综述[J].计算机研究与发展，2020，57（2）：378-394.
CHEN Y W，SHEN L L，ZHONG C M，et al.Survey on density peak clustering algorithm[J].Journal of Computer Research and Development，2020，57（2）：378-394.
[11] 杜沛，程晓荣.一种基于K近邻的比较密度峰值聚类算法[J].计算机工程与应用，2019，55（10）：161-168.
DU P，CHENG X R.Comparative density peaks clustering based on K-nearest neighbors[J].Computer Engineering and Applications，2019，55（10）：161-168.
[12] GUO Z，HUANG T，CAI Z，et al.A new local density for density peak clustering[C]//Pacific-Asia Conference on Knowledge Discovery and Data Mining.Cham：Springer，2018：426-438.
[13] 金辉，钱学忠.自然最近邻优化的密度峰值聚类算法[J].计算机科学与探索，2019，13（4）：711-720.
JIN H，QIAN X Z.Optimized density peak clustering algorithm by natural nearest neighbor[J].Journal of Frontiers of Computer Science and Technology，2019，13（4）：711-720.
[14] WANG S L，LI Q，ZHAO C F，et al：Extreme clustering-a clustering method via density extreme points[J].Inf Sci，2021，542：24-39.
[15] CHENG D D，HUANG J L，ZHANG S L，et al.Improved density peaks clustering based on shared-neighbors of local cores for manifold data sets[J].IEEE Access，2019，7：151339-151349.
[16] CAO L，ZHANG X Y，WANG T，et al.An adaptive ellipse distance density peak fuzzy clustering algorithm based on the multi-target traffic radar[J].Sensors，2020，20（17）：4920.
[17] 周洁，姜志彬，张远鹏，等.基于密度的模糊代表点聚类算法[J].控制与决策，2020，35（5）：1123-1133.
ZHOU J，JIANG Z B，ZHANG Y P，et al.A density-based fuzzy exemplar clustering algorithm[J].Journal of Control and Decision，2020，35（5）：1123-1133.
[18] HAWKINS D.Identification of outliers[M].London：Chapman and Hall，1980.
[19] MOONESINGHE H　D K，TAN　Pangning.Outlier detection using random walks[C]//Proceedings of ICTAI，2006：532-539.
[20] ZHU Q S，FENG J，HUANG J L.Natural neighbor：a self-adaptive neighborhood method without parameter K[J].Pattern Recognition Letters，2016，80：30-36.
[21] CHENG D D，ZHU Q S，HUANG J L，et al.Natural neighbor based clustering algorithm with local representatives[J].Knowl Based Syst，2017，123：238-253.
[22] HUANG J L，ZHU Q S，YANG L J，et al.A non-parameter outlier detection algorithm based on natural neighbor[J].Knowl Based Syst，2016，92：71-77.
[23] YANG L J，ZHU Q S，HUANG J L.et al.Adaptive edited natural neighbor algorithm[J].Neurocomputing，2017，230：427-433.
[24] LIU R，WANG H，YU X M.Shared-nearest-neighbor-based clustering by fast search and find of density peaks[J].Inf Sci，2018，450：200-226.
[25] ZHAO S W，LI J N.ELS：a fast parameter-free edition algorithm with natural neighbors-based local sets for k nearest neighbor[J].IEEE Access，2020，8：123773-123782.
[26] ERIC P.Smith：an introduction to statistical modeling of extreme values[J].Technometrics，2002，44（4）：397.
[27] HUANG D，WANG C，WU J，et al.Ultra-scalable spectral clustering and ensemble clustering[J].IEEE Transactions on Knowledge and Data Engineering，2020，32：1212-1226.