The \(k\)-weak hierarchical representations: An extension of the indexed closed weak hierarchies. (English) Zbl 1012.62067

Summary: Several approaches have been proposed for the purpose of proving that different classes of dissimilarities (e.g., ultrametrics) can be represented by certain types of stratified clusterings which are easily visualized (e.g., indexed hierarchies). These approaches differ in the choice of the clusters that are used to represent a dissimilarity coefficient. More precisely, the clusters may be defined as the maximal linked subsets, also called \(M_{\text L}\)-sets; equally they may be defined as a particular type of 2-balls.
In this paper, we first introduce the notion of a \(k\)-ball, thereby extending the notion of a 2-ball. For an arbitrary dissimilarity coefficient, we establish some properties of \(k\)-balls that pinpoint the connection between them and the \(M_{\text L}\)-sets. We also introduce the (2,\(k\))-point condition (\(k\geqslant 1\)) which is an extension of the Bandelt four-point condition [H.-J. Bandelt, Four-point characterization of the dissimilarity functions obtained from indexed closed weak hierarchies. Math. Seminar, Univ. Hamburg/Germany (1992)].
For \(k\geqslant 2\), we prove that the dissimilarities satisfying the (2,\(k\))-point condition are in one–one correspondence with a class of stratified clusterings, called \(k\)-weak hierarchical representations, whose main characteristic is that the intersection of (\(k+1\)) arbitrary clusters may be reduced to the intersection of some \(k\) of these clusters.


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


[1] Arabie, P.; Hubert, L.J., Advances in cluster analysis relevant to marketing research, (), 3-19
[2] Arabie, P.; Hubert, L.J., An overview of combinatorial data analysis, (), 5-63 · Zbl 0902.62005
[3] Bandelt, H.-J., Four-point characterization of the dissimilarity functions obtained from indexed closed weak hierarchies, mathematisches seminar, (1992), Universität Hamburg Germany
[4] Bandelt, H.-J.; Dress, A.W.M., Weak hierarchies associated with similarity measuresan additive clustering technique, Bull. math. biol., 51, 133-166, (1989) · Zbl 0666.62058
[5] Bandelt, H.-J.; Dress, A.W.M., An order theoretic framework for overlapping clustering, Discrete math., 136, 21-37, (1994) · Zbl 0832.92032
[6] Batbedat, A., LES isomorphismes HTS et HTE (après la bijection de benzécri-Johnson), Metron, 46, 47-59, (1988) · Zbl 0724.05055
[7] J.-P. Benzécri, L’Analyse des données: la Taxinomie, Vol. 1, Dunod, Paris, 1973.
[8] Bertrand, P., Structural properties of pyramidal clustering, DIMACS ser. discrete math. theoret. comput. sci., 19, 35-53, (1995) · Zbl 0814.62032
[9] Bertrand, P., Set systems and dissimilarities, European J. combin., 21, 727-743, (2000) · Zbl 0957.05103
[10] P. Bertrand, M.F. Janowitz, Pyramids and weak hierarchies in the ordinal model for clustering, Discrete Appl. Math. 122 (2002) 55-81. · Zbl 1040.62052
[11] F. Critchley, B. Van Cutsem, An order-theoretic unification and generalisation of certain fundamental bijections in mathematical classification, LMC-Imag Rapports de recherche, RR 874-M and RR 875-M, France, 1992.
[12] Diatta, J., Dissimilarités multivoies et généralisations d’hypergraphes sans triangles, Math. inf. sci. hum., 138, 57-73, (1997) · Zbl 0910.62062
[13] Diatta, J.; Fichet, B., From apresjan hierarchies and bandelt-dress weak hierarchies to quasi-hierarchies, (), 111-118
[14] Diatta, J.; Fichet, B., Quasi-ultrametrics and their 2-ball hypergraphs, Discrete math., 192, 87-102, (1998) · Zbl 0951.54023
[15] E. Diday, Une représentation visuelle des classes empiétantes: les pyramides, Rapport de recherche I.N.R.I.A. No. 291, Rocquencourt, France, 1984.
[16] Diday, E., Orders and overlapping clusters in pyramids, (), 201-234
[17] Durand, C.; Fichet, B., One-to-one correspondences in pyramidal representation: a unified approach, (), 85-90
[18] Janowitz, M.F., An order theoretic model for cluster analysis, SIAM J. appl. math., 34, 55-72, (1978) · Zbl 0379.62050
[19] Jardine, N.; Sibson, R., Mathematical taxonomy, (1971), Wiley New York · Zbl 0322.62065
[20] Johnson, S.C., Hierarchical clustering schemes, Psychometrika, 32, 241-254, (1967) · Zbl 1367.62191
[21] Mirkin, B., Mathematical classification and clustering, (1996), Kluwer Dordrecht · Zbl 0874.90198
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.