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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Fast Minimum Spanning Tree Clustering Algorithm Based on Granular-Ball Computing

  • Xiaocui Jiang,
  • Dongdong Cheng,
  • Jinlong Huang,
  • Sulan Zhang

摘要

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.