---
_id: '4114'
abstract:
- lang: eng
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
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.
article_processing_charge: No
article_type: original
author:
- first_name: William
full_name: Day, William
last_name: Day
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
citation:
ama: Day W, Edelsbrunner H. Investigation of Proportional Link Linkage Clustering
Methods. Journal of Classification. 1985;2(2-3):239-254. doi:10.1007/BF01908077
apa: Day, W., & Edelsbrunner, H. (1985). Investigation of Proportional Link
Linkage Clustering Methods. Journal of Classification. Springer. https://doi.org/10.1007/BF01908077
chicago: Day, William, and Herbert Edelsbrunner. “Investigation of Proportional
Link Linkage Clustering Methods.” Journal of Classification. Springer,
1985. https://doi.org/10.1007/BF01908077.
ieee: W. Day and H. Edelsbrunner, “Investigation of Proportional Link Linkage Clustering
Methods,” Journal of Classification, vol. 2, no. 2–3. Springer, pp. 239–254,
1985.
ista: Day W, Edelsbrunner H. 1985. Investigation of Proportional Link Linkage Clustering
Methods. Journal of Classification. 2(2–3), 239–254.
mla: Day, William, and Herbert Edelsbrunner. “Investigation of Proportional Link
Linkage Clustering Methods.” Journal of Classification, vol. 2, no. 2–3,
Springer, 1985, pp. 239–54, doi:10.1007/BF01908077.
short: W. Day, H. Edelsbrunner, Journal of Classification 2 (1985) 239–254.
date_created: 2018-12-11T12:07:01Z
date_published: 1985-12-01T00:00:00Z
date_updated: 2022-01-31T10:37:13Z
day: '01'
doi: 10.1007/BF01908077
extern: '1'
intvolume: ' 2'
issue: 2-3
language:
- iso: eng
month: '12'
oa_version: None
page: 239 - 254
publication: Journal of Classification
publication_identifier:
eissn:
- 1432-1343
issn:
- 0176-4268
publication_status: published
publisher: Springer
publist_id: '2006'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Investigation of Proportional Link Linkage Clustering Methods
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 2
year: '1985'
...
---
_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."
article_processing_charge: No
article_type: original
author:
- first_name: William
full_name: Day, William
last_name: Day
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
citation:
ama: Day W, Edelsbrunner H. Efficient algorithms for agglomerative hierarchical
clustering methods. Journal of Classification. 1984;1:7-24. doi:10.1007/BF01890115
apa: Day, W., & Edelsbrunner, H. (1984). Efficient algorithms for agglomerative
hierarchical clustering methods. Journal of Classification. Springer. https://doi.org/10.1007/BF01890115
chicago: Day, William, and Herbert Edelsbrunner. “Efficient Algorithms for Agglomerative
Hierarchical Clustering Methods.” Journal of Classification. Springer,
1984. https://doi.org/10.1007/BF01890115.
ieee: W. Day and H. Edelsbrunner, “Efficient algorithms for agglomerative hierarchical
clustering methods,” Journal of Classification, vol. 1. Springer, pp. 7–24,
1984.
ista: Day W, Edelsbrunner H. 1984. Efficient algorithms for agglomerative hierarchical
clustering methods. Journal of Classification. 1, 7–24.
mla: Day, William, and Herbert Edelsbrunner. “Efficient Algorithms for Agglomerative
Hierarchical Clustering Methods.” Journal of Classification, vol. 1, Springer,
1984, pp. 7–24, doi:10.1007/BF01890115.
short: W. Day, H. Edelsbrunner, Journal of Classification 1 (1984) 7–24.
date_created: 2018-12-11T12:07:04Z
date_published: 1984-01-01T00:00:00Z
date_updated: 2022-01-27T14:16:27Z
day: '01'
doi: 10.1007/BF01890115
extern: '1'
intvolume: ' 1'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007%2FBF01890115
month: '01'
oa_version: None
page: 7 - 24
publication: Journal of Classification
publication_identifier:
eissn:
- 1432-1343
issn:
- 0176-4268
publication_status: published
publisher: Springer
publist_id: '1998'
quality_controlled: '1'
status: public
title: Efficient algorithms for agglomerative hierarchical clustering methods
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 1
year: '1984'
...