=Paper=
{{Paper
|id=Vol-162/paper-1
|storemode=property
|title=Every Concept Lattice With Hedges Is Isomorphic To Some Generalized Concept Lattice
|pdfUrl=https://ceur-ws.org/Vol-162/paper1.pdf
|volume=Vol-162
|dblpUrl=https://dblp.org/rec/conf/cla/Krajci05
}}
==Every Concept Lattice With Hedges Is Isomorphic To Some Generalized Concept Lattice==
https://ceur-ws.org/Vol-162/paper1.pdf
Every
Every Concept
Concept Lattice
Lattice With
With Hedges
Hedges
Is Isomorphic To Some
Is Isomorphic To Some
?
Generalized
Generalized Concept
Concept Lattice
Lattice ?
Stanislav Krajči
Stanislav Krajči
krajci@science.upjs.sk
Institute of
Institute of Computer
Computer Science,
Science, Faculty
Faculty of
of Science,
Science,
UPJŠ Košice,UPJ
Slovakia krajci@science.upjs.sk
Š Košice, Slovakia
Abstract. We show the relationship between two different types of com-
mon platforms of till known fuzzifications of a concept lattice, namely
that the notion of a concept lattice with hedges is a special case of our
generalized concept lattice.
1 Introduction
There are some approaches to fuzzify (i. e. generalize for fuzzy case too) the
classical Ganter-Wille construction of concept lattice. If we omit the (maybe
slightly naive) attempt done by Burusco & Fuentes-Gonzalez ([6]), the first ap-
proach, which was theoretically and practically well developed, was given by
Bělohlávek ([1]) and Pollandt ([11]). It use (L-)fuzzy subsets of objects and (L-
)fuzzy subsets of attributes. The another approach, so-called one-sided fuzzy
concept lattice was invented independently by Ben Yahia & Jaoua ([5]), by
Bělohlávek et al. ([4]) and by the author ([8]). It considers fuzzy subsets of at-
tributes but ordinary/classical/crisp subsets of objects (or vice versa). Because
there is no inclusion between these two fuzzy approaches the natural asking for
some common platform of both had arose.
We know about two such generalizations. One of them was shown by Bělohlá-
vek et al. ([3] and partially in [2]) and it uses so-called hedges (or truth-stressers)
(details below). The second one was given by author ([9]) and its idea is to
separate between the ranges of fuzzy sets of objects and fuzzy sets of attributes
(again details below). Till now it seemed that these two generalizing approaches
are not compatible, but in this paper we try to show that the first is contained
in the second.
2 A generalized concept lattice
Let us shortly recall a notion of a generalized concept lattice given by the author.
All these results are proven in [9] (and/or in [10]).
Let P be a poset, C and D be complete lattices. Let • : C × D → P be
monotone and left-continuous in both their arguments, i.e.
?
Partially supported by grant 1/0385/03 of the Slovak grant agency VEGA.
Radim Bělohlávek, Václav Snášel (Eds.): CLA 2005, pp. 1–9, ISBN 80–248–0863–3.
2 Stanislav Krajči
1a) c1 ≤ c2 implies c1 • d ≤ c2 • d for all c1 , c2 ∈ C and d ∈ D.
1b) d1 ≤ d2 implies c • d1 ≤ c • d2 for all c ∈ C and d1 , d2 ∈ D.
2a) If c • d ≤ p holds for d ∈ D, p ∈ P and for all c ∈ X ⊆ C, then
sup X • d ≤ p.
2b) If c • d ≤ p holds for c ∈ C, p ∈ P and for all d ∈ Y ⊆ D, then
c • sup Y ≤ p.
Let A and B be non-empty sets and let R be P -relation on their Cartesian
product, i.e. R : A × B → P .
Define the following mapping % : B D → A C (by S T we understand the set
of all mappings from the set S to the set T ):
If g : B → D then %(g) : A → C is defined as follows:
%(g)(a) = sup{c ∈ C : (∀b ∈ B)c • g(b) ≤ R(a, b)}.
Symmetrically we define the mapping . : A C → B D:
If f : A → C then .(f ) : B → D is defined as follows:
.(f )(b) = sup{d ∈ D : (∀a ∈ A)f (a) • d ≤ R(a, b)}.
Because these two mappings . and % form a Galois connection, it can be
repeated a classical construction of concept lattice. The result of this construc-
tion is called a generalized concept lattice and the following basic theorem on
generalized concept lattice holds (the proofs are in [9] and [10]):
Theorem 1. 1) The generalized concept lattice L is a complete lattice in which
* !!+
^ ^ _
hgi , fi i = gi , % . fi
i∈I i∈I i∈I
and * !! +
_ _ ^
hgi , fi i = . % gi , fi .
i∈I i∈I i∈I
2) Let moreover P have the least element 0P and 0C • d = 0P and c • 0D = 0P
for every c ∈ C and d ∈ D. Then a complete lattice V is isomorphic to L if
and only if there are mappings α : A × C → V and β : B × D → V s.t.
1a) α is non-increasing in the second argument.
1b) β is non-decreasing in the second argument.
2a) α[A × C] is infimum-dense.
2b) β[B × D] is supremum-dense.
3) For every a ∈ A, b ∈ B, c ∈ C, d ∈ D
α(a, c) ≥ β(b, d) if and only if c • d ≤ R(a, b).
This approach is really a generalization of Bělohlávek’s fuzzy concept lattice
and of one-sided fuzzy concept lattice (and, of course, of a classical crisp case).
Isomorphism of Concept Lattice With Hedges 3
3 A concept lattice with hedges
Bělohlávek consider a (complete) residuated lattice L = hL, ∨, ∧, ⊗, →, 0, 1i,
where ⊗ and → are connectives on L which form an adjoint pair, i.e. x ⊗ y ≤ z
iff x ≤ y → z. ⊗ is isotone in both their arguments, → is antitone in the first
argument and isotone in the second one, ⊗ is commutative and x⊗1 = 1⊗x = x.
Moreover he has sets X and Y and an incidence relation I : X × Y → L.
Then he defines the mappings 0 : LX → LY and 00 : LY → LX as follows: If
A ∈ LX and B ∈ LY then
^
A0 (y) = (A(x) → I(x, y))
x∈X
and ^
B 00 (x) = (B(y) → I(x, y)).
y∈Y
The new idea of Bělohlávek (et al.)’s is to modify these definitions in this
way:
↑ ^
A (y) = (A(x)∗X → I(x, y))
x∈X
and
↓ ^
B (x) = (B(y)∗Y → I(x, y)),
y∈Y
where ∗X and ∗Y are so-called hedges on L. A hedge is a function ∗ on L which
fulfills these properties:
1∗ = 1,
a∗ ≤ a,
(a → b)∗ ≤ a∗ → b∗ ,
a∗∗ = a∗ .
(Note that the last one can be rewrite in the form
∗◦∗=∗
where ◦ is the composition of mappings.) Moreover they work with the following
functions:
– For arbitrary A : U → L (U is some universe) define:
bAc = {hu, ai ∈ U × L : a ≤ A(u)}.
– For arbitrary B ⊆ U × L take the function dBe : U → L defined by:
_
dBe(u) = {a ∈ L : hu, ai ∈ B}.
4 Stanislav Krajči
– For arbitrary A : U → L and ∗ : L → L define the function A∗ given
pointwise by:
A∗ (u) = (A(u))∗ .
– For arbitrary B ⊆ U × L and ∗ : L → L define:
B ∗ = {hx, a∗ i : hx, ai ∈ B}.
Then they have taken the set
↑ ↓
B(X ∗X , Y ∗Y , I) = {hA, Bi : A = B, B = A}
of all fixpoints of the pair h↑ , ↓ i and showed that this structure is isomorphic to
the ordinary concept lattice B(X × ∗X [L], Y × ∗Y [L], Ihf,gi ) where
Ag = bdAe↑ c∗X
and
B f = bdBe↓ c∗Y ,
and relation Ihf,gi is given by
hhx, ai, hy, bii ∈ Ihf,gi iff a ⊗ b ≤ I(x, y).
Finally, they have proven this basic theorem for concept lattice with hedges
(we present here only its second part):
Theorem 2. An arbitrary complete lattice hV, ≤i is isomorphic to the complete
lattice B(X ∗X , Y ∗Y , I) iff there are mappings γ : X × ∗X [L] → V and µ : Y ×
∗Y [L] → V s. t.
1a) µ[Y × ∗Y [L]] is infimum-dense.
1b) γ[X × ∗X [L]] is supremum-dense.
2)
γ(x, a) ≤ µ(y, b) if and only if a ⊗ b ≤ I(x, y).
4 A few observations
We add some small, but useful assertions about these notions:
Lemma 1. Every hedge is monotonous, i. e. a ≤ b implies a∗ ≤ b∗ .
Proof. By properties of a hedge we obtain: a ≤ b iff 1 ⊗ a ≤ b iff 1 ≤ a → b iff
1 = a → b, which implies 1 = (a → b)∗ ≤ a∗ → b∗ , and then a∗ = 1 ⊗ a∗ ≤ b∗ .
Lemma 2. For every hedge ∗ if A ⊆ ∗[L] then sup A ∈ ∗[L].
Proof. For every a ∈ A we know a ≤ sup A, and then (from the previous lemma)
a = a∗ = (sup A)∗ . It means that (sup A)∗ is an upper bound of A, which implies
sup A ≤ (sup A)∗ . But it follows sup A = (sup A)∗ , i. e. sup A ∈ ∗[L].
Isomorphism of Concept Lattice With Hedges 5
Lemma 3. The function b·c is monotonous.
Proof. If A1 , A2 : U → L and A1 ≤ A2 , then obviously bA1 c = {hu, ai ∈ U × L :
a ≤ A1 (u)} ⊆ {hu, ai ∈ U × L : a ≤ A2 (u)} = bA2 c.
Lemma 4. The function d·e is monotonous.
W
Proof. If B1 ⊆ B2 W⊆ U × L, then for all u ∈ U we have clearly dB1 e(u) = {a ∈
L : hu, ai ∈ B1 } = {a ∈ L : hu, ai ∈ B2 } = dB2 e(u).
Lemma 5. For arbitrary A : U → L it is true that dbAce = A.
W W
Proof. dbAce(u) = {a ∈ L : hu, ai ∈ bAc} = {a ∈ L : a ≤ A(u)} = A(u).
5 Relationship between these two approaches
We can see that the basic theorem for concept lattice with hedges and the basic
theorem for our generalized concept lattice are very similar. And it is suspicious.
So take such special case of our generalized concept lattice given by the following
table:
general special
P L
A Y
B X
C ∗Y [L]
D ∗X [L]
• ⊗
R:A×B →P I :X ×Y →L
Then our definitions can be rewritten in this form:
If g : X → ∗X [L] then %(g) : Y → ∗Y [L] is defined as follows:
%(g)(y) = sup{c ∈ ∗Y [L] : (∀x ∈ X)c ⊗ g(x) ≤ I(x, y)},
and if f : Y → ∗Y [L] then .(f ) : X → ∗X [L] is defined by:
.(f )(x) = sup{d ∈ ∗X [L] : (∀y ∈ Y )f (y) ⊗ d ≤ I(x, y)}.
And now we will try to prove that such special case of generalized concept
lattice is isomorphic to the lattice from [3]:
Theorem 3. The lattices L = L(X (∗X [L]), Y (∗Y [L]), I) and B = B(X×∗X [L], Y ×
∗Y [L], Ihf,gi ) are isomorphic and the isomorphisms are
Φ(hg, f i) = hbgc, bf ci
and
Ψ (hS, T i) = hdSe, dT ei,
where g : X → ∗X [L], f : Y → ∗Y [L], S ⊆ X × ∗X [L], T ⊆ Y × ∗Y [L].
6 Stanislav Krajči
It is enough to prove the following six claims:
Claim 1 If hg, f i ∈ L then Ψ (hg, f i) ∈ B.
Proof. Let hg, f i ∈ L, i. e. g = .(f ) and f = %(g), we want to prove bgc =
bf cg = bdbf ce↓ c∗ = bf ↓ c∗ (because from the lemma 5 we have dbf ce = f ) and
bf c = bgcf = bdbgce↑ c∗ = bg ↑ c∗ (because again dbgce = g), which will mean
Φ(hg, f i) = hbgc, bf ci ∈ B, what we want to show.
By above definitions we obtain:
bf ↓ c∗
= {hx, d∗X i ∈ X × ∗X [L] : hx, di ∈ bf ↓ c},
= {hx, di ∈ X × ∗X [L] : hx, d∗X i ∈ bf ↓ c}, (because ∗X ◦ ∗X = ∗X , we have
d∗X = d for all d ∈ ∗X [L]),
= {hx, di ∈ X × ∗X [L] : d ≤ Vf ↓ (x)},
= {hx, di ∈ X × ∗X [L] : d ≤ y∈Y (f (y)∗Y → I(x, y))},
= {hx, di ∈ X × ∗X [L] : (∀y ∈ Y )(f (y)∗Y ⊗ d ≤ I(x, y))},
= {hx, di ∈ X ×∗X [L] : (∀y ∈ Y )(f (y)⊗d ≤ I(x, y))} (because ∗Y ◦∗Y = ∗Y ,
we have c∗Y = c for all c ∈ ∗Y [L], especially f (y) ∈ ∗Y [L]),
= {hx, di ∈ X × ∗X [L] : d ≤ sup{e ∈ ∗X [L] : (∀y ∈ Y )f (y) ⊗ e ≤ I(x, y)}},
= {hx, di ∈ X × ∗X [L] : d ≤ .(f )(x)},
= {hx, di ∈ X × ∗X [L] : d ≤ g(x)},
= bgc,
So we have bf ↓ c∗ = bgc, and the equality bg ↑ c∗ = bf c can be proven symmetri-
cally.
Claim 2 If hS, T i ∈ B then Φ(hS, T i) ∈ L.
Proof. Let hS, T i ∈ B, i. e. S = T f = bdT e↓ c∗ and T = S g = bdSe↑ c∗ , we
want to prove %(dSe) = dT e and .(dT e) = dSe which will mean Ψ (hS, T i) =
hdSe, dT ei ∈ L, what we want to show.
Firstly we show that for all y ∈ Y we have dT e(y) ∈ ∗Y [L]:
dT e(y)
↑ ∗
= dbdSe c e(y),
= W{a ∈ L : hy, ai ∈ bdSe↑ c∗ },
W
= {a ∈ ∗Y [L] : hy, ai ∈ bdSe↑ c∗ },
∈ ∗Y [L] (because of lemma 2).
Hence by above definitions we obtain for every x ∈ X:
.(dT e)(x)
= sup{d ∈ ∗X [L] : (∀y ∈ Y )dT e(y) ⊗ d ≤ I(x, y)},
= sup{d ∈ ∗X [L] : (∀y ∈ Y )dT e(y)∗Y ⊗ d ≤ I(x, y)} (because ∗Y ◦ ∗Y = ∗Y ,
we have c∗Y = c for all c ∈ ∗Y [L], especially for dT e(y) as we have shown
above),
= sup{d ∈ ∗X [L] : d ≤ y∈Y (dT e(y)∗Y → I(x, y))},
V
Isomorphism of Concept Lattice With Hedges 7
= sup{d ∈ ∗X [L] : d ≤ dT e↓ (x)},
= sup{d ∈ ∗X [L] : hx, di ∈ bdT e↓ c},
= sup{d ∈ ∗X [L] : hx, d∗X i ∈ bdT e↓ c∗ },
= sup{d ∈ ∗X [L] : hx, di ∈ bdT e↓ c∗ } (because ∗X ◦ ∗X = ∗X , we have
d∗X = d for all d ∈ ∗X [L]),
= sup{d ∈ L : hx, di ∈ bdT e↓ c∗ } (the (stronger) condition d ∈ ∗X [L] is
covered by the condition hx, di ∈ bdT e↓ c∗ ),
=Wsup{d ∈ L : hx, di ∈ S},
= {d ∈ L : hx, di ∈ S},
= dSe(x).
So we have .(dT e) = dSe, and the equality %(dSe) = dT e can be proven
symmetrically.
Claim 3 If hg, f i ∈ L then
Φ(Ψ (hg, f i)) = hg, f i.
Proof. Φ(Ψ (hg, f i)) = hdbgce, dbf cei = hg, f i because of lemma 5. (You can see
that assumption hg, f i ∈ L is only formal, we do not need it.)
Claim 4 If hS, T i ∈ B then
Ψ (Φ(hS, T i)) = hS, T i.
Proof. By definition we obtain Ψ (Φ(hS, T i)) = hbdSec, bdT eci, so we want to
prove that bdSec = S and bdT ec = T .
For one inclusion we will need the following observation: Because hS, T i ∈ B,
we have S = T f = bdT e↓ c∗ , i. e. S = bgc∗ for some g : X → ∗X [L].
Using definitions we obtain:
hx, di ∈ bdSec
iff d ≤ dSe(x),
W
iff d ≤ W{e ∈ L : hx, ei ∈ S},
iff d ≤ W{e ∈ L : hx, ei ∈ bgc∗ },
iff d ≤ {e ∈ ∗X [L] : hx, e∗X i ∈ bgc∗ } (because if hx, ei ∈ bgc∗ then e ∈
∗X
∗X [L] and
W e = e ),
iff d ≤ W{e ∈ ∗X [L] : hx, ei ∈ bgc},
iff d ≤ {e ∈ ∗X [L] : e ≤ g(x)} = g(x),
iff hx, di ∈ bgc and d ∈ ∗X [L],
iff hx, d∗X i ∈ bgc∗ and d ∈ ∗X [L],
iff hx, di ∈ bgc∗ (because ∗X ◦ ∗X = ∗X , so d = d∗X for all d ∈ ∗X [L]),
iff hx, di ∈ S.
So we have bdSec = S, and the second equality bdT ec = T can be proven
symmetrically.
Claim 5 Φ is order-preserving.
8 Stanislav Krajči
Proof. Let hg1 , f1 i, hg2 , f2 i ∈ L and hg1 , f1 i ≤ hg2 , f2 i. This inequality means
that g1 ≤ g2 and f1 ≥ f2 (pointwise) and by monotonicity of b·c we obtain bg1 c ⊆
bg2 c and bf1 c ⊇ bf2 c, which implies Φ(hg1 , f1 i) = hbg1 c, bf1 ci ≤ hbg2 c, bf2 ci =
Φ(hg2 , f2 i).
Claim 6 Ψ is order-preserving.
Proof. Let hS1 , T1 i, hS2 , T2 i ∈ B and hS1 , T1 i ≤ hS2 , T2 i. This inequality means
that S1 ⊆ S2 and T1 ⊇ T2 and by monotonicity of d·e we obtain dS1 e ≤ dS2 e
and dT1 e ≥ dT2 e, which implies Ψ (hS1 , T1 i) = hdS1 e, dT1 ei ≤ hdS2 e, dT2 ei =
Ψ (hS2 , T2 i).
Now we have proven that the lattices B and L are isomorphic. Hence we have
this:
Corrolary 1 The lattices L(X (∗X [L]), Y (∗Y [L]), I) and B(X ∗X , Y ∗Y , I) are iso-
morphic.
Or we can say it in another words, that every concept lattice with hedges is
isomorphic to some generalized concept lattice.
6 Conclusions
In this paper we showed that the notion of a generalized concept lattice defined
in [10] contains as a part the notion of a fuzzy concept lattice with hedges. Hence
relationships between all classes of concept lattices mentioned in Introduction
can be depicted in this diagram:
generalized CL
L-fuzzy CL with hedge
@
@
@
@
@
L-fuzzy CL one-sided fuzzy CL
@
@
@
@
@
classical CL
Isomorphism of Concept Lattice With Hedges 9
The inverse question arises how big is distinction between these classes, e. g.
what additional conditions are needed for a generalized concept lattices to be
isomorphic to some fuzzy concept lattice with hedges. Or are these notions the
same?. . .
References
1. R. Bělohlávek: Concept Lattices and Order in Fuzzy Logic, Annals of Pure and
Applied Logic, 128 (2004), 277–298
2. R. Bělohlávek, T. Funioková, V. Vychodil: Galois Connection with Truth
Stressers: Foundation for Formal Concept Analysis of Object-Attribute Data with
Fuzzy Stressers, Journal of IGPL, accepted
3. R. Bělohlávek, V. Vychodil: Reducing the size of fuzzy concept lattices by hedges,
Proceedings of FUZZ-IEEE 2005: The 14th IEEE International Conference on
Fuzzy Systems, 2005, pp. 663-668, [IEEE, ISBN 0780391586, ISSN 10987584,
Catalog Number: 05CH37680]
4. R. Bělohlávek, V. Sklenář, J. Zacpal: Crisply generated fuzzy concepts: reducing
the number of concepts in formal concept analysis, Proc. 5th Int. Conf. on Recent
Advances in Soft Computing, RASC 2004, Nottingham, United Kingdom, 16–
18 December, 2004, pp. 63 (extended abstract); pp. 524–529 (full paper on the
included CD) [ISBN 1-84233-110-8]
5. S. Ben Yahia, A. Jaoua: Discovering knowledge from fuzzy concept lattice. In:
Kandel A., Last M., Bunke H.: Data Mining and Computational Intelligence,
169–190, Physica-Verlag, 2001
6. A. Burusco, R. Fuentes-Gonzalez: The study of L-fuzzy concept lattice, Mathware
& Soft Computing 3(1994), 209–218
7. B. Ganter, R. Wille: Formal Concept Analysis, Mathematical Foundation,
Springer Verlag 1999, ISBN 3-540-62771-5
8. S. Krajči: Cluster based efficient generation of fuzzy concepts, Neural Network
World 13,5 (2003) 521–530
9. S. Krajči: The basic theorem on generalized concept lattice, CLA 2004, Ostrava,
proceedings of the 2nd international workshop, eds. V. Snášel, R. Bělohlávek,
ISBN 80-248-0597-9, 25–33
10. S. Krajči: A generalized concept lattice, Journal of IGPL, accepted
11. S. Pollandt: Datenanalyse mit Fuzzy-Begriffen, in: G. Stumme, R. Wille: Begrif-
fliche Wissensverarbeitung. Methoden und Anwendungen, Springer, Heidelberg
2000, 72–98