Croisements, ordres et ultramétriques
Mathématiques et Sciences humaines, Volume 83  (1983), p. 31-54

La représentation visuelle d'une hiérarchie induit un ordre sur les singletons. Si l'on désire représenter la même hiérarchie en tenant compte de contraintes extérieures (ordre des singletons induit par une autre hiérarchie, une partition, un indice de dissimilarité, par exemple) des croisements peuvent apparaître. Il y a un croisement dans la représentation visuelle d'une hiérarchie quand une branche horizontale (associée à un palier) est coupée par une branche verticale associée à un singleton. Il s'agit d'étudier les liens entre croisements, ordres, indices de dissimilarité et ultramétriques. On utilise la notion de compatibilité entre un ordre et un indice de dissimilarité ; on introduit les notions de semi-compatibilité et compatibilité faible. On étudie les aspects matriciels qui débouchent sur une généralisation des matrices de Robinson. On fait le lien entre toutes ces notions et les chaînes de longueur minimales au sens de l'indice de dissimilarité choisi. En introduisant la notion d'élément «compatible à gauche» ou «à droite» d'une chaîne, on donne de nouvelles propriétés concernant les chaînes incluses dans un arbre de longueur minimum. Dans le cas où cet indice est une ultramétrique, on obtient des propriétés intéressantes liant l'ordre des singletons correspondant à la visualisation d'une hiérarchie indicée et l' ultramétrique induite par cette hiérarchie.

@article{MSH_1983__83__31_0,
     author = {Diday, Edwin},
     title = {Croisements, ordres et ultram\'etriques},
     journal = {Math\'ematiques et Sciences humaines},
     publisher = {Ecole Pratique des hautes \'etudes, Centre de math\'ematique sociale et de statistique},
     volume = {83},
     year = {1983},
     pages = {31-54},
     zbl = {0528.62056},
     mrnumber = {728544},
     language = {fr},
     url = {http://www.numdam.org/item/MSH_1983__83__31_0}
}
Diday, Edwin. Croisements, ordres et ultramétriques. Mathématiques et Sciences humaines, Volume 83 (1983) , pp. 31-54. http://www.numdam.org/item/MSH_1983__83__31_0/

[1] E.N. Adams., "Consensus techniques and the comparison of taxonomic trees", Syst. Zool, 21, pp. 390-397, (1972).

[2] G. Brossier., "Représentation ordonnée des classifications hiérarchiques", Statistique et Analyse des données, Vol. 2., pp. 31-44, (1980).

[3] J.L. Chandon., J. Lemaire., J. Pouget., Construction de l'ultramétrique la plus proche d' une dissimilarité au sens des moindres carrés, RAIRO, 14, 2, pp. 157-170, (1980) . | Numdam | MR 575663 | Zbl 0434.90051

[4] E. Diday., J. Lemaire., J. Pouget., F. Testu., Elements d'analyse des données, Paris, DUNOD, (1982) . | MR 691136 | Zbl 0504.62002

[5] E. Diday., "Croisements, ordres et ultramétriques : application à la recherche de consensus en classification automatique", Rapport de Recherche INRIA, n° 144, (1982).

[6] E. Diday., "Problèmes d'inversions en classification hiérarchique ", Revue de Statistique appliquée, Vol. XXXI, n° 1, pp. 45, (1982). | Numdam | Zbl 0538.62052

[7] J.G. Farris., "On comparing the shape of taxonomic trees ", Syst. Zool., 22, pp. 50-54, (1973).

[8] O. Frank., K. Svensson., "On probability distributions of single-linkage dendograms", J. Stat. Comput. Simul., 12, pp. 121-131, (1981). | MR 629041 | Zbl 0453.62048

[9] L. Hubert., "Some applications on graph theory and related non-metrics techniques to problems of approximate seriation", The British Journal of Mathematical and Statistical Psychology, Tome27, pp. 133-153, (1974). | Zbl 0285.92029

[10] L. Hubert., F. Baker., "The comparison and filting of given classification schemes", J. Math. Psychol. 16, pp. 233-253, (1977). | MR 484565 | Zbl 0368.62109

[11] D.G. Kendall., "Incidence matrices : interval graphs and seriation in archeologic", Pacific J. Math. 28, (1969). | MR 239990 | Zbl 0185.03301

[12] M.F. Mickevich., Taxonomic congruence, Ph. D. Dissertation, State Univ. of New York at Stony Brook, 70 pp., (1978).

[13] B. Leclerc., "An application of combinatorial theory to hierarchical classification" in : BARA J.L. et AI. Eds., Recent Developments in Statistics, Amsterdam North Holland, (1977). | MR 468039 | Zbl 0362.62063

[14] B. Leclerc., "Description combinatoire des ultramétriques ". Math. Sci. hum.19ème année, n° 73, pp. 5-37, (1981). | Numdam | MR 623034 | Zbl 0476.05079

[15] I.C. Lerman., Classification automatique et analyse ordinale des données, Paris Dunod, (1981). | MR 645150 | Zbl 0485.62051

[16] F.J. Rohlf., "Consensus indices for comparing classsifications",_ IBM Research Report R.C. 8940, (1981). | MR 673311