Espaliers: A generalization of dendrograms
Journal of Classification - 1996
Tóm tắt
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.
Từ khóa
Tài liệu tham khảo
BROSSIER, G. (1980). “Représentation ordonnée des classifications hiérarchiques,”Statistique et Analyse des Données, 2, 31–44.
BUFFON, G. L., LECLERC, Comte de (1749),Histoire Naturelle, Premier Discours: De la manière d'étudier et de traiter l'histoire naturelle, Paris.
CHANDON, J., LEMAIRE, J., and POUGET, J. (1980). “Construction de l'ultramétrique la plus proche d'une dissimilarité au sens des moindres carrés,”RAIRO-Recherche Opérationnelle, 14(2), 157–170.
DELATTRE, M., and HANSEN, P. (1980). “Bicriterion, Cluster Analysis”IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-2(4), 277–291.
GLASBEY, C.A. (1987), “Complete Linkage as a Multiple Stopping Rule for Single Linkage Clustering,”Journal of Classification, 4, 103–109.
GORDON, A. D. (1981),Classification: Methods for the Exploratory Analysis of Multivariate Data, New York: Chapman and Hall.
GORDON, A. D. (1987), “A Review of Hierarchical Classification”Journal of Royal Statistical Society A, 150, part 2, 119–137.
GOWER, J. C., and ROSS, G. J. S. (1969), “Minimum Spanning Trees and Single Linkage Cluster Analysis,”Applied Statistics, 18, 54–64.
GUENOCHE, A., HANSEN, P., and JAUMARD, B. (1991), “Efficient Algorithms for Divisive Hierarchical Clustering with the Diameter Criterion,”Journal of Classification, 8, 5–30.
HARTIGAN, J. A. (1975),Clustering Algorithms, New York: Wiley.
HUBERT, L. (1973), “Monotone Invariant Clustering Procedures,”Psychometrika, 38(1), 47–62.
JAMBU, M. (1978),Classification automatique pour l'analyse des données, Paris: Dunod (Cluster Analysis and Data Analysis, Amsterdam: North-Holland, 1983).
JOHNSON, S. C. (1967), “Hierarchical Clustering Schemes,”Psychometrika, 12, 241–254.
KAUFMAN, L., and ROUSSEEUW, P. J. (1990),Finding Groups in Data: An Introduction to Cluster Analysis, New York: Wiley.
LANCE, G. N., and WILLIAMS, W. T. (1967), “Mixed-data Classificatory Systems: I. Agglomerative Systems,”Australian Computer Journal, 1, 15–20.
MCCAMMON, R. B. (1968), “The Dendrograph: A New Tool for Correlation,”Geological Society of America bulletin, 79, 1663–1670.
RAO, M. R. (1971), “Cluster Analysis and Mathematical Programming,”Journal of American Statistical Association, 66, 622–626.
SNEATH, P. H. A., and SOKAL, R. R. (1973),Numerical Taxonomy. The Principles and Practice of Numerical Classification, Freeman: San Francisco.
SOKAL, R. R., and ROHLF, F. J. (1962), “The Comparison of Dendrograms by Objective Methods,”Taxon, 11, 33–40.