一个基于粗集的决策树规则提取算法

收稿日期 :2007 - 01 - 24 基金项目 :国家自然科学基金项目 (60273043) ;安徽省自然科学基 金项目 (050420204) ;安徽省高校拔尖人才基金项目 (05025102) 作者简介 :丁春荣 (1975 - ) ,女 ,安徽淮北人 ,硕士研究生 ,讲师 ,研 究方向为数据挖掘、粗糙集 ;李龙澍 ,教授 ,博士生导师 ,研究方向为 智能软件和知识工程。 一个基于粗集的决策树规则提取算法 丁春荣1 ,2 ,李龙澍1 (1. 安徽大学 计算机科学与技术学院 ,安徽 合肥 230039 ; 2. 泉州师范学院 ,福建 泉州 362311) 摘　要 :决策树是数据挖掘任务中分类的常用方法。在构造决策树的过程中 ,分离属性的选择直接影响到分类的效 果 ,传统的决策树算法往往是基于信息论度量的。基于粗糙集的理论提出了一种基于属性重要度和依赖度为属性选择标 准的决策树规则提取算法。使用该算法 ,能提取出明确的分类规则 ,比传统的 ID3 算法结构简单 ,并且能提高分类效率。 关键词 :数据挖掘 ;粗糙集 ;决策树 ;属性约简 中图分类号 : TP301. 6 　　　　 　文献标识码 :A 　　　　　　　文章编号 :1673 - 629X(2007) 11 - 0110 - 04 A Rule Abstracting Algorithm of Decision Tree Based on Rough Set DIN G Chun2rong1 ,2 ,L I Long2shu1 (1. College of Computer Science and Technology ,Anhui University ,Hefei 230039 ,China ; 2. Quanzhou Normal University ,Quanzhou 362311 ,China) Abstract :The decision tree is a usual method of classification in data mining. In the process of constructing a decision tree ,the criteria of selecting attributes to split will influence the efficiency of classification directly. The decision tree algorithm traditionally is based on infor2 mation theory measure. Presented a new algorithm for classification rules extraction by choosing attributes of importance of attributes and dependance based on rough set . Using this algorithm ,can extract crisp rules from classification information system. Compared with the tra2 ditional ID3 algorithm ,it’s simpler in the structure ,and can improve the efficiency of classification. Key words :data mining ;rough set ;decision tree ;attribute reduction 0 　引 　言 分类是数据挖掘领域中的一个重要课题 ,许多挖 掘问题本质上都可以等价地转化为分类问题。分类的 主要方法有决策树[1 ] 、神经网络、统计学、粗糙集[2～5 ] 及遗传算法等 ,其中决策树方法是应用最广的推理算 法之一 ,具有分类精度高、速度快、生成的模式易于理 解等优点 ,特别是在学习过程中不需要很多背景知识 , 只要训练样本集能够用“属性—值”的方式达出来就 能使用决策树学习算法进行分类 ,因而在数据挖掘中 受到广泛关注。目前已经存在多种决策树算法 ,其中 最经典的就是 Quinlan 提出的基于信息熵的算法 ID3[1 ] ,C4. 5 [1 ]及后来的多个改进版本 ,并且已被广泛 应用于实际的分类问题中。但是基于信息熵[1 ,6 ]的算 法存在决策树中子树重复 ,及有些属性在某一路径上 被多次检验等问题 ,以致降低了分类的效率和效果。 特别当存在大量对分类无关的冗余属性时 ,生成的决 策树过度庞大 ,结构性差 ,难以发现一些本来可以找到 的有用规则。 粗糙集理论[3 ,4 ]是波兰科学家 Pawlak. Z 在 1982 年提出的对不完整数据进行分析、推理、学习、发现的 新方法 ,借鉴了逻辑学和哲学中对不精确、模糊的各种 定义 ,针对信息的不同分类模型 ,提出不精确范畴等概 念 ,为处理模糊信息系统或不确定性问题提供了一种 新型的数学工具 ,它不仅能够解决传统的数据分析方 法如决策树法不能解决的粗糙集数据 ,得到传统方法 如神经网络得不到的较高精度规则 ,而且能发现属性 之间的依赖关系并对所得的结果进行简明易懂的解 释。该理论已广泛应用于信息处理、数据挖掘等认知 领域。 文中基于粗糙集的理论提出了一种依据属性重要 度和依赖度为属性选择标准的决策树规则提取算法。 使用该算法 ,能提取出明确的分类规则 ,与传统的 ID3 第 17 卷 　第 11 期 2007 年 11 月 　　　　　　　　　 计 算 机 技 术 与 发 展 COMPU TER TECHNOLO GY AND DEVELOPMEN T 　　　　　　　　Vol. 17 　No. 11Nov. 　2007 算法相比 ,结构简单 ,并且能提高分类效率。 1 　相关概念 给定知识表达系统 S = ( U , A , V , f ) ,其中非空 有限集合 U 表示论域 , A 是关于 U 的属性非空有限集 合 V = ∪ a ∈A V a , V a 是属性 a的值域 , f : U ×A →V 是一 个信息函数 ,对于 Π a ∈A , x ∈U , f ( x , a) ∈V a ,若 属性集合 A = C ∪D ,其中 C 是条件属性 , D 是决策 属性 ,则该系统也被称为决策系统或决策表。 1. 1 　不可区分关系 对决策系统 S , R ∈ A 是条件属性集合的一个子 集 ,称二元关系 Ind( R) 为 S 的不可区分关系 : Ind( R) = { ( x , y) ∈U ×U | Π a ∈R , f ( x , a) = f ( y , a) } , 表示样本对象 x 和 y 关于属性子集 B 是不可区分的。 U/ Ind( R) 即等价关系 Ind( R) 的所有等价类 ,有时也 记作 U/ R 。 1. 2 　上、下近似 给定决策系统 S , R 是 U 上的一个等价关系 , X 是 U 的一个子集 ,则上近似 R - ( X) = ∪{ Y ∈U/ R | Y ∩ X ≠ ª} , R - ( X) 是根据知识 R , U 中一定能和可 能归入 X 的元素的集合。下近似 R - ( X) = ∪{ Y ∈ U/ R | Y Α X} , R - ( X) 是根据知识 R , U 中一定能归 入 X 的元素的集合。Pos R ( X) = R - ( X) 是 X 的 R 正 域。 1. 3 　知识依赖 如果知识 D的部分初等范畴能用知识C的某些初 等范畴来定义 ,称知识 D 部分依赖于知识 C。有 k = γC ( D) = Card( PosC ( D) ) Card( U) ,其中Card表示集合基数 ,则 称 D 是 k ∈[0 ,1 ] 依赖于 C。k 反映了知识C对D 的分 类能力 ,若 k = 0 ,则 D完全不依赖于C;若 k = 1 ,则 D 完全依赖于 C;若 0 < k < 1 ,则 D 部分依赖于 C。 1. 4 　属性重要性 在确定决策目标时 ,不同属性的重要性是不同的。 粗集根据属性的分类能力来确定该属性的重要性。属 性子集 C′Α C 关于 D 的重要性定义为σCD ( C′) = γC ( D) - γC- C′( D) ,当 C′= { a} 时 ,属性 a 的重要性 为σCD ( a) = γC ( D) - γC- ( a) ( D) ,σCD ( a) 的值越大 ,说 明属性 a 对分类的影响越大 ,分类能力越强。 1. 5 　属性约简 对决策系统 S ,属性 r ∈R Α A 是 R 中必要的 ,当 且仅当 Ind( R) ≠Ind( R - { r} ) ,否则 ,属性 r 在 R 中 是冗余或可省略的。属性 R 的约简是一个集合 R′∈ R ,当且仅当满足 : ①R′是独立的 ; ②Ind( R′) = Ind( R) 。 1. 6 　规则可信度和支持度 对于完全相容的决策表进行规则挖掘 ,得到确定 性的规则。而不相容的决策表挖掘到的规则是不确定 的 ,规则不确定性可以通过可信度和支持度进行度量。 对于决策表 S = ( U , A , V , f ) , A = C ∪{ d} : 决策规则 A →B 的可信度CD( A →B) = | X ∩ Y || X | , 其中 X = { x | x ∈U ∩A x} , Y = { y | y ∈U ∩B y} , A x 表示实例 x 的条件属性值满足公式A , B x 表示实例 x 的决策属性值满足公式 B 。支持度 CD( A → B) = | X ∩ Y | | U | 。 2 　提取规则算法 粗糙集中的规则提取 ,一般是先对条件属性集合 进行约简 ,约简后的属性个数直接影响着决策规则的 繁简和性能 ,而找到具有最少条件属性的约简是 NP 难问题。利用一些启发式约简算法可以得到约简属性 集 ,合并决策表中相同的行后得到约简表 ,可以认为该 约简表就是规则 ,但此时规则可能还含有很多冗余信 息 ,如何得到最简或相对最简的规则是粗糙集规则提 取算法要处理的问题。一般做法是 :先求得约简表的 核值属性 ,然后再在核中添加属性 ,直到某条规则可以 在约简表中是唯一的表达为止。但求核后逐个增加条 件属性是个组合问题 ,最坏的情况是计算 2| A | - 1 次。 2. 1 　算法及测试属性选择标准 ID3 算法建立的决策树是单变量决策树 ,在每一 个非叶结点只能选择唯一属性 ,势必会造成子树重复 , 上述问题促使人们考虑多变量决策树[7 ] ,或者构造一 种超属性[6 ] 。文中提出一种基于决策树的规则提取算 法 (AAID ,an Algorithm by Attribute Importance and De2 pendance) ,利用该算法从约简表中提取规则 ,即使不能 保证得到最简规则 ,但也得到相对最简规则。算法既 可以处理相容决策表 ,也可以处理不相容决策表。在 决策树构造过程中 ,对每个结点分裂属性的选择是至 关重要的 ,总希望能得到最佳划分 ,使尽可能多的样本 被正确分类。传统的决策树构建方法是利用信息论中 信息增益[2 ,5 ]寻找数据库中具有最大信息增益的属性 来建立分支结点 ,现在通过粗糙集方法可以依据属性 对分类的影响即属性重要性来选择属性建立分支 ,但 是有时在属性重要性相等情况下仍难以选择分裂属 性。如表 1 所示[8 ] 。 根据属性重要性公式计算条件属性 a ,b ,c 的重要 性 ,结果σCD (a) =σCD (b) =σCD (c) ,此时根据属性重要 ·111·第 11 期 　　　　　　　　　　　　丁春荣等 :一个基于粗集的决策树规则提取算法 性无法选择用哪个属性进一步分裂 ,但从条件属性 a , b ,c 和决策属性 d 分别对 U 的划分 : 表 1 　决策表 U a b c D 1 0 0 1 1 2 0 1 1 0 3 1 0 1 1 4 1 1 0 0 5 1 1 1 1 U/ { d} = { (2 ,4) , (1 ,3 ,5) } , Y1 = (2 ,4) , Y2 = (1 , 3 ,5) U/ { a} = { (1 ,2) , (3 ,4 ,5) } , U/ { b} = { (1 ,3) , (2 ,4 , 5) } , U/ { c} = { (4) , (1 ,2 ,3 ,5) } 可以看出 ,由 b 取某一值能正确分类 Y2 中的 2 个对 象 ,由 c取某一值能正确分类 Y1中的1个对象 ,而 a取 任何值都不能正确分类任何样例。可见选择属性对分 类效果更好 ,如果选择 a 决策树的复杂度将大于前者。 由此 ,选取一个参数 K 来反映决策分类对条件属性集 的依赖度 : K = max{ | X i Α Y j | / | Y j | } ,上例中 , a , b , c 的 K 值分别为 0 ,2/ 3 ,1/ 2。 2. 2 　AAID 算法 输入 :一个信息系统 S ; 输出 :决策规则表 DT ; (1) 对 S 进行属性约简 ,删除冗余属性。 (2) 计算约简属性集中各属性的重要性 , 选择值 最大的属性作为分裂属性 ,if 各个属性重要性相等 , then 选择 K 值最大的属性作为分裂属性 ,if 各属性 K 值相等 , then 选择序号靠前的属性建立分支结点。 (3) 重复以上过程 ,直到各分类的决策属性一致或 属性集合为空 ,产生一个叶子结点。被选属性选择后 , 在属性集中删除掉 ,以保证各分支不重复选择属性。 (4) 读树 ,生成规则 ,并计算规则的 CD 和 SD。 (5) 验证规则最简性。对每一条规则从第一个属 性结点逐个去掉 ,如果去掉后该规则在约简表中对应 唯一的实例 ,则继续去除下一个规则属性结点 ,直到没 有可供去除的规则属性结点为止 ;如果规则对应多个 样例则停止验证该规则转向下一条规则。 步骤 1 是约简掉冗余属性过程 ,步骤 2 和 3 是建 树过程 ,步骤 4 是生成规则过程 ,由于决策树本身特 点 ,进行验证可保证得到最简规则集。 3 　算例分析 假设下面数据集是一个信息系统(如表 2 所示) 。 对表 2 进行属性约简 ,知 A4 ,A6 相对于决策属性 D 是可以省略的 ,将其去除后不会改变系统的分类能 力 ,去除冗余属性后的决策表如表 3 所示。 表 2 　一个信息系统 U Condition attributes( C) A 1 A 2 A 3 A 4 A 5 A 6 Decision attribute ( D) 1 0 1 0 1 1 1 0 2 1 0 0 0 1 0 1 3 0 0 1 0 0 0 0 4 0 0 1 1 0 0 0 5 1 0 1 1 1 1 0 6 1 0 0 1 1 1 1 7 1 1 0 1 1 1 1 8 1 1 1 1 0 1 0 9 0 1 1 0 1 1 0 10 1 1 1 1 1 1 1 11 1 1 1 1 1 1 0 表 3 　约简后的决策表 U new 　　old Condition attributes( C) A 1 A 2 A 3 A 5 Decision attribute ( D) 1 1 0 1 0 1 0 2 2 ,6 1 0 0 1 1 3 3 ,4 0 0 1 0 0 4 5 1 0 1 1 0 5 7 1 1 0 1 1 6 8 1 1 1 0 0 7 9 0 1 1 1 0 8 10 1 1 1 1 1 9 11 1 1 1 1 0 　　这是一个不相容决策表 ,针对表 2 ,论域 U = { 1 , 2 ,3 ,4 ,5 ,6 ,7 ,8 ,9} ,条件属性 C = { A 1 , A 2 , A 3 , A 5} , 决策属性是 D ,依据 AAID 算法建树 ,过程如下 : U/ D = { (1 ,3 ,4 ,6 ,7 ,9) , (2 ,5 ,8) } ; U/ C = { (1) , (2) , (3) , (4) , (5) , (6) , (7) , (8 ,9) } posC ( D) = { 1 ,2 ,3 ,4 ,5 ,6 ,7} ; 则γC ( D) = Card( PosC ( D) Card( U) = 7/ 9 对于属性 A 1 , U/ Ind( C - { A 1} ) = { (1 ,5) , (2) , (3) , (4) , (6) , (7 ,8 ,9) } posC- { A 1} ( D) = { 2 ,3 ,4 ,6} ,则γC- { A 1} ( D) = 4/ 9 ; 属性 A 1 的重要性σCD ( A 1) = γC ( D) - γC- { A 1} ( D) = 1/ 3 ; 对于属性 A 2 , U/ Ind( C - { A 2} = { (1) , (2 ,5) , (3) , (6) , (7) , (4 ,8 ,9) } posC- { A 2} ( D) = { 1 ,2 ,3 ,5 ,6 ,7} , 则 γC- { A 2} ( D) = 2/ 3 ; 属性 A 2 的重要性σCD ( A 2) = γC ( D) - γC- { A 2} ( D) = 1/ 9 ; 对于属性 A 3 , U/ Ind( C - { A 3} ) = { (1 ,7) , (2 ,4) , (3) , (5 ,8 ,9) , (6) } posC- { A 3} ( D) = { 1 ,3 ,6 ,7} ,则γC- { A 3} ( D) = 4/ 9 ; 属性 A 3 的重要性σCD ( A 3) = γC ( D) - γC- { A 3} ( D) = 1/ 3 ; ·211·　　　　　　　　　　　　　　　　　　　　　计算机技术与发展 　　　　　　　　　　　　　　　　　　第 17 卷 对于属性 A 5 , U/ Ind( C - { A 5} ) = { (1) , (2) , (3) , (4) , (5) , (6 ,8 ,9) , (7) } pos C- { A5} ( D) = { 1 ,2 ,3 ,4 ,5 ,7} , 则 γC- { A 5} ( D) = 2/ 3 ; 属性 A 5 的重要性σCD ( A 5) = γC ( D) - γC- { A 5} ( D) = 1/ 9。 由此知 ,条件属性中 A 1 和 A 3 重要性最大 ,且相 同 ,此时再计算 K值 ,属性 A 1与 A 3的 K值也相等 ,此 时选择序号靠前的 A 1 作为根结点 ,当 A 1 = 0 时 ,{ 1 , 3 ,7} ;当 A 1 = 1 时 ,{ 2 ,4 ,5 ,6 ,8 ,9} 。对于 A 1 = 0 这个 分支 ,分类集合决策为一类 ,停止选择属性过程。规则 可信度 CD = 1 ,支持度 SD = 3/ 11 3 100 % = 27 . 3 %。 对另一个分类集合继续选择属性。分类集合如表 4 所示。 表 4 　A 1 =‘1’分类集合 U new 　　　old Condition attributes( C) A 2 A 3 A 5 Decision attribute ( D) 2 2 ,6 0 0 1 1 4 5 0 1 1 0 5 7 1 0 1 1 6 8 1 1 0 0 8 10 1 1 1 1 9 11 1 1 1 0 　　此时 ,计算 A 2 , A 3 , A 5 的属性重要性 ,方法同上 , 结果 A 3 重要性大于另外两个属性 ,此时选择 A 3 作为 分裂结点进行分类 , 当 A 3 = 0 时 , { 2 ,5} ;当 A 3 = 1 时 ,{ 4 ,6 ,8 ,9} 。当 A 3 取值 0 时 ,决策属性类别为 1 ,停 止选择属性过程 , 规则可信度 CD = 1 , 支持度 SD = 2/ 11 3 100 % = 18 . 2 % ;当 A 3 取值为 1 时 ,继续选择 属性。重复以上过程 ,直到最后得到完整决策树 ,如图 1 所示。 图 1 　决策树 根据生成的决策树提取规则 ,得到规则集 (如表 5 所示) 。 表5 经过验证后 ,规则 4 可将 A 1 和 A3 属性除去 , 所以化简后的决策表如表 6 所示。 表 5 　得到的规则集 序号 If Then CD SD 1 A 1 = 0 D = 0 1 36. 36 % 2 A 1 = 1 &A 3 = 0 D = 1 1 27. 27 % 3 A 1 = 1 &A 3 = 1 &A 2 = 0 D = 0 1 9. 09 4 A 1 = 1 &A 3 = 1 &A 2 = 1 &A 5 = 0 D = 0 1 9. 09 5 A 1 = 1 &A 3 = 1 &A 2 = 1 &A 5 = 1 D = 1 0. 5 9. 1 6 A 1 = 1 &A 3 = 1 &A 2 = 1 &A 5 = 1 D = 0 0. 5 9. 1 　　 表 6 　简化后规则集 序号 If Then CD SD 1 A 1 = 0 D = 0 1 36. 36 % 2 A 1 = 1 &A 3 = 0 D = 1 1 27. 27 % 3 A 1 = 1 &A 3 = 1 &A 2 = 0 D = 0 1 9. 09 4 A 2 = 1 &A 5 = 0 D = 0 1 9. 09 5 A 1 = 1 &A 3 = 1 &A 2 = 1 &A 5 = 1 D = 1 0. 5 9. 09 6 A 1 = 1 &A 3 = 1 &A 2 = 1 &A 5 = 1 D = 0 0. 5 9. 09 　　通过以上处理 ,得到了相对最简规则 ,并且完全保 留了原信息表中的信息。上述例子采用传统 ID3 算法 进行处理后可得到完全相同的决策树 ,因此 AAID 算 法的执行效率优于 ID3 算法。 4 　结束语 文中结合粗糙集与决策树的优点 ,提出了一种新 的基于粗糙集和决策树的决策规则提取算法 ,结合粗 糙集和决策树的优点 ,可以处理相容表 ,也可以处理不 相容表。虽然不一定得到最简的规则 ,但却能方便地 得到相对最简规则 ,避开了 NP 问题。并且执行效率 优于 ID3 算法 ,通过与其它实验数据的比较 ,用 AIAD 算法得到的规则所用的属性有时比较少 ,但规则个数 不一定会比 ID3 少。实际应用表明该算法是有效的。 参考文献 : [ 1 ] 　Quinlan J R. Induction of decision trees[J ] . Machine Learn2 ing ,1986 ,1 (1) :81 - 106. [2 ] 　Pawlak Z. Rough sets[J ] . International Journal of Computer Information Science ,1982 ,11 :341 - 356. [3 ] 　曾黄麟. 粗糙集理论及其应用[ M] . 修订版. 重庆 :重庆大 学出版社 ,1998 :119 - 129. [4 ] 　张文修. 粗糙集理论与方法[ M] . 北京 :北京科学工业出版 社 ,2001 :3 - 24. [5 ] 　Pawlak Z. Rough sets[J ] . Communications of ACM ,1995 ,38 (11) :89 - 95. [ 6 ] 　赵卫东 ,盛昭瀚. 粗糙集在决策树生成中的应用[J ] . 东南 大学学报 ,2000 ,30 (4) :134 - 136. [ 7 ] 　苗夺谦 ,王 　珏. 基于粗糙集的多变量决策树构造方法 [J ] . 软件学报 ,1997 ,8 (6) :425 - 431. [ 8 ] 　Zhu H. The Research of the Simplest Decision Tree Production Algorithm Based on Rough Set [J ] . Computer Engineering and Application ,2003 (13) :129 - 131. ·311·第 11 期 　　　　　　　　　　　　丁春荣等 :一个基于粗集的决策树规则提取算法