Efficient MST-based clustering with leader node selection and outlier edge cutting

The clustering algorithm based on the minimum spanning tree (MST) can identify clusters of different shapes. However, the minimum spanning tree clustering algorithm has a high computational cost due to multiple rounds of traversing required during the construction and edge-breaking clustering phases. To address this issue, a density peak fusion idea is proposed, which utilizes kd-trees to obtain neighborhoods and designs leader nodes to propose an algorithm that reduces the time cost of the minimum spanning tree. The main idea of the algorithm is that nodes with higher density than surrounding nodes are used to replace the nodes participating in the formation of the minimum spanning tree. By using the selection technique of density peaks, the number of points required for initial construction and subsequent traversal of the minimum spanning tree is reduced, thereby reducing the complexity of the minimum spanning tree and achieving faster clustering speed. The algorithm has been tested on various synthetic and real datasets. It has achieved significant improvements in speed and clustering performance. Compared with the most advanced mst-based clustering algorithm, the algorithm has a speed increase of at least 30% and a performance increase of about 5%.