第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,V,f>,其中，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 , V , f > ,其中 , U 为对象的集合 ,即论域; A 是属性集合 , A = C ∪D , C 和 D 分别是条件属性集 和决策属性集 , D ≠Φ,V = V ∪a ∈A V a ,V a 表示属性 a 的 值域; f :U ×A →V 是一信息函数 ,它指的 U 中每一