key: cord-0888290-jzpt9ldx
authors: Ren, Ruisi; Wei, Ling
title: The attribute reductions of three-way concept lattices
date: 2016-05-01
journal: Knowl Based Syst
DOI: 10.1016/j.knosys.2016.01.045
sha: a7878910b3988c9d30b8d2b0bd10581cf2842267
doc_id: 888290
cord_uid: jzpt9ldx

Three-way concept analysis is a newly proposed area of formal concept analysis from which one can obtain both the inclusion decision and the exclusion decision. In general, given a context, some attributes may not be essential in three-way concept analysis, such as forming three-way concept lattice. So in this paper, we study the attribute reductions of three-way concept lattices in order to make the data easily be understood. Firstly, based on different criteria generated from object-induced three-way concept (OE-concept), four kinds of attribute reductions are proposed. The four reductions together embody different characteristics of a formal context and can be used in different occasions. Secondly, we discuss their relationships, including their advantages and disadvantages and the relationships among consistent sets and among the cores. Thirdly, based on attribute-induced three-way concept (AE-concept), we also give four attribute-induced three-way attribute reductions and discuss their relationships. Finally, the approaches to computing these attribute reductions are presented and the obtained results are demonstrated and verified by an empirical case. In this paper, we systematically investigate the attribute reductions of three-way concept lattices which enriches the study of formal concept analysis.

The three-way decision (3WD), an extension of the two-way decision model with an added third option, is a common human practice in problem solving and is widely used in our daily life's decision making process [1] . Because of its extensive usages, Yao [2] outlined the theory of three-way decision. The basic idea of 3WD is to divide the universe of discourse into three disjoint subsets by given criteria. These three disjoint parts are called positive, negative and boundary regions from which one can construct different rules to make three-way decision. One can construct rules of acceptance from positive region, rules of rejection from negative region and rules of non-commitment from boundary region.

In the past few years, more and more attentions have been paid to this newly proposed theory and the 3WD has been studied from the different views. Actually, 3WD plays a key role in knowledgebased systems and has been widely used in many fields and disciplines, including computer science, information science, management science, engineering, social science, medical decision-making, etc. [1, [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] .

Formal concept analysis (FCA), as an efficient tool for decision making and knowledge discovery, was proposed by Wille in 1982 [14] , and has subsequently been extended by Wille and Ganter [15] and other scholars. As an effective method for data analysis and knowledge processing, FCA has been used in various areas, such as data mining, information retrieval, and software engineering [16] [17] [18] [19] [20] [21] [22] .

However, in FCA we can only get the two-way decision rather than the three-way decision. That is, based on a formal concept, one can only determine whether an object (attribute) certainly possesses (is shared by) all elements in the intent (extent) and such decision is called inclusion method. Actually, the formal context also offers us the information about whether an object (attribute) does not possesses (is not shared by) any attribute (object), which is called exclusion method, but this cannot be reflected in the formal concept. Since this kind of exclusion method is commonly used in our daily life, Qi et al. [23] applied 3WD to FCA and proposed three-way concept analysis (3WCA). Two key components in 3WCA are three-way concepts and three-way concept lattices. Similar with the formal concept in FCA, a three-way concept is also determined by two parts named extent and intent. However, the extent or intent of a three-way concept should be an orthopair studied by Ciucci [24] . That is to say, in 3WCA, "the extent (or the intent) of a three way concept is equipped with two parts: positive one and negative one. These two parts are used to express the semantics 'jointly possessed' and 'jointly not possessed' in a formal context." [25] This newly proposed three-way concept combines inclusion method (positive region) with exclusion method (negative region). Thus based on a three-way concept, one can divide the object (attribute) universe into three regions to make threeway decision.

Being an important issue in knowledge discovery, attribute reduction has been extensively studied in different fields of soft computing since it can decrease the dimension and make the data easily be understood [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] . It is also an interesting topic in FCA. Many significant results in attribute reduction have been obtained based on a formal context. For example, Zhang et al. [36] discussed the lattice reduction theory where the notion of "reducing the context" in [15] was developed. Within such framework, Zhang et al. [36] constructed judgment theorems of consistent sets, and developed approaches to attribute reduction based on discernibility matrix, which was given a further simplification by Qi [37] from the viewpoint of parent-child concepts. Based on the lattice reduction theory of formal contexts, Wei et al. [38] also studied the reduction theory of formal decision contexts under two different meanings of consistency. And Li et al. [39] have proposed the attribute reduction in order to preserve the rules in the formal decision context. On the other hand, Wang and Ma [40] proposed another attribute reduction in order to preserve the extents of meet-irreducible elements in the original formal concept lattice. Based on the irreducible elements, Li et al. [41] defined the join-irreducible attribute reduction in order to preserve the extents of join-irreducible elements in the original formal concept lattice. From the viewpoint of granular computing, granular reduction was proposed by Wu et al. [42] Additionally, Liu et al. [43] have studied the attribute reduction of object oriented formal concept lattices and property oriented formal concept lattices, and furthermore Wang et al. [44] discussed relations of attribute reductions between object and property oriented formal concept lattices.

Because of the extensive usages of 3WD and FCA, 3WCA will become a very useful tool for knowledge discovery and data analysis. In order to make the discovery and representation of implicit knowledge in three-way concept lattices easier and simpler, based on the different criteria generated from three-way concepts, we firstly propose different attribute reductions. Since the generalization and the specialization of the knowledge contained in the context are all reflected in the three-way concept lattices, if our reduction can preserve the lattice structure, then the basic knowledge reflected in the three-way concept lattices is preserved. Also, because every three-way concept is the join (meet) of join (meet)-irreducible elements, if our reduction can preserve the irreducible elements, we actually preserve the basic elements in lattice construction. Thus this kind of reduction is very important in lattice construction. From the perspective of granular computation, a three-way object or attribute concept can be regarded as a kind of granule, so a kind of attribute reduction which can preserve the extents of the three-way object (attribute) concepts is proposed. All these attribute reductions together embody different characteristics of a context. The basic ideas of these attribute reductions are similar with the classical attribute reductions mentioned in the previous paragraph. However, different from the attribute reductions in FCA, all the reductions in this paper depend on the three-way concept and the three-way concept can reflect more information than the classical formal concept, so the results and meaning of these attribute reductions in 3WCA are different with the classical ones in FCA. Then, we analyze the relationships among these three-way reductions. Finally, we give some approaches to these attribute reductions. Since the study we make is based on the three-way concept analysis, our work can be regarded as a three-way extension of the attribute reductions mentioned in previous paragraph. This paper mainly discusses the different attribute reductions of three-way concept lattices and the relationships among them. The content is organized as follows. In Section 2 , the basic knowledge of classical and three-way concept analysis is reviewed. Section 3 gives the definitions of four different OE-attribute reductions and discusses their relationships, including the relationships among the corresponding consistent sets and cores. Analogously, in Section 4 , we define four different AE-attribute reductions and discuss the relationships among them. Then, the approaches to computing these attribute reductions are presented in Section 5 . Finally, an empirical case is shown in Section 6 and this paper is concluded with a summary in Section 7 .

In order to make this paper self-contained, we firstly review some basic notions in formal concept analysis and three-way concept analysis.

Definition 1 [15] . A formal context ( G, M, I ) consists of two sets G and M , and a relation I between G and M . The elements of G are called the objects and the elements of M are called the attributes of the context. In order to express that an object x is in a relation I with an attribute m , we write xIm or ( x, m ) ∈ I and read it as "the object x has the attribute m ".

A pair of operators are defined on X ⊆ G and A ⊆ M respectively in ( G, M, I ) [15] :

The operator * is same with the modal-style operator R in [45] , which expresses the meaning of jointly possessing.

The properties of this pair of operators are shown in [15] , so we do not describe here.

Definition 2 [15] . A formal concept of the context ( G, M, I ) is a pair ( X, A ) with X * = A and X = A * ( X ⊆ G, A ⊆ M ). We call X the extent and A the intent of the formal concept ( X, A ).

The formal concepts of a formal context ( G, M, I ) are ordered by

All formal concepts of ( G, M, I ) can form a complete lattice called the formal concept lattice of ( G, M, I ) and denoted by L ( G, M, I ). The infimum and supremum are given by

In order to distinguish from the following three-way concept analysis, the formal concept mentioned above will be called classical concept and other notions in the FCA also be named in the same way in the following parts of this paper. Now, we give the definition of reduct as follows.

Definition 3 [36] . Here

Definition 4 [46] . Let L be a lattice. An element x ∈ L is joinirreducible if 1. x = 0 (in case L has a zero)

A meet-irreducible element is dually defined.

Applying the idea of three-way decision into formal concept analysis, Qi et al. [23] recently proposed three-way concept analysis. Firstly, based on the formal concept in Definition 2 and the operators defined on it, called positive operators here, another pair of two-way operators are given, named negative operators, as follows:

for X ⊆ G and A ⊆ M , we have

Combining the operators * and * , a pair of three-way operators are defined on X ⊆ G and A ⊆ M respectively:

In relation to the above three-way operators, their inverse can be defined as follows [23] : for X, Y ⊆ G and A, B ⊆ M ,

Then the three-way concept is given. In particular, ( x , x ) is an OE-concept for all x ∈ G , which is called OE-object concept. Here, for convenience, we write x instead of { x } for any x ∈ G .

If ( X , ( A, B )) and ( Y , ( C, D )) are OE-concepts, then they can be ordered by

is called a subconcept of ( Y , ( C, D )), and ( Y , ( C, D )) is called a super-concept of ( X , ( A, B ) ). If there is no OE-concept ( Z , ( E, F )) such that ( X , ( A, B )) < ( Z , ( E, F )) < ( Y , ( C, D )), then ( X , ( A, B )) is called a child-concept of ( Y , ( C, D )), and ( Y , ( C, D )) is called a parent-concept of ( X , ( A, B )), which is denoted by ( X , ( A, B )) ≺( Y , ( C, D )).

All the OE-concepts form a complete lattice, which is called the object-induced three-way concept lattice of ( G, M, I ) and written as OEL ( G, M, I ). The infimum and supremum are given by

Similarly, the dual attribute-induced three-way concept is given. Definition 6 [23] . Let ( G, M, I ) be a formal context. A pair (( X, Y ), A ) of two object subsets X, Y ⊆ G and an attribute subset A ⊆ M is called an attribute-induced three-way concept, for short, an AE-

In particular, ( m , m ) is an AE-concept for all m ∈ M which is called AE-attribute concept.

If (( X, Y ), A ) and (( Z, W ), B ) are AE-concepts, then they can be ordered by

All AE-concepts also form a complete lattice, which is called the attribute-induced three-way concept lattice of ( G, M, I ) and written as AEL ( G, M, I ). The infimum and supremum are given by

In the classical formal concept analysis, the reduction is defined related to the extents of the formal concepts. In order to give and analyze the attribute reductions of an OE-concept lattice, we firstly give the necessary and sufficient condition for an object set to be an extent of an OE-concept.

. Also from the Definition 5 , we can get (A, B ) = X, that is,

The three-way concept lattices are the core structures in 3WCA, because the hierarchical knowledge of three-way concepts is all reflected in these three-way concept lattices. Thus based on the OEconcept lattice, we propose the OE-lattice reduction of ( G, M, I ). From [15] , we know that in a finite lattice, the set of meet-irreducible elements is infimum-dense and the set of joinirreducible elements is supremum-dense. So the meet-irreducible elements and join-irreducible elements are important in the structure of the lattice. Thus from this point of view, we define the object-induced three-way irreducible elements preserving reductions as follows. Analogous to the classical formal concept, every OE-concept can be represented by the join of OE-object concepts. Hence, every OEobject concept can be regarded as an information granule. Thus from the viewpoint of granular computing, object-induced threeway granular (OE-granular) reduction is proposed. The four different object-induced three-way attribute reductions embody different characteristics of a formal context. The OElattice reduction preserves the OE-lattice of the context. Since the OE-lattice can reflect the hierarchical knowledge of the context, the OE-lattice reduction can preserve this kind of hierarchical knowledge of the context. But it needs to consider all the OE-concepts, which let OE-lattice reduction more difficult to be computed. The OE-MIE (JIE)-preserving reduction is to preserve the extents of the meet (join)-irreducible elements of the OE-concept lattice. Because every OE-concept is meet (join) of meet (join)-irreducible elements of the OE-lattice, the meet (join)-irreducible elements are the basic elements of lattice construction. Thus, although the OE-MIE (JIE)-preserving reduction cannot preserve all the hierarchical knowledge of the context, it still plays an important role in lattice construction. Also since OE-MIE (JIE)-preserving reduction only considers the irreducible elements, the results are easy to be computed. The OE-granular reduction is to preserve the extent of the OE-object concept which can be regarded as a kind of information granule from the perspective of granular computing. Thus OE-granular reduction is meaningful in granular computing. Since it only considers OE-object concepts, compared with other OE-reductions, the computation is the simplest. From Definition 7 to 10 , we find that these different attribute reductions consider different perspectives or different information of the context and they can be used in different occasions. If we want to preserve all the knowledge of the context, we need to use OE-lattice reduction; if we want to preserve the basic elements of lattice construction, we need to use OE-MIE (JIE)-preserving reduction; if we want to preserve the information granules, we need to use OE-granular reduction. The above discussions are about the differences of these four OE-reductions which are summarized in Table 1 . Now, let us discuss the relationships among these four OE-attribute reductions. In order to analyze the relationship between OE-granular reduction and OE-JIE-preserving reduction, we firstly discuss the relationship between OE-object concept and the join-irreducible element of OEL ( G, M, I ) in the following proposition. ( X , ( A, B ) ) is an OE-object concept.

Proof. Necessity. Let ( X , ( A, B ) ) ∈ OEL ( G, M, I ). Then

By the properties of * and * , we can obtain

From Lemma 1 , we know that in a finite lattice, every element is join of join-irreducible elements, so the join-irreducible element of OEL ( G, M, I ) must be an OE-object concept.

Sufficiency. Assume (X, (x * i , x * i )) is an OE-object concept induced by x i . From Lemma 1 we know that (X, (x * i , x * i )) is a join of join-irreducible elements, and the necessity of Lemma 3 shows that the join-irreducible element of OEL ( G, M, I ) must be an OEobject concept, thus we have

j , x j * )) . Therefore, according to the definition of join-irreducible element, we obtain that (X, (x *

is a join-irreducible element of OEL ( G, M, I ).

Lemma 3 shows that in an OE-lattice, the join-irreducible element is same with the object concept; therefore, if D ⊆ M can preserve the extent set of OE-object concepts, then it must preserve the extent set of join-irreducible elements. Thus, we obtain the following theorem. Based on the above analysis, we can sum up the relationships among these four kinds of OE-reductions in Fig. 1 , and its explanation is shown in Fig. 2 . 

Similarly, we can give four attribute reductions of an AEconcept lattice. Analogously to the proofs of theorems in Section 3 , the proofs in this section are omitted. In AE-concept lattice, the granule is different from the one in OE-concept lattice. Here, the AE-attribute concept can be regarded as granule, since every AE-concept can be represented by the meet of AE-attribute concepts. Then the AE-granular reduction is given as follows. If set D is an AE-granular consistent set of ( G, M, I ), and there is no proper subset E ⊂ D such that E is an AE-granular consistent set of ( G, M, I ), then set D is called an AE-granular reduct of ( G, M, I ).

The sets containing the above four kinds of consistent sets are denoted according to the above order by CS ( AEL ), CS ( AEM ), CS ( AEJ ) and CS ( AEG ), respectively; the sets containing the associated reducts are denoted by Red ( AEL ), Red ( AEM ), Red ( AEJ ) and Red ( AEG ); and the cores of reductions are denoted by Core ( AEL ), Core ( AEM ), Core ( AEJ ) and Core ( AEG ).

Then, we give the relationships among four AE-attribute reductions, which are similar to the last section. Lemma 4 shows that in AE-lattice, the meet-irreducible element is same with the attribute concept; therefore, if D ⊆ M can preserve the extent set of AE-attribute concepts, then it must preserve the extent set of meet-irreducible elements. Thus, we obtain the following theorem. Based on above analysis, we can sum up the relationships among the four kinds of AE-reductions in Fig. 3 , and its explanation is shown in Fig. 4 .

Based on the similar idea of discernibility matrix proposed by Zhang et al. [36] , we introduce the discernibility matrix and discernibility functions which can be used to find the four different OE-reductions. ((X, (A, B ) ) , (Y, (C, D )))

is called the OE-discernibility attributes set between ( X , ( A, B ) ) and ( Y , ( C, D ) ). ((X, (A, B ) ) , (Y, (C, D )))( (X, (A, B ) ) , (Y, (C, D ) ) ∈ OEL (G, M, I)) is called the OEL-discernibility matrix of ( G, M, I ). OEJ = (DIS OEL ((X, (A, B ) ) , (Y, (C, D ) )) , where ( X , ( A, B ) ) is the join-irreducible element of OEL ( G, M, I ) ).

Because we only need to use the non-empty sets in the attribute reduction, we also let denote the set of the non-empty OE-discernibility attributes sets. C ∩ B, D ∩ B ) ) ∈ OEL ( G, M, I ), then from X ⊂ Y , we can get Theorem 9 gives us a necessary and sufficient condition of an OE-concept to hold its extent unchanged. Considering the definitions of the four different OE-attribute reductions and their relationships, we give the following methods to computing these reductions.

In order to give a more concise description of the following methods, we also use DIS OEL (( X , ( A, B ) ), ( Y , ( C, D ))) to denote the union of its components in the following definition. For instance, if DIS OEL ((X, (A, B ) ) , (Y, (C, D ))) = (E, F ) , then E ∪ F is also denoted as DIS OEL (( X , ( A, B ) ), ( Y , ( C, D ) )). And we also use OEL to represent the OE-discernibility matrix of ( G, M, I ).

Let ( G, M, I ) be a formal context. The OELdiscernibility function, OEM-discernibility function, OEJdiscernibility function and OEG-discernibility function are defined as follows:

By absorption law and distributive law, the OE-discernibility function f can be transformed to a minimal disjunctive normal form, whose items can form all the OE-reducts of ( G, M, I ).

Example 1. Table 2 shows a formal context ( G 1 , M 1 , I 1 ) , in which, the object set is G 1 = { 1 , 2 , 3 , 4 } , and the attribute set is M 1 = Table 2 A formal context (G 1 , M 1 , I 1 ) . 5 . The OE-concept lattice of ( G 1 , M 1 , I 1 ).

{ a, b, c, d, e } . And the OE-concept lattice of ( G 1 , M 1 , I 1 ) is shown in Fig. 5 .

There are 11 OE-concepts: (G 1 , (∅ , ∅ )) , (13, ( d, c ) ), (23 , (∅ , e ) ) , (124 , (ab, ∅ )) , (14 , (abe, ∅ )) , (24, ( abc, d ) ), (1, ( abde, c ) ), (3, ( d, abce )), (2, ( abc, de )), (4, ( abce, d )), (∅ , (M 1 , M 1 )) , which are labeled as T C i (i = 1 , 2 , . . . , 11) . According to Definition 13 , the OEL of OEL ( G 1 , M 1 , I 1 ) is shown in Table 3 .

More specifically, if TC i is a child-concept of TC j , then the OEdiscernibility attributes set between TC i and TC j ( DIS OEL ( TC i , TC j )) is at the i th row and j th column of Table 3 . Now we calculate the discernibility functions. 

In order to get the AE-attribute reductions, the AE-discernibility attributes set is defined as follows: Here, we also let denote the set of the non-empty AE-discernibility attributes sets.

Any AE-concept (( X, Y ), A ) can be written as the following form (( X, Y ) , ( X, Y ) ). Since operators and are dual, we can get the following theorem from Theorem 9 dually. Table 3 The OEL-discernibility matrix of the OE-concept lattice in Fig. 5 . Table 4 The AEL-discernibility matrix of the AE-concept lattice in Fig. 8 . AEG-discernibility function are defined as follows:

By absorption law and distributive law, the AE-discernibility function f can be transformed to a minimal disjunctive normal form, whose items can form all the AE-reducts of ( G, M, I ).

Example 2 (Continued with Example 1 ) . The AE-concept lattice of ( G 1 , M 1 , I 1 ) is shown in Fig. 8 . 1 , 2 , . . . , 11) . According to Definition 15 , the AEL of AEL ( G 1 , Table 4 . Then we calculate the discernibility functions. 

In this section, a real-life database is analyzed to demonstrate the application of the proposed attribute reduction methods. The chosen database is about the patients who suffer from severe acute respiratory syndrome (SARS) and their symptoms. Here we only use OE-reductions as examples and the AE-reductions can be studied similarly. The details are as follows: Table 5 depicts a dataset of four patients who suffer from severe acute respiratory syndrome (SARS) [47] . Let G be the set of four patients and M be the set of five symptoms. For convenience, we denote the four patients by 1, 2, 3, 4, respectively, and the five symptoms ( Fever, Cough, Headache, Difficulty Breathing and Diarrhea ) by a, b, c, d, e , respectively. That is

Firstly, we can get all the formal concepts of Table 5 and the corresponding formal concept lattice is shown in Fig. 10 . There are 7 formal concepts: (G, ∅ ) , (14, ce ), (12, a ), (1, ace ), (2, ad ), (3, b ) , (∅ , M) . Then, we can get 12 OE-concepts: (G, (∅ , ∅ )) , (134 , (∅ , d) ) , (124 , (∅ , b) ) , (34 , (∅ , ad) ) , (14, ( ce, bd )), (12, ( a, b ) ), (23 , (∅ , ce ) ) , (4, ( ce, abd )), (1, ( ace, bd )), (2, ( ad, bce )), (3, ( b, acde ) ), (∅ , (M, M) ) , which are labeled as T C i (i = 1 , 2 , . . . , 12) . The OElattice is shown in Fig. 11 .

From classical formal concept, one can only get the information that the objects in the extent have the attributes in the intent of this formal concept (inclusion method). But from the OE-concept, one can obtain not only that the objects in the extent have the attributes in the first component of intent (inclusion method), but also that the objects in the extent don't have the attributes in the second component of intent (exclusion method). For example, the formal concept (14, ce ) only tells us that patients 1 and 4 belong to one class because they have same symptoms Headache and Diarrhea , but the OE-concept (14, ( ce, bd )) tells us that patients 1 and 4 belong to one class not only because they have the symptoms Headache and Diarrhea but also because they don't have the symptoms Cough and Difficulty Breathing . Thus three-way concepts can reflect more knowledge than the classical formal concepts.

However, in order to obtain all OE-concepts and the corresponding OE-concept lattice, one needs to consider all attributes. In this case, there are only 5 attributes, but from Fig. 11 we can see that the representations of all OE-concepts are a little bit complicated. Actually, in real life, we even meet more complicated data. Thus the attribute reductions are necessary to be considered.

Since the ordered hierarchical structure of all the OE-concepts is reflected by the OE-concept lattice, OE-concept lattice is a core structure in 3WCA. Hence, we show the OE-lattice attribute reduction firstly. According to Definition 13 , the OEL of OEL ( G, M, I ) is shown in Table 6 . Now we calculate the discernibility functions. From Fig. 12 , we can see that the OE-lattice of (G, M 5 , I M 5 ) is isomorphic to the OE-lattice of ( G, M, I ). Thus the classification of patients and the hierarchy of the three-way concepts don't change, but we only need to consider smaller amount of attributes. For instance, only based on 4 symptoms Fever, Cough, Headache and Difficulty Breathing , patients 1 and 4 can still be classified into one class. So after OE-lattice reduction, the knowledge is represented in an easier way.

Then, we calculate the OE-JIE-preserving (OE-granular) reducts. Table 6 The OEL-discernibility matrix of the OE-concept lattice in Fig. 11 . 

(a, ∅ ) ( ce, d ) TC 10 ( d, ce ) ( ad, b ) TC 11 ( b, ce ) ( b, ad ) TC 12 ( abd, ce ) ( db, ace ) ( bce, ad ) ( acde, b ) Fig. 13 . The OE-concept lattice of (G, M 6 , I M 6 ) .

The OE-JIE-preserving (OE-granular) reducts are { a, c }, { a, e } and { a, b, d }. The OE-concept lattice of (G, M 6 , I M 6 ) is presented in Fig. 13 . Here M 6 is the OE-JIE-preserving (OE-granular) reduct { a, c }.

From Fig. 13 , we can see that the OE-granular reduct cannot preserve the structure of the OE-lattice. That means some knowledge may be lost after reduction. For example, now in Fig. 13 , the patients 1, 2 and 4 can not belong to one class because the attribute Difficulty Breathing has been removed after reduction. But the extents of the OE-object concepts and the join-irreducible elements of OE-lattice in Fig. 11 don't change. Since the joinirreducible elements are important in the lattice construction and the OE-object concepts are important in granular computing, these two reductions are important in lattice construction and granular computing.

In this paper, the attribute reductions of three-way concept lattices have been systematically studied. We have defined eight kinds of attribute reductions of three-way concept lattices, four OE-attribute reductions and four AE-attribute reductions, and discussed their advantages and disadvantages. Then we investigated the relationships among these newly proposed attribute reductions, the relationships among their consistent sets, as well as the relationships among their cores. Also, we have presented the approaches to computing most of these reductions. Finally, an empirical case is shown to illustrate our analysis. Since three-way concept analysis can be regarded as an extension of formal concept analysis and the three-way concept lattice can reflect more knowledge than the classical one, the study of the three-way concept lattice is a newly proposed but meaningful part of formal concept analysis. Also because the attribute reductions of three-way con-cept lattices are necessary in three-way concept analysis, the attribute reductions we discussed in this paper enrich the study of formal concept analysis.

The current approach to AE-JIE-preserving reduction is complicated and cannot be unified under the frame of the discernibility matrices and discernibility functions, so, in this paper, we omitted the discussion of it and focused on the relationships among different attribute reductions. Also, since the three-way concept analysis can be regarded as a generalization of the classical formal concept analysis, there must exist some relationships between these two theories. Hence, the relationship among the attribute reductions on these two theories should be studied in the future. Actually, for any kind of attribute reduction mentioned in this paper, the attributes can be classified into three types according to their roles in the reduction [36] . Let ( G, M, I ) be a formal context. For a certain kind of reduction, suppose the set { D i | D i is a reduct, i ∈ τ }( τ is an index set) includes all associated reducts of ( G, M, I ). Then attributes in M can be classified into three types: absolutely necessary attribute, also called core attribute (attribute in ∩ i ∈ τ D i ), relatively necessary attribute (attribute in ∪ i ∈ τ D i − ∩ i ∈ τ D i ), and absolutely unnecessary attribute (attribute in M − ∪ i ∈ τ D i ). Of course, different attributes play different roles in different reductions. For further research, it is of significance to investigate their relationships based on different reductions. Also, in order to apply the theories we discussed in this paper in the real world, in the future, we will propose the corresponding algorithms of these eight different attribute reductions, which may help us to deal with the big data problems in our daily lives more conveniently. And the utility value will also be introduced and added to every concept and the new attribute reductions based on the utility value will be studied, which will make our study more suitable in practices.

Advances in three-way decisions and granular computing, Knowl.-Based Syst

An outline of a theory of three-way decisions

Decision-theoretic three-way approximations of fuzzy sets

Granular computing and sequential three-way decisions

Three-way decisions space and three-way decisions

Multi-class decision-theoretic rough sets

A multiple-category classification approach with decision-theoretic rough sets

A novel three-way decision model based on incomplete information system

Proximal three-way decisions: theory and applications in social networks

A tree-based incremental overlapping clustering method using the three-way decision theory, Knowl.-Based Syst

Web-based medical decision support systems for three-way medical decision making with game-theoretic rough sets

Three-way recommender systems based on random forests, Knowl.-Based Syst

Three-way decisions solution to filter spam email: an empirical study

Restructuring lattice theory: an approach based on hierarchies of concepts

Formal Concept Analysis: Mathematical Foundations

Formal Concept Analysis: Foundations and Applications

Preprocessing input data for machine learning by FCA

Exploring the preference of customers between financial companies and agents based on TCA, Knowl.-Based Syst

Combined rough sets with flow graph and formal concept analysis for business aviation decision-makig

An intergration method combining rough set theory with formal concept analysis for personal investment portfolios

Using a concept lattice of decomposition slices for program understanding and impact analysis

A comparative study of multigranulation rough sets and concept lattices via rule acquisition

Three-way formal concept analysis

Orthopairs: a simple and widely used way to model uncertainty

The connections between three-way and classical concept lattices

Evidence-theory-based numerical algorithms of attribute reduction with neighborhood-covering rough sets

Attribute selection based on a new conditional entropy for incomplete decision systems

Generalized attribute reduct in rough set theory, Knowl.-Based Syst

Double-quantitative fusion of accuracy and importance: Systematic measure mining, benign integration construction, hierarchical attribute reduction, Knowl.-Based Syst

Attribute reduction in decision-theoretic rough set models

Tabu search for attribute reduction in rough set theory

Information-preserving hybrid data reduction based on fuzzy-rough techniques

An accelerator for attribute reduction based on perspective of objects and attributes

A set covering based approach to find the reduct of variable precision rough set

Approaches to knowledge reduction based on variable precision rough set model

Attribute reduction theory and approach to concept lattice, science in china series

Attribute reduction in formal contexts based on a new discernibility matrix

Attribute reduction theory of concept lattice based on decision formal contexts

Knowledge reduction in decision formal contexts

A novel approach to attribute reduction in concept lattices

Attribute reduction of concept lattice based on irreducible elements

Granular computing and knowledge reduction in formal contexts

The reduction theory of object oriented concept lattices and property oriented concept lattices

Relations of attribute reduction between object and property oriented concept lattices

A possibility-theoretic view of formal concept analysis

Introduction of Lattices and Order

Transmission dynamics and control of SARS: the 20 02C20 03 epidemic

The authors of this paper really appreciate the anonymous reviewers. This work was partially supported by the National Natural Science Foundation of China (Grant Nos. 11371014 , 11071281 and 61202206 ).