WC-KNNG-PC: Watershed clustering based on k-nearest-neighbor graph and Pauta Criterion. (January 2022)

• Record Type: Journal Article
• Authors: Xia, Jianhua; Zhang, Jinbing; Wang, Yang; Han, Lixin; Yan, Hong
• Is Part Of: Pattern recognition. Volume 121(2022)
• Publication Date: 2022-01
• Subjects: Watershed clustering -- K-nearest neighbor graph (KNNG) -- Pauta criterion -- Shared nearest neighbor (SNN); Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2021.108177
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: Propose a new watershed clustering based on k -nearest-neighbor graph and Pauta Criterion to deal with complex dataset. Introduce neighbor information and Pauta Criterion to altitude and point-to-point aggregation. propose a two-step immersion to accomplish the point-to-point aggregation. This algorithm utilize stability to determine outliers and mergeable subclusters. The algorithm presents a basin-level similarity measure to merge sub-clusters. Abstract: Watershed clustering utilizes the concept of watershed algorithm to process clustering or cluster analyzes. The most attractive characteristic of this method is the capability to determine automatically the number of clusters from the data sets. However, in terms of the literature, the purposes of the original watershed clustering algorithm and the improved version are the detection of the clusters within two-dimensional linear data sets. In order to enable watershed clustering to deal with the dataset with multiple dimensions and nonlinear structures, we introduce k -nearest neighbor graph (KNNG), the shared nearest neighbor method and Pauta Criterion into watershed clustering to present a new watershed graph clustering with noise detection, WC-KNNG-PC. This approach first calculates a KNNG for the data sets, and then compute catchment basins (subclusters), basin immersions (connectivity between basins) and outliers. To prevent the merger of illegal subclusters, a maximum normalization stability factor, based on t -nearest neighbors and angle, MNSF, is proposed to detect the invalid basin immersions. Finally, a basin level similarity using median criterion is presented to merge the catchment basins to obtain the final clustering. Experiments on complex synthetic datasets and multidimensional real-world datasets have successfully demonstrated that the performance of the WC-KNNG-PC in clustering some various dimensional and complex datasets with heterogeneous density and diverse shapes.