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 standard 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.
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 [
Pattern structures is another extension of FCA that allows processing complex 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 Structure" (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 scaling 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 formalism 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.
The rest of the paper is organized as follows. Section 2 describes a running example. Later, in Section 3 we introduce main de nitions 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
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 the fraction of di erent items shared by two baskets Dist(t1; t2) = jt01+t02j and jMj Sim(t1; t2) = 1 Dist(t1; t2), where operation '+' between sets is an exclusive OR (a so-called XOR or the symmetric di erence, i.e., A+B = (AnB)[(B nA)). 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 di erent 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
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 . There are a number of extensions of Formal Concept Analysis (FCA)
for dealing with complexity of descriptions, e.g., pattern structures [
Fuzzy FCA works with fuzzy logic instead of crisp-logic, used in standard FCA.
There are several generalizations of FCA to the fuzzy case [
De nition 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 8a(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.
An important residuated lattice based on a linearly ordered set is Goodel residuated lattice, which is used in examples of this paper. In Goodel residuated lattices the fuzzzy implication is de ed as following: a b = > a b b a > b (1)
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 De nition 1 it is required that the fuzzy implication is adjoint (related) with an -operation. For Goodel residuated lattices the fuzzy implication is adjoint with a b = min(a; b).
A fuzzy dataset is encoded by means of a fuzzy context as de ned below.
X Y ! L, for some residuated lattice L.
Y is a set of attributes, I is a fuzzy relation, I : X Y ! L.
Let us now de ne what is a fuzzy set, the next building block of fuzzy FCA. De nition 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 element of the residuated lattice. A fuzzy set is denoted as fli2L=xi2X g, where S xi = X, and for simplicity elements A(x 2 X) = ? are omitted.
In the fuzzy case of FCA one also de nes Galois connections between a fuzzy set of objects A : X ! L and a fuzzy set of attributes B : Y ! L.
fuzzy set of objects A : X ! L, a fuzzy set of attributes B : Y ! L, the fuzzy membership for object x 2 X and for attribute y 2 Y in the corresponding sets A" and B# are as follows:
A"(y) = B#(x) =
^ (A(x) 8x2X ^ (B(y) 8y2Y
A : X ! L and B is a fuzzy set of attributes B : Y ! L, such that A" = B and A = B#.
In particular there is the following fuzzy concept.
f1:0=t1 ;1:0 =t2 ;0:286 =t3 g; f0:714=t1 ;0:714 =t2 ;0:571 =t3 ;0:429 =t4 ;0:429 =t5 g : The set of fuzzy concepts is ordered such that (A; B) (X; Y ) i A dually B Y ) forming a complete lattice, called fuzzy concept lattice. (2) X (or 3.2
A concept lattice L(G; M; I) is constructed from a (binary) formal context
(G; M; I) [
De nition 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) := f (g) j g 2 Gg generates a complete subsemilattice (D ; u) of (D; u).
Derivation operator for a pattern structure (G; (D; u); ), relating sets of objects and descriptions, is de ned as follows:
A := l (g);
g2A d := fg 2 G j d v (g)g; for A
G for d 2 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 de ned w.r.t. the similarity operation u: c v d , cud = c (in this case we say that c is subsumed by d).
De nition 8. A pattern concept of a pattern structure (G; (D; u); ) is a pair (A; d), where A G and d 2 D such that A = d and d = A; A is called the pattern extent and d is called the pattern intent.
The set of all pattern concepts is partially ordered w.r.t. inclusion of extents or, dually, w.r.t. subsumption of pattern intents 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 [
In Table 1b we have the set G as both, a set of objects and a set of attributes. Let us rst 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 descriptions (numbers) is the minimum. When there are several attributes, the set of descriptions is just an element of RjNj, 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 ft2g u ft3g = = 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); = h0:714; 0:571; 0:571; 0:286; 0:429i
min(0:571; 1); min(0:429; 0:286); min(0:429; 0:714)i 4
Let us now discuss a possible connection between fuzzy FCA and pattern
structures. A certain connection was already proposed in [
Here, we discuss a loss-less scaling from a fuzzy formal context (X; Y; I) to a pattern structure, that allows a more e cient 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 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. A natural way is to scale the object set X from a fuzzy context (X; Y; I) by substituting it with the direct product of the crisp set of objects and the residuated lattice (the degrees of con dence), 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 2 X is an object and l 2 L is the membership degree of this object. The description of this element should correspond to the description of the fuzzy set fl=xg, since hx; li is \a model of" this fuzzy set.
The derivation operator fl=xg"(y 2 Y ) = fl=xg(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 2. It consist of jT j jLj = 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.
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 de ne the correspondence between fuzzy sets of objects and scaled sets of objects.
equivalent to a scaled object set N G, denoted as A N , when ! L is (8hx; li 2 G)(A(x)
l , hx; li 2 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 f0:286=t1 ;0:429 =t4 g is equivalent to the scaled set fht1; 0:286i; ht4; 0:429i; ht4; 0:286ig3, where hg; li 2 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 = LjY j is a tuple of elements from the residuated lattice L and the semilattice operation is given by the componentwise in mum 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.
De nition 10. A fuzzy attribute set B : Y ! L is equivalent to a pattern d 2 D, written as B d, i (8y 2 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 i for any attribute y 2 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 f0:5=y1 ;0:7 =y2 g.
It should be noticed that the de nition 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 fht1; 0:286i; ht4; 0:429ig, since according to De nition 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 de ne equivalence classes of scaled sets of objects in order to have a bijection between the equivalence classes and the fuzzy sets of objects.
X; l 2 Li belongs to N , then (8l 2 L; l G is complete i a scaled object hx 2 l)hx; l i 2 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 = fht1; 0:286i; ht4; 0:429ig is not complete, since the scaled object ht4; 0:286i is not in N .
By contrast, Nc = (N ) = fht1; 0:286i; ht4; 0:429i; ht4; 0:286ig is complete. Moreover, it can be seen that this set is equivalent to f0:286=t1 ;0:429 =t4 g according to De nition 9. Furthermore, it can be checked, that any complete scaled set of objects is equivalent to a fuzzy set and accordingly the function ( ) de nes the required equivalence classes. 3 We notice that ht4; 0:429i and ht4; 0:286i are two di erent scaled objects. In this subsection we show that our scaling procedure is correct. And the resulting pattern lattice and the fuzzy lattice are isomorphic. Moreover, the extents and intents of these lattices are connected by means of De nitions 9 and 10. The rst 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 2 L such that l1 l2 then l1 l l2 l Proof. Let l2
l = r then according to Def. 1: (8f 2 L; f , (8f
r)(f r)(f l
Lemma 2 Given a fuzzy set of objects A : X ! L and a scaled set of objects
Proof. Consider the value of the pattern tuple N corresponding to an attribute y: N (y) = d8g2N (g) (y). The semilattice operation of the minimum pattern structure corresponds to the in mum in the residuated lattice:
Finally let us show, that starting from equivalent fuzzy set of attributes and pattern, the sets of objects given by the derivation operators are also equivalent. Lemma 3 Given a fuzzy set of attributes B : Y ! L and a pattern d 2 D, such that B d, we have B# d .
Proof. Let us study when object hx 2 X; l 2 Li can be included into d . hx 2 X; l 2 Li 2 d , (hx; li) w d , (8y 2 Y )( (hx; li)(y) , (8y 2 Y )(l I(x; y) d(y)) , (8y 2 Y )(d(y) l
I(x; y)) , (8y 2 Y )(l I(x; y) l) d(y)) d(y)
pattern lattice Lp corresponding to the pattern structure (G; D; ), where G = X L, D = LjY j with component-wise minimum as the semilattice operation, and (hx 2 X; l 2 Li)(y) = l I(x; y) are isomorphic. The extents and intents of the corresponding concepts are equivalent.
Proof. Let us show, that for any concept in one lattice there is a concept in the other lattice with equivalent extents and intents. Lemmas 2 and 3 are symmetric w.r.t. the type of extents and intents. Accordingly, we can just denote by L1 and L2 fuzzy and pattern lattices and prove the theorem in both directions. If we take an intent i1 from L1, we can always nd an equivalent pattern p (for simplicity, fuzzy set of attributes is also referred as a pattern). Applying appropriate derivation operators to i1 and p we get equivalent sets of objects according to Lemma 3. Both sets are closed and are extents of L1 and L2. Applying derivation operators to the extents we get equivalent intents according to Lemma 2. Thus, for any concept of L1 there is an equivalent concept in L2 and vice versa. 4.4
Let us demonstrate how the theorem works in the running example. The proof is based on search of concepts with equivalent extents and intents. Let us nd the scaled concept corresponding to the fuzzy concept (2). In the theorem we start from the intent. It can be seen that f0:714=t1 ;0:714 =t2 ;0:571 =t3 ;0:429 =t4 ;0:429 =t5 g h0:714; 0:714; 0:571; 0:429; 0:429i: (3) For the moment we are not sure that the pattern on the right side is an intent. Accordingly we apply derivation operators to the left and right hand sides and according to Lemma 3 the resulting object sets should be equivalent. Indeed, f1=t1 ;1 =t2 ;0:286=t3 g
fht1; 1i; ht1; 0:857i; : : : ; ht1; 0:286i; ht2; 1i; : : : ht2; 0:286i; ht3; 0:286ig:
On the left side we have the extent of the concept, while on the right side we
have a closed scaled set of objects, since the result of the derivation operator is
always closed. If we apply the derivation operators to these two sets of objects,
we have equivalent patterns according to Lemma 2. In fact we have exactly the
patterns from (3). Thus, we have found the scaled concept corresponding to
the fuzzy concept. Similarly, we can start from a scaled concept and nd the
corresponding fuzzy concept.
In this paper we highlighted the relation between fuzzy FCA and pattern
structures. Our result is related to the work of [
The introduced scaling procedure can be useful, rst, for migrating results between pattern structure community and fuzzy FCA community, and, second, for e cient implementation of software dealing with both pattern structures and fuzzy FCA at the same time.
Finally, we notice that such a work naturally raises (as it was already
mentioned in [