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

Daniel-Vatonne, Marie-Catherine; De la Higuera, Colin

Mathématiques informatique et sciences humaines, Tome 122 (1993), pp. 41-63.

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.

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.

[1] Barbut M., Monjardet B., Ordre et classification : Algèbre et combinatoire (tome I et II), Paris, Collection Hachette Université, Hachette,1970. | MR | Zbl

[2] Birkhoff G., Lattice theory, Colloquium Publications, vol. XXV, AMS, Providence, 3ème édition, 1967. | MR | Zbl

[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. | EuDML | Numdam | MR | Zbl

[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] Dietterich T.G., Michalski R.S., "A Comparating Review of Selected Methods for Learning from Examples ", Machine learning: an Artificial Intelligence approach, Tioga, Palo Alto 1983, pp. 41-75.

[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] 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] 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. | MR | Zbl

[9] Guénoche A., "Generalization and Conceptual Classification: Indices and algorithm ", Data analysis, learning symbolic and numeric knowledge, E. Diday Ed., Nova Science Pub 1982, pp. 503-510.

[10] Guessarian I., "Algebraic Semantics", Lecture Notes, Computer Science , 99, Goos & Hartmanis Ed., Springer-Verlag, 1981. | MR | Zbl

[11] Haussler D., "Learning conjunctive concepts in structural domains", Machine learning, vol 4 (1989), pp. 7-40.

[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] 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] Pitt L., Reinke R.E., "Criteria for polynomial-time (conceptual) clustering", Machine Learning, vol 2 (1988), pp. 371-396.

[ 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. | MR | Zbl

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