Agglomerative Hierarchical Clustering (AHC) methods play an important role in the science of classification. In this paper, We present exact centroid and median AHC algorithms and an approximate single-link AHC algorithm for clustering data objects in the d-D space for any constant integer d ≥ 2; the time and space bounds of all our algorithms are O(n log n) and O(n), where n is the size of the input data set. Previously best algorithmic approaches for these three methods take at least quadratic time in the worst case. We implemented these AHC algorithms, and the experimental results show that our algorithms are quite efficient and practical.
展开▼
