Croisements, ordres et ultramétriques

Edwin Diday

Mathématiques et Sciences Humaines (1983)

  • Volume: 83, page 31-54
  • ISSN: 0987-6936

Abstract

top
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.

How to cite

top

Diday, Edwin. "Croisements, ordres et ultramétriques." Mathématiques et Sciences Humaines 83 (1983): 31-54. <http://eudml.org/doc/94292>.

@article{Diday1983,
abstract = {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.},
author = {Diday, Edwin},
journal = {Mathématiques et Sciences Humaines},
keywords = {clustering; order; hierarchies; ultrametrics; consensus; overlapping clusters; dissimilarity index; compatibility; extension of Robinson matrices; minimum spanning chains; minimum spanning trees},
language = {fre},
pages = {31-54},
publisher = {Ecole Pratique des hautes études, Centre de mathématique sociale et de statistique},
title = {Croisements, ordres et ultramétriques},
url = {http://eudml.org/doc/94292},
volume = {83},
year = {1983},
}

TY - JOUR
AU - Diday, Edwin
TI - Croisements, ordres et ultramétriques
JO - Mathématiques et Sciences Humaines
PY - 1983
PB - Ecole Pratique des hautes études, Centre de mathématique sociale et de statistique
VL - 83
SP - 31
EP - 54
AB - 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.
LA - fre
KW - clustering; order; hierarchies; ultrametrics; consensus; overlapping clusters; dissimilarity index; compatibility; extension of Robinson matrices; minimum spanning chains; minimum spanning trees
UR - http://eudml.org/doc/94292
ER -

References

top
  1. [1] E.N. Adams., "Consensus techniques and the comparison of taxonomic trees", Syst. Zool, 21, pp. 390-397, (1972). 
  2. [2] G. Brossier., "Représentation ordonnée des classifications hiérarchiques", Statistique et Analyse des données, Vol. 2., pp. 31-44, (1980). 
  3. [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) . Zbl0434.90051MR575663
  4. [4] E. Diday., J. Lemaire., J. Pouget., F. Testu., Elements d'analyse des données, Paris, DUNOD, (1982) . Zbl0504.62002MR691136
  5. [5] E. Diday., "Croisements, ordres et ultramétriques : application à la recherche de consensus en classification automatique", Rapport de Recherche INRIA, n° 144, (1982). Zbl0607.62074
  6. [6] E. Diday., "Problèmes d'inversions en classification hiérarchique ", Revue de Statistique appliquée, Vol. XXXI, n° 1, pp. 45, (1982). Zbl0538.62052
  7. [7] J.G. Farris., "On comparing the shape of taxonomic trees ", Syst. Zool., 22, pp. 50-54, (1973). 
  8. [8] O. Frank., K. Svensson., "On probability distributions of single-linkage dendograms", J. Stat. Comput. Simul., 12, pp. 121-131, (1981). Zbl0453.62048MR629041
  9. [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). Zbl0285.92029
  10. [10] L. Hubert., F. Baker., "The comparison and filting of given classification schemes", J. Math. Psychol.16, pp. 233-253, (1977). Zbl0368.62109MR484565
  11. [11] D.G. Kendall., "Incidence matrices : interval graphs and seriation in archeologic", Pacific J. Math.28, (1969). Zbl0185.03301MR239990
  12. [12] M.F. Mickevich., Taxonomic congruence, Ph. D. Dissertation, State Univ. of New York at Stony Brook, 70 pp., (1978). 
  13. [13] B. Leclerc., "An application of combinatorial theory to hierarchical classification" in : BARA J.L. et AI. Eds., Recent Developments in Statistics, AmsterdamNorth Holland, (1977). Zbl0362.62063MR468039
  14. [14] B. Leclerc., "Description combinatoire des ultramétriques ". Math. Sci. hum.19ème année, n° 73, pp. 5-37, (1981). Zbl0476.05079MR623034
  15. [15] I.C. Lerman., Classification automatique et analyse ordinale des données, ParisDunod, (1981). Zbl0485.62051MR645150
  16. [16] F.J. Rohlf., "Consensus indices for comparing classsifications",_ IBM Research Report R.C.8940, (1981). MR673311

Citations in EuDML Documents

top
  1. Feridoun Sadat-Aghili, Instabilité hiérarchique d'un ensemble de données économiques et applications
  2. P. Bertrand, E. Diday, Une généralisation des arbres hiérarchiques : les représentations pyramidales
  3. Bruno Leclerc, Caractérisation, construction et dénombrement des ultramétriques supérieures minimales
  4. Bruno Leclerc, Arbres minimums communs et compatibilité de données de types variés
  5. A. Batbedat, Les dissimilarités médas ou arbas
  6. Bruno Leclerc, Guy Cucumel, Consensus en classification : une revue bibliographique
  7. A. Guenoche, B. Monjardet, Méthodes ordinales et combinatoires en analyse des données

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.