收稿日期:2006-02-28作者简介:孙 胜(1978-),男,湖北黄冈人,博士研究生,研究方向为现代数据库理论与技术及系统实现;导师:王元珍,教授,博士生导师,主要研究方向为现代数据库理论及实现技术。
决策表的一种知识约简与规则获取方法孙 胜1,2(1.华中科技大学计算机学院,湖北武汉430074;2.黄石理工学院计算机学院,湖北黄石435003)摘 要:粗糙集理论是一种新型的数据挖掘和决策分析方法,利用粗糙集理论进行决策表的知识约简与决策规则挖掘已经成为研究热点。
文中介绍了粗糙集的基本理论,在此基础上运用该理论对从决策表中获取最小规则进行了研究,提出了决策表约简的启发式方法,并通过一个具体实例详细说明了决策规则获取过程,实例分析表明了其有效性。
关键词:粗糙集;决策表;决策规则;属性约简中图分类号:T P311.131 文献标识码:A 文章编号:1673-629X(2006)09-0035-03Knowledge Reduction and Rule Acquirement Method in Decision TableSUN Sheng 1,2(1.Schoo l of Computer Science,Huazhong U niv ersity of Science and T echnolog y,Wuhan 430074,China;2.School of Computer Science,Huangshi Institute of T echnolog y,Huangshi 435003,China)Abstract:Rough set theory is a new data mining and decision analysis method.Knowledge reduction and decision rule mining in decision table by using rough set theory has become a research hotspot.T he article introduces basic con cepts in rough set theory first.M inimal dec-i sion rule acquirement in deci sion table based on rough set theory i s researched.A heuristic approach for rule reduction is put forward,and the procedure of decisi on rule acquirem ent is i lluminated using an example.T he instance analysis show s its validity.Key words:rough set;deci sion table;decision rule;attribute reduction0 引 言粗糙集理论是由波兰科学家Z.Paw lak 教授于1982年提出的一种研究不精确、不确定性知识的数学工具[1,2]。
已应用于机器学习、知识发现、数据挖掘、决策支持与分析、专家系统、归纳推理和模式识别等许多科学和工程领域[3]。
从实际系统采集到的数据可能包含各种噪声,存在许多不确定因素和不完全信息有待处理。
传统的不确定信息处理方法,如模糊集理论、证据理论和概率统计理论等需要数据的附加信息或先验知识,而粗糙集理论能在缺少关于数据的先验知识的情况下,仅仅以对数据的分类能力为基础,对模糊或不确定性数据进行分析和处理,这就克服了以上几种方法的不足之处。
知识约简就是在保持知识库的分类和决策能力不变的条件下,删除其中不相关或不重要的知识[4]。
决策表的简化是知识约简的重要内容之一,并在数据挖掘和知识发现等领域有重大应用价值。
粗糙集理论的研究对象是一个二元信息表,称为信息系统[5]。
信息系统由一些对象通过在一些属性上的取值来构成。
若属性集合分为条件集和决策集,则信息系统称为决策表。
决策表简化的理论基础是属性的核与约简及其关系、规则的核与约简及其关系。
根据决策表简化的结果,利用决策规则挖掘算法可以获取决策系统的规则。
1 有关的粗糙集概念现实世界中的信息,在粗糙集理论中用决策表的形式给出。
下面先简要介绍一下文中主要用到的Rough 集基本概念,详细的请参考文献[3~5]。
定义1 称S =(U,A ,V ,f )是一个知识表达系统,其中U 是非空有限对象集合,U ={X 1,X 2,,,X n };A 是非空有限属性集合;f 是一个U @A 到属性值集合V 上的一个映射,它表示每个对象在每个属性上对应一个值,称为信息函数。
若A =C G D ,其中C 是非空有限条件属性集合,D 是非空有限决策属性集合,且C H D =ª,则称该知识表达系统为决策表。
此知识表达系统又称为决策系统。
定义2 若X A U,则称R -(X ){x I U:[x ]R A X }为X 的下近似集,R -(X )={x I U:[x ]R H X X ª}为X 的上近似集。
pos R (X )=R -(X )称为X 的R 正域,neg R (X )=U -R -(X )称为X 的R 负域。
第16卷 第9期2006年9月计算机技术与发展COM PUT ER TECHNOLOGY AND DEVELOPM ENTVo l.16 N o.9Sep. 2006定义3 设P A R ,如果P 是独立的,且ind (P )=ind (R ),则称P 为R 的一个约简,记为red (R )。
由定义知R 的约简是不惟一的。
定义4 设P A R ,P 中所有必要关系组成的集合称为P 的核,记为c ore (P )。
核与约简有如下关系:core (P)=H red (P)。
其中red (P )表示P 的所有约简。
定义5 设属性集P A R ,对象X ,Y I U,对于每个a I P,当且仅当f (X ,a)=f (Y ,a)时,X 和Y 是不可分辨的,即ind (P )={(X ,Y )IU:a I P ,f (X ,a)=f (Y,a)}。
定义6 设有决策表S =(U,A ,V ,f ),a(x )是记录x 在属性a 上的值,即a (x )=f (x ,a),C ij 表示辨识矩阵第i 行,第j 列的元素,辨识矩阵的定义为:C ij ={a I C :a(x i )X a (x j )} D (x i )X D(x j )ª D (x i )=D(x j )其中i,j =1,2,3,,,n,这里n =|U |。
定义7 信息系统中每一行就是一条决策规则des ([x]C )]des ([x ]d ),其中de s ([x ]C )表示U 中的个体x 关于属性集C 的属性值。
定义8 设U 为一个论域,C 和D 为定义在U 上的两个等价关系簇,若POS C (D)=POS (C \{a})(D),则称a 为C 中相对于D 是可省略的;否则,称a 为C 中相对于D 是不可省略的。
2 决策表约简的启发式方法决策表的简化就是化简表中的条件属性,化简后的决策表具有与化简前的决策表相同的功能,但化简后的决策表具有更少的条件属性。
这里包括属性的简化(即去掉一列)和属性值的简化(即去掉一列中的某些冗余属性值)。
去掉冗余属性值的决策表称为条件属性的核值表。
决策表的约简分为三步:(1)计算条件属性的约简,即从决策表中删去一些列;(2)删去重复的行;(3)删去多余的属性值。
前两步是对决策表进行整体约简,第三步是对每一条决策规则(每一行)进行进一步约简,使得在一行中去掉某些属性值后仍能划分到原来的决策类中。
决策表约简的第一步通常需要求出核属性集,有两种方法可以求出核属性集。
第一种求核方法的思想是:首先生成辨识矩阵,然后在辨识矩阵中找出所有属性个数为1的元素,所求核属性集是指所有满足上述条件的属性的集合;在第二种方法中,条件属性相对于决策属性e 不可省略的属性集为核属性集。
属性约简的启发式方法的基本思路是:先计算出核,而后根据其它属性的重要程度依次在核的基础上添加属性直到使所得的知识与原信息系统或决策表的分类能力相同为止,也可以根据决策属性对条件属性的依赖程度依次剔除掉那些对分类不产生影响的条件属性。
在属性约简之后,还要进行属性值的约简。
属性值约简是针对每条决策规则,去掉表达该规则的冗余值,以便进一步使决策算法最小化。
属性值的约简,最常用的方法就是数据分析法,是基于规则逐条进行处理的。
设B A A ,x I U,关于等价关系ind (B )包含x 的等价类[x ]ind (B)可以写成[x ]B 。
在一条决策规则中,对于任意的条件属性集C ,[x ]C =H [x ]a ,a I C 。
U y 7的条件属性集、决策属性集分别为C ,D,且a I C ,当且仅当[x](C -{a })A [x]D 时,称属性a 是规则U y 7中可省略的,否则,a 为不可省略的。
消去每条决策规则中不必要条件之后可得到属性值的约简结果。
3 基于粗糙集理论的最小决策规则获取算法从决策表分析得到的规律性知识,通常采用决策规则的形式记录下来,并可以在将来的决策过程中利用这些知识来对未知的观察样本进行决策判定。
知识约简的目的是导出关于决策表的决策规则,约简中属性的多少直接影响着决策规则的繁简。
因此期望找到具有最少属性的约简,即最小约简。
实际计算知识约简时,往往采用某种启发式算法。
属性重要性是算法的重要启发式信息,按照属性重要性从大到小逐个加到被选择的属性子集中,直到该集合是一个约简为止。
在决策表S 中,C 和D 分别为条件属性集和决策属性集,属性子集C c A C 关于D 的重要性定义为R CD (C c )=C C (D)-C C -C c (D )。
其中C C (D )=|POS C (D)|/|U |。
可以将上式左边的R CD (C c )理解为当属性子集C c 被除去时所发生的分类错误率。
特别地,当C c ={a}时,属性a I C 关于D 的重要性为R CD (a )=C C (D )-C C-{a}(D )。
决策规则的重要性一般通过其支持度和信任度两个指标进行度量。
其定义如下:决策规则de s ([x ]C )]des ([x ]d )的支持度为|[x ]C H [d ]D |/|U |。
决策规则des ([x ]C )]de s ([x ]d )的信任度为|[x ]C H [d ]D |/|x |C 。
下面给出基于粗糙集的最小决策规则获取算法:输入:一个决策表S =<U,C G D,V ,f >输出:最小决策规则集RULE步骤1:计算决策表S 中条件属性集C 关于决策属性集D 的重要性C C (D )=|POS C (D )|/||U |;步骤2:计算C 相对于D 的核R =CORE D (C);步骤3:对每个属性a I C -R ,计算其属性重要性R CD (a )=C C (D)-C C-a (D);步骤4:在C -R 中选择属性a 使得R CD (a )达到最大值,如果有多个属性a i (i =1,2,,,m )达到最大,那么选择与R 组合数最少的a j ;步骤5:R =R G {a j };步骤6:如果C R (D)=C C (D ),则终止,转步骤7;否则转步骤4;步骤7:在得到C 相对于D 的某个相对约简R 之后,进#36# 计算机技术与发展 第16卷一步运用数据分析法对决策表进行属性值约简,可得规则核值表;步骤8:根据规则支持度函数,对规则核值表所对应的每条规则进行评价,得到每条规则的支持度值;步骤9:对于规则核值表,提取大于支持度阈值的规则写入规则集RULE中,这样得到的规则集RULE就是决策表的最小决策规则集。