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


Espaliers: A Generalization of Dendrograms

, et

Dendrograms are widely used to represent graphically the clusters and partitions obtained with hierarchical clustering schemes. Espaliers are generalized dendrograms in which the length of horizontal lines is used in addition to their level in order to display the values of two characteristics of each cluster (e.g., the split and the diameter) instead of only one. An algorithm is first presented to transform a dendrogram into an espalier without rotation of any part of the former. This is done by stretching some of the horizontal lines to obtain a diagram with vertical and horizontal lines only, then cutting off by diagonal lines the parts of the horizontal lines exceeding their prescribed length. The problem of finding if, allowing rotations, no diagonal lines are needed is solved by an O (N2) algorithm where N is the number of entities to be classified. This algorithm is then generalized to obtain espaliers with minimum width and, possibly, some diagonal lines.

, 27 pages

Ce cahier a été révisé en février 1994