Characterizing functional dependencies in formal concept analysis with pattern structures

Jaume Baixeries 1 Mehdi Kaytoue 2 Amedeo Napoli 3
1 Departament de Llenguatges i Sistemes Informatics
LSI - Llenguatges i Sistemes Informàtics
2 DM2L - Data Mining and Machine Learning
LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information
3 ORPAILLEUR - Knowledge representation, reasonning
Inria Nancy - Grand Est, LORIA - NLPKD - Department of Natural Language Processing & Knowledge Discovery
Abstract : Computing functional dependencies from a relation is an impor-tant database topic, with many applications in database management, reverse engineering and query optimization. Whereas it has been deeply investigated in those fields, strong links exist with the mathematical framework of For-mal Concept Analysis. Considering the discovery of functional dependencies, it is indeed known that a relation can be expressed as the binary relation of a formal context, whose implications are equivalent to those dependencies. How-ever, this leads to a new data representation that is quadratic in the number of objects w.r.t. the original data. Here, we present an alternative avoiding such a data representation and show how to characterize functional dependencies using the formalism of pattern structures, an extension of classical FCA to handle complex data. We also show how another class of dependencies can be characterized with that framework, namely, degenerated multivalued depen-dencies. Finally, we discuss and compare the performances of our new approach in a series of experiments on classical benchmark datasets.
Type de document :
Article dans une revue
Annals of Mathematics and Artificial Intelligence, Springer Verlag, 2014, 72, pp.129 - 149. 〈10.1007/s10472-014-9400-3〉
Liste complète des métadonnées

Littérature citée [43 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01101107
Contributeur : Amedeo Napoli <>
Soumis le : vendredi 9 janvier 2015 - 17:04:10
Dernière modification le : jeudi 19 avril 2018 - 14:38:06
Document(s) archivé(s) le : vendredi 11 septembre 2015 - 01:40:16

Fichier

jb+mk+an-amai72-2014.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Jaume Baixeries, Mehdi Kaytoue, Amedeo Napoli. Characterizing functional dependencies in formal concept analysis with pattern structures. Annals of Mathematics and Artificial Intelligence, Springer Verlag, 2014, 72, pp.129 - 149. 〈10.1007/s10472-014-9400-3〉. 〈hal-01101107〉

Partager

Métriques

Consultations de la notice

363

Téléchargements de fichiers

190