Density Backbone Clustering Algorithm Based on Adaptive Threshold

Abstract

The existing clustering algorithms are inaccurate to identify arbitrary clusters, sensitive to density changes within clusters, sensitive to outliers and difficult to determine the threshold. An adaptive threshold-constrained density cluster backbone clustering algorithm (DCBAT) is proposed to solve the problems. Firstly, the adaptive reachability density threshold is defined in combination with the skewness coefficient and points density mean. Under the constraint of the threshold, the core points with higher local densities and higher relative distances are grouped according to the reachability, and the initial clusters backbones are obtained. The non-core points are then assigned into the cluster which their nearest neighbors with higher density belong to. Finally, the adaptive density D-value threshold is proposed in combination with D-value mean and scale factor. According to the threshold, the initial cluster is separated at the point where the density varies sharply, and the final clusters are obtained. DCBAT fully considers the internal structure and distribution of the data when clustering, thereby improving the clustering performance. The performance of this algorithm is demonstrated compared with five excellent algorithms k-means,DBSCAN, OPTICS, CFDP and MulSim on eight datasets with various dimensions and types. DCBAT algorithm has the advantages of good recognition of arbitrary clusters, insensitivity to density changes within clusters, insensitivity to outliers and stable clustering result. Its overall performance is superior to comparison algorithms.

Keywords

• clustering; cluster backbone; reachability adaptive threshold of density; adaptive threshold of density d-value; arbitrary clusters