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.
Complete list of metadatas

Cited literature [33 references]  Display  Hide  Download

https://hal.inria.fr/hal-01673441
Contributor : Amedeo Napoli <>
Submitted on : Friday, December 29, 2017 - 5:05:16 PM
Last modification on : Tuesday, December 18, 2018 - 4:38:02 PM

File

jb+vc+mk+an-dam171229.pdf
Files produced by the author(s)

Identifiers

Citation

Jaume Baixeries, Victor Codocedo, Mehdi Kaytoue, Amedeo Napoli. Characterizing Approximate-Matching Dependencies in Formal Concept Analysis with Pattern Structures. Discrete Applied Mathematics, Elsevier, 2018, 249, pp.18-27. ⟨10.1016/j.dam.2018.03.073⟩. ⟨hal-01673441⟩

Share

Metrics

Record views

479

Files downloads

169