=Paper=
{{Paper
|id=Vol-433/paper-23
|storemode=property
|title=Factorization of Concept Lattices with Hedges by Means of Factorization of Residuated Lattices
|pdfUrl=https://ceur-ws.org/Vol-433/paper19.pdf
|volume=Vol-433
}}
==Factorization of Concept Lattices with Hedges by Means of Factorization of Residuated Lattices==
https://ceur-ws.org/Vol-433/paper19.pdf
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)