In this work we focus on the use of intensifying hedges as a tool to reduce the size of the recently introduced multi-adjoint concept lattices with heterogeneous conjunctors. ⋆ Partially supported by grant No. P202/10/0262 of the Czech Science Foundation. ⋆⋆ Partially supported by Spanish Ministry of Science and FEDER funds through project TIN09-14562-C05-03 and Junta de Andaluc´ıa project P09-FQM-5233. ⋆ ⋆ ⋆ Partially supported by Spanish Ministry of Science and FEDER funds through project TIN09-14562-C05-01 and Junta de Andaluc´ıa project P09-FQM-5233.
Formal concept analysis (FCA) is a very active topic for several research groups throughout the world [6, 1, 3, 5, 7, 8, 10, 11]. In this work, the authors aim to merge recent advances obtained in this area: on the one hand, the use of hedges as structures which allow to modulate the size of fuzzy concept lattices [4] and, on the other hand, the consideration of heterogeneous conjunctors in the general approach to fuzzy FCA so-called multi-adjoint framework [9].
One of the key features of the latter approach is that some quasi-closure operators arise which, although do not directly allow to prove the complete lattice structure of the resulting set of concepts as usual, i.e. in terms of a Galois connection, actually do provide means to manually build the operators for suprema and infima of a set of concepts. The core notion in [9] is that of P connected pair of posets which, in some sense, turns out to be a more abstract notion than a truth-stressing hedge. As a consequence of this observation, due to Radim Belohlavek, we now focus on the use of the specific properties of hedges in order to import some results related to the size of fuzzy concept lattices to the more general framework of [9].
The structure of the paper is the following: in Section 2 the preliminary definitions are introduced, interested readers will obtain further comment on the intuitions underlying the definitions in the original papers [4, 9]; the main results are presented in Section 3. c 2012 by the paper authors. CLA 2012, pp. 245–256. Copying permitted only for private and academic purposes. Volume published and copyrighted by its editors. Local Proceedings in ISBN 978–84–695–5252–0, Universidad de M´alaga (Dept. Matem´atica Aplicada), Spain.
In this section, we introduce the basic definitions and preliminary results which will be used later in the core of this work.
Definition 1. Let (L, , ⊤, ⊥) be a complete lattice, a truth-stressing hedge in L is a mapping ∗ : L → L satisfying, for each x, y ∈ L, ∗(⊤) = ⊤, ∗(x)
x, x y implies ∗ (x)
∗(y), ∗(∗(x)) = ∗(x) fix(∗) denotes set of fixed points of ∗ in L, i.e. fix(∗) = {a ∈ L | ∗(a) = a}.
In [3, 4] truth-stressing hedges were used to decrease size of a concept lattice (in fact, the truth-stressing hedges were defined on a residuated lattice).
Lemma 1. Let (L, ) be a complete lattice, for any mapping ∗ : L → L
satisfying (
i∈I i∈I In addition, if we have xj = Wi∈I xi for some j ∈ I then Similarly, if we have xj = Vi∈I xi for some j ∈ I then ∗(_ xi) = _ ∗(xi).
i∈I i∈I ∗(^ xi) = ^ ∗(xi).
i∈I i∈I
Lemma 2. (a) Let ∗ : L → L be a mapping satisfying (
By Lemma 2 the set fix(∗) of truth-stressing hedge ∗ is a ∨-subsemilattice.
Now we will introduce the basic notions of multi-adjoint concept lattices with
heterogeneous conjunctors, in order to show how both frameworks, hedges and
heterogeneous conjunctors, can be merged.
(
Firstly, let us introduced a bit of terminology: in the rest of this work we will
call a mapping ∗ : L → L satisfying (
The two main notions on which multi-adjoint concept lattices with heterogeneous conjunctors is defined are given below: the P -connection between posets, and the adjoint triples.
Definition 2. Given the posets (P1, ≤1), (P2, ≤2) and (P, ≤), we say that P1 and P2 are P -connected if there exist non-decreasing mappings ψ1 : P1 → P , φ1 : P → P1, ψ2 : P2 → P and φ2 : P → P2 verifying that φ1(ψ1(x)) = x, and φ2(ψ2(y)) = y, for all x ∈ P1, y ∈ P2.
Definition 3. Let (P1, ≤1), (P2, ≤2), (P3, ≤3) be posets, and consider mappings & : P1 × P2 → P3, ւ : P3 × P2 → P1, տ : P3 × P1 → P2, then (&, ւ, տ) is an adjoint triple with respect to P1, P2, P3 if: x ≤1 z ւ y iff x & y ≤3 z iff y ≤2 z տ x, where x ∈ P1, y ∈ P2 and z ∈ P3.
Corollary 1. Consider the posets (P1, ≤1), (P2, ≤2) and (P, ≤), and assume
that L1 and L2 are P -connected, then:
(a) If ψ1 ◦ φ1 is contractive (i.e. satisfies (
Lemma 3. Let (L, ), (L1, 1), (L2, 2) be lattices and let (&, ւ, տ) be an adjoint triple. For a, ai ∈ L1, b, bi ∈ L2, we have
Wi∈I (ai & b) = (W1i∈I a) & b and
Wi∈I (a & bi) = a &(W2i∈I bi)
(
(L1, L2, P, &1, ւ1, տ1, . . . , &n, ւn, տn) where Li are complete lattices and P i a poset, such that (&i, ւi, տi) is an adjoint triple with respect to L1, L2, P for all i = 1, . . . , n.
Definition 5. Let (L1, L2, P, &1, . . . , &n) be a multi-adjoint frame, a multiadjoint context is a tuple (A, B, R, σ) such that A and B are non-empty sets (usually interpreted as attributes and objects, respectively), R is a P -fuzzy relation R : A × B → P and σ : B → {1, . . . , n} is a mapping which associates any element in B with some particular adjoint triple in the frame.
Given a complete lattice (L, ) such that L1 and L2 are L-connected, a
multi-adjoint frame (L1, L2, P, &1, . . . , &n), and a context (A, B, R, σ), we can
define the mappings ↑cσ : LB → LA and ↓cσ : LA → LB defined for all g ∈ LB
and f ∈ LA as follows:
g↑cσ (a) = ψ1(inf{R(a, b) ւσ(b) φ2(g(b)) | b ∈ B})
f ↓cσ (b) = ψ2(inf{R(a, b) տσ(b) φ1(f (a)) | a ∈ A})
(
The notion of concept is defined as usual. A concept is a pair hg, f i satisfying g ∈ LB, f ∈ LA and that g↑cσ = f and f ↓cσ = g.
Definition 6. Given the complete lattices (L1, 1), (L2, 2) and (L, ), where L1 and L2 are L-connected, the set of multi-adjoint L-connected concepts associated to a multi-adjoint frame (L1, L2, P, &1, . . . , &n) and context (A, B, R, σ) is given by ML = {hg, f i | hg, f i is a concept}.
The main theorem of concept lattices in [9], proves that ML has the structure of a complete lattice: Theorem 1 ([9]). Given complete lattices (L1, 1), (L2, 2) and (L, ), where L1 and L2 are L-connected, a context (A, B, R, σ), and a multi-adjoint frame (L1, L2, L, &1, . . . , &n), the multi-adjoint L-connected concept lattice ML is actually a complete lattice with the meet and join operators f, g : ML ×ML → ML defined below, for all hg1, f1i, hg2, f2i ∈ ML, hg1, f1i f hg2, f2i = hψ2 ◦ φ2(g1 ∧ g2), (f1 ∨ f2)↓c↑c i hg1, f1i g hg2, f2i = h(g1 ∨ g2)↑c↓c , ψ1 ◦ φ1(f1 ∧ f2)i
which corresponds to f and g is defined as hg1, f1i
hg2, f2i iff φ2(g1) ≤ φ2(g2) (iff φ1(f2) ≤ φ1(f1))
In what follows M denotes multi-adjoint L-connected concept lattice of given context (A, B, R, σ). We will also omit subscript σ(b) and write just ւ instead of ւσ(b). 3
Reducing the size of multi-adjoint concept lattices The size of the concept lattice M can be reduced either by a suitable selection of a ∨-subsemilattice of L1 (and/or L2) and the use of a restriction of &. The following proposition says that the selection of ∨-subsemilattices of L1 (resp. L2) yields a reduction of size of concept lattice and, moreover, preserves intents (or extents) of the original concept lattice, meaning that each intent of the reduced concept lattice is an intent of the original concept lattice. Proposition 1. Let A = (L1, L2, P, &1, . . . , &n), A′ = (K1, L2, P, &′1, . . . , &′n) be multi-adjoint frames, s.t. K1 is a ∨-subsemilattice of L1, and &′1, . . . , &′n are restrictions of &1, . . . , &n to K1 × L2 and ψ1′ = ψ1, ψ2′ = ψ2, φ′2 = φ2, φ′1 = ∗K1 ◦φ1, where ∗K1 is the hedge associated to K1 as introduced in Lemma 2. Then, Int(MA′ ) ⊆ Int(MA) where Int(M) denotes the set of intents in M. Proof (sketch). We have z տ′ x = z տ x, for each x ∈ K1, z ∈ P , whence f ↓′ = f ↓, for each f : A → ψ1(K1) where ψ1(K1) ∈ L is image of ψ1 (note that ւ′ is well-defined since K1 is ∨-subsemilattice) and thus by Proposition 16 in [9] Ext(MA′ ) ⊆ Ext(MA). ⊔⊓ Remark 1. One can state a dual proposition to Proposition 1 for intents. Let A = (L1, L2, P, &1, . . . , &n), A′ = (L1, K2, P, &′1, . . . , &′n) be multi-adjoint frames, s.t. K2 is a ∨-subsemilattice of L2, and &′1, . . . , &′n are restrictions of &1, . . . , &n to L1 × K2 and φ′2 = ∗K2 ◦ φ2.
The following proposition says that by selection of ∨-subsemilattices of both L1 and L2 we obtain a reduction of the size as well. However, the preservation of intents (or extents) is lost.
Proposition 2. Let A = (L1, L2, L, &1, . . . , &n), A′ = (K1, K2, L, &′1, . . . , &′n) be multi-adjoint frames, s.t. K1 is a ∨-subsemilattice of L1, K2 is a ∨-subsemilattice of L2, and &′1, . . . , &′n are restrictions of &1, . . . , &n to K1 × K2, and φ′1 = ∗K1 ◦ φ1, φ′2 = ∗K2 ◦ φ2. Then we have |MA′ | ≤ |MA|.
In the next result we show how to generate new adjoint triples using hedges.
Lemma 4. Assume (&, ւ, տ) is an adjoint triple with respect to L1, L2, P ,
and ∗1 : L1 → L1, ∗2 : L2 → L2 are hedges, then x &∗ y = ∗1(x) & ∗2(y) has two
residuated implications ւ∗, տ∗ which form a new adjoint triple with respect to
L1, L2, P , if and only if the following equalities hold:
∗1(z ւ ∗2(y)) = ∗1(_{x | x &∗ y ≤ z})
∗2(z տ ∗1(x)) = ∗2(_{y | x &∗ y ≤ z})
(
∗2(y) 2 z տ∗ ∗1(x) implies ∗2 (y) 2 ∗2(z տ∗ ∗1(x))
and due to (
∗2(y) 2 ∗2(z տ∗ ∗1(x)) implies ∗2 (y) 2 z տ∗ ∗1(x)
x &∗ y ≤ z iff ∗2 (y) 2 ∗2(z տ∗ ∗1(x)).
∗1(x) & ∗2(y) ≤ z iff ∗2 (y) 2 ∗2(z տ ∗1(x)) By setting y = (z տ ∗1(x)), in Equation (13), and y = (z տ∗ ∗1(x)), in Equation (15), we obtain equivalent inequalities ∗2(z տ ∗1(x)) ∗2(z տ∗ ∗1(x)), ∗2(z տ ∗1(x)) ∗2(z տ∗ ∗1(x)) respectively. Thus we have
∗2(z տ ∗1(x)) = ∗2(z տ∗ ∗1(x)).
“⇐”: Assume (12) holds true. By properties of adjointness, to show that &∗ generates an adjoint triple we need to show that
R = {y | ∗1(x) & ∗2(y) ≤ z} has a greatest element.
∗1(x) & ∗2(y) ≤ z iff ∗2 (y) 2 ∗2(z տ ∗1(x))
(15)
hence R = {y | ∗2(y) ∗2(z տ ∗1(x))}. Now, if R has no greatest element, i.e.
WR ∈/ R, then we have ∗2(WR) 6 ∗2(z տ ∗1(x)) which is a contradiction with
the assumption. By the contradiction we proved that R has a greatest element.
⊔⊓
Proposition 3. Let A = (L1, L2, P, &1, . . . , &n) be a multi-adjoint frame ∗1, ∗2
be hedges on L1 and L2, respectively. Let A′ = (fix(∗1), fix(∗2), P, &′1, . . . , &′n)
s.t. &′1, . . . , &′n are restrictions of &1, . . . , &n to fix(∗1) × fix(∗2), and φ′1 = ∗1 ◦
φ1, φ′2 = ∗2 ◦φ2. Let A∗ = (L1, L2, P, &1∗, . . . , &∗n) be a multi-adjoint frame where
&i∗ is defined by a &i∗ b = ∗1(a) &i ∗2(b), for all i ∈ {1, . . . , n}, and the conditions
in Lemma 4 are satisfied. Then (MA′ , ′) and (MA∗ , ∗) are isomorphic.
Proof. Let K = (A, B, R, σ) be a formal context, denote by ↑, ↓ concept-forming
operators induced by K and A′ and denote by ⇑, ⇓ concept-forming operators
induced by K and A∗. Furthermore, denote compositions ψ1 ◦ ∗1 ◦ φ1 and ψ2 ◦
∗2 ◦ φ2 by •1 and •2 respectively.
(13)
(14)
For each mapping g : B → L we have
where (∆ ) is due to Lemma 1 (
1 = ψ1^ _ {x | ∗1(x) & ∗2 ∗2 (φ2(g(b))) ≤ R(a, b)}
1 2 = ψ1^ _ {x | ∗1(x) & ∗2(φ2(g(b))) ≤ R(a, b)}
1 2 = ψ1^ R(a, b) ւ∗ φ2(g(b)))
1 = g⇑(a) and dually •1(f )⇓ = f ⇓. Putting it together, we have g = g⇑⇓ = •1(g⇑)⇓ = •2(g)↑⇓ showing that ↑⇓ is injective; whence •1, •2 are bijections.
To show that •1, •2 are order-preserving let hg1, f1i , hg2, f2i ∈ MA∗ . An extent of hg1, f1i ∧ hg2, f2i is equal to ψ2φ2(g1 ∧ g2) by the main Theorem in [9].
For g1, g2 ∈ Ext(MA∗ ) we have •2ψ2φ2(g1 ∧ g2) = ψ2 ∗2 φ2ψ2φ2(g1 ∧ g2) (∆ ) = ψ2φ′2(•2(g1) ∧ •2(g2)) Equality (∆ ) is due to Corollary 1(b) since note that g1, g2 are fixpoints of ψ2◦φ2.
Now, let g1, g2 ∈ Ext(MA′ ). We have (ψ2φ′2(g1 ∧ g2))↑⇓ = (ψ2 ∗2 φ2(g1 ∧ g2))↑⇓ = (•1(g1 ∧ g2))↑⇓ = (•1(g1↑↓ ∧ g2↑↓))↑⇓ = (•1(•1(g1↑⇓) ∧ •1(g2↑⇓))↑⇓ (=∆) (•1 •1 (g1↑⇓ ∧ g2↑⇓))↑⇓ = (•1(g1↑⇓ ∧ g2↑⇓))↑⇓ = (g1↑⇓ ∧ g2↑⇓)⇑⇓ (∇) = ψ2φ2(g1↑⇓ ∧ g2↑⇓) Equality (∆ ) is due to Corollary 1(b) since g1, g2 are fixpoints of ψ2 ◦ φ2; equality (∇) is due to [9, Lemma 21].
This proves that •1, •2, ↑⇓, and ↓⇑ are order-preserving. ⊔⊓ Example 1. Consider the multi-adjoint frame depicted in Fig. 1 (structures are the same as in [9, Example 3 (Fig. 2)] (where all &i’s coincide). Figure 2 depicts a formal context with two objects and two attributes, together with their associated multi-adjoint concept lattice.
Concept lattices with truth-stressing hedges In this part, we follow the way in which the hedges are used in [4], i.e. we generalize concept-forming operators using intensifying hedges. Then we show how this is related to the theory described above.
g△(a) = ψ1^ f ▽(b) = ψ2^ 1b∈B 2a∈A
R(a, b) ւ ∗2(φ2(g(b))),
R(a, b) տ ∗1(φ1(f (a))).
Note that this is not strictly the same approach as used in Proposition 3 since ւ and տ are residua of the original adjoint operators &, not the altered operators &∗. In fact, generally there is no base operation & such that (·) ւ ∗2(·) and (·) տ ∗1(·) are its residua, since we do not generally have
x ≤ z ւ ∗2(y) iff y ≤ z տ ∗1(x) for each x ∈ L1, y ∈ L2, z ∈ L.
Lemma 5. Assume (&, ւ, տ) is an adjoint triple, ∗1, ∗2 are intensifying hedges, and ւ⋄, տ⋄ being defined as z ւ⋄ y = z ւ ∗2y, and z տ⋄ x = z տ ∗1x; then
Using intensifying hedges to reduce size of multi-adjoint concept lattices 253 v
y t x ւ α β γ δ t d d c c u d d d d v d d d b x d a a a y d d c a z d a a a u տ a b c d t δ β δ β u δ δ δ δ v δ δ γ γ x δ α α α y δ β γ β z δ α α α 1 2 1 u v 2 v y (v,v)(u,x) (v,u)(u,t)
(u,v)(v,x) (v,y)(u,v)
(u,u)(v,t) (u,y)(v,v) (v, v)(x, x) (x, t)(y, x) (v, x)(x, t) (x, v)(y, x) (v, x)(x, y) (x, x)(t, t) (x, x)(v, v) ւ⋄, տ⋄ are part of an adjoint triple with conjunctor &⋄ if and only if for all x, y the following equality holds and, in this case the previous value is the definition of &⋄.
∗1(x) & y ≤ z iff y 2 z տ ∗1(x) iff y 2 z տ⋄ x.
x & ∗2(y) ≤ z iff x 1 z ւ ∗2(y) iff x 1 z ւ⋄ y.
y 2 z տ⋄ x iff x 1 z ւ⋄ y x & ∗2(y) ≤ z iff ∗1 (x) & y ≤ z, which is equivalent to x & ∗2(y) = ∗1(x) & y. ⊔⊓
However, the concept-forming operators △, ▽ are in one-to-one correspondence with concept-forming operators ↑, ↓ with restrictions of L1 and L2 to subsemilattices fix(∗1) and fix(∗2): •1(g△(a)) = •1(ψ1^
R(a, b) ւ ∗2φ2(g(b))) b∈B 1b∈B = ψ1 ∗1 (^
R(a, b) ւ ∗2(φ2(g(b)))) = ψ1^1b∈B ∗1 (R(a, b) ւ ∗2(φ2(g(b)))) = ψ1^1b∈B ∗1 _ {x | x & ∗2(φ2(g(b))) ≤ R(a, b)}
1 = ψ1^
_ {∗1(x) | x & ∗2(φ2(g(b))) ≤ R(a, b)} 1b∈B 1 (∆ ) = ψ1^ = ψ1^ = ψ1^ = ψ1^
1b∈B = g↑(a)
_ {∗1(x) | ∗1(x) & ∗2(φ2(g(b))) ≤ R(a, b)} 1b∈B 1
_ {x ∈ fix(∗1) | x & ∗2(φ2(g(b))) ≤ R(a, b)} 1b∈B 1
_ {x ∈ fix(∗1) | x & φ′2(g(b)) ≤ R(a, b)} 1b∈B 1
R(a, b) ւ φ′2(g(b)) where equality (∆ ) holds because each x satisfying x & y ≤ z satisfies ∗2(x) & y ≤ z as well; and because each ∗2(x) such that ∗2(x) & y ≤ z there is x′ (explicitly, ∗2(x)) with ∗2(x′) = ∗2(x) such that x′ & y ≤ z. Dually, one can show •2(f ▽) = f ↓.