第2卷第6期 智能系统学报 Vol.2 N26 2007年12月 CAAI Transactions on Intelligent Systems Dec.2007 最小化决策规则集的计算方法 裴小兵，吴涛陆永忠 (华中科技大学软件学院，湖北武汉430074) 摘要：在决策算法中，并不是所有的决策规则都是必要的，一些过剩的决策规则应该消去，而不影响作决策，因此， 研究最小化决策规则集的计算方法是很有意义的.传统的决策算法并没有给出最小化决策规则集的形式化计算方 法，为了解决最小化决策规则集的形式化计算问题，引入了最小化决策规则可辨识矩阵概念，提供了基于可辨识矩 阵的基本决策规则的最小化决策规则集的计算方法 关键词：粗糙集；决策表；最小化决策规则集 中图分类号：TP311文献标识码：A文章编号：1673-4785(2007)06006503 Calculating method for a minimal set of decision rules PEI Xiao-bing,WU Tao,LU Yong-zhong (School of Software Engineering,Huazhong University of Science Technology,Wuhan 430074,China) Abstract Not all decision rules in existing decisionmaking algorithms are necessary.Irrelevant and super- fluous decision rules should be eliminated as they do not affect decisiommaking,yet increase computational overhead as well as complexity,which can lead to errors.Therefore,research on a method for calculating a minimal set of decision rules is very important.But the algorithms currently available for decision rules don't present a formalized method for calculating a minimal set of decision rules.To solve this problem,in this paper,a new concept of a discernable matrix for minimal decision rules is introduced,and a theorem for judging a minimal set of decision rules is given.On this basis,we proposed a formalized calculation method for a minimal decision rules set based on a discernable matrix.To illustrate this method,an exam- ple is presented. Key words rough set;decisiom making table;minimal decision rules set 粗糙集理论山是20世纪80年代由波兰的 策规则，影响了决策时的效率，文献[23]中强调了 Pawlak教授提出，它是一种新型的处理模糊性和不 最小化决策规则集的意义及重要性，但没有给出最 确定性知识的数学工具，在数据挖掘、决策支持系统 小化决策规则的形式化计算方法，为了解决最小化 等领域得到了应用2.) 决策规则集的计算问题，引入了最小化决策规则集 决策规则获取是粗糙集理论和应用的关键问题 可辨识矩阵概念，从而提供了基于可辨识矩阵的基 之一，在决策算法中，并不是所有的决策规则都是必 本决策规则的最小化决策规则集的计算方法，该方 要的，或者说，具有相同决策类相结合的一些过剩的 法直观、易理解 决策规则应该消去，因此，研究最小化决策规则集的 1 计算方法是很有意义的.计算最小化决策规则集（决 最小化决策规则集的基本概念 策算法的极小化)是决策规则获取算法的重要组成 定义1一个决策表系统S可以表示为：S= 部分2引.目前，许多学者对决策规则的获取作了深 ,其中，U为对象的集合，即论域：A 入研究，并取得了很好成果4)，但是这些研究都没 是属性集合，A=CUD,C和D分别是条件属性集 有给出最小化决策规则集，这样就产生了过多的决 和决策属性集，D地，V=Vr。,V.表示属性a的 值域；f:UX4Ψ是一信息函数，它指的U中每一 收稿日期：20061012。 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 2 卷第 6 期 智 能 系 统 学 报 Vol. 2 №. 6 2007 年 12 月 CAAI Transactions on Intelligent Systems Dec. 2007 最小化决策规则集的计算方法 裴小兵 ,吴 涛 ,陆永忠 (华中科技大学 软件学院 ,湖北 武汉 430074) 摘 要 :在决策算法中 ,并不是所有的决策规则都是必要的 ,一些过剩的决策规则应该消去 ,而不影响作决策 ,因此 , 研究最小化决策规则集的计算方法是很有意义的. 传统的决策算法并没有给出最小化决策规则集的形式化计算方 法 ,为了解决最小化决策规则集的形式化计算问题 ,引入了最小化决策规则可辨识矩阵概念 ,提供了基于可辨识矩 阵的基本决策规则的最小化决策规则集的计算方法. 关键词 :粗糙集 ;决策表 ;最小化决策规则集 中图分类号 : TP311 文献标识码 :A 文章编号 :167324785 (2007) 0620065203 Calculating method for a minimal set of decision rules PEI Xiao2bing , WU Tao , L U Yong2zhong (School of Software Engineering , Huazhong University of Science & Technology ,Wuhan 430074 ,China) Abstract :Not all decision rules in existing decision2making algorit hms are necessary. Irrelevant and super2 fluous decision rules should be eliminated as t hey do not affect decision2making , yet increase comp utational overhead as well as complexity , which can lead to errors. Therefore , research on a met hod for calculating a minimal set of decision rules is very important. But t he algorit hms currently available for decision rules don’t present a formalized method for calculating a minimal set of decision rules. To solve t his problem , in t his paper , a new concept of a discernable matrix for minimal decision rules is introduced , and a t heorem for judging a minimal set of decision rules is given. On t his basis , we proposed a formalized calculation met hod for a minimal decision rules set based on a discernable matrix. To illustrate t his met hod , an exam2 ple is presented. Keywords :rough set ; decision2making table ; minimal decision rules set 收稿日期 :2006210212. 粗糙集理论[1 ] 是 20 世纪 80 年代由波兰的 Pawlak 教授提出 ,它是一种新型的处理模糊性和不 确定性知识的数学工具 ,在数据挖掘、决策支持系统 等领域得到了应用[2 - 3 ] . 决策规则获取是粗糙集理论和应用的关键问题 之一 ,在决策算法中 ,并不是所有的决策规则都是必 要的 ,或者说 ,具有相同决策类相结合的一些过剩的 决策规则应该消去 ,因此 ,研究最小化决策规则集的 计算方法是很有意义的. 计算最小化决策规则集(决 策算法的极小化) 是决策规则获取算法的重要组成 部分[ 2 - 3 ] . 目前 ,许多学者对决策规则的获取作了深 入研究 ,并取得了很好成果[4 - 5 ] ,但是这些研究都没 有给出最小化决策规则集 ,这样就产生了过多的决 策规则 ,影响了决策时的效率 ,文献[2 - 3 ]中强调了 最小化决策规则集的意义及重要性 ,但没有给出最 小化决策规则的形式化计算方法 ,为了解决最小化 决策规则集的计算问题 ,引入了最小化决策规则集 可辨识矩阵概念 ,从而提供了基于可辨识矩阵的基 本决策规则的最小化决策规则集的计算方法 ,该方 法直观、易理解. 1 最小化决策规则集的基本概念 定义 1 一个决策表系统 S 可以表示为 : S = ,其中 , U 为对象的集合 ,即论域; A 是属性集合 , A = C ∪D , C 和 D 分别是条件属性集 和决策属性集 , D ≠Φ,V = V ∪a ∈A V a ,V a 表示属性 a 的 值域; f :U ×A →V 是一信息函数 ,它指的 U 中每一
·66· 智能系统学报 第2卷 个对象x的属性值，即x∈U,a∈A,有f(x,ad∈ 识矩阵的定义得到.根据性质)，计算最小化决策 Va. 规则可辨识矩阵时，只需计算矩阵的下三角矩阵即 对于任意B∈A,记：ind(B)={(x,以：f(x,a)= 可 f(y,ad,廿au∈A},则ind(B)是U上的等价关系， 实例1考虑如表1的决策表，条件属性集C= 称为由B决定的不可区分关系，它们产生的U上的 a,b,c,决策属性集D=/d,U={#1,#2,#3, 划分为：U/ind(B)=[x]s:x∈U},其中：[x]a= #4,#5 fy:(x,以Gnd(B)}是x关于B的等价类P. 表1决策表 定义2设决策表系统S=,AS Table 1 Decision table 是S上的一个基本算法，AS中有相同后件中的所 C a b c 有基本规则的集合被表示为AS·,并且用AP表示 #1 1 0 2 1 属于AS·的决策规则的所有前件的集合.如果= #2 2 0 3 1 sVAP一V(AP-),则在AS中的基本规则 #3 1 1 中→是可约去的，其中VAP表示AP中所有公式 #4 3 的析取，否则这条规则在AS中是不能被约去的： #5 0 0 如果AS中所有决策规则都是不能被约去的，则规 则集合AS被称为独立的：如果AS6中所有决策规 在表1中求得决策类1（相同后件(d,1)的所 则集都是独立的，并且=s VA P&-P,则称决策 有基本决策规则的集合为AS={(c,2)→(d,1), 规则集AS的子集AS。是AS0的一个约简，AS (a,2b,0)→(d,1),(b,2)→(d,1),(c,1)→(d 称做AS的一个最小化决策规则集.显然，AS可 )},其对应的最小化决策规则可辨识矩阵[C]为 以有多个最小化决策规则集P引 G1=C2=G3=C2=G23=C3=:G1=f(a,2)(b, 0};G1=f(c,2)∧c,1),c,2)∧b,2),(a,2)(b 2最小化决策规则集的计算方法 0)b,2),a,2)(b,0∧(c,1)};C2=f(a,2)(b, 定义3设决策表系统S=,AS 0∧b,2),a,2(b,0∧(c,1)}. 是S上的一个基本算法，AS中有相同后件中的所 命题2设决策表系统S=， 有基本规则的集合为AS=中，9→中，…中一 AS0=中，攻→中，…，→剪为具有相同后件中 g,AP表示属于ASΦ的决策规则的所有前件的集 的所有基本规则的集合，[C]为决策规则集AS0的 合AP0={中，，…，虫}.记[中]表示满足所有后件中 最小化决策规则可辨识矩阵，AS为决策规则集 的对象集合，[A]表示满足所有前件的对象集 AS0的子集，AP6表示属于AS·的决策规则的所有 合，I=4],对任意的，∈(，当i为时， 前件的集合，则，出，=内对任意的G地都 C={6:6∈AP0且x,x∈[6]，或6=A∧4且x:∈ 存在Y∈C,使得YSAP. [4]、x∈4]，A、$∈AP}:当i=j时，C=中称 证明假设存在C≠中，不存在Y∈C,使得 Cg为x:,x的最小化决策规则集；[C]为决策规则 Y∈AP%,则x:∈（且x,∈6品，I6]或方∈(]且 集AS0=中→中，→中，…，虫→的最小化决策规 后品可，这与出1=子盾.所以，对任意 则集可辨识矩阵. 的Cg≠Φ，都存在Y∈C,使得YSAP6. 定义4设决策表系统S=， AS0={中→中，$→中，，虫→州为具有相同后件中 反证：假设存在，∈（且x,怎[可，对任意 的所有基本规则的集合，[C]为AS·的最小化决策 的x∈[，记C为x,x的最小化决策规则集，则 规则可辨识矩阵，则称M=个(Va::a∈C}为 不存在Y∈C,使得YSAP6,这与已知条件矛盾，所 可辨识公式. 以1可2I.又品，I∈.即，I1= 命题1[C]为决策规则集AS·=(4→中， $一中，中→的最小化决策规则可辨识矩阵，则 命题3设决策表系统S=, [C1具有如下性质： AS={中→中，一→中，…虫→g为具有相同后件中 1)[Cg是对称矩阵：2[C1主对角线上的元素 的所有基本规则的集合，[Cg]为决策规则集AS的 为空 最小化决策规则可辨识矩阵，其对应的可辨识公式 性质1)2)可以直接根据最小化决策规则可辨 M的极小析取范式为M,则M包含AS的全体 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
个对象 x 的属性值 ,即 x ∈U , a ∈A ,有 f ( x , a) ∈ V a . 对于任意 B ΑA ,记:ind (B) = { ( x , y) : f ( x , ak ) = f ( y , ak ) , ΠaA ∈A} ,则 ind ( B) 是 U 上的等价关系 , 称为由 B 决定的不可区分关系 ,它们产生的 U 上的 划分为 :U/ ind ( B) = { [ x ]B : x ∈U} , 其中 : [ x ]B = { y :( x , y) ∈ind ( B) }是 x 关于 B 的等价类[2 - 3 ] . 定义 2 设决策表系统 S = , A S 是 S 上的一个基本算法 , A S 中有相同后件φ的所 有基本规则的集合被表示为 A Sφ ,并且用 A Pφ 表示 属于 A Sφ 的决策规则的所有前件的集合. 如果| = s ∨A Pφ ∴∨( A Pφ - { , A S 是 S 上的一个基本算法 , A S 中有相同后件φ的所 有基本规则的集合为 A Sφ = { , A Sφ = { , A Sφ = { , A Sφ = { <1 →φ, <2 →φ, …, <n →φ} 为具有相同后件φ 的所有基本规则的集合 ,[ Cij ]为决策规则集 A Sφ 的 最小化决策规则可辨识矩阵 ,其对应的可辨识公式 M 的极小析取范式为 M1 ,则 M1 包含 A Sφ 的全体 · 66 · 智 能 系 统 学 报 第 2 卷
第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=,具有相 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 = ,具有相 同后件φ的基本决策规则集 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 ·
