第6期 裴小兵，等：最小化决策规则集的计算方法 *67· 最小化决策规则集 在命题2的基础上，借鉴文献[6-8的思想，易 参考文献： 于证明命题3 [1]PAWLAK Z.Rough sets [J ]International Journal of 命题3直观上提供了最小化决策规则集的计算 Computer and Information Science,1982,11 (5):341 方法 356. 类似于基于可辨识矩阵的属性约简算法P.3.61 [2]刘清.Rough集及Rough推理[M].北京：科学出版 社，2001. 下面根据上述结果提供基于可辨识矩阵的基本决策 [3]张文修，吴伟志，梁吉业，等.粗糙集理论与方法[M],北 规则集的最小化决策规则集的计算方法 京：科学出版社，2001， 算法1最小化决策规则集的计算方法 [4]KR YSZKIEWICZ M.Rules in incomplete information 输入：决策表系统S=<U,A,V,f>,具有相 systems[J ]Information Sciences,1999,113 271 -292. 同后件中的基本决策规则集AS。=/→中，攻→中， [5]MOLL ESTAD T,SKOWRON A.A rough set frame- …虫→g; work for data mining of propositional default rules[A]. 输出：AS的全体最小化决策规则集 Foundations of Intelligent Systems of the 9th Interna- 方法步骤为 tional Symposium[C].Zakopane,Poland,1996. 1)计算决策规则集AS。的最小化决策规则集 [6]SKOWRON,RAUSZER C.Intelligent decision support 可辨识矩阵[Cg: handbook of application and advances of the rough sets 2)计算最小化决策规则集可辨识矩阵[C,J的 theory[M].Dordreecht:Kluwer Academic Publishers, 1992. 可辨识公式M: [7]MIJ S,WU W Z,ZHANG W X.Approaches to knowl- 3)计算可辨识公式M的极小析取范式M,它将 edge reduction based on variable precision rough set 给出全体最小化决策规则集。 model[J ]Information Sciences,2004,159:255-272. 实例1以表1的决策表为实例，其中条件属 [8]张文修，米据生，吴伟志.不协调决策表信息系统的知识 性集C={a,b,cg,决策属性集D={d,对象集U= 约简[U].计算机学报，2003,26(1)：12.18. /#1,#2,#3,#4,#5} ZHANG Wenxiu,MI Jusheng,WU Weizhi.Knowledge 在表1中求得决策类1（相同后件(d,1))的所 reductions in inconsistent information systems [J ]Chi- 有基本规则的集合为AS0=(c,2)→(d,1),(a,2) nese Journal of Computers,2003,26(1):12-18. 作者简介： (b,0→d,1),(b,2)→(d,1),(c,1)→(d,1)},其 裴小兵，男，1972年生，博士，主要 对应的最小化决策规则可辨识矩阵[C]为C1= 研究方向为数据挖掘、数据库、软件工 G2=C3=C2=C23=C3=Φ：C21=f(a,2)(b,0)}: 程 G1={(c,2∧c,1),(c,2)∧b,2),a,2)(b,0 Email:xiaobingp @tom.com (b,2,a,2)(b,0)Ac,1)};C2={(a,2)b,0A (b,2,(a,2)(b,0Λc,1)3. 可辨识矩阵[C,的可辨识公式M的极小析取 范式为 吴涛，男，1972年生副教授，主 M=f(a,2)(b,0y八b,2}V{(a,2)(b,0)∧ 要研究方向为软件工程. (c,l)}. E mail:wutaooptal @tom.com. 因此，基本规则的集AS有2个最小化决策规 则集： 1)(a,2)(b,0八b,2td,1)； 2(a,2)(b,0c,)→(d,1). 陆永忠，男，1969年生，副教授，主 3结束语 要研究方向为机器学习软件工程. E mail hotmailuser @126.com. 介绍了一种直观、易理解的最小化决策规则集的 计算方法，该方法基于构造最小化决策规则集的可辨 识矩阵来获得最小化决策规则集.如何提高计算最小 化决策规则集的效率将是下一步的研究任务 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net最小化决策规则集. 在命题 2 的基础上 ,借鉴文献[6 - 8 ]的思想 ,易 于证明命题 3. 命题 3 直观上提供了最小化决策规则集的计算 方法. 类似于基于可辨识矩阵的属性约简算法[2 - 3 ,6 ] , 下面根据上述结果提供基于可辨识矩阵的基本决策 规则集的最小化决策规则集的计算方法. 算法 1 最小化决策规则集的计算方法 输入 :决策表系统 S = < U , A , V , f > ,具有相 同后件φ的基本决策规则集 A Sφ = { <1 →φ, <2 →φ, …, <n →φ} ; 输出 :A Sφ 的全体最小化决策规则集. 方法步骤为 1) 计算决策规则集 A Sφ 的最小化决策规则集 可辨识矩阵[ Cij ]; 2) 计算最小化决策规则集可辨识矩阵[ Ci , j ]的 可辨识公式 M ; 3) 计算可辨识公式 M 的极小析取范式 M ,它将 给出全体最小化决策规则集. 实例 1 以表 1 的决策表为实例 ,其中条件属 性集 C = { a , b, c} ,决策属性集 D = { d} ,对象集 U = { # 1 , # 2 , # 3 , # 4 , # 5} . 在表 1 中求得决策类 1 (相同后件 ( d , 1) ) 的所 有基本规则的集合为 A Sφ = { ( c , 2) →( d ,1) , ( a , 2) ( b,0) →( d ,1) , ( b, 2) →( d , 1) , ( c , 1) →( d , 1) } ,其 对应的最小化决策规则可辨识矩阵[ Cij ]为 C11 = C12 = C13 = C22 = C23 = C33 =Φ; C21 = { ( a , 2) ( b, 0) } ; C31 = { ( c ,2) ∧( c ,1) , ( c , 2) ∧( b,2) , ( a , 2) ( b, 0) ∧ ( b,2) , ( a ,2) ( b, 0) ∧( c , 1) } ; C32 = { ( a , 2) ( b, 0) ∧ ( b,2) , ( a ,2) ( b,0) ∧( c ,1) } . 可辨识矩阵[ Cij ]的可辨识公式 M 的极小析取 范式为 M = { ( a ,2) ( b, 0) ∧( b, 2) } ∨{ ( a , 2) ( b, 0) ∧ ( c ,1) } . 因此 ,基本规则的集 A Sφ 有 2 个最小化决策规 则集 : 1) ( a,2) ( b,0) ∧( b,2) →( d ,1) ; 2) ( a,2) ( b,0) ∧( c ,1) →( d ,1) . 3 结束语 介绍了一种直观、易理解的最小化决策规则集的 计算方法 ,该方法基于构造最小化决策规则集的可辨 识矩阵来获得最小化决策规则集. 如何提高计算最小 化决策规则集的效率将是下一步的研究任务. 参考文献 : [1 ] PAWLA K Z. Rough sets[J ]. International Journal of Computer and Information Science , 1982 , 11 ( 5) : 341 - 356. [2 ]刘 清. Rough 集及 Rough 推理[ M ]. 北京 :科学出版 社 ,2001. [3 ]张文修 ,吴伟志 ,梁吉业 ,等. 粗糙集理论与方法[ M ]. 北 京 :科学出版社 ,2001. [ 4 ] KR YSZKIEWICZ M. Rules in incomplete information systems[J ]. Information Sciences ,1999 ,113 :271 - 292. [5 ] MOLL ESTAD T , SKOWRON A. A rough set frame2 work for data mining of propositional default rules[ A ]. Foundations of Intelligent Systems of the 9th Interna2 tional Symposium[C]. Zakopane ,Poland ,1996. [6 ] SKOWRON , RAUSZER C. Intelligent decision support handbook of application and advances of the rough sets theory[ M ]. Dordreecht : Kluwer Academic Publishers , 1992. [7 ]MI J S , WU W Z , ZHAN G W X. Approaches to knowl2 edge reduction based on variable precision rough set model[J ]. Information Sciences , 2004 ,159 : 255 - 272. [8 ]张文修 ,米据生 ,吴伟志. 不协调决策表信息系统的知识 约简[J ]. 计算机学报 , 2003 , 26 (1) : 12 - 18. ZHAN G Wenxiu ,MI J usheng , WU Weizhi. Knowledge reductions in inconsistent information systems [J ]. Chi2 nese Journal of Computers , 2003 ,26 (1) : 12 - 18. 作者简介 : 裴小兵 ,男 ,1972 年生 ,博士 ,主要 研究方向为数据挖掘、数据库、软件工 程. E2mail : xiaobingp @tom. com. 吴 涛 ,男 ,1972 年生 ,副教授 ,主 要研究方向为软件工程. E2mail : wutaooptal @tom. com. 陆永忠 ,男 ,1969 年生 ,副教授 ,主 要研究方向为机器学习、软件工程. E2mail : hotmailuser @126. com. 第 6 期 裴小兵 ,等 :最小化决策规则集的计算方法 · 76 ·