=Paper=
{{Paper
|id=Vol-1624/paper7
|storemode=property
|title=On Scaling of Fuzzy FCA to Pattern Structures
|pdfUrl=https://ceur-ws.org/Vol-1624/paper7.pdf
|volume=Vol-1624
|authors=Aleksey Buzmakov,Amedeo Napoli
|dblpUrl=https://dblp.org/rec/conf/cla/BuzmakovN16
}}
==On Scaling of Fuzzy FCA to Pattern Structures==
https://ceur-ws.org/Vol-1624/paper7.pdf
On Scaling of Fuzzy FCA to Pattern Structures
Aleksey Buzmakov1 and Amedeo Napoli2
1
National Research University Higher School of Economics, Perm, Russia
2
LORIA (CNRS – Inria – University of Lorraine), Vandœuvre-lès-Nancy, France
avbuzmakov@hse.ru, amedeo.napoli@loria.fr
Abstract. FCA is a mathematical formalism having many applications
in data mining and knowledge discovery. Originally it deals with binary
data tables. However, there is a number of extensions that enrich stan-
dard FCA. In this paper we consider two important extensions: fuzzy
FCA and pattern structures, and discuss the relation between them. In
particular we introduce a scaling procedure that enables representing a
fuzzy context as a pattern structure. Studying the relation between dif-
ferent extensions of FCA is of high importance, since it allows migrating
methods from one extension to another. Moreover, it allows for more
simple implementation of different extensions within a software.
Keywords: fuzzy FCA, pattern structures, scaling
1 Introduction
In this paper we deal with Formal Concept Analysis (FCA) and its extensions.
FCA is a mathematical formalism having many applications in data mining and
knowledge discovery. It starts from a binary table, a so-called formal context
(G, M, I), where G is the set of objects, M is the set of attributes, and I ⊆ G×M
is a relation between G and M , and proceeds to a lattice of formal concepts [1].
Fuzzy FCA is an extension of standard FCA that allows for fuzzy sets of objects
and attributes in order to express uncertainty.
Pattern structures is another extension of FCA that allows processing com-
plex data, e.g., graph or sequence datasets. It is a quite general framework and
the question if fuzzy FCA can be represented within Pattern Structures and vice
versa is still open. In this paper we make a step in this direction and study the
connections between pattern structures and fuzzy FCA.
We show how a fuzzy context can be scaled to a “Minimum Pattern Struc-
ture” (MnPS), a special kind of pattern structures, that is close to interval
pattern structures when considering numerical data. A scaling is needed, since
pattern structures deal with crisp sets of objects and, thus, fuzzy extents cannot
be expressed within the formalism of pattern structures. For such a kind of scal-
ing we add new objects to the fuzzy context that express objects with uncertain
membership in fuzzy sets, allowing expressing fuzzy sets of objects in the for-
malism of pattern structures. The resulting context is processed by MnPS. This
kind of scaling is applicable to fuzzy FCA based on residuated lattices, a special
kind of lattices expressing uncertain membership degrees in fuzzy sets.
Table 1: A toy dataset of transactions for a supermaket and the related similarity
matrix.
(a) A dataset with 5 transactions. (b) Similarity matrix.
i1 i2 i3 i4 i5 i6 i7 t1 t2 t3 t4 t5
t1 x x x x x t1 1.000 0.714 0.857 0.429 0.429
t2 x x x x x t2 0.714 1.000 0.571 0.429 0.429
t3 x x x x t3 0.857 0.571 1.000 0.286 0.714
t4 x x x t4 0.429 0.429 0.286 1.000 0.000
t5 x x x x t5 0.429 0.429 0.714 0.000 1.000
The rest of the paper is organized as follows. Section 2 describes a running
example. Later, in Section 3 we introduce main definitions of fuzzy FCA and
pattern structures. The main contribution of this paper is located in Section 4,
where we introduce and discuss the scaling procedure of fuzzy FCA to pattern
structures. Finally, at the end of the paper we discuss some related works.
2 Running Example
Let us consider a toy dataset of transactions within a supermarket. It is shown
in Table 1a. Every row corresponds to a basket bought by a customer and every
attribute corresponds to an item that can be bought in the supermarket. A cross
in a cell (i, j) means that in the basket i there is the item j.
For making the example concrete, let us consider a clustering task. When
dealing with clustering one typically needs a similarity or a distance measure.
Such distance and similarity measures for the purpose of this example could be
|t0 +t0 |
the fraction of different items shared by two baskets Dist(t1 , t2 ) = 1|M |2 and
Sim(t1 , t2 ) = 1 − Dist(t1 , t2 ), where operation ’+’ between sets is an exclusive
OR (a so-called XOR or the symmetric difference, i.e., A+B = (A\B)∪(B \A)).
The similarity measure for any pair of transactions is shown in Table 1b. For
example, similarity between t1 and t2 is equal 0.714. These baskets are different
in two items i4 and i5 . Thus Dist(t1 , t2 ) = 72 = 0.286, where 7 is the number of
items in the supermarket, and Sim(t1 , t2 ) = 1 − Dist(t1 , t2 ) = 0.714.
3 Definitions
Formal Concept Analysis (FCA) is a formalism for dealing with data mining and
knowledge discovery tasks. It starts from a binary context (G, M, I), where G is
the set of objects, M is the set of attributes and I ⊆ G × M is a relation between
G and M . However, in real tasks such a binary encoding is too limited and several
extensions of FCA were introduced. One of them is fuzzy FCA [2] that changes
crisp sets into fuzzy sets. By doing so one is able to encode uncertainty. Another
extension is pattern structures [3] dealing with crisp sets of objects but replacing
binary sets of attributes with arbitrary descriptions allowing processing of many
kinds of datasets, e.g., graph or sequential datasets. Below we discuss these two
generalizations and their relation.
3.1 Fuzzy FCA
Fuzzy FCA works with fuzzy logic instead of crisp-logic, used in standard FCA.
There are several generalizations of FCA to the fuzzy case [2]. Here the approach
of Belohlavek is considered [4]. In fuzzy logic formulas can be valid up to a certain
degree. It means that the formula can be completely valid, completely invalid,
or between these two states. This fuzziness in fuzzy FCA is represented by a
so-called residuated lattice, where the top of the lattice > corresponds to “com-
pletely valid” state of the logic and the bottom ⊥ corresponds to “completely
invalid” state.
Definition 1. A Residuated Lattice is an algebra L = hL, ∨, ∧, ⊗, , 0, 1i, where
hL, ∨, ∧, 0, 1i is a complete lattice; hL, ⊗, 1i is a commutative monoid, i.e. ⊗ is
commutative, associative, and ∀a(a ⊗ 1 = 1 ⊗ a = a); and ⊗ form an adjiont
pair, i.e., a ⊗ b ≤ c ⇔ a ≤ b c.
For the following, L refers to the set of elements of some residuated lattice
and L for the residuated lattice itself. Such a lattice naturally appears when
we want to introduce some degree of uncertainty. In the running example we
introduced a similarity measure for any two objects. The values of the similarity
can be considered as elements of the residuated lattice [0, 1], a linear order of
real numbers. The lattice operators x ∧ y and x ∨ y are given by min(x, y) and
max(x, y) correspondingly. The operations ⊗ and are “fuzzy conjunction”
and “fuzzy implication”.
An important residuated lattice based on a linearly ordered set is Göodel
residuated lattice, which is used in examples of this paper. In Göodel residuated
lattices the fuzzzy implication is defied as following:
>a≤b
a b= (1)
b a>b
In the crisp logic the implication > → ⊥ is not valid, i.e., > → ⊥ = ⊥,
while other three possible implications are valid, i.e., > → > = >, ⊥ → > = >,
and ⊥ → ⊥ = >. The formula (1) generalizes this behavior. If the premise is
less certain than the conclusion, then the implication is valid (>), otherwise the
validity of the implication is equal to the certainty of the conclusion.
In Definition 1 it is required that the fuzzy implication is adjoint (related)
with an ⊗-operation. For Göodel residuated lattices the fuzzy implication is
adjoint with a ⊗ b = min(a, b). Indeed, b c ≥ c according to (1). If a ⊗ b ≤ c,
i.e., min(a, b) ≤ c and min(a, b) = a, then a ≤ c ≤ b c. If min(a, b) = b, then
b ≤ c and a ≤ 1 = b c. Accordingly one can check that a ≤ b c ⇒ a ⊗ b ≤ c.
⊗-operation is called fuzzy conjunction since it is a generalization of the crisp
conjunction that is valid only if both arguments are valid, i.e., > ⊗ > = >.
A fuzzy dataset is encoded by means of a fuzzy context as defined below.
Definition 2. A Fuzzy Relation between two sets X and Y is a function I :
X × Y → L, for some residuated lattice L.
Definition 3. A Fuzzy Context is a triple (X, Y, I) where X is a set of objects,
Y is a set of attributes, I is a fuzzy relation, I : X × Y → L.
Let us consider Table 1b as an example. It describes a fuzzy context where
the set of attributes and the set of objects are the same. The cells of this table
are similarity measures between objects. In this case the residuated lattice is
formed as a linear order on similarity values.
Let us now define what is a fuzzy set, the next building block of fuzzy FCA.
Definition 4. Given a crisp set X, a fuzzy set A is a function A : X → L,
mapping each element of the crisp set to an S element of the residuated lattice. A
fuzzy set is denoted as {li ∈L /xi ∈X }, where xi = X, and for simplicity elements
A(x ∈ X) = ⊥ are omitted.
For example, {1 /t2 ,0.571 /t3 } is a fuzzy set. Object t2 belongs to this set
entirely while object t3 belongs only partially. The other items do not belong to
this set, i.e., A(g) = ⊥. Given our similarity measure we know that 1 ≡ > and
0 ≡ ⊥.
In the fuzzy case of FCA one also defines Galois connections between a fuzzy
set of objects A : X → L and a fuzzy set of attributes B : Y → L.
Definition 5 (Derivation Operators). Given a fuzzy context (X, Y, I), a
fuzzy set of objects A : X → L, a fuzzy set of attributes B : Y → L, the
fuzzy membership for object x ∈ X and for attribute y ∈ Y in the corresponding
sets A↑ and B ↓ are as follows:
^
A↑ (y) = (A(x) I(x, y))
∀x∈X
^
↓
B (x) = (B(y) I(x, y))
∀y∈Y
Let us illustrate the derivation operators. First let us introduce the fuzzy
set of interest A = {1.0 /t1 ,1.0 /t2 } (all other objects do not belong to this set,
i.e., they have “0” membership in that set). Then we would like to find A↑ .
To compute A↑ we should compute A(x) I(x, y) for every object x ∈ X
and for every attribute y ∈ Y (in the example we have a particular case where
X ≡ Y ). According to our set of interest A(x) is either 1 or 0. For the function
I(x, y), the first argument varies from row to row and the second argument varies
from column to column. The result of these operations is shown in Table 2. For
example, the result of computing A(t1 ) I(t1 , t2 ) is given in the first row
second column cell. The last row of that table shows the resulting fuzzy set of
Table 2: Example of computations for {1.0 /t1 ,1.0 /t2 }↑ .
y t1 t2 t3 t4 t5
(A(t1 ) = 1) I(t1 , y) 1.000 0.714 0.857 0.429 0.429
(A(t2 ) = 1) I(t2 , y) 0.714 1.000 0.571 0.429 0.429
(A(t3 ) = 0) I(t3 , y) 1 1 1 1 1
(A(t4 ) = 0 I(t4 , y) 1 1 1 1 1
(A(t5 ) = 0) I(t5 , y) 1 1 1 1 1
{1.0 /t1 ,1.0 /t2 }↑ 0.714 0.714 0.571 0.429 0.429
Table 3: Example of computations for {1.0 /t1 ,1.0 /t2 }↑↓ .
/t2 } ↑↓
t1 )
t2 )
t3 )
t4 )
t5 )
I (x,
I (x,
I (x,
I (x,
I (x,
/t1 , 1.0
0.714
0.714
0.571
0.429
0.429
{ 1.0
t1 1 1 1 1 1 1
t2 1 1 1 1 1 1
t3 1 0.571 1 0.286 1 0.286
t4 0.429 0.429 0.286 1 0 0
t5 0.429 0.429 1 0 1 0
the attributes (more precisely their membership degree). The value of the last
row can be computed by applying ∧ operator of the residuated lattice to the
whole column, and in the case of our example ∧ corresponds to the minimum.
As the result of A↑ we obtained
B = A↑ = {0.714 /t1 ,0.714 /t2 ,0.571 /t3 ,0.429 /t4 ,0.429 /t5 }.
Let us now apply the derivation operator to the set A↑ . To find B ↓ = A↑↓
we need to compute B(x) I(x, y). The result of these operations is shown
in Table 3 and should be read in the same way as Table 2. The last column
corresponds to the result of B ↓ . Then we have:
{1.0 /t1 ,1.0 /t2 }↑↓ = {1.0 /t1 ,1.0 /t2 ,0.286 /t3 }
It can be checked that A↑↓↑ = B and A↑↓↑↓ = B ↓ = A↑↓ . These properties
of the derivation operators defines fuzzy concepts [2].
Definition 6. A fuzzy concept is a pair (A, B), where A is a fuzzy set of objects,
A : X → L and B is a fuzzy set of attributes B : Y → L, such that A↑ = B and
A = B↓.
In particular in the previous example we have found the concept:
{1.0 /t1 ,1.0 /t2 ,0.286 /t3 }, {0.714 /t1 ,0.714 /t2 ,0.571 /t3 ,0.429 /t4 ,0.429 /t5 } .
(2)
This concept can be interpreted in the following way. Every object from the
extent is similar (with a certain degree of confidence) to an object from the
intent by at least the corresponding membership degree, e.g., object t1 is similar
to object t2 with confidence 1 (taken from the left membership degree of t1 ) by
at least 0.714 (taken form the right membership degree of t2 ), while object t3
is similar with t2 by at least 0.714 with confidence only 0.286. In particular if
on the extent side we consider objects with membership degree of 1 (>), e.g., t1
and t2 then we would find the similarity of all these objects to the rest of the
objects, thus, providing a good description for a cluster around these objects.
The set of fuzzy concepts is ordered such that (A, B) ≤ (X, Y ) iff A ⊆ X (or
dually B ⊇ Y ) forming a complete lattice, called fuzzy concept lattice.
3.2 Pattern Structures
A concept lattice L(G, M, I) is constructed from a (binary) formal context
(G, M, I) [1]. For non-binary data, such as sequences or graphs, lattices can
be constructed in the same way using pattern structures [3].
Definition 7. A pattern structure P is a triple (G, (D, u), δ), where G, D are
sets, called the set of objects and the set of descriptions, and δ : G → D maps an
object to a description. Respectively, (D, u) is a meet-semilattice on D w.r.t. u,
called similarity operation such that δ(G) := {δ(g) | g ∈ G} generates a complete
subsemilattice (Dδ , u) of (D, u).
For illustration, let us represent standard FCA in terms of pattern structures.
The set of objects G is preserved, the semilattice of descriptions is (℘(M ), ∩),
where ℘(M ) denotes the powerset of the set of attributes M , a description is
a subset of attributes and ∩ is the set-theoretic intersection. If x = {a, b, c}
and y = {a, c, d} then x u y = x ∩ y = {a, c}, and δ : G → ℘(M ) is given by
δ(g) = {m ∈ M | (g, m) ∈ I}.
Derivation operator for a pattern structure (G, (D, u), δ), relating sets of
objects and descriptions, is defined as follows:
l
A := δ(g), for A ⊆ G
g∈A
d := {g ∈ G | d v δ(g)}, for d ∈ D
Given a subset of objects A, A returns the description which is common
to all objects in A. Given a description d, d is the set of all objects whose
description subsumes d. The natural partial order (or subsumption order between
descriptions) v on D is defined w.r.t. the similarity operation u: c v d ⇔ cud = c
(in this case we say that c is subsumed by d). In the case of standard FCA the
natural partial order corresponds to the set-theoretical inclusion order, i.e., for
two sets of attributes x and y, x v y ⇔ x ⊆ y.
Definition 8. A pattern concept of a pattern structure (G, (D, u), δ) is a pair
(A, d), where A ⊆ G and d ∈ D such that A = d and d = A; A is called the
pattern extent and d is called the pattern intent.
As in standard FCA, a pattern concept corresponds to the maximal set of
objects A whose description subsumes the description d, where d is the maximal
common description of objects in A. The set of all pattern concepts is partially
ordered w.r.t. inclusion of extents or, dually, w.r.t. subsumption of pattern in-
tents within a concept lattice, these two anti-isomorphic orders form a lattice,
called pattern lattice.
Let us return to the example in Table 1b. Let us consider a special case of
pattern structures, a so-called Minimum Pattern Structure (MnPS), that is close
to interval pattern structures [5]. MnPS is based on the minimum of two numbers
as the similarity operation rather than on the convex hull of two intervals. We will
show that MnPS is well adapted for formalizing fuzzy FCA within the framework
of pattern structures.
In Table 1b we have the set G as both, a set of objects and a set of attributes.
Let us first consider only one attribute. Then the set of descriptions D is just
the interval [0, 1] of real numbers and the similarity operation between two de-
scriptions (numbers) is the minimum. When there are several attributes, the set
of descriptions is just an element of R|N | , where R is the set of real numbers and
N is the set of numerical attributes.
In particular, in our example the set of objects is G. The set D of descriptions
is R5 , since we have 5 numerical attributes. The mapping function δ is given in
Table 1b, e.g., δ(t2 ) = h0.714, 1, 0.571, 0.429, 0.429i. The similarity operation is
the component-wise minimum, e.g., the similarity between descriptions of t2 and
t3 is given by
{t2 } u {t3 } =
= h0.714, 1, 0.571, 0.429, 0.429i u h0.857, 0.571, 1, 0.286, 0.714i =
= hmin(0.714, 0.857), min(1, 0.571),
min(0.571, 1), min(0.429, 0.286), min(0.429, 0.714)i
= h0.714, 0.571, 0.571, 0.286, 0.429i
4 From Fuzzy FCA to Pattern Structures with Scaling
Let us now discuss a possible connection between fuzzy FCA and pattern struc-
tures. A certain connection was already proposed in [6]. In particular, every
crisply closed subset of objects is an extent of an interval pattern structure.
Here, crisply closed subset of objects means that the fuzzy closure of this set
contains no additional objects g with a membership degree coinciding with the
top of the residuated lattice, i.e., A(g) = >.
Here, we discuss a loss-less scaling from a fuzzy formal context (X, Y, I) to
a pattern structure, that allows a more efficient processing than the loss-less
scaling to crisp formal context and highlights another connection between fuzzy
FCA and pattern structures.
Since pattern structures can deal with any kind of descriptions, they should
take into account fuzziness on the intent side. However, for the extent side it
Table 4: Scaling of the fuzzy context from table Table 1b to a number-minimum
pattern structure.
t1 t2 t3 t4 t5 t1 t2 t3 t4 t5
ht1 , 1.000i 1.000 0.714 0.857 0.429 0.429 ···
ht1 , 0.857i 1.000 0.714 1.000 0.429 0.429 ht3 , 0.429i 1.000 1.000 1.000 0.286 1.000
ht1 , 0.714i 1.000 1.000 1.000 0.429 0.429 ···
··· ht4 , 1.000i 0.429 0.429 0.286 1.000 0.000
ht2 , 1.000i 0.714 1.000 0.571 0.429 0.429 ···
··· ht4 , 0.286i 1.000 1.000 1.000 1.000 0.000
ht2 , 0.571i 1.000 1.000 1.000 0.429 0.429 ···
··· ht5 , 1.000i 0.429 0.429 0.714 0.000 1.000
ht3 , 1.000i 0.857 0.571 1.000 0.286 0.714 ···
··· ht5 , 0.286i 1.000 1.000 1.000 1.000 0.000
is not so straightforward, since pattern structures deal only with crisp sets of
objects. Accordingly, we should somehow “scale” object sets, in order to express
fuzzy sets of objects.
4.1 On expressing Fuzziness on the Extent Side of Pattern
Structures
A natural way is to scale the object set X from a fuzzy context (X, Y, I) by sub-
stituting it with the direct product of the crisp set of objects and the residuated
lattice (the degrees of confidence), X × L. For every scaled object from this new
set, we should compute a description. Let us consider the scaled description for
the pair hx, li, where x ∈ X is an object and l ∈ L is the membership degree of
this object. The description of this element should correspond to the description
of the fuzzy set {l /x }, since hx, li is “a model of” this fuzzy set.
The derivation operator {l /x }↑ (y ∈ Y ) = {l /x }(x) I(x, y) = l I(x, y)
gives the description of the element hx, li and allows computing the fuzzy relation
I˜ between X × L and Y .
Let us return to our example. Let T be the set of transaction IDs. The scaled
fuzzy context is partially shown in Table 4. It consist of |T | · |L| = 5 · 7 =
35 objects, 5 attributes and the fuzzy relation between them. Every subset of
objects corresponds to a fuzzy set of objects by joining corresponding fuzzy
representation for every object. This is made precise in the next subsection.
4.2 Relation between fuzzy and pattern extents and intents
Let (X, Y, I) be a fuzzy context with a residuated lattice L and (G, D, δ) be
a pattern structure, where G is the scaled set of objects G = X × L. Let us
formally define the correspondence between fuzzy sets of objects and scaled sets
of objects.
Definition 9 (Object sets equivalence). A fuzzy object set A : X → L is
equivalent to a scaled object set N ⊆ G, denoted as A ∼ N , when
(∀hx, li ∈ G)(A(x) ≥ l ⇔ hx, li ∈ N )
Then object sets are equivalent when all scaled objects with membership
degree smaller than or equal to A(x) (w.r.t. the residuated lattice) are present in
the scaled object set. For example, the fuzzy set {0.286 /t1 ,0.429 /t4 } is equivalent
to the scaled set {ht1 , 0.286i, ht4 , 0.429i, ht4 , 0.286i}3 , where hg, li ∈ X × L is an
element of the direct product of the set of objects and the residuated lattice.
Given a scaled fuzzy context (X × L, Y, I) ˜ we can process it as a minimum
pattern structure (X × L, D, δ), where D = L|Y | is a tuple of elements from the
residuated lattice L and the semilattice operation is given by the component-
wise infimum of L. In particular, we have discussed that for the numerical case,
the similarity operation is the component-wise minimum. Indeed, fuzziness on
the extent side is expressed by means of scaled object sets, and fuzziness on
the intent side is directly processed by the pattern structure. Let us discuss the
correspondence between fuzzy intents and patterns.
Definition 10. A fuzzy attribute set B : Y → L is equivalent to a pattern
d ∈ D, written as B ∼ d, iff (∀y ∈ Y )(B(y) = d(y)), where d(y) is the value of
the tuple d corresponding to the attribute y.
A fuzzy attribute set B is equivalent to a pattern d iff for any attribute y ∈ Y ,
the membership degree B(y) in the fuzzy set is equal to the value in the pattern
tuple in the position corresponding to the attribute y, e.g., the pattern h0.5, 0.7i
corresponds to the fuzzy set {0.5 /y1 ,0.7 /y2 }.
It should be noticed that the definition of equality between fuzzy sets of
attributes and patterns is a bijection, while there are scaled sets of objects that
have no equivalent fuzzy set of objects. Indeed, there is no equivalent fuzzy
set to the scaled set {ht1 , 0.286i, ht4 , 0.429i}, since according to Definition 9 all
hx, li such that A(x) ≥ l should be in this set. And since we have ht4 , 0.429i in
this set, we should also have ht4 , 0.286i in the set. We can notice here that in
our particular example the residuated lattice has only the element 0.286 that is
smaller than 0.429. By contrast, if we take the real interval [0, 1], then all points
smaller than 0.429 should be added to the scaled set.
Let us define equivalence classes of scaled sets of objects in order to have a
bijection between the equivalence classes and the fuzzy sets of objects.
Definition 11. A scaled object set N ⊆ G is complete iff a scaled object hx ∈
X, l ∈ Li belongs to N , then (∀l∗ ∈ L, l∗ ≤ l)hx, l∗ i ∈ N .
It can be checked that for any scaled object set N ⊆ G there is only one
minimal complete superset of N . Let us denote this complete set by φ(N ).
For example, the set N = {ht1 , 0.286i, ht4 , 0.429i} is not complete, since the
scaled object ht4 , 0.286i is not in N .
By contrast, Nc = φ(N ) = {ht1 , 0.286i, ht4 , 0.429i, ht4 , 0.286i} is complete.
Moreover, it can be seen that this set is equivalent to {0.286 /t1 ,0.429 /t4 } according
to Definition 9. Furthermore, it can be checked, that any complete scaled set of
objects is equivalent to a fuzzy set and accordingly the function φ(·) defines the
required equivalence classes.
3
We notice that ht4 , 0.429i and ht4 , 0.286i are two different scaled objects.
4.3 Isomorphism of fuzzy and pattern lattices
In this subsection we show that our scaling procedure is correct. And the result-
ing pattern lattice and the fuzzy lattice are isomorphic. Moreover, the extents
and intents of these lattices are connected by means of Definitions 9 and 10.
The first lemma (a standard property of residuated lattices) shows that fuzzy
implications are related if their premises are comparable.
Lemma 1 If there are l1 , l2 , l ∈ L such that l1 ≤ l2 then
l1 l ≥ l2 l
Proof. Let l2 l = r then according to Def. 1:
(∀f ∈ L, f ≤ r)(f ⊗ l2 ≤ l) ⇔ (∀f ≤ r)(l2 ⊗ f ≤ l)
⇔ (∀f ≤ r)(f l ≥ l2 ≥ l1 ) ⇔ (∀f ≤ r)(l1 l ≥ f ) ⇒ l1 l ≥ r.
Let us now show that starting from two (fuzzy and scaled) equivalent sets of
objects the resulting descriptions are also equivalent.
Lemma 2 Given a fuzzy set of objects A : X → L and a scaled set of objects
N ⊆ G, such that A ∼ φ(N ), we have A↑ ∼ N .
Proof. Consider
d the value of the pattern tuple N corresponding to an attribute
y: N (y) = ∀g∈N δ(g) (y). The semilattice operation of the minimum pattern
structure corresponds to the infimum in the residuated lattice:
^ ^
N (y) = ˜
I(hx, li, y) = l I(x, y) =
∀hx,li∈N ∀hx,li∈N
^ ^
= A(x) I(x, y) ∧ l I(x, y) =
∀x∈X ∀hx,li∈N :l