Density-based clustering using approximate natural neighbours

Maia Angelova, Gleb Beliakov, Ye Zhu*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


We propose a computationally efficient natural neighbour based metric for discovering clusters of arbitrary shape based on fuzzy measures. The approximate natural neighbours are found with the help of the Choquet integral with respect to a specially designed two-additive fuzzy measure. Fuzzy betweenness relation is used to construct such a measure and helps determine the natural neighbours of a query point. The natural neighbours of a datum allow the computation of point density estimate, which in turn defines a density-based metric suitable for clustering. The proposed method overcomes the exponential computational complexity of the Delaunay triangulation traditionally used to identify the natural neighbours. The run-time of the density estimate by this metric keeps the same quadratic trends as the Euclidean distance based estimates with respect to the data size. Empirical evaluation based on 20 synthetic and real-world datasets shows that this metric has a higher clustering accuracy for existing state-of-the-art density-based clustering algorithms, such as DBSCAN, SNN and DP. Furthermore, the proposed metric is easily combined with these algorithms, and the enhanced clustering algorithms inherit positive features such as resistance to noise and imbalanced data.

Original languageEnglish
Article number105867
Number of pages10
JournalApplied Soft Computing
Publication statusPublished - 4 Dec 2019

Bibliographical note

Publisher Copyright:
© 2019 Elsevier B.V.


  • Choquet integral
  • Clustering
  • Density estimate
  • Fuzzy betweenness relation
  • Fuzzy measure


Dive into the research topics of 'Density-based clustering using approximate natural neighbours'. Together they form a unique fingerprint.

Cite this