L-Bonds vs extents of direct product of two L-fuzzy contexts

Abstract

We focus on the direct product of two L-fuzzy contexts, which are defined with the help of a binary operation on a lattice of truth-values L. This operation, essentially a disjunction, is defined as k ⋉ l = ¬k → l, for k, l ∈ L where negation is interpreted as ¬l = l → 0. We provide some results which extend previous work by Kr¨otzsch, Hitzler and Zhang.

Introduction

Formal concept analysis (FCA) introduced by Ganter and Wille [ 9 ] has become an extremely useful theoretical and practical tool for formally describing structural and hierarchical properties of data with “object-attribute” character. Regarding applications, we can find papers ranging from ontology merging [ 20 ], to applications to the Semantic Web by using the notion of concept similarity [ 7 ], and from processing of medical records in the clinical domain [ 11 ] to the development of recommender systems [ 6 ].

Soon after the introduction of “classical” formal concept analysis, several approaches towards its generalization were introduced and, nowadays, there are recent works which extend the theory by using ideas from fuzzy set theory, or fuzzy logic reasoning, or from rough set theory, or some integrated approaches such as fuzzy and rough, or rough and domain theory [ 1, 15–18, 21, 22 ].

In this paper, we are concerned with extensions of Bˇelohl´avek’s approach. In [ 2, 4 ] he provided an L-fuzzy extension of the main notions of FCA, such as context and concept, by extending its underlying interpretation on classical logic to the more general framework of L-fuzzy logic [ 10 ].

In this work, we aim at formally describing some structural properties of intercontextual relationships [ 8 ] of L-fuzzy formal contexts. The categorical treatment of morphisms as fundamental structural properties has been advocated by [ 14 ] as a means for the modelling of data translation, communication, and distributed computing, among other applications. Research on (extensions of) the theory of Chu spaces studies morphisms among contexts in order to obtain categories with certain specific properties. Previous work in this line has been developed by the authors in [ 12 ] by using category theory following the results in [ 19 ].

The main result here is the extension of the relationship between bonds and extents of direct products of contexts to the realm of L-fuzzy FCA. 2

Preliminary definitions

In order to make this contribution as self-contained as possible, we proceed now with the preliminary definitions of complete residuated lattice, L-fuzzy context, L-fuzzy concept. 2.1

L-fuzzy concept lattice Definition 1. An algebra hL, ∧, ∨, ⊗, →, 0, 1i is said to be a complete residuated lattice if 1. hL, ∧, ∨, 0, 1i is a complete bounded lattice with the least element 0 and the greatest element 1, 2. hL, ⊗, 1i is a commutative monoid, 3. ⊗ and → are adjoint, i.e. a⊗b ≤ c if and only if a ≤ b → c, for all a, b, c ∈ L, where ≤ is the ordering in the lattice generated from ∧ and ∨.

Now, the natural extension of the notion of context is given below. Definition 2. Let L be a complete residuated lattice, an L-fuzzy context is a triple hB, A, ri consisting of a set of objects B, a set of attributes A and an Lfuzzy binary relation r, i.e. a mapping r : B × A → L, which can be alternatively understood as an L-fuzzy subset of B × A.

We now introduce the L-fuzzy extension provided by Bˇelohl´avek [ 2, 3 ], where we will use the notation Y X to refer to the set of mappings from X to Y . Definition 3. Given an L-fuzzy context hB, A, ri, a pair of mappings ↑ : LB → LA and ↓ : LA → LB can be defined for every f ∈ LB and g ∈ LA as follows: ↑ f (a) = ^ (f (o) → r(o, a)) o∈B ↓ g(o) = ^ ¡g(a) → r(o, a)¢ a∈A (1) Lemma 1. Let L be a complete residuated lattice, let r ∈ LB×A be an L-fuzzy relation between B and A. Then the pair of operators ↑ and ↓ form a Galois connection between hLB ; ⊆i and hLA; ⊆i, that is, ↑ : LB → LA and ↓ : LA → LB are antitonic and, furthermore, for all f ∈ LB and g ∈ LA we have f ⊆ ↓↑ f and g ⊆ ↑↓ g.

Definition 4. Consider an L-fuzzy context C = hB, A, ri. An L-fuzzy set of objects f ∈ LB (resp. an L-fuzzy set of attributes g ∈ LA) is said to be closed in C iff f =↓↑ f (resp. g =↑↓ g). Lemma 2. Under the conditions of Lemma 1, the following equalities hold for arbitrary f ∈ LB and g ∈ LA, ↑ f =↑↓↑ f and ↓ g =↓↑↓ g, that is, both ↓↑ f and ↑↓ g are closed in C.

Definition 5. An L-fuzzy concept is a pair hf, gi such that ↑ f = g, ↓ g = f . The first component f is said to be the extent of the concept, whereas the second component g is the intent of the concept.

The set of all L-fuzzy concepts associated to a fuzzy context (B, A, r) will be denoted as L-F CL(B, A, r).

An ordering between L-fuzzy concepts is defined as follows: hf1, g1i ≤ hf2, g2i if and only if f1 ⊆ f2 if and only if g1 ⊇ g2.

Proposition 1. The poset (L-F CL(B, A, r), ≤) is a complete lattice where ^ hfj , gj i = D ^ fj , ↑ ¡ ^ fj )E j∈J j∈J j∈J and _ hfj , gj i j∈J = D ↓ ¡ ^ gj ), ^ gj E j∈J j∈J 3

Other operations on an L-context The corresponding notions of negation, disjunction and complement on an Lcontext are introduced below.

Definition 6. Let us consider a unary operator negation and a binary disjunction operator on the underlying structure of truth values L as follows: 1. Negation ¬ : L → L is defined by ¬(l) = ¬l = l → 0 2. Disjunction ⋉ : L × L → L is defined by l1 ⋉ l2 = ¬l1 → l2

Some of the properties of negation appear in the following lemma. Lemma 3 (Bˇelohl´avek [ 5 ]). For any a, b, c ∈ L the following holds. 1. a ≤ ¬b ⇐⇒ a ⊗ b = 0 2. a ⊗ ¬a = 0 3. a ≤ ¬¬a 4. ¬0 = 1 5. ¬a = ¬¬¬a 6. a → b ≤ ¬b → ¬a 7. a ≤ b =⇒ ¬b ≤ ¬a 8. ¬(a ∨ b) = ¬a ∧ ¬b

From Property 6 above and the definition of disjunction, we can see that disjunction needs not be, in general, commutative. However, this property will be very important for the definition and properties of direct product of two L-contexts. Notice that commutativity will hold if the law of double negation (¬¬a = a) holds. The following result states some properties of residuated lattices satisfying double negation. Proposition 2 (Bˇelohl´avek [ 5 ]). If a residuated lattice satisfies the law of double negation then it also satisfies the following conditions: 1. l → k = ¬(k ⊗ ¬l) 2. ¬(Vi∈I li) = Wi∈I ¬li 3. l → k = ¬k → ¬l

It is convenient here to recall that adding conditions of our underlying residuated lattice may change the class of structures we are working with. In particular, a residuated lattice satisfying the double negation law and divisibility (that is, x ≤ y implies the existence of z such that x = y ⊗ z), we are working with an MV-algebra. If divisibility is replaced by the fact that the product ⊗ coincides with the infimum of the lattice, then we are have just a Boolean algebra.

We finish this section with a specific notion of complement of a given L-fuzzy formal context.

Definition 7. The complement of an L-fuzzy formal context is a formal context with the binary relation ¬r defined by ¬r(o, a) = r(o, a) → 0 for all o ∈ B and a ∈ A. The uparrow and downarrow mappings on the complement are denoted by ↑¬ and ↓¬.

Lemma 4. Let C = hB, A, ri be an L-fuzzy formal context. For all objects o, b ∈ B the inequality ↓↑ (χo)(b) ≤↓¬↑¬ (χb)(o) holds. If, moreover, the law of double negation holds we have the equality ↓↑ (χo)(b) =↓¬↑¬ (χb)(o).

Proof. In the following, we use the common notation χe to denote the characteristic function of an element e in a set: ↓↑ (χo)(b) = ^ (↑ (χo)(a) → r(b, a))

a∈A = ^ ( ^ (χo(c) → r(c, a)) → r(b, a))

a∈A c∈B = ^ (( ^

a∈A c∈B,c6=o = ^ (( ^ a∈A c∈B,c6=o (χo(c) → r(c, a)) ∧ (χo(o) → r(o, a))) → r(b, a)) (0 → r(c, a)) ∧ (1 → r(o, a))) → r(b, a)) = ^ ((1 ∧ (1 → r(o, a))) → r(b, a))

a∈A = ^ ((1 → r(o, a)) → r(b, a))

a∈A = ^ (r(o, a) → r(b, a))

a∈A =∗ ^ (¬r(b, a) → ¬r(o, a)) = · · · =↓¬↑¬ (χb)(o)

a∈A Equality (∗) follows from the law of double negation, otherwise we can only obtain the inequality ↓↑ (χo)(b) ≤↓¬↑¬ (χb)(o). ⊓⊔

L-Multifunctions and L-fuzzy relations The definition of L-bonds is based on a suitable extension of the theory of multifunctions (also called, many-valued functions, or correspondences) whose notation and terminology is introduced below.

Definition 8. An L-multifunction from X to Y is a mapping ϕ : X → LY .

The transposed of an L-multifunction ϕ : X → LY is an L-multifunction tϕ : Y → X L defined by tϕ(y)(x) = ϕ(x)(y).

The L-multifunction ϕ : X → LY can be extended to a mapping ϕ∗ : LX → LY by ϕ∗(f )(y) = Wx∈X (f (x) ⊗ ϕ(x)(y)), for f ∈ LX .

The set L-Mfn(X, Y ) of all the L-multifunctions from X to Y can be endowed with a poset structure by defining the ordering ϕ1 ≤ ϕ2 as ϕ1(x)(y) ≤ ϕ2(x)(y) for all x ∈ X and y ∈ Y .

The usual definition of curry and uncurry operations can be adapted to the framework of L-multifunctions as follows: Definition 9. Let us define for arbitrary L-multifunction ϕ ∈ L-Mfn(X, Y ) an L-fuzzy relation ϕr ∈ LX×Y defined by ϕr(x, y) = ϕ(x)(y) for all (x, y) ∈ X × Y . For arbitrary L-fuzzy relation r ∈ LX×Y lets define an L-multifunction from rmfn : X → LY defined by rmfn(x)(y) = r(x, y).

Finally, the notion of L-bond is given in the following definition: Definition 10. An L-bond between two formal contexts C1 = hB1, A1, r1i and C2 = hB2, A2, r2i is a multifunction b : B1 → LA2 satisfying the condition that for all o1 ∈ B1 and a2 ∈ A2 both b(o1) and tb(a2) are closed L-fuzzy sets of, respectively, attributes in C2 and objects in C1. The set of all bonds from C1 to C2 is denoted as L-Bonds(C1, C2).

Lemma 5. Let hBi, Ai, rii be two L-fuzzy formal contexts for i ∈ {1, 2}, where L satisfies the double negation law. For all L-bonds β ∈ L-Bonds(C1, C2) and for all objects o1 ∈ B1 the equation β(o1) = β∗(↓¬1 ↑¬1 (χo1 )) holds. Proof. We will prove the two inequalities separately.

β(o1)(a2) =

_ (β(b1)(a2) ⊗ χo1 (b1)) b1∈B1 ≤

_ (β(b1)(a2)⊗ ↓¬1 ↑¬1 (χo1 )(b1)) = β∗(↓¬1 ↑¬1 (χo1 ))(a2) b1∈B1 ∗ = = = = For the other inequality, consider the following chain where (⋆) follows from the inequality (k → l) ⊗ (l → m) ≤ k → l which holds for all k, l, m ∈ L. ⊓⊔ 5

Direct product of two L-fuzzy contexts Here we introduce the corresponding extension of the notion of direct product of two L-fuzzy contexts.

Definition 11. The direct product of two L-fuzzy contexts C1 = hB1, A1, r1i and C2 = hB2, A2, r2i is an L-fuzzy context C1ΔC2 = hB1 × A2, A1 × B2, Δi, such that Δ((o1, a2), (a1, o2)) = ¬r1(o1, a1) → r2(o2, a2).

The following result states properties of the just defined direct product of L-fuzzy contexts.

Lemma 6. Let C1 = hB1, A1, r1i and C2 = hB2, A2, r2i be two L-fuzzy contexts, where L satisfies the double negation law. Given two arbitrary L-multifunctions ϕ : B1 → LA2 and ψ : A2 → LB1 , for all o1, o2 ∈ B1 and a1, a2 ∈ A2 the following equalities hold ↑Δ (ϕr)(o2, a1) = ↓2 (ϕ∗(↓¬1 (χa1 )))(o2) = ↑1 (tϕ∗(↑¬2 (χo2 )))(a1) ↓Δ (ψr)(o1, a2) = ↑2 (ψ∗(↑¬1 (χo1 )))(a2) = ↓1 (tψ∗(↓¬2 (χa2 )))(o1) Proof. Consider the following chain of equalities: ↑Δ (ϕr)(o2, a1) = = = = = = ^ ^ ^ ^ ^ ^ (o1,a2)∈B1×A2 (o1,a2)∈B1×A2 (o1,a2)∈B1×A2 (o1,a2)∈B1×A2 (o1,a2)∈B1×A2 (o1,a2)∈B1×A2 (ϕr(o1, a2) → Δ((o1, a2), (o2, a1))) (ϕr(o1, a2) → (¬r1(o1, a1) → r2(o2, a2))) ((ϕr(o1, a2) ⊗ ¬r1(o1, a1)) → r2(o2, a2)) ((ϕr(o1, a2) ⊗ (1 → ¬r1(o1, a1))) → r2(o2, a2)) ((ϕr(o1, a2) ⊗

^ (χa1 (t1) → ¬r1(o1, t1))) → r2(o2, a2)) t1∈A1 ((ϕr(o1, a2)⊗ ↓¬1 (χa1 )(o1)) → r2(o2, a2)) = ^

^ ((ϕr(o1, a2)⊗ ↓¬1 (χa1 )(o1)) → r2(o2, a2)) o1∈B1 a2∈A2 = ^

^ (↓¬1 (χa1 )(o1) ⊗ (ϕ(o1)(a2)) → r2(o2, a2)) o1∈B1 a2∈A2 = ^ ↓2 (↓¬1 (χa1 )(o1) ⊗ ϕ(o1))(o2)

o1∈B1 = ↓2 ( _ (↓¬1 (χa1 )(o1) ⊗ ϕ(o1)))(o2)

o1∈B1 = ↓2 (ϕ(↓¬1 (χa1 )))(o2) Similarly we have ↑Δ (ϕr)(o2, a1) = (ϕr(o1, a2) → (¬r1(o1, a1) → r2(o2, a2))) (tϕ(a2)(o1) → (¬r2(o2, a2) → r1(o1, a1))) =

L-bonds vs direct products of L-fuzzy contexts The main contribution of the paper is presented in this section, in which a relationship between L-bonds and extents of direct products of L-fuzzy contexts is drawn by the following theorem. Theorem 1. Let Ci = hBi, Ai, rii be L-fuzzy contexts for i ∈ {1, 2}, where L satisfies the double negation law. Let β ∈ L-Mfn(B1, A2). Then: 1. If βr is an extent of C1ΔC2, then β ∈ L-Bond(C1, C2). 2. If β ∈ L-Bond(C1, C2) and ^ (↑¬1 (χo1 )(a1) → ↑2↓2 (β∗(↓( χa1 )))(a2)) = a1∈A1 =

^ (↑¬1 (χo1 )(a1) → a1∈A1

^ (↓2 (β∗(↓¬1 (χa1 )))(o2) → r2(o2, a2))) o2∈B2 = ^

^ (↑¬1 (χo1 )(a1) → (↓2 (β∗(↓¬1 (χa1 )))(o2) → r2(o2, a2))) a1∈A1 o2∈B2 = ^

^ ((↑¬1 (χo1 )(a1)⊗ ↓2 (β∗(↓¬1 (χa1 )))(o2)) → r2(o2, a2)) a1∈A1 o2∈B2 =

^ ( _ (↑¬1 (χo1 )(a1)⊗ ↓2 (β∗(↓¬1 (χa1 )))(o2)) → r2(o2, a2)) o2∈B2 a1∈A1 = ↑2 ( _ (↑¬1 (χo1 )(a1)⊗ ↓2 (β∗(↓¬1 (χa1 ))))(a2)

a1∈A1 = ↑2 ( _ (↑¬1 (χo1 )(a1) ⊗ (↑Δ (βr))mfn(a1))(a2)

a1∈A1 = ↑2 ((↑Δ (βr))mfn∗(↑¬1 (χo1 )))(a2) = ↓Δ↑Δ (βr)(o1, a2) =⋆ β∗(↓¬1 ↑¬1 (χo1 ))(a2) = β(o1)(a2) where (⋆) follows, firstly, from the hypothesis, which states that it equals to β∗(↓¬1 ↑¬1 (χo1 ))(a2) and, as β ∈ L-Bond(C1, C2), by Lemma 5. ⊓⊔

Conclusions and future work

We have introduced an adequate generalization of the study of L-bonds as morphisms among contexts, initiated in [ 14 ], by showing how the classical relationships between bonds and contexts can be lifted to a more general framework.

The contribution seems to pave the way towards determining possible categories on which to model knowledge transfer and information sharing. Other steps have been given in [ 12, 13 ] where the category of L-Chu correspondences has been considered. However, much work still has to be done.

A thorough study of the properties of the extended categorical framework of Chu correspondences and L-Chu correspondences is needed, in order to identify their natural interpretation within the theory of knowledge representation.

References

1. C. Alcalde , A. Burusco , R. Fuentes-Gonz´alez, and I. Zubia. Treatment of L-fuzzy contexts with absent values . Information Sciences , 179 : 1 - 15 , 2009 .

2. R. Bˇelohl´avek. Fuzzy concepts and conceptual structures: induced similarities . In Joint Conference on Information Sciences , pages 179 - 182 , 1998 .

3. R. Bˇelohl´avek . Lattices Generated By Binary Fuzzy Relations Tatra Mountains Mathematical Publications 16 : 11 - 19 , 1999

4. R. Bˇelohl´avek. Lattices of fixed points of fuzzy Galois connections . Mathematical Logic Quartely , 47 ( 1 ): 111 - 116 , 2001 .

5. R. Bˇelohl´avek . Fuzzy Relational Systems: Foundations and Principles Kluwer Academic Publishers, 2002

6. P. du Boucher-Ryana and D. Bridge . Collaborative recommending using formal concept analysis . Knowledge-Based Systems , 19 ( 5 ): 309 - 315 , 2006 .

7. A. Formica . Concept similarity in formal concept analysis: An information content approach . Knowledge-Based Systems , 21 ( 1 ): 80 - 87 , 2008 .

8. B. Ganter . Relational Galois connections. Lect Notes in Computer Science 4390 : 1 - 17 , 2007

9. B. Ganter and R. Wille . Formal concept analysis . Springer-Verlag, 1999 .

10. J. Goguen. The logic of inexact concepts . Synthese 19 : 325 - 373 , 1969 .

11. G. Jiang, K. Ogasawara , A. Endoh , and T. Sakurai . Context-based ontology building support in clinical domains using formal concept analysis . International Journal of Medical Informatics , 71 ( 1 ): 71 - 81 , 2003 .

12. O. Kr´ıdlo, M. Ojeda-Aciego, On the L-fuzzy generalization of Chu correspondences , International Journal of Computer Mathematics , to appear.

13. O. Kr´ıdlo, S. Krajˇci, and Ojeda-Aciego , M., An embedding of ChuCors in LChuCors , In Proc of Computational Methods in Mathematics, Science, and Engineering , 2010 . To appear

14. M. Kr¨otzsch, P. Hitzler, G-Q. Zhang , Morphisms in Context. Lecture Notes in Computer Science 3596 : 223 - 237 , 2005

15. Y. Lei and M. Luo . Rough concept lattices and domains . Annals of Pure and Applied Logic , 159 ( 3 ), 333 - 340 , 2009 .

16. X. Liu , W. Wang , T. Chai , and W. Liu . Approaches to the representations and logic operations of fuzzy concepts in the framework of axiomatic fuzzy set theory (I) and (II) . Information Sciences , 177 ( 4 ): 1007 - 1026 , and 1027- 1045 , 2007 .

17. J. Medina , and M. Ojeda-Aciego. Multi-adjoint t-concept lattices . Information Sciences , 180 ( 5 ): 712 - 725 , 2010 .

18. J. Medina , M. Ojeda-Aciego , and J. Ruiz-Calvin˜o. Formal concept analysis via multi-adjoint concept lattices . Fuzzy Sets and Systems , 160 ( 2 ): 130 - 144 , 2009 .

19. H. Mori . Chu Correspondences. Hokkaido Matematical Journal , 37 : 147 - 214 , 2008

20. V. Phan-Luong . A framework for integrating information sources under lattice structure . Information Fusion , 9 : 278 - 292 , 2008 .

21. L. Wang and X. Liu . Concept analysis via rough set and AFS algebra . Information Sciences , 178 ( 21 ): 4125 - 4137 , 2008 .

22. Q. Wu and Z. Liu . Real formal concept analysis based on grey-rough set theory . Knowledge-Based Systems , 22 ( 1 ): 38 - 45 , 2009 .