In the first part, we extend our results from a previous paper on factorization of residuated lattices to residuated lattices with hedges. In the second part, we show how this result can be applied to the problem of factorization of fuzzy concept lattices with hedges. Our approach is that instead of factorizing the original concept lattice with hedges we construct a new data table with fuzzy values of attributes in a factorized residuated lattice with hedges and show that the induced concept lattice is isomorphic to the factor concept lattice.
Formal concept analysis (FCA) is a popular method for analysis of object-attribute data
[
In the case of formal concept analysis of data with fuzzy values of attributes the domain for data can consist of more than two elements (representing degrees to which particular objects can have particular attributes). Since the number of formal concepts can be large in this case, several methods of reducing the size of resulting concept lattice have been proposed. In this paper, we consider two of them: factorization and hedges.
The idea behind factorization of fuzzy concept lattices is that instead of
considering the original concept lattice, which can be very large, we accept not to distinguish
between formal concepts which are sufficiently similar. This can be done by choosing
a degree of similarity of formal concepts and factorizing the concept lattice by the
tolerance relation induced by this degree. As the result, we obtain a smaller lattice, whose
size depends on the prescribed degree. This parametrized size reduction method has
been introduced in [
In [
In [
In [
In this paper, we first generalize our results from [
In the next part we show that factor fuzzy concept lattices with hedges can be again described by means of factor residuated lattices with hedges. More precisely, we show that each factor fuzzy concept lattice with hedges is isomorphic to a fuzzy concept lattice with hedges built on a data table with values from the factorized residuated lattice.
This paper is organized as follows. In Section 2 we summarize basic known facts on residuated lattices, fuzzy sets, factorization of residuated lattices and factorization of concept lattices with hedges. In Section 3 we give our two main results on factorization of residuated lattices with hedges and factorization of concept lattices with hedges. 2 2.1
We use complete residuated lattices as structures of truth values. We recall only basic
facts here, for more detailed review, we refer the reader to [
A complete residuated lattice is defined as an algebra L = hL, ∧, ∨, ⊗, →, 0, 1i such that hL, ∧, ∨, 0, 1i is a complete lattice with the least element 0 and the greatest element 1; hL, ⊗, 1i is a commutative monoid (i.e. ⊗ is commutative, associative, and a ⊗ 1 = 1 ⊗ a = a for each a ∈ L); ⊗ (product) and → (residuum) satisfy so-called adjointness property: a ⊗ b ≤ c iff a ≤ b → c for each a, b, c ∈ L. Elements of L are called truth degrees. ⊗ and → are (truth functions of) “fuzzy conjunction” and “fuzzy implication”.
For each complete residuated lattice we consider a derived (truth function of) logical connective ↔ (“fuzzy equivalence”) defined by a ↔ b = (a → b) ∧ (b → a). ↔ is called biresiduum and is used for measuring similarity of truth degrees.
A common choice of L is a structure with L = [
Go¨del:
Goguen (product):
a ⊗ b = max(a + b − 1, 0),
a → b = min(1 − a + b, 1),
a → b =
a ⊗ b = min(a, b),
1 if a ≤ b,
b otherwise,
a → b =
a ⊗ b = a · b,
1 if a ≤ b,
ba otherwise.
(1)
(2)
(3)
Complete residuated lattices on [
The class of complete residuated lattices include finite structures as well. For
instance, we can put Ln+1 = {a0 = 0, a1, . . . , an = 1} ⊆ [
A special case of a complete residuated lattice is the two-element Boolean algebra h{0, 1}, ∧, ∨, ⊗, →, 0, 1i, denoted by 2, which is the structure of truth degrees of the classical logic. That is, the operations ∧, ∨, ⊗, → of 2 are the truth functions (interpretations) of the corresponding logical connectives of the classical logic.
A hedge (or truth stresser) on residuated lattice L is a unary operation ∗ satisfying
(i) 1∗ = 1, (ii) a∗ ≤ a, (iii) (a → b)∗ ≤ a∗ → b∗, (iv) a∗∗ = a∗, for a, b ∈ L. A hedge ∗ is
a (truth function of) logical connective “very true” [
Among all hedges on any residuated lattice, the greatest one is given by a∗ = a and is called (obviously) identity. The smallest hedge is called globalization and is given by 1∗ = 1 and a∗ = 0 for a < 1. In Fig. 1 there are depicted all possible hedges on L5.
glob.
!L1 !L2 !L3 Fig. 1. All hedges on L5 Figure 1: Truth stressers 0.75 0.5 0.25 1 0 iden. be an L-relation between X and Y , !↑, ↓$ be on with hedges ∗X and ∗Y . Then alois connection with hedges ∗X and ∗Y ; as in the proof of Lemma 7 is an L-relation nd Y and we have ↓$ , ↓I!↑,↓$ $ and I = I!↑I ,↓I $.
Element a ∈ L is said to be a fixspmoainllt oflahregdege ∗fairf a∗ =neaar. For two fixpoints a1, a2 rem 3, Theorem 5, and Lemma 7oift∗s,utfhfiecepsroduct a ⊗ b is aMlsoercaufiryxpoin1t of ∗. 0 0 1 I $. We have Recall that an L-set (or fuVzeznyusset)0.7A5in un0iverse X0 is a m1apping A : X → L. For any x ∈ X , A(x) is interpreted asEtharethdeg0r.e7e5 to wh0ich x b0elong0s.7t5o A. For two such L-sets !↑I ,↓I $(x, y) = { 1!x}↑I (y) = Mars 1 0 0.5 0.75 ^ { 1∗X !x}(z) → I(z, y) = I(x, y). JSuaptiutrenr 00 11 00..7755 00..55 ∈X Uranus 0.25 0.5 1 0.25
! NepPtluuntoe 0.125 00.5 11 00 pics A1, A2, the degree of their similarity A1 ≈X A2 ∈ L is defined by
A1 ≈X A2 = ^ A1(x) ↔ A2(x).
x∈X B1 ⊗ B2 = h_B1 ⊗ _B2i ,
e _B2i .
e 2.2
We use factorization of residuated lattices by compatible tolerances as the main tool
in this paper. Regarding factorization of (complete) ordinary lattices we use results of
Cze´dli [
Recall that tolerance on a set X is a relation ∼ which is reflexive and symmetric. Each tolerance induces a covering of its underlying set, called the factor set. This set consists of all maximal blocks of the tolerance, i.e., the maximal subsets whose any two elements are in ∼. In the case of tolerance ∼ on the set X , the factor set is denoted X /∼.
Compatible tolerance relation on a complete lattice L is a tolerance which preserves suprema and infima, i.e., a tolerance ∼ on L is compatible if from a j ∼ b j for any j ∈ J follows W j∈J a j ∼ W j∈J b j and V j∈J a j ∼ V j∈J b j.
For a ∈ L we denote a∼ = W{b ∈ L | a ∼ b},
a∼ = V{b ∈ L | a ∼ b}, [a]∼ = [a∼, (a∼)∼], [a]∼ = [(a∼)∼, a∼] ([a1, a2] denotes the interval {b ∈ L | a1 ≤ b ≤ a2}).
Maximal blocks of ∼ are exactly sets [a]∼ and [a]∼, i.e., it holds L/∼ = {[a]∼ | a ∈ L} = {[a]∼ | a ∈ L}.
Ordering on the set L/∼ is introduced using suprema of maximal blocks and can be equivalently introduced using infima. For blocks B1, B2 ∈ L/∼ we set B1 ≤ B2 iff _B1 ≤ _B2.
The set L/∼ together with this ordering is a complete lattice, which is denoted by L/∼.
Now suppose that L is a residuated lattice. The following results can be found in [
For e ∈ L we denote the e-cut of biresiduum in L by ∼eL or simply ∼e. By definition of e-cuts of fuzzy relations, for any a1, a2 ∈ L, a1 ∼e a2 if and only if a1 ↔ a2 ≥ e. ∼e is a compatible tolerance on L.
We introduce the following simplified notations: ae = a∼e , ae = a∼e , [a]e = [a]∼e , [a]e = [a]∼e . The factor lattice L/∼e will be denoted by L/e.
It holds for any a ∈ L, ae = e ⊗ a, ae = e → a. As a consequence, we obtain the following equalities, which hold for any maximal block B ∈ L/∼e: W B = e → V B, V B = e ⊗ W B.
In [
In the following lemma, we introduce some basic properties of factor residuated
lattices which will be needed later. For more systematic approach, the reader can refer
to [
Lemma 1. For any a1, a2 ∈ L, B1, B2 ∈ L/e it holds
[a1 → a2]e ≤ [a1]e → [a2]e, [a1 → (e → a2)]e = [a1]e → [e → a2]e, _(B1 → B2) = _ B1 → _ B2. 2.3
In this section, we recall some basic notions and notations and state some basic results
on fuzzy concept lattices with hedges and their factorization. We refer the reader to [
Let X , Y be nonempty sets, I : X × Y → L an L-relation between X and Y . The triple hX ,Y, Ii is called a formal L-context, elements of X and Y are called objects and attributes, respectively. hX ,Y, Ii represents a data table which assigns to each x ∈ X and y ∈ Y a truth degree I(x, y) ∈ L to which object x has the attribute y.
For a hedge ∗X on L and L-set A ∈ LX of objects we define an L-set A↑ ∈ LY of attributes by
x∈X
A↑(y) = ^ (A(x)∗X → I(x, y)) .
Similarly, for any hedge ∗Y and L-set B of attributes we define an L-set B↓ of objects by
B↓(x) = ^ (B(y)∗Y → I(x, y)) .
y∈Y
The following lemma summarizes basic properties of mappings ↑ and ↓ [
Next we set
B(X ∗X ,Y ∗Y , I) = {hA, Bi ∈ LX × LY | A↑ = B, B↓ = A}.
We define a partial ordering on B(X ,Y, I) by hA1, B1i ≤ hA2, B2i iff A1 ≤ A2 (10) (11) (12) (13) (14) (15) (or, equivalently, B2 ≤ B1). B(X ∗X ,Y ∗Y , I) with this ordering is a complete lattice, called an L-concept lattice induced by hX ,Y, Ii and hedges ∗X , ∗Y .
Elements hA, Bi of B(X ∗X ,Y ∗Y , I) are called formal concepts, for each formal concept hA, Bi, A is called its extent, B intent. Formal concepts are interpreted as concepts/clusters hidden in the data table. Namely, the conditions A↑ = B and B↓ = A say that B is the collection of all attributes shared by all objects (for which it is very true that they are) from A, and A is the collection of all objects sharing all attributes (for which it is very true that they are) from B.
The main idea of adding hedges to fuzzy concept lattices is that using hedges, one
can affect the size of concept lattices. Namely, if we choose both ∗X , ∗Y to be identities,
we obtain an ordinary fuzzy concept lattice. Other choices lead to smaller concept
lattices. For example, if both ∗X , ∗Y are globalizations then the generated concept lattice
consists of so called crisply generated formal concepts [
Now we recall the parametrized concept lattice factorization method, as introduced
in [
As we mentioned in Introduction, factorization represents another attempt to reduce
the size of fuzzy concept lattice. In this method, user choses a degree e ∈ L to which
he/she considers two different concepts to be similar. Factorizing-out similar concepts
by a tolerance relation induced by e a smaller lattice is obtained. This lattice do not
preserve information on differences between similar concepts. Reader can refer [
We introduce a similarity relation ≈ on the set B(X ,Y, I) of all formal concepts of hX ,Y, Ii by hA1, B1i ≈ hA2, B2i = A1 ≈X A2 (17) (see (4)).
hA1, B1i ≈ hA2, B2i is called the degree of similarity of formal concepts hA1, B1i and hA2, B2i. ≈ is known to be a fuzzy equivalence on B(X ,Y, I).
Since ≈ is a fuzzy equivalence on B(X ,Y, I) then, for any user-chosen threshold e ∈ L, the e-cut e≈ is a (crisp) tolerance relation (“being similar to degree at least e”) on B(X ,Y, I). This tolerance is compatible with the lattice structure on B(X ,Y, I).
Maximal blocks of e≈ are exactly intervals [hA, Bi]e≈ (or, equivalently, intervals [hA, Bi]e≈, see (6)), and the factor set B(X ,Y, I)/e≈ together with the ordering given by (7) is a complete lattice.
This result can also be generalized to fuzzy concept lattices with hedges. First we
show some properties of the fuzzy equivalence ≈X (resp. ≈Y ) on LX (resp. LY ) with
connection to functions ↑ and ↓ [
For a concept lattice B(X ∗X ,Y ∗Y , I), similarity of concepts is defined as above, as well as its e-cut, used for factorization. The factor set B(X ∗X ,Y ∗Y , I)/e≈ together with the ordering given by (7) is again a complete lattice. The structure of maximal blocks of e≈ on B(X ∗X ,Y ∗Y , I) is given by the following lemma.
Lemma 4. For hA, Bi ∈ B(X ,Y, I) we have 1. hA, Bie≈ = h(e → A)↑↓, (e ⊗ B)↓↑i, 32.. hhAA,, BBiiee≈≈ == (h((heA⊗, BAi)e↑≈↓,)(ee )→e≈B,)↓↑i,
e≈ 4. hA, Bie≈ = ((hA, Bie≈) ≈)e≈. 3 3.1
The first main result of this paper concerns introducing a hedge on the factor residuated lattice L/e induced by a hedge on the original residuated lattice L.
Suppose that ∗ is a hedge on residuated lattice L and e ∈ L is its fixpoint, i.e., e∗ = e. We define a new unary operation ∗e (or, simply, ∗ if e and underlying residuated lattice are obvious) on L/e by setting for any B ∈ L/e,
B∗e = h _ B ∗i e .
(18)
We have the following result for the new operation ∗e:
Theorem 1. If e ∈ L is a fixpoint of the hedge ∗ then the operation ∗e on L/e is a hedge.
Proof. Let 1 ∈ L and 1 ∈ L/e be unite elements. We have 1 = [
Now let B ∈ L/e. Then
B∗e = h _ B ∗i e ≤ h_ Bi = B, e which proves condition (ii).
To prove condition (iii) we use Lemma 1 and obtain for B1, B2 ∈ L/e, (B1 → B2)∗e = h _(B1 → B2) ∗i = h _ B1 → _ B2 ∗i e ≤
e h _ B1 ∗i e → _ B2 ∗i
e ≤ h _ B2 ∗i = e ≤
h _ B1 ∗ = B∗1e → B∗2e .
→
Let B ∈ L/e. To prove the equality B∗e = B∗e∗e we show that infima of both sides are equal. Denote W B = a. We have V B∗e = e ⊗ a∗ and V B∗e∗e = e ⊗ (e → e ⊗ a∗)∗. Now, from condition (iii) for hedges and from the fact that e ⊗ a∗ is a fixpoint of ∗ (both e and a∗ are fixpoints) we obtain ^ B∗e∗e ≤ e ⊗ (e∗ → (e ⊗ a∗)∗) = e ⊗ (e → e ⊗ a∗) = ^ B∗ . e The opposite inequality V B∗e ≤ V B∗e∗e follows from (e → e ⊗ a∗)∗ ≤ e → e ⊗ a∗ by multiplying both sides by e. This proves the remaining condition (iv) for hedges. 3.2
In this section, we present our second main result: the factorized L-concept lattice B(X ∗X ,Y ∗Y , I)/e≈ is isomorphic to an L/e-concept lattice, constructed from a formal L/e-context, which is easily computable from the original formal L-context hX ,Y, Ii.
For any L-set A ∈ LX we shall use the symbols Ae, Ae, [A]e, [A]e as before, where e is identified with the constant mapping x 7→ e. We have Ae, Ae ∈ LX , [A]e, [A]e ∈ (LX )/e.
In what follows, we shall not distinguish between sets LX /e and (L/e)X and their
elements. For example, we can consider [A]e as an element of (L/e)X , having [A(x)]e =
[A]e(x) ∈ L/e, for any x ∈ X (see [
For a formal context hX ,Y, Ii, the L-relation I is a mapping I : X × Y → L. Using
results from [
Let hX ,Y, Ii be a formal context, ∗X , ∗Y hedges, e ∈ L a fixed threshold. We consider a new formal L/e-context hX ,Y, [I]ei. Using results of previous section, we introduce two thresholds ∗eX , ∗Ye on the factor residuated lattice L/e such that e is their common e e fixpoint. Then we construct the concept lattice B(X ∗X ,Y ∗Y , [I]e).
When the underlying residuated lattice and e are obvious, we also denote the thresholds ∗eX , ∗Ye simply by ∗X , ∗Y . Since there will be no possibility of confusion, we also denote the formal-context-defining operators with respect to the formal context hX ,Y, [I]ei and hedges ∗eX , ∗Ye again by ↑, and ↓.
Lemma 5. For any A¯ ∈ LX /e with A = W A¯ it holds A¯↑ = [A↑]e. For any B¯ ∈ LY /e with B = W B¯ it holds B¯↓ = [B↓]e.
Proof. From basic properties of blocks of compatible tolerances in residuated lattices and from (11) we obtain
A¯↑(y) = ^ A¯∗eX (x) → [I]e(x, y) = x∈X x∈X x∈X " = ^ A¯∗eX (x) → [e → I(x, y)]e = = ^ [A∗X (x)]e → [e → I(x, y)]e =
x∈X = ^ [A∗X (x) → (e → I(x, y))]e =
x∈X = ^ [e → (A∗X (x) → I(x, y))]e =
x∈X = ^ [A∗X (x) → I(x, y)]e = ^ (A∗X (x) → I(x, y)) #e
= =
x∈X = [A↑(y)]e. The second statement follows by duality.
Lemma 6. For any A¯ ∈ LX /e, if A ∈ A¯ then A↑ ∈ A¯↑. For any B¯ ∈ LY /e, if B ∈ B¯ then B↓ ∈ B¯↓.
Proof. This is a simple consequence of Lemma 5. If A ∈ A¯ then A ≤ W A¯ and A ≈X W A¯ ≥ e. Hence A↑ ≥ (W A¯)↑ (Lemma 2, part 2) and A↑ ≈Y (W A¯)↑ ≥ e∗X = e (Lemma 3). Thus, A↑ ∈ [(W A¯)↑]e = A¯↑ (Lemma 5). The second statement can be proved similarly. Lemma 7. For hA¯, B¯i ∈ B(X ∗X ,Y ∗Y , [I]e), (W B¯)↓ is the least fixpoint of ↑↓ in A¯. Proof. Denote B0 = W B¯, A0 = B↓0. First we show that A0 is a fixpoint of ↑↓. The element A↑0 is a fixpoint of ↓↑ (Lemma 2, part 5). We have B∗Y ≤ A↑0 (Lemma 2, part 1) and 0 A↑0 ≤ B0 (Lemma 6, applied twice). Hence for fixpoint A↑↓ of ↑↓ we obtain (using 0 Lemma 2, part 2), B↓0 ≤ A↑↓ ≤ B∗0Y ↓. But from Lemma 2, part 3, we have B↓0 = B∗0Y ↓, 0 which shows that A0 is a fixpoint of ↑↓.
Now from antitony of ↑ and ↓ (Lemma 2, part 2) we have for any fixpoint A ∈ A¯: A ≥ V A¯, A↑ ≤ (V A¯)↑ ≤ B0 (Lemma 6), which leads to A0 ≤ A↑↓ = A. Lemma 8. For every hA¯, B¯i ∈ B(X ∗X ,Y ∗Y , [I]e), the set F(hA¯, B¯i) of all hA, Bi from B(X ∗X ,Y ∗Y , I) such that A ∈ A¯, is a maximal block of e≈ (i.e., F(hA¯, B¯i) belongs to B(X ∗X ,Y ∗Y , I)/e≈).
Proof. According to Lemma 7, A0 = (W B¯)↓ is the least fixpoint of ↑↓ in A¯. From Lemma 5 we have e → A0 = W A¯ and (e → A0)↑↓ = A1, where A1 is the greatest fixpoint of ↑↓ in A¯. According to Lemma 6, A1 ∈ A.
¯
It remains to be shown (Lemma 4) that A0 = (e ⊗ A1)↑↓ ∈ A¯. We have (W A¯)∗X ≤ A1 ≤ W A¯ (Lemma 2, part 1) and from Lemma 2, parts 2, 3, the intent B1 = A↑1 is equal to (W A¯)↑. Hence, W B¯ = e → B1 (Lemma 5) and (e → B1)↓↑ is the greatest intent of B(X ∗X ,Y ∗Y , I) from B¯. According to Lemma 4, the corresponding extent is equal to A0. Applying Lemma 6 now completes the proof.
Lemma 9. For any maximal block K = [hA0, B0i, hA1, B1i] ∈ B(X ∗X ,Y ∗Y , I)/e≈ there is exactly one formal concept G(K) = hA¯, B¯i ∈ B(X ∗X ,Y ∗Y , [I]e) such that V A¯ ≤ A0, A1 ≤ W A¯. It holds A¯ = [A0]e.
Proof. Since A0 e≈ A1 then there exists a maximal block A0 ∈ LX /e such that A0 ∈ A0, A1 ∈ A0. From Lemma 6 we have A0 ∈ A0↑↓, A1 ∈ A0↑↓. This gives existence of at least one hA¯, B¯i with desired properties.
Now suppose that hA¯, B¯i ∈ B(X ∗X ,Y ∗Y , [I]e) is such that V A¯ ≤ A0, A1 ≤ W A¯. The element (W B¯)↓ is the least fixpoint of ↑↓ in A¯ (Lemma 7). Hence, (W B¯)↓ = A0 (K is a maximal block). From Lemma 5 we have A¯ = [A0]e which proves the uniqueness of A¯ as well as the desired equality.
Lemmas 8 and 9 give us mapping F : B(X ∗X ,Y ∗Y , [I]e) → B(X ∗X ,Y ∗Y , I)/e≈ and mapping G : B(X ∗X ,Y ∗Y , I)/e≈ → B(X ∗X ,Y ∗Y , [I]e) which are obviously mutually inverse. Using mapping F, we state our main result: Theorem 2. Mapping F is an isomorphism of lattices.
Proof. It remains to be shown that F and G are morphisms of ordered sets. For two elements hA¯, B¯i, hC¯, D¯ i ∈ B(X ∗X ,Y ∗Y , [I]e), denote F(hA¯, B¯i) = [hA0, B0i, hA1, B1i] and, similarly, F(hC¯, D¯ i) = [hC0, D0i, hC1, D1i] (intervals taken in B(X ∗X ,Y ∗Y , I)).
If hA¯, B¯i ≤ hC¯, D¯ i then W A¯ ≤ WC¯, from which and from Lemma 7 it follows B1 = (W A¯)↑ ≥ (WC¯)↑ = D1. This means [hA0, B0i, hA1, B1i] ≤ [hC0, D0i, hC1, D1i].
To prove the opposite we start with A0 ≤ C0. This and Lemma 5 give W A¯ = e → A0 ≤ e → C0 = WC¯, which finishes the proof. 4
The two main results of this paper can be interpreted as follows. If we are trying to reduce the complexity of some concept lattice with hedges by factorization, then we are, in fact, constructing another concept lattice with hedges, which is built over a data table with values in some factorized residuated lattice. Thus, the problem of factorization of concept lattice by similarity is replaced with the problem of factorization of the used set of truth degrees (residuated lattice) which indicate the similarity levels.
This paper extends our previous results from [
There is even more general approach (“Generalized concept lattice”, [