Dominancebased rough set theory over intervalvalued information systems Article DOI: 10.1111/exsy.12022 Dominance-based rough set theory over interval-valued information systems Bingzhen Sun,1,2 Weimin Ma1* and Zengtai Gong3 (1) School of Economics and Management, Tongji University, Shanghai 200092, China E-mail: mawm@tongji.edu.cn (2) School of Traffic and Transportation, Lanzhou Jiaotong University, Lanzhou, Gansu 730070, China (3) College of Mathematics and Information Science, Northwest Normal University, Lanzhou, Gansu 730070, China E-mail: bzh--sun@163.com Abstract: This paper proposes a new generalization of classical real-valued information systems, that is, interval-valued information systems. By defining an interval-valued dominance relation on a condition attribute, a rough set model and attribute reduction are established over interval-valued information systems. Moreover, several interesting properties are investigated by constructive approach. Furthermore, knowledge reductions of consistent and inconsistent interval-valued dominance decision information systems are studied, respectively. Subsequently, some descriptive theorems of knowledge reduction are presented for interval-valued dominance decision information systems. Finally, the validity of the model and conclusions is verified by numerical example. Keywords: rough set, interval-valued dominance relation, knowledge reduction 1. Introduction Rough set theory, introduced by Pawlak (1982), has become well established as an approach to studying information systems characterized by insufficient and incomplete information in a wide variety of applications. Various generalizations of rough approximations and applications have been made over the past years. Recently, rough set theory has become a popular mathematical tool in areas such as pattern recognition, image processing, feature selection (Pawlak & Skowron, 2007), conflict analysis (Pawlak, 1998), decision support (Tsumoto, 1998; Kim & Han, 2001;Tsumoto, 2004), data mining and knowledge discovery processes from large data sets (Lingras & Yao, 1998). The concept of rough set theory is founded on the assumption that every object of the universe of discourse is associated with some information. Objects characterized by the same information are indiscernible in view of their available information. This kind of generalization for indiscernibility relation forms the mathematical basis of rough set theory (Yao, 2003; Beynon et al., 2000; Skowron & Stepaniuk, 1996; Huynh & Nakamori, 2005). Classical rough set adopts two definable sets, namely the lower and upper approximations, to deal with the approximation computation for any subset of universe. Then, potential knowledge will be revealed from information systems by lower and upper approximations, and a decision rule can be induced. One important usage of rough set theory is knowledge reduction for information systems. Knowledge reduction deletes unnecessary attributes from the original attribute set, while the same ability to classify remains (Kryszkiewicz, 1998; Ziarko, 2003; Xu et al., 2010). Many valuable conclusions have been drawn through the method of knowledge reduction in consistent information systems (Zhang et al., 2003a, 2003b). Meanwhile, more attention has been paid to knowledge reduction in inconsistent systems in research on rough set theory. Many types of knowledge reduction also have been proposed in this field (Zhang et al., 2006; Wang & Lin, 2006; Xu & Zhang, 2008; Xu et al., 2010). Information systems or decision information systems transacting with Pawlak rough set theory are self-contained, and the value of the attributes is discrete or certain. At the same time, decision rule and knowledge discovery of information systems are acquired by attribute reduction based on equivalence relation (satisfying reflexive, symmetric and transitive properties). Recently, many authors have generalized equivalence relation to various forms such as similarity relation, dominance relation and covering relation in terms of Pawlak rough set theory. More detailed studies on generalized information systems follow from the perspective of knowledge reduction (Greco et al., 1999; Greco et al., 2001; Greco et al., 2002; Kazimierz, 2004; Zhu, 2007; Leung et al., 2008; Wu et al., 2005; Leung et al., 2006; Huang et al., 2012a, 2012b). Moreover, a large number of concepts of knowledge reduction such as generalized decision reduct, b � reduct (Kryszkiewicz, 2001; Zhang et al., 2006), probability reduct, dynamic reduct (Grzymala, 1997), entropy reduct and approximation entropy reduct (Slezak, 2002), distribution reduct and allocation reduct (Zhang et al., 2003a, 2003b, Zhang et al., 2006; Xu & Zhang, 2008; Xu et al., 2010) also have been developed for decision information systems. However, the value of attribute may be symbolic-valued, set-valued, fuzzy-valued or fuzzy number-valued and continuous-valued for the existing database in practice. Therefore, Pawlak rough set has some limitations in handling these values of attributes in information systems. Moreover, apart from different definitions of the knowledge reduction established for classical real-valued information © 2013 Wiley Publishing Ltd Expert Systems, xxxx 2013, Vol. 00, No. 00 systems, various generalized information systems are proposed, such as set-valued information systems (Guan & Wang, 2006; Zhang et al., 2006; Qian et al., 2008, 2009; Wang & Zhang, 2006), ordered information systems (Xu & Zhang, 2008; Xu et al., 2010), fuzzy information systems (Zhang et al., 2003a, 2003b; Yang et al., 2009), continuous- valued information systems (Ziarko, 2003; Zhang et al., 2003a, 2003b), interval-valued information systems and interval-valued fuzzy information systems (Sun et al., 2008; Gong et al., 2008; Zhang et al., 2009; Yang & Sheng, 2011; Huang, 2012; Dai et al., 2012; Chen & Miao, 2011), interval-valued intuitionistic fuzzy information systems (Zhang, 2010; Huang et al., 2012a, 2012b) and vague objective information systems (Feng et al., 2010). Though there is different background in theory and application for these generalized information systems or decision information systems, these methods go along with classical real-valued information systems. Moreover, the concepts of knowledge reduction for classical real-valued information systems have been successfully generalized in these information systems. The terms with the reduction of aforementioned various generalized information systems also use the same concepts, such as the classical real-valued information systems (Zhang et al., 2003a, 2003b; Zhang et al., 2006). So far, most research has been conducted on interval- valued information systems. Actually, the interval value of an attribute is a closed interval of the universe of real number for existing interval-valued information systems (Huang et al., 2006; Leung et al., 2008; Qian et al., 2008; Yang et al., 2009). There are many useful applications based on these interval-valued information systems, such as pattern recognition and automated knowledge acquisition. However, it would be of great value to understand what restricts the value of an attribute on the closed interval of [0,1] where the uncertainty decision or comprehension evaluation is concerned. Therefore, research on the information systems with the value of an attribute in closed interval [0,1] is a necessity. In this paper, we tentatively discuss the rough set model and knowledge reduction in interval-valued information systems. This paper studies interval-valued information systems by defining an interval-valued dominance relation over attribute set, that is, we establish a rough set model on interval-valued information systems. Like the Pawlak rough set, several properties of this model are also studied. Meanwhile, we also study interval-valued decision infor- mation systems by defining an interval-valued dominance relation over condition attribute and an equivalence relation over decision attribute, respectively. The attribute reduction of interval-valued information systems is investigated in a manner similar to classical real-valued information systems (Zhang et al., 2003a, 2003b; Mi et al., 2004; Wu et al., 2005; Zhang et al., 2006; Wu, 2008; Xu & Zhang, 2008; Xu et al., 2010). Furthermore, knowledge reduction of both consistent and inconsistent interval-valued decision information systems is discussed. In fact, all conclusions presented in this paper are generalization of the corresponding conclusions of classical real-valued decision information systems (Zhang et al., 2003a, 2003b; Mi et al., 2004; Wu et al., 2005; Zhang et al., 2006; Xu & Zhang, 2008; Xu et al., 2010). However, there also exist some differences with the corre- sponding conclusions of classical real-valued information systems because the interval values in closed interval [0,1] have some specialized properties. Generally speaking, all similar research focuses on the definition of a binary relation on condition and decision attributes. The existing research related to our work focuses on the following aspects. One is to define two dominance relations on both condition and decision attributes, as in ordered information systems (Xu & Zhang, 2008; Xu et al., 2010). Another is to define two equivalence relations over both condition and decision attributes, as in real-valued information systems (Zhang et al., 2003a, 2003b; Zhang et al., 2006; Mi et al., 2004). Some others define a binary relation or partial relation on condition and decision attributes, as in set-valued or language-valued information systems (Guan & Wang, 2006; Wang & Zhang, 2006; Wang & Lin, 2006; Qian et al., 2008; Qian et al., 2009). Therefore, some conclusions reached in the existing related work could not hold in the interval-valued (decision) information systems studied in this paper. The rest of this paper is organized as follows. Section 2 briefly introduces some important notions of the classical Pawlak rough set theory and the concept of interval-valued systems. Section 3 establishes the rough set model over interval-valued information systems. Furthermore, attribute reduction is studied in detail for interval-valued information systems. In Section 4, knowledge reduction for both consistent and inconsistent interval-valued dominance decision information systems is discussed, respectively. A numerical example is employed to test our conclusions. We conclude our research and set further future research directions in Section 5 2. Preliminary In this section, we present some concepts and conclusions that will be used in this paper (Pawlak & Skowron, 2007; Gong et al., 2008; Sun et al., 2008; Zhang, 2010). Let U be a non-empty finite set, which is called universe. Let R be an equivalence relation on U. That is, R is a binary relation and satisfies reflexive, symmetric and transitive properties. Then, we call (U,R) an approximation space. Moreover, binary relation R divides the universe U into piecewise disjoint classes such that any two different elements x and y belong to the same class if and only if (x,y) 2 R. Furthermore, U/R = {X1,X2, . . .,Xm} denotes all equiv- alence classes in universe U induced by equivalence relation R. If both of any two different elements x and y of U belong to Xi 2 U/R, then x and y are called indiscernible. The equivalence class of R and ∅ is called the primary set in approximation space (U,R). We describe the definition of information systems (Huynh & Nakamori, 2005; Gong et al., 2008; Sun et al., 2008) as follows. In general, a triple (U,A,{Va}a 2 A) is called an information system, where U is the set of object, A is the set of attribute and Va is the domain of attribute a, understood as a mapping a : U ! Va. It can be easily seen that each subset of attribute set A induces an equivalence relation: ind Að Þ ¼ x; yð Þ 2 U � U a xð Þ ¼ a yð Þ; a 2 Aj g:f © 2013 Wiley Publishing LtdExpert Systems, xxxx 2013, Vol. 00, No. 00 Then, ind(A) is called an indiscernibility relation and denotes ind(A) = ∩ a 2 Aind(a) (where ind(a) means ind({a})). If (x,y) 2 ind(A), we then say that the objects x and y are indiscernible with respect to A. In other words, we cannot distinguish x from y in terms of the attributes in A and vice versa. For any X ⊆ U, we define the two subsets of approximation space (U,R) as follows: R � X ¼ x 2 U x½ �R⊆ X �� �; R�X ¼ x 2 U x½ �R∩ X 6¼ ∅�� ��� We call R � X and R � X the lower and upper approximations of X with respect to (U,R). If R � X ¼ R�X, then X is called the definable set. Otherwise, X is called the rough set. The lower approximation R � X is the union of all elementary sets that are the subset of X, and the upper approximation R � X is the union of all elementary sets that have a non-empty intersection with X. The lower (upper) approximation R � X R � Xð Þ is interpreted as the collection of those elements of U that definitely (possibly) belong to X.(Huynh & Nakamori, 2005; Pawlak & Skowron, 2007; Gong et al., 2008; Sun et al., 2008). In what follows, we give the definition of interval value in [0,1] and its operators. We assume throughout that I is a unit closed interval, that is, I = [0,1]. Let [I] = {[a,b]|a ≤ b, a, b 2 I}. For any a 2 I, define �a ¼ a; a½ �, then �a 2 I½ �: Definition 2.1. Gorzafczary, 1988; Turksen, 1986; Gong et al., 2008; Sun et al., 2008; Zhang, 2010 For any ai 2 I, i 2 J, we define ∨i2Jai ¼ sup aiji 2 Jf g; ∧i2Jai ¼ inf aiji 2 Jf g; ∨i2J ai; bi½ � ¼ ∨i2Jai; ∨i2Jbi½ �; ∧i2J ai; bi½ � ¼ ∧i2Jai; ∧i2Jbi½ � where ∨ means maximum and ∧ means minimum. For any interval-valued [ai, bi] 2 [I], i = 1, 2, we define the following operations. [a1, b1] ¼ [a2, b2] if and only if a1 = a2, b1 = b2, [a1, b1] ≤ [a2, b2] if and only if a1 ≤ a2, b1 ≤ b2, [a1, b1] < [a2, b2] if and only if [a1,b1] ≤ [a2, b2] but [a1, b1] 6¼ [a2, b2]. Remark 2.1. It can be easily known that the following relation does not hold for any [ai, bi] 2 [I], i = 1, 2. a1; b1½ �≰ a2; b2½ � , a1; b1½ �> a2; b2½ �; a1; b1½ �≮ a2; b2½ � , a1; b1½ � ≥ a2; b2½ �: In general, the aforementioned two relations hold when [ai, bi] 2 [I], i = 1, 2 is real-valued. That is, ai = bi for any ai, bi 2 I, i = 1, 2. 3. Dominance-based rough set model over interval-valued information systems In this section, we discuss the basic rough set theory by defining an interval-valued dominance relation for interval- valued information systems. 3.1. Rough set model on interval-valued information systems The interval-valued information system was first defined by Sun and Gong (Sun et al., 2008; Gong et al., 2008). Here, we present the definition of interval-valued information systems as follows. Let U = {x1,x2, . . .,xk}, A= {a1,a2, . . .,am}. F = {fi|i ≤ m} is a family of mapping set between U and A, where fi is an interval- valued mapping from U to A. That is, fi : U ! [I](i ≤ m), and [I] is the domain of attribute ai. Then, we call triple (U,A,F) as an interval-valued information system(Gong et al., 2008; Sun et al., 2008). In general, every attribute set has determined an indiscernibility relation or equivalence relation in real- valued information systems. So, every attribute set defines an equivalence relation over interval-valued information systems as well. However, the equivalence relation could not be satisfied in practice, such as the multi-object comprehensive evaluation decision-making, the supplier selection decision-making with uncertainty and group decision-making in emergency events based on interval- valued information systems. So, there should be given a more suitable binary relation for interval-valued information systems. Therefore, we define an interval- valued dominance relation for interval-valued information systems in this section. It is also a generalization of the dominance relation in real-valued information systems (Zhang et al., 2003a, 2003b; Zhang et al., 2006; Xu & Zhang, 2008; Xu et al., 2010). Definition 3.1. Let (U,A,F) be interval-valued information systems. For any B ⊆ A, we define R≤B ¼ xi; xj � � fk xið Þ ≤ fk xj � � ; 8ak 2 B; xi; xj 2 U �� �� Then, R≤B is called an interval-valued dominance relation over interval-valued information systems. Furthermore, we call triple (U,A,F) as interval-valued information systems based on interval-valued dominance relation. For the sake of clarity, denote U; R≤A; F � � ¼ U; A; Fð Þ, and we call U; R≤A; F � � as interval-valued dominance information systems. Remark 3.1. If the value of attribute a 2 A is real-valued, U; R≤A; F � � will be real-valued information systems. Moreover, the interval- valued dominance relation will be real-valued dominance relation (Zhang et al., 2003a, 2003b; Zhang et al., 2006; Xu & Zhang, 2008; Xu et al., 2010). Denote x½ �≤B ¼ y 2 U fk xð Þ ≤ fk yð Þ; ak 2 Bj g:f It is easy to see that the interval-valued dominance relation satisfies the following properties and that all of © 2013 Wiley Publishing Ltd Expert Systems, xxxx 2013, Vol. 00, No. 00 them are similar to real-valued information systems, ordered information systems, set-valued information systems and other information systems with dominance relation (Zhang et al., 2003a, 2003b; Wang & Zhang, 2006; Xu & Zhang, 2008; Xu et al., 2010). Proposition 3.1. Let R≤A be an interval-valued dominance relation of U; R≤A; F � � . Then, the following conclusions hold. 1. R≤A is reflexive and transitive but not symmetric. Therefore, it is not an equivalence relation. 2. If B1 ⊆ B2 ⊆ A, then R≤A⊆R≤B2⊆R ≤ B1 : 3. If B1 ⊆ B2 ⊆ A, then x½ �≤A⊆ x½ �≤B2⊆ x½ � ≤ B1 : 4. If y 2 x½ �≤A, then y½ �≤A⊆ x½ �≤A and x½ �≤A ¼ ∪ y½ �≤A y 2 x½ �≤A �� �:� 5. y½ �≤A ¼ x½ �≤A if and only if f(x,a) = f(y,a), a 2 A. 6. C≤ ¼ x½ �≤A x 2 Uj g � is a covering of universe U. In what follows, we give the rough set model for interval- valued information systems. Let U; R≤A; F � � be interval-valued dominance information systems. For any X⊆ U, we define the lower and upper approximations of X as follows: R � ≤ A Xð Þ ¼ x 2 U x½ �≤A⊆X ��� o; R�≤A Xð Þ ¼ x 2 U x½ �≤A∩X 6¼ ∅�� �� n If R � ≤ A Xð Þ ¼ R �≤ A Xð Þ, then X is called a definable set with interval-valued dominance relation R≤A . Otherwise, X is called a rough set in U; R≤A; F � � : Like the rough set model over the existing generalized information systems (Zhang et al., 2003a, 2003b; Wang & Zhang, 2006; Xu & Zhang, 2008; Xu et al., 2010), the following properties are clear. Theorem 3.1. Let U; R≤A; F � � be an interval-valued dominance information system. Then, the lower and upper approximations satisfy the following properties: 1. R � ≤ A Uð Þ ¼ U; R �≤ A ∅ð Þ ¼ ∅; 2. R � ≤ A Xð Þ ¼ ≃R �≤ A ≃Xð Þ; R �≤ A Xð Þ ¼ ≃R� ≤ A ≃Xð Þ; 3. R � ≤ AðX∩YÞ¼R � ≤ AðXÞ∩R� ≤ AðYÞ; R � ≤ AðX∪YÞ¼R �≤ AðXÞ∪R �≤ AðYÞ; 4. R � ≤ AðX∪YÞ⊇R � ≤ A Xð Þ∪R� ≤ A Yð Þ; R �≤ AðX∩YÞ⊆R �≤ A Xð Þ∩R �≤ A Yð Þ; 5. R � ≤ A Xð Þ⊆X⊆R �≤ A Xð Þ; 6. R � ≤ A Xð Þ⊆R� ≤ A R� ≤ A Xð Þ � � ; R �≤ A R �≤ A Xð Þ � � ⊆R�≤A Xð Þ; where ≃ X stands for the complement of X. Proof It can be easily proven by the definitions earlier. Example 3.1. Table 1 gives an example of interval-valued information systems. It is easy to obtain the following dominance classes by Definition 3.1: x1½ �≤A ¼ x1; x2; x5f g x2½ �≤A ¼ x2; x5f g x3½ �≤A ¼ x2; x3; x4; x5f g x4½ �≤A ¼ x4f g x5½ �≤A ¼ x5f g Setting X = {x2, x3, x5}. Then, come the following relations: R � ≤ A Xð Þ ¼ x2; x5f g; R �≤ A Xð Þ ¼ x1; x2; x3; x5f g Clearly, R � ≤ A Xð Þ⊆X⊆R �≤ A Xð Þ: Remark 3.1. By Example 3.1, the following relations could not hold. 1. � R ≤ A Xð Þ ¼ ∪ x½ �≤Aj x½ �≤A⊆X; x 2 U � � ¼ x 2 Uj x½ �≤A⊆X � � : 2. �R ≤ A Xð Þ ¼ ∪ x½ �≤Aj x½ �≤A∩X 6¼ ∅; x 2 U � � ¼ x 2 Uj x½ �≤A∩X 6¼ ∅ � � : Similar to the definition by Huynh and Nakamori (Huynh & Nakamori, 2005; Gong et al., 2008; Zhang, 2010), we give the following definitions. Definition 3.2. Let U; R≤A; F � � be interval-valued dominance information systems. For any X, Y ⊆ U, X and Y are called lower rough equal if R � ≤ A Xð Þ ¼ R� ≤ A Yð Þ. Denote as X≂Y. X and Y are called upper rough equal if R �≤ A Xð Þ ¼ R �≤ A Yð Þ. Denote as X ’ Y. X and Y are called rough equal if they are both lower and upper equal. Denote as X � Y. It is easytoknow that the operators≂, ’ and� are equivalence relations. Then, the following conclusions are satisfied. Theorem 3.2. Let U; R≤A; F � � be interval-valued dominance information systems. For any subset X, Y, X0, Y0 ⊆ U, the following properties hold: 1. X ≂ Y , (X∩ Y ) ≂X and (X ∩Y ) ≂Y, 2. X ’ Y , (X∪Y ) ’ X and (X ∪ Y ) ’ Y, 3. If X ≂ X 0 and Y ≂ Y 0, then (X ∩Y ) ≂ (X 0 ∩Y 0 ), 4. If X ’ X 0 and Y ’ Y 0, then (X ∪Y ) ’ (X 0 ∪Y0 ), 5. If X ≂ Y, then X∩ (∼Y ) ≂ ∅, 6. If X ’ Y, then X∪ (∼Y ) ’ U. Proof It is easy to prove by the aforementioned definition. In general, the formula will not be satisfied when ’ is replaced by ≂ in Theorem 3.2 and vice versa. Table 1: An interval-valued information systems U a1 a2 a3 x1 [0.1, 0.5] [0.2, 0.6] [0.1, 0.6] x2 [0.3, 0.8] [0.2, 0.6] [0.2, 0.7] x3 [0.1, 0.5] [0.1, 0.6] [0.2, 0.6] x4 [0.2, 0.9] [0.1, 0.7] [0.3, 0.8] x5 [0.3, 1] [0.3, 0.9] [0.2, 0.8] © 2013 Wiley Publishing LtdExpert Systems, xxxx 2013, Vol. 00, No. 00 Remark 3.2. Let U; R≤A; F � � be interval-valued dominance information systems. For any X,Y⊆ U, the following relations do not hold according to Remark 3.1 and Theorem 3.1. 1. R � ≤ A Xð Þ ¼ ∩ Y⊆UjY≂Xf g; 2. R �≤ A Xð Þ ¼ ∪ Y⊆UjY ’ Xf g: However, these two equations hold for real-valued information systems. This is the difference between the interval-valued dominance and real-valued information systems (Zhang et al., 2003a, 2003b). Definition 3.3. Let U; R≤A; F � � be interval-valued dominance information systems. For any X⊆U, the precision of X in U; R≤A; F � � is defined as follows: aA Xð Þ ¼ R � ≤ A Xð Þ ��� ��� R �≤ A Xð Þ ��� ��� Moreover, rA(X) = 1 � aA(X) is called the roughness of X in U; R≤A; F � � : The ratio gA Xð Þ ¼ R � ≤ A Xð Þ ��� ��� Uj j defines the quality of approximation of X by R≤A in U; R ≤ A; F � � : Clearly, there is 0 ≤ aA(X) ≤ 1 and aA(X) ¼ 1 if and only if R � ≤ A Xð Þ ¼ X ¼ �R ≤ A Xð Þ: 3.2. Dominance-based attribute reduction for interval-valued information systems In this section, we study attribute reduction for interval- valued dominance information systems. In general, objects are described by different attributes. However, it is not necessary to know all attributes for the classification of information systems. That is, some attributes are unnecessary and do not affect the result of classification when removed from the attribute set. Meanwhile, some attributes are indispensable to the result of classification when removed from the attribute set. Furthermore, some attributes are relatively necessary for the classification and may determine the result by associating with other attributes. The attribute reduction presents a minimum attribute subset completely describing the classification as the original attribute set for information systems. First of all, we define the reduction for the interval-valued dominance information systems. Let U; R≤A; F � � be interval-valued dominance information systems. If B ⊆ A satisfies the following relations, 1. R≤B ¼ R≤A; 2. For any b 2 B; R≤B� bf g 6¼ R≤A: then, B is called a reduction of U; R≤A; F � � : Clearly, it is easy to know that there is not only one reduction of interval-valued dominance information systems. In what follows, we give the concepts of discernibility attribute set and discernibility matrix. Definition 3.4. Let U; R≤A; F � � be interval-valued dominance information systems. DP x; yð Þ ¼ ai 2 A fai xð Þ ≰ fai yð Þ; x; y 2 Uj gf is called a discernibility attribute set of an interval-valued dominance information system. Remark 3.3. According to Remark 2.1, we know that the discernibility attribute set will be defined as DP x; yð Þ ¼ ai 2 A fai xð Þ > fai yð Þ; x; y 2 Uj gf when U; R≤A; F � � is the real-valued information system. Remark 3.4. The relation of DP(x,y) ∩DP(y,x) = ∅, x, y 2 U could not hold in U; R≤A; F � � , but it is correct for real-valued information systems. This is the difference between the interval-valued domi- nance and real-valued information systems. The following Example 3.2 shows this difference directly. Example 3.2. Continued from Example 3.1 By Table 1, we have, respectively, the values of elements x1 and x4 with respect to attribute A as follows: fa1 x1ð Þ ¼ 0:1; 0:5½ �; fa1 x4ð Þ ¼ 0:2; 0:9½ �; fa2 x1ð Þ ¼ 0:2; 0:6½ �; fa2 x4ð Þ ¼ 0:1; 0:7½ �; fa3 x1ð Þ ¼ 0:1; 0:6½ �; fa3 x4ð Þ ¼ 0:3; 0:8½ � By Definition 3.4, we obtain the discernibility attribute set of x1 and x4 as follows: DP x1; x4ð Þ ¼ ai 2 Aj fai x1ð Þ≰ fai x4ð Þf g ¼ a2f g; DP x4; x1ð Þ ¼ ai 2 Aj fai x4ð Þ≰ fai x1ð Þf g ¼ a1; a2; a3f g Then, DP(x1,x4)∩DP(x4,x1) = {a2} 6¼ ∅. In what follows, we discuss the attribute reduction for interval-valued dominance information systems. Denote DP ¼ DP x; yð Þ x; y 2 Uj gf Then, DP is called the discernibility matrix of interval- valued dominance information systems U; R≤A; F � � : Denote DP0 ¼ DP x; yð Þ DP x; yð Þ 6¼ ∅j gf By the aforementioned definitions, the following conclusions are clear. Theorem 3.4. Let U; R≤A; F � � be interval-valued dominance information systems. For any B ⊆ A, the following propositions are equivalent. 1. R≤B ¼ R≤A: 2. B ∩B0 6¼ ∅, for any B0 2 DP0: 3. If B ∩B0 = ∅, for any B0 ⊆A, then B0=2DP0: © 2013 Wiley Publishing Ltd Expert Systems, xxxx 2013, Vol. 00, No. 00 Proof Firstly, we prove that 1 is equivalent to 2. 1 ⇒ 2: For any x, y 2 U, there is x½ �≤A ¼ y½ �≤B according to R≤B ¼ R≤A .So, if y =2 x½ �≤B , it can be easily obtained that fai xð Þ≰ fai yð Þ for any ai 2 B, x 2 U by the definition of x½ �≤B. That is, ai 2 DP(x,y). It proves B0 ∩B 6¼ ∅ for any B0 2 DP0; x; y 2 U: 2 ⇒ 1: Clearly, there exists ai 2 B that satisfies ai 2 B0 according to B∩B0 6¼ ∅ for any B0 2 DP0 .This shows fai xð Þ ≰ fai yð Þ; x; y 2 U. So, x½ �≤B∩ y½ �≤B ¼ ∅. Furthermore, there are x½ �≤A⊆ x½ �≤B and y½ �≤A⊆ y½ �≤B by the relation B⊆A. So, there are x½ �≤A ¼ x½ �≤B and y½ �≤A ¼ y½ �≤B for any x, y 2 U. Then, R≤B ¼ R≤A: Therefore, 1 is equivalent to 2. The equivalence of 2 and 3 has a similar proof. By the aforementioned discussion, the following theorem is clear. Theorem 3.5. Let U; R≤A; F � � be interval-valued dominance information systems. For any B ⊆ A, then B is a reduction of U; R≤A; F � � if and only if the following conditions are satisfied: 1. B ∩B0 6¼ ∅, for any B0 2 DP0: 2. For any b 2 B, there exists B0 2 DP0 that satisfies (B � {b}) ∩B0 = ∅. Proof It is easy to prove by the definition of reduction and Theorem 3.4. Example 3.3. Continued from Example 3.1 Table 2 gives the discernibility matrix of interval-valued dominance information systems in Table 1. By the aforementioned definition, we can obtain the discernible attribute set as follows: DP0 ¼ a2f g; a3f g; a1; a2f g; a1; a3f g; Ag Let B ¼ {a2,a3}. By Table 1, it is easy to obtain the interval-valued dominance classes as follows: x1½ �≤B ¼ x1; x2; x5f g x2½ �≤B ¼ x2; x5f g x3½ �≤B ¼ x2; x3; x4; x5f g x4½ �≤B ¼ x4f g x5½ �≤B ¼ x5f g The conclusion (1) of Theorem 3.4 R≤B ¼ R≤A can be easily verified. Meanwhile, it is easy to verify that B ∩B0 6¼ ∅ holds for any B 0 2 DP0: Let B0 = {a1} and B0 = ∅, respectively. It also can be easily seen that the conclusion (3) of Theorem 3.4 holds. Thus, the validity of Theorem 3.4 is tested. Furthermore, Theorem 3.5 also can be easily illuminated as the way to Theorem 3.4. Therefore, B = {a2,a3} is a reduction of interval-valued dominance information systems U; R≤A; F � � : 4. Dominance-based knowledge reduction for interval- valued decision information systems In this section, we establish some conclusions of knowledge reduction for interval-valued decision information systems by the rough set theory based on interval-valued dominance relation. Actually, another similar problem in knowledge reduction is feature selection, which has been a hot problem investigated by many researchers from the artificial intelligence and machine learning community (Kohavi & John, 1997; Praczyk, et al., 1999; Dash & Liu, 1997, 2003; Xiong & Funk, 2006, 2010; Vale et al., 2010). Feature selection is an effective technique in dealing with dimensionality reduction. Many valuable algorithms and results have been established for feature selection problem by these scholars. Moreover, rough set theory also has been used as an effective approach to feature selection problems in recent years (Kuncheva, 1992; Thangavel & Pethalakshmi, 2009; Tsenga & Huang, 2007; Maria & Maite, 2011). In this paper, we discuss the knowledge reduction or feature selection problem for interval-valued decision information systems by using dominance-based rough set theory over interval-valued information systems in detail. Decision information systems are special information systems with condition and decision attributes simultaneously. The decision information systems study the interrelationship between condition and decision attributes, and then acquire the decision rule from information systems. Let U; R≤A; F; D; gD � � be interval-valued dominance decision information systems, where U; R≤A; F � � is an interval-valued dominance information system, and D is a decision attribute set and satisfies A∩D ¼ ∅. F ¼ fai U ! I½ �; ai 2 Aj gf is a family of mapping between U and A; gD : U ! VD is a discrete integer-valued mapping from universe U to decision attribute set D, where VD ¼ {1,2, . . .,k} is the domain of decision attribute. So, an equivalence relation RD is defined by the integer- valued mapping gD. That is, RD¼ {(x,y)|gD(x)¼ gD(y),x,y2 U} is an equivalence relation over universe U. Denote U=RD ¼ x½ �D x 2 Uj g � where [x]D = {y|(x,y) 2 RD, x, y 2 U}. In what follows, we present the concept of consistent and inconsistent interval-valued dominance decision information systems. Table 2: Discernibility matrix DP U x1 x2 x3 x4 x5 x1 ∅ ∅ {a2} {a2} ∅ x2 {a1, a3} ∅ A {a1, a2} ∅ x3 {a3} ∅ ∅ ∅ ∅ x4 A A A ∅ {a3} x5 A A A {a1, a2} ∅ © 2013 Wiley Publishing LtdExpert Systems, xxxx 2013, Vol. 00, No. 00 Definition 4.1. Let U; R≤A; F; D; gD � � be interval-valued dominance decision information systems. If R≤A⊆RD , that is, x½ �≤A⊆ x½ �D . Then U; R≤A; F; D; gD � � is called a consistent interval-valued dominance decision information system. Otherwise, U; R≤A; F; D; gD � � is called an inconsistent interval-valued dominance decision information system. Remark 4.1. The binary relation based on condition and decision attributes is different over consistent and inconsistent interval-valued dominance information systems, that is, a dominance relation on condition attribute and an equivalence relation on decision attribute. However, the binary relation defined on condition and decision attributes is identical for real-valued decision information systems. That is, they define two equivalence relations or two dominance relations on condition and decision attributes (Zhang et al., 2003a, 2003b; Zhang et al., 2006; Xu & Zhang, 2008; Xu et al., 2010). In what follows, we discuss the methods of knowledge reduction for consistent and inconsistent interval-valued dominance decision information systems, respectively. 4.1. Consistent interval-valued dominance decision information systems We first introduce the concept of inclusion degree. Definition 4.2. Zhang et al., 2003a, 2003b Let (X,≤) be a partial order set. For any x, y 2 X, there exists a number D(y/x) that satisfies the following conditions: 1. 0 ≤ D(y/x) ≤ 1. 2. x ≤ y ⇒ D(y/x) ¼ 1. 3. x ≤ y ≤ z ⇒ D(x/z) ≤ D(x/y). Then, D(•) is called the inclusion degree over X. Let U; R≤A; F; D; gD � � be interval-valued dominance decision information systems for any B⊆A. Denote U=A≤B ¼ x½ �≤B x 2 Uj g � U=RD ¼ D1; D2 . . . ; Drf g where Dj ¼ [xj]D, j ¼ 1, 2, . . ., r. Obviously, U=A≤B is a covering, but U/RD is a partition of universe U. Denote D Dj= x½ �≤B � � ¼ Dj∩ x½ � ≤ B �� �� x½ �≤B �� �� ; Dj 2 U=RD where | • | stands for the cardinality of the set. Then, D Dj= x½ �≤B � � is an inclusion degree of P(U) (where P(U) stands for the power set of U) according to Definition 4.2. On the basis of the inclusion degree D Dj= x½ �≤B � � , the following conclusion is clear. Theorem 4.1. Let U; R≤A; F; D; gD � � be consistent interval-valued dominance decision information systems. For any B ⊆ A, the following propositions are equivalent. 1. D x½ �D= x½ �≤B � � ¼ 1, for any x 2 U. 2. R≤B⊆RD: 3. 1Uj j X X2U=RD � R≤B Xð Þ ��� ��� ¼ 1: Proof Because D x½ �D= x½ �≤B � � ¼ 1 , x½ �≤B⊆ x½ �D, this proves that 1 is equivalent to 2. According to Theorem 3.1, we have � R≤B Xð Þ⊆X: Therefore, 1 Uj j X X2U=RD � R≤B Xð Þ ��� ��� ¼ 1 means that � R≤B Xð Þ ¼ X: That is, R≤B⊆RD: So, we prove that 3 is equivalent to 2. Lemma 4.1. Zhang et al., 2003a, 2003b Let P be a partition of universe U, P; ≤ð Þ be a partial order set and D be an inclusion degree over (P(U),⊆), for any two partitions A and B of universe U, where A ¼ E1; ; E2; . . . ; ; Ekf g; B ¼ F1; ; F2; . . . ; ; Flf g: Denote D B=Að Þ ¼ ∧ k i¼1 ∨ l j¼1 D Fj=Ei � � Then, B is an inclusion degree over P; ≤ð Þ. Proof It is easy to obtain that 0 ≤ D B=Að Þ ≤ 1 by 0 ≤ D(Fj/Ei) ≤ 1. Meanwhile, the relation A ≤ B means that there exists Fj 2 B and satisfies the relation Ei ⊆Fj for any Ei 2 A. This is equivalent to ∨lj¼1D Fj=Ei � � ¼ 1: Hence, it is also equivalent to D B=Að Þ ¼ 1: Given C ¼ G1; G2 . . . ; Grf g and A ≤ B ≤ C: Then, for any Ei 2 A, there exists Fj 2 B , and Gp 2 C satisfies the relation Ei ⊆ Fj ⊆ Gp. Because D is the inclusion degree over P Uð Þ; ⊆ð Þ, so there is D(Ei/Gp) ≤ D(Ei/Fj). Therefore, it proves the relation D A=Cð Þ ≤ D A=Bð Þ: Lemma 4.2. Let U; R≤A; F; D; gD � � be consistent interval-valued dominance decision information systems. For any B⊆A, denote CB R≤B � � as the covering of universe U that is generated by the interval- valued dominance relation R≤B. Then, D U=RDð Þ=CB R≤B � �� � ¼ min x2U D x½ �D= x½ �≤B � � and D U=RDð Þ=CB R≤B � �� � ¼ 1 Uj j X X2U=RD � R≤ B Xð Þ ��� ��� are the inclusion degree of universe U. Proof It can be easily proved by Theorem 4.1 and Lemma 4.1. In the following, we establish the definition of reduction and also provide the judgement theorem of knowledge © 2013 Wiley Publishing Ltd Expert Systems, xxxx 2013, Vol. 00, No. 00 reduction based on the inclusion degree for consistent interval-valued dominance decision information systems by Theorem 4.1 and Lemma 4.2. Definition 4.3. Let U; R≤A; F; D; gD � � be consistent interval-valued dominance decision information systems. For any B ⊆ A, if the following equations are satisfied 1. D U=RDð Þ=CB R≤B � �� � ¼ 1: 2. D U=RDð Þ=CB R≤B� bf g � �� � < 1 for any b 2 B. then B is called a reduction of (U,A,F,D,gD). Definition 4.4. Zhang et al., 2006; Xu & Zhang, 2008; Xu et al., 2010; Li et al., 2010 Let a ¼ (a1,a2, . . .,an), b ¼ (b1,b2, . . .,bn) be two n dimension vectors. If ai ¼ bi(i = 1,2, . . ., n), then a is called equal to b, denoted as a ¼ b. If ai ≤ bi(i = 1,2, . . ., n), then a is called less than b, denoted as a ≤ b. Otherwise, if there exists i0(i0 2 {1,2, . . .,n}), and ai0 > bi0 is satisfied, then a is defined as no greater than b, denoted as a ≰ b: Remark 4.2. If ai, bi 2 [I], then a and b are called n-dimension interval- valued vectors. Therefore, similar to Definition 4.4, the definition of the relations a ¼ b, a ≤ b and a ≰ b is clear for an n-dimension interval-valued vector. Remark 4.3. It can be easily seen that a≰b is not equivalent to a > b because both a and b are interval-valued vectors. So is a < b and a 6¼ b. In what follows, we present the description of knowledge reduction for consistent interval-valued dominance decision information systems. Definition 4.5. Let U; R≤A; F; D; gD � � be consistent interval-valued dominance decision information systems. Define Dg x; yð Þ ¼ ak 2 Ajfak xð Þ ≰ fak yð Þf g; gD xð Þ 6¼ gD yð Þ;A; gD xð Þ ¼ gD yð Þ; where fak xð Þ stands for the value of object x 2 U about attribute ak. Then, Dg(x,y) is called the dominated discernibility attribute set of objects x and y with respect to consistent interval-valued dominance decision information systems. Moreover, Dg = (Dg(x,y)|x, y 2 U) is called the dominated discernibility matrix of consistent interval-valued dominance decision information systems. Here, the term for the aforementioned definition comes from Zhang et al. (2006), but the conditions in the definition are defined in a different manner. Theorem 4.2. Let U; R≤A; F; D; gD � � be consistent interval-valued dominance decision information system. For any B ⊆ A, 1. 8x; y 2 U; R≤B⊆RD , B∩Dg x; yð Þ 6¼ ∅; 2. R≤B⊆RD , 8B 0⊆A, if B∩B0 = ∅, then B0=2Dg: Proof 1. If R≤B⊆RD, then there is Dg(x,y) = A when gD(x) = gD(y). So, B∩Dg(x,y) 6¼ ∅. Meanwhile, there is y =2 x½ �D when gD(x) 6¼ gD(y). Then, x½ �≤B⊆ x½ �D is satisfied by R≤B⊆RD . So, y =2 x½ �≤B and ak 2 B satisfy fak xð Þ≰ fak yð Þ. That is, ak 2 Dg(x,y). This proves B ∩Dg(x,y) 6¼ ∅. Conversely, there is gD(x) 6¼ gD(y) when y =2 x½ �D for any x, y 2 U. Then, by B∩Dg(x,y) 6¼ ∅, we know there exists ak 2 B satisfying fak xð Þ≰ fak yð Þ. So, y =2 x½ �≤B: That is, x½ �≤B⊆ x½ �D: This proves R≤B⊆RD: 2. By the conclusion of 1, R≤B⊆RD , for any B0 2 Dg, and there is B ∩B0 6¼ ∅. By Theorem 4.2, the following conclusion is clear. For B ⊆A, denote g Bð Þ ¼ Πx;y2UwB Dg x; yð Þ � � where wB Dg x; yð Þ � � ¼ 1; B∩Dg x; yð Þ 6¼ ∅; 0; B∩Dg x; yð Þ ¼ ∅ Theorem 4.3. Let U; R≤A; F; D; gD � � be consistent interval-valued dominance decision information systems. Dg = {Dg(x,y)|x, y 2 U} is a dominated discernibility matrix. For any B⊆A, there is g Bð Þ ¼ 1 , R≤B⊆RD Proof It is easy to prove by the aforementioned definition. Theorems 4.2 and 4.3 give the conditions of sufficiency and necessity of knowledge reduction for consistent interval-valued dominance decision information systems. Next, we discuss the knowledge reduction for inconsistent interval-valued dominance decision information systems. 4.2. Inconsistent interval-valued dominance decision information systems In general, we also can define the distribution reduction, generalized distribution reduction and maximum distribution reduction with corresponding judgement theorems of knowledge reduction similar to real-valued inconsistent decision, inconsistent ordered and set-valued decision and others (Wang & Zhang, 2006; Xu & Zhang, 2008; Xu et al., 2010; Li et al., 2010; Zhang, 2010). In this section, we discuss another two reductions for inconsistent interval-valued dominance decision information systems. We begin with some basic definitions as follows. Let U; R≤A; F; D; gD � � be inconsistent interval-valued dominance decision information systems. © 2013 Wiley Publishing LtdExpert Systems, xxxx 2013, Vol. 00, No. 00 For any B ⊆ A, denote �B ¼ 1 Uj j Xr j¼1 �R ≤ B Dj � � j �� dB xð Þ ¼ Dj Dj∩ x½ �≤B 6¼ ∅; x 2 U �� �� where Dj 2 U/RD ¼ {[x]D|gD(x) ¼ gD(y), x, y 2 U}. It is easy to know that the following two propositions are clear by dB(x) and �B. Proposition 4.1. Let U; R≤A; F; D; gD � � be inconsistent interval-valued dominance decision information systems. For any B⊆A, 1. dA(x) ⊆dB(x) for any x 2 U. 2. If x½ �≤B⊆ y½ �≤B, then dB(x) ⊆dB(y)x, for any y 2 U. Proposition 4.2. Let U; R≤A; F; D; gD � � be inconsistent interval-valued dom- inance decision information systems. For any B ⊆A, the following conditions hold. 1. 1 ≤ �B ≤ |U/RD|. 2. For any Dj 2 U/RD, �B ¼ 1 , �R ≤ B Dj � � ¼ Dj; �B ¼ U=RDj j , �R ≤ B Dj � � ¼ U; Dj 2 U=RD 3. If �R ≤ A Dj � � ⊆�R≤B Dj � � , then �A ≤ �B. On the basis of dB(x) and �B, we give two reductions for inconsistent interval-valued dominance decision information system as follows. Definition 4.6. Let U; R≤A; F; D; gD � � be inconsistent interval-valued dom- inance decision information systems. For any B⊆ A, 1. If dA(x) ¼ dB(x) for any x 2 U, then B is called a dominated allocation consistent set. Furthermore, if B � {a} for any a 2 B is not a dominated allocation consistent set, then B is called a dominated allocation reduction; 2. If �B ¼ �A for any x 2 U, then B is called an approximation-dominated consistent set. Furthermore, if B � {a} for any a 2 B is not an approximation- dominated consistent set, then B is called an approximation-dominated reduction. Theorem 4.4. Let U; R≤A; F; D; gD � � be inconsistent interval-valued dom- inance decision information systems. For any B ⊆ A, then B is a dominated allocation consistent set if and only if B is an approximation-dominated consistent set. Proof Let B be a dominated allocation consistent set. That is, dB (x) ¼ dA(x) for any x 2 U. Then, x 2 �R≤B Dj � � , x½ �≤B∩Dj 6¼ ∅ , Dj 2 dB xð Þ , Dj 2 dA xð Þ , x½ �≤A∩Dj 6¼ ∅ , x 2 �R ≤ A Dj � � This proves �R ≤ B Dj � � ¼ �R≤A Dj � � : Therefore, �B ¼ �A, and B is the approximation- dominated consistent set. Conversely, if B is an approximation-dominated consistent set, then �B ¼ �A. That is, Xr j¼1 �R ≤ B Dj � ��� �� ¼ Xr j¼1 j�R≤A Dj � � j: Meanwhile, �R ≤ A Dj � � ⊆�R≤B Dj � � holds for any Dj 2 U/RD. Therefore, �R ≤ A Dj � � ¼ �R≤B Dj � � : So, Dj 2 dB xð Þ , x½ �≤B∩Dj 6¼ ∅ , x 2 �R≤B Dj � � , x 2 �R≤A Dj � � , x½ �≤A∩Dj 6¼ ∅ , Dj 2 dA xð Þ This proves dB(x) ⊆dA(x). Furthermore, we know that dA(x)⊆dB(x) by Proposition 4.2. Thus, we prove that dA(x)¼ dB(x). This proves that B is a dominated allocation consistent set. Example 4.1. Table 3 gives an inconsistent interval-valued dominance decision information system. It is easy to obtain the interval-valued dominance classes and equivalence classes by condition attribute A and decision attribute D, respectively, as follows: x1½ �≤A ¼ x1; x2; x5f g x2½ �≤A ¼ x2; x5f g x3½ �≤A ¼ x2; x3; x4; x5f g x4½ �≤A ¼ x4f g x5½ �≤A ¼ x5f g and x1½ �D ¼ x5½ �D ¼ x1; x5f g x2½ �D ¼ x4½ �D ¼ x2; x4f g x3½ �D ¼ x3f g It can be easily seen that ∪x2U x½ �≤A is a covering, and ∪ x 2 U[x]D is a partition of universe U. Let D1 ¼ x1½ �D ¼ x5½ �D D2 ¼ x2½ �D ¼ x4½ �D D3 ¼ x3½ �D Table 3: Inconsistent interval-valued dominance decision information system U a1 a2 a3 D x1 [0.1, 0.5] [0.2, 0.6] [0.1, 0.6] 3 x2 [0.3, 0.8] [0.2, 0.6] [0.2, 0.7] 2 x3 [0.1, 0.5] [0.1, 0.6] [0.2, 0.6] 1 x4 [0.2, 0.9] [0.1,0.7] [0.3, 0.8] 2 x5 [0.3, 1] [0.3,0.9] [0.2, 0.8] 3 © 2013 Wiley Publishing Ltd Expert Systems, xxxx 2013, Vol. 00, No. 00 We calculate the value of dA(x)(x 2 U) as follows: dA x1ð Þ ¼ D1; D2f g; dA x2ð Þ ¼ D1; D2f g; dA x3ð Þ ¼ D1; D2; D3f g; dA x4ð Þ ¼ D2f g; dA x5ð Þ ¼ D1f g Taking B ¼ {a2,a3} ⊆A ¼ {a1,a2,a3}. for any x 2 U, we can easily obtain that x½ �≤A ¼ x½ �≤B: Then, dB(x) ¼ dA(x) holds. So, B is a dominated allocation consistent set. In what follows, we give the two descriptive theorems of knowledge reduction for inconsistent interval-valued dominance decision information systems. Theorem 4.5. Let U; R≤A; F; D; gD � � be inconsistent interval-valued dom- inance decision information systems. For any B⊆A, x, y 2 U, B is a dominated allocation consistent set if and only if x½ �≤B⊈ y½ �≤B when dA xð Þ⊈dA yð Þ: Proof 1. Suppose that x½ �≤B⊈ y½ �≤B does not hold when dA xð Þ⊈dA yð Þ for any x, y 2 U. That is, x½ �≤B⊆ y½ �≤B; then we know dB(x) ⊆ dB(y) by Proposition 4.1. Moreover, B is a dominated allocation consistent set. So, dA(x) ¼ dB(x) and dA(y) ¼ dB(y). Therefore, there is dA(x) ⊆ dA(y). This is a contradiction. Conversely, we only need to prove that dB(x) ¼ dA(x) for any x 2 U. It is easy to know that dA(x)⊆ dB(x) holds. Then, we only prove dB(x) ⊆dA(x). In what follows, we prove this conclusion by two different cases. • If dB(x) ¼ ∅, the conclusion holds. • If dB(x) 6¼ ∅, x½ �≤B ⊈ y½ �≤B when dA xð Þ ⊈ dA yð Þ: That is, if x½ �≤B⊆ y½ �≤B , then dA(x) ⊆dA(y) holds for any x, y 2 U. Because dB(x) 6¼ ∅ andDj∩ x½ �≤B 6¼ ∅hold for any Dj 2 U/RD, let y 2 Dj∩ x½ �≤B . Then, there are y 2 x½ �≤B and y 2 Dj. So, y½ �≤B⊆ x½ �≤B: This proves that dA(y) ⊆dA(x) holds. It is easy to know that y 2 y½ �≤A, that is, y 2 Dj∩ y½ �≤A: So, Dj∩ x½ �≤A⊆Dj∩ y½ �≤A: This proves that dB(x) ⊆dA(y). The aforementioned two cases prove that dB(x)⊆dA(x) hold. So, the conclusion is proved. The following is a corollary. Corollary 4.1. Let U; R≤A; F; D; gD � � be inconsistent interval-valued dom- inance decision information systems. For any B ⊆ A, the following two conclusions are equivalent. 1. B is an approximation-dominated consistent set. 2. x½ �≤B⊈ y½ �≤B when dA xð Þ⊈dA yð Þ; x; y 2 U: On the basis of dominated consistent attribute sets, we can obtain the reduction for inconsistent interval-valued dominance decision information systems. In what follows, we give another descriptive theorem of knowledge reduction for inconsistent interval-valued dominance decision information systems. First of all, we present the following definition. Let U; R≤A; F; D; gD � � be inconsistent interval-valued dominance decision information systems. Denote D�d ¼ x; yð Þ dA xð Þ⊆dA yð Þj gf Definition 4.7. Let U; R≤A; F; D; gD � � be inconsistent interval-valued dom- inance decision information systems. Define Dd x; yð Þ ¼ fak 2 A fak xð Þ≰ fak yð Þj g; x; yð Þ 2 D�d; A; x; yð Þ =2 D�d ( Then, Dd(x,y) is called the dominated allocation discernibility attribute set of x and y. Let U; R≤A; F; D; gD � � be inconsistent interval-valued dominance decision information systems. Denote Dd ¼ Dd x; yð Þ x; y 2 Uj Þð Then, Dd is called the dominated allocation discernibility matrix for inconsistent interval-valued dominance decision information systems. On the basis of the aforementioned definitions, we have the following descriptive theorem. Theorem 4.6. Let U; R≤A; F; D; gD � � be inconsistent interval-valued dom- inance decision information systems. For any B ⊆ A, B is a dominated allocation consistent set if and only if B ∩ Dd(x,y) 6¼ ∅ for any x; yð Þ 2 D�d: Proof 1. For any x, y 2 U, dA xð Þ⊈dA yð Þ holds when (x,y) 2 U. Furthermore, we have x½ �≤B⊆ y½ �≤B because B is a dominated allocation consistent set. Then, there are three cases for x½ �≤B and y½ �≤B: (a) x½ �≤B⊈ y½ �≤B; (b) x½ �≤B∩ y½ �≤B ¼ ∅; (c) x½ �≤B∩ y½ �≤B⊆ x½ �≤B and x½ �≤B∩ y½ �≤B⊆ y½ �≤B: In what follows, we prove B ∩Dd(x,y) 6¼ ∅ for the aforementioned three cases. (a) If x½ �≤B⊈ y½ �≤B, there exists z 2 y½ �≤B that satisfies z =2 x½ �≤B. Then, there exists ak 2 B that satisfies fak xð Þ≰fak zð Þ: So, fak yð Þ≤fak zð Þ according to z 2 y½ �≤B: Therefore, fak yð Þ≤fak xð Þ: This proves ak 2 Dd(x,y). That is, B ∩Dd(x,y) 6¼ ∅. © 2013 Wiley Publishing LtdExpert Systems, xxxx 2013, Vol. 00, No. 00 (b) If x½ �≤B∩ y½ �≤B ¼ ∅ , there exists ak 2 B that satisfies fak xð Þ≰fak yð Þ. That is, B ∩Dd(x,y) 6¼ ∅. Otherwise, there is fak xð Þ ≤ fak yð Þ for any ak 2 B. So, it proves that y 2 x½ �≤B: This is contradicted by x½ �≤B∩ x½ �≤B ¼ ∅: (c) If x½ �≤B∩ y½ �≤B⊆ x½ �≤B and x½ �≤B∩ y½ �≤B⊆ y½ �≤B , then it can be proved in the same way as (a). Considering the aforementioned discussion, B ∩Dd (x, y) 6¼ ∅ when B is a dominated allocation consistent set for x; yð Þ 2 D�d: Conversely, there is B ∩Dd(x,y) 6¼ ∅ for x; yð Þ 2 D�d: Then, there exists ak 2 B satisfying ak 2 Dd(x,y). So, we have fak xð Þ≰fak yð Þ. That is, y=2 x½ �≤B: Furthermore, there is x½ �≤B⊈ y½ �≤B because y 2 y½ �≤B . Meanwhile, there is dA xð Þ⊈dA yð Þ for any x; yð Þ 2 D�d: Hence, we have x½ �≤B⊈ y½ �≤B when dA xð Þ⊈dA yð Þ: Thus, B is a dominated allocation consistent set. Example 4.2. Continued from Example 4.1 Table 4 gives the discernibility matrix for inconsistent interval-valued dominance decision information systems. From Table 4, it easy to know that B = {a2,a3} is a dominated allocation reduction of an inconsistent interval-valued dominance decision information system U; R≤A; F; D; gD � � : Moreover, the following results can be easily calculated according to Example 4.1: x1½ �≤B ¼ x1; x2; x5f g; x2½ �≤B ¼ x2; x5f g; x3½ �≤B ¼ x2; x3; x4; x5f g; x4½ �≤B ¼ x4f g; x5½ �≤B ¼ x5f g and dA x1ð Þ ¼ D1; D2f g; dA x2ð Þ ¼ D1; D2f g; dA x3ð Þ ¼ D1; D2; D3f g; dA x4ð Þ ¼ D2f g; dA x5ð Þ ¼ D1f g By these results, we can verify the condition: If dA xð Þ⊈dA yð Þ, then x½ �≤B⊈ y½ �≤B, for any x, y 2 U. This is the conclusion of Theorem 4.5. Furthermore, it can be easily known that Dd(x,y) ¼ {{a2}, {a3}, {a1,a2}, {a1,a3}, A} by Definition 4.7. Then we have B ∩Dd(x,y) 6¼ ∅, for any x, y 2 U. This is the conclusion of Theorem 4.6. 5. Conclusions and remarks Knowledge reduction over information systems and the generalization of real-valued information systems are two main research directions both in theory and application of rough set theory. This paper studies a type of extended real-valued information systems, that is, interval-valued information systems. Moreover, we study the basic rough set theory over interval-valued information systems. We systematically discuss attribute reduction for interval-valued dominance information systems based on the proposed rough set model. To discuss knowledge reduction for interval-valued dominance decision information systems, some concepts concerning the reduction of both consistent and inconsistent interval-valued dominance decision information systems have been established by the definitions of an interval-valued dominance relation and an equivalence relation in U; R≤A; F; D; gD � � .Some descriptive theorems for knowledge reduction are given in detail for interval-valued dominance decision information systems. It is also an extension of real-valued decision information systems. A numerical example is applied to test the methods and conclusions of the interval-valued dominance decision information systems as well. There are at least two aspects in the study of rough set theory: constructive and axiomatic approaches (Wu and Zhang 2004). The same is true for interval-valued information systems. In this paper, we define the rough lower (upper) approximation operator and discuss the basic properties by the constructive method. So further work should consider the axiomatic approaches to rough lower (upper) approximation operator and decision-making in the context of an interval-valued environment. Acknowledgements The authors thank the editor-in-chief Dr Jon Hall and the anonymous reviewers for valuable comments to improve the quality of this paper. The work was partly supported by the National Science Foundation of China (71161016 and 71071113), the Foundation for the Author of National Excellent Doctoral Dissertation of PR China (200782), the Shuguang Plan of Shanghai Education Development Foundation and Shanghai Education Committee (08SG21), the Shanghai Pujiang Program, and Shanghai Philosophical and Social Science Program (2010BZH003) and the Fundamental Research Funds for the Central Universities. The third author is supported by the National Science Foundation of China (71061013). References BEYNON, M., B. CURRY and P. MORGAN (2000) Classification and rule induction using rough sets theory, Expert Systems, 17, 136–148. CHEN, Y. and D.Q. MIAO (2011) Rule extraction based on granulation order in interval-valued fuzzy information system, Expert Systems with Applications, 38, 12249¨C12261. DAI, J.H., W.T. WANG, Q. XU and H.W. TIAN (2012) Uncertainty measurement for interval-valued decision systems based on extended conditional entropy, Knowledge-Based Systems, 27, 443–450. DASG, M. and H. LIU (2003) Consistency-based search in feature selection, Artificial Intelligence, 151, 155–176. DASH, M. and H. LIU, (1997) Feature selection for classification, Intelligent Data Analysis, 1, 131. Table 4: Dominated allocation discernibility matrix Dd U x1 x2 x3 x4 x5 x1 ∅ ∅ {a2} A A x2 {a1, a3} ∅ A A A x3 {a3} ∅ ∅ A A x4 A A A ∅ A x5 A A A {a1, a2} ∅ © 2013 Wiley Publishing Ltd Expert Systems, xxxx 2013, Vol. 00, No. 00 FENG, L., G.Y. WANG and X.X. LI (2010) Knowledge acquisition in vague objective information systems based on rough sets, Expert Systems, 17, 129–142. GONG, Z.T., B.Z. SUN and D.G. CHEN (2008) Rough set theory for the interval-valued fuzzy information systems, Information Scineces, 178, 1968–1985. GORZAFCZARY, B. (1988) Interval-valued fuzzy controller based on verbal modal of object, Fuzzy Sets and Systems, 28, 45–53. GRECO, S., B. MATARAZZO and R. SLOWINSKI (1999) Rough approximation of a preference relation by dominance relations, European Journal of Operational Research, 117, 63–83. GRECO, S., B. MATARAZZO and R. SLOWINSKI (2001) Rough sets theory for multicriteria decision analysis, European Journal of Operational Research, 129, 1–47. GRECO, S., B. MATARAZZO and R. SLOWINSKI (2002) Rough approximation by dominance relation, International Journal of Intelligent Systems, 17, 153–171. GRZYMALA, B.J.W. (1997) A new version of the rule induction system LERS, Fundamenta Informaticae, 31, 27–39. GUAN, Y.Y. and H.K. WANG (2006) Set-valued information systems, Information Sciences, 176, 2507–2525. HUANG, B. (2012) Graded dominance interval-based fuzzy objective information systems, Knowledge-Based Systems, 24, 1004–1012. HUANG, J.J., C.S. ONG and G.H. TZENG (2006) Interval multidimensional scaling for group decision using rough set concept, Expert Systems with Applications, 31, 525–530. HUANG, B., D.K. WEI, H.X. LI and Y.L. ZHANG (2012a) Using a rough set model to extract rules in dominance-based interval- valued intuitionistic fuzzy information systems, Information Sciences, DOI.org/10.1016/j.ins.2012.09.010. HUANG, B., H.X. LI and D.K. WEI (2012b) Dominance-based rough set model in intuitionistic fuzzy information systems, Knowledge- Based Systems, 28, 115–123. HUYNH, V.N. and Y. NAKAMORI (2005) A roughness measure for fuzzy sets, Information Scineces, 173, 255–275. KAZIMIERZ, Z. (2004) Rough approximation of a preference relation by a multi-attribute dominance for deterministic, stochastic and fuzzy decision problems, European Journal of Operational Research, 159, 196–206. KIM, K.J. and I. HAN (2001) The extraction of trading rules from stock market data using rough sets, Expert Systems, 18, 194–202. KOHAVI, R. and JOHN, G.H. (1997) Wrapper for feature subset selection, Artificial Intelligence, 97, 273–324. KRYSZKIEWICZ, M. (1998) Rough set approach to incomplete information systems, The Information of the Science, 112, 39–49. KRYSZKIEWICZ, M. (2001) Comparative study of alternative type of knowledge reduction in inconsistent systems, International Journal of Intelligent Systems, 16, 105–120. KUNCHEVA, L.L. (1992) Fuzzy rough sets: application to feature selection, Fuzzy Sets and Systems, 51, 147–153. LEUNG, Y., W.Z. WU and W.X. ZHANG (2006) Knowledge acquisition in incomplete information systems: a rough set approach, European Journal of Operational Research, 168, 164–180. LEUNG, Y., M.F. MANFRED, W.Z. WU and J.S. MI (2008) A rough set approach for the discovery of classification rules in interval- valued information systems, International Journal of Approximate Reasoning, 47, 233–246 LINGRAS, P.J. and YAO, Y.Y. (1998) Data mining using extensions of the rough set model, Journal of the American Society for Information Science, 49, 415–422. LI, Y., J. ZHAO, N.X. SUN and SAMKAR, K.P. (2010) Generalized distribution reduction reduction in inconsistent decision systems based on dominance relations, J. Xu et al., (Eds.): RSKT, 6401, 151–158. MARIA, S. and L.S. MAITE (2011) Rough set based approaches to feature selection for case-based reasoning classifiers, Pattern Recognition Letters, 32, 280–292. MI, J.S., W.Z. WU and W.X. ZHANG (2004) Approach to knowledge reduction based on variable precision rough set model, Information Sciences, 159, 255–272. PAWLAK, Z. (1982) Rough sets. International Journal Information Science, 11, 341–356. PAWLAK, Z. (1998) An inquiry into anatomy of conflicts, European Journal of Operational Research, 109, 184–190. PAWLAK, Z. and SKOWRON, A. (2007) Rough sets: some extensions, Information Sciences, 177, 28–40. PRACZYK, K., H. KIENDL and T. SLAWINSKI (1999) Finding relevant process characteristics with a method for data-based complexity reduction, Lecture Notes in Computer Science 1625, 548–555. QIAN, Y.H., J.Y. LIANG and C.Y. DANG (2008) Interval ordered information systems, Computers and Mathematics with Applications, 56, 1994–2009. QIAN, Y.H., C.Y. DANG, J.Y. LIANG, and D.W. TANG (2009) Set- valued ordered information systems, Information Sciences, 179, 2809¨C2832. SKOWRON, A. and J. STEPANIUK (1996) Tolerance approximation space, Fundanation Information, 27, 245–253. SLEZAK, D. (2002) Approximation entropy reducts, Fundamenta Information, 53, 365–390. SUN, B.Z., Z.T. GONG and D.G. CHEN (2008) Fuzzy rough set theory for the interval-valued fuzzy information systems, Information Scineces, 178, 2794–2815. THANGAVEL, K. and A. PETHALAKSHMI (2009) Dimensionality reduction based on rough set theory: a review, Applied Soft Computing, 9,1–12. TSENGA, T.L. and C.C. HUANG (2007) Rough set-based approach to feature selection in customer relationship management, Omega, The International Journal of Management Science, 35,365–383. TSUMOTO, S. (1998) Automated extraction of medical expert system rules from clinical databases based on rough set theory, Information Sciences, 112, 67–84. TSUMOTO, S. (2004) Mining diagnostic rules from clinical databases using rough sets and medical diagnostic model, The Information of the Science, 162, 65–80. TURKSEN, B. (1986) Interval-valued fuzzy sets based on normal forms, Fuzzy Sets and Systems, 20, 191–210. VALE, K.O., A.F. NETO and A.M.P. CANUTO (2010) Using a reinforcement-based feature selection method in classifier ensemble, Hybrid Intelligent Systems (HIS), 10th International Conference on, 23–25, 213–218. WANG, J.Y. and R.B. LIN (2006) A new knowledge reduction in inconsistent decision information system, IEEE International Conference on Granular Computing, 377–380. WANG, H and W.X. ZHANG (2006) Knowledge reduction in set- valued decision information systems, Lecture Notes in Control and Information Sciences, 344, 927–932. WU, W.Z. (2008) Attribute reduction based on evidence theory in incomplete decision systems, Information Sciences, 178, 1355–1371. WU, W.Z., W.X. ZHANG (2004) Constructive and axiomatic approaches of fuzzy approximation operators, The Information of the Science, 159, 233–254. WU, W.Z., Y. LEUNG and J.S. SHENG (2005) On characterizations of (I, J)-fuzzy rough approximation operators, Fuzzy Sets and Systems, 154(1), 76–102. WU, W.Z., W.X. ZHANG and H.Z. LI (2003) Knowledge acquisition in incomplete fuzzy information systems via the rough set approach, Expert Systems, 20, 280–286. XIONG, N. and P. FUNK (2006) Construction of fuzzy knowledge bases incorporating feature selection, Soft Computing, 9(10), 796–804 XIONG, N. and P. FUNK (2010) Combined feature selection and similarity modeling in case-based reasoning using hierarchical memetic algorithm, In: Proceedings of the IEEE World Congress on Computational Intelligence, 1537–1542. XU, W.H. and W.X. ZHANG (2008) Methods for knowledge reduction in inconsistent ordered information systems, Journal of Applied Mathematics and Computing, 26, 313–323. XU, W.H., X.Y. ZHANG, J.M. ZHANG and W.X. ZHANG (2010) Attribute reduction in ordered information systems based on evidence theory, Knowledge and Information Systems, 25, 169–184. YANG, H. and C. SHENG (2011) New roughness measures of the interval-valued fuzzy sets, Expert Systems with Applications, 38, 2849–2856. YANG, X.B., D.J. YU, J.Y. YANG and L.H. WEI (2009) Dominance- based rough set approach to incomplete interval-valued information system, Data & Knowledge Engineering, 68, 1331–1347. YAO, Y.Y. (2003) Probabilistic approaches to rough sets, Expert Systems, 20, 2871–297. © 2013 Wiley Publishing LtdExpert Systems, xxxx 2013, Vol. 00, No. 00 http://DOI.org ZHANG, Z.M. (2010) An interval-valued rough intuitionistic fuzzy set model, International Journal of General Systems, 39, 135–164. ZHANG, W.X., Y. LEUNG and W.Z. WU (2003a) Information Systems and Knowledge Discovery, Beijing: Science Press, 13–56. ZHANG, M., L.D. XU, W.X. ZHANG and H.Z LI (2003b) A rough set approach to knowledge reduction based on inclusion degree and evidence reasoning theory, Expert Systems, 20, 298–304. ZHANG, W.X., Y.Y. YAO and Y. LEUNG (2006) Rough Sets and Concept Lattices. Xi’an: Xi’an Jiaotong University Press, 325–354. ZHANG, H.Y., W.X. ZHANG and W.Z. WU (2009) On characterization of generalized interval-valued fuzzy rough sets on two universes of discourse, International Journal of Approximate Reasoning, 51, 56–70. ZHU, W. (2007) Generalized rough sets based on relations, Information Sciences, 177, 4997–5011. ZIARKO, W. (2003) Acquisition of hierarchy structured probabilistic decision tables and rules from data, Expert Systems, 20, 305–310. The authors Bingzhen Sun Bingzhen Sun is currently a PhD candidate of the School of Economics & Management, Tongji University in Shanghai, China. He received the BS degree from the Department of Mathematics and Applied Mathematics at the Northwest Normal University in Lanzhou, China, in 2003. He received the MS degree in applied mathematics from the College of Mathematics and Information Science, Northwest Normal University in Lanzhou, China, in 2006. His research interests include rough sets theory and applications, fuzzy sets and system, decision-making with uncertainty and operations research. Weimin Ma Weimin Ma, a professor of the School of Economics & Management, serves as an authorized PhD supervisor in management science and engineering at Tongji University in Shanghai, China. He received the BS degree from the Department of Mechanical Manufacturing Engineering at the Northwest Polytechnic University in Xi’an, China, in 1993. He received the MS and PhD degrees in management science and engineering from the School of Economics & Management, Xi’an Jiaotong University, Xi’an, China, in 1999 and 2003, respectively. His research interests include on-line computation, fuzzy sets and system, information system and technology, decision-making with uncertainty, algorithm design and operations research. Zengtai Gong Zengtai Gong received his PhD degree in science from the Harbin Institute of Technology in China. He is a professor and doctor supervisor at the College of Mathematics and Statistics, Northwest Normal University in China. His research directions include rough set theory, fuzzy analysis, real analysis and their applications in environment problems and management of water resources. © 2013 Wiley Publishing Ltd Expert Systems, xxxx 2013, Vol. 00, No. 00