G-90-07
Efficient Algorithms for Divisive Hierarchical Clustering with the Diameter Criterion
, , and
BibTeX referenceDivisive hierarchical clustering algorithms with the diametercriterion proceed by recursively selecting the cluster with largest diameter and partitioning it into two clusters whose largest diameter is smallest possible. We provide two such algorithms with complexities  and
 and  respectively, where
 respectively, where  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 Hubert,  allows to find all partitions into at most
 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 Hubert,  allows to find all partitions into at most  clusters and is in
  clusters and is in  for fixed
 for fixed  . 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
. 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  , it provides a complete hierarchy of partitions in
, it provides a complete hierarchy of partitions in  time. The latter algorithm, a refinement of an algorithm of Rao, allows to build a complete hierarchy of partitions in
 time. The latter algorithm, a refinement of an algorithm of Rao, allows to build a complete hierarchy of partitions in  time without any restriction. Comparative computational experiments with both algorithms and with an agglomerative hierarchical algorithm of Benzécri are reported.
 time without any restriction. Comparative computational experiments with both algorithms and with an agglomerative hierarchical algorithm of Benzécri are reported.
Published February 1990 , 31 pages
This cahier was revised in August 1990