Applied Mathematics, 2011, 2, 918921 doi:10.4236/am.2011.27125 Published Online July 2011 (http://www.SciRP.org/journal/am) Copyright © 2011 SciRes. AM Lower Approximation Reduction in Ordered Information System with Fuzzy Decision Xiaoyan Zhang, Weihua Xu School of Mathematics and Statistics, Chongqing University of Technology, Chongqing, China Email: zhangxyms@gmail.com , chxuwh@gmail.com Received March 28 , 20 1 1; Revised June 5, 2011; accepted J un e 8, 2011 Abstract Attribute reduction is one of the most important problems in rough set theory. This paper introduces the concept of lower approximation reduction in ordered information systems with fuzzy decision. Moreover, the judgment theorem and discernable matrix are obtained, in which case an approach to attribute reduction in ordered information system with fuzzy decision is constructed. As an application of lower approximation reduction, some examples are applied to examine the validity of works obtained in our works. Keywords: Fuzzy Decision, Lower Approximation Reduction, Ordered Information Systems, Rough Set 1. Introduction Rough set theory, proposed by Pawlak Z. in the early 1980s [1], is an extension of classical set theory and can be regarded as a soft computing tool to deal with uncer tainty or imprecision information. It was well known that this theory is based upon the classification mechanism, from which the classification can be viewed as an equivalence relation and knowledge blocks induced by it be a partition on universe. For this reason, it has been applied widely and successfully in pattern recognition [2], medical diagnosis [3], granular computing [4] and so on. Attributes reduction, as one important portion of rough set researching, its main idea is not only to delete re dundant attributes but also to pr eserve th e invariability o f classification ability. In fact, for the reason of noise or information losing, there have many information systems that the relation is not equivalence relation. Therefore, how to deal with this type of information systems has be came a very hot topic in rough set theory. Meantime, many experts have studied attribute reduction by extend ing the equivalence relation to consistent relation, similar relation, dominance relation [57] and so on. Also, some useful works, take dominance relation based information systems, [814] for example, have been done in detail. At the same time, for decision makers, there may exist one case that the decision objects are not certain or precision but fuzzy. So the fuzzy decision must be taken into consideration. Our work in this paper is to consider the attribute reduction in ordered information systems with fuzzy decision. Firstly, concept of lower approxi mation consistent set is proposed by comparing decision attribute values. What is more, lower approximation re duction and judgment theo rem is introduced, from which one can define the discernable matrix and find that it is an useful approach to attribute reduction in ordered in formation system with fuzzy decision. As an applica tion of lower approximation reduction, examples are considered to illustrate the validity of some results ob tained in our works. The rest of this paper is organized as follows. Some preliminary concepts required in our work are briefly recalled in Section 2. In Section 3 the lower approxi mation reduction in ordered information system with fuzzy decision is investigated. The discernable matrix and approach to attribute reduction are defined in Section 4. Section 5 concludes this paper. 2. Information System with Fuzzy Decision In this section, we shall begin our work with some nec essary concepts required. For more detailed description of the theory, please refer to references [15,16]. Definition 2.1. An information system is a quaternion (, ,,) UA DFG , where 12 ,,, n Uuu u is nonempty finite set of objects; 12 ,,, aa a is nonempty finite set of condi tional attributes; {}Dd is set of decision attribute. , kk fUVk p is relation set ofand U ,
X. Y. ZHANG ET AL.919 and ikk i VfuuU is the domain of k aA . Table 1. An ordered IS with fuzzy decision. Attributes d dUV is th, and Ge relation set of d U anD U is the domain of dD. Inith fuzzy decisio d dii Vuu formation system w that the de n is cision value of objects is expressed as fuzzy form, i.e., for any i uU, 0, 1 i du . Defin2.ition 2. Let ,,, UADFG A, if denote be an infor mation system and B ,,Ruu fuf kBij kij UUu B , then k a R to means a dominance relation on re U with io spect B, in which case the informatn system ,,, UA FG is called an ordered information y D systnoted bem and de . If an information system is based on domrela tio inance n and the decision value of objects is fuzzy, then the information system is called ordered information system with fuzzy decision. For convenience, the notation is used to express ordered information systems w fuzzy decision, from which the dominance class of any i uU is denoted as ith , ij uuuuR . i B Pro t jB position 2.1. Le be an informm an ation syste dBA. 1) R is reflexive, transitive, but noric, so it is th. t symmet B . 21 i B . stem not an equivalence relation. 2) If 12 BBA, thenA R 21 B R R uu 3) If , then u 12 BBA ii AB 4) If en uu ji A uu, ition 2.3. iA A j n information syDefin For a re, the lower and lower approximation sets of D withspect to , which are fuzzy sets, are denoteby d and respectively. And their membership functs are ned by , defi ion min Dij ji A Auduu u , . ation sy max Dij ji A Auduu u Example 2.1. Consider an ordered informstem wi and th fuzzy dec ision in Table 1. By comput i ng we hav e that 0.5, du du 12 34 56 0.3, 0.7, 0.9, 0.1, 0.6, du du du du 256 46 6 , ,, , , . uuu uu u 1 12562 3 234564 55 6 ,,,, ,,,,, , AA A A AA u uuuuu uuuuuuu uu u U 1 a 2 a 3 a d 1 u 1 2 1 0.5 2 u 3 2 2 0.3 1 1 0.7 2 1 3 0.9 3 u 2 4 u 5 u 3 3 2 0.1 6 u 3 2 3 0.6 So we have tht a 1 u2 4 6 23456 .1.60 0.6 , 0.6 0.6 0.9 0.9 0.10.6. D Au uu uuuuu 3. Lower Approximation Reduction of Ordered Information System with Fuzzy Decision n, a tio wiision. Therefore, the lower approximation consistent set is constructed and lower approximation 3 u5 u 1 D Au 0.10 0.10.1 Since dominance relation is not the equivalence relatio the approach to attribute reduction in original inform n systems is not fitted for ordered information system th fuzzy dec reduction is defined, from which the judgment theorem is introduced. Definition 3.1. Let be an information system and BA. If iDi uBu for any i uU, then B is called lower approximation consistent set of this in formation system. Moreover, if any proper subset of B is not a lower approximation consistenen on n system t set, thB is e lower approximatio reduction of this information . Example 3.1. (Continued from Example 2.1) If take 23 ,Baa, we will have that ii AB uu holds for any i uU . Hence iDi uBu , that is, 23 ,aa is one lower approximation consistent set of this infor mation system. Moreover, if take 13 ,Caa, by com inputg we ha ve 1 6 2256 , ,, , ,,,, C C u u uuuu uuuuu 12 5 3 23456 446 5256 66 34 ,,,, , ,, ,, , , , C C C C uuuuu u uuu uuuu uu Copyright © 2011 SciRes. AM
X. Y. ZHANG ET AL. 920 and 123456 0.10.10.1 0.60.1 0.6. D CA uuuuuu Hence, 31,aa set. Mois also another lower approximation consistentreover, we can obtain that 3 a concl n redu is lower appron consistent sets. Hence weude that d only lower approximatioc tion ation system. the next, the judgment theorem in ordered informa tion system with fuzzy decision is proposed. Theorem 3.1. Let oximati is one an is inform 3 a of th In wer be an information syst and . is a loapproximation consistent set if em BA an B d only if for every i u, j uU , if iDj uAu , then there exist k aB such that kki ufu Proof: “: Suppose that . ” kki ufu for every k aB when() () iDj uAu . So we can obtain ij uu , that is, ij B uu . By min Di i Buduu u and min Dj j Buduuu , we ht ave tha jD Bu B Since er approximaonsistent set, we have th i u. B at is lowtion c jDj u dBu an iDi uBu . So we can obtain jDi uAu . It is a contction. ”: Supposeis not lower approximation con et, then thust exist one such that radi “ sisten B ere mt s0 i uU Di 00 Di uBu . According have to Proposition 2.1, we that Di uu k00 00 Di BA If we tae j i uu such that 000 jiDi B duuB u . min duu We have known that 00 min A jj du uduu . From above, we have that because of00 jA j uu 00 Di D u Au , thus there exist such that j k aB 00 kki ufcontradiction u . It is a with 00 j i uu . The theorem is proved. 4. Approach to Lower Approximation on In theorem 3.1, we proposed an equivalent description of lower approximatch it can be used to estimate whether the attribute set is an lower ap proximation consistent set or not. In next, discernable mnd reduction approach is con structed im Reducti ion consistent set, from whi atrix is introduced first a mediately. Definition 4.1. Let be an information system and iDj D uAu . If denote , fijD uuA , ,, kijijf fij ij kk auuuuD Duu uu D Af f , then D is called the lower approximation discernable attribute set between i u and u, and ,MDuu , ij ffij uu U is the discernable matrix of this information system. Theorem 4.1. Let is lower approxim be an information system and ation consistent set if an only if BA, B d , fij BDuu for all of m 3.1 wehere exist , ij f uu D. Pro : “”: By theore have that t k aB s.t. kki ufu for, then , ij f uu D u, hence BD,u kf aDij fij ,uu . “ ”: For , ij f uuD , if , fij BDuu , erexist k aB thee n th s.t. , k aDuu, that is fij kki um 3.1 wB fu lowe r a . By Theoree have that is a pproximation consistent set of . Ttheorem is proved. ition 4ormat he Defin .2. For an infion system and er approle f BA, the lowximation discernaboula is denoted as rm ,, ,,, fkf i kkfi jijf aa D uuuuD Theorem 4.2. Let , . kj ij FaaD uuuuU be an information system and th normal form is defined as e minimum alternative 1 pk f B . If take ,1,2,, k k E sk Basq then ,,p the lower approxim ,1,2 k f Bkis the set with all its elements have ation reduction form. Proof: For any , ij f uu D normal form , by the definitin of minimum alternative and theorem 4.1, we have that o k B is consistent set. If on lower approximation e element of k B in 1 pk f k B is deleted and k B becomes then the re must exis t ` k f B,from which Copyright © 2011 SciRes. AM
X. Y. ZHANG ET AL. Copyright © 2011 SciRes. AM 921 Table 2. Discernable matrix of the IS in example 2.1. Objects U 1 u 2 u 3 u 4 u 5 u 6 u 1 u 13 aa 13 aa 2 u 3 a 3 a 3 u 123 aaa 13 aa 4 u 5 3 a 3 a u 6 u such that 00 , ijf uu D , k ffij BDuu 00 . So is not a lower approximation consistent set. ` k f B Hen eck B r approxiation reduction. Sinceis a lowem includes all , ij Duu redutions , there don’t exist other atit at have different forms. Eple 4.1. (Continued fro Example 2.1 and ample 3.1)y comutinghave Table . Hence, a, that to say, ation eduction sion ac quired in this consistent with the resul Examp . systems are based on dominance rel f va ation consistent set is constructed and te reduction in ordered information on is proposed. Moreover, the lower approximon ch m xam Ex Bp we 2 3 1233faa a aaa 3 {}a is the one and only lower approxim from which we have that the conclu 1 3 E is r, Example is ts in le 3.1. 5Conclusions Attribute reduction, as one hot research topic, has played an important role in rough set theory. However, most of informationations because orious factors. To acquire brief decision rules from inconsistent ordered information systems with fuzzy decision, attribute reductions are needed. The main aim of this paper is to study the problem. In this paper, the lower approxim approach to attribu system with fuzzy decisi judgment theorem of lower approximation consistent set is obtained and some useful works are done in detail. 6. References [1] Z. Pawlak, “Rough Set,” International Journal of Com puter and Information Sciences, 1982, Vol. 11, No. 5, pp. 341356. doi:10.1007/BF01001956 [2] R. W. Swiniarski and A. Showron, “Rough Set Method in Feature Selection and Recognition,” Pattern Recognition letter, Vol. 24, No. 6, 2003, pp. 833849. doi:10.1016/S01678655(02)001964 [3] H. L. Li and M. H. Chen “Induction of Multiple Criteria Optimal Classification Rules for Biological and Medical ters in Biology and Medicine, Vol. 38, No. 1, 2008, 4245. doi:10.1016/j.compbiomed.2007.07.006 Data,” Compu 26. Research, Vol. [4] G. Y. Wang, Q. H. Zhang and J. Hu, “An Overview of Granular Computing,” CAA I Transactions on Intelligent Systems, Vol. 26, No. 2, 2007, pp. 8 [5] S. Greco, B. Matarazzo and R. Slowinski, “Rough Ap proximation of a Preference Relation by Dominance Re lation,” European Journal of Operation 117, 1999, pp. 6383. doi:10.1016/S03772217(98)001271 [6] S. Greco, B. Matarazzo and R. Slowinski, “Rough Sets Theory for Multicriteria Decision Analysis,” European Journal of Operational Research, Vol. 129, No. 1, 2001, pp. 147. doi:10.1016/S03772217(00)001673 [7] K. Dembczynski, R. Pindur and R. Susmaga, “DominanceBased Rough Set Classifier without Induc tion of Decision Rules,” Electronic Notes in Theoretical Computer Science, Vol. 82, No. 4, 2003, pp. 8495. doi:10.1016/S15710661(04)807084 [8] W. H. Xu, X. Y. Zhan proximation Reduction in Inconsis g and W. X. Zhang, “Lower Ap tent Informations formation ystems,” omputing, Vol. 26, ation Based on Dominance Relations,” Computer Engineering and Applications, Vol. 45, No. 16, 2009, pp. 6668. [9] W. H. Xu, X. Y. Zhang and W. X. Zhang, “Lower Ap proximation Reduction in Inconsistent Target In System Based on Dominance Relations,” Computer En gineering, Vol. 35, No. 18, 2009, pp. 191193. [10] W. H. Xu and W. X. Zhang, “Methods for Knowledge Reduction in Inconsistent Ordered Information S Journal of Applied Mathematics & c No. 1, 2008, pp. 313323. [11] 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 Inform Systems, Vol. 25, No. 1, 2010, pp. 169184. doi:10.1007/s1011500902485 [12] W. H. Xu, X. Y. Zhang and W. X. Zhang, “Knowledge Granulation, Knowledge Entropy and Knowledge Uncer y a Covering,” Fuzzy tainty Measurein Ordered Information Systems,” Applied Soft Computing, Vol. 9, 2009, pp. 12441251. [13] W. H. Xu and W. X. Zhang, “Measuring Roughness of Generalized Rough Sets Induced B Sets and Systems, Vol. 158, No. 22, 2007, pp. 24432455. doi:10.1016/j.fss.2007.03.018 [14] W. H. Xu, M. W. Shao and W. X. Zhang, “Knowledge Reduction Based on Evidence Reasoning Th dered Information Systems,” Lec eory in Or ture Notes in Artificial Intelligence, Vol. 4092, 2006, pp. 535547. doi:10.1007/11811220_45 [15] W. X. Zhang, W. Z. Wu, J. Y. Liang, et al., “Theory and Method of Rough Sets,” Science Press, Beijing, 2001. [16] W. X. Zhang, Y. Leung and W. Z. Wu, “Information System and Knowledge Discovery,” Science Press, Bei jing, 2003.
