Density Peaks Clustering Combining Relative Local Density and Nearest Neighbor Relationship

Abstract

When the density peaks algorithm deals with datasets with different densities, the wrong center points may be selected, and the problem of associated errors may occur in the sample allocation process. To solve the above problems, a density peaks clustering algorithm based on the relative local density and nearest neighbor relationship is proposed. The weights of sparse balance are introduced into the definition of local density, and the definition of relative local density is proposed. The density peak can be found according to the relative local density, which avoids the error of selecting the density peak in the dataset with large sparse differences, and ensures the accuracy of the center point selection. The nearest neighbor allocation strategy is proposed by combining the nearest neighbor criterion and threshold limit to suppress the allocation error effectively. The modified allocation strategy based on the mean value of the distance within the class is proposed to enhance the accuracy of the algorithm for boundary point clustering. The proposed algorithm is compared with DPC, DPC-MND, FKNN-DPC, DBSCAN, OPTICS, AP, and K-means algorithms on 5 synthetic datasets and 5 UCI datasets, and the experimental results demonstrate that the proposed algorithm has sound clustering performance in metrics of adjusted mutual information, adjusted Rand index, and Fowlkes-Mallows index. Friedman test shows that the algorithm has the best performance.

Keywords

• clustering algorithm; density peaks; relative local density; nearest neighbor relations; allocation strategy