Efficient algorithms for divisive hierarchical clustering with the diameter criterion (Q1176597)

Divisive hierarchical clustering algorithms with the diameter criterion proceed by recursively selecting the cluster with largest diameter and partitioning it into two clusters whose largest diameter is the smallest possible. We provide two such algorithms with complexities \(O(\overline{M} N^ 2)\) and \(O(N^ 2\log N)\), respectively, where \(\overline{M}\) denotes the maximum number of clusters in a partition and \(N\) the number of entities to be clustered. The former algorithm, an efficient implementation of an algorithm of \textit{L. Hubert} [see J. Am. Stat. Assoc. 69, 698-704 (1974; Zbl 0291.62071)] allows to find all partitions into at most \(\overline{M}\) clusters and is in \(O(N^ 2)\) for fixed \(\overline{M}\). Moreover, if in each partitioning the size of the largest cluster is bounded by \(p\) times the number of entities in the set to be partitioned, with \(1/2\leq p<1\), it provides a complete hierarchy of partitions in \(O(N^ 2 \log N)\) time. The latter algorithm, allows to build a complete hierarchy of partitions in \(O(N^ 2\log N)\) time without any restriction. Comparative computational experiments with both algorithms and with an agglomerative hierarchical algorithm are reported. (From the authors' abstract).