Efficient algorithms for agglomerative hierarchical clustering methods (Q1057599)

Whenever n objects are characterized by a matrix of pairwise dissimilarities, they may be clustered by any of a number of sequential, agglomerative, hierarchical, nonoverlapping clustering methods. These SAHN clustering methods are defined by a paradigmatic algorithm that usually requires \(O(n^ 3)\) time, in the worst case, to cluster the objects. We describe a SAHN clustering algorithm that requires \(O(n^ 2 \log n)\) time in the worst case. When SAHN clustering methods exhibit reasonable space distortion properties, further improvements are possible. We adapt a SAHN clustering algorithm, based on the efficient construction of nearest neighbor chains, to obtain a reasonably general SAHN clustering algorithm that requires in the worst case \(O(n^ 2)\) time and space. Whenever n objects are characterized by k-tuples of real numbers, they may be clustered by any of a family of a centroid SAHN clustering methods. These methods are based on a geometric model in which clusters are represented by points in k-dimensional real space and points being agglomerated are replaced by a single (centroid) point. For this model, we have solved a class of special packing problems involving point- symmetric convex objects and have exploited it to design an efficient centroid clustering algorithm.