Characterizing Approximate-Matching Dependencies in Formal Concept Analysis with Pattern Structures - Archive ouverte HAL Access content directly
Journal Articles Discrete Applied Mathematics Year : 2018

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

(1) , (2) , (3, 4) , (5)
1
2
3
4
5
Victor Codocedo
Mehdi Kaytoue
Amedeo Napoli

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.
Fichier principal
Vignette du fichier
jb+vc+mk+an-dam171229.pdf (604.39 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01673441 , version 1 (29-12-2017)

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook Twitter LinkedIn More