Since its development attribute exploration was successfully applied in di erent elds, proving itself as a strong tool for knowledge acquisition. However, the disadvantage of this method is that it can be applied only for binary data. The growing number of applications of fuzzy logic in numerous domains including formal concept analysis makes it a natural wish to generalise the powerful technique of attribute exploration for fuzzy data. It is this paper's purpose to ful ll this wish and present a generalisation of attribute exploration to the fuzzy setting.
Attribute exploration, as introduced in [
Attribute exploration was successfully applied in di erent areas of research, for a brief overview see Subsection 2.1.
Formal fuzzy concept analysis goes back to [
The article is structured as follows: In Section 2 we give short introductions to attribute exploration in the crisp setting, fuzzy sets and fuzzy logic, formal fuzzy concept analysis and implications in such a setting. Section 3 rst presents how the stem bases can be computed in a fuzzy setting using the globalisation and afterwards it focuses on attribute exploration in such a setting. In Section 4 we treat the same subject as in the section before but this time we use a general hedge in the residuated lattice for the exploration. The last section contains concluding remarks and further topics of research. 2 2.1
We assume basic familiarities with Formal Concept Analysis and refer the reader
to [
Attribute exploration ([
The following proposition justi es why we do not have to reconsider the
already con rmed implications:
Proposition 1. ([
As mentioned in the introductory section, attribute exploration was
successfully applied in both theoretical and practical research domains. On the one hand
it facilitated the discovery of implications between properties of mathematical
structures, see for example [7{9]. On the other hand it was also used in real-life
scenarios, for instance in civil engineering ([
The algorithm is implemented in di erent formal concept analytical tools, as for example in ConExp1 and Conexp-clj2.
There are also further variants of attribute exploration, for instance attribute
exploration with background knowledge for the case that the user knows in
advance some implications between the attributes that hold ([
In this subsection we present some basics about fuzzy sets and fuzzy logic. The
interested reader may nd more details for instance in [
A complete residuated lattice with truth-stressing hedge (shortly,
a hedge) is an algebra L := (L; ^; _; ; !; ; 0; 1) such that: (L; ^; _; 0; 1) is a
complete lattice; (L; ; 1) is a commutative monoid; 0 is the least and 1 the
greatest element; the adjointness property, i.e., a b c , a b ! c, holds for
all a; b; c 2 L. The hedge is a unary operation on L satisfying the following:
i) a a,
ii) (a ! b) a ! b ,
iii) a = a ,
iv) Vi2I ai = (Vi2I ai) ,
for every a; b; ai 2 L (i 2 I). Elements of L are called truth degrees, and !
are (truth functions of) \fuzzy conjunction" and \fuzzy implication". The hedge
is a (truth function of) logical connective \very true", see [
A common choice of L is a structure with L = [0; 1], ^ and _ being minimum and maximum, being a left-continuous t-norm with the corresponding !. The 1 http://conexp.sourceforge.net/ 2 http://daniel.kxpq.de/math/conexp-clj/ three most important pairs of adjoint operations on the unit interval are:
b := max(0; a + b 1) with a ! b := min(1; 1 a + b);
Product: a a b := min(a; b) with a ! b := b := ab with a ! b := 1; a b=a; a 1; a b; a bb : bb ; Typical examples for the hedge are the identity, i.e., a := a for all a 2 L, and the globalization, i.e., a := 0 for all a 2 L n f1g and a := 1 if and only if a = 1.
Let L be the structure of truth degrees. A fuzzy set (L-set) A in a universe U is a mapping A : U ! L, A(u) being interpreted as \the degree to which u belongs to A". If U = fu1; : : : ; ung, then A can be denoted by A = fa1 =u1; : : : ;an =ung meaning that A(ui) equals ai for each i 2 f1; : : : ; ng. Let LU denote the collection of all fuzzy sets in U . The operations with fuzzy sets are de ned component-wise. For example, the intersection of fuzzy sets A; B 2 LU is a fuzzy set A \ B in U such that (A \ B)(u) = A(u) ^ B(u) for each u 2 U , etc. Binary fuzzy relations (L-relations) between G and M can be thought of as fuzzy sets in the universe G M . For A; B 2 LU , the subsethood degree is de ned as
S(A; B) := ^ (A(u) ! B(u)); u2U which generalises the classical subsethood relation . Therefore, S(A; B) represents a degree to which A is a subset of B. In particular, we write A B i S(A; B) = 1. 2.3
In the following we give brief introductions to Formal Fuzzy Concept Analysis
[
A triple (G; M; I) is called a formal fuzzy context if I : G M ! L is a fuzzy relation between the sets G and M and L is the support set of some residuated lattice. Elements from G and M are called objects and attributes, respectively. The fuzzy relation I assigns to each g 2 G and each m 2 M the truth degree I(g; m) 2 L to which the object g has the attribute m. For fuzzy sets A 2 LG and B 2 LM the derivation operators are de ned by A"(m) := ^ (A(g) g2G ! I(g; m)); B#(g) := ^ (B(m) ! I(g; m));
(1)
m2M
for g 2 G and m 2 M . Then, A"(m) is the truth degree of the statement \m
is shared by all objects from A" and B#(g) is the truth degree of \g has all
attributes from B". The operators ";# form a so-called Galois connection with
hedges ([
The fuzzy lectic order ([
L we de ne B
(i; j) := ((B \ f1; 2; : : : ; i 1g) [ faj =ig)#": Furthermore, for B; C 2 LM de ne B <(i;j) C :() B \ f1; : : : ; i 1g = C \ f1; : : : ; i 1g and B(i) < C(i) = aj: We say that B is lectically smaller than C, written B < C, if B <(i;j) C for some (i; j). As in the crisp case we have that B+ := B (i; j) is the least intent which is greater than a given B with respect to < and (i; j) is the greatest with B <(i;j) B (i; j).
Example 1. Consider the formal fuzzy context (G; M; I) given in Figure 1. Using the Lukasiewicz logic with the identity as hedge we obtain 15 formal fuzzy concepts. For example (fM o; T;0:5 =W g; fc; rg) is a fuzzy concept. We could name it the concept of cold and rainy days because of its intent. Then, Monday, Tuesday and partially Wednesday belong to this concept, i.e., they are cold and rainy days. Another example is (f0:5=W; T h; F g; fwg) which corresponds to warm days. Yet another example are the warm and partially rainy days given by (f0:5=W; T h;0:5 =F g; fw;0:5 =rg). The fuzzy concept lattice is displayed on the left side in Figure 2. For better legibility we did not use all the labels. Using the globalisation instead of the identity, we obtain 10 formal fuzzy concepts which are displayed on the right in Figure 2. The concepts obtained through the globalisation need not be a subset of those obtained with the identity. In this example this case does not appear. Using the Godel structure one obtains 13 concepts with the identity and 10 with the globalisation. 2.4
As already mentioned, fuzzy implications were studied in a series of papers by
R. Belohlavek and V. Vychodil, for instance in [
Tuesday (T) Wednesday (W) Thursday (Th)
Friday (F) warm (w) cold (c) rainy (r) 0 1 1 0 1 1 0:5 0:5 1 1 0 0:5 1 0 0 Mo, T
W 0:5=w w F Th
A fuzzy attribute implication (over the attribute set M ) is an expression A ) B, where A; B 2 LM . The verbal meaning of A ) B is: \if it is (very) true that an object has all attributes from A, then it also has all attributes from B". The notions \being very true", \to have an attribute", and logical connective \if-then" are determined by the chosen L. For a fuzzy set N 2 LM of attributes, the degree jjA ) BjjN 2 L to which A ) B is valid in N is de ned as jjA ) BjjN := S(A; N ) ! S(B; N ): If N is the fuzzy set of all attributes of an object g, then jjA ) BjjN is the truth degree to which A ) B holds for g. For a set N LM , the degree jjA ) BjjN 2 L to which the implication A ) B holds in N is de ned by jjA ) BjjN := ^ jjA ) BjjN :
N2N For a fuzzy context (G; M; I), let Ig 2 LM (g 2 G) be a fuzzy set of attributes such that Ig(m) = I(g; m) for each m 2 M . Clearly, Ig corresponds to the row labelled g in (G; M; I). The degree jjA ) Bjj(G;M;I) 2 L to which A ) B holds in (each row of) K = (G; M; I) is de ned by
jjA ) BjjK = jjA ) Bjj(G;M;I) := jjA ) BjjN ; where N := fIg j g 2 Gg. Denote by
Int(G ; M; I) := fB 2 LM j (A; B) 2 B(G ; M; I) for some Ag the set of all intents of B(G ; M; I). Since N 2 LM is the intent of some concept if and only if N = N #", we have Int(G ; M; I) = fN 2 LM j N = N #"g. The degree jjA ) BjjB(G ;M;I) 2 L to which A ) B holds in (the intents of) B(G ; M; I) is de ned by
jjA ) BjjB(G ;M;I) := jjA ) BjjInt(G ;M;I):
Lemma 1. ([
jjA ) Bjj(G;M;I) = jjA ) BjjB(G ;M;I) = S(B; A#") for each fuzzy attribute implication A ) B.
Example 2. Consider once again the fuzzy context given in Figure 1. Using the Lukasiewicz logic and the globalisation as the hedge we have jjc ) rjj(G;M;I) = 1, i.e., this is a true implication. However, in the fuzzy case, there are implications which are valid to a certain degree di erent from 1, for instance we have the implication jjc ) f0:5=w; rgjj(G;M;I) = 0:5. We obtain the same truth value for these implications also by using the identity. Consider the Godel logic with the globalisation. For example, we have the implication jjw; r ) cjj(G;M;I) = 1 but using the identity this implication holds with the truth value 0. This is due to the fact that we have fw; rg#" = fw; r; cg with the globalisation and fw; rg#" = fw; rg with the identity.
Due to the large number of implications in a fuzzy and even in a crisp formal
context, one is interested in the stem base of the implications. The stem base
is a set of implications which is non-redundant and complete. The problem for
the fuzzy case was studied in [
Let T be a set of fuzzy attribute implications. A fuzzy attribute set N 2 LM is called a model of T if jjA ) BjjN = 1 for each A ) B 2 T . The set of all models of T is denoted by M od (T ), i.e.,
M od (T ) := fN 2 LM j N is a model of T g:
The degree jjA ) BjjT 2 L to which A ) B semantically follows from T is
de ned by jjA ) BjjT := jjA ) BjjMod(T ). T is called complete (in (G; M; I))
if jjA ) BjjT = jjA ) Bjj(G;M;I) for each A ) B. If T is complete and no
proper subset of T is complete, then T is called a non-redundant basis.
Theorem 1. ([
M od (T ) = Int(G ; M; I).
As in the crisp case the stem base of a given fuzzy context can be obtained through the pseudo-intents.
LM is called a system of pseudo-intents if for each De nition 1. P P 2 LM we have:
P 2 P () (P 6= P #" and jjQ ) Q#"jjP = 1 for each Q 2 P with Q 6= P ):
For each (G; M; I) there exists a unique system of pseudo-intents, if is the
globalisation and M is nite (this does not hold for the other hedges in general).
Theorem 2. ([
Attribute exploration is a very powerful tool. However, its theoretical basis lies in Proposition 1 which represents its key to success. Thus, the crucial step is to generalise this proposition to the fuzzy setting. After developing the theoretical ingredients for a successful attribute exploration in a fuzzy setting, we turn our attention to its practical parts. First, we develop an appropriate algorithm for this technique and afterwards illustrate the method by an example.
In case we choose for the globalisation, then the formalisation of pseudointents from De nition 1 becomes: P LM is a system of pseudo-intents if P 2 P () (P 6= P #" and Q#"
P for each Q 2 P with Q & P ):
(2)
Theorem 3. ([
For Z 2 LM we put
S(A; Z) j A ) B 2 T and A 6= Zg; ZT := Z [ [fB ZT0 := Z; ZTn := (ZTn 1 )T ; for n
1;
where B S(A; Z) is computed component-wise, and we de ne an operator
clT on L-sets in M by
clT (Z) :=
1
[ ZTn :
n=0
Theorem 4. ([
is the globalisation, then clT is an L -closure operator fclT (Z) j Z 2 LM g = P [ Int(X ; Y; I):
According to this theorem, if is the globalisation, then we can obtain all
intents and all pseudo-intents of a given fuzzy context by computing the xed
points of clT . In [
Proof. Easy, by induction on the number of pseudo-intents in P.
With this result we are able to generalise the attribute exploration algorithm to the fuzzy setting, as displayed below. The rst intent or pseudo intent is the empty set. If it is an intent, add it to the set of intents of the context. Otherwise, ask the expert whether the implication is true in general. If so, add this implication to the stem base else ask for a counterexample and add it to the context (line 2 6). Until A is di erent from the whole attribute set, repeat the following steps: Search for the largest attribute i in M with its largest value l such that A(i) < l. For this attribute compute its closure with respect to the clT -closure operator and check whether the result is the lectically next intent or pseudo-intent (line 9 12). Thereby, A & i := A \ f1; : : : ; i 1g. If the result is an intent, add it to the set of intents (line 13 14), otherwise ask the user whether the implication provided by the pseudo-intent holds. If the implication holds, add it to the stem base otherwise ask the user for a counterexample (line 15 17).
The algorithm generates interactively the stem base of the formal fuzzy context. As in the crisp case we enumerate the intents and pseudo-intents in the lectic order. Hence, we go through the list of all such elements. Due to Proposition 2 we are allowed to extend the context by objects whose object intents respect the already con rmed implications. This way, the pseudo-intents already used in the stem base do not change. Hence, the algorithm is sound and correct. Example 3. We want to explore the size and distance of the planets. We include some of them into the object set and obtain the context given in Figure 4. In this example we will be using the Lukasiewicz logic with the globalisation as hedge.
small (s) large (l) far (f) near (n) Earth Mars Pluto This is a true implication and we con rm it. The next pseudo-intent is ff;0:5 =ng which yields the following question:
Objects having attribute f and n to degree 1 and 0:5, respectively, also have attribute l to degree 1? This is a true implication and we con rm it. The algorithm proceeds with Objects having attribute l to degree 0:5 also have the attributes
l; f; n to degree 1; 1; 0:5, respectively? This implication is not true for our planet system and we give a counterexample:
0:5=l ) f; l; f )0:5 =n; 0:5=s;0:5 =n ) s; n; s;0:5 =l; f ) l; n: And the attribute exploration has stopped. Now we have an extended formal fuzzy context, namely the one containing Jupiter and Uranus besides the objects given in Figure 4. Note that we did not have to include all the planets into the object set, just a representative part of them. The other planets with their attributes are displayed in Figure 5. These objects contain just redundant information and the knowledge provided by them is already incorporated into the stem base of the extended context.
small (s) large (l) far (f) near (n) Mercury Venus Saturn Neptune As the title of this section suggests, we will now turn our attention to attribute exploration with general hedges. After introducing the necessary background information, we will focus on the exploration. As it turns out, there are several obstacles that make a straight-forward generalisation of attribute exploration in such a setting impossible. At the end of the section we will discuss which approaches may lead to a successful exploration. However, it is also an open question whether an exploration in such a setting is desirable.
The computation of the systems of pseudo-intents for general hedges was
studied in [
V j P 6= Q and jjQ ) Q#"jjP 6= 1g: (3) (4) In case of a non-empty V , G := (V; E [ E 1) is a graph. For Q 2 V , P de ne the following subsets of V :
V P red (Q) := fP 2 V j (P; Q) 2 Eg; P red (P) := [ P red (Q):
Q2P Described verbally, P red (Q) is the set of all elements from V which are predecessors of Q (in E). P red (P) is the set of all predecessors of any Q 2 P.
We will compute the systems of pseudo-intents through maximal independent
sets. Therefore, the following result is useful:
Lemma 2. ([
LM . If V n P =P red (P), then P is a maximal
The next theorem characterises the systems of pseudo-intents of a fuzzy
context using general hedges:
Theorem 5. ([
It is well-known that the maximal independent sets of a graph can be e
ciently enumerated in lexicographic order with only polynomial delay between
the output of two successive independent sets ([
In the following we will exemplify the computation of the systems of pseudointents. Afterwards, we illustrate how an attribute exploration with general hedge could be performed.
Example 4. We start with a very simple example. Let (fgg; fa; bg; I) be the formal fuzzy context with I(g; a) = 0:5 and I(g; b) = 0. Further, we use the three-element Lukasiewicz chain with being the identity. First, we compute V as given by (3) and obtain
V = ff0:5=a;0:5 =bg; f0:5=bg; fg; f0:5=a; bg; fbg; fagg: Afterwards, we compute the binary relation E as given by (4) which is displayed in Figure 6. Considering the undirected diagram of Figure 6 we obtain the graph G. There, we have four maximal independent sets, namely
P1 = ffg; f0:5=a; bg; fagg; P2 = ff0:5=bg; fagg; P3 = ffbg; fagg;
P4 = ff0:5=a;0:5 =bg; fagg: P1 and P3 do not satisfy the condition of Theorem 5 and are therefore not fbg
fag fg systems of pseudo-intents. P2 and P4 do satisfy this condition and hence they are systems of pseudo-intents yielding the stem bases displayed in Figure 7.
Objects having attribute b to degree 0:5 also have attribute a to degree 1? Let us answer this question a rmatively. The next question is:
Objects having attribute a to degree 1 also have attribute b to degree 0:5? We deny this implication and provide a counterexample, namely the object h with I(h; a) = 1 and I(h; b) = 0. This counterexample obviously respects the already con rmed implication so the context is extended by the new object h. For this extended context we can compute the sets V and E. The binary relation f0:5=a;0:5 =bg f0:5=bg fg fbg E for the extended context is given in Figure 8. From this graph we obtain four maximal independent sets, three of which form systems of pseudo-intents. The stem bases which they induce are displayed in Figure 9. At the beginning we
T2p (5) 0:5=b ) a (6) (7)
T2pp fg )0:5 =a 0:5=a; b ) b
T2ppp (8)
fbg ) a have con rmed implication (1) from Figure 7. However, this implication is now not present any more in the stem bases T2pp and T2ppp. This is also re ected in the stem base T4. Even though the counterexample respects implication (3), the pseudo-intent belonging to this implication also disappears.
Concluding, by extending the context with objects which respect the already con rmed implications, the latter may disappear from the stem base of the extended context. Hence, we do not have an analogon of Proposition 2 for general hedges.
The attribute exploration with general hedges raises a lot of questions and open problems. First of all it is unclear whether such an exploration is desirable. We have more than one stem base for a context. These bases are equally powerful with respect to their expressiveness. The major problem however is how to perform an attribute exploration successfully. It is an open problem how to enumerate the pseudo-intents obtained by general hedges such that the already con rmed implication still remain in the stem base of the extended context. One could for instance make some constraints on the counterexamples. However, such an approach is not in the spirit of attribute exploration. 5
We presented a generalisation of attribute exploration to the fuzzy setting. The problem is two-sided. If one uses the globalisation in the residuated lattice, the stem base is unique. For such a setting the results regarding the exploration from the crisp case can be transferred without problems and one can perform successfully an attribute exploration with attributes having fuzzy values. Using hedges di erent from the globalisation one obtains more than one system of pseudo-intents. This alone would not cause such a big problem. The major di culty comes with the fact that the already con rmed pseudo-intents are not necessarily pseudo-intents of the extended context. This is therefore an open problem, how to perform an attribute exploration using a general hedge.
In the future we will focus on the problem regarding the general hedge and on extensions of this method, as for instance on fuzzy attribute exploration with background knowledge. There, the user can enter in advance some implications which he/she knows to hold between the attributes. Using such background knowledge one usually has to provide less examples and answer to fewer questions.
We are expecting that the method will have many practical applications, as its crisp variant has. Therefore, we will also focus on applications using attribute exploration in a fuzzy setting.