Intelligent Information Ma nagement, 2011, 3, 131136 doi:10.4236/iim.2011.34016 Published Online July 2011 (http://www.SciRP.org/journal/iim) Copyright © 2011 SciRes. IIM Rough Computational Approach to UAR based on Dominance Matrix in IOIS Xiaoyan Zhang, Weihua Xu 1 Chongqing University of Technology, Chongqing, China Email: zhangxyms@gmail.com, chxuwh@gmail.com Received March 28, 2011; revised June 30, 2011; accepted July 7, 2011 Abstract Rough set theory is a new mathematical tool to deal with vagueness and uncertainty. The classical rough set theory based on equivalence relation has made a great progress, while the equivalence relation is too harsh to meet and is extended to dominance relation in real world. It is important to investigate rough computational methods for rough set theory, which is one of the bottleneck problems in the development of rough set theory. In this article, rough computational approach to upper approximation reduction (UAR) is discussed based on dominance matrix in inconsistent ordered information systems (IOIS). The algorithm of upper approximation reduction is obtained, from which we can provide approach to upper approximation reduction operated sim ply in inconsistent systems based on dominance relations. Finally, an example illustrates the validity of this method, and shows the method is excellent to a complicated information system. Keywords: Dominance Relation, Information System, Rough Set, Upper Approximation Reduction 1. Introduction The rough set theory, proposed by Pawlak in the early 1980s [1], is an extension of the classical set theory for modeling uncertainty or imprecision information. The re search has recently roused great interest in the theoretical and application fronts, such as machine learning, pattern recognition, data analysis, and so on. Attributes reduction is one of the hot research topics of rough set theory. Much study on this area had been re ported and many useful results were obtained until now [27]. However, most work was based on consistent infor mation systems, and the main methodology has been de veloped under equivalence relations (indiscernibility rela tions). In practice, most of information systems are not only inconsistent, but also based on dominance relations because of various factors. The ordering of properties of attributes plays a crucial role in those systems. For this reason, Greco, Matarazzo, and Slowinski [813] proposed an extension rough sets theory, called the dominancebased rough sets approach (DRSA) to take into account the or dering properties of attributes. This innovation is mainly based on substitution of the indiscernibility relation by a dominance relation. In DRSA, where condition attributes and classes are preference orde red. And many studies have been made in DRSA [1419]. But simpler results of knowl edge reductions are very poor in inconsistent ordered in formation sy stems until now. In this paper, the method operated simply for upper ap proximation reduction is introduced in inconsistent is ob tained, from which we can provide new approach to know ledge reductions in inconsistent systems based on domi nance relations. Finally, an example illustrates the validity of this method, and shows the method is excellent to a complicat ed information system . 2. Rough Sets and OIS The following recalls necessary concepts and prelimi naries required in the sequel of our work. Detailed de scription of the theory can be found in [4,5]. An information system with decisions is an ordered quadruple ,,,UA DFG, where 12 ,,, n Uxx x is a nonempty finite set of ob jects; D is a nonempty finite attributes set; 12 ,,, aa a denotes the set of condition at tributes; 12 ,,, q Ddd d denotes the set of decision attrib utes, and AD ; ,, kk k fUVkpfx is the value of k a on ,k UV is the domain of , kk aa A;
X. Y. ZHANG ET AL. Copyright © 2011 SciRes. IIM 132 ,, kk k GgUVkqgx is the value of k d on ,k UV is the domain of , kk dd D . In an information system, if the domain of a attribute is ordered according to a decreasing or increasing pref erence, then the attribute is a criterion. Definition 2.1 (See [4]) An information system is called an ordered information system (OIS) if all condi tion attributes are criterions. Assumed that the domain of a criterion aA is complete preordered by an outranking relation a , then a y means that is at least as good as y with respect to criterion a. And we can say that domi nates y. In the following, without any loss of generality, we consider condition and decision criterions having a numerical domain, that is, a V ( d enotes the se t of real numbers). We define y by ,, xaf ya according to increasing preference, where aA and, yU . For a subset of attributesBA, B y means that a y for any aB. That is to say dominates y with respect to all attributes in B. Furthermore, we de note B y by B Ry . In general, we indicate a or dered information system s with decision by ,,,UA DFG . Thus the following definition can be obtained. Let ,,,UA DFG be an ordered informa tion system with decisions, for BA, denote , , Bij liljl RxxUUfxfxaB , , Dij mimjm RxxUUgxgxdD . R and R are called dominance relations of in formation system . If we denote [] {(,)} iBjj iB xUxx R {()(), }; jljlil UfxfxaB [] {(,)} iDjj iD xUxx R {()(), }, jmjmim Ug xg xdD then the following properties of a dominance relation are trivial. Proposition 2.1 (See [4]) Let A R be a dominance relation. The following hold. 1) A R is reflexive, transitive, but not symmetric, so it is not a equivalence relation. 2) If BA, then AB RR . 3) If BA, then ii AB x . 4) If ji A x, then ji A A x and iA x  jji A A xxx . 5) ji A A x iff ,, ij xafxaa A . 6)  A xU constitute a covering of U. For any subset of U, and of define ; AA RX xUxX  AA RX xUx X A RX and A Rx are said to be the lower and up per approximation of with respect to a dominance relation A R. And the approximations have also some properties which are similar to those of Pawlak approxi mation spaces. Definition 2.2 (See [4]) For a ordered information system with decisions ,,,UA DFG , if AD RR , then this information system is consistent, otherwise, this information system is inconsistent. For simple description, the following information sys tems with decisions are based on dominance relations, i.e. ordered information systems. Let ,,,UA DFG be an inconsistent or dered information system, and denote ,1,2,, kD DUR kr 12 ((),(),,()) BB BBr RDRD RD the following definition is gave. Definition 2.3 (See [5]) If A , for all BA, we say that B is an upper approximation consistent set of . If B is an upper approx imation consistent set, and no proper subset of B is upper approximation consis tent set, then B is called an upper approximation con sistent reduction of . From the above, we can find that an upper approxima tion consistent set preserves the upper approximation of every decision class. Theorem 2.1 (See [5]) Let = ,,,UA DFG be an information system, BA, then B is an upper approximation consistent set if and only if there exist bB such that bb xfy when Ak RD and Ak yRD for every kD DUR 1, 2,,kr. From the theorem, authors have provided approach to upper approximation reduction in inconsistent ordered systems based on indiscernable matrixes in [5]. We can find that it is not convenient to use the method by com puters. So we will propose the approach to upper ap proximation reduction operated simply by computers.
X. Y. ZHANG ET AL. Copyright © 2011 SciRes. IIM 133 3. Rough Computational Approach to UAR Based on Dominance Matrix 3.1. Dominance Matrices and Upper Approximation Decision Matrices In this section, the dominance matrices and upper ap proximation decision matrices are proposed, and some properties are obtained. Definition 3.1 Let ,,,UA DFG be an or dered information system, and denote , Bij nn Mm where 1, , 0, otherwise. ji ij xx m The matrix is called dominance matrix of attrib utes setBA. If Bl, we say that the order of is l. Definition 3.2 Let ,,,UA DFG be an or dered information system, and dominance matrices , C of attributes sets ,BCA. The intersection of and C is defined by BC ijij nn nn MM mm min ,. ij ij nn mm The following properties are obviously. Proposition 3.1 Let , C be dominance matri ces of attributes sets ,BCA, the following results always hold. 1) 1 ii m. 2) If , C , then CBC MM . Definition 3.3 Let ,,,UA DFG be an or dered information system, and denote , Dij nn Mr where 00 0 0, and hold at same time for some1,2,,. 1, otherwise. iAkjAk ij xRD xRD rkr The matrix is called upper approximation deci sion matrix of . From the above, we can see that the dominance rela tion of objects is decided by dominance matrices, and different decisions of objects is decided by upper ap proximation decision matrix. Definition 3.4 Let 12 ,,, n aa a and 12 ,,, n bb bbe two n dimension vectors. If ,1,2,, ii abi n, we say vector is less than vector , denoted by . Definition 3.5 Let 12 ,,, T An M and B M 12 ,,, , T n be two matrices, i and i be row vectors respectively. If ii , we say A is less than , denoted by AB M. By the definitions, dominance matrices have the fol lowing properties straightly. Proposition 3.2 Let ,,,UA DFG be an ordered information system, and BA. If A and are the dominance matrices, then AB M. 3.2. Theories of Matrix Computation for Upper Approximation Reduction In the following, we will give the theory of matrix com putation for upper approximation reduction in ordered information systems. Theorem 3.1 Let = ,,,UA DFGbe an infor mation system, BA, then B is an upper approxi mation consistent set if and only if D M.Proof “” quad we need prove that if A holds for BA then D M . So we only prove1 ij r , when 1 ij m . In fact, we can have that 1 ijj i mxx ji B x One can obtain that if 0 iAk xRD then 0 jAk xRD for 01, 2,,kr That is to say 0 iAk xRD and 0 iAk xRD don not hold at same time. Hence, we have 1 ij r . “ ” Suppose B be not an upper approximation co nsistent set, then there must exist some 0 k D 0 /, 1,2,, D UR kr such that 0 Ak RD 0 Bk RD . That is to say there 0 iAk RD , but 0 iBk RD. So we have 0 ik A xD and 0 ik B xD . On the other hand, we know that ii AB x . So there exists ji x and 0 k D. Since jj A xx , so 0 jk A xD . Thus 0 jAk xRD. From above, we have 0 iAk RD and 0 Ak RD .
X. Y. ZHANG ET AL. Copyright © 2011 SciRes. IIM 134 That means 0 ij r. Since D M, so we have 0 ij m. However, we have obtained ji x, which is a contradiction with0 ij m. Hence, B is an upper approximation consistent set of if D M. The theorem is proved. Corollary 3.1 Let ,,,UA DFG be an or dered information system, and BA. B is a upper approximation reduction of if and only if D Mand D M does not hold for all proper subset 'Bof B. 3.3. Algorithm of Matrix Computation for Upper Approximation Reduction Let ,,,UA DFG be an ordered information system. We denote the dominance matrix of attributes sets B by 12 ,,, T Bn M , and upper approxi mation decision matrix of by 12 ,,, T Dn M , where , ii is the ith row vectors of and respectively, and T means transposed matrix of ma trix . So we can obtain the following algorithm by Theorem 3.1 and Corollary 3.1. Algorithm Algorithm of matrix computation for upper approximation reduction in inconsistent ordered infor mation systems is described as follows: Input: An inconsistent ordered information sys tem ,,,UA DFG , where 12 ,,, n Uxxx and 12 ,,, aa a. Output: Upper approximation reductions of ,,,UA DFG . Step 1. Simplify the system by combining the objects with same values of every attribute. Step 2. Calculate upper approximation decision matrix of : 12 ,,, T Dn M . Step 3. For all ,1 l aA lp, calculate the first order dominance matrices, (1)(1) (1)(1) {}{}12 ,,, ll T aa n MM . For 1i to n. If (1) 0ii , then let(1) 0 i , Denote the new matrix by (1) {} l a FM , and turn into next step. Step 4. Call matrix (1)(1) (1)(1) {}12 ,,,, l T an FM ,1 l aA lp to be the first order upper ap proximation matrix. If (1) {} 0 l a FM , then obtain an the first order upper approximation reduction: l a. Other wise, turn into next step. Step 5. Calculate the intersection of all the first order nonzero matrix which are obtained in step 3, and call new matrices to be the second order dominance matrices, denoted by (2) {} ls aa M, (2)(1) (2)(1) {}{}{}{} , lsl lss aaa aaa MMMM . Go back to step 3 and calculate all the second order upper approximation reductions. Step 6. Obtain the higher order upper approximation reductions by repeating step 5. If the new matrices are zero matrices, then output all upper approximation re ductions and terminate the algorithm. From the above algorith m, we can know that the com plication of times is 2 2 A OU easily. 3. An Example Example Given an ordered information system in the following Table. From the table, we can compute the dominance matrices and upper approximation decision m atrices, which are 1 {} 111111 010011 111111 010111 010011 010011 a M 2 {} 110011 110011 111111 111111 000010 110011 a M 3 {} 111111 011111 011111 000101 011111 000101 a M {} 111111 111111 111111 000101 111111 000001 Dd MM By comparing matrices 123 {} {}{} ,, aaa MMM and {}d , we can find that vectors of the first, second, third, and 5th row in matrix 1 {}a M and 2 {}a M are less then those in matrix {}d M respectively. So the system has not the first order upper approximation reduction. Thus the first order upper approximation matrices are as follows:
X. Y. ZHANG ET AL. Copyright © 2011 SciRes. IIM 135 Table 1. An ordered information system. U 1 a 2 a 3 a d 1 1 2 1 3 2 3 2 2 2 3 1 1 2 1 4 2 1 3 2 5 3 3 2 3 6 3 2 3 1 1 (1) {} 000000 000000 000000 010111 000000 010011 a FM ; 2 (1) {} 000000 000000 000000 111111 000000 110011 a FM ; 3 (1) {} 000000 000000 000000 000000 000000 000101 a FM Furthermore, the second order upper approximation matrices are 121 2 (2)(1) (1) {,}{} {} 000000 000000 000000 010111 000000 010011 aaa a MFMFM 131 3 (2)(1) (1) {,}{}{} 000000 000000 000000 000000 000000 000001 aaa a MFMFM 232 3 (2)(1) (1) {,}{} {} 000000 000000 000000 000000 000000 000001 aa a a MFMFM So, we can see that 13 23 (2) (2) {} {} aa aa MM, and the 6th row vectors of them are less then those of {}d M respectively, by comparing 12 (2) {} aa M, 13 (2) {} aa M, 23 (2) {} aa M and {}d . Hence, we can obtain all the second order upper ap proximation reductions, which are 13 23 ,,,aaaa. In the next, we have 13 23 (2) (2) {,} {,} 000000 000000 000000 000000 000000 000000 aa aa FM FM So, the algorithm is terminated. Thus, all upper approximation reductions are 13 23 ,,,aaaa in the system of above example, which are consistent with ref.[5]. From the example, we can find that the algorithm is valid, and operated simply, for systems with a great deal of objects and attributes 5. Conclusions It is well known that most of information systems are based on dominance relations because of various factors in practice. Therefore, it is meaningful to study the knowledge reductions in inconsistent ordered informa tion system. In this article, the dominance matrix and upper approximation decision matrix are introduced in information systems based on dominance relations. Fur thermore, the algorithm of upper approximation reduc tion is obtained, from which we can provide new ap proach to knowledge reductions in inconsistent systems based on dominance relations. Finally, an example illus trates the validity of this method, and shows the method is applicable to a complicated information system. 6. References [1] Z. Pawlak, “Rough Sets,” International Journal of Computer and Information Science, Vol. 11 , N o. 5, 1982, pp. 341356. HH0UUdoi:10.1007/BF01001956U [2] Y. Leuang, W. Z. Wu and W. X. Zhang, “Knowledge Ac quisition in Incomplete Information Systems: A Rough Set Approach,” European Journal of Operational Re
X. Y. ZHANG ET AL. Copyright © 2011 SciRes. IIM 136 search, Vol. 168, No. 1, 2006, pp. 164180. HH1UUdoi:10.1016/j.ejor.2004.03.032U [3] W. H. Xu and W. X. Zhang, “Measuring Roughness of Generalized Rough Sets Induced by a Covering,” Fuzzy Sets and Systems, Vol. 158, No. 22, 2007, pp. 24432455. HH2UUdoi:10.1016/j.fss.2007.03.018U [4] W. X. Zhang, W. Z. Wu, J. Y. Liang and D. Y. Li, “Theory and Method of Rough Sets,” Science Press, Beijing, 2001. [5] W. H. Xu, X. Y. Zhang and W. X. Zhang, “Upper Ap proximation Reduction in Inconsistent Information Sys tems Based on Dominance Relations,” Computer Engi neering, Vol. 35, No. 18, 2009, pp. 191193. [6] W. H. Xu, X. Y. Zhang and W. X. Zhang, “Knowledge Granulation, Knowledge Entropy and Knowledge Uncer tainty Measure in Information Systems,” Applied Soft Computing, Vol. 9, No. 4, 2009, pp. 12441251. HH3UUdoi:10.1016/j.asoc.2009.03.007U [7] W. H. Xu, X. Y. Zhang, J. M. Zhong and W. X. Zhang, “Attribute Reduction in Ordered Information Systems Based on Evidence Theory,” Knowledge and Information Systems, Vol. 25, No. 1, 2010, pp. 169184. HH4UUdoi:10.1007/s1011500902485U [8] W. H. Xu and W. X. Zhang, “Knowledge Reduction and Matrix Computation in Inconsistent Ordered Information Systems,” International Journal Business Intelligence and Data Mining, Vol. 3, No. 4, 2008, pp. 409425. HH5UUdoi:10.1504/IJBIDM.2008.022737U [9] W. H. Xu, M. W. Shao and W. X. Zhang, “Knowledge Reduction Based on Evidence Reasoning Theory in Or dered Information Systems,” Lecture Notes in Artificial Intelligence, Vol. 4092, 2006, pp. 535547. [10] W. H. Xu and W. X. Zhang, “Methods for Knowledge Reduction in Inconsistent Ordered Information Systems,” Journal of Applied Mathematics & Computing, Vol. 26, No. 12, 2008, pp. 313323. [11] W. Z. Wu, M. Zhang, H. Z. Li and J. S. Mi, “Attribute Reduction in Random Information Systems Via Demp sterShafer Theory of Evidence,” Information Sciences, Vol. 174, No. 34, 2005, pp. 143164. HH6UUdoi:10.1016/j.ins.2004.09.002U [12] M. Zhang, L. D. Xu, W. X Zhang and H. Z. Li, “A Rough Set Approach to Knowledge Reduction Based on Inclu sion Degree and Evidence Reasoning Theory,” Expert Systems, Vol. 20, No. 5, 2003, pp. 298304. HH7UUdoi:10.1111/14680394.00254U [13] S. Greco, B. Matarazzo and R. Slowingski, “Rough Ap proximation of a Preference Relatioin by Bominance Re latioin,” European Journal of Operational Research, Vol. 117, No. 1, 1999, pp. 6383. HH8UUdoi:10.1016/S03772217(98)001271U [14] S. Greco, B. Matarazzo and R. Slowingski, “A New Rough Set Approach to Multicriteria and Multiattribute Classificatioin. In: Rough Sets and Current Trends in Computing (RSCTC'98),” SpringerVerlag, Berlin, 1998. pp. 6067. [15] S. Greco, B. Matarazzo and R. Slowingski, “Rough Sets Theory for Multicriteria Decision Analysis,” European Journal of Operational Research, Vol. 129, No. 1, 2001, pp. 1147. HH9UUdoi:10.1016/S03772217(00)001673U [16] S. Greco, B. Matarazzo, R. Slowingski, “Rough Sets Methodology for Sorting Problems in Presence of Mul tiple Attributes and Criteria,” European Journal of Op erational Research, Vol. 138, No. 2, 2002, pp. 247259. HH1UUdoi:10.1016/S03772217(01)002442U [17] K. Dembczynski, R. Pindur and R. Susmaga, “Genera tion of Exhaustive Set of Rules within Dominance Based Rough Set Approach,” Electronic Notes Theory Compute Sciences, Vol. 82, No. 4, 2003. [18] Y. Sai, Y. Y. Yao and N. Zhong, “Data Analysis and Mining in Ordered Information Tables,” IEEE Com puter Society Press, San Jose, 2001, pp. 497504. [19] M. W. Shao and W. X. Zhang, “Dominance Relation and Rules in an Incomplete Ordered Information System,” International Journal of Intelligent Systems, Vol. 20, No. 2005, pp. 1327. HH1UUdoi:10.1016/S03772217(01)002442UHHH
