Skip to main content
SpringerLink
Log in

Symbolic objects: order structure and pyramidal clustering

  • Data Analysis: Progress And Recent Trends
  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

We recall a formalism based on the notion of symbolic object (Diday [15], Brito and Diday [8]), which allows to generalize the classical tabular model of Data Analysis. We study assertion objects, a particular class of symbolic objects which is endowed with a partial order and a quasi-order. Operations are then defined on symbolic objects. We study the property of completeness, already considered in Brito and Diday [8], which expresses the duality extension intension. We formalize this notion in the framework of the theory of Galois connections and study the order structure of complete assertion objects. We introduce the notion ofc-connection, as being a pair of mappings (f,g) between two partially ordered sets which should fulfil given conditions. A complete assertion object is then defined as a fixed point of the composedf o g; this mapping is called a “completeness operator” for it “completes” a given assertion object. The set of complete assertion objects forms a lattice and we state how suprema and infima are obtained. The lattice structure being too complex to allow a clustering study of a data set, we have proposed a pyramidal clustering approach [8]. The symbolic pyramidal clustering method builds a pyramid bottom-up, each cluster being described by a complete assertion object whose extension is the cluster itself. We thus obtain an inheritance structure on the data set. The inheritance structure then leads to the generation of rules.

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

  1. A. Arnault and P. Nicole,La Logique ou l'Art de Penser (Flammarion, Paris, 1662, 1970).

    Google Scholar 

  2. M. Barbut and B. Monjardet,Ordre et Classification, Algèbre et Combinatoire, Vols. 1 and 2 (Hachette, Paris, 1970).

    Google Scholar 

  3. P. Bertrand, Etude de la représentation pyramidale, Thèse de 3ème cycle, Univ. Paris-IX Dauphine (1986).

  4. P. Bertrand and E. Diday, A visual representation of the compatibility between an order and a dissimilarity index: the pyramids, in: Comp. Statist. Quarterly 2 (1985) 31–42.

    Google Scholar 

  5. G. Birkhoff,Lattice Theory, American Mathematical Society Colloquium Publications, Vol. 25, 3rd ed. (1967).

  6. G. Bisson, Learning of rule systems by combining clustering and generalization, in:Symbolic-Numeric Data Analysis and Learning, eds. E. Diday and Y. Lechevallie (Nova Science, New York, 1991).

    Google Scholar 

  7. P. Brito, Analyse de données symboliques. Pyramides d'héritage. Thèse, Université Paris IX-Dauphine, Paris (1991).

    Google Scholar 

  8. P. Brito and E. Diday, Pyramidal representation of symbolic objects, in:Knowledge, Data and Computer-Assisted Decisions, Proc. NATO Advanced Workshop on Data, Expert Knowledge and Decision, Hamburg, eds. M. Schader and W. Gaul (Springer, 1990).

  9. F.A.T. De Carvalho, J. Lebbe, R. Vignes and E. Diday, Dissimilarity in symbolic data analysis, in:Proc. COMPSTAT, 9th Symp. on Computational Statistics, Dubrovnik, Yugoslavia (1990).

  10. C. Decaestecker. Apprentissage en classification conceptuelle incrementale, Thése, Univ. Libre de Bruxelles (1991).

  11. E. Diday, Nouveaux concepts et nouvelles méthodes en classification automatique, Thèse d'Etat, Univ. Paris VI (1972).

    Google Scholar 

  12. E. Diday, Selection typologique de paramètres, Rapport de Recherche INRIA No. 188, INRIA, Rocquencourt, Le Chesnay (1976).

    Google Scholar 

  13. E. Diday, Une représentation visuelle des classes empiétantes: les pyramides, Rapport de Recherche INRIA No. 291, INRIA, Rocquencourt, Le Chesnay (1984).

    Google Scholar 

  14. E. Diday, Orders and overlapping clusters by pyramids, in:Multidimensional Data Analysis Proc., eds. J. De Leeuw et al. (DSWO Press, Leiden, 1986).

    Google Scholar 

  15. E. Diday, The symbolic approach in clustering and related methods of data analysis: the basic choices, in:Proc. Ist Conf. of the International Federation of Classification Societies, Technical Univ. of Aachen, ed. H. Bock (1987).

  16. E. Diday, Introduction à l'approche symbolique en Analyse des Données, RAIRO 23 (1989).

  17. E. Diday, Knowledge representation and symbolic data analysis, in:Knowledge, Data and Computer-Assisted Decisions, Proc. NATO Advanced Workshop on Data, Expert Knowledge and Decision, Hamburg, eds. M. Schader and W. Gaul (Springer, 1989).

  18. E. Diday, Des objets de l'Analyse des Données à ceux de l'Analyse des Connaissances, in:Induction Symbolique Numérique à Partir de Données, eds. Y. Kodratoff and E. Diday (Cepadues, 1991).

  19. E. Diday, G. Govaert, Y. Lechevallier and J. Sidi, Clustering in pattern recognition, in:Proc. NATO Advanced Study Institute on Digital Image Processing and Analysis, Bonas, ed. J.C. Simon (1980).

  20. E. Diday and L. Roy, Generating rules by symbolic data analysis and application to soil feature recognition, in:Actes des 8emes Journees Internationales “Les systèmes experts et leurs applications”. Avignon (1988) pp. 533–549.

  21. E. Diday and J.C. Simon, Clustering analysis, in:Communication and Cybernetics 10, Digital Pattern Recognition, ed. K.S. Fu (Springer, 1976) pp. 47–94.

  22. J. Dorst and P. Dandelot, Guide des Grands Mammiferes d'Afrique (Delachaux et Niestlé, Neuchātel, 1972).

    Google Scholar 

  23. V. Duquenne, Contextual implications between attributes and some representation properties for finite lattices, Rapport C.A.M.S. P.023, Centre d'Analyse et de Mathématiques Sociales, Maison des Sciences de L'Homme. Paris (1986).

    Google Scholar 

  24. C. Durand, Ordres et graphes pseudo-hiérarchiques: théories et optimisation algorithmique, Thèse, Univ. de Provence Saint Charles (1989).

  25. D.H. Fisher, Conceptual clustering, learning from examples and inference, in:Proc. 4th Int. Workshop on Machine Learning. Irvine, CA (1987).

  26. D.H. Fisher, Improving inference through conceptual clustering,Proc. AAAl-87, 6th National Conf. on Artificial Intelligence. Seattle, WA (1987).

  27. O. Gascuel, Inductive learning, numerical criteria and combinatorial optimization, some results, in:Proc. Conf. on Data Analysis, Learning Symbolic and Numerical Knowledge, Antibes, ed. E. Diday (Nova Science, New York, 1989).

    Google Scholar 

  28. C. Jacq, Combining a decision tree with kernel estimates, in:Symbolic Numeric Data Analysis and Learning, eds. E. Diday and Y. Lechevallier (Nova Science, New York, 1991).

    Google Scholar 

  29. J. Lebbe, Représentation des concepts en biologie et en médecine. Thèse, Université Paris-VI, Paris (1991).

    Google Scholar 

  30. R. Michalski, Aqual I Computer implementation of a variable-valued logic system VL1 and examples of its application to pattern recognition, in:Proc. 1st Int. Joint Conf. on Pattern Recognition, Washington, DC (1973) pp. 3–17.

  31. R. Michalski, Pattern recognition as rule-guided inductive inference, IEEE Trans. Pattern Anal. Machine Int. PAMI-2 (1980).

  32. R. Michalski, Knowledge acquisition through conceptual clustering: a theoretical framework and an algorithm for partitioning data into conjunctive concepts, Int. J. Policy Anal. Inf. Syst. (1980).

  33. R. Michalski, A theory and methodology of inductive learning, in:Machine Learning I, eds. R.S. Michalsky, J.G. Carbonell and T.M. Mitchell (Springer, 1984) pp. 83–134.

  34. R. Michalski, E. Diday and R. Stepp, A recent advance in Data Analysis: Clustering objects into classes characterized by conjunctive concepts, in:Progress in Pattern Recognition, Vol. 1. eds. L. Kanal and A. Rosenfeld (1982).

  35. R. Michalski and R. Stepp, An application of A1 techniques to structuring objects into an optimal conceptual hierarchy, in:Proc. 7th Int. Joint Conf. on Artificial Intelligence, Vancouver, Canada (1981).

  36. R. Michalski and R. Stepp, Revealing conceptual structure in data by inductive inference, in:Machine Intelligence, Vol. 10 (1981).

  37. R. Michalski and R. Stepp, Learning from observation: conceptual clustering, in:Machine Learning I, eds. R.S. Michalsky, J.G. Carbonell and T.M. Mitchell (Springer, 1984) pp. 331–363.

  38. T. Mitchell, Generalization as search, Art. Int. 18 (1982) 203–226.

    Article  Google Scholar 

  39. L. Rendell, A general framework for induction and a study of selective induction, Machine Learning 1 (1986) 177–226.

    Google Scholar 

  40. M. Sebag and M. Schoenauer, Incremental learning of rules and meta rules, in:Proc. 7th Int. Conf. on Machine Learning, eds. B. Porter and R. Mooney (Morgan Kaufmann, 1990).

  41. J. Sidi, L'approche logique en classification automatique et reconnaissance des formes. Thèse de 3ème cycle, Univ. Pierre et Marie Curie (1980).

  42. R.E. Stepp and R.S. Michalski, Conceptual clustering: inventing goal-oriented classifications of structured objects, in:Machine Learning II, eds. R.S. Michalsky, J.G. Carbonell and T.M. Mitchell (Morgan Kaufmann, Los Altos, CA, 1986) pp. 471–498.

    Google Scholar 

  43. J.C. Stoffel, The theory of prime events. Data Analysis for sample vectors with inherently discrete variables. in:Information Processing 74 (1974).

  44. R. Vignes. Caracterisation automatique de groupes biologiques, Thèse. Université Paris-VI. Paris (1991).

    Google Scholar 

  45. R. Wille, Restructuring lattice theory: an approach based on hierarchies of concepts, in:Proc. Symp. on Ordered Sets, ed. I. Rival (Reidel, Dordrecht/Boston, 1982) pp. 445–470.

    Google Scholar 

  46. M. Lebowitz, Experiments with incremental concept formation: UNINEM, in:Machine Learning 2 (1987) pp. 103–138.

    Google Scholar 

  47. R. Michalsky, Automated constructions of classifications: conceptual clustering versus numerical taxonomy, IEEE Trans. Pattern Anal. Machine Int. PAMI-5 (1983).

Download references

Author information

Authors and Affiliations

  1. ENST, Dept. Informatique, 46 rue Barrault, F-75634, Paris Cedex 13, France

    P. Brito

  2. INRIA, Projet CLOREC, Rocquencourt, F-78153, Le Chesnay Cedex, France

    P. Brito

Authors
  1. P. Brito
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Brito, P. Symbolic objects: order structure and pyramidal clustering. Ann Oper Res 55, 277–297 (1995). https://doi.org/10.1007/BF02030863

Download citation

  • Issue Date:

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

Keywords

Search

Navigation