The second order formal context is a formal context such that its object and attribute sets are disjoint unions of object and attribute sets of external formal contexts. Every subset of object or attribute set will be evaluated from concept lattice of corresponding external formal context. The paper provides a method how to compute such second order formal concepts by using of bonds between external formal contexts or by using of heterogeneous formal contexts methods. Last part of the paper shows how this structure generalizes homogenic fuzzy formal context and its derivation operators.
TV W Ce R
• • ◦ • • • • ◦ • ◦ • ◦ • ? Partially supported by grant VEGA 1/0832/12 and APVV-0035-10. c paper author(s), 2013. Published in Manuel Ojeda-Aciego, Jan Outrata (Eds.): CLA 2013, pp. 117{128, ISBN 978{2{7466{6566{8, Laboratory L3i, University of La Rochelle, 2013. Copying permitted only for private and academic purposes.
F
Bob
• ◦ ◦ ◦ • • ◦ ◦ ◦ • • • • ◦ • • • ◦ • • •
All contexts are filled by truth degrees from the following set {• = true, ◦ = middle, ” ” = false}. Computing of L-concepts is based on Lukasiewicz logic.
Now, we aim at connecting such table data with known intercontextual mechanisms in order to obtain closed sets of friends from F that are able to stay in any of a closed set of hotels from H. The hotels of this closed set offer as much requirements from P as it gets.
H TV W C R H1 • • • • H2 • • • H3 • H4 • • • 2 2.1
Preliminaries
Formal Concept Analysis (FCA) as an applied Lattice Theory [
a ⊗ b ≤ c is equivalent to a ≤ b → c for any a, b, c ∈ L.
Definition 2. L-fuzzy formal context C is a triple hB, A, ri, where r : B × A → L is an L-fuzzy binary relation and L is the complete residuated lattice. Definition 3. Let hB, A, ri be an L-fuzzy formal context. Lets define a pair of derivation operators h↑, ↓i of the form ↑: LB −→ LA and ↓: LA −→ LB, where ↑ (f )(a) = ↓ (g)(b) = b∈B a∈A ^ (f (b) → r(b, a)) for any f ∈ LB and a ∈ A, ^ (g(a) → r(b, a)) for any g ∈ LA and b ∈ B. Lemma 1. Let h↑, ↓i be a pair of derivation operators defined on an L-fuzzy formal context hB, A, ri. A pair h↑, ↓i forms a Galois connection between complete lattices of all L-sets of objects LB and attributes LA.
Definition 4. Let C = hB, A, ri be an L-fuzzy formal context. Formal concept is a pair of L-sets hf, gi ∈ LB × LA such that ↑ (f ) = g and ↓ (g) = f . The set of all L-concepts of C will be denoted by FCL(C). Object or attribute part of any concept is called extent or intent. Sets of all extents or intents of C will be denoted as Ext(C) or Int(C), respectively. 2.2
FCA provides the useful methods how to connect two formal contexts. A
structure of the so called Chu correspondence was introduced by Mori [
Definition 5. Let Ci = hBi, Ai, rii for i ∈ {1, 2} be two L-fuzzy formal contexts. Pair of L-multimappings ϕ = hϕL, ϕRi such that – ϕL : B1 −→ Ext(C2), – ϕR : A2 −→ Int(C1), where ↑2 (ϕL(o1))(a2) =↓1 (ϕR(a2))(o1) for any (o1, a2) ∈ B1 × A2, is said to be an L-Chu correspondence between C1 and C2. Set of all L-Chu correspondences between L-contexts C1 and C2 will be denoted by L-ChuCors(C1, C2). Definition 6. Let Ci = hBi, Ai, rii for i ∈ {1, 2} be two L-fuzzy formal contexts. L-multimapping β : B1 −→ Int(C2), such that βt : A2 −→ Ext(C1), where βt(a2)(o1) = β(o1)(a2) for any (o1, a2) ∈ B1 × A2, is said to be an L-bond. Set of all L-bonds beyween L-contexts C1 and C2 will be denoted by L-Bonds(C1, C2). Lemma 2. Let Ci = hBi, Ai, rii for i ∈ {1, 2} be two L-fuzzy formal contexts. Each set L-Bonds(C1, C2) and L-ChuCors(C1, C2) forms a complete lattice and, moreover, there exists a dual isomorphism between them.
The dual isomorphism between bonds and Chu correspondences is based on the following construction. Consider two L-fuzzy formal contexts Ci = hBi, Ai, rii for i ∈ {1, 2} and let β ∈ L-Bonds(C1, C2), then hϕβL, ϕβRi such that for any (o1, a2) ∈ B1 × A2
ϕβL(o1) =↓2 (β(o1)) and ϕβR(a2) =↑1 (βt(a2)) is an L-Chu correspondence from L-ChuCors(C1, C2).
Categories ChuCors and L-ChuCors of classical or fuzzy formal contexts and
classical or fuzzy Chu correspondences are described in [
Definition 7. Lets define a functor Γ : L-ChuCors −→ L-CLLOS in the following way: 1. Γ (C) = hhL-FCL(C), ≈i, i for any L-context C 2. Γ (ϕ) = hλϕL, λϕRi for any ϕ ∈ L-ChuCors(C1, C2) such that λϕL : FCL(C1) −→ FCL(C2) and λϕR : FCL(C2) −→ FCL(C1) λϕL(hf, ↑1 (f )i) = h↓2↑2 (ϕL+(f )), ↑2 (ϕL+(f ))i
ϕ λR(h↓2 (g), gi) = h↓1 (ϕR+(g)), ↑1↓1 (ϕR+(g))i for any two L-concepts hf, ↑1 (f )i ∈ FCL(C1) and h↓2 (g), gi ∈ FCL(C2), where for any multifunction ω : X −→ LY is ω+ : LX −→ LY defined as ω+(f )(y) = Wx∈X f (x) ⊗ ω(x)(y) for any f ∈ LX and y ∈ Y .
In [
ϕ Lemma 3. Consider two L-contexts Ci = hBi, Ai, rii for i ∈ {1, 2} and let ϕ ∈ L-ChuCors(C1, C2). A functor Γ (ϕ) is a fuzzy Galois connection between hhFCL(C1), ≈1i, 1i and hhFCL(C2∗), ≈2i, 2i where C2∗ = hA2, B2, r2ti. Proof. Due to order reversing of dual L-context C2∗ for any two L-concepts we ϕ ϕ obtain hf, ↑1 (f )i 1 λR(h↓2 (g), gi) = h↓2 (g), gi 2 λL(hf, ↑1 (f )i) . tu 3
Formal concept analysis of second order Once we have introduced preliminaries, the formal context of second order and the corresponding results are presented now in details.
Definition 8. Consider two non-empty index sets I and J and an L-fuzzy formal context h i∈I Bi, Sj∈J Aj, ri, whereby
S – Bi1 ∩ Bi2 = ∅ for any i1, i2 ∈ I, – Aj1 ∩ Aj2 = ∅ for any j1, j2 ∈ J , – r : Si∈I Bi × Sj∈J Aj −→ L. Moreover, consider two non-empty sets of L-contexts notated – {Ci = hBi, Ti, pii : i ∈ I} – {Dj = hOj, Aj, qji : j ∈ J }.
Formal context of second order is a tuple
D [ Bi, {Ci; i ∈ I}, [ Aj, {Dj; j ∈ J }, i∈I j∈J [ Definition 9. Lets define the mappings h⇑, ⇓i as follows ⇑: Y FCL(Ci) −→ i∈I
Y FCL(Dj) and ⇓: Y FCL(Dj) −→ Y FCL(Ci) j∈J j∈J i∈I ⇑ (Φ)j = ^ λijL(Φi), for any Φ ∈ Y FCL(Ci) ⇓ (Ψ )i = ^ λijR(Ψ j), for any Ψ ∈ Y FCL(Dj) i∈I j∈J such that λij = hλijL, λijRi = Γ (ϕρij ), where
ρij = _{β ∈ L-Bonds(Ci, Dj) : (∀(oi, aj) ∈ Bi × Aj)β(oi)(aj) ≤ rij(oi, aj)}. Lemma 4. Let {hf, gi} ∪ {hfk, gki : k ∈ K} be a non-empty set of L-concepts of any L-context and K be a non-empty index set. Then hf, gi ^ hfk, gki = ^ (hf, gi
hfk, gki). k∈K k∈K Proof. Let the L-context be of the form hB, A, ri. Hence hf, gi ^ hfk, gki = ^ f (o) → ^ fk (o) = ^ f (o) → ^ fk(o) k∈K
o∈B k∈K o∈B = ^ ^ f (o) → fk(o) = ^ hf, gi k∈K hfk, gki . k∈K o∈B k∈K Lemma 5. Pair of mappings h⇑, ⇓i forms a Galois connection between complete
Q Q lattices h i∈I FCL(Ci), vI i and h j∈J FCL(Dj), vJ i.
Proof. Proof is provided in fuzzy ordering as a generalization of classical one. Ψ vJ ⇑ (Φ) = ^ (Ψ j j⇑ (Φ)j) = ^ Ψ j
j ^ λijL(Φi) 3.1
In this subsection will be presented a method that simplifies the previous consideration.
Definition 10. Let Ci = hBi, Ai, rii for i ∈ {1, 2} be two L-fuzzy contexts and let β be an arbitrary L-bond between C1 and C2. Consider the following pair of mappings ↑β: LB1 −→ LA2 and ↓β: LA2 −→ LB1 such that ↑β (f )(a) = ^ (f (o) → β(o)(a)), ↓β (g)(o) = ^ (g(a) → β(o)(a)) o∈B1 for any f ∈ LB1 and g ∈ LA2 . a∈A2 Lemma 6. Let Ci = hBi, Ai, rii for i ∈ {1, 2} be two L-fuzzy contexts and let β be an arbitrary L-bond between C1 and C2. A pair h↑β, ↓βi forms a Galois connection between complete lattices hExt(C1), ≤i and hInt(C2), ≤i, where ≤ is ordering based on fuzzy sets inclusion.
Proof. Proof of the fact that h↑β, ↓βi forms a Galois connection between hLB1 , ≤i and hLA2 , ≤i is simple, h↑β, ↓βi is a pair of derivation operators for L-context hB1, A2, βri, where binary L-relation βr is defined as βr(o1, a2) = β(o1)(a2).
Now, we will show that h↑β, ↓βi is a pair of mappings between complete lattices of extents and intents of C1 and C2, respectively. First, let f be an extent of C1.
↑β (f )(a) = ^ (f (o) → β(o)(a)) o∈B1 ^ (ϕβL(o)(b) → r2(b, a)) b∈B2
Proof of ↓β (g) is an extent of C1 is easy to obtain similarly with equality β(o)(a) =↓1 (ϕβR(o))(a).
Definition 11. Let K be a second order formal context of the form K = D[ Bi, {Ci : i ∈ I}, [ Aj, {Dj : j ∈ J }, i∈I j∈J [ (i,j)∈I×J
E rij .
Lets define an L-context Kb
Kb = D[ Bi, [ Aj, i∈I j∈J
[
ρij = _{β ∈ L-Bonds(Ci, Dj) : (∀(oi, aj) ∈ Bi × Aj)β(oi)(aj) ≤ rij(oi, aj)}. Lemma 7. Concept lattices of K and Kb are isomorphic.
Proof. Let hΦ, Ψ i be an L-concept of Kb and o ∈ Bi.
Φi(o) = (↓Kb (Ψ ))i(o) = ^
^ (Ψ j(a) → ρij(o)(a)) j∈J a∈Aj j∈J a∈Aj j∈J = ^
^ (Ψ j(a) →↓i (ϕρijR(a))(o)) = ^ ↓i (ϕρijR+(Ψ j))(o). Φi = (↓Kb (Ψ ))i = ^ ↓i (ϕρijR+(Ψ j)) = ^ ext(λϕRρij (Ψ j))
j∈J = ext
j∈J ^ λϕρij (Ψ j) = ext(⇓ (Ψ )i),
R j where Ψ = h↓j (Ψ j), Ψ ji for any j ∈ J . Then Φ =⇓ (Ψ ) and hΦ, Ψ i is a second order concept of K. tu 4
Motivation example – solution The motivation example introduced in Section 1 can be considered as the second order formal context
h{Anna,Bob,Cyril,David,Eva}, F , {TV,W,Ce,R}, H, ri, whereby r represents the L-relation from P. Firstly, we find a bond ρ that is the closest to r.
P TV W Ce R Anna • • • Bob ◦ ◦ • • Cyril ◦ • • ◦ David • • ◦ Erik • • ◦ • ρ(P) TV W Ce R Anna • • • Bob ◦ ◦ • ◦ Cyril ◦ ◦ • ◦
There are just six (instead of twenty-eight L-concepts of P) L-concepts of ρ(P) such that we can easily convert into the form of second order concepts. The following table contains the list of the all second order concepts.
concepts of F concepts of H {◦/A, •/B, •/C, ◦/D, ◦/E} {◦/TV, ◦/W, •/Ce, ◦/R} {◦/A, •/B, •/C, ◦/D, ◦/E} {•/H1, /H2, ◦/H3, ◦/H4} {•/A, •/B, •/C, •/D, •/E} { /TV, /W, ◦/Ce, /R} { /A, ◦/B, ◦/C, /D, /E} {•/H1, ◦/H2, •/H3, •/H4} {•/A, •/B, •/C, ◦/D, ◦/E} {◦/TV, /W, •/Ce, ◦/R} {◦/A, ◦/B, ◦/C, /D, /E} {•/H1, /H2, ◦/H3, •/H4} {•/A, ◦/B, ◦/C, /D, /E} {•/TV, /W, •/Ce, •/R} {•/A, ◦/B, ◦/C, /D, /E} {•/H1, /H2, /H3, •/H4} {◦/A, ◦/B, ◦/C, /D, /E} {•/TV, ◦/W, •/Ce, •/R} {•/A, •/B, •/C, ◦/D, ◦/E} {•/H1, /H2, /H3, ◦/H4} { /A, ◦/B, ◦/C, /D, /E} {•/TV, •/W, •/Ce, •/R} {•/A, •/B, •/C, •/D, •/E} {•/H1, /H2, /H3, /H4}
The first concept can be interpreted as follows. Friends Bob and Cyril with their common requirements should stay in hotel H1. They should stay also in H3 and H4 with a little relaxation of their requirements. The fourth concept is saying that Anna as a very lonely person should stay in H1 or H4. The second concept includes the whole group of co-workers who have very poor common requirements. Thus, all people should stay in an arbitrary hotel together.
Connection to heterogeneous formal contexts
The fruitful idea is to view the second order formal context in terms of a
heterogeneous formal context proposed in [
Definition 12. Heterogeneous formal context is a tuple hB, A, P, R, U , V, i, where – B and A are non-empty sets, – P = {hPb,a, ≤Pb,a i : (b, a) ∈ B × A} is a system of posets, – R is a mapping from B × A such that R(b, a) ∈ Pb,a for any b ∈ B and a ∈ A, – U = {hUb, ≤Ub i : b ∈ B} and V = {hVa, ≤Va i : a ∈ A} are systems of complete latices, – = {◦b,a : (b, a) ∈ B × A} is a system of isotone and left-continuous mappings ◦b,a : Ub × Va −→ Pb,a.
Lets describe our situation in terms of heterogeneous formal contexts. Below is the translation: – B and A will be the index sets I and J , – complete lattices Ui or Vj for any (i, j) ∈ B × A = I × J will be the complete lattices hExt(Ci), ≤i and hInt(Dj ), ≤i, – Pi,j will be a complete lattice of all fuzzy relations from LBi×Aj , – any value of relation r will be a binary relation r(i, j) = ri,j ∈ LBi×Aj , – operation ◦i,j : Ext(Ci) × Int(Dj ) −→ LBi×Aj is defined as
(f ◦i,j g)(b, a) = f (b) ⊗ g(a) for any f ∈ Ext(Ci) and g ∈ Int(Dj ) and any (b, a) ∈ Bi × Aj . The mapping ◦i,j is isotone due to isotonicity of ⊗.
Lemma 8. The mapping ◦i,j is left-continuous.
Proof. Let
(fk ◦ g)(b, a) = fk(b) ⊗ g(a) ≤ m for all k ∈ K and for some (b, a) ∈ B × A and m ∈ L. It is equivalent to inequality fk(b) ≤ g(a) → m for all k ∈ K. Hence, Wk∈K fk(b) ≤ g(a) → m and it is equivalent to _ fk ◦ g (b, a) = k∈K _ fk(b) ⊗ g(a) ≤ m.
k∈K
Definition 13. Lets define a pair of derivation operators h-, &i of the following form -: Qi∈I Ext(Ci) → Qj∈J Int(Dj) and &: Qj∈J Int(Dj) → Qi∈I Ext(Ci) defined for heterogeneous formal context mentioned above as follows: - (Φ)j = _{g ∈ Int(Dj) : (∀i ∈ I)Φi ◦i,j g ≤ ri,j} & (Ψ )i = _{f ∈ Ext(Ci) : (∀j ∈ J )f ◦i,j Ψ j ≤ ri,j} for any Φ ∈ Qi∈I Ext(Ci) and any Ψ ∈ Qj∈J Int(Dj).
Lemma 9. Let K = hSi∈I Bi, {Ci; i ∈ I}, Sj∈J Aj, {Dj; j ∈ J }, S(i,j)∈I×J ri,ji be a second order formal context. Then
↑Kb (Φ) ≤- (Φ) and ↓Kb (Ψ ) ≤& (Ψ ) for any Φ ∈ Qi∈I Ext(Ci) and Ψ ∈ Qj∈J Int(Dj).
↑Kb (Φ)j(a) = ^
^ (Φi(o) → ρij(o)(a)) i∈I o∈Bi = _{g ∈ Int(Dj) : (∀i ∈ I)(∀o ∈ Bi)Φi(o) ⊗ g(a) ≤ ρij(o)(a)}.
↑Kb (Φ)j = _{g ∈ Int(Dj) : (∀i ∈ I)(∀o ∈ Bi)Φi ◦ij g ≤ ρij} because of ρij ≤ rij ≤ _{g ∈ Int(Dj) : (∀i ∈ I)(∀o ∈ Bi)Φi ◦ij g ≤ rij} =- (Φ)j.
Hence ↑Kb (Φ) ≤- (Φ). Similarly for ↓Kb and &. 6
Connections to standard homogenic fuzzy operators In this part, we focus on an appropriate generalization of the standard homogenic fuzzy formal concept derivation operators in two different ways. 6.1
Lemma 10. Lets have an L-fuzzy formal context h{x}, L, λi, where for an arbitrary k ∈ L is ⊥x = λ(x, k) = k. Any value k ∈ L is an extent of ⊥x. Proof. Let k be an arbitrary value from L.
↓↑ (k)(x) = ^ (↑ (k)(m) → m) = m∈L ^ ( ^ (k → m) → m) m∈L x∈{x} tu m∈L:m≥k (1 → m) ∧ m ∧
^ m∈L:m<k
^ m∈L:m<k
((k → m) → m) ((k → m) → m) = ? m = k (L is a complete lattice) (k → m) → m ≥ k (closure property) ^
((k → m) → m) ≥ k m∈L:m<k ? = k So ↓↑ (k) = k for any k ∈ L.
Proof. Let Φ ∈ Qb∈B Ext(⊥b). By previous lemma is easy to see that Φ ∈ LB. Moreover r(b, a) for any (b, a) ∈ B × A as an arbitrary value from L is an extent of ⊥b and intent of ⊥∗a = hL, {a}, tλi. Hence any r(b, a) ∈ L-Bonds(⊥b, ⊥∗a). ↑Kb (Φ)(a) = ^ ↑r(b,a) (Φ(o)) =
^ (Φ(o) → r(o, a)) =↑ (Φ)(a). b∈B b∈B Similarly for ↓Kb =↓. 6.2 6= connection Moreover, an another connection is presented in this subsection. The connection is based on the fact that concept lattice of hX, X, 6=i is isomorphic to LX in the case that L is closed under double negation law.
Lemma 12. Lets have an L-fuzzy formal context X = hX, X, 6=i, where L is closed under double negation law. Then any L-set from LX is closed in X . Proof. Lets have an arbitrary L-set f ∈ LX .
↑ (f )(x) = ^ (f (y) → (y 6= x)) y∈X
^ y∈X:y6=x = 1 ∧ ¬f (x) = ¬f (x) =
(f (y) → 1) ∧ (f (x) → (x 6= x)) Then ↓↑ (f )(x) = ¬¬f (x) = f (x). tu tu Lemma 13. Lets have an L-fuzzy formal context C = hB, A, ri, where L is closed under double negation law. Concept lattice of C is isomorphic to a concept lattice of second order formal context K = B, B, A, A, r , where B = hB, B, 6=i and A = hA, A, 6=i.
Proof. Index sets I and J are singletons in this case. So due to previous lemma Φ ∈ Ext(B) = LB. ⇑ (Φ) =↑ρ (f ) where ρ = W{β ∈ L-Bonds(B, A) : β ≤ r}. Because of the previous lemma we know that any row and column or r is closed in B and A, respectively. Hence r ∈ L-Bonds(B, A) and r = ρ.
Finally ↑Kb =↑. Similarly for ↓Kb =↓. tu