Abstract
Proportional link linkage (PLL) clustering methods are a parametric family of monotone invariant agglomerative hierarchical clustering methods. This family includes the single, minimedian, and complete linkage clustering methods as special cases; its members are used in psychological and ecological applications. Since the literature on clustering space distortion is oriented to quantitative input data, we adapt its basic concepts to input data with only ordinal significance and analyze the space distortion properties of PLL methods. To enable PLL methods to be used when the numbern of objects being clustered is large, we describe an efficient PLL algorithm that operates inO(n 2 logn) time andO(n 2) space.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
AHO, A.V., HOPCROFT, J.E. and ULLMAN, J.D., (1974),The Design and Analysis of Computer Algorithms, Reading, Massachusetts: Addison-Wesley.
ANDERBERG, M.R., (1973),Cluster Analysis for Applications, New York: Academic Press.
BATAGELJ, V., (1981), “Note on Ultrametric Hierarchical Clustering Algorithms,”Psychometrika, 46, 351–352.
BROMLEY, D.B., (1966), “Rank Order Cluster Analysis,”British Journal of Mathematical and Statistical Psychology, 19, 105–123.
DAY, W.H.E., and EDELSBRUNNER, H., (1984), “Efficient Algorithms for Agglomerative Hierarchical Clustering Methods,”Journal of Classification, 1, 7–24.
D'ANDRADE, R.G., (1978), “U-statistic Hierarchical Clustering,”Psychometrika, 43, 59–67.
DEFAYS, D., (1977), “An Efficient Algorithm for a Complete Link Method,”Computer Journal, 20, 364–366.
DIDAY, E. (1983), “Inversions en Classification Hiérarchique: Application à la Construction Adaptative d'indices d'agrégation,”Revue de Statistique Appliquée, 31, 45–62.
DuBIEN, J.L., and WARDE, W.D., (1979), “A Mathematical Comparison of the Members of an Infinite Family of Agglomerative Clustering Algorithms,”Canadian Journal of Statistics, 7, 29–38.
EVERITT, B., (1980),Cluster Analysis (second edition), London: Heinemann.
FLOREK, K., LUKASZEWICZ, J., PERKAL, J., STEINHAUS, H., and ZUBRZYCKI, S., (1951), “Taksonomia Wroclawska,”Przeglad Antropologiczny, 17, 193–211.
FURNAS, G.W., (1980), “Objects and Their Features: The Metric Representation of Two-Class Data,” Ph.D. dissertation, Department of Psychology, Stanford University, Stanford, California.
HUBERT, L., (1972), “Some Extensions of Johnson's Hierarchical Clustering Algorithms,”Psychometrika, 37, 261–274.
HUBERT, L., (1973), “Monotone Invariant Clustering Procedures,”Psychometrika, 38, 47–62.
HUBERT, L.J., (1974), “Some Applications of Graph Theory to Clustering,”Psychometrika, 39, 283–309.
HUBERT, L., (1977), “A Set-Theoretical Approach to the Problem of Hierarchical Clustering,”Journal of Mathematical Psychology, 15, 70–88.
HUBERT, L., and BAKER, F.B., (1976), “Data Analysis by Single-Link and Complete-Link Hierarchical Clustering,”Journal of Educational Statistics, 1, 87–111.
HUBERT, L., and SCHULTZ, J., (1975), “Hierarchical Clustering and the Concept of Space Distortion,”British Journal of Mathematical and Statistical Psychology, 28, 121–133.
JAMBU, M., and LEBEAUX, M.-O., (1983),Cluster Analysis and Data Analysis, New York: Elsevier Science.
JANOWITZ, M.F., (1978a), “An Order Theoretic Model for Cluster Analysis,”SIAM Journal on Applied Mathematics, 34, 55–72.
JANOWITZ, M.F., (1978b), “Semiflat L-Cluster Methods,”Discrete Mathematics, 21, 47–60.
JANOWITZ, M.F., (1979a), “Monotone Equivariant Cluster Methods,”SIAM Journal on Applied Mathematics, 37, 148–165.
JANOWITZ, M.F., (1979b), “Preservation of Global Order Equivalence,”Journal of Mathematical Psychology, 20, 78–88.
JANOWITZ, M.F. (1981), “Continuous L-Cluster Methods,”Discrete Applied Mathematics, 3, 107–112.
JARDINE, N., and SIBSON, R., (1968), “A Model for Taxonomy,”Mathematical Biosciences, 2, 465–482.
JARDINE, N., and SIBSON, R., (1971),Mathematical Taxonomy, New York: John Wiley.
JOHNSON, S.C., (1967), “Hierarchical Clustering Schemes,”Psychometrika, 32, 241–254.
KENDRICK, W.B., and PROCTOR, J.R., (1964), “Computer Taxonomy in the Fungi Imperfecti,”Canadian Journal of Botany, 42, 65–88.
KRUSKAL, J.B., (1956), “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem,”Proceedings of the American Mathematical Society, 7, 48–50.
LANCE, G.N., and WILLIAMS, W.T., (1966), “A Generalized Sorting Strategy for Computer Classifications,”Nature, 212, 218.
LANCE, G.N., and WILLIAMS, W.T., (1967), “A General Theory of Classificatory Sorting Strategies. 1. Hierarchical Systems,”Computer Journal, 9, 373–380.
LEGENDRE, L., and LEGENDRE, P., (1983a),Numerical Ecology, Amsterdam: Elsevier Scientific.
LEGENDRE, L., and LEGENDRE, P., (1983b), “Partitioning Ordered Variables into Discrete States for Discriminant Analysis of Ecological Classifications,”Canadian Journal of Zoology, 61, 1002–1010.
LEGENDRE, P., BALEUX, B., and TROUSSELLIER, M., (1984), “Dynamics of Pollution-indicator and Heterotrophic Bacteria in Sewage Treatment Lagoons,”Applied and Environmental Microbiology, 48, 586–593.
LEGENDRE, P., DALLOT, S., and LEGENDRE, L., (1985), “Succession of Species Within a Community: Chronological Clustering, with Applications to Marine and Freshwater Zooplankton,”American Naturalist, 125, 257–288.
LEGENDRE, P., and LEGENDRE, V. (1984), “Postglacial Dispersal of Freshwater Fishes in the Quebéc Peninsula,”Canadian Journal of Fisheries and Aquatic Sciences, 41, 1781–1802.
LING, R.F., (1972), “On the Theory and Construction of k-Clusters,”Computer Journal, 15, 326–332.
LUKASZEWICZ, J., (1951), “Sur la liaison et la division des points d'un ensemble fini,”Colloquium Mathematicum, 2, 282–285.
MATULA, D.W., (1977), “Graph Theoretic Techniques for Cluster Analysis Algorithms,” inClassification and Clustering, ed. J. van Ryzin, New York: Academic Press, 95–129.
McQUITTY, L.L., (1957), “Elementary Linkage Analysis for Isolating Orthogonal and Oblique Types and Typal Relevancies,”Educational and Psychological Measurement, 17, 207–229.
MILLIGAN, G.W., (1979), “Ultrametric Hierarchical Clustering Algorithms,”Psychometrika, 44, 343–346.
MURTAGH, F., (1983), “A Survey of Recent Advances in Hierarchical Clustering Algorithms,”Computer Journal, 26, 354–359.
MURTAGH, F., (1984), “Complexities of Hierarchic Clustering Algorithms: State of the Art,”Computational Statistics Quarterly, 1, 101–113.
ROHLF, F.J., (1963), “Classification of Aedes by Numerical Taxonomic Methods (Diptera: Culicidae),”Annals of the Entomological Society of America, 56, 798–804.
ROHLF, F.J., (1977), “Computational Efficiency of Agglomerative Clustering Algorithms,” Report RC 6831, IBM T. J. Watson Research Center, Yorktown Heights, New York.
SIBSON, R., (1970), “A Model for Taxonomy. II,”Mathematical Biosciences, 6, 405–430.
SIBSON, R., (1972), “Order Invariant Methods for Data Analysis,”Journal of the Royal Statistical Society Series B, 34, 311–349.
SIBSON, R., (1973), “SLINK: An Optimally Efficient Algorithm for the Single-Link Cluster Method,”Computer Journal, 16, 30–34.
SNEATH, P.H.A., (1957), “The Application of Computers to Taxonomy,”Journal of General Microbiology, 17, 201–226.
SNEATH, P.H.A., (1966), “A Comparison of Different Clustering Methods as Applied to Randomly-spaced Points,”Classification Society Bulletin, 1, 2–18.
SNEATH, P.H.A., and SOKAL, R.R., (1973),Numerical Taxonomy, San Francisco: W. H. Freeman.
SOKAL, R.R., and SNEATH, P.H.A., (1963),Principles of Numerical Taxonomy, San Francisco: W. H. Freeman.
SØRENSEN, T., (1948), “A Method of Establishing Groups of Equal Amplitude in Plant Sociology Based on Similarity of Species Content and its Application to Analyses of the Vegetation on Danish Commons,”Biologiske Skrifter, 5, 1–34.
WARD, Jr., J.H., (1963), “Hierarchical Grouping to Optimize an Objective Function,”Journal of the American Statistical Association, 58, 236–244.
WEIDE, B., (1977), “A Survey of Analysis Techniques for Discrete Algorithms,”Computing Surveys, 9, 291–313.
WISHART, D., (1969), “256 Note. An Algorithm for Hierarchical Classifications,”Biometrics, 25, 165–170.
Author information
Authors and Affiliations
Additional information
This work was partially supported by the Natural Sciences and Engineering Research Council of Canada and by the Austrian Fonds zur Förderung der wissenschaftlichen Forschung.
Rights and permissions
About this article
Cite this article
Day, W.H.E., Edelsbrunner, H. Investigation of proportional link linkage clustering methods. Journal of Classification 2, 239–254 (1985). https://doi.org/10.1007/BF01908077
Issue Date:
DOI: https://doi.org/10.1007/BF01908077