Factorization of Concept Lattices with Hedges by Means of Factorization of Residuated Lattices Michal Krupka Dept. Computer Science, Palacký University, Olomouc, Tomkova 40, CZ-779 00, Olomouc, Czech Republic, michal.krupka@upol.cz Abstract. In the first part, we extend our results from a previous paper on fac- torization 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. 1 Introduction Formal concept analysis (FCA) is a popular method for analysis of object-attribute data [11], [9]. Its aim is to process data in a tabular form (describing objects and their at- tributes) and extract interesting clusters, called formal concepts, which correspond to maximal rectangles in the processed data table. These formal concepts form a concept lattice, which represents the main output of the method. 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 consider- ing 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 tol- erance 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 [1] and further improved in [3], see also [2]. In [8], the notion of fuzzy concept lattice with hedges was introduced (see also [4], [5]). It can be viewed as another tool for reducing size of concept lattices. It introduces two additional parameters, called (truth-stressing) hedges, which are unary functions on the scale of truth degrees and can be seen as truth functions of connectives “very c Radim Belohlavek, Sergei O. Kuznetsov (Eds.): CLA 2008, pp. 231–241, ISBN 978–80–244–2111–7, Palacký University, Olomouc, 2008. 232 Michal Krupka true”. Hedges can be used as parameters selecting “important attributes” and “important objects”. Stronger hedges lead to smaller number of extracted concepts. In [6], these two approaches (factorization and hedges) were combined and a method of factorizing fuzzy concept lattices with hedges was introduced. In [17], we dealt with residuated lattices, which are frequently used as structures of truth values in fuzzy logic, and as such are also used in the above papers. We showed (using results of [10] and [18]) that residuated lattices can be factorized by means of a prescribed degree of similarity of truth values. We also stated a general idea of ap- proximate size reduction of fuzzy systems by factorizing the underlying structure of truth values (i.e., a residuated lattice) by a tolerance relation, induced by the user- prescribed degree to which we allow different truth values to be non-distinguishable. We also showed that this general idea is applicable to fuzzy concept lattices: factorized fuzzy concept lattice is in fact isomorphic to another concept lattice, constructed from a data table with values from factor residuated lattice. In this paper, we first generalize our results from [17] to residuated lattices with hedges. We show that any hedge on a residuated lattice induces a hedge on the factorized residuated lattice. The only limitation is that the prescribed similarity degree must be a fixpoint of the used hedge (similar condition appears also in [6]). 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 lat- tice 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 Preliminaries 2.1 Residuated lattices and fuzzy sets 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 [2], [12]. 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 = [0, 1] (unit interval), ∧ and ∨ being minimum and maximum, ⊗ being a left-continuous t-norm with the corresponding →. Factorization of Concept Lattices with Hedges by Means of Factorization of 233 Residuated Lattices Three most important pairs of adjoint operations on the unit interval are: a ⊗ b = max(a + b − 1, 0), Łukasiewicz: (1) a → b = min(1 − a + b, 1), a ⊗ b = min(a, b),  Gödel: 1 if a ≤ b, (2) a→b = b otherwise, a ⊗ b = a · b,  Goguen (product): 1 if a ≤ b, (3) a→b = b a otherwise. Complete residuated lattices on [0, 1] given by (1), (2), and (3) are called standard Łukasiewicz, Gödel, Goguen (product) algebras, respectively. The class of complete residuated lattices include finite structures as well. For in- stance, we can put Ln+1 = {a0 = 0, a1 , . . . , an = 1} ⊆ [0, 1], where a0 < · · · < an are equidistant and ⊗ and → are restrictions of the operations from (1). In this case, the residuated lattice Ln+1 = hLn+1 , min, max, ⊗, →, 0, 1i is called an equidistant Łukasie- wicz chain. 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 (interpre- tations) 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” [13]. 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 . I be an L-relation between X and Y , !↑ , ↓ $ be 1 ion with hedges ∗X and ∗Y . Then 0.75 0.5 Galois connection with hedges ∗X and ∗Y ; 0.25 d as in the proof of Lemma 7 is an L-relation 0 and Y and we have glob. !L1 !2 L !L3 iden. ↓I!↑,↓$ Fig. 1. All hedges on L5 ,↓$ , $ and I = I!↑I ,↓I $ . Figure 1: Truth stressers Element a ∈ L is said to be a fixpoint small oflarge if a∗ = hedge ∗far a. For two fixpoints a1 , a2 near orem 3, Theorem 5, and Lemma 7 it suffices of ∗, the product a ⊗ b is also Mercury 1 of ∗. 0 a fixpoint 0 1 ↓I $ . We have Venus set) Recall that an L-set (or fuzzy 0.75 0 A in universe X0 is a mapping 1 A : X → L. For any ! x ∈ X, A(x) is interpreted as Earth the 0.75 degree to 0 which x 0 belongs0.75to A. For two such L-sets I!↑I ,↓I $ (x, y) = { 1 x}↑I (y) = Mars 1 0 0.5 0.75 ^ ∗X ! Jupiter 0 1 0.75 0.5 { 1 x}(z) → I(z, y) = I(x, y). Saturn 0 1 0.75 0.5 z∈X Uranus 0.25 0.5 1 0.25 Neptune 0.25 0.5 1 0 ! Pluto 1 0 1 0 Table 1: Data table with fuzzy attributes opics 2.4.4 Automatic generation of statements omment on selected topics. 234 Michal Krupka A1 , A2 , the degree of their similarity A1 ≈X A2 ∈ L is defined by ^ A1 ≈X A2 = A1 (x) ↔ A2 (x). (4) x∈X 2.2 Factorization of residuated lattices 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 Czédli [10] and Wille [18]. 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 j∈J a j ∼ j∈J b j and j∈J a j ∼ j∈J b j . W W V V For a ∈ L we denote a∼ = {b ∈ L | a ∼ b}, a∼ = {b ∈ L | a ∼ b}, W V (5) [a]∼ = [a∼ , (a∼ )∼ ], [a]∼ = [(a∼ )∼ , a∼ ] (6) ([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 . (7) 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 [2], [3], where a more general approach is presented, namely sets of fixpoints of L-closure operators are considered in place of residuated lattice L. For e ∈ L we denote the e-cut of biresiduum in L by ∼Le 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] = [a]∼e . The factor lattice L/∼e will be denoted by L/e. e It holds for any a ∈ L, ae = e ⊗ a, ae = e → a. As a consequence, we obtain the equalities, which hold for any maximal block B ∈ L/∼e : B = e → B, W V following B = e ⊗ B. V W In [17] we introduced a structure of residuated lattice on the factor set L/e as fol- lows. For B1 , B2 ∈ L/e we set h_ _ i B1 ⊗ B2 = B1 ⊗ B2 , (8) e h_ _ i B1 → B2 = B1 → B2 . (9) e Factorization of Concept Lattices with Hedges by Means of Factorization of 235 Residuated Lattices Now the set L/e together with elements 0, 1 ∈ L/e and operations ∧, ∨ given by the factor lattice structure and together with operations ⊗, → introduced in (8) and (9) is a complete residuated lattice, which is denoted by L/e. More formally, L/e is equal to the tuple hL/e, ∧, ∨, ⊗, →, 0, 1i. 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 [17]. Lemma 1. For any a1 , a2 ∈ L, B1 , B2 ∈ L/e it holds [a1 → a2 ]e ≤ [a1 ]e → [a2 ]e , (10) [a1 → (e → a2 )]e = [a1 ]e → [e → a2 ]e , (11) _ _ _ (B1 → B2 ) = B1 → B2 . (12) 2.3 Fuzzy concept lattices with hedges 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 [2], [6], [8] for details. 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 A↑ (y) = (A(x)∗X → I(x, y)) . ^ (13) x∈X 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)) . ^ (14) y∈Y The following lemma summarizes basic properties of mappings ↑ and ↓ [4]: Lemma 2. Mappings ↑ and ↓ defined by (13) and (14) satisfy the following properties: 1. A∗X ≤ A↑↓ and B∗Y ≤ B↓↑ ; 2. A1 ≤ A2 implies A↑2 ≤ A↑1 , and B1 ≤ B2 implies B↓2 ≤ B↓1 (antitony); 3. A↑ = A∗X ↑ and B↓ = B∗Y ↓ ; 4. A↑∗Y ≤ A↑↓↑ ≤ A∗X ↑ and B↓∗X ≤ B↓↑↓ ≤ B∗Y ↓ ; 5. A↑↓ = A↑↓↑↓ and B↓↑ = B↓↑↓↑ . Next we set B(X ∗X ,Y ∗Y , I) = {hA, Bi ∈ LX × LY | A↑ = B, B↓ = A}. (15) We define a partial ordering on B(X,Y, I) by hA1 , B1 i ≤ hA2 , B2 i iff A1 ≤ A2 (16) 236 Michal Krupka (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 con- cept hA, Bi, A is called its extent, B intent. Formal concepts are interpreted as con- cepts/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 lat- tices. For example, if both ∗X , ∗Y are globalizations then the generated concept lattice consists of so called crisply generated formal concepts [7]. If ∗X and ∗Y are globaliza- tion and identity (respectively) then B(X ∗X ,Y ∗Y , I) is isomorphic to so-called one-sided concept lattice [15]. Now we recall the parametrized concept lattice factorization method, as introduced in [1], and then mention its generalization to fuzzy concept lattices with hedges. 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 [6], [8] for details on factorization of concept lattices and its generalization to concept lattices with hedges. We introduce a similarity relation ≈ on the set B(X,Y, I) of all formal concepts of hX,Y, Ii by hA1 , B1 i ≈ hA2 , B2 i = A1 ≈X A2 (17) (see (4)). hA1 , B1 i ≈ hA2 , B2 i is called the degree of similarity of formal concepts hA1 , B1 i and hA2 , B2 i. ≈ 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 e [hA, Bi] ≈ , 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 ↓ [6]: Lemma 3. For A1 , A2 ∈ LX and B1 , B2 ∈ LY we have (A1 ≈X A2 )∗X ≤ A↑1 ≈Y A↑2 and (B1 ≈Y B2 )∗Y ≤ B↓1 ≈X B↓2 . 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 Factorization of Concept Lattices with Hedges by Means of Factorization of 237 Residuated Lattices 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 e 1. hA, Bi ≈ = h(e → A)↑↓ , (e ⊗ B)↓↑ i, 2. hA, Biee ≈ = h(e ⊗ A)e↑↓ , (e → e≈ B)↓↑ i, ≈ ≈ 3. hA, Bi = ((hA, Bi )e ≈ ) , e 4. hA, Bie ≈ = ((hA, Bie ≈ ) ≈ )e ≈ . 3 Results 3.1 Factorization of residuated lattices with hedges 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, e h_ ∗ i B∗ = B . (18) e 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 = [1]e and e e 1∗ = ([1]e )∗ = [1∗ ]e = 1, which proves condition (i) for hedges. Now let B ∈ L/e. Then e h_ ∗ i h_ i B∗ = B ≤ B = B, e e which proves condition (ii). To prove condition (iii) we use Lemma 1 and obtain for B1 , B2 ∈ L/e, e h_ ∗ i h_ _ ∗ i (B1 → B2 )∗ = (B1 → B2 ) = B1 → B2 ≤ e e h_ ∗ _ ∗ i h_ ∗ i h_ ∗ i ≤ B1 → B2 ≤ B1 → B2 = e e e e e = B∗1 → B∗2 . e e e Let B ∈ L/e. To prove the equality B∗ = B∗ ∗ we show that infima of both sides V e V e e are equal. Denote B = a. We have B∗ = e ⊗ a∗ and B∗ ∗ = e ⊗ (e → e ⊗ a∗ )∗ . W 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 e e e B∗ ∗ ≤ e ⊗ (e∗ → (e ⊗ a∗ )∗ ) = e ⊗ (e → e ⊗ a∗ ) = B∗ . ^ ^ e e e The opposite inequality B∗ ≤ B∗ ∗ follows from (e → e ⊗ a∗ )∗ ≤ e → e ⊗ a∗ by V V multiplying both sides by e. This proves the remaining condition (iv) for hedges. 238 Michal Krupka 3.2 Factorization of fuzzy concept lattices with hedges 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 [17] for details). For a formal context hX,Y, Ii, the L-relation I is a mapping I : X × Y → L. Using results from [17], we define an L/e-relation [I]e : X ×Y → L/e by [I]e (x, y) = [I(x, y)]e (19) (like before, we do not distinguish between elements of (L/e)X×Y and LX×Y /e). 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]e i. 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 thresh- olds ∗eX , ∗Ye simply by ∗X , ∗Y . Since there will be no possibility of confusion, we also de- note the formal-context-defining operators with respect to the formal context hX,Y, [I]e i and hedges ∗eX , ∗Ye again by ↑ , and ↓ . Lemma 5. For any Ā ∈ LX /e with A = Ā it holds Ā↑ = [A↑ ]e . For any B̄ ∈ LY /e with W B = B̄ it holds B̄↓ = [B↓ ]e . W Proof. From basic properties of blocks of compatible tolerances in residuated lattices and from (11) we obtain e Ā↑ (y) = Ā∗X (x) → [I]e (x, y) = ^ x∈X e Ā∗X (x) → [e → I(x, y)]e = ^ = x∈X [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 = ^ = x∈X " #e ∗X ^ = (A (x) → I(x, y)) = x∈X ↑ = [A (y)]e . Factorization of Concept Lattices with Hedges by Means of Factorization of 239 Residuated Lattices The second statement follows by duality. Lemma 6. For any Ā ∈ LX /e, if A ∈ Ā then A↑ ∈ Ā↑ . For any B̄ ∈ LY /e, if B ∈ B̄ then B↓ ∈ B̄↓ . simple consequence of Lemma 5. If AW∈ Ā then A ≤ Ā and A ≈X Ā ≥ W W Proof. This is a W e. Hence A ≥ ( Ā)↑ (Lemma 2, part 2) and A↑ ≈Y ( Ā)↑ ≥ e∗X = e (Lemma 3). Thus, ↑ A ∈ [( Ā) ] = Ā↑ (Lemma 5). The second statement can be proved similarly. ↑ W ↑e Lemma 7. For hĀ, B̄i ∈ B(X ∗X ,Y ∗Y , [I]e ), ( B̄)↓ is the least fixpoint of ↑↓ in Ā. W Proof. Denote B0 = B̄, A0 = B↓0 . First we show that A0 is a fixpoint of ↑↓. The element W A↑0 is a fixpoint of ↓↑ (Lemma 2, part 5). We have B∗0Y ≤ A↑0 (Lemma 2, part 1) and A↑0 ≤ B0 (Lemma 6, applied twice). Hence for fixpoint A↑↓ 0 of ↑↓ we obtain (using Lemma 2, part 2), B↓0 ≤ A↑↓ 0 ≤ B∗Y ↓ 0 . But from Lemma 2, part 3, we have B↓0 = B∗0Y ↓ , 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↑ ≤ ( Ā)↑ ≤ B0 (Lemma 6), which leads to A0 ≤ A↑↓ = A. V V Lemma 8. For every hĀ, B̄i ∈ B(X ∗X ,Y ∗Y , [I]e ), the set F(hĀ, B̄i) of all hA, Bi from B(X ∗X ,Y ∗Y , I) such that A ∈ Ā, is a maximal block of e ≈ (i.e., F(hĀ, B̄i) belongs to B(X ∗X ,Y ∗Y , I)/e ≈). Proof. According to LemmaW7, A0 = ( B̄)↓ is the least fixpoint of ↑↓ in Ā. From W Lemma 5 we have e → A0 = Ā and (e → A0 )↑↓ = A1 , where A1 is the greatest fixpoint of ↑↓ in Ā. According to Lemma 6, A1 ∈ Ā. It remains to be shown (Lemma 4) that A0 = (e ⊗ A1 )↑↓ ∈ Ā. We have ( Ā)∗X ≤ W A1 ≤ 2, part 1) and from Lemma 2, parts 2, 3, the intent B1 = A↑1 is equal W Ā (Lemma W to ( Ā) . Hence, B̄ = e → B1 (Lemma 5) and (e → B1 )↓↑ is the greatest intent of W ↑ 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 , B0 i, hA1 , B1 i] ∈ B(X ∗X ,Y ∗Y , I)/ e ≈ there one formal concept G(K) = hĀ, B̄i ∈ B(X ,Y , [I] ) such that Ā ≤ A0 , ∗ ∗ e V is exactly X Y A1 ≤ Ā. It holds Ā = [A0 ]e . W 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 hĀ, B̄i with desired properties. Now suppose that hĀ, B̄i ∈ B(X ∗X ,Y ∗Y , [I]e ) is such that Ā ≤ A0 , A1 ≤ Ā. The V W W ↓ W ↓ element ( B̄) is the least fixpoint of ↑↓ in Ā (Lemma 7). Hence, ( B̄) = A0 (K is a maximal block). From Lemma 5 we have Ā = [A0 ]e which proves the uniqueness of Ā 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 in- verse. Using mapping F, we state our main result: 240 Michal Krupka 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 hĀ, B̄i, hC̄, D̄i ∈ B(X ∗X ,Y ∗Y , [I]e ), denote F(hĀ, B̄i) = [hA0 , B0 i, hA1 , B1 i] and, similarly, F(hC̄, D̄i) = [hC0 , D0 i, hC1 , D1 i] (intervals taken in B(X ∗X ,Y ∗Y , I)). If hĀ, B̄i ≤ hC̄, D̄i then Ā ≤ C̄, from which and from Lemma 7 it follows B1 = W W W ↑ W ↑ ( Ā) ≥ ( C̄) = D1 . This means [hA0 , B0 i, hA1 , B1 i] ≤ [hC0 , D0 i, hC1 , D1 i]. To prove the opposite we start with A0 ≤ C0 . This and Lemma 5 give Ā = e → W A0 ≤ e → C0 = C̄, which finishes the proof. W 4 Conclusion 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 [17], where we considered residuated lattices and fuzzy concept lattices without hedges. There is even more general approach (“Generalized concept lattice”, [16]), which contains the notion of fuzzy concept lattice with hedges as a special case [14]. There arises a question whether the method of factorization of concept lattices can be gen- eralized to this case. This question is open; the main obstacle seems to be that in this general framework there is no known natural notion of similarity of concepts. References 1. Belohlavek, R.: Similarity relations in concept lattices. J. Logic Comput., 10 (6), 823–845 (2000) 2. Belohlavek, R.: Fuzzy Relational Systems, Foundations and Principles. Kluwer, New York (2002) 3. Belohlavek, R. et al.: Fast factorization by similarity in formal concept analysis of data with fuzzy attributes. J. Comput. Syst. Sci., 73 (6), 1012–1022 (2007) 4. Belohlavek, R., Funiokova, T., Vychodil, V.: Galois connections with hedges. In: Yingming Liu, Guoqing Chen, Mingsheng Ying (Eds.): Fuzzy Logic, Soft Computing & Computational Intelligence: Eleventh International Fuzzy Systems Association World Congress (Vol. II), 2005, pp. 1250–1255. Tsinghua University Press and Springer, ISBN 7–302–11377–7. 5. Belohlavek, R., Outrata, J. and Vychodil, V.: Thresholds and shifted attributes in formal con- cept analysis of data with fuzzy attributes. In: Schärfe, H., Hitzler, P., Øhrstrøm, P. (eds.) Lec- ture Notes in Artificial Intelligence, 4068, pp. 117–130. Springer, Berlin/Heidelberg (2006) 6. Belohlavek, R., Outrata, J., Vychodil, V.: Fast Factorization by Similarity of Fuzzy Concept Lattices with Hedges. Int. J. Found. Comput. Sci. 19(2): 255-269 (2008) 7. Belohlavek, R., Sklenář, V., Zacpal, J.: Crisply generated fuzzy concepts. In: B. Ganter and R. Godin (Eds.): ICFCA 2005, Lecture Notes in Computer Science 3403, pp. 268–283, Springer-Verlag, Berlin/Heidelberg, 2005. Factorization of Concept Lattices with Hedges by Means of Factorization of 241 Residuated Lattices 8. Belohlavek, R., Vychodil, V.: Reducing the size of fuzzy concept lattices by hedges. In: FUZZ-IEEE 2005, The IEEE International Conference on Fuzzy Systems, May 22–25, 2005, Reno (Nevada, USA), pp. 663–668. 9. Carpineto, C., Romano, G.: Concept Data Analysis. Theory and Applications. J. Wiley (2004). 10. Czédli, G.: Factor lattices by tolerances. Acta Sci. Math., 44, 35–42 (1982) 11. Ganter, B., Wille, R.: Formal Concept Analysis. Mathematical Founda- tions. Springer- Verlag, Berlin (1999). 12. Hájek, P.: Metamathematics of Fuzzy Logic. Kluwer, Dordrecht (1998) 13. Hájek, P.: On very true. Fuzzy sets and systems 124(2001), 329–333. 14. Krajči, S.: Every concept lattice with hedges is isomorphic to some generalized concept lat- tice. In: R. Belohlavek, V. Snasel (Eds.), Proceedings of CLA 2005: The 3rd international conference on Concept Lattices and Their Applications, Olomouc, Czech Republic, Septem- ber 2005, pp. 1–9 15. Krajči, S.: Cluster based efficient generation of fuzzy concepts. Neural Network World 5(2003), 521–530. 16. Krajči, S.: The basic theorem on generalized concept lattice. In: R. Belohlavek, V. Snasel (eds.), CLA 2004, Ostrava, Proceedings of the 2nd international workshop, pp. 25–33 17. Krupka, M.: Factorization of residuated lattices with application to concept lattices. In: R.Trappl (ed.) Cybernetics and Systems 2008, pp. 21–25. Austrian Society for Cybernetic Studies, Vienna (2008) 18. Wille, R.: Complete tolerance relations of concept lattices. In: G. Eigenthaler et al. Contri- butions to General Algebra, Vol. 3, pp. 397–415, Hölder-Pichler-Tempsky, Wien (1985)