A clustering algorithm based on maximal θθ-distant subtrees

This paper presents a clustering algorithm based on maximal θθ-distant subtrees, the basic idea of which is to find a set of maximal θθ-distant subtrees by threshold cutting from a minimal spanning tree and merge each of their vertex sets into a cluster, coupled with a post-processing step for merging small clusters. The proposed algorithm can detect any number of well-separated clusters with any shapes and indicate the inherent hierarchical nature of the clusters present in a data set. Moreover, it is able to detect elements of small clusters as outliers in a data set and group them into a new cluster if the number of outliers is relatively large. Some computer simulations demonstrate the effectiveness of the clustering scheme.