In Formal Concept Analysis, attribute reduction is a important step in order to reduce the complexity of the computation of the concept lattice. This reduction is more complex in fuzzy environments. In this paper, we will present a first approximation to reduce the set of attributes in the multi-adjoint concept lattice. The solution found is based on the development of specific results which allow us to reduce the number of attributes in the classical case, by detecting some relatively necessary and absolutely unnecessary attributes and, then, use linguistic labels in order to obtain a method to reduce the number of attributes in a multi-adjoint context, working up to some level of tolerance, and preserving the original lattice structure of the set of concepts.
Formal concept analysis (FCA) has become an important and appealing research
topic both from a theoretical perspective [
In a nutshell, FCA extracts information from databases containing a set attributes A and a set of objects B together with a relation R ⊆ A × B. This information is classified into concepts and an order among them is defined, the final algebraic structure obtained this way is the so-called concept lattice. Usually, the set of attributes is very large and the complexity to built the concept lattice is very high.
Different fuzzy approaches for generalizing FCA were introduced and, nowadays, there are works which extend the theory with ideas from fuzzy set theory or from rough set theory or even integrated approaches encompassing both approaches.
Rough set theory is an alternative formal tool for modelling and processing
information under uncertainty. For both environments, FCA and RST, there
exist mechanisms to reduce the number of attributes [
In this paper we concentrate on the problem of attribute reduction in a fuzzy extension of formal concept analysis. Specifically, we introduce some results which allow us to reduce the number of attributes in the classical case, by detecting some relatively necessary and absolutely unnecessary attributes. Later, we use linguistic labels in order to obtain a method to reduce the number of attributes in a multi-adjoint context, working up to some level of tolerance. As the method to compute the reduced set of attributes does not require to build the whole concept lattice in advance, the complexity to obtain the multi-adjoint concept lattice, after attribute reduction, decreases notably. 2
In classical formal concept analysis [
X↑ = {a ∈ A | for all b ∈ X, aRb} = {a ∈ A | if x ∈ X, then aRb} Y ↓ = {b ∈ B | for all a ∈ Y, aRb} = {b ∈ B | if a ∈ Y, then aRb} (1) (2)
A concept in the context (A, B, R) is defined to be a pair (X, Y ), where X ⊆ B, Y ⊆ A, and which satisfies that X↑ = Y and Y ↓ = X. The element X of the concept (X, Y ) is the extent and Y the intent.
The set of concepts in a context (A, B, R) is denoted as B(A, B, R) and it is
a complete lattice [
An important fact is that the extent and intent mappings form a Galois
connection [
2. x ≤1 x↓↑ for all x ∈ P1. 3. y ≤2 y↑↓ for all y ∈ P2.
Recently, a fuzzy generalization of the formal concept analysis was presented
in [
The first definition introduces the basic building blocks of the multi-adjoint concept lattices, the adjoint triples, which are generalisations of the notion of adjoint pair under the hypothesis of having a non-commutative conjunctor.
The lack of commutativity of the conjunctor, directly provides two different ways of generalising the well-known adjoint property between a t-norm and its residuated implication, depending on which argument is fixed in the conjunction. Definition 2. Let (P1, ≤1), (P2, ≤2), (P3, ≤3) be posets and & : P1 × P2 → P3, ւ : P3 × P2 → P1, տ : P3 × P1 → P2 be mappings,3 then (&, ւ, տ) is an adjoint triple with respect to P1, P2, P3 if:
3. x ≤1 z ւ y iff x & y ≤3 z iff y ≤2 z տ x, where x ∈ P1, y ∈ P2 and z ∈ P3.
Note that in the domain and codomain of the considered conjunctor we have
three (in principle) different sorts, thus providing a more flexible language to
a potential user. Furthermore, notice that no boundary condition is required,
in difference to the usual definition of multi-adjoint lattice [
In order to provide more flexibility into our language, we will allow the existence of several adjoint triples for a given triplet of posets. Notice, however, that since these triplets will be used as the underlying structures of our generalization of concept lattice, it is reasonable to require the lattice structure on some of the posets in the definition of adjoint triple.
Definition 3. A multi-adjoint frame L is a tuple
(L1, L2, P, ¹1, ¹2, ≤, &1, ւ1, տ1, . . . , &n, ւn, տn) where (L1, ¹1) and (L2, ¹2) are complete lattices, (P, ≤) is a poset and, for all i ∈ {1, . . . , n}, (&i, ւi, տi) is an adjoint triple with respect to L1, L2, P . For short, a multi-adjoint frame will be denoted as (L1, L2, P, &1, . . . , &n).
Following the usual approach to formal concept analysis, given a frame, a
multi-adjoint context is a tuple consisting of sets of objects and attributes and a
fuzzy relation among them; in addition, the multi-adjoint approach also includes
a function which assigns an adjoint triple to each object (or attribute). This
feature is important in that it allows for defining subgroups of objects or attributes
in terms of different degrees of preference, see [
a tuple (A, B, R, σ) such that A and B are non-empty sets (usually interpreted
3 Note that the use of ւ done in [
As usual in the different frameworks of formal concept analysis, a multiaandjdoifn↓tσc=ongce;pwtiitsha(↑pσa,i↓rσh)gb,feiinsgatthisefyGinaglotihsactognn∈ecLti2Bo,nfd∈efiLne1Adaanbdovthe.at g↑σ = f
frame (L1, L2, P, &1, . . . , &n) and a context (A, B, R, σ) is the set M = {hg, f i | g ∈ L2B , f ∈ L1A and g↑σ = f, f ↓ σ = g} in which the ordering is defined by hg1, f1i ¹ hg2, f2i if and only if g1 ¹2 g2 (equivalently f2 ¹1 f1).
The ordering just defined above actually provides M with the structure of a complete lattice. 3
any (X, Y ) ∈ B(A2, B, R2) there exists (X′, Y ′) ∈ B(A1, B, R1) such that X =
B(A1, B, R1) ≤ B(A2, B, R2)
If B(A1, B, R1) ≤ B(A2, B, R2) and B(A2, B, R2) ≤ B(A1, B, R1), then these two concept lattices are said to be isomorphic to each other, and we will write:
B(A1, B, R1) =∼ B(A2, B, R2)
Given a context (A, B, R), if we consider a subset of attributes, Y ⊆ A and the restriction relation RY = R ∩ (Y × B), the triple (Y, B, RY ) is also a formal context, which can be interpreted as a subcontext of the original. Hence, we can apply the mappings ↓ and ↑, in this subcontext we will write ↓Y and ↑Y . It is clear that, given X ⊆ B we have that X↑Y = X↑ ∩ Y . 4 A similar theory could be developed by considering a mapping τ : A → {1, . . . , n} which associates any element in A with some particular adjoint triple in the frame.
that Y 6= ∅, B(A, B, R) ≤ B(Y, B, RY ) holds.
A such that B(A, B, R) =∼ B(Y, B, RY ), then Y is called a consistent set of (A, B, R). Moreover, if B(Y r {y}, B, RY r{y}) 6=∼ B(A, B, R), for all y ∈ Y , then
Theorem 2 ( [
In [
consider the set {Yi | Yi is a reduct, i ∈ Λ} of all reducts of (A, B, R). Then A can be divided into the following three parts: 1. Absolutely necessary attributes (core attribute) Ac = Ti∈Λ Yi. 2. Relatively necessary attributes Ar = (Si∈Λ Yi) r (Ti∈Λ Yi). 3. Absolutely unnecessary attributes Au = A r (Si∈Λ Yi).
It can be checked that {ac}↓ 6= {ar}↓, {ar}↓ 6= {au}↓, {ac}↓ 6= {au}↓ for all ac ∈ Ac, ar ∈ Ar, au ∈ Au.
Now, we will introduce a mechanism in order to obtain a reduct from a given context. The most important feature is that it is not necessary to obtain all the concepts in order to classify the attributes.
Proposition 1. Let (A, B, R) be a context and consider a ∈ A. If aR = T{aiR | ai ∈ {a}↓↑ r {a}}, then A r {a} is a consistent set.
Proof. Let us write A for A r {a}. Thus, we need to prove that, given (X, Y ) ∈ B(A, B, R), there exists (X′, Y ′) ∈ B(A, B, RA) such that X = X′.
If a 6∈ Y , then Y ⊆ A and we consider (X′, Y ′) = (X, Y ). Otherwise, we have that {a}↓↑ ⊆ Y and we consider Y ′ = Y r {a}. Hence,
X = Y ↓ = \{aiR | ai ∈ Y } = \{aiR | ai ∈ Y r {a}↓↑} ∩ \{aiR | ai ∈ {a}↓↑} (=∗) \{aiR | ai ∈ Y r {a}↓↑} ∩ \{aiR | ai ∈ {a}↓↑ r {a}} = (Y ′)↓A = X′ where (∗) follows by hypothesis.
Lemma 1. Let (A, B, R) be a context, and a1, a2 ∈ A. If {a1}↓↑ = {a2}↓↑, then a1R = a2R (which is equivalent to {a1}↓ = {a2}↓). ⊓⊔
Given a context (A, B, R), with A = {a1, . . . , am}, we have the following set of intents I0 = {{a1}↓↑, . . . , {am}↓↑}. Set equality defines an equivalence relation in I0, and we denote by [Y ] the equivalence class of Y , for all Y ⊆ A.
[{a}↓↑] = {{a1}↓↑, . . . , {an}↓↑} and |{a}↓↑| = n, with n ≥ 2, then a1, . . . , an are relatively necessary attributes. Proof. The hypothesis |{a}↓↑| = n implies that {a}↓↑ = {a1, . . . , an}, n ≥ 2. Without loss of generality we can assume that a = an and, therefore, [{an}↓↑] = {{a1}↓↑, . . . , {an}↓↑} now, by Lemma 1, we have that a1R = a2R = · · · = anR. As a result, given the concept ({an}↓, {an}↓↑) ∈ B(A, B, R), the extent {an}↓ is equal to each of the aiR, with i ∈ {1, . . . , n}. In particular,
a1R = \ ©aiR | ai ∈ {an}↓↑ r {a1}ª by Proposition 1, we obtain that Y = A r {a1} is consistent and the pair ({an}↓Y , {an}↓Y ↑Y ) is an element of the concept lattice B(Y, B, RY ), where
Y {an}↓ = {an}↓ = anR, and {an}↓Y ↑Y = {a2, . . . , an}. is an element of the concept lattice B(Z, B, RZ ), where {an}↓ = {an}↓ = anR, and {an}↓Z↑Z = {an}.
Let us see that an belongs to at least one reduct. For each reduct Z′ ⊆ Z, the attribute an must belong to Z′ since, otherwise, there would not exist an element in the resulting concept lattice which is related to ({an}↓ , {an}↓Z↑Z ), Z and this would imply that Z′ is not consistent, which is contradictory.
Now, it is easy to check that an cannot belong to every reduct, since the initial procedure could have been done with respect to any other attribute among a1, . . . , an−1, with n ≥ 2. Therefore, an (actually any ai) is a relatively necessary attribute. ⊓⊔
The previous proposition can be extended to the case in which the cardinality of the intent {a}↓↑ is greater than n. The obtained result depends on whether the cardinality is equal to n + 1 or strictly greater than that value.
[{a}↓↑] = {{a1}↓↑, . . . , {an}↓↑} and aR = \ ©akR | ak ∈ {a}↓↑ r {a1, . . . , an}ª then the following statements hold:
– If |{a}↓↑| = n + 1, then all the elements in {a}↓↑ are relatively necessary. – If |{a}↓↑| ≥ n + 2, then a1, . . . , an are absolutely unnecessary. Proof. Follows the idea of the previous proposition. ⊓⊔
Under certain circumstances, we can recognize absolute unnecessary and relative necessary attributes, and it is possible to prove that the rest of attributes are absolute necessary.
Therefore, given a context (A, B, R), where A = {a1, . . . , am}, we have a method that computes the character of all attributes and the reducts of (A, B, R). Firstly, we compute the subsets {{a1}↓↑, . . . , {am}↓↑} and we apply Proposition 1, 2 and 3 in order to obtain consistent sets of attributes and classifying them. Finally, note that when we cannot apply Proposition 1, we have obtained a reduct of (A, B, R).
Notice that it is possible to obtain reducts before building the concept lattice,
as in [
Attribute reduction is an interesting tool in order to reduce the complexity of
the computation of concept lattices [
From now on we will consider the lattice (L, ¹) as the unit interval ([
In+1 = {[x0, x1], (x1, x2], . . . , (xn, xn+1]} such that x0 = 0 and xn+1 = 1, for all i ∈ {0, 1, . . . , n − 1}.
Now, a set H of linguistic labels such as low, medium, high, very, more or less, much, essentially, slightly, . . . , will be assigned to the previous partition of the unit interval by a mapping φ : H → In+1.
Note that in the rest of the paper, we will often directly refer to the set of labels as an ordered set H = {h0, h1, . . . , hn} to denote that φ(hi) = (xi, xi+1]. For example, if we consider H = {Low, Medium-Low, Medium-High, High} we can assume the following regular partition:
I4 = {[0, 1/4], (1/4, 2/4], (2/4, 3/4], (3/4, 1]} where φ assigns Low with [0, 1/4], Medium-Low with (1/4, 2/4], Medium-High with (2/4, 3/4], and High with (3/4, 1].
Now, we will consider a fuzzy or multi-adjoint context which set of attributes will be reduced by using the ideas described at the beginning of the section.
Let (A, B, R, σ) be a multi-adjoint context and H = {h0, h1, . . . , hn} be a list of labels. The cardinality of H depends on the level of tolerance than the user may assume. Thus, we will be working with a regular partition of the unit interval in n + 1 pieces, In+1, and the mapping φ : H → In+1.
We consider a new crisp context (AH , B, Rφ) where the set of objects is equal to the original one, the set of attributes is extended by composing each of the labels with each attribute from the original A, that is, AH = {hia | i ∈ {0, . . . , n}, a ∈ A}, and finally the relation Rφ : AH × B → {0, 1} is defined as Rφ(hia, b) = (1 if R(a, b) ∈ φ(hi)
0 otherwise
The following example will be used the rest of the paper in order to show the definitions and the procedure we are introducing.
Example 1. Let us consider an example in which a number of journals are considered as objects and several parameters appearing in the ISI Journal Citation Report are the set of attributes.
The sets of attributes and objects are the following:
A = {Impact Factor, Immediacy Index, Cited Half-Life, Best Position} B = {AMC, CAMWA, FSS, IEEE-FS, IJGS, IJUFKS, JIFS} where the “best position” means the best quartile of the different categories under which the journal is included, and the journals considered are Applied Mathematics and Computation (AMC), Computer and Mathematics with Applications (CAMWA), Fuzzy Sets and Systems (FSS), IEEE transactions on Fuzzy Systems (IEEE-FS), International Journal of General Systems (IJGS), International Journal of Uncertainty Fuzziness and Knowledge-based Systems (IJUFKS), Journal of Intelligent and Fuzzy Systems (JIFS).
The fuzzy relation between them, R : A × B → [
Before computing the multi-adjoint concept lattice it is certainly advantageous to reduce the number of attributes in order to decrease the complexity of its computation. In order to do this, let as assume a level of tolerance for the defuzzification. In this example we will consider a list of of four labels, H = {Low, Medium-Low, Medium-High, High}. Hence, we will be working with the regular partition I4 = {[0, 1/4], (1/4, 2/4], (2/4, 3/4], (3/4, 1]}.
Hence, we have a new context (AH , B, Rφ), where AH and Rφ are shown in Table 2, applying the definitions above.
Once we have obtained the crisp context above, we can focus on reducing the number of attributes; any method will do but, in the following, we apply the method based on the results of the previous section. For example, if in an instance of our running example the attributes Low IF, Medium-Low IF and High IF absolutely unnecessary and, moreover, Medium-High IF and Medium-Low II are relatively necessary, then we would delete Medium-High IF instead of deleting Medium-Low II because deleting both Low IF, Medium-Low IF, High IF and Medium-High IF we would reduce the attribute Impact Factor in the original context.
As stated in the previous paragraph, the main idea in this stage is looking for full blocks of superfluous (crisp) attributes in order to reduce original attributes, that is, if we can reduce all the crisp attributes Ha = {h0a, h1a, . . . , hna} in the modified context (AH , B, Rφ), then we are able to reduce attribute a in the original context (A, B, R).
Example 2. Continuing with Example 1, we can check that: Medium-High IF, High IF, Medium-Low II, Medium-High II, High II, Low CHL, Medium-High BP are absolutely unnecessary; the final context is shown in Table 3. Therefore, the reduction given in the crisp context has not direct consequences in the original context. As a result, we may affirm that the set of original attributes are not much dependent.
Now, assume the following modification in the original relation, in which we have R(Best Position, IJGS) = 1/4 and that R(Best Position, CAMWA) = 3/4. The new context is shown in Table 4.
The absolutely unnecessary attributes now are Medium-High IF, High IF, Medium-Low II, Medium-High II, High II, Low CHL and Medium-Low BP. But, in addition,
[{Low IF}↓↑] = {{Low IF}↓↑, {Low BP}↓↑} and [{Medium-Low IF}↓↑] = {{Medium-Low IF}↓↑, {Medium-Low BP}↓↑} Hence, we choose to delete both Low IF and Medium-Low IF in order to completely get rid of the full set of labelled versions of Impact Factor. As a result, we obtain the context given in Table 5 and, therefore, Impact Factor can be removed in the original context.
We have started to consider the problem of attribute reduction in the multiadjoint extension of formal concept analysis. However, the solution found is based on the development of specific results which allow us to reduce the number of attributes in the classical case, by detecting some relatively necessary and absolutely unnecessary attributes and, then, use linguistic labels in order to obtain a method to reduce the number of attributes in a multi-adjoint context, working up to some level of tolerance, and preserving the original lattice structure of the set of concepts. Certainly, this idea is applicable to any other fuzzy approach to FCA.
So far we have not conducted any experimental tests but, this is future work to be done in the short term; however, as the method to compute the reduced set of attributes does not require to build the whole concept lattice in advance, the complexity to obtain the multi-adjoint concept lattice, after attribute reduction, is expected to decrease notably.