Research And Application Of Density Peak Clustering Algorithm Based On Density Decay Graph

Human societies produce a vast assortment of data every day,with the arrival of the era of big data.The main task of data mining is to extract useful information from these huge and complex data.Clustering analysis is one of the most important methods of data mining.Clustering analysis,as an unsupervised learning method,aims to mine the hidden information behind data without prior knowledge.Clustering algorithms can be divided into five categories: partition based clustering algorithm,density based clustering algorithm,hierarchical based clustering algorithm,grid based clustering algorithm and model based clustering algorithm.The density based clustering algorithm is one of the most well-known clustering algorithms,which is also the focus of this thesis.In recent years,the density peak clustering algorithm(DPC)proposed by Rodriguez and Laio has become a research hotspot in the field of clustering analysis because of its simplicity and efficiency.Its related research results have been widely used in image processing,information security,big data and other application fields.However,there are two known drawbacks in DPC: first,it is difficult to select the appropriate cluster center through the decision graph on certain data sets;second,DPC has the so-called “chain reaction” problem.Since DPC was proposed,many researchers have proposed a lot of excellent improvement methods for these two drawbacks,such as FKNN-DPC of Xie et al.,IVDPC of Zhou et al.,FDPC of Xu,Xiao et al.Although these methods alleviate the problem in varying degrees,the problem has not been completely solved.This thesis focuses on how to solve these two problems of DPC and our contributions are as follows:(1)This thesis summarizes the theoretical knowledge of data mining and cluster analysis.The definitions,process steps,algorithms and evaluation methods of cluster analysis are expounded comprehensively and systematically.The latest research results in this field are sorted out and introduced.Through comparative analysis,the advantages and disadvantages of the new algorithm are summarized.(2)A new clustering method,density decay graph based density peak clustering(DGDPC),is proposed.Inspired by the decay phenomenon,a phenomenon which is common in nature,we proposed the core concept of DGDPC density-decay-graph.DGDPC first forms the initial cluster according to the density-decay-graph,then merges the cluster through a simple strategy and obtains the final result.The algorithm does not need to select cluster centers manually,and alleviates the problem of chain reaction.Although DGDPC introduces an additional parameter m,m is robust and easy to be determined in advance.Experiments on 10 synthetic data sets and 10 real data sets show that the algorithm is better than DPC,DGB,K-means,DBSCAN and single-link in most cases.(3)In order to verify the practicability of DGDPC,DSMS,a new 3D model mesh segmentation method combining DGDPC with shape diameter function(SDF),is proposed.The algorithm first calculates the thickness of the centroid of each facet in the mesh(the thickness is obtained by the SDF value after some post-processing steps);then,through the algorithm processes similar to DGDPC,the mesh is segmented by using the thickness decay graph.The user can control the number of blocks in the segmentation result by adjusting the parameter m.DSMS has good stability and consistency,and the degree of manual intervention is low.Experiments on classic 3D models show that DSMS is better than K-means based mesh segmentation method in most cases.