Les termes : un modèle algébrique de représentation et de structuration de données symboliques

Marie-Catherine Daniel-Vatonne; Colin de la Higuera

Mathématiques et Sciences Humaines (1993)

  • Volume: 122, page 41-63
  • ISSN: 0987-6936

Abstract

top
Our framework is concept analysis. Our goal is to generalize systems based on descriptions by nominal or binary variables, by taking into account the internal structure of data. The problem nevertheless is not to lose in algorithmic complexity what is gained in quality of the description. Under these considerations, ordered trees seem a good compromise. The representation system we propose is based on an algebraic model : magmas. Typed terms (isomorphic to oriented trees) are used to describe the data (and class characterization). Their interpretation is intuitive and recursive descriptions are allowed. A natural partial order, generalization, induces a lattice structure on these terms. Term construction, term comparison, computation of the supremum and infimum of sets of terms are all polynomially tractable problems. This model preserves most properties of the description by binary variables ; in particular we show how the Galois lattice between sets of objects and their description can be constructed. As an illustration this lattice is constructed from data related to the transmission of colour-blindness.

How to cite

top

Daniel-Vatonne, Marie-Catherine, and de la Higuera, Colin. "Les termes : un modèle algébrique de représentation et de structuration de données symboliques." Mathématiques et Sciences Humaines 122 (1993): 41-63. <http://eudml.org/doc/94442>.

@article{Daniel1993,
abstract = {Nos travaux se situent dans le cadre de l'analyse conceptuelle des données. Notre objectif est de généraliser les représentations par variables binaires ou nominales en y adjoignant la modélisation de structures internes. Le problème est de ne pas perdre en complexité algorithmique ce qui est gagné en puissance de représentation. Selon ces considérations, décrire les données et des classes de données par des structures arborescentes semble un bon compromis. Le système de représentation que nous proposons s'appuie sur un modèle algébrique : les magmas. Il permet de construire des termes assimilables à des arborescences finies, étiquetées et typées. Leur interprétation est intuitive et ils autorisent les descriptions récursives. Une relation d'ordre naturelle, la généralisation, induit un treillis sur les termes. La construction des termes, leur comparaison dans l'ordre, le calcul des bornes supérieures et inférieures ont une complexité polynomiale. Ce modèle inclut le cadre binaire tout en conservant certaines propriétés. En particulier, nous montrons que l'on peut construire un treillis de Galois mettant en correspondance des ensembles d'objets et leurs descriptions par des termes. Une application est donnée à titre d'illustration, portant sur la transmission héréditaire du daltonisme.},
author = {Daniel-Vatonne, Marie-Catherine, de la Higuera, Colin},
journal = {Mathématiques et Sciences Humaines},
keywords = {lattice structure on terms; term construction; internal structure of data; algorithmic complexity; ordered trees; magmas; term comparison; Galois lattice},
language = {fre},
pages = {41-63},
publisher = {Ecole des hautes-études en sciences sociales},
title = {Les termes : un modèle algébrique de représentation et de structuration de données symboliques},
url = {http://eudml.org/doc/94442},
volume = {122},
year = {1993},
}

TY - JOUR
AU - Daniel-Vatonne, Marie-Catherine
AU - de la Higuera, Colin
TI - Les termes : un modèle algébrique de représentation et de structuration de données symboliques
JO - Mathématiques et Sciences Humaines
PY - 1993
PB - Ecole des hautes-études en sciences sociales
VL - 122
SP - 41
EP - 63
AB - Nos travaux se situent dans le cadre de l'analyse conceptuelle des données. Notre objectif est de généraliser les représentations par variables binaires ou nominales en y adjoignant la modélisation de structures internes. Le problème est de ne pas perdre en complexité algorithmique ce qui est gagné en puissance de représentation. Selon ces considérations, décrire les données et des classes de données par des structures arborescentes semble un bon compromis. Le système de représentation que nous proposons s'appuie sur un modèle algébrique : les magmas. Il permet de construire des termes assimilables à des arborescences finies, étiquetées et typées. Leur interprétation est intuitive et ils autorisent les descriptions récursives. Une relation d'ordre naturelle, la généralisation, induit un treillis sur les termes. La construction des termes, leur comparaison dans l'ordre, le calcul des bornes supérieures et inférieures ont une complexité polynomiale. Ce modèle inclut le cadre binaire tout en conservant certaines propriétés. En particulier, nous montrons que l'on peut construire un treillis de Galois mettant en correspondance des ensembles d'objets et leurs descriptions par des termes. Une application est donnée à titre d'illustration, portant sur la transmission héréditaire du daltonisme.
LA - fre
KW - lattice structure on terms; term construction; internal structure of data; algorithmic complexity; ordered trees; magmas; term comparison; Galois lattice
UR - http://eudml.org/doc/94442
ER -

References

top
  1. [1] Barbut M., Monjardet B., Ordre et classification : Algèbre et combinatoire (tome I et II), Paris, Collection Hachette Université, Hachette,1970. Zbl0267.06001MR419311
  2. [2] Birkhoff G., Lattice theory, Colloquium Publications, vol. XXV, AMS, Providence, 3ème édition, 1967. Zbl0153.02501MR227053
  3. [3] Bordat J.P., "Calcul pratique du treillis de Galois d'une correspondance", Mathématiques et Sciences Humaines, 24e année, n° 96,1986, pp. 31-47. Zbl0626.06007MR878296
  4. [4] Daniel-Vatonne M.C., Les termes : un modèle de représentation et structuration de données symboliques, thèse de Doctorat, Université des Sciences et Techniques du Languedoc, Montpellier II, Février 1993. 
  5. [5] Dietterich T.G., Michalski R.S., "A Comparating Review of Selected Methods for Learning from Examples ", Machine learning: an Artificial Intelligence approach, Tioga, Palo Alto1983, pp. 41-75. 
  6. [6] Gascuel O., "PLage : a way to give and use knowledge in learning", in Machine and human learning, Y. Kodratoff Ed., Michaël Horwood series, Artificial Intelligence, 1989, pp. 105-120. 
  7. [7] Gascuel O., Guénoche A., "Approches symboliques/numériques en apprentissage", 3èmes journées nationales PRC-GDR, Intelligence Artificielle, B. Bouchon-Meunier Ed., Hermes, 1990, pp. 91-110. 
  8. [8] Goguen J.A., Thatcher J.W., Wagner E.G., Wright J.B., "Initial algebra semantics and continuous algebras", A. C.M, vol 24:1 (1977), pp. 68-95. Zbl0359.68018MR520711
  9. [9] Guénoche A., "Generalization and Conceptual Classification: Indices and algorithm ", Data analysis, learning symbolic and numeric knowledge, E. Diday Ed., Nova Science Pub1982, pp. 503-510. 
  10. [10] Guessarian I., "Algebraic Semantics", Lecture Notes, Computer Science , 99, Goos & Hartmanis Ed., Springer-Verlag, 1981. Zbl0474.68010MR617908
  11. [11] Haussler D., "Learning conjunctive concepts in structural domains", Machine learning, vol 4 (1989), pp. 7-40. 
  12. [12] Liquière M., Apprentissage à partir d'objets structurés, thèse de Doctorat, Université des Sciences et Techniques du Languedoc, Montpellier II, Février 1990. 
  13. [13] Monjardet B., Problèmes de transversalité dans les hypergraphes, les ensembles ordonnés, et en théorie de la décision collective., thèse de Doctorat d'Etat, Université Paris VI, 1974. 
  14. [14] Pitt L., Reinke R.E., "Criteria for polynomial-time (conceptual) clustering", Machine Learning, vol 2 (1988), pp. 371-396. 
  15. [ 15] Wille R., "Restructuring lattice theory : an approach based on hierarchies of concepts", Ordered sets, I. Rival Ed., Reidel, Dordrecht- Boston,1982, pp. 445-470. Zbl0491.06008MR661303
  16. [16] Winston P.H., "Learning structural descriptions from examples", The psychology of Computer Vision, P.H. Winston Ed., McGraw Hill, New-York, ch.5,1975. 

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.