ISSN:
1432-1343
Keywords:
Dendrogram
;
Espalier
;
Hierarchical clustering
;
Diagram
;
Polynomial algorithm
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Description / Table of Contents:
Résumé Les dendrogrammes sont fréquemment utilisés pour représenter graphiquement les classes et les partitions obtenues par les méthodes de classification hiérarchique ascendantes ou descendantes. Les espaliers sont des dendrogrammes généralisés où la longueur des lignes horizontales est utilisée en plus de leur niveau pour représenter deux caractéristiques de chaque classe (par exemple l'écart et le diamètre) au lieu d'une seule. On présente d'abord un algorithme pour transformer un dendrogramme en espalier sans permettre de rotation d'aucune partie du premier. Ceci est fait en allongeant certaines des lignes horizontales de façon à obtenir un diagramme utilisant seulement des lignes horizontales et verticales, puis en coupant par des lignes diagonales les parties des lignes horizontales excèdant la longueur qui leur est affectée. Le problème de déterminer si, les rotations étant permises, aucune ligne diagonale n'est nécessaire est résolu par un algorithme polynomial enO(N 2) oùN est le nombre d'objets à classifier. Cet algorithme est généralisé pour résoudre le problème de déterminer un espalier de largeur minimum avec, éventuellement, des lignes diagonales.
Notes:
Abstract 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, the 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 anO(N 2) algorithm whereN is the number of entities to be classified. This algorithm is the generalized to obtain espaliers with minimum width and, possibly, some diagonal lines.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01202584
Permalink
