Groupe d’études et de recherche en analyse des décisions

G-91-55

Average-Linkage Divisive Hierarchical Clustering

, et

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.

, 30 pages

Ce cahier a été révisé en janvier 1993