The most popular basis in Formal Concept Analysis is the Duquenne-Guigues basis, which ensure minimality in the number of dependencies and it is built with pseudo-intents, and some method to calculate these basis from an arbitrary set of implications have been introduced. We propose in this paper, an automated method to calculate a left-minimal direct basis from the set of all implications built between a closed set and its corresponding minimal generators. The new basis also has the minimal property demanded in the Duquenne-Guigues basis. It is minimal in the cardinal of the set of implications, and minimal in the size of the left-hand side of the implications.
Formal Concept Analysis [
Attribute implication can be managed syntactically using Armstrong’s
Axioms [
In [
We also introduce an automated method to calculate from a set of implications a left-minimal direct basis. The new method is based on the Simplification Logic for Funcional Dependency SLFD [?], a sound and complete inference system for implications. The main characteristics of SLFD is that its inference system is not built around the transitivity rule, like other well known Armstrong-like axiomatic systems for implications.
The work is organized as follows. In Section 2 we summarize preliminary
concepts and results on FCA concerning implications, basis, etc. In Section 3 we
outline the automated method that we have proposed in [
We will use the well-kwon notation used on Formal Concept Analysis (FCA) [
A relevant notion in the framework of Formal Concept Analysis is the concept
of attribute implication [
Alternatively, attribute implications allow us to capture all the information which can be deduced from a context. The set of all valid implications in a context may be syntactically managed by means of the following inference system known as Armstrong’s axioms. An implication basis of K is defined as a set L of implications of K from which any valid implication for K can be deduced by using Armstrong rules.
The goal is to obtain an implication basis with minimal size. This condition
is satisfied by the so-called Duquenne-Guigues (or stem) basis [
In the following, a summary of some interesting result of this survey are
showed. More specifically we present the definitions of some characteristics
studied in the survey that will be used to identify the kind of basis we introduce in
this paper. In the practice, it is interesting considering some properties [
Definition 1. A set of implications Γ it is said – minimal or non-redundant if Γ \ {X → Y } is not equivalent to Γ . – minimum if if it is of least cardinality, that is, | Γ |≤| Γ 0 | for all set of implications Γ 0 equivalent to Γ . – optimal if || Γ ||≤|| Γ 0 || for all set of implications Γ 0 equivalent to Γ , where the size of Γ is defined as || Γ ||=
X {X→Y ∈Γ } (| X | + | Y |)
And finally the two characteristics that constitutes the center of our basis are introduced: Definition 2. Let Γ = {X0 → Y0, . . . Xn → Yn} be a set of implications, it is said a left-minimal basis if there does not exist a Xi → Yi and a subset Xi0 ( Xi such that Γ \ {Xi → Yi} ∪ {Xi0 → Yi} is equivalent to Γ .
A set of implications Γ and is said direct if for all implication A → B the set A ∪ B is a closed set w.r.t. Γ . 3
Some methods to obtain generators of closed sets have been studied in [
We agree with these authors about the importance of the study of closed sets
and minimal generators. They constitute a source of essential information to
analyze a formal context. As we mention in the introduction, in [
In the literature, the most cited algorithm to compute Duquenne-Guigues
basis is the Ganter Algorithm [
Algorithm 1: Algorithm for computing a Duquenne-Guigues basis input : An LSI Φ output: A Duquenne-Guigues basis T := ∅; foreach hB, mg(B)i ∈ Φ do
foreach A ∈ mg(B) do T := T ∪ {A → B} repeat
S := T ; foreach A → B, C → D ∈ T such that A C and B 6⊆ C do
T := T r {C → D}; if B ∪ C 6= D then T := T ∪ {BC → D} until T = S ; S := ∅; foreach A → B ∈ T do S := S ∪ {A → B r A}; return S
In the following example, we show how to link the above algorithm with the
work presented in [
Example 1. For the input T = {ab → c, ac → bd, b → d, d → c}, Algorithm
MinGen 0 (see [
The following theorem ensures the minimality (w.r.t. the cardinality) of the Duquenne-Guigues basis.
Theorem 1. Any Duquenne-Guigues basis is a minimum basis.
In the following, we describe the algorihtm 2 to calculate a Left-Minimal Direct Basis based on Algorithm 1. The algorithm is polynomial and it is described searching a good understanding. Of course, an implementation using lectic order would improve considerably its efficiency.
First, we consider the following equivalence rules.
Definition 3 (Aggregation rules). Let A, B, C and D be sets of attributes. 1. If A ⊆ C then {A → B, C → D} ≡ {A → B, BC → D r B}. 2. If A ⊆ C ⊆ A ∪ B then {A → B, C → D} ≡ {A → BD}. Algorithm 2: Algorithm for computing a Left-Minimal Direct Basis input : An LSI Φ output: A Minimal Direct Basis T := ∅; foreach hB, mg(B)i ∈ Φ do
foreach A ∈ mg(B) do T := T ∪ {(A, A → B)} repeat
S := T ; foreach (M, A → B), (N, C → D) ∈ T such that A
T := T r {(N, C → D)}; if B ∪ C 6= D then T := T ∪ {(N, BC → D)} until T = S ; S := ∅; foreach (M, A → B) ∈ T do S := S ∪ {M → B r M }; return S C and B 6⊆ C do
We let for an extended version of this paper the proof that these equivalences rules are derived rules of equivalences presented in Theorem ??.
We propose in the Algorithm 2 the use of the two aggregation rules for reducing the number of implications and also the consequent of implications. Theorem 2. Let T = {(M1, A1 → B1), . . .} be a set of pairs with minimal generators and implications obtained from minimal generators and closed sets. The exhaustive application of the two Aggregation rules produces a left-minimal direct basis.
Example 2. Let T = {b → agh, d → a, bn → h, ab → def g, abc → djk} be
a set of implications, Algorithm MinGen 0 ([
In the first step of the Algorithm 2 with Φ we build T = {(b, b→abdefgh), (bc,bc →abcdefghkj), (bn, bn → abdef ghn), (bcn, bcn → abcdef ghkn), (d, d → ad)}.
Then, we apply the Aggregation rules foreach couple of elements in T . At the end of these comparisons, we have T = {(b, b → abdef gh), (bc, abcdef gh → abcdef ghkj), (d, d → ad)}. And from this, in the last foreach of the Algorithm 2, it renders the following left-minimal direct basis S = {b → adef gh, bc → adef ghkj, d → a}.
By the other side, Algorithm 1 return the following Duquenne-Guigues basis {b → adef gh, abcdef gh → kj, d → a} which in a minimal basis, but not a left-minimal one. 4
In this paper we present an algorithm which allows the transformation of a set of all closed sets and their corresponding minimal generators into a left-minimal direct basis. The study about the soundness, completeness, and complexity of the algorithms proposed are left to a extended paper.
The new method uses some equivalences deduced in the SLFD Logic and follows the Lectic order to traverse the list of minimal generators and implications associated and return a set of implications but with good properties.
As future work we propose to extend the Duquenne-Guigues basis definition
to consider a generalized fuzzy extension of implications. We propose the
definition introduced in [
Supported by Grants TIN2011-28084 of the Science and Innovation Ministry of Spain, and No. P09-FQM-5233 of the Junta de Andaluc´ıa.