Sets of attribute implications may have a certain degree of redundancy and the notion of basis appears as a way to characterize the implication set with less redundancy. The most widely accepted is the Duquenne-Guigues basis, strongly based on the notion of pseudo-intents. In this work we propose the minimal generators as an element to remove redundancy in the basis. The main problem is to enumerate all the minimal generators from a set of implications. We introduce a method to compute all the minimal generators which is based on the Simplification Rule for implications. The simplification paradigm allows us to remove redundancy in the implications by deleting attributes inside the implication without removing the whole implication itself. In this work, the application of the Simplification Rule to the set of implications guides the search of the minimal generators in a logic-based style, providing a deterministic approach.
A concept is a general idea that corresponds to some kind of entities and that
may be characterized by some essential features of the class. When Wille [
The main goal of Formal Concept Analysis is to identify the relationships
between sets of objects and sets of attributes from information in a binary table.
These relationships establish a Galois connection which allows us to identify the
concepts by using lattice theory. The construction of the lattice of concepts is
known to be a hard problem due to its exponential complexity. For this task,
probably the most cited method is the NEXTCLOSURE algorithm developed by
Ganter [
Apart from building the concept lattice itself, one of the key problems is to extract the set of attribute implications which hold in the concept lattice. In c 2012 by the paper authors. CLA 2012, pp. 187–198. Copying permitted only for private and academic purposes. Volume published and copyrighted by its editors. Local Proceedings in ISBN 978–84–695–5252–0,
real applications the size of the concept lattice is usually huge and is impossible
for the user to visualize it. Belohlavek and Vychodil developed [
The problem arises when the set of implications has a high degree of
redundancy: by the existence of redundant implications or redundant attributes
inside the implications. One desired goal in this area is to remove redundancy
and obtain a minimal basis. The most widely approach comes from the notion
of Duquenne-Guigues Basis [
Nevertheless, this notion of minimality and its associated redundancy may be improved. To illustrate this assertion, we present here an example appeared in [5, pp. 30 and 84] where Ganter presents a context of developing countries. In the example, 130 countries and six attributes are considered: Group of 77, Non-aligned, LLDC (Least Developed Countries), MASC (Most Seriously Affected Countries), OPEC (Organization of Petrol Exporting Countries) and ACP (African, Caribbean and Pacific Countries). Ganter builds the concept lattice from this context and provides the following Duquenne-Guigues basis: OPEC → Group 77, Non-aligned
MASC → Group 77
Non-aligned → Group of 77 Group 77, Non-aligned, MASC, OPEC → LLDC, ACP
Group 77, Non-aligned, LLDC, OPEC → MASC, ACP
Note, however, that in the last two implications, there still exist redundant attributes in the left hand side, whereas in the first and in the last implications the redundancy appears in the right hand sides. This implies that it is possible to provide an equivalent and simpler set of implications:
OPEC → Non-aligned
MASC → Group 77
Non-aligned → Group of 77 MASC, OPEC → LLDC, ACP
LLDC, OPEC → MASC Thus, we have an example in which the Duquenne-Guigues basis still can contain redundant information. In order to obtain the latter basis it is necessary to consider minimal generators instead of pseudo-intents.
Implications define a closure system, and for this reason, a closure system
can be replaced by their equivalent implications. The relationship between closed
sets and implications are the key of the attribute exploration techniques [
In [
Methods for obtaining generators of closed sets have been studied in [
We would like to provide, in a further step, an alternative definition of basis built around the notion of minimal generator, since our goal is to avoid redundancy inside the implications, instead of just minimizing the number of implications. As a preliminary step, we have to design a method to enumerate all the minimal generators and their corresponding closed sets.
This paper is structured in the following way: in Section 2 some preliminaries about formal concept analysis and the Simplification paradigm are presented. In Section 3 a method to enumerate all the minimal generators from an implication set is introduced and in subsection 3.2 the algorithm is modified to compute the non-trivial minimal generators. The paper ends with a section on conclusions and prospects for future work. 2 2.1
Intuitively, Formal Concept Analysis (FCA) provides methods to describe the relationship between a set of objects and a set of attributes. A formal context is a triple K := (G, M, I) where G is a set of objects, M is a set of attributes and I ⊆ G × M is a binary relation between G and M such that, for o ∈ G and a ∈ M , o I a means that the object o has the attribute a. From this triple two mappings can be defined. One of them ( )′ : 2G → 2M is defined for all A ⊆ G as A′ = {m ∈ M | g I m for all g ∈ A}. The other one, ( )′ : 2M → 2G is defined for all B ⊆ M as B′ = {g ∈ G | g I m for all m ∈ B}. Both mappings are denoted by the same symbol because no confusion arises. This pair of mappings is a Galois connection and both are antitone mappings (A1 ⊆ A2 implies A′2 ⊆ A1 ′ for all A1, A2 ⊆ G, and, for all B1, B2 ⊆ M , if B1 ⊆ B2 then B2′ ⊆ B1′)
The composition of the intent and the extent mappings, and vice versa, give us two closure operators ( )′′ : 2G → 2G and ( )′′ : 2M → 2M . That is, both are extensive (X ⊆ X′′), idempotent ((X′′)′′ = X′′) and isotone (if X1 ⊆ X2 then X1′′ ⊆ X2′′). In order to make this work self-contained, the notion of closed set (as a fixpoint of a closure operator) is defined below: Definition 1. A formal concept is a pair (A, B) such that A ⊆ G, B ⊆ M , A′ = B and B′ = A. Consequently, A and B are closed sets of objects and attributes, respectively called extent and intent.
It is well-known that the set of formal concepts is a complete lattice, the concept lattice associated to the context, with the following partial ordering is considered:
(A1, B1) ≤ (A2, B2) if and only if A1 ⊆ A2 (or equivalently B1 ⊇ B2) Related to the notion of closed set, the minimal generator (mingen) and implication are defined as follows: Definition 2. Let K = (G, M, I) be a formal context and A ⊆ M . The set of attributes A is said to be a minimal generator (mingen) if, for all set of attributes X ⊆ A if X′′ = A′′ then X = A.
Attribute implication allows us to capture all the information which can be deduced from a context. They are expressions A → B being A and B sets of attributes. A context satisfies the implication A → B if every object that has all the attributes from A also has all the attributes from B.
Definition 3. An (attribute) implication of a formal context K = (G, M, I) is defined as a pair (A, B), written A → B, where A, B ⊆ M . Implication A → B holds (is valid) in K if A′ ⊆ B′.
The set of all valid implications in a context satisfies the well-known Armstrong’s axioms: [Ref]
A ⊇ B A→B , [Augm]
A→B A ∪ C→B ∪ C , [Trans]
A→B, B→C
A→C
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 a implication basis with minimal size. This condition is satisfied by
the so-called Duquenne-Guigues basis [
As we have illustrated in the introduction, the definition of the DuquenneGuigues basis refers to minimality only in the size of the set of implicants, but redundant attributes use to appear in this kind of minimal basis. This situation comes from the use of pseudo-intents in the construction of the basis. To avoid redundant attributes, we propose to consider minimal generators in the left hand side of the implications. In this work we do not provide such alternative definition of minimal basis, but focus on the problem of enumerating all the minimal generators. This is the main goal of Section 3, but before we need to recall the basics of the simplification logic. 2.2
Simplification logic and closures
Armstrong’s axiom system has influenced the design of several logics for
functional dependencies [
To begin with, SLF D logic considers reflexivity as axiom scheme [Ref]
A ⊇ B A→B together with the following inference rules called fragmentation, composition and simplification respectively.
A→B ∪ C
A→B
A→B, C→D [Comp] A ∪ C→B ∪ D
A→B, C→D [Simp] A ∪ (C r B)→D
The equivalence between SLF D logic and Armstrong’s Axioms and an
efficient algorithm to compute the closure of a set of attributes were proposed
in [
Proposition 1. Let A, B, C, D sets of attributes. In SLF D logic, the following equivalences hold: 1. {A→B} ≡ {A→B r A} 2. {A→B, A→C} ≡ {A→B ∪ C} 3. A ∩ B = ∅ and A ⊆ C imply {A→B, C→D} ≡ {A→B, C r B→D r B}
It is well-known that, given a basis of a context, the closure of attribute sets defined based on Armstrong’s axioms coincides with the closure ()′′ : 2M → 2M . On the other hand, Armstrong’s axioms and the axiom system in SLF D logic are equivalent.
Definition 4. Let Γ be a set of implications and A be a set of attributes. The closure of A in SLF D logic is defined as the maximum set of attributes A+ such that Γ ⊢ A→A+.
Theorem 1. Let K = (G, M, I) a formal context and Γ a basis for K. For all A ⊆ M , the equality A+ = A′′ holds.
As we have said, in [
if and only if {∅→A} ∪ Γ ⊢ {∅→B} The closure algorithm is based on the previous theorem and the systematic application of the following equivalences which are direct consequences of the simplification equivalence (item 3 in Proposition 1).
Proposition 2. Let A, B and C be sets of attributes, then the following equivalences hold: – Eq. I: If B ⊆ A then {∅→A, B→C} ≡ {∅→A ∪ C}. – Eq. II: If C ⊆ A then {∅→A, B→C} ≡ {∅→A}.
– Eq. III: Otherwise {∅→A, B→C} ≡ {∅→A, B r A→C r A}.
Given a set of implications Γ and a set of attributes A, the execution of the SLF D closure method begins with the construction of the guide ∅→A. The three equivalences are systematically applied to Γ , which produces a growth of the guide. When none of the three equivalences can be applied, in the guide we have the closure.
Method 1 Let Γ be a set of implications and A a subset of attributes. The following method computes the closure A+ of the set A w.r.t. Γ : 1. Build the guide as follows {∅→A} 2. While there exist B→C ∈ Γ such that A ∩ B 6= ∅ or A ∩ C 6= ∅ (being {∅→A} the guide in this state of the execution), execute the corresponding equivalence: – If B ⊆ A then remove B→C from Γ and change the guide {∅→A} by {∅→A ∪ C}. – If C ⊆ A then remove B→C from Γ .
– Otherwise substitute B→C by B r A→C r A in Γ . 3. If {∅→A} is the guide (in this state) then return A.
Example 1. Let Γ = {ab→c, bc→d, de→f, ce→f } and A = de. The following table summarizes the execution of Method 1 to compute A+ = def .
Guide ∅→de
Γ ab→c bc→d de→f ce→f ∅→de ab→c bc→6 d 6 d6 e→f c6 e→f ∅→def ab→c c→6 f ∅→def ab→c
The new closure operator was proven to be faster than other closure
algorithms [
Cls(de, {ab→c, bc→d, de→f, ce→f }) = (def, {ab→c}) 3
In this section, we present how the Simplification paradigm can be considered as a powerful tool to guide the search of all minimal generator sets. In the first method we present here, we will compute mingens (the set of all minimal generators) from a set of implicant set. The algorithm works by applying the SLF D Closure algorithm to the set of implications. This application provides a new candidate to be added to mingen and a smaller implications set which guides us in the search of new sets of attributes to be added to mingens.
The input of this algorithm is a set of attributes M and a set of implications Γ over the attributes in M . The output is the set of closed sets endowed with all the mingens that generate them, i.e. {hC, mg(C)i : C is a closed set of attributes} where mg(C) = {D : D is a mingen and D+ = C}.
For example, if M = {a, b, c} and Γ = {a→b, b→a} the output must be {habc, {ac, bc}i, hab, {a, b}i, hc, {c}i, h∅, {∅}i} It can be seen as the concept lattice in which we have added labels with the mingens to each closed set.
With this idea we are going to need operators that allow us to work with this kind of sets, i.e. sets of pairs hA, Bi such that A ⊆ M is an intent and B ⊆ 2M satisfies the following conditions: 1. X ⊆ A for all X ∈ B. 2. X, Y ∈ B and X ⊆ Y imply X = Y .
This kind of sets are called labeled set of intents (LSI). Given two LSIs Φ and Ψ , we define the join of both, Φ ⊔ Ψ , as the the minimum LSI that satisfies: – If hA1, B1i ∈ Φ and A1 6= A2 for all hA2, B2i ∈ Ψ then hA1, B1i ∈ Φ ⊔ Ψ – If hA1, B1i ∈ Ψ and A1 6= A2 for all hA2, B2i ∈ Φ then hA1, B1i ∈ Φ ⊔ Ψ – If hA, B1i ∈ Ψ and hA, B2i ∈ Φ then hA, B3i ∈ Φ ⊔ Ψ being B3 the set of minimal elements of B1 ∪ B2.
We define an operator, the trivial operator, that given M and Γ returns the following LSI:
trv(M, Γ ) = {hX, {X}i : X ⊆ M with A 6⊆ X for all A→B ∈ Γ } For example, trv({a, b, c}, {a→b, b→a}) = {hc, {c}i, h∅, {∅}i}.
We will also need a way to add a pair to an LSI; it is defined as follows:
Add(hC, {D}i, Φ) = {hA ∪ C, {X ∪ D : X ∈ B}i : hA, Bi ∈ Φ} For example,
Add(hab, {a}i, {hc, {c}i, h∅, {∅}i}) = {habc, {ac}i, hab, {a}i}
Add(hc, {c}i, {hab, {a, b}i, h∅, {∅}i}) = {habc, {ac, bc}i, hc, {c}i} 3.1
MinGen Algorithm We already have all the tools needed to define the algorithm, which is introduced below, together with an illustrative example of its application.
Example 2. We want to compute
MinGen({a, b, c, d}, {a→b, c→bd, bd→ac})
Φ = trv({a, b, c, d}, {a→b, c→bd, bd→ac} = = {hb, {b}i, hd, {d}i, h∅, {∅}i}
Data: M, Γ Result: Φ begin if Γ = ∅ then Φ = trv(M, Γ ) else
Cls(a, Γ ) = (ab, {c→d, d→c})
Let Φ = trv(M, Γ ); foreach A→B ∈ Γ do
Let (A+, Γ ′) = Cls(A, Γ );
Let Φ := Φ ⊔ Add(hA+, {A}i, MinGen(M r A+, Γ ′); and call to MinGen({c, d}, {c→d, d→c}) Step 2.1. This label (2.1) points that we have passed to a lower level, i.e. we have made a recursive call to the procedure.
Φ1 = trv({c, d}, {c→d, d→c} = {h∅, {∅}i} ∅→a ∅→a ∅→ab a→b c→bd bd→ac 6 a→b c→bd bd→6 ac
c→6 bd 6 bd→c ∅→c ∅→c ∅→cd ∅→d ∅→d ∅→cd c→d d→c 6 c→d d→6 c c→d d→c c→6 d 6 d→c
Cls(c, Γ1) = (cd, ∅) and MinGen(∅, ∅) = {h∅, {∅}i}.
And so Φ1 = {h∅, {∅}i} ⊔ Add(hcd, {c}i, {h∅, {∅}i}) = {hcd, {c}i, h∅, {∅}i}
Cls(d, Γ1) = (cd, ∅) and MinGen(∅, ∅) = {h∅, {∅}i}.
And so Φ1 = {hcd, {c}i, h∅, {∅}i} ⊔ Add(hcd, {d}i, {h∅, {∅}i}) = {hcd, {c, d}i, h∅, {∅}i}
Φ = {hb, {b}i, hd, {d}i, h∅, {∅}i} ⊔ Add(hab, {a}i, {hcd, {c, d}i, h∅, {∅}i}) = {habcd, {ac, ad}i, hab, {a}i, hb, {b}i, hd, {d}i, h∅, {∅}i}
Cls(bc, Γ ) = (abcd, ∅) ∅→c ∅→c ∅→bcd ∅→abcd a→b c→bd bd→ac a→b 6 c→bd bd→a6 c a→6 b 6 b6 d→a Φ = {habcd, {ac, ad}i, hab, {a}ihb, {b}i, hd, {d}i, h∅, {∅}i} ⊔ Add(habcd, {c}i, {h∅, {∅}i}) = {habcd, {c, ad}i, hab, {a}i, hb, {b}i, hd, {d}i, h∅, {∅}i} Note that {habcd, {ac, ad}i} ⊔ {habcd, {c}i} = {habcd, {c, ad}i}.
Cls(bd, Γ ) = (abcd, ∅)
{habcd, {c, ad, bd}i, hab, {a}ihb, {b}i, hd, {d}i, h∅, {∅}i} 3.2
Non-trivial minimal generators.
Notice that the first method we have just introduced computes all minimal generators, including trivial mingens with non-relevant information.
In this subsection, we slightly modify the previous algoritm to produce only the relevant information (not trivial mingens), by considering that trv(M, Γ ) returns always only {h∅, {∅}i}. This new algorithm is called L MinGen0. Example 3. We want L to compute
MinGen0({a, b, c, d, e, f }, {a→b, bc→d, de→f, ace→f })
The full execution of the method MinGen0 is depicted in Figure 1. In Figure 2 we show the lattice of closed sets built with the non-trivial mingens provided by MinGen0. Φ1 = {h∅, {∅}i} ⊔ Add(hcd, {c}i, {hef, {e}i, h∅, {∅}i})
= {hcdef, {ce}i, hcd, {c}i, h∅, {∅}i} Step 2.3. Considering de→f ∈ Γ ′, Cls(de, Γ ) = (def, ∅). Moreover, MinGen0({c}, ∅) = {h∅, {∅}i} Φ1 = {hcdef, {ce}i, hcd, {c}i, h∅, {∅}i} ⊔ Add(hdef, {de}i, {h∅, {∅}i})
= {hcdef, {ce}i, hdef, {de}i, hcd, {c}i, h∅, {∅}i} Step 2.4. Considering ce→f ∈ Γ ′, compute Cls(ce, Γ ) = (cdef, ∅). Moreover MinGen0(∅, ∅) = {h∅, {∅}i} Φ1 = {hcdef, {ce}i, hdef, {de}i, hcd, {c}i, h∅, {∅}i} ⊔ Add(hcdef, {ce}i, {h∅, {∅}i}) = {hcdef, {ce}i, hdef, {de}i, hcd, {c}i, h∅, {∅}i}
Step 3. Considering bc→d ∈ Γ , Cls(bc, Γ ) = (bcd, {e→f, ae→f }). Now we compute MinGen0({a, e, f }, {e→f, ae→f }).
Step 3.1. Φ2 = {h∅, {∅}i} Step 3.2. Considering e→f ∈ Γ ′, compute Cls(e, Γ ) = (ef, ∅) and MinGen0({a}, ∅) = {h∅, {∅}i}
Φ2 = {h∅, {∅}i} ⊔ Add(hef, {e}i, {h∅, {∅}i}) = {hef, {e}i, h∅, {∅}i} Step 3.3. Considering ae→f ∈ Γ ′, Cls(ae, Γ ) = (aef, ∅). Moreover MinGen0(∅, ∅) = {h∅, {∅}i} Φ2 = {hef, {e}i, h∅, {∅}i} ⊔ Add(haef, {ae}i, {h∅, {∅}i})
= {haef, {ae}i, hef, {e}i, h∅, {∅}i} Returning to the high level, Φ = {habcdef, {ace}i, habdef, {ade}i, habcd, {ac}i, hab, {a}i, h∅, {∅}i} ⊔Add(hbcd, {bc}i, {haef, {ae}i, hef, {e}i, h∅, {∅}i}) = {habcdef, {ace}i, habdef, {ade}i, habcd, {ac}i, hab, {a}i, h∅, {∅}i} ⊔{habcdef, {abce}i, hbcdef, {bce}i, hbcd, {bc}i} ={habcdef, {ace}i, habdef, {ade}i, hbcdef, {bce}i, habcd, {ac}i,
hbcd, {bc}i, hab, {a}i, h∅, {∅}i}
Φ = {habcdef, {ace}i, habdef, {ade}i, hbcdef, {bce}i, habcd, {ac}i, hbcd, {bc}i, hdef, {de}i, hab, {a}i, h∅, {∅}i}
Φ = {habcdef, {ace}i, habdef, {ade}i, hbcdef, {bce}i, habcd, {ac}i, hbcd, {bc}i, hdef, {de}i, hab, {a}i, h∅, {∅}i} 4
In this work we have proposed the minimal generators as a basic notion to remove redundancy in sets of implications. To achieve this goal, the first step is to design a method to compute all minimal generators corresponding to a set of implications. The simplification paradigm is the key to design the MinGen and MinGen0 algorithms. The application of SLF D closure algorithm guides the search of minimal generators.
As future work we will present a thorough study about the soundness, completeness, and complexity of the mingens algorithms, which have not been included here due to space limitations; moreover, a definition of basis center within the notion of minimal generators will be studied, together with a method to compute such a basis.