PaVa: A novel path-based valley-seeking clustering algorithm

Lin Ma, Conan Liu, Tiefeng Ma, Shuangzhe Liu

Research output: Contribution to journalArticlepeer-review


Clustering methods are being applied to a wider range of scenarios involving more complex datasets, where the shapes of clusters tend to be arbitrary. In this paper, we propose a novel Path-based Valley-seeking clustering algorithm for arbitrarily shaped clusters. This work aims to seek the valleys among clusters and then individually extract clusters. Three vital techniques are used in this algorithm. First, path distance (minmax distance) is employed to transform the irregular boundaries among clusters, that is density valleys, into perfect spherical shells. Second, a suitable density measurement, k-distance, is employed to make adjustment on Minimum Spanning Tree, by which a robust minmax distance is calculated. Third, we seek the transformed density valleys by determining their centers and radii. Based on the vital techniques, the main contributions of the proposed algorithm can be summarized as follows. First, the clusters are wrapped in spherical shells after the distance transformation, making the extraction process efficient even with clusters of arbitrary shape. Second, adjusted Minimum Spanning Tree enhances the robustness of minmax distance under different kinds of noise. Last, the number of clusters does not need to be inputted or decided manually due to the individual extraction process. After applying the proposed algorithm to several commonly used synthetic datasets, the results indicate that the Path-based Valley-seeking algorithm is accurate and efficient. The algorithm is based on the dissimilarity of objects, so it can be applied to a wide range of fields. Its performance on real-world datasets illustrates its versatility.

Original languageEnglish
Article number120380
Pages (from-to)1-20
Number of pages20
JournalInformation Sciences
Publication statusE-pub ahead of print - Mar 2024


Dive into the research topics of 'PaVa: A novel path-based valley-seeking clustering algorithm'. Together they form a unique fingerprint.

Cite this