Fuzzy weighted natural nearest neighbor based density peak clustering

DPC (density peaks clustering) algorithm has garnered widespread attention due to its novelty and superior performance. However, it is sensitive to the arbitrary cutoff distance, and its very efficient assignment strategy is prone to leading “domino effect”. Although FKNN-DPC and other variants addressed DPC’s limitations somewhat, the arbitrarily fixed number of neighbors to calculate the local density of a point will bring the bias, particularly for the dataset containing dense and sparse clusters simultaneously, resulting in the bias to cluster centers and that in the final clustering. To remedy these limitations, this paper proposes a novel Fuzzy Weighted Natural Nearest Neighbor based parameter-free Density Peak clustering algorithm named FWNNN-DPC. It proposes a novel local density of a point utilizing its natural nearest neighbors by assuming that there is at least one “true friend” for a point when its natural nearest neighborhood is empty. Furthermore, a novel divide-and-conquer assignment strategy is proposed, which assigns non-outliers and outliers to the most appropriate clusters utilizing natural nearest neighbors based shortest distance principle, and fuzzy weighted natural nearest neighbors based membership degree, respectively. Extensive experiments on benchmark datasets and the statistic test demonstrate that the proposed FWNNN-DPC outperforms DPC and its variants, and the typical clustering algorithms DBSCAN and K-means.