Fast Minimum Spanning Tree Clustering Algorithm Based on Granular-Ball Computing
摘要
Distance measure is a key issue in clustering analysis. Most existing clustering algorithms, like K-means and density peaks clustering, use Euclidean distance to measure the dissimilarity between objects, making it difficult for discovering irregular-shaped clusters. Some algorithms specially designed for recognizing irregular-shaped clusters have high time complexity. In this paper, we introduce granular-ball (GB) into clustering and use the neighbors of the boundary objects of granular-balls to quantitatively evaluate the distance between granular-balls. By combining minimum spanning tree (MST)-based clustering algorithm, we propose a GB-based MST clustering algorithm, called GB-MST. Since GB model is a multi-granularity data representation and the number of GBs is far less than that of objects in a dataset, the proposed algorithm greatly reduces the running time of MST-based clustering algorithms and the effective distance between GBs makes it suitable for discovering irregular-shaped clusters. The experiment results on synthetic and real datasets have shown that GB-MST outperforms the compared algorithms in terms of time and effectiveness in discovering irregular-shaped clusters.