A fast hierarchical clustering approach based on partition and merging scheme

Hierarchical clustering is one major kind of clustering approaches. As far as we know, given n data points, the time complexity of most existing hierarchical clustering approaches is O(n). Although some state-of-the-art fast hierarchical clustering approaches have lower time complexity, their clustering accuracy is sacrificed and sensitive to some certain data distribution types. This paper therefore presents a partition-and-merging scheme for fast hierarchical clustering, which divides data objects into proper groups and merges them within their groups to save computation cost. Since both spatial distance and density difference, which contain local and global distribution information of data, are considered in the merging stage, the proposed approach has outstanding performance in terms of effectiveness, efficiency and robustness. Experimental results show the promising results in comparison with the existing counterparts.

I. Introduction

Clustering analysis has been widely used in a variety of scientific areas, e.g. see [1]–[4]. As one of major kind of clustering approach, hierarchical clustering (HC) provides more data details by incorporating data objects into different hierarchies. Traditional HC approaches, i.e. single-linkage HC (SLHC), average-linkage HC (ALHC), and complete-linkage HC (CLHC) [5], can just cope with one or more certain data types. For instance, SLHC works well for data set with well-separated clusters and the other two have good performance on data set with spherical-shaped clusters [6]. To cope with this issue, ensemble-based HC approaches [7] [8] have been proposed to improve the robustness of traditional HC approaches by combining the HC results produced by multiple HC approaches. However, their computation cost is even higher than the traditional ones, which limits their application to a certain degree.