A three-way density peak clustering method based on evidence theory

摘要

Density peaks clustering (DPC) algorithm is an efficient and simple clustering method attracting the attention of many researchers. However, its strategy of assigning each non-grouped object to the same cluster depends on its nearest neighbors having a higher local density. This may lead to the cluster label error propagation problem, i.e. if an object is wrong-labeled during the clustering process, its label will be propagated in the subsequent assignment. To overcome this defect, in this paper we propose a three-way density peak clustering method based on evidence theory, referred to as 3W-DPET. 3W-DPET forms clusters as interval sets using three-way clustering representation including three disjoint regions called positive region (POS), boundary region (BND) and negative region (NEG). 3W-DPET mainly consists of three steps: (1) finding out cluster centers and noises before clustering; (2) using a midrange distance comparison method to detect positive regions of clusters; and (3) allocating the remaining non-grouped objects, including noises, to the boundary region or the negative region of clusters. The distinguishing feature of 3W-DPET is that evidence theory is used to construct and collect the information of K-nearest neighbors in order to assign non-grouped objects to the most suitable cluster, which can effectively solve the problem of cluster label error propagation. In order to validate 3W-DPET, we test it on 18 datasets using three benchmarks (ACC, ARI and NMI), and compare it to K-means, FCM, DPC, KNN-DPC, DPCSA, SNN-DPC and CE3-kmeans methods. Experimental results suggest that 3W-DPET can effectively find clusters and its results conform with human cognition.