An exact algorithm is proposed for average-linkage divisive hierarchical clustering, i.e., at each level of the hierarchy a cluster is bipartitioned in such a way that the average dissimilarity between all pairs of entities, one in each of the resulting clusters, is maximum. This subproblem is shown to be equivalent to a hyperbolic program in 0-1 variables, solved in turn through a sequence of unconstrained quadratic 0-1 programs. Since the exact algorithm only allows the solution of moderate size problems, two heuristics are considered. The first one is a simplified version of the exact algorithm. The second one applies directly to the hyperbolic 0-1 program. Both heuristics allow the solution of large problems. Computational experience with test problems from the literature is reported.
Published December 1991 , 30 pages
This cahier was revised in January 1993