[{"publication_identifier":{"issn":["0176-4268"],"eissn":["1432-1343"]},"acknowledgement":"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.","doi":"10.1007/BF01908077","date_updated":"2022-01-31T10:37:13Z","date_published":"1985-12-01T00:00:00Z","author":[{"full_name":"Day, William","last_name":"Day","first_name":"William"},{"full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert"}],"month":"12","oa_version":"None","scopus_import":"1","language":[{"iso":"eng"}],"citation":{"ista":"Day W, Edelsbrunner H. 1985. Investigation of Proportional Link Linkage Clustering Methods. Journal of Classification. 2(2–3), 239–254.","ama":"Day W, Edelsbrunner H. Investigation of Proportional Link Linkage Clustering Methods. <i>Journal of Classification</i>. 1985;2(2-3):239-254. doi:<a href=\"https://doi.org/10.1007/BF01908077\">10.1007/BF01908077</a>","chicago":"Day, William, and Herbert Edelsbrunner. “Investigation of Proportional Link Linkage Clustering Methods.” <i>Journal of Classification</i>. Springer, 1985. <a href=\"https://doi.org/10.1007/BF01908077\">https://doi.org/10.1007/BF01908077</a>.","apa":"Day, W., &#38; Edelsbrunner, H. (1985). Investigation of Proportional Link Linkage Clustering Methods. <i>Journal of Classification</i>. Springer. <a href=\"https://doi.org/10.1007/BF01908077\">https://doi.org/10.1007/BF01908077</a>","ieee":"W. Day and H. Edelsbrunner, “Investigation of Proportional Link Linkage Clustering Methods,” <i>Journal of Classification</i>, vol. 2, no. 2–3. Springer, pp. 239–254, 1985.","short":"W. Day, H. Edelsbrunner, Journal of Classification 2 (1985) 239–254.","mla":"Day, William, and Herbert Edelsbrunner. “Investigation of Proportional Link Linkage Clustering Methods.” <i>Journal of Classification</i>, vol. 2, no. 2–3, Springer, 1985, pp. 239–54, doi:<a href=\"https://doi.org/10.1007/BF01908077\">10.1007/BF01908077</a>."},"year":"1985","date_created":"2018-12-11T12:07:01Z","article_type":"original","quality_controlled":"1","title":"Investigation of Proportional Link Linkage Clustering Methods","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publist_id":"2006","status":"public","intvolume":"         2","_id":"4114","abstract":[{"text":"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","lang":"eng"}],"publication_status":"published","type":"journal_article","page":"239 - 254","day":"01","volume":2,"publisher":"Springer","extern":"1","issue":"2-3","publication":"Journal of Classification","article_processing_charge":"No"},{"intvolume":"         1","_id":"4121","abstract":[{"lang":"eng","text":"Whenevern objects are characterized by a matrix of pairwise dissimilarities, they may be clustered by any of a number of sequential, agglomerative, hierarchical, nonoverlapping (SAHN) clustering methods. These SAHN clustering methods are defined by a paradigmatic algorithm that usually requires 0(n 3) time, in the worst case, to cluster the objects. An improved algorithm (Anderberg 1973), while still requiring 0(n 3) worst-case time, can reasonably be expected to exhibit 0(n 2) expected behavior. By contrast, we describe a SAHN clustering algorithm that requires 0(n 2 logn) time in the worst case. When SAHN clustering methods exhibit reasonable space distortion properties, further improvements are possible. We adapt a SAHN clustering algorithm, based on the efficient construction of nearest neighbor chains, to obtain a reasonably general SAHN clustering algorithm that requires in the worst case 0(n 2) time and space.\r\nWhenevern objects are characterized byk-tuples of real numbers, they may be clustered by any of a family of centroid SAHN clustering methods. These methods are based on a geometric model in which clusters are represented by points ink-dimensional real space and points being agglomerated are replaced by a single (centroid) point. For this model, we have solved a class of special packing problems involving point-symmetric convex objects and have exploited it to design an efficient centroid clustering algorithm. Specifically, we describe a centroid SAHN clustering algorithm that requires 0(n 2) time, in the worst case, for fixedk and for a family of dissimilarity measures including the Manhattan, Euclidean, Chebychev and all other Minkowski metrics."}],"status":"public","date_updated":"2022-01-27T14:16:27Z","main_file_link":[{"url":"https://link.springer.com/article/10.1007%2FBF01890115"}],"date_published":"1984-01-01T00:00:00Z","publication_status":"published","author":[{"first_name":"William","full_name":"Day, William","last_name":"Day"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","first_name":"Herbert","orcid":"0000-0002-9823-6833"}],"month":"01","type":"journal_article","volume":1,"oa_version":"None","page":"7 - 24","day":"01","publication":"Journal of Classification","language":[{"iso":"eng"}],"extern":"1","publisher":"Springer","article_processing_charge":"No","publication_identifier":{"issn":["0176-4268"],"eissn":["1432-1343"]},"citation":{"mla":"Day, William, and Herbert Edelsbrunner. “Efficient Algorithms for Agglomerative Hierarchical Clustering Methods.” <i>Journal of Classification</i>, vol. 1, Springer, 1984, pp. 7–24, doi:<a href=\"https://doi.org/10.1007/BF01890115\">10.1007/BF01890115</a>.","short":"W. Day, H. Edelsbrunner, Journal of Classification 1 (1984) 7–24.","ieee":"W. Day and H. Edelsbrunner, “Efficient algorithms for agglomerative hierarchical clustering methods,” <i>Journal of Classification</i>, vol. 1. Springer, pp. 7–24, 1984.","chicago":"Day, William, and Herbert Edelsbrunner. “Efficient Algorithms for Agglomerative Hierarchical Clustering Methods.” <i>Journal of Classification</i>. Springer, 1984. <a href=\"https://doi.org/10.1007/BF01890115\">https://doi.org/10.1007/BF01890115</a>.","apa":"Day, W., &#38; Edelsbrunner, H. (1984). Efficient algorithms for agglomerative hierarchical clustering methods. <i>Journal of Classification</i>. Springer. <a href=\"https://doi.org/10.1007/BF01890115\">https://doi.org/10.1007/BF01890115</a>","ista":"Day W, Edelsbrunner H. 1984. Efficient algorithms for agglomerative hierarchical clustering methods. Journal of Classification. 1, 7–24.","ama":"Day W, Edelsbrunner H. Efficient algorithms for agglomerative hierarchical clustering methods. <i>Journal of Classification</i>. 1984;1:7-24. doi:<a href=\"https://doi.org/10.1007/BF01890115\">10.1007/BF01890115</a>"},"doi":"10.1007/BF01890115","date_created":"2018-12-11T12:07:04Z","year":"1984","quality_controlled":"1","article_type":"original","title":"Efficient algorithms for agglomerative hierarchical clustering methods","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publist_id":"1998"}]