Characterizing Approximate-Matching Dependencies in Formal Concept Analysis with Pattern Structures

Jaume Baixeries 1 Victor Codocedo 2 Mehdi Kaytoue 3, 4 Amedeo Napoli 5
3 DM2L - Data Mining and Machine Learning
LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information
5 ORPAILLEUR - Knowledge representation, reasonning
Inria Nancy - Grand Est, LORIA - NLPKD - Department of Natural Language Processing & Knowledge Discovery
Abstract : Functional dependencies (FDs) provide valuable knowledge on the relations between the attributes of a data table. A functional dependency holds when the values of an attribute can be determined by another. It is shown that FDs can be expressed in terms of partitions of tuples that are in agreement w.r.t. the values taken by some subsets of attributes. To extend the use of FDs, several generalizations are proposed. In this work, we study approximate-matching dependencies that generalize FDs by relaxing the constraints on the attributes, i.e. agreement is based on a similarity relation rather than on equality. Such dependencies are attracting attention in the database field since they allow to uncrisp the basic notion of FDs, and can be applied in many different fields, e.g. data quality, data mining, behavior analysis, data cleaning or data partition... Here we show that these dependencies can be formalized in the framework of Formal Concept Analysis (FCA). Such a formalization was previously introduced for basic FDs, but needs to be adapted and extended for approximate-matching dependencies. Our new result states that, starting from the conceptual structure of a pattern structure and generalizing the notion of relation between tuples, approximate-matching dependencies can be characterized as implications in a pattern concept lattice. We finally show how to adapt basic FCA algorithms to construct a pattern concept lattice that entails these dependencies after a slight and tractable transformation of the original data.
Liste complète des métadonnées

Littérature citée [35 références]  Voir  Masquer  Télécharger
Contributeur : Amedeo Napoli <>
Soumis le : vendredi 29 décembre 2017 - 17:05:16
Dernière modification le : mercredi 16 mai 2018 - 01:18:29


Fichiers produits par l'(les) auteur(s)



Jaume Baixeries, Victor Codocedo, Mehdi Kaytoue, Amedeo Napoli. Characterizing Approximate-Matching Dependencies in Formal Concept Analysis with Pattern Structures. Discrete Applied Mathematics, Elsevier, In press, pp.1-26. 〈10.1016/j.dam.2018.03.073〉. 〈hal-01673441〉



Consultations de la notice


Téléchargements de fichiers