Removing redundant information in databases is a key issue in Formal Concept Analysis. This paper introduces several results on the attributes that generate the meet-irreducible elements of a multi-adjoint concept lattice, in order to provide di erent properties of the reducts in this framework. Moreover, the reducts of particular multi-adjoint concept lattices have been computed in di erent examples.
Attribute reduction is an important research topic in Formal Concept Analysis
(FCA) [
Di erent fuzzy extensions of FCA have been introduced [
Due to the relation between the given attribute classi cation and the meetirreducible elements of a concept lattice, this paper studies the attributes that generate the meet-irreducible elements of a multi-adjoint concept lattice. From the introduced results, di erent properties of the corresponding reducts have been presented. In addition, two examples in which the reducts of particular multi-adjoint concept lattices have been included. 2
A brief summary with the basic notions and results related to attribute classi cation in the fuzzy framework of multi-adjoint concept lattices is presented. 2.1
First of all, we will recall the de nitions of multi-adjoint frame and context where
the operators to carry out the calculus are adjoint triples [
De nition 1. A multi-adjoint frame is a tuple (L1; L2; P; &1; : : : ; &n) where (L1; 1) and (L2; 2) are complete lattices, (P; ) is a poset and (&i; .i; -i) is an adjoint triple with respect to L1; L2; P , for all i 2 f1; : : : ; ng. De nition 2. Let (L1; L2; P; &1; : : : ; &n) be a multi-adjoint frame, a context is a tuple (A; B; R; ) such that A and B are nonempty sets (usually interpreted as attributes and objects, respectively), R is a P -fuzzy relation R : A B ! P and : A B ! f1; : : : ; ng is a mapping which associates any element in A B with some particular adjoint triple in the frame.
In order to introduce the multi-adjoint concept lattice associated with this
frame and this context, two concept-forming operators " : L2B ! L1A and # : L1A !
L2B are considered. These operators are de ned as
g"(a) = inffR(a; b) . (a;b) g(b) j b 2 Bg
f #(b) = inffR(a; b) - (a;b) f (a) j a 2 Ag
(1)
(2)
for all g 2 L2B, f 2 L1A and a 2 A, b 2 B, where L2B and L1A denote the set
of mappings g : B ! L2 and f : A ! L1, respectively, which form a Galois
connection [
By using the concept-forming operators, a multi-adjoint concept is de ned as a pair hg; f i with g 2 L2B, f 2 L1A satisfying g" = f and f # = g. The fuzzy subsets of objects g (resp. fuzzy subsets of attributes f ) are called extensions (resp. intensions ) of the concepts.
De nition 3. The multi-adjoint concept lattice associated with a multi-adjoint frame (L1; L2; P; &1; : : : ; &n) and a context (A; B; R; ) given, is the set
M = fhg; f i j g 2 L2B; f 2 L1A and g" = f; f # = gg where the ordering is de ned by hg1; f1i alently f2 1 f1). hg2; f2i if and only if g1 2 g2 (equiv
A classi cation of the attributes of a multi-adjoint context from a
characterization of the ^-irreducible elements of the corresponding concept lattice (M; )
was given in [
De nition 4. For each a 2 A, the fuzzy subsets of attributes a;x 2 L1A de ned,
for all x 2 L1, as
a;x(a0) =
x if a0 = a
?1 if a0 6= a
will be called fuzzy-attributes, where ?1 is the minimum element in L1. The set
of all fuzzy-attributes will be denoted as = f a;x j a 2 A; x 2 L1g.
Theorem 1 ([
The main results, related to the attribute classi cation in a multi-adjoint concept
lattice framework, were established by meet-irreducible elements of the concept
lattice and the notions of consistent set and reduct [
A is a consistent set of (A; B; R; ) if
M(Y; B; RY ; Y B) =E M(A; B; R; ) This is equivalent to say that, for all hg; f i 2 M(A; B; R; ), there exists a concept hg0; f 0i 2 M(Y; B; RY ; Y B) such that g = g0.
Moreover, if M(Y n fag; B; RY nfag; Y nfag B) 6=E M(A; B; R; ), for all a 2 Y , then Y is called a reduct of (A; B; R; ).
The core of (A; B; R; ) is the intersection of all the reducts of (A; B; R; ).
A classi cation of the attributes can be given from the reducts of a context. De nition 6. Given a formal context (A; B; R; ) and the set Y = fY A j Y is a reductg of all reducts of (A; B; R; ). The set of attributes A can be divided into the following three parts: 1. Absolutely necessary attributes (core attribute) Cf = TY 2Y Y . 2. Relatively necessary attributes Kf = (SY 2Y Y ) n (TY 2Y Y ). 3. Absolutely unnecessary attributes If = A n (SY 2Y Y ).
The attribute classi cation theorems introduced in [
Theorem 2 ([
ai;xi i 2 MF (A), satisfying that h #ai;xi ; #a"i;xi i 6= h #aj;xj ; #a"j;xj i, for all xj 2 L1 and aj 2 A, with aj 6= ai.
Theorem 3 ([
Eai;x = faj 2 A n faig j there exist x0 2 L1; satisfying #ai;x =
#aj;x0 g
Theorem 4 ([
The classi cation of the set of attributes in absolutely necessary, relatively necessary and absolutely unnecessary attributes, provided by the previous theorems, will allow us to obtain reducts (minimal sets of attributes) in the following section. Determining the reducts can entail an important reduction of the computational complexity of the concept lattice. 3
This section is focused on analyzing the construction process of reducts from the attribute classi cation shown in the previous section. To begin with, the attributes in the core, that is, the absolutely necessary attributes, are included in all reducts and the unnecessary attributes must be removed.
The choice of the relatively necessary attributes is the main task in the process, because several reducts are obtained when the set of relatively necessary attributes is nonempty.
Hence, several issues raise, such as, how should we select the set of relatively necessary attributes? What is the most e cient way to perform this process? Do all the reducts have the same cardinality? How can we get a reduct with a minimal number of attributes? This work establishes the rst steps in order to answer these questions.
Regarding a simpli cation in the selection of the relatively necessary attributes, a subset of attributes associated with each concept will be considered. De nition 7. Given a multi-adjoint frame (L1; L2; P; &1; : : : ; &n) and a context (A; B; R; ) with the associated concept lattice (M; ). Let C be a concept of (M; ), we de ne the set of attributes generating C as the set: Atg(C) = fai 2 A j there exists ai;x 2 such that h #ai;x; #a"i;xi = Cg R b1 b2 b3 a1 1 1 0 a2 0:5 1 0 a3 0:5 1 0 a4 1 1 0:5 a5 1 1 1 C3 C2 C1 C0
Now, we will present several properties about the attributes of the context which will be useful to build reducts in our context, together with some example which illustrate them.
Proposition 1. If C is a meet-irreducible concept of (M; ), then Atg(C) is a nonempty set.
The following example was introduced in [
The concept lattice of the considered framework and context are displayed in Figure 1, from which it is easy to see that the meet-irreducible elements are C0, C1 and C2. Now, we will show that the sets Atg(C0), Atg(C1) and Atg(C2) are not empty. For that, the fuzzy-attributes associated with the meet-irreducible concepts need to be obtained. Applying the concept-forming operators to the fuzzy-attributes we have obtaining the association which is written in Table 1.
Proposition 2. If C is a meet-irreducible concept of (M; ) satisfying that card(Atg(C)) = 1, then Atg(C) Cf .
Example 2. In the framework of Example 1, if we consider the concept C2 then we see that the hypothesis given in Proposition 2 are satis ed, that is card(Atg(C2)) = 1, and consequently Atg(C2) = fa4g Cf .
This can be checked from the attribute classi cation given from Table 1 and the classi cation theorems:
If = fa1; a5g Kf = fa2; a3g
Cf = fa4g
Note that the counterpart of the previous proposition is not true, in general. That is, we can nd a 2 Cf such that a 2 Atg(C) and satisfying that card(Atg(C)) 1. What we can assert is that we can always nd a meetirreducible element C satisfying that card(Atg(C)) = 1, if the core is nonempty, as the following proposition explains.
Proposition 3. If the attribute a 2 Cf then there exists C 2 MF (A) such that a 2 Atg(C) and card(Atg(C)) = 1.
Example 3. Coming back to Example 1, we can ensure that the attribute a4 belongs to Cf and, as Proposition 3 shows, there exists a concept in MF (A), which is C2, verifying that a4 2 Atg(C2) and card(Atg(C2)) = 1. tu As a consequence of the above properties, the following corollary holds. tu tu Corollary 1. If C is a meet-irreducible concept of (M; ) and Atg(C)\Kf 6= ? then card(Atg(C)) 2.
Example 4. In Example 1, the concept C1 is a meet-irreducible element such that Atg(C1) \ Kf = fa1; a2; a3g \ fa2; a3g = fa2; a3g 6= ?. As a consequence, we have that card(Atg(C1)) = 3 2 as Corollary 1 shows. tu
The next proposition guarantees that, if a meet-irreducible concept C is obtained from a relatively necessary attribute, then there does not exist an attribute in the core belonging to Atg(C).
Proposition 4. Let C be a meet-irreducible concept. Atg(C) \ Kf 6= ? if and only if Atg(C) \ Cf = ?.
Example 5. Considering the meet-irreducible concept C0 of Example 1, we have that Atg(C0) \ Kf = fa2; a3g. Since this intersection is nonempty, applying Proposition 4, we obtain that Atg(C0) \ Cf = fa2; a3g \ fa4g = ?. A similar situation is given if we take into account C1. tu
A lower bound and a upper bound of the cardinality of the reducts in a multi-adjoint concept lattice framework are provided.
Proposition 5. Given GK = fAtg(C) j C 2 MF (A) and Atg(C) \ Kf 6= ?g and any reduct Y of the context (A; B; R; ). Then, the following chain is always satis ed: card(Cf ) card(Y ) card(Cf ) + card(GK ) Example 6. From Example 1, we can ensure that either attribute a2 or a3 is needed (the attribute a1 is absolutely unnecessary) in order to obtain the meetirreducible concepts C0 and C1. Hence, since a4 2 Cf , two reducts Y1 = fa2; a4g and Y2 = fa3; a4g exist. Thus, only two attributes are needed in order to consider a concept lattice isomorphic to the original one. Now, we will see that these reducts satisfy the previous proposition.
Since the set GK is composed by the attributes generating C0 and C1, we have that GK = ffa2; a3g; fa1; a2; a3gg. Therefore, both reducts Y1 and Y2 satisfy the inequalities in Proposition 5: 1 = card(Cf ) card(Y1) = card(Y2) card(Cf ) + card(GK ) = 3 tu
The proposition below is fundamental in order to provide a su cient condition to ensure that all the reducts have the same cardinality.
Proposition 6. If GK = fAtg(C) j C 2 MF (A) and Atg(C) \ Kf 6= ?g is a partition of Kf , each attribute in Kf generates only one meet-irreducible element of the concept lattice.
The following result states several conditions to guarantee that all the reducts have the same cardinality.
is a partition of Kf , then: (a) All the reducts Y nality is:
GK = fAtg(C) j C 2 MF (A) and
A have the same cardinality and, speci cally, the cardi(b) The number of di erent reducts obtained from the multi-adjoint context is card(Y ) = card(Cf ) + card(GK )
Y Atg(C)2GK
card(Atg(C))
Note that the previous theorem provides a su cient condition in order to ensure that the cardinality of the reducts is the same, however it is not a necessary condition as Example 6 reveals. 4
This section begins with an illustrative example of Proposition 6 and Theorem 5 that computes the reducts of a particular multi-adjoint concept lattice framework, and shows that these reducts have the same cardinality. Example 7. Let (L1; L2; L3; ; &G) be a multi-adjoint frame, where L1 = [0; 1]10, L2 = [0; 1]4 and L3 = [0; 1]5 are regular partitions of [0; 1] in 10, 4 and 5 pieces, respectively, and &G is the discretization of the Godel conjunctor de ned on L1 L2. We consider a context (A; B; R; ), where A = fa1; a2; a3; a4; a5; a6g, B = fb1; b2; b3g, R : A B ! L3 is given by the table shown in the left side of Figure 2 and is constantly &G.
In order to obtain reducts, we will study the meet-irreducible elements of the concept lattice displayed in the right side of Figure 2 and the fuzzy-attributes associated with them. From the corresponding Hasse diagram, we can assert that MF (A) = fC1; C8; C9; C10; C13; C14g. The fuzzy-attributes related to these concepts are shown in Table 2.
Applying the attribute classi cation theorems, we obtain:
Once we have classi ed the attributes, we are going to construct all possible reducts. Clearly, the attributes a1 and a2 must be included in all reducts. Hence, it only remains to choose the relatively necessary attributes that should b1 0:6 0:2 0:2 0 1 0:6 b2 0:8 0:4 0:6 0:6 1 0:8 b3 0:6 0:6 0:2 0 0 0 be contained in each reduct. For that purpose, we will analyze the attributes generating each meet-irreducible concept:
Atg(C1) = fa3; a4g Atg(C8) = fa1g Atg(C9) = fa5; a6g Atg(C10) = fa1g Atg(C13) = fa2g
Atg(C14) = fa2g Since Atg(C1) and Atg(C9) are disjoint subsets of Kf , we can guarantee that GK is a partition of Kf and therefore: (1) By Proposition 6, each attribute in Kf generates only one meet-irreducible element of the concept lattice. From Table 2, it is easy to prove that the attributes a3 and a4 only generate the meet-irreducible concept C1. The concept C9 is uniquely generated by a5 and a6.
C8 C9 C10 C13
C14 MF (A) Fuzzy-attributes generating the meet-irreducible concept
C1 we have that card(Y ) = card(Cf ) + card(GK ) = 2 + 2 = 4, for any reduct Y of the context. Moreover, the number of reducts that we obtain from this context is
Y Atg(C)2GK
card(Atg(C)) = 2 2 = 4 Speci cally, the whole set of reducts are listed below:
Y1 = fa1; a2; a3; a5g Y2 = fa1; a2; a3; a6g Y3 = fa1; a2; a4; a5g
Y4 = fa1; a2; a4; a6g From the previous reducts, we obtain the following isomorphic concept lattices: (M; ) = (MY1 ; ) = (MY2 ; ) = (MY3 ; ) = (MY4 ; )
Now, we will present a situation where the elements belonging to the set GK are not a partition of Kf , and we will see that in this particular example several reducts with di erent cardinality are obtained.
Example 8. Considering the same framework that in the previous example, we x a context (A; B; R; ) where the set A consists of seven attributes, the set B contains three objects and R is obtained from the relation of the previous example with a few of changes shown in Table 3. Hence, we obtain an isomorphic concept lattice to the one shown in Figure 2, but a di erent attribute classi cation arises. tu The attributes are classi ed as follows:
As a consequence, a1 and a2 must belong to all the reducts and a3 should be removed. Analyzing the meet-irreducible elements and the fuzzy-attributes generating them, we obtain: R a1 a2 a3 a4 a5 a6 a7
Now, we have to select one attribute of Atg(C1) and another one of Atg(C9) in order to obtain the whole set of meet-irreducible concepts and compute the reducts. However, in this case, Atg(C1) Kf and Atg(C9) Kf and the intersection Atg(C1) \ Atg(C9) = a6 is nonempty. Therefore, the set GK = fAtg(C1); Atg(C9)g is not a partition of Kf .
Consequently, we can obtain the following di erent reducts whose sizes depend on the chosen attributes as we can see below:
Y1 = fa1; a2; a6g Y2 = fa1; a2; a4; a7g Y3 = fa1; a2; a5; a7g tu
This example provides the idea that, in order to compute a minimal reduct, with respect to the number of attributes, the relatively necessary attributes to be taken into account must be the ones given in the intersection of the sets Atg(C), with Atg(C) 2 GK . 5
Based on the attribute classi cation introduced in [
More properties related to reducts will be investigated in the future in order to nd the most pro table way to generate them. We are also interested in obtaining an algorithm that provides a reduct with a minimal number of attributes for any multi-adjoint concept lattice framework given.