=Paper=
{{Paper
|id=None
|storemode=property
|title=Relations between Proto-fuzzy concepts, Crisply Generated Fuzzy
Concepts, and Interval Pattern Structures
|pdfUrl=https://ceur-ws.org/Vol-672/paper5.pdf
|volume=Vol-672
|dblpUrl=https://dblp.org/rec/conf/cla/PankratievaK10
}}
==Relations between Proto-fuzzy concepts, Crisply Generated Fuzzy
Concepts, and Interval Pattern Structures==
https://ceur-ws.org/Vol-672/paper5.pdf
Relations between Proto-fuzzy Concepts,
Crisply Generated Fuzzy Concepts, and Interval
Pattern Structures
Vera V. Pankratieva and Sergei O. Kuznetsov
State University Higher School of Economics, Pokrovskiy bd., 11, Moscow 101000,
Russia,
vera.pankratieva@gmail.com, skuznetsov@hse.ru
Abstract. Relationships between proto-fuzzy concepts, crisply gener-
ated fuzzy concepts, and pattern structures are considered. It is shown
that proto-fuzzy concepts are closely related to crisply generated fuzzy
concepts in the sense that the mappings involved in the definitions co-
incide for crisp subsets of attributes. Moreover, a proto-fuzzy concept
determines a crisp subset of attributes, which generates a (crisply gen-
erated) fuzzy concept. However, the reverse is true only in part: given
a crisp subset of attributes, one can find a proto-fuzzy concept whose
intent includes (but not necessarily coincides with) the given subset of
attributes. Interval pattern concepts are shown to be related to crisply
generated formal concepts. In particular, every crisply closed subset of
objects is an extent of an interval pattern concept.
1 Introduction
Various approaches to extending the basic definitions of the Formal Concept
Analysis to numerical and more complex data representations were proposed
in the last three decades. An important direction of this research is related to
fuzzy concept analysis, see [2] for an overview of various approaches to fuzzy
concept lattices and some relationships between fuzzy concept lattices and con-
cept lattices of l-cuts of formal fuzzy contexts. A relationship between ordinary
Galois connections and fuzzy Galois connections was given in [3]. In this pa-
per we try to establish relationships between most important notions of several
approaches to fuzzy concept analysis. We show how crisply generated fuzzy con-
cepts (R. Belohlavek, V. Sklenar, and J. Zacpal [4]), proto-fuzzy concepts (in-
troduced by O. Kridlo and S. Krajci in [5]), and pattern structures (B. Ganter
and S.O. Kuznetsov [6]), in particular interval pattern structures, are related. It
is shown that proto-fuzzy concepts are closely related to crisply generated fuzzy
concepts in the sense that the mappings involved in the definitions coincide for
crisp subsets of attributes. Also, each proto-fuzzy concept determines a crisp
subset of attributes, which generates a (crisply generated) fuzzy concept. How-
ever, the reverse is true only in part: given a crisp subset of attributes, one can
find a proto-fuzzy concept whose intent includes (but not necessarily coincides
with) the given subset of attributes.
Relations between Concepts 51
Interval pattern concepts, which are particular case of pattern structures, are
shown to be related to crisply generated formal concepts. In particular, every
crisply closed subset of objects is an extent of an interval pattern concept.
The paper is organized as follows. The second section contains main defini-
tions of FCA and their extensions to fuzzy data. The third section describes re-
lations between crisply-generated fuzzy concepts and proto-fuzzy concepts. The
relationship between fuzzy concepts and interval pattern concepts is described
in the fourth section.
2 Fuzzy Contexts and Formal Concepts
We start with a set X of objects, a set Y of attributes, and a fuzzy relation I
between X and Y . This means that a truth degree I(x, y) ∈ L, where L is the
set of values of some complete residuated lattice L, see, e.g., [1], is assigned to
each pair (x, y), x ∈ X, y ∈ Y . The element I(x, y) is interpreted as the degree
to which attribute y applies to object x. The triple hX, Y, Ii is called a formal
fuzzy context.
In paper [3] the following mappings are introduced. Fuzzy sets A ∈ LX and
B ∈ LY are mapped into fuzzy sets A↑ ∈ LY and B ↓ ∈ LX according to the
formulas
V
A↑ (y) = (A(x) → I(x, y)),
x∈X
↓ V
B (x) = (B(y) → I(x, y))
y∈Y
for y ∈ Y and x ∈ X.
Definition 1 ([4]). A formal fuzzy concept hA, Bi consists of a fuzzy set A
of objects (the extent of the concept) and a fuzzy set B of attributes (the concept
intent) such that A↑ = B and B ↓ = A. The set of all formal fuzzy concepts is
denoted by B(X, Y, I).
Definition 2 ([4]). A formal fuzzy concept hA, Bi ∈ B(X, Y, I) is said to be
crisply generated if there exists a crisp subset Bc ⊆ Y such that A = Bc↓
(thus, B = Bc↓↑ ).
Strictly speaking, such crisply generated concepts should be called crisply
attribute-generated fuzzy concepts in contrast to crisply object-generated
fuzzy concepts which can be defined in a similar way.
There is another approach to generalization of formal concept analysis to the
case of fuzzy contexts, which was developed in paper [5]. Given a fuzzy context
hX, Y, Ii, define its l-cuts Il , l ∈ L, as
Il = {(x, y) ∈ X × Y : I(x, y) ≥ l}
and introduce the mappings ↑l : 2X → 2Y and ↓l : 2Y → 2X :
↑l (A) = {y ∈ Y : (∀x ∈ A)I(x, y) ≥ l}, A ⊆ X,
↓l (B) = {x ∈ X : (∀y ∈ B)I(x, y) ≥ l}, B ⊆ Y.
52 Vera V. Pankratieva, Sergei O. Kuznetsov
Definition 3 ([5]). A pair hA, Bi ∈ 2X × 2Y is called an l-concept if and only
if ↑l (A) = B and ↓l (B) = A, which means that the pair hA, Bi is a formal
concept in the l-cut hX, Y, Il i, which is a binary context. The set of all concepts
in the l-cut is denoted by Kl .
S
Definition 4 ([5]). Triples hA, B, li ∈ 2X × 2Y × L such that hA, Bi ∈ Kk
k∈L
and l = sup{k ∈ L : hA, Bi ∈ Kk } are called proto-fuzzy concepts. The set
of all proto-fuzzy concepts is denoted by KP .
Definition 5 ([5]). Let B ⊆ Y be an arbitrary set of attributes. We define the
contraction of the set of proto-fuzzy concepts subsistent to the set B as
P
KB = {hA, li ∈ 2X × L : (∃B ′ ⊇ B)hA, B ′ , li ∈ KP }.
P
Thus, the elements of the set KB are proto-fuzzy concepts (in the fuzzy context
hX, Y, Ii) “contracted to the subset B.”
Definition 6 ([5]). Define the mappings
⇑: LX → 2Y ,
⇓: 2Y → LX
as follows: for any subset A of objects and any subset B of attributes let
[
P
⇑ (Ã) = {B ⊆ Y : (∀x ∈ X)(∃hA, li ∈ KB x ∈ A & l ≥ Ã(x)};
P
⇓ (B)(x) = sup{l ∈ L : (∃hA, li ∈ KB ), x ∈ A}.
The mapping ⇑ takes a fuzzy subset of objects à to a (crisp) set of at-
tributes B ⊆ Y . The mapping ⇓ takes a crisp subset of attributes B ⊆ Y to a
fuzzy subset of objects Ã.
3 Relationship between crisply generated fuzzy concepts
and proto-fuzzy concepts
Consider a fuzzy context hX, Y, Ii with k objects and n attributes (i.e., |X| = k,
|Y | = n)
b1 b2 · · · bn
a1 d11 d12 . . . d1n
a2 d21 d22 . . . d2n
.. ..
. .
ak dk1 dk2 . . . dkn
Relations between Concepts 53
and take some (crisp) intent B ⊆ Y to which some proto-fuzzy concepts may
be contracted. To compute ⇓ (B), we write the set B in the form of an n-tuple
(b1 , b2 , . . . , bn ), where bi = 1 if and only if the intent B contains the ith attribute.
Then
P
⇓ (B)(x) = sup{l ∈ L : (∃hA, li ∈ KB ) x ∈ A}.
Evaluating ⇓ (B) at the element x1 gives
P
⇓ (B)(x1 ) = sup{l ∈ L : (∃hA, li ∈ KB ) x1 ∈ A}.
This means that it is necessary to find a cut that corresponds to the maximum
value of l and contains a proto-fuzzy concept (including the elements of the top
row) which may be contracted to B.
In order that all entries d1j that correspond to unit jth attributes be con-
tained in some l-cut, it is necessary that the condition
V d1j ≥ l be satisfied for
all such indices j. If we take the infimum d∗ = d1j over all j such that
bj =1
bj = 1, then all d1j are not less than d∗ . Therefore, all d1j are contained in the
d∗ -cut and, hence, they belong to some proto-fuzzy concept in this cut. Such
proto-fuzzy concept may consist of the top row contracted to B, unless it may
be extended to other rows to form a rectangular (i.e., if the contraction of any
other row to B contains elements which are less than d∗ ). It may also happen
that the d∗ -cut contains a rectangular that consists of at least two rows and can
be contracted to B. Such rectangular presents a proto-fuzzy concept, since this
∗
is a formal concept which doesV not occur higher than at the d -cut.
Thus, a1 =⇓ (B)(x1 ) = d1j .
bj =1
The same for all other objects xi . As a result, we arrive at a fuzzy set
^ ^ ^
⇓ (B) = (a1 , a2 , . . . , ak ) = d1j , d2j , · · · dkj .
bj =1 bj =1 bj =1
Now let us compute the result of the mapping ↓ applied to the crisp set of
attributes B = (b1 , b2 , . . . , bn ):
^
B ↓ (x) = (B(y) → I(x, y)).
y∈Y
Here and in what follows, computations are performed in the framework of the
lattice with the L
à ukasiewicz logical connectives (however, most of the statements
seem to hold also for the general case), so a → b = min{1 − a + b, 1}, and
a ∧ b = min{a, b}. Let us compute B ↓ (x1 ) — the result of the evaluation of the
mapping ↓ at the element x1 :
^ ^
B ↓ (x1 ) = (B(y) → I(x1 , y)) = (b1 → d11 , b2 → d12 , . . . , bn → d1n ).
y∈Y
The values bj that are equal to zero are inessential, since the corresponding
implication evaluates to 1: min{1 − 0 + d1j , 1} = 1. For the values bj which are
54 Vera V. Pankratieva, Sergei O. Kuznetsov
equal to 1, we have bj → d1j = 1 − 1 + d1j = d1j . Thus, to determine the result
of the mapping, it is necessary
V to find the infimum over all elements of the top
row. Therefore, B ↓ (x1 ) = d1j . The same for all other objects.
bj =1
As a result, we obtain
^ ^ ^
B ↓ = (a1 , a2 , . . . , ak ) = d1j , d2j , . . . , dkj .
bj =1 bj =1 bj =1
Thus, we arrive at
Theorem 1. The mapping ⇓ coincides with the mapping ↓ restricted to crisp
subsets of attributes.1
For an arbitrary k-tuple A = (a1 , . . . , ak ) by l A = (l a1 , . . . , l ak ) we denote
the l-cut of A, i.e., the crisp k-tuple whose components are defined as
(
l 1, aj ≥ l,
aj =
0, aj < l.
W W
Theorem 2. Let A = (a1 , . . . , ak ) = Bc↓ , B = Bc↓↑ . Denote l = Bc↓ = ai
and consider the set Z = (z1 , . . . , zk ) such that zi = 0 if ai < l and zi = 1 if
ai = l. Then (z1 , z2 , . . . , zk ) × 1 B corresponds to some proto-fuzzy concept in the
l-cut that may be contracted to 1 B.
Proof. Consider the rows that correspond to ai = l. The elements that stay
at the intersection of these rows with 1 B belong to the l-cut. This rectangular
cannot be extended to other rows, since any other row contracted to 1 B contains
elements which are less than l. However, it may happen that it may be extended
to columns which correspond to zero components of Bc . In the case of such
extension we obtain in the l-cut a proto-fuzzy concept which may be contracted
to Bc . ⊓
⊔
Remark 1. The statement that this procedure gives a proto-fuzzy concept (rather
than a contraction of one) is, in general, not valid.
Example. Consider a fuzzy context and its 0.5-cut given by the following
tables:
1 0.7 1 0.7 0.5-cut
0.2 0.2 0.2 0.5 0.7 XX
0.3 0.3 0 0.7 0.8 XX
0.5 0.5 0.8 0.8 0.2 XXX
0.5 0.5 0.7 0.7 0.4 XXX
1
When this text was already prepared for publication, the authors discovered the
work [7], which contains related results.
Relations between Concepts 55
Take Bc = (1, 0, 1, 0).WThen Bc↓ = A = (0.2, 0.3, 0.5, 0.5); A↑ = B = (1, 0.7, 1, 0.7);
↓
B = (0.2, 0.3, 0.5, 0.5); ai = 0.5; Z = (0, 0, 1, 1).
As a result, Z × Bc = (0, 0, 1, 1) × (1, 0, 1, 0) corresponds to the context
0000
0000
1010
1010
Theorem 3. Let A = (a1 , . . . , ak ) = Bc↓ and B = Bc↓↑ . For any i, 1 ≤ i ≤ k,
specify a k-tuple Zi by the formula
(
j 1, aj ≥ ai ,
zi =
0, aj < ai .
Then the context Zi × Bc corresponds to a proto-fuzzy concept in the ai -cut of
the original context, which may be contracted to Bc .
The proof of this theorem is similar to that of Theorem 2.
Theorem 4. Suppose that the l-cut contains a proto-fuzzy formal concept. Then
there exists an n-tuple Bc satisfying the following conditions:
1. Bc↓ = (a1 , . . . , ak ), where ai ≥ l if this proto-fuzzy concept involves the ith
object and ai < l, otherwise;
2. the n-tuple Bc is closed with respect to crisp components (or just crisply
closed); that is, 1 (Bc↓↑ ) = Bc .
Proof. Define the n-tuple Bc = (b1 , . . . , bn ) as follows: bi = 1 if and only if the
given proto-fuzzy concept involves the ith attribute. Then, in accordance with
the definition of a proto-fuzzy concept, we have Bc↓ = A = (a1 , . . . , ak ), where
ai ≥ l if this proto-fuzzy concept involves the ithe object and ai < l, otherwise.
Let us show that the n-tuple Bc obtained in this way satisfies Property 2.
Suppose, by contradiction, that there is an attribute j such that
Bc (j) = bj = 0 and Bc↓↑ (j) = 1.
Then there exists an object i that belongs to the given formal concept and
satisfies the condition dij < l (or else the attribute j belongs to the given formal
concept and Bc (j) = bj = 1). Now, taking into account the inequality Bc↓ (i) ≥ l,
we obtain
Bc↓↑ (j) ≤ 1 − Bc↓ (i) + dij ≤ 1 − l + dij < 1 − l + l = 1.
This estimate means that the n-tuple 1 (Bc↓↑ ) has no nonzero components other
than those of Bc . ⊓
⊔
56 Vera V. Pankratieva, Sergei O. Kuznetsov
By Theorem 3 the context l A × Bc may be considered a contraction of some
proto-fuzzy concept to Bc .
In order to find out whether the context l A × Bc determines a proto-fuzzy
concept or a contraction of some proto-fuzzy concept, we consider the closure
B = A↑c of the crisp n-tuple l A = Ac . Following the lines of the proof of Theo-
rem 3 one can show that the context Ac × l B is a contraction of some proto-fuzzy
concept to Ac .
On the other hand, the n-tuple Ac = l A was defined as the l-cut of the n-
tuple A, which is the closure of the crisp n-tuple Bc of attributes. For this reason,
the n-tuple Ac cannot be majorized by a greater (crisp) n-tuple “possessing”
the attributes Bc and, therefore, the context Ac × l B cannot be considered a
nontrivial contraction of some proto-fuzzy concept to Ac .
4 Relationship between fuzzy formal concepts and
pattern structures
Definition 7. Let G be a set of an arbitrary nature, (D, ⊓) be a meet-semilattice,
and let there be a mapping
δ : G → D.
The triple
(G, D, δ),
where D = (D, ⊓), is called a pattern structure, provided that the set
δ(G) := {δ(g)|g ∈ G}
generates a complete subsemilattice (Dδ , ⊓) of (D, ⊓). Each complete semilattice
of this kind has lower and upper bounds, which we denote by 0 and 1, respectively.
For a pattern structure (G, D, δ) we define the derivation operators acting
on subsets A ⊆ G as l
A¤ := δ(g)
g∈A
and on the semilattice elements d ∈ D as
d¤ := {g ∈ G|d ⊑ δ(g)}.
Example. Consider the following fuzzy context:
object 1 0.2 0.2 0.5 0.7
object 2 0.3 0 0.7 0.8
object 3 0.5 0.8 0.8 0.2
object 4 0.5 0.7 0.7 0.4
Relations between Concepts 57
The set G is the set of all objects. The closure operator applied to a sub-
set A of objects gives an n-tuple (the length of which is equal to the number of
attributes — in this case, n = 4) of shortest intervals which cover the values of
the corresponding attributes for all objects of the subset A.
For instance, for the subset A = {1, 2} of objects we have
{1, 2}¤ = d12 = {[0.2; 0.3], [0; 0.2], [0.5; 0.7], [0.7; 0.8]}
and d¤12 = {1, 2}. As in the binary case, a pair (A, d), A ⊆ G, d ∈ D, satisfying
the conditions A¤ = d, d¤ = A, is said to comprise a pattern concept. Thus,
the pair ({1, 2}, {[0.2; 0.3], [0; 0.2], [0.5; 0.7], [0.7; 0.8]}) is a pattern concept.
Now let us compute {1, 3}¤ . We have
{1, 3}¤ = d13 = {[0.2; 0.5], [0.2; 0.8], [0.5; 0.8], [0.2; 0.7]}
and d¤
13 = {1, 3, 4}.
Subsets of objects may be considered as crisp n-tuples (of objects), where
n = |G|, extents are then closed crisp n-tuples. Object implication is defined as
usual: for sets A, C ⊆ G we write A → C iff A¤ ⊑ C ¤ , where ⊑ is a natural
subsumption relation associated to ⊓: X ⊑ Y iff X ⊓ Y = X. In particular,
there is an object implication ai → aj (ai , aj ∈ G) if the row of the context
corresponding to ai (i.e., a¤
i ) is component-wise smaller than the row of the
context corresponding to aj (i.e., a¤
j ).
Theorem 5. If the set of all extents of interval pattern concepts coincides with
the set of all crisply closed n-tuples, then the context contains no implications.
Proof. Assume that all (crisp) n-tuples that correspond to closed subsets of
objects (i.e., such that A¤¤ = A) are crisply closed and there are no other
crisply closed n-tuples. Then suppose, by contradiction, that the formal context
contains an implication ai → aj . Since the context contains no identical rows, all
objects are closed. In particular, a¤¤
i = ai . Consider the crisp n-tuple Ai that
corresponds to the object ai
(0, . . . , 0, 1, 0, . . . , 0)
| {z } | {z }
i−1 n−i
and its image A↑i under the mapping ↑. It is easily seen that A↑i is a fuzzy n-
tuple that coincides with the ith row of the context. Since every component of
the fuzzy n-tuple A↑i is not greater than the corresponding component of the jth
row, the closure A↑↓i contains 1 at the jth component. Thus, the n-tuple Ai is
not crisply closed. The contradiction obtained proves the theorem. ⊓
⊔
Theorem 6. For any crisply closed n-tuple the corresponding subset of objects
is closed.
58 Vera V. Pankratieva, Sergei O. Kuznetsov
Proof. Consider an arbitrary crisply closed n-tuple A. The tuple A↑ consists of
the row minima for the support of the crisp n-tuple A. The fact that A is crisply
closed means that A↑↓ = A, that is, none of the rows dominate A↑ . Hence,
the corresponding extent is closed, since no other row falls within the interval
between the minimum and the maximum values. ⊓
⊔
Thus, the set of crisply closed n-tuples is contained in the set of extents of
interval formal concepts.
Corollary 1. In order that the set of crisply closed n-tuples coincide with the
set of extents of interval pattern concepts it is necessary that each pattern concept
satisfy the following condition: the minima of the intervals comprise an n-tuple
which is not less than any object intent of an object not contained in the extent
of the interval pattern concept.
Proof. Follows directly from Theorems 5 and 6. ⊓
⊔
5 Conclusions
In this work, we studied relations between various generalizations of formal con-
cept analysis to the case of numerical values. The known approaches include
proto-fuzzy concepts, crisply generated fuzzy concepts, and pattern structures.
It was shown that proto-fuzzy concepts and fuzzy concepts have much in
common: the mappings involved in their definitions coincide for crisp subsets of
attributes. Also, each proto-fuzzy concept determines a crisp subset of attributes,
which generates a (crisply generated) fuzzy concept. However, the reverse is true
only in part: any crisp subset of attributes is a contraction of the intent of some
proto-fuzzy concept, but not necessarily the intent itself.
Interval pattern concepts, which are particular case of pattern structures,
were shown to be related to crisply generated formal concepts. In particular,
every crisply closed subset of objects is an extent of an interval pattern concept.
Sufficient conditions are derived under which no other extents of interval pattern
concepts exist.
Further research in this area would go in the following directions:
– introduce “two-sided” (double) pattern structures and study their relation-
ship with fuzzy formal concepts;
– find a minimal (canonical) fuzzy context that induces a lattice of fuzzy con-
cepts isomorphic to a given one;
– elaborate new methods for fuzzy data analysis on the basis of the results
obtained.
References
1. Hájek, P., Metamathematics of Fuzzy Logic, Kluwer, Dordrecht, 1998.
Relations between Concepts 59
2. Bělohlávek, R., Vychodil V.: What is a fuzzy concept lattice?, in CLA 2005, pp.
34-45, 2005.
3. Belohlavek R.: Fuzzy Galois connections. Math. Logic Quarterly 45,4 (1999), 497-
504.
4. Bělohlávek, R., Sklenář, V., Zacpal, J.: Crisply Generated Fuzzy Concepts, in:
B. Ganter and R. Godin (Eds.): ICFCA 2005, LNCS 3403, pp. 268–283, 2005
(Springer-Verlag, Berlin, Heidelberg, 2005).
5. O. Krı́dlo, S. Krajči, Proto-fuzzy Concepts, Their Retrieval and Usage, in: B. Gan-
ter and R. Godin (Eds.): CLA 2008, pp. 83–95, ISBN 978-80-244-2111-7, Palacký
University, Olomouc, 2008.
6. B. Ganter and S.O. Kuznetsov, Pattern Structures and Their Projections, preprint
MATH-AL-14-2000, Technische Universität Dresden, Herausgeber, Der Rektor,
November 2000.
7. O. Krı́dlo, S. Krajči, Fuzzy concept lattice is made by proto-fuzzy concepts, in:
J.P. Carvalho, D. Dubois, U. Kaymak, and J.M.C. Sousa (Eds.): Proceedings of
the Joint 2009 International Fuzzy Systems Association World Congress and 2009
European Society of Fuzzy Logic and Technology Conference, Lisbon, Portugal, July
20-24, 2009, pp. 1252–1257.