A multi-stage hierarchical clustering algorithm based on centroid of tree and cut edge constraint

Abstract The minimum spanning tree clustering algorithm is known to be capable of detecting clusters with irregular boundaries. The paper presents a novel hierarchical clustering algorithm based on minimum spanning tree (MST), which tends to reduce the complexity of the merging process with guaranteed clustering performance. There are two core ideas in the proposed method: (1) The inter-cluster distance is calculated with the centroid of MST instead of the center of cluster. (2) The length of cut edge at the intersection of two adjacent clusters is taken as a merge condition. Based on this idea, we propose a three-stage MST-based hierarchical clustering algorithm (CTCEHC). In Stage 1, a preliminary partition is performed with the degrees of vertices in MST. In Stage 2, small subclusters are merged via the geodesic distance between the centroids of MST in two clusters and the cut edge constraint I. In Stage 3, the adjacent cluster pairs satisfying the cut edge constraint II are merged. The experimental results on the synthetic data sets and real data sets demonstrate a good performance of the proposed clustering method.