Abstract
Given two or more dendrograms (rooted tree diagrams) based on the same set of objects, ways are presented of defining and obtaining common pruned trees. Bounds on the size of a largest common pruned tree are introduced, as is a categorization of objects according to whether they belong to all, some, or no largest common pruned trees. Also described is a procedure for regrafting pruned branches, yielding trees for which one can assess the reliability of the depicted relationships. The tree obtained by regrafting branches on to a largest common pruned tree is shown to contain all the classes present in the strict consensus tree. The theory is illustrated by application to two classifications of a set of forty-nine stratigraphical pollen spectra.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
ADAMS, E.N. (1972), “Consensus Techniques and the Comparison of Taxonomic Trees,”Systematic Zoology, 21, 390–397.
ANSI (1978), “American National Standard Programming Language FORTRAN, ANSI X3.9- 1978,” American National Standards Institute, New York.
BIRKS, H.H., and MATHEWES, R.W. (1978), “Studies in the Vegetational History of Scotland V,”New Phytologist, 80, 455–484.
COOK, R.D., and WEISBERG, S. (1982),Residuals and Influence in Regression, London: Chapman and Hall.
DAY, W.H.E., and EDELSBRUNNER, H. (1984), “Efficient Algorithms for Agglomerative Hierarchical Clustering Methods,”Journal of Classification, 1, 7–24.
DEC (1982), “VAX-11 FORTRAN Language Reference Manual,” Digital Equipment Corporation, Maynard, Massachusetts.
DIDAY, E. (1982), “Croisements, Ordres et Ultramétriques: Application à la Recherche de Consensus en Classification Automatique”, Rapport 144, INRIA, Centre de Rocquencourt, Le Chesnay.
FINDEN, C.R. (1983), “CMTREE Manual,” Report, Department of Statistics, University of St. Andrews.
FINDEN, C.R. (1984a), “FSTREE Manual,” Report, Department of Statistics, University of St. Andrews.
FINDEN, C.R. (1984b), “UBTREE Manual,” Report, Department of Statistics, University of St. Andrews.
FINDEN, C.R. (1984c), “LMTREE Manual,” Report, Department of Statistics, University of St. Andrews.
GAREY, M.R., and JOHNSON, D.S. (1979),Computers and Intractability: A Guide to the Theory of NP-Completeness, New York: W.H. Freeman and Co.
GORDON, A.D. (1979), “A Measure of the Agreement between Rankings,”Biometrika, 66, 7–15.
GORDON, A.D. (1980), “On the Assessment and Comparison of Classifications,” inAnalyse de Données et Informatique, ed. R. Tomassone, Le Chesnay: INRIA.
GORDON, A.D. (1981),Classification: Methods for the Exploratory Analysis of Multivariate Data, London: Chapman and Hall.
HARTIGAN, J.A. (1975),Clustering Algorithms, New York: John Wiley.
KRUSKAL, J. (1977), “The Relationship between Multidimensional Scaling and Clustering,” inClassification and Clustering, ed. J. Van Ryzin, New York: Academic Press.
MAIER, D. (1978), “The Complexity of Some Problems on Subsequences and Supersequences,”Journal of the Association for Computing Machinery, 25, 322–336.
MARGUSH, T., and MC MORRIS, F.R. (1981), “Consensus n-Trees,”Bulletin of Mathematical Biology, 43, 239–244.
MURTAGH, F. (1984), “Counting Dendograms: A Survey,”Discrete Applied Mathematics, 7, 191–199.
NEUMANN, D.A. (1983), “Faithful Consensus Methods for n-Trees,”Mathematical Biosciences, 63, 271–287.
ROHLF, F.J. (1970), “Adaptive Hierarchical Clustering Schemes,”Systematic Zoology, 19, 58–82.
SIBSON, R. (1972), “Order Invariant Methods for Data Analysis,”Journal of the Royal Statistical Society, Series B, 34, 311–349.
SOKAL, R.R., and ROHLF, F.J. (1981), “Taxonomic Congruence in the Leptopodomorpha Re-examined,”Systematic Zoology, 30, 309–325.
WAGNER, R.A., and FISCHER, M.J. (1974), “The String-to-String Correction Problem,”Journal of the Association for Computing Machinery, 21, 168–173.
Author information
Authors and Affiliations
Additional information
This work was supported by the Science and Engineering Research Council. The authors are grateful to the referees for constructive criticisms of an earlier version of the paper, and to Dr. J.T. Henderson for advice on PASCAL.
Rights and permissions
About this article
Cite this article
Finden, C.R., Gordon, A.D. Obtaining common pruned trees. Journal of Classification 2, 255–276 (1985). https://doi.org/10.1007/BF01908078
Issue Date:
DOI: https://doi.org/10.1007/BF01908078