Galois closed entity sets and \(k\)-balls of quasi-ultrametric multi-way dissimilarities. (English) Zbl 1133.62335

Summary: Quasi-ultrametric multi-way dissimilarities and their respective sets of \(k\)-balls extend the fundamental bijection in classification between ultrametric pairwise dissimilarities and indexed hierarchies. We show that nonempty Galois closed subsets of a finite entity set coincide with \(k\)-balls of some quasi-ultrametric multi-way dissimilarity. This result relates the order theoretic Galois connection based clustering approach to the dissimilarity based one. Moreover, it provides an effective way to specify easy-to-interpret cluster systems, from complex data sets, as well as to derive informative attribute implications.


62H30 Classification and discrimination; cluster analysis (statistical aspects)
91C20 Clustering in the social and behavioral sciences
06B99 Lattices
Full Text: DOI


[1] Bandelt H-J (1992) Four point characterization of the dissimilarity functions obtained from indexed closed weak hierarchies. Mathematisches Seminar, Universität Hamburg
[2] Benzécri J-P (1973) L’Analyse des données : la Taxinomie. Dunod, Paris · Zbl 0297.62038
[3] Birkhoff G (1967) Lattice theory. 3rd edn. Coll. Publ., XXV. American Mathematical Society, Providence · Zbl 0153.02501
[4] Bock HH, Diday E (eds) (2000) Analysis of symbolic data. Springer, Heidelberg · Zbl 1039.62501
[5] Diatta J (1997) Dissimilarités multivoies et généralisations d’hypergraphes sans triangles. Math Inf Sci hum 138:57–73 · Zbl 0910.62062
[6] Diatta J (2006) Description-meet compatible multiway dissimilarities. Discrete Appl Math 154:493–507 · Zbl 1159.62355
[7] Diatta J, Fichet B (1994) From Apresjan hierarchies and Bandelt-Dress weak hierarchies to quasi-hierarchies. In: Diday E, Lechevalier Y, Schader M, Bertrand P, Burtschy B (eds) New approaches in classification and data analysis. Springer, Heidelberg, pp 111–118
[8] Diatta J, Fichet B (1998) Quasi-ultrametrics and their 2-ball hypergraphs. Discrete Math 192:87–102 · Zbl 0951.54023
[9] Domenach F, Leclerc B (2002) On the roles of Galois connections in classification. In: Opitz O, Schwaiger M (eds) Explanatory data analysis in empirical research. Springer, Heidelberg, pp 31–40
[10] Johnson SC (1967) Hierarchical clustering schemes. Psychometrika 32:241–254 · Zbl 1367.62191
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.