Abstract
A new and apparently rather useful and natural concept in cluster analysis is studied: given a similarity measure on a set of objects, a sub-set is regarded as a cluster if any two objectsa, b inside this sub-set have greater similarity than any third object outside has to at least one ofa, b. These clusters then form a closure system which can be described as a hypergraph without triangles. Conversely, given such a system, one may attach some weight to each cluster and then compose a similarity measure additively, by letting the similarity of a pair be the sum of weights of the clusters containing that particular pair. The original clusters can be reconstructed from the obtained similarity measure. This clustering model is thus located between the general additive clustering model of Shepard and Arabie (1979) and the standard hierarchical model. Potential applications include fitting dendrograms with few additional nonnested clusters and simultaneous representation of some families of multiple dendrograms (in particular, two-dendrogram solutions), as well as assisting the search for phylogenetic relationships by proposing a somewhat larger system of possibly relevant “family groups”, from which an appropriate choice (based on additional insight or individual preferences) remains to be made.
Similar content being viewed by others
Literature
Abbott, L. A., F. A. Bisby and D. J. Rogers. 1985.Taxonomic Analysis in Biology. New York: Columbia University Press.
Anstee, R. P. 1980. “Properties of (0, 1)-Matrices with no Triangles”.J. Combinatorial Theor. A29, 186–198.
Arabie, P. and J. D. Carroll. 1980. “MAPCLUS: A Mathematical Programming Approach to Fitting the ADCLUS Model”.Psychometrika 45, 211–235.
——, W. DeSarbo and J. Wind. 1981. “Overlapping Clustering: A New Method for Product Positioning”.J. Marketing Res,18, 310–317.
Bandelt, H.-J. and A. Dress. 1986. “Reconstructing the Shape of a Tree from Observed Dissimilarity Data”.Adv. Appl. Math. 7, 309–343.
Arabie, P. and J. D. Carroll. (a). “A Canonical Decomposition Theory for Metrics on a Finite Set”, in preparation.
Barthélemy, J. P. and N. X. Luong. 1987. “Sur la Topologie d'un Arbre Phylogénétique: Aspects Théoriques, Algorithmes et Applications à l'Analyse de Données Textuelles”,Math. Sci. Hum. 100, 57–80.
Birkhoff, G. 1967.Lattice Theory (3rd edn). Providence: American Mathematical Society.
Bock, H. H. 1974.Automatische Klassifikation. Göttingen: Vandenhoeck & Ruprecht.
Brouwer, A. E. and A. Kolen. 1980. “A Super-Balanced Hypergraph has a Nest Point”. Report ZW 146/80. Amsterdam: Mathematisch Centrum.
Butler, K. A. and J. E. Corter. 1986. “Use of Psychometric Tools for Knowledge Acquisition: A Case Study.” InArtificial Intelligence and Statistics, W. A. Gale (Ed.), pp. 295–319. Reading, MA: Addison-Wesley.
Carroll, J. D. 1976. “Spatial, Non-Spatial and Hybrid Models for Scaling”.Psychometrika,41, 439–463.
— and S. Pruzansky. 1980. “Discrete and Hybrid Scaling Models”. InSimilarity and Choice, E. D. Lantermann and H. Feger (Eds), pp. 108–139. Switzerland: Hans Huber.
— and —. 1986. “Discrete and Hybrid Models for Proximity Data”. InClassification as a Tool of Research, W. Gaul and M. Schader (Eds), pp. 47–59. Amsterdam: Elsevier.
Corter, J. E. 1982. “ADDTREE/P: A PASCAL Program for Fitting Additive Trees based on Sattath and Tversky's ADDTREE Algorithm”.Behavior Research Methods and Instrumentation 14, 353–354.
— and A. Tversky. 1986. “Extended Similarity Trees”,Psychometrika 51, 429–451.
Giles, R. 1978. “A Balanced Hypergraph Defined by Certain Subtrees of a Tree”.Ars Combinatoria 6, 179–183.
Golumbic, M. C. and R. E. Jamison. 1985. “The Intersection Graphs of Paths in a Tree”.J. Combinatorial Theor. B38, 8–22.
Gordon, A. D. 1987. “A Review of Hierarchical Classification”.J. R. Statist. Soc. A150, 119–137.
Mamison-Waldner, R. E. 1981. “Partition Numbers for Trees and Ordered Sets”.Pacif. J. Math. 96, 115–140.
—. 1982. “A Perspective on Abstract Convexity: Classifying Alignments by Varieties”. InConvexity and Related Combinatorial Geometry, D. C. Kay and M. Breen (Eds), pp. 113–150. New York: Dekker.
Kolen, A. 1983. “Solving Covering Problems and the Uncapacitated Plant Location Problem on Trees”,Eur. J. Oper. Res. 12, 266–278.
Lassak, M. 1983. “The Rank of Product Closure Systems”,Arch. Math. 40, 186–191.
Leffers, H., J. Kjems, L. Østergaard, N. Larsen and R. A. Garrett. 1987. “Evolutionary Relationships Amongst Archaebacteria: A Comparative Study of 23S Ribosomal RNAs of a Sulphur-Dependent Extreme Thermophile, an Extreme Halophile and a Thermophilic Methanogen”.J. Molec. Biol. 195, 43–61.
Lehel, J. 1985. “A Characterization of Totally Balanced Hypergraphs”.Discrete Math. 57, 59–65.
Margush, T. and F. R. McMorris. 1981. “Consensusn-trees”.Bull. Math. Biol. 43, 239–244.
McMorris, F. R. 1987. Proceedings of the 1st Conference of the IFCS. Aachen.
Mirkin, B. G. 1987. “Additive Clustering and Qualitative Factor Analysis Methods for Similarity Matrices”.J. Classification 4, 7–31.
Nei, M. 1987.Molecular Evolutionary Genetics. New York: Columbia University Press.
Punj, G. and D. W. Stewart. 1983. “Cluster Analysis in Marketing Research: Review and Suggestions for Application”.J. Marketing Res. 20, 134–148.
Ryser, H. J. 1972. “A Fundamental Matrix Equation for Finite Sets”.Proc. Am. Math. Soc. 34, 332–336.
— 1973. “Intersection Properties of Finite Sets”.J. Combinatorial Theor. A14, 79–92.
Sattath, S. and A. Tversky. 1977. “Additive Similarity Trees”.Psychometrika,42, 319–345.
— and —. 1987. “On the Relation Between Common and Distinctive Feature Models”.Psychol. Rev. 94, 16–22.
Shepard, R. N. and P. Arabie. 1979. “Additive Clustering: Representation of Similarities as Combinations of Discrete Overlapping Properties”.Psychol. Rev. 86, 87–123.
Sibley, C. G. and J. E. Ahlquist. 1984. “The Phylogeny of the Hominoid Primates as Indicated by DNA-DNA Hybridization”.J. Molec. Evol. 20, 2–15.
Sneath, P. H. A. and R. R. Sokal. 1973.Numerical Taxonomy. San Francisco: Freeman.
Tversky, A. 1977. “Features of Similarity”.Psychol. Rev. 84, 327–352.
van de Vel, M. 1987. “Abstract, Topological, and Uniform Convex Structures I”. Rapport nr. 325, Fac. W & I, Vrije Universiteit, Amsterdam.
Wille, R. 1988. “Lattices in Data Analysis: How to Draw Them with a Computer”. InAlgorithms and Order, I. Rival (Ed.). Dordrecht: Reidel.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Bandelt, H.J., Dress, A.W.M. Weak hierarchies associated with similarity measures—An additive clustering technique. Bltn Mathcal Biology 51, 133–166 (1989). https://doi.org/10.1007/BF02458841
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02458841