TY - JOUR
T1 - PaVa
T2 - A novel path-based valley-seeking clustering algorithm
AU - Ma, Lin
AU - Liu, Conan
AU - Ma, Tiefeng
AU - Liu, Shuangzhe
N1 - Funding Information:
We extend our sincere gratitude to the Editors and Reviewers for their invaluable comments and insights, which have greatly enriched the presentation of this manuscript. Special thanks are due to Dr. Qijing Yan for her thoughtful discussions and collaborative efforts. The completion of this research was made possible through the support of the Ministry of Education in China under the Project of Humanities and Social Sciences (No. 23YJCZH259 ).
Publisher Copyright:
© 2024 Elsevier Inc.
PY - 2024/3
Y1 - 2024/3
N2 - 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.
AB - 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.
KW - Adjusted minimum spanning tree
KW - Arbitrarily shaped cluster
KW - k-distance
KW - Minmax distance
KW - Valley-seeking
UR - http://www.scopus.com/inward/record.url?scp=85186767327&partnerID=8YFLogxK
U2 - 10.1016/j.ins.2024.120380
DO - 10.1016/j.ins.2024.120380
M3 - Article
AN - SCOPUS:85186767327
SN - 0020-0255
VL - 665
SP - 1
EP - 20
JO - Information Sciences
JF - Information Sciences
M1 - 120380
ER -