DenMune: Density peak based clustering using mutual nearest neighbors. (January 2021)

• Record Type: Journal Article
• Authors: Abbas, Mohamed; El-Zoghabi, Adel; Shoukry, Amin
• Is Part Of: Pattern recognition. Volume 109(2021)
• Publication Date: 2021-01
• Subjects: Clustering -- Mutual neighbors -- Dimensionality reduction -- Arbitrary shapes -- Pattern recognition -- Nearest neighbors -- Density peak; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2020.107589
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: We present a novel algorithm (pseudo code given) to find clusters of arbitrary number, shapes and densities in two-dimensions. Higher dimensions are first reduced to 2-D using the t-sne algorithm. The algorithm relies on a single parameter K (the number of nearest neighbors). The algorithm proposes a simple rule that classifies the data points into three types: those that certainly belong to clusters/ certainly do not belong to any cluster (i.e. noise) and uncertain points (that either succeed to join a cluster or are considered, also, as noise). The performance of the proposed algorithm is compared to nine well known algorithms using thirty-six real and synthetic data sets. The results show the superiority of the proposed algorithm. Graphical abstract: Abstract: Many clustering algorithms fail when clusters are of arbitrary shapes, of varying densities, or the data classes are unbalanced and close to each other, even in two dimensions. A novel clustering algorithm "DenMune" is presented to meet this challenge. It is based on identifying dense regions using mutual nearest neighborhoods of size K, where K is the only parameter required from the user, besides obeying the mutual nearest neighbor consistency principle. The algorithm is stable for a wide range of values of K . Moreover, it is able to automatically detect and remove noise from the clustering process as well as detecting the target clusters. It produces robust results on various low and high dimensional datasets relative to several known state of the art clustering algorithms.