Skip to main content
SpringerLink
Log in

On the use of ordered sets in problems of comparison and consensus of classifications

  • Authors Of Articles
  • Published:
Journal of Classification Aims and scope Submit manuscript

Abstract

Ordered set theory provides efficient tools for the problems of comparison and consensus of classifications Here, an overview of results obtained by the ordinal approach is presented Latticial or semilatticial structures of the main sets of classification models are described Many results on partitions are adaptable to dendrograms; many results on n-trees hold in any median semilattice and thus have counterparts on ordered trees and Buneman (phylogenetic) trees For the comparison of classifications, the semimodularity of the ordinal structures involved yields computable least-move metrics based on weighted or unweighted elementary transformations In the unweighted case, these metrics have simple characteristic properties For the consensus of classifications, the constructive, axiomatic, and optimization approaches are considered Natural consensus rules (majoritary, oligarchic, ) have adequate ordinal formalizations A unified presentation of Arrow-like characterization results is given In the cases of n-trees, ordered trees and Buneman trees, the majority rule is a significant example where the three approaches converge

Résumé

La théorie des ensembles ordonnés fournit des outils utiles pour les problèmes de comparaison et de consensus de classifications Nous présentons une revue des résultats obtenus grâce à l'approche ordinale Les principaux ensembles de modèles de classifications possèdent des structures de treillis ou de demi-treillis, qui sont décrites Le fait que bien des résultats sur les partitions s'adaptent aux hiérarchies indicées provient de la proximité de leurs structures latticielles; de même, des résultats sur les hiérarchies, portant en fait sur les demi-treillis à médianes, ont des équivalents pour les hiérarchies stratifiées et les arbres phylogénétiques de Buneman Pour la comparaison des classifications, la semi-modularité des structures ordinales prises en compte permet de définir des métriques de plus courts chemins, basées sur des ensembles de transformations élémentaires, et effectivement calculables Lorsque ces transformations ne sont pas pondérées, ces métriques se caractérisent simplement Pour le consensus de classifications, on considère les approches constructive, axiomatique et par optimisation d'un critère On a de bonnes formalisations ordinales de règles naturelles (majoritaire, oligarchique, ), à partir desquelles on obtient une présentation unifiée de divers résultats de type arrowien Dans le cas des hiérarchies, des hiérarchies stratifiées et des arbres de Buneman, un fait important, résultant de leurs structures de demi-treillis à médianes, est que la règle majoritaire peut être obtenue par chacune des trois approches

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • ADAMS, E N, III (1972), “Consensus Techniques and the Comparison of Taxonomic Trees,”Systematic Zoology, 21, 390–397

    Google Scholar 

  • AIGNER, M (1979),Combinatorial Theory, Berlin: Springer-Verlag

    Google Scholar 

  • ARABIE, P, and BOORMAN, S A (1973), “Multidimensional Scaling of Measures of Distances Between Partitions,”Journal of Mathematical Psychology, 17, 31–63

    Google Scholar 

  • ARROW, K J (1951),Social Choice and Individual Values, New York: Wiley

    Google Scholar 

  • BANDELT, H J, and BARTHELEMY, J P (1984), “Medians in Median Graphs,”Discrete Applied Mathematics, 8, 131–142

    Google Scholar 

  • BARBUT, M (1961), “Médiane, distributivité, éloignements,” repr (1980),Mathématiques et Sciences humaines, 70, 5–31

    Google Scholar 

  • BARBUT, M, and MONJARDET, B (1970),Ordre et Classification, Algèbre et Combinatoire, Paris: Hachette

    Google Scholar 

  • BARTHELEMY, J P (1978), “Remarques sur les propriétés métriques des ensembles ordonnés,”Mathématiques et Sciences humaines, 61, 39–60

    Google Scholar 

  • BARTHELEMY, J P (1979a), “Caractérisations axiomatiques de la distance de la différence symétrique entre des relations binaires,”Mathématiques et Sciences humaines, 67, 85–113

    Google Scholar 

  • BARTHELEMY, J P (1979b), “Propriétés métriques des ensembles ordonnés Comparaison et agrégation des relations binaires,” Thése, Université de Besancon

  • BARTHELEMY, J P (1985), “From Copair Hypergraphs to Median Graphs with Latent Vertices,” submitted

  • BARTHELEMY, J P, and LUONG, X (1986), “Mathématique, algorithmique et histoire des représentations arborées,” submitted

  • BARTHELEMY, J P, and MCMORRIS, F R (1986), “The Median Procedure for n-Trees,“Journal of Classification, 3,329–334

    Google Scholar 

  • BARTHELEMY, J P, LECLERC, B, and MONJARDET, B (1984a), “Ensembles ordonnés et taxonomie mathématique,” inOrders Description and Roles, eds M Pouzet and D Richard,Annals of Discrete Mathematics, 23, Amsterdam: North-Holland, 523–548

    Google Scholar 

  • BARTHELEMY, J P, LECLERC, B, and MONJARDET, B (1984b), “Quelques aspects du consensus en classification,” inData Analysis and Informatics III, eds E Didayet al, Amsterdam: North-Holland, 307–316

    Google Scholar 

  • BARTHELEMY, J P, and MONJARDET, B (1981), “The Median Procedure in Cluster Analysis and Social Choice Theory,”Mathematical Social Sciences, 1, 235–268

    Google Scholar 

  • BENZECRI, J P (1967), “Description mathématique des classifications,” repr (1973) inL'analyse des données, la Taxinomie, J P Benzécriet coll, Paris: Dunod, 119–152

    Google Scholar 

  • BIRKHOFF, G (1967),Lattice Theory, 3rd ed, Providence: American Mathematical Society

    Google Scholar 

  • BLYTH, T S, and JANOWITZ, M F (1972),Residuation Theory, Oxford: Pergamon Press

    Google Scholar 

  • BOORMAN, S A, and ARABIE, P (1972), “Structural Measures and the Method of Sorting,” inMultidimensional Scaling, Vol 1, Theory and Applications in the Behavioral Sciences, eds R N Shepard, A K Romney and S B Nerlove, New York: Seminar Press, 226–249

    Google Scholar 

  • BOORMAN, S A, and OLIVIER, D C (1973), “Metrics on Spaces of Finite Trees,”Journal of Mathematical Psychology, 10, 26–59

    Google Scholar 

  • BORDA, J C (1784),Mémoire sur les élections au scrutin, Histoire de l'Académie Royale des Sciences pour 1781, Paris

  • BORDES, G (1976), “Métriques bornées définies par des valuations sur un demi-treillis,”Mathématiques et Sciences humaines, 56, 89–96

    Google Scholar 

  • BUNEMAN, P (1971), “The Recovery of Trees from Measures of Dissimilarity,” inMathematics in Archaeological and Historical Sciences, eds F R Hodson, D G Kendall and P Tautu, Edinburgh: Edinburgh University Press, 387–395

    Google Scholar 

  • COMTET, L (1970), “Sur le quatrième problème et les nombres de Schröder,”Comptes-Rendus Académie des Sciences de Paris, A-271, 913–916

    Google Scholar 

  • COMTET, L (1974),Advanced Combinatorics, Dordrecht: Reidel

    Google Scholar 

  • CONDORCET, M J A (1785),Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix, Paris

  • DAY, W H E (1981), “The Complexity of Computing Metric Distances Between Partitions,”Mathematical Social Sciences, 1, 269–287

    Google Scholar 

  • DAY, W H E (1983a), “The Role of Complexity in Comparing Classifications,”Mathematical Biosciences, 66, 97–114

    Google Scholar 

  • DAY, W H E (1983b), “Computationally Difficult Parsimony Problems in Phylogenetic Systematics,”Journal of Theoretical Biology, 103, 429–438

    Google Scholar 

  • DAY, W H E (1985), “Optimal Algorithms for Comparing Trees with Labelled Leaves,”Journal of Classification, 2, 7–28

    MathSciNet  Google Scholar 

  • DAY, W H E, and FAITH, D P (1986), “A Model in Partial Orders for Comparing Objects by Dualistic Measures,”Mathematical Biosciences, 8, 179–192

    Google Scholar 

  • DAY, W H E, and MCMORRIS, F R (1985), “A Formalization of Consensus Index Methods,”Bulletin of Mathematical Biology, 47, 215–229

    Google Scholar 

  • DAY, W H E, and WELLS, R S (1984), “Extremes in the Complexity of Computing Metric Distances Between Partitions,”IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-6, 69–73

    Google Scholar 

  • DIJKSTRA, E W (1959), “A Note on Two Problems in Connection with Graphs,”Numerische Mathematik, 1, 269–271

    Article  Google Scholar 

  • DOBINSKY, T (1877), “Summirung der Reihe Σn m/n′ furm = 1,2,3,4,5,,”Grunert Archiv, 61, 333–336

    Google Scholar 

  • FINDEN, C R, and GORDON, A D (1985), “Obtaining Common Pruned Trees,”Journal of Classification, 2, 255–276

    Google Scholar 

  • FLAMENT, C (1963),Application of Graph Theory to Group Structure, New York: Prentice Hall

    Google Scholar 

  • FOULDS, L R, and ROBINSON, R W (1980), “Determining the Asymptotic Number of Phylogenetic Trees,” inCombinatorial Mathematics VII, Lecture Notes in Mathematics 829, Berlin Springer-Verlag, 110–126

    Google Scholar 

  • GIBBONS, A (1985),Algorithmic Graph Theory, Cambridge (UK): Cambridge University Press

    Google Scholar 

  • GOWER, J C, and ROSS, G J S (1969), “Minimum Spanning Tree and Single Linkage Cluster Analysis,”Applied Statistics, 18, 54–64

    Google Scholar 

  • GRATZER, G (1978),General Lattice Theory, Basel: Birkhaüser Verlag

    Google Scholar 

  • GUENOCHE, A (1986), “Etude comparative de cinq algorithmes d'approximation des dissimilarités par des arbres à distances additives,”Mathématiques et Sciences humaines, to appear

  • GUILBAUD, G Th (1952), “Les théories de l'intérêt général et le problème logique de l'agrégation,”Economie Appliquée, 5, 501–551, repr (1968) inEléments de la Théorie des Jeux, Paris: Dunod

    Google Scholar 

  • HARARY, F (1969),Graph Theory, Reading, Mass Addison-Wesley

    Google Scholar 

  • HARDING, E S (1971), “The Probability of Rooted Tree-Shapes Generated by Random Bifurcations,”Advances in Applied Probability, 3, 44–77

    Google Scholar 

  • HARTIGAN, J A (1975),Clustering Algorithms, New York Wiley

    Google Scholar 

  • HUBERT, L (1977), “Data Analysis Implications of Some Concepts Related to the Cuts of a Graph,”Journal of Mathematical Psychology, 15, 199–208

    Article  Google Scholar 

  • HUBERT, L, and BAKER, F B (1977), “The Comparison and Fitting of Given Classification Schemes,”Journal of Mathematical Psychology, 16, 233–255

    Article  Google Scholar 

  • JANOWITZ, M F (1978), “An Order Theoretic Model for Cluster Analysis,”SIAM Journal on Applied Mathematics, 34, 55–72

    Article  Google Scholar 

  • JANOWITZ, M F (1985), “A Generalized Setting for Consensus Functions,” University of Massachusetts, Department of Mathematics and Statistics

  • JARDINE, N, and SIBSON, R (1971),Mathematical Taxonomy, London: Wiley

    Google Scholar 

  • JOHNSON, S C (1967), “Hierarchical Clustering Schemes,”Psychometrika, 32, 241–254

    Google Scholar 

  • KEMENY, J G (1959), “Mathematics without Numbers,”Daedalus, 88, 575–591

    Google Scholar 

  • KNUTH, D E (1973),The Art of Computer Programming, Vol 3, Searching, Reading, Mass: Addison-Wesley

    Google Scholar 

  • LECLERC, B (1979), “Semi-modularité des treillis d'ultramétriques,”Comptes-Rendus Académie des Sciences de Paris, A-288, 575–577

    Google Scholar 

  • LECLERC, B (1981), “Description combinatoire des ultramétriques,”Mathématiques et Sciences humaines, 73, 5–37

    Google Scholar 

  • LECLERC, B (1984a), “Efficient and Binary Consensus Functions on Transitively Valued Relations,”Mathematical Social Sciences, 8, 45–61

    Article  Google Scholar 

  • LECLERC, B (1984b), “Indices compatibles avec une structure de treillis et fermeture résiduelle,” Technical Report P 011, Centre d'Analyse et de Mathématique Sociales

  • LECLERC, B (1985a) “Les hiérarchies de parties et leurs demi-treillis,”Mathématiques et Sciences humaines, 89, 5–34

    Google Scholar 

  • LECLERC, B (1985b), “La comparaison des hiérarchies: indices et métriques,”Mathématiques et Sciences humaines, 92, 5–40

    Google Scholar 

  • MARCOTORCHINO, F, and MICHAUD, P (1982), “Agrégation de similarités en classification automatique,”Revue de Statistique Appliquée, 30, 21–44

    Google Scholar 

  • MARGUSH, T (1982), “Distances Between Trees,”Discrete Applied Mathematics, 4, 281–290

    Article  Google Scholar 

  • MARGUSH, T, and MCMORRIS, F R (1981), “Consensus n-Trees,”Bulletin of Mathematical Biology, 43, 239–244

    Google Scholar 

  • MCMORRIS, F R (1985), “Axioms for Consensus Functions on Undirected Phylogenetic Trees,”Mathematical Biosciences, 74, 17–21

    Article  Google Scholar 

  • MCMORRIS F R, and NEUMANN, D A (1983), “Consensus Functions on Trees,”Mathematical Social Sciences, 4, 131–136

    Article  Google Scholar 

  • MIRKIN, B G (1975), “On the Problem of Reconciling Partitions,” inQuantitative Sociology, International Perspectives on Mathematical and Statistical Modelling, New York: Academic Press, 441–449

    Google Scholar 

  • MIRKIN, B G, and CHERNYI, L B (1970), “On Measurement of Distance Between Partitions of a Finite Set of Units,”Automation and Remote Control, 31, 786–792

    Google Scholar 

  • MONJARDET, B (1976), “Caractérisations métriques des ensembles ordonnés semimodulaires,”Mathématiques et Sciences humaines, 56, 77–87

    Google Scholar 

  • MONJARDET, B (1980), “Théorie et applications de la médiane dans les treillis distributifs finis,”Annals of Discrete Mathematics, 9, 87–91

    Google Scholar 

  • MONJARDET, B (1981), “Metrics on Partially Ordered Sets, A Survey,”Discrete Mathematics, 35, 173–184

    Article  Google Scholar 

  • MONJARDET, B (1986), “Characterizations of Polynomial Functions in Median Semilattices,” Technical Report, Centre d'Analyse et de Mathématique Sociales

  • NEUMANN, D A (1983), “Faithful Consensus Methods for n-Trees,”Mathematical Biosciences, 63, 271–287

    Article  Google Scholar 

  • NEUMANN, D A, and NORTON, V (1985), “Consensus of Partitions with Applications to Other Structures,” Technical Report n° 85-20, Bowling Green State University, Department of Mathematics and Statistics

  • PUDLAK, P, and TUMA, J (1980), “Every Finite Lattice Can be Embedded in the Lattice of all Equivalences Over a Finite Set,”Algebra Universalis, 10, 74–95

    Google Scholar 

  • REGNIER, S (1965), “Sur quelques aspects mathématiques des problémes de classification automatique,”ICC Bulletin, 4, 175–191, repr (1983),Mathématiques et Sciences humaines, 82, 13–29

    Google Scholar 

  • REGNIER, S (1977), “Stabilité d'un opérateur de classification,”Mathématiques et Sciences humaines, 60, 21–30

    Google Scholar 

  • ROBINSON, D F (1971) “Comparison of Labelled Trees with Valency Three,”Journal of Combinatorial Theory, 11, 105–119

    Article  Google Scholar 

  • ROBINSON, D F, and FOULDS, L R (1981), “Comparison of Phylogenetic Trees,”Mathematical Biosciences, 53, 131–147

    Article  Google Scholar 

  • ROHLF, F J (1982), “Consensus Indices for Comparing Classifications,“Mathematical Biosciences, 59, 131–144

    Article  Google Scholar 

  • SCHADER, M (1980), “Hierarchical Analysis: Classification with Ordinal Object Dissimilarities,”Metrika, 27, 127–132

    Google Scholar 

  • SHOLANDER, M (1954), “Medians, Lattices and Trees,”Proceedings of the American Mathematical Society, 5, 808–812

    Google Scholar 

  • STINEBRICKNER, R (1984), “s-Consensus Trees and Indices,”Bulletin of Mathematical biology, 46, 923–935

    Google Scholar 

  • YOUNG, H P, and LEVENGLICK, A (1978), “A Consistent Extension of Condorcet's Election Principle,”SIAm Journal on Applied Mathematics, 35, 285–300

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. E N S T, 46 rue Barrault, F-75634, Paris Cedex 13, France

    Jean-Pierre Barthélemy

  2. C A M S, 54 boulevard Raspail, F-75270, Paris Cedex 06, France

    Bruno Leclerc & Bernard Monjardet

Authors
  1. Jean-Pierre Barthélemy
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bruno Leclerc
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Bernard Monjardet
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

The authors would like to thank the anonymous referees for helpful suggestions on the first draft of this paper, and W H E Day for his comments and his significant improvements of style

Rights and permissions

Reprints and permissions

About this article

Cite this article

Barthélemy, JP., Leclerc, B. & Monjardet, B. On the use of ordered sets in problems of comparison and consensus of classifications. Journal of Classification 3, 187–224 (1986). https://doi.org/10.1007/BF01894188

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01894188

Keywords

Search

Navigation