From an implicational system to its corresponding D-basis

From an implicational system to its corresponding D-basis Estrella Rodr´ıguez-Lorenzo1, Kira Adaricheva2, Pablo Cordero1, Manuel Enciso1, and Angel Mora1 1University of M´alaga, Andaluc´ıa Tech, Spain, e-mail: {estrellarodlor,amora}@ctima.uma.es, p[email protected], [email protected] 2Nazarbayev University, Kazakhstan e-mail: [email protected] Abstract. Closure system is a fundamental concept appearing in several areas such as databases, formal concept analysis, artificial intelligence, etc. It is well-known that there exists a connection between a closure operator on a set and the lattice of its closed sets. Furthermore, the closure system can be replaced by a set of implications but this set has usually a lot of redundancy inducing non desired properties. In the literature, there is a common interest in the search of the minimality of a set of implications because of the importance of bases. The well-known Duquenne-Guigues basis satisfies this minimality condition. However, several authors emphasize the relevance of the optimality in order to reduce the size of implications in the basis. In addition to this, some bases have been defined to improve the computation of closures relying on the directness property. The efficiency of computation with the direct basis is achieved due to the fact that the closure is computed in one traversal. In this work, we focus on the D-basis, which is ordered-direct. An open problem is to obtain it from an arbitrary implicational system, so it is our aim in this paper. We introduce a method to compute the D-basis by means of minimal generators calculated using the Simplification Logic for implications. 1 Introduction Discovering knowledge and information retrieval are currently active issues where Formal Concept Analysis (FCA) provides tools and methods for data analysis. The notions around the concept lattice may be considered as the main attractions in Formal Concept Analysis and they are strongly connected to the notion of closure. Closure system is a fundamental concept appearing in several areas such as database theory, formal concept analysis, artificial intelligence, etc. It is wellknown that there exists a connection between a closure operator on a set and the lattice of its closed sets. Furthermore, the closure system can be presented, dually, as a set of attribute implications, namely an implicational system but this set has usually a lot of redundancy inducing non-desired properties. We can not fail to mention the relevance of the role of the implication notion in different areas. It was the main actor of the normalization theory in database area; it has an outstanding character in Formal Concept Analysis and it was prominently used in Frequent Set Mining and Learning Spaces, see the survey of M. Wild [10]. The latter is devoted to mathematical theory of implications and the different faces of the concept of an implication. Implications linked data represented in several forms going from the relationship between itemsets in transactions (Frequent Set Mining) to the boolean functions (Horn Theory). Nonetheless, as V. Duquenne says in [6] “it is surprising if not hard to acknowledge that we did not learn much more on their intimacy in the meantime, despite many interesting papers using or revisiting them”. We believe there is a long way to go, and a deeper theory on properties of implications with automated and efficient methods to manipulate them can be developed. In this paper, we are focused in the Formal Concept Analysis area and the fundamental notions are assumed (see [7]). The task of information retrieval carried out by the tools in FCA conduits to infer concepts from the data set, i.e. to deduce (in an automated way) a set of objects that may be precisely characterized by a set of attributes. Such concepts inherit an order relation induced by attribute set inclusion, providing a lattice structure of the concept set. Here implications are retrieved from a binary table (formal context) representing the relationship between a set of objects and a set of attributes. Implications represent an alternative way for the underlying information contained in the formal context. Many applications must massively compute closures of sets of attributes and any improvement of execution time is relevant. In [9] the author establishes the necessity of obtaining succinct representation of closure operators to achieve an efficient computational usage. In this direction, properties associated to implications are studied to render equivalent sets fulfilling desired properties, directness and optimality. An important matter in FCA is to transform implicational systems in canonical forms for special proposals in order to provide an efficient further management. Hence, some alternative definitions have been established: DuquenneGuigues basis, direct optimal basis, D-basis, etc. In this work we focus on the last one [1], because it combines, in a balanced way, a brief representation (it has a small number of elements) and a efficient computation of closures (it is computed in just one traversal). To this end, D-basis proposes an order in which implications will be attended. The major issue is that the execution of the D-basis in one iteration is more efficient that the execution of a shorter, but un-ordered one, for instance the canonical basis of Duquenne and Guigues. K. Adaricheva et.al prove in [1] that one can extract the D-basis from any direct unit basis Σin time polynomial of size of Σ, and it takes only linear time of the number of implications of the D-basis to put it into a proper order. In [5] we have proposed a method to calculate all the minimal generators from a set of implications as a way to remove redundancy in the basis. The method to compute all the minimal generators is based on the Simplification Logic for implications [8]. Using this logic we are able to remove redundancy in the implications [4] and following the same style of application of the Simplification Rule to the set of implications we can obtain all the minimal generators. Currently the retrieval of the D-basis from an arbitrary implicational system is an open problem, so it becomes our aim in this paper. We introduce a method to compute the D-basis by means of minimal generators calculated using the Simplification Logic for implications. The relationship among minimal generators, covers, minimal covers and D-basis is presented and an algorithm to calculate D-basis from an arbitrary set of implications is proposed. Section 2 presents the main notions necessary to the understanding of the new method: closure operators, the D-basis, Simplification Logic and the method to calculate minimal generators. In Section 3, the relationships between covers and generators are presented. In Section 4, the new method to obtain the Dbasis from a set of implications is shown, and some conclusions and extensions are proposed in Section 5. 2 Background 2.1 Closure systems Given a non-empty set Mand the set12Mof all its subsets, a closure operator is a map φ: 2M→2Mthat satisfies the following, for all X, Y ∈2M: (1) increasing: X⊆φ(X); (2) isotone: X⊆Yimplies φ(X)⊆φ(Y); (3) idempotent: φ(φ(X)) = φ(X). We will refer to the pair hM, φiof a set Mand a closure operator on it as a closure system. In the next two subsections we will follow the introduction of the implicational system based on the minimal proper covers2given in [1], which was named there the D-basis. We will call closure system reduced, if φ({x}) = φ({y})→x=y, for any x, y ∈M3. If the closure system hM, φiis not reduced, one can modify it to produce an equivalent one that is reduced, see [1] for more details. We will now define a closure operator φ∗, which is associated with a given operator φ. Definition 1. Let hM, φibe a closure system. Define φ∗as a self-map on 2M such that φ∗(X) = Sx∈Xφ(x), X ⊆2M. It is straightforward to verify that 1In the FCA framework, that set M can be thought a set of attributes of a context. 2Although in [1] it was introduced as minimal cover, here we name it minimal proper cover because in this paper we generalize the notion of cover in Section 3. 3To clarify the notation φ({x}) will be represented as φ(x) if no risk of confusion. Lemma 1. φ∗is a closure operator on M. Given a closure system hM, φi, we introduce several important concepts. Definition 2 ([1]). For x∈Mwe call a subset X⊆Ma proper cover for xif x∈φ(X)\φ∗(X). If Xis a proper cover for x, it will be denoted as x∼pX. 2.2 The D-basis In this subsection, we briefly summarize the introduction of the D-basis in [1]. Its definition is strongly based on the notion of a minimal proper cover: Definition 3. A proper cover Yfor xis called minimal, if, for any other proper cover Zfor x,Z⊆φ∗(Y)implies Y⊆Z. The existence of several proper covers for the same element induces the need to introduce the notion of minimality. Lemma 2. If x∼pX, then there exists Ysuch that x∼pY,Y⊆φ∗(X)and Yis a minimal proper cover for x. In other words, every proper cover can be reduced to a minimal proper cover under the subset relation added with the φ∗ operator. These ideas bring to the following definition of the implicational system defining the reduced closure system by means of the minimal proper covers. Definition 4. Given a reduced closure system hM, φi, define the D-basis ΣD as a union of two subsets of implications: 1. {y→x:x∈φ(y)\y, y ∈M}(such implications are called binary); 2. {X→x:Xis a minimal proper cover for x}. Note that the D-basis belongs to the family of the unit bases, i.e. implicational sets where each implication A→bhas a singleton b∈Mas a consequent. Lemma 3. ΣDgenerates hM, φi. 2.3 Ordered direct set of implications Here we recall the notion of the ordered direct basis introduced in [1], which is designed for a quick computation of the closures based on some fixed order of implications. First we recall the definition of the ordered iteration of implications. Definition 5. Suppose the set of implications Σis equipped with some linear order, or equivalently, the implications are indexed as Σ={s1, s2, . . . , sn}. Define a mapping ρΣ: 2M→2Massociated with this ordering as follows. For any X⊆M, let X0=X. If Xkis computed and implication sk+1 is A→B, then Xk+1 =Xk∪B, if A⊆Xk, Xk,otherwise. Finally, ρΣ(X) = Xn. We will call ρΣan ordered iteration of Σ. The concept of the ordered iteration is central for the definition of the ordered direct basis. For any given set of implications Σon set M, by φΣwe understand the closure operator on Mdefined by Σ. Equivalently, the fixed points of φΣ are exactly subsets X⊆Mwhich are stable for all implications A→Bin Σ: if A⊆X, then B⊆X. Definition 6. The set of implications with some linear ordering on it, hΣ, <i, is called an ordered direct basis, if, with respect to this ordering, φΣ(X) = ρΣ(X) for all X⊆S. We note that any direct basis is ordered direct. By direct basis we understand any set of implications that allows to produce the closure of subsets of the base set while attending each implication only once. More precisely, if Σis some set of implications defining the closure system hM, φi, then let πΣ(X) = X∪S{B:A⊆Xand (A→B)∈Σ}. In order to obtain φ(X), for any X⊆M, one would normally need to repeat several iterations of πΣ:φ(X) = πΣ(X)∪π2 Σ(X)∪π3 Σ(X). . . . The bases for which one can obtain the closure of any set Xperforming only one iteration of πΣ, i.e., φ(X) = πΣ(X), are called direct. The various direct bases appearing in the literature were surveyed in K. Bertet and B. Monjardet [3]. Important result of their analysis is that in the family of all possible (unit) direct bases for the same closure system, there exists a ⊆-smallest direct basis Σcd, which was called as canonical unit direct basis. The following result from [1] summarizes the relation between the D-basis ΣDand Σcd for a given closure system. Theorem 1. ΣD⊆Σcd. 2.4 Minimal Generators via Simplification Logic In this subsection we summarize how the inference system of Simplification Logic SLFD [4, 8] (equivalent to Armstrong’s axioms) is used to enumerate all minimal generators. SLFD is guided by the idea of simplifying the set of implications by efficiently removing some redundant attributes. SLFD logic considers reflexivity as axiom scheme [Ref] A⊇B A→B and the following inference rules called fragmentation, composition and simplification respectively. [Frag] A→B∪C A→B[Comp] A→B, C →D A∪C→B∪D[Simp] A→B, C →D A∪(CrB)→D The important matter is that these rules can be considered as equivalence rules which have been used as the core in automated methods for removing redundancies, obtaining minimal keys, or computing closures. In particular, the last method indicated is based on the following results (see [8] for details, proofs and examples): Theorem 2 ([8]). Let A, B ⊆Mand Σbe a set of implications. We have Σ`A→Bif and only if {∅ → A} ∪ Σ`∅→B. In order to compute closures, since φ(A) is the biggest subset Bsuch that Σ` A→B, the formula ∅ → Ais used as a seed which guides the reasoning to render the closure φ(A) just by applying the following equivalences where the [Simp] inference rule plays a main role. Proposition 1. Let A, B and Cbe subsets of M, then the following equivalences hold: – Eq. I: If B⊆Athen {∅ → A, B →C} ≡ {∅ → A∪C}. – Eq. II: If C⊆Athen {∅ → A, B →C} ≡ {∅ → A}. – Eq. III: Otherwise {∅ → A, B →C} ≡ {∅ → A, B rA→CrA}. Based on the above proposition and Theorem 2, in [5] the method Cls is introduced. This method receives as input set A⊆Mand a set of implications Σand renders the pair (φ(A), Σ0) where Σ0is the set of implications simplified with respect to ∅ → φ(A) (i.e. Σcontracted to 2Mrφ(A)). Notation: From now on, in order to simplify the examples, elements of Mare denoted by numbers from 0 to 9 or lowercase letters and we omit brackets and commas in subsets of M. Example 1. Let Σbe {ab →c, ac →df, bcd →ef, f →c}. Then, Cls(af, Σ) = (acdf, {b→e}) where φ(af) = acdf and Σ0={b→e}has important information that will be used in the computation of minimal generators. For X, Y ⊆Msatisfying that X=φ(Y), it is usual to say that Yis a generator of the closed set X. Notice that any subset of Xcontaining Yis also a generator of X. When the base set Mof a closure system is finite, the set of generators of a closed set can be characterized by its minimal ones. Definition 7 (Minimal Generator). Let hM, φibe a closure system. X⊆M is said to be a minimal generator if, for all proper subsets Y⊂X, one has φ(Y)⊂φ(X). In [5], a method to compute all minimal generators is presented. This method named MinGen is based on above mentioned closure algorithm Cls and it takes the advantages of the additional information that it provides. That is, Cls is used not only to compute closed sets from generators but also a smaller implicational set which guides us in the search of new subsets to be considered as minimal generators. The input of MinGen is a subset of Mand a set of implications Σ and the output is the set of closed sets endowed with all the minimal generators that generate them, i.e. {hC, mg(C)i:Cis a closed set}where mg(C) is the set of minimal generators Dsatisfying φ(D) = C. It can be seen as the lattice of the closure system in which we have added labels with the minimal generators to each closed set. Example 2. Let M={a, b, c, d}and Σ={a→b, c →bd, bd →ac}. Then the MinGen algorithm returns the following set: MinGen(M, Σ) = {habcd, {c, ad, bd}i,hab, {a}i,hb, {b}i,hd, {d}i,h∅,{∅}i} Observe that there is trivial information (e.g. hb, {b}i) included in the output of this algorithm. In [5], a version of MinGen, named MinGen0, is also presented. The difference between this algorithm and the previous one is that here only non-trivial generators are calculated. For the same input, MinGen0(M, Σ) = {habcd, {c, ad, bd}i,hab, {a}i,h∅,{∅}i} 3 Covers and Generators: Relationships The definition of a D-basis is strongly based on the notion of a proper minimal cover, and the latter is connected with the notion of a minimal generator. In this paper we are going to work with covers instead of proper covers because our idea is to manage, in a uniform way, the binary implications and non-binary ones. Throughout this section we will assume that Mis the base set of a closure system defined either by closure operator φ, or by means of a set of implications Σand its related operator φΣ. The following definition introduces a notion that extends the concept of a proper cover. Definition 8 (Cover). Given X⊆Mand x∈M, we say Xis a cover of x, denoted x∼X, if x∈φ(X)\X. The following proposition, whose proof is straightforward from definitions, illustrates the relationship among proper covers, covers and minimal generators. Proposition 2. Let Σbe a set of implications. For each set C⊆Mclosed with respect to φΣand each X C, 1. Xis a generator of Cif and only if Xis a cover of any x∈CrX. 2. If Xis a proper cover of x∈Mthen Xis also a cover of x. Observe that the converse of the second item is not true, e.g. ad is a cover of b(b∼ad) in Example 2 but it is not a proper cover. As we have remarked in Section 2, the above definition of a cover does not coincide with the one introduced in [1]. Corollary 1. Let Σbe a set of implications. For each set C⊆Mclosed with respect to φΣand each X C, if Xis a minimal generator of Cthen Xis a cover of any x∈CrX. The following example illustrates these relationships and gives a counterexample to the converse statement in the previous corollary. Example 3. Let M={a, b, c, d, e}and Σ={a→d, bce →ad, bde →ac, ade → bc, cd →abe, abd →ce}. In Table 1, the covers of each element of Mand the nontrivial minimal generators of each φΣ-closed set are shown. Moreover, underlined covers are not proper covers whereas the others are. Attribute Covers a cd, bcd, bce, bde, cde, bcde b ac, ae, cd, acd, ace, ade, cde, acde c ab, ae, abd, abe, ade, bde, abde d a, ab, ac, ae, abc, abe, ace, bce, abce e ab, ac, cd, abc, abd, acd, bcd, abcd Closed Sets Minimal Generators abcde ab, ac, ae, bce, bde, cd ad a Table 1. Covers, Proper Covers and Minimal Generators. Observe that, by Proposition 2, Xis a cover of an element xif and only if there exist a closed set Cand a minimal generator Yof Csuch that Y⊆Xand x∈CrX. For example, cd is a minimal generator of abcde and cd ⊆cde, thus, cde is a cover of abut not a minimal generator. The closure operator φ∗allows us to introduce the notion of a minimal cover. It will be used later to avoid redundancies in the implications of the basis when we look for an optimal basis. Definition 9 (Minimal Cover). Let Σbe a set of implications. Given X⊆M and x∈M,Xis a minimal cover of xif Xis a cover and satisfies one of the following conditions: 1. Xis a singleton, i.e., |X|= 1. 2. for every cover Yof x,Y⊆φ∗(X)implies X⊆Y. From this definition we directly obtain the following proposition that relates minimal generators and minimal covers. Proposition 3. Let Σbe a set of implications, X⊆Mand x∈M. If Xis a minimal cover of x∈φ(X)\X, then X is a minimal generator of φ(X). The following example illustrates the definition of minimal covers and shows that the converse statement to the above proposition is not true. Example 4. Given the base set and the set of implications of Example 3, Table 2 shows the minimal covers of each element. Element Minimal Covers a cd, bce, bde b ae, cd c ab, ae, bde d a, bce e ab, cd Table 2. Minimal Covers. Although ae is a minimal generator of abcde, it is not a minimal cover for all x∈φ({a, b, c, d, e})\ {a, e}={b, c, d}but only for band c. As the previous examples show, a minimal cover is always a minimal generator, but not conversely. Thus, if we compute all minimal generators for some x∈M, we have, at the same time, all minimal covers for x, and the latter are exactly what we need for the computation of the D-basis. 4D-basis by means of Minimal Generators We remark that it is an open problem to design an algorithm rendering the D-basis from an arbitrary implicational system. In this section, we are going to introduce such an algorithm based on the strong connection between minimal covers and minimal generators. This is shown in Algorithm 1. To begin with, we define the Function MinimalCovers to make the algorithm easier to understand. The input of the Function MinimalCovers is a set of covers of a given x∈M and it returns a subset with all its minimal covers. Function MinimalCovers(L) input : A set of covers L output: The set of minimal covers begin foreach g∈Ldo foreach h∈L\gdo if h⊆gthen remove gfrom L else if |g|6= 1 and h⊆[ x∈g φ(x)then remove gfrom L return L Notice that although the condition h⊆gimplies h⊆[ x∈g φ(x) and both of them lead to the same action, it is more efficient to split them off because the cost of the first one is lower. Thus, we previously check the first one and, if it is not fulfilled, then the other one is tested. As we have mentioned before, our goal is to obtain the D-basis from an arbitrary implicational system. In the first stage, the algorithm computes all minimal generators by means of the MinGen0method proposed in [5]. Then, in a second stage, it associates each minimal generator with all elements for which it is a cover. In this stage, we have calculated a subset of covers containing all minimal covers of a given attribute a. Finally, the algorithm removes those intermediate covers which are not minimal covers, obtaining the D-basis. This sequence of tasks is illustrated in Figure 1. As Figure 1 depicts, the transition from stage 1 to stage 2 needs a way to associate the minimal generators with some of the elements in its closed set.