WC-KNNG-PC : Watershed clustering based on k-nearest-neighbor graph and Pauta Criterion

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

27 Scopus Citations
View graph of relations

Author(s)

  • Jianhua Xia
  • Jinbing Zhang
  • Yang Wang
  • Lixin Han
  • Hong Yan

Related Research Unit(s)

Detail(s)

Original languageEnglish
Article number108177
Journal / PublicationPattern Recognition
Volume121
Online published23 Jul 2021
Publication statusPublished - Jan 2022

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.

Research Area(s)

  • K-nearest neighbor graph (KNNG), Pauta criterion, Shared nearest neighbor (SNN), Watershed clustering

Citation Format(s)

WC-KNNG-PC: Watershed clustering based on k-nearest-neighbor graph and Pauta Criterion. / Xia, Jianhua; Zhang, Jinbing; Wang, Yang et al.
In: Pattern Recognition, Vol. 121, 108177, 01.2022.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review