The aim of this paper is to define so-called proto-fuzzy concepts, as a base for generating different types of one-sided fuzzy concept lattices. Fuzzy formal context is a triple of a set of objects, a set of attributes and a fuzzy binary relation over a complete residuated lattice, which determines the degree of membership of each attribute to each object. A proto-fuzzy concept is a triple of a subset of objects, a subset of attributes and a value as the best common degree of membership of all pairs of objects and attributes from the above-mentioned sets to the fuzzy binary relation. Then the proto-fuzzy concepts will be found with a help of cuts and projections to the object-values or attribute-values plains of our fuzzy-context.
The table is a concrete example of fuzzy formal context. Students represent
objects, subjects represent attributes and corresponding valuations represent
values assigned to every object–attribute pair by fuzzy binary relation over the
set {1, 2, 3, 4, 5} (1 – best, . . . , 5 – worst). Goal is to find groups of students
similar by their studying results of all subjects, or to find subsets of subjects
similar by results of all students. In other words to find pairs of classical subset
of objects or attributes and fuzzy subset of attributes or objects. Similarity is
determined by fuzzy subsets. Those pairs are called one-sided fuzzy concepts
([
The starting point of this paper is to define so-called proto-fuzzy concepts, triples made of a subset of objects, a subset of attributes and a value from the set of degrees of membership forming fuzzy binary relation, which is not exceeding for any object-attribute pair of cartesian product of object and attribute subsets meant above. Every element of the triple is “maximal” opposite to other two elements. Proto-fuzzy concepts can be taken as a “base structure unit” of one-sided fuzzy concepts. If values in the table are taken as columns tall as degree of membership of subsistent object–attribute pair to fuzzy binary relation, then proto-fuzzy concepts could be taken as a maximal “sub-blocks” of satisfying triples object-attribute-value of the 3D block representing fuzzy context. Examples of some proto-fuzzy concepts of the example will be shown in section 3. 2
Definition 1. A formal context is a triple hO, A, Ri consists of two sets O, the set of objects, and A, the set of attributes, and a relation R ⊆ O × A. Definition 2. A fuzzy formal context is a triple hO, A, ri consists of two sets O, the set of objects, and A, the set of attributes, and r is fuzzy subset of O × A, mapping from O × A to L, where L is a lattice.
In the sense of simplicity of an idea “fuzzy” will be used instead of L-fuzzy. Definition 3. For every l ∈ L define mappings ↑l: P(O) → P(A) and ↓l: P(A) → P(O): For every subset O ⊆ O put
↑l (O) = {a ∈ A : (∀o ∈ O)r(o, a) ≥ l} and for all A ⊆ A put
↓l (A) = {o ∈ O : (∀a ∈ A)r(o, a) ≥ l}.
Lemma 1. For all l ∈ L the pair (↑l, ↓l) forms a Galois connection between the power-set lattices P(O) and P(A).
Definition 4. Let hO, A, ri be a fuzzy context. A pair hO, Ai is called an lconcept iff ↑l (O) = A, and ↓l (A) = O, hence the pair is a concept in a classical context hO, A, Rli, that
Rl = {(o, a) ∈ O × A : r(o, a) ≥ l}.
Context hO, A, Rli is called an l-cut. The set of all concepts in an l-cut will be denoted Kl. student in each subject at least of the value l? For example a concept hO, Ai from K2 represents the group O of students, that every subject of the set A is
By exploring all l-cuts for such l ∈ L, it can be seen that some l-concepts are equal for different l ∈ L. But information that Eve and Mary are successful in all subjects for the value 2 is not complete and not as useful as information that they are successful for 1. This information is not complete, “closed”.
Two interesting properties will be shown in following lemmas and theorems.
It will be a continuation of the knowledge of the paper [
.
Lemma 2. Let l1, l2 ∈ L that l1 ≤ l2. ↑l1 (O) ⊇↑l2 (O) for every O ⊆ O and
{a ∈ A : (∀o ∈ O)r(o, a) ≥ l1} ⊇ {a ∈ A : (∀o ∈ O)r(o, a) ≥ l2}.
Hence ↑l1 (O) ⊇↑l2 (O). (O) and ↓l1 (A)∩ ↓l2 (A) =↓l1∨l2 (A).
Lemma 3. Let O ⊆ O
, A ⊆ A and l1, l2 ∈ L. Then ↑l1 (O)∩ ↑l2 (O) =↑l1∨l2
Proof. If a ∈↑l1 (O)∩ ↑l2 (O) then for all o ∈ O is r(o, a) ≥ l1 and r(o, a) ≥ l1. It follows from above that for every o ∈ O is r(o, a) ≥ l1 ∨ l2 and so a ∈↑l1∨l2 (O). Hence ↑l1 (O)∩ ↑l2 (O) ⊆↑l1∨l2 (O). The lemma 6 implies that ↑l1∨l2 (O) ⊆↑l1 (O) and ↑l1∨l2 (O) ⊆↑l2 (O). It implies that ↑l1∨l2 (O) ⊆↑l1 (O)∩ ↑l2 (O). From the both inclusions implies that ↑l1∨l2 (O) =↑l1 (O)∩ ↑l2 (O). The proof for ↓ is tu tu l1 ≤ l ≤ l2 then hO, Ai ∈ Kl.
Theorem 1. Let l1, l2 ∈ L and hO, Ai ∈ Kl1 ∩ Kl2 . Then for all l ∈ L, if
Theorem 2. Let l1, l2 ∈ L and hO, Ai ∈ Kl1 ∩ Kl2 . Then hO, Ai ∈ Kl1∨l2 . Proof. The lemma 7 implies
tu tu 3
Proto-fuzzy concepts and their usage Definition 5. Triples hO, A, li ∈ P(O) × P(A) × L such that hO, Ai ∈ S concepts. The set of all proto-fuzzy concepts will be denoted KP .
k∈L Kk and l = sup{k ∈ L : hO, Ai ∈ Kk} will be called proto-fuzzy For our example will proto-fuzzy concept hO, A, li means the group of students O, whose best common result of all subjects from the set A is l. In the following tables are some proto-fuzzy concepts of our example.
{F, J, A, N, M, E, L, D, P, T}
{F, J, A, P, E, M} {Sl, Ge, Gr, En, Ch, Ae, Hi} {Sl, Bi, Ae , Gr, En , Hi} 3 2 {F, M, E, L} {Ma, Ph} 1
The set of all proto-fuzzy concepts will be used for creating one-sided fuzzy concepts with help of mappings defined below. Mappings will determine which side will be fuzzy.
Definition 6. Let O ⊆ O be an arbitrary set of objects. The set
KOP = {hA, li ∈ P(A) × L : (∃B ⊇ O)hB, A, li ∈ KP } will be called the contraction of the set of proto-fuzzy concepts subsistent to the set O.
Definition 7. Define mappings ⇑: 2O → LA, ⇓: LA → 2O in the following way: For every subset O of objects and for every fuzzy-subsets of attributes put
⇑ (O)(a) = sup{l ∈ L : (∃hA, li ∈ KOP)a ∈ A} ⇓ (Ae) = [ {O ⊆ O : (∀a ∈ A)(∃hA, li ∈ KOP)a ∈ A & l ≥ Ae(a)}. Lemma 4. Let O and A are arbitrary subsets of objects and attributes respectively, and l be an arbitrary value of L such that for every object o of the set O ⊇ O, A ⊇ A and value k ∈ L such that k ≥ l and hO, A, ki ∈ KP . O and for every attribute a of the set A, R(o, a) ≥ l. Then there exist subsets
A =↑l (O) = {a ∈ A : (∀o ∈ O)r(o, a) ≥ l} ⊇ A.
Then
O =↓l (A) =↓l (↑l (O)) it implies that ↓l (↑l (O)) ⊇ O and hence hO, Ai ∈ Kl. If and from the fact that for every l ∈ L the pair (↑l, ↓l) forms a Galois connection, the theorem 9 implies that hO, Ai ∈ Kk and so k = sup{m ∈ L : hO, Ai ∈ Km}
hO, A, ki ∈ KP . k ≥ l.
Lemma 5. Let l ∈ L, O1, O2 ⊆ O and hA1, l1i ∈ KOP1 , hA2, l2i ∈ KO2 P A1 ∩ A2 6= ∅ and l1 ∧ l2 ≥ l. Then exists hA, ki ∈ KO1∪O2 that A ⊇ A1 ∩ A2 and P that
hA2, l2i ∈ KOP2 it means that (∀o ∈ O1)(∀a ∈ A1)r(o, a) ≥ l1.
(∀o ∈ O2)(∀a ∈ A2)r(o, a) ≥ l2.
Hence hence The lemma 13 implies that
(∀o ∈ O1 ∪ O2)(∀a ∈ A1 ∩ A2)r(o, a) ≥ l1 ∧ l2 ≥ l. (∃O ⊇ O1 ∪ O2)(∃A ⊇ A1 ∩ A2)(∃k ∈ L : k ≥ l)hO, A, ki ∈ K
P
P hA, ki ∈ KO1∪O2 . tu tu there exist A ⊆ A and l ≥ l1 ∨ l2 such that hA, li ∈ KOP.
Lemma 6. Let O ⊆ O, hA1, l1i, hA2, l2i ∈ KOP such that A1 ∩ A2 6= ∅. Then
From above and lemma 13 implies that there exist r(o, a) ≥ l1 and r(o, a) ≥ l2.
r(o, a) ≥ l1 ∨ l2. (∃B ⊇ O)(∃A ⊇ A1 ∩ A2)(∃l ∈ L : l ≥ l1 ∨ l2)hB, A, ki ∈ KP . hA, li ∈ KOP.
Hence Hence Hence ⇒ tu tu O1 ⊆ O2. Then KO1 ⊇ KOP2 .
P
Lemma 7. Let O1, O2 be an arbitrary subsets of the set of objects such that {hA1, l1i ∈ P(A) × L : (∃B1 ⊇ O1)hB1, A1, l1i ∈ KP } ⊇ ⊇ {hA2, l2i ∈ P(A) × L : (∃B2 ⊇ O2)hB2, A2, l2i ∈ K } the power-set lattice P(O) and the fuzzy power-set lattice F (A). Theorem 3. The pair of mappings (⇑, ⇓) forms a Galois connection between Proof. For every set O, the subset of the set of objects and the fuzzy set Ae, the fuzzy-subset of the set of attributes, have to be proven that O is the subset of ⇓ (Ae) if, and only if Ae is the fuzzy-subset of ⇑ (O).
O ⊆⇓ (Ae) = [
{B ⊆ O : (∀b ∈ A)(∃hA, li ∈ KBP)b ∈ A & l ≥ Ae(b)}.
P hAa, lai ∈ K⇓(Ae) .
O ⊆⇓ (Ae) implies that KOP ⊇ K⇓(Ae) P
. Hence hAa, lai ∈ KOP. So
Ae(a) ≤ la ≤ sup{l ∈ L : (∃hA, li ∈ KOP)a ∈ A} =⇑ (O)(a). O ⊆ [
{B ⊆ O : (∀b ∈ A)(∃hA, li ∈ KBP)a ∈ A & l ≥ Ae(b)} =⇓ (Ae).
tu For the case of object fuzzy side will be used mappings: ⇑: 2A → LO, ⇓: LO → 2A. ⇐ Let a ∈ A be an arbitrary attribute. Denote Because of arbitrarity of attribute a and from unequality above implies that Ae la =⇑ (O)(a) = sup{l ∈ L : (∃hA, li ∈ KOP)a ∈ A}. that there exists Aa ⊆ A such that hAa, lai ∈ KOP, and that implies The proposition implies that for every a ∈ A, Ae(a) ≤ la. The lemma 15 implies
O ∈ {B ⊆ O : (∀b ∈ A)(∃hA, li ∈ KBP)a ∈ A & l ≥ Ae(b)} hence where
⇑ (A)(o) = sup{l ∈ L : (∃hO, li ∈ KAP)o ∈ O} ⇓ (Oe) = [{T ⊆ A : (∀o ∈ O)(∃hO, li ∈ KTP )o ∈ O & l ≥ Oe(a)},
KAP = {hO, li : (∃T ⊇ A)hO, T, li ∈ K } results satisfy to Ae. Hence ⇓ (Ae) ={F,L,M,E}. Elements of KP are shown in the next table. Hence ⇓(Ae) ⇑ (⇓ (Ae)) = = {(Ma,1),(Sj,3),(Ph,1),(Ge,3),(Bi,2),(Gr,2),(En,2),(Ch,2),(Ae,2),(Hi,2)} {Ma,Sl,Ph,Ge,Bi,Gr,En,Ch,Ae,Hi} 3
{Ma, Ch, Ae, Gr, En, Hi} 2 {Ma, Ph, Bi, Ch, Ae, Gr, En, Hi} 2 {Ma,Ph,Bi,Gr,En,Ae,Hi} 2
{Ae,Gr,En,Hi} 2 {Ph,Bi,Gr,En,Ae,Hi} 2 {Bi,Gr,En,Ae,Hi} 2 {Bi,Gr,En,Ae,Hi} 2
{Ch,Gr,En,Hi} 2 {Ma,Gr,En,Ae,Hi} 2
{Ma,Ph} 1
Retrieval of proto-fuzzy concepts Proto-fuzzy concepts will be retrieved with a help of cuts and “pessimistic sights” to object-value or attribute-value plains.
Definition 8. Define new binary relations
RA = {(o, l) ∈ O × L : (∀a ∈ A)r(o, a) ≥ l} and
RO = {(a, l) ∈ A × L : (∀o ∈ O)r(o, a) ≥ l}.
The formal context hO, L, RAi will be called object–value sight and the formal context hA, L, ROi will be called attribute–value sight. For every O ⊆ O, A ⊆ A and l ∈ L put ↑A: 2O → L and ↓A: L → 2O, ↑O: 2A → L and ↓O: L → 2A. ↑A (O) = inf{sup{l ∈ L : (o, l) ∈ RA} : o ∈ O}
↓A (l) = {o ∈ O : (o, l) ∈ RA} ↑O (A) = inf{sup{l ∈ L : (a, l) ∈ RO} : a ∈ A}
↓O (l) = {a ∈ A : (a, l) ∈ RO}. between the power-set lattice P(O) or P(A) and the lattice of values L. Theorem 4. Pairs of mappings (↑A, ↓A) and (↑O, ↓O) form Galois connections Proof. The proof will be shown only for first pair. The proof for second pair is
and from a properties of infimum Hence Hence 2. Let l1, l2 ∈ L. If l1 ≤ l2 then 3. Let O ⊆ O. Denote {sup{l ∈ L : (o, l) ∈ RA} : o ∈ O1} ⊆ ⊆ {sup{l ∈ L : (o, l) ∈ RA} : o ∈ O2} inf{sup{l ∈ L : (o, l) ∈ RA} : o ∈ O1} ≥ ≥ inf{sup{l ∈ L : (o, l) ∈ RA} : o ∈ O2}.
↑A (O1) ≥↑A (O2). {o ∈ O : (o, l1) ∈ RA} ⊇ {o ∈ O : (o, l2) ∈ RA}.
↓A (l1) ⊇↓A (l2). so = sup{l ∈ L : (o, l) ∈ RA}, ↑A (O) = inf{sb : b ∈ O} ≤ so for arbitrary object o ∈ O. From definition of ↑A and from property 2 implies Arbitrarity of o implies that ↓A (↑A (O)) ⊇↓A (so) = {b ∈ O : (b, so) ∈ RA}.
[ o∈O ↓A (↑A (O)) ⊇
{b ∈ O : (b, so) ∈ RA} ⊇ O. all is so ≥ l. Hence 4. Let l ∈ L be an arbitrary value. Denote so = sup{k ∈ L : (o, k) ∈ RA}. For o ∈↓A (l) = {b ∈ O : (b, l) ∈ RA} ↑A (↓A (l)) = inf{sb : b ∈↓A (l)} ≥ l. denoted KA. denoted KO.
Definition 10. The pair hO, li is called A-concept of the object–value sight hO, L, RAi iff ↑A (O) = l and ↓A (l) = O. The set of all A-concepts will be Definition 11. The pair hA, li is called O-concept of the attribute–value sight hA, L, ROi iff ↑O (A) = l and ↓O (l) = A. The set of all O-concepts will be
It can be defined an object–value sight for every subset of attributes or attribute–value sight for every subset of objects, but their usage for this paper wasn’t necessary. ∈ K
P and hO2, A2i ∈ Kl for context hO \ O1, A \ A1, Rli. Then Theorem 5. Let l ∈ L, A1, A2 ⊆ A, O1, O2 ⊆ O such that hO, A1, li, hO1, A, li hO1 ∪ O2, A1 ∪ A2, li, ∈ KP .
Proof. It will be shown that A1 ∪ A2 =↓l (O1 ∪ O2) and O1 ∪ O2 =↑l (A1 ∪ A2).
If a ∈ A1 then for all o ∈ O is (o, a) ∈ Rl.
If a ∈ A2 then for all o ∈ O1 ∪ O2 is (o, a) ∈ Rl.
If a ∈ A1 ∪ A2 then for all o ∈ (O ∩ (O1 ∪ O2)) = O1 ∪ O2 is (o, a) ∈ Rl. Hence A1 ∪ A2 ⊆↑l (O1 ∪ O2). a ∈↑l (O1 ∪ O2) and a 6∈ A1 ∪ A2.
The opposite inclusion will be shown by contradiction. Let us assume The second equality can be shown likewise.
From a ∈↑l (O1 ∪ O2) implies that for all o ∈ O1 ∪ O2 ⊇ O2 is (o, a) ∈ Rl.
tu
Subcontexts from the theorem will be called auxiliary subcontexts of l-cut. example. Hence Concepts of sights will be retrieved with a help of mappings ↑A, ↓A, ↑O and ↓O.
Denote A as the set of all subjects and O as the group of all students from our hO, A, 4i ∈ KP , hO \ {N,D}, A, 3i, hO, A \ {Ma,Ph,Bi}, 3i ∈ KP ,
h{M,E}, A, 1i, hO, {Gr,En,Hi}, 2i ∈ KP , Let us create auxiliary subcontexts of 3-cut, 2-cut and 1-cut. N D • •
There are only two concepts in the auxiliary subcontext of 3-cut, h{N }, {Bi}i and h{D}, {M a}i. The theorem 23 implies that hO \ {N}, A \ {P h, Bi}, 3i, hO \ {D}, A \ {Ma,Ph}, 3i ∈ KP .
Because of the convexity of l-concepts, we can omit Eve and Mary from the set of students for auxiliary subcontext of 2-cut. And for input of theorem 23 for degree 2 can be used proto-fuzzy concepts h{M,E}, A, 1i, hO, {Gr,En,Hi}, 2i ∈ KP . Conceptual scaling and theory of triadic contexts will be the object of our future work and study. We will try to algoritmize outline process.
We are grateful for precious comments of our colleagues RNDr. Peter Eliaˇs PhD. and RNDr. Jozef P´ocs.
Paper was created with support of grant 1/3129/06 Slovak grant agency VEGA.