PaVa: a novel Path-based Valley-seeking clustering algorithm
Lin Ma Conan Liu Tiefeng Ma Shuangzhe Liu
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 radius. 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.