A geometric-based clustering method using natural neighbors

Neighborhood-based and density-based clustering methods are applied in various data analysis applications. However, most of them have low performance in mixed heterogeneous datasets, and high computational cost. To mitigate these challenges, in this paper, a geometric-based clustering method is proposed which uses the concept of natural neighborhoods to extract the local density of data points. At the first stage of the algorithm, primary clusters are formed by identifying dense points that have a higher number of natural neighbors. Then, the heads of the clusters are extracted in dense points, based on the local natural density criterion. Afterward, a novel natural neighborhood-based method is applied to identify the points having a low number of natural neighbors, which called weak or noise data points. Finally, the desired clusters are obtained by ignoring the weak/noise points. The computational complexity of the proposed method is O(nlogn). The proposed method is independent of any specific parameter setting. The results of experiments on benchmark datasets confirm that it achieves a higher performance compared to the competitors.