| Cluster analysis is one of the commonly used techniques in data mining.It aims to divide a data set into several small clusters in a way that the similarity of two objects in the same clusters is higher than that of two objects from different clusters.Cluster analysis can be used not only as a tool to explore the internal structural features of a data set but also as a preprocessing step for other data mining techniques such as classification,feature extraction,attribute subset selection,and so on.Cluster analysis has been widely applied in disciplines such as computer science,physics,economics,biology,and medicine.After decades of development,many mature theories and algorithms have been formed in the field of cluster analysis.Among them,hierarchical clustering has attracted extensive attention because of its simplicity and readily explicable.However,it still faces problems like inaccurate,high time complexity,and complex parameter tuning process.Representative point is a common concept in clustering algorithms.On the one hand,it can be used to compress data sets and capture their local features,on the other hand,it can also be used to find high-quality cluster centers based on which the clustering is accomplished through a remaining points allocation process.This thesis studies hierarchical clustering algorithms based on representative points aiming to improve efficiency.The main contributions of this thesis include two aspects.First,we propose a new hierarchical clustering algorithm Na NSyn C by integrating the principles of natural neighbors and synchronization dynamics.To get rid of the dependency on parameters,the definition of natural neighbor is introduced.To reduce the time complexity we use the feature that similar data objects in the synchronization-based clustering will gradually move to the same position.The concept of co-location representative point is proposed and applied to the hierarchical clustering framework to gradually reduce the number of data objects involved in the iterative process.Comparative experiments on commonly used synthetic data sets and UCI data sets prove that Na NSyn C is more efficient and is less reliant on parameters compared with synchronization-based clustering and its performance is also better than the recent RSC algorithm.Second,we propose another hierarchical clustering algorithm called HCLCS based on local cores and sharing concept.An extended representative point search algorithm based on the idea of sharing called ELORE is proposed which is used to get a rough partition of the data set.Then,a two-step hierarchical merging process is adopted.The first sub-step is to pre-connect the small clusters that belong very likely to the same category according to a proposed indicator that measures the stickiness between two clusters.The second sub-step is to perform a traditional hierarchical clustering process on the pre-connected intermediate clusters and the remaining unconnected small clusters.Experiments on synthetic data sets,UCI data sets,and KEEL data sets show that HCLCS is overall better than five comparison algorithms and it can identify clusters of arbitrary shapes.It also reduces the running time while improving the accuracy. |
