（系统理论专业论文）粗集理论在决策规则提取中的应用.pdf

山东大学硕士学位论文 粗篡理论在决策规则提取中的应用 李钢 ( 山东大学数学与系统科学学院，济南，2 5 0 1 0 0 ) 摘要 粗集理论。由z p a w l a k 于1 9 8 2 年提出，它作为一种处理不确定性与模糊性 的新兴数据工具，得到了越来越广泛的应用，特别在决策分析领域。文章分析了 粗集理论在决策规则提取方面的应用，从决策表的预处理。到决策规则的提取， 决策规则的评价。 第一章，文章简单介绍了粗集理论的基础知识。 第二章，文章讨论了决策表的预处理，特别是简单的数据过滤问题。传统的 方法是将决策表转化为二元的决策表，这往往占用大量的存储空间。文章中提出 了一种基于过滤矩阵的简单数据过滤方法，并针对不同的情况( 是否保持属性值 序关系) 提出了不同的计算策略：最后，文章分析了此方法的有效性：可以提高 决策表的统计意义。 第三章，文章分析了决策规则的提取问题。首先，文章简单比较了几种决策 规则提取算法，包括：最小数目的决策规则，所有的决策规则，用户满意的决策 规则的提取算法；随后，文章分析了动态情况下的决策规则提取问题，即决策表 在不断更新的情况下，决策规则的维护问题。文章中提出了一种新的规则提取算 法：它不是简单地对更新后的决策表进行决策规则提取，而是充分利用已有的决 策规则信息，在搜索决策表之前，尽量减小搜索候选集的大小。通过分析表明这 种方法不仅可以大大减少计算时间，降低计算的复杂性，而且是十分实用的。 第四章，文章分析了决策规则的评价问题。文章提出了种简单易于计算的 评价指标，可以有效的表达所提取的决策规则的预测能力。文章针对不同的几种 决策规则：n n 规则n o 规则，o o 规则，n o o 规则，分析了评价指标的计算以及它 们相应的性质。对于n n 规则，通过分析发现：这一评价指标与z p a w l a k 定义 的“近似质量”是一致的。另外，文章分析了在决策属性中存在等级结构情况下， 评价指标的变化情况。对于n o 规则，0 0 规则，n o o 规则，文章重点分析了评 价指标计算过程中关于权重的计算，以及评价指标取极值的情况。 关键词：粗集理论数据过滤决策规则规则提取评价 l l 山东大学硕士学位论文 t ea p p l i c a t i o no fr o u g hs e tt h e o r y i nd e c i s i o nr u l e si n d u c n o n l i g a n g s c h o o lo f m a t h e m a t i c sa n ds y s t e ms c i e n c e s ，s h a n d o n gu n i v e r s i t y , j i n a n , s h a n d o n g 。c h i n a , 2 5 0 1 0 0 a b s tr a o t z p a w l a kp r o p o s e dr o u g hs e tt h e o r yi nt 9 8 2 i ti san e wt o o lt od e a lw i t ht h e u n c e r t a i n t ya n df u z z i n e s s i t sa p p l i c a t i o ni n c l u d e s s e v e r a ld o m a i n s ，e s p e c i a l l yt h e d e c i s i o na n a l y s i s i nt h ep a p e r , w ea n a l y z et h ea p p l i c a t i o no fr o u g hs e t st h e o r yi nt h e i n d u c t i o no fd e c i s i o nr u l e s ，i n c l u d i n gt h ep r e - p m c e s so fd e c i s i o nt a b l e ，t h ei n d u c t i o n o f d e c i s i o nr u l e sa n dt h em e a s u r e m e n to f d e c i s i o nr u l e s i ns e c t i o n1 ，w eg i v et h ef u n d a m e n t a lk n o w l e d g ea b o u tr o b g hs e tt h e o r y i ns e c t i o n 2 ，t ot h ep r e p r o c e s so f d e c i s i o nt a b l e ，w ea n a l y z et h es i m p l ed a t af i l t e r w ep m p o s e a n e wm e t h o dt os i m p l ed a t af i l t e rb a s e do nt h ef i l t e rm a t r i xa n dg i v et h ed i f f e r e n t c o m p u t a t i o n m e t h o d su n d e rt h ed i f f e r e n tc o n d i t i o n s a tl a s t , w ea n a l y z et h ee f f i c i e n c y o ft h em e t h o d , i e ，t h ei m p r o v e m e n to fs t a t i s t i c ss i g n i f i c a n c e i ns e c t i o n3 ，t ot h e i n d u c t i o no fd e c i s i o nr u e s ，f i r s t , w e c o m p a r e s e v e r a ld e c i s i o nr u l ei n d u c t i o n a l g o r i t h m si n c l u d i n gt h ei n d u c t i o na l g o r i t h m so f t h es m a l l e s tn u m b e rd e c i s i o nr u l e s ， a 1 1 也ed e c i s i o nr u l e s t h ed e c i s i o nr u l e ss a t i s f y i n gt h eu s e r t h e nw ep r o p o s et h e i n d u c t i o na l g o r i t h m su n d e rt h ec o n d i t i o no fc h a n g e ，i e ，t h em a i n t e n a n c eo fd e c i s i o n r u l es e t i td o e sn o to n l yi n d u c et h ed e c i s i o nr u l e sf r o mt h ed e c i s i o nt a b l ea f t e rc h a n g e i tu s e st h ei n f o n n a t i o no fi n d u c e dd e c i s i o nr u l e st od e c r e a s et h es i z eo fc a n d i d a t es e t b e f o r es c a n n i n gt h ed e c i m o nt a b l e w ed e m o n s t r a t et h em e t h o dc a nr e d u c et h et i m e a n dc a l lb ea p p l i e di nr e a ll i f e i ns e c t i o n4 ，t ot h ee v a l u a t i o no fd e c i s i o nr u l e s ，w e p r o p o s eas i m p l ea n d e f f i c i e n te v a l u a t i o ni n d e xt h a tc a nm e a s u r et h e p r e d i c t i o na b i l i t y o fd e c i s i o nr u l e s t os e v e r a lk i n d so fd e c i s i o nr u l e s ：n n - r u l e ，n o - r u l e ，0 0 - r u l e ， n o 一0r u l e ，w ea n a l y z et h ec o m p u t a t i o na n dt h ep r o p e r t i e so f t h ei n d e x f o rn n - r u l e ， w ec a nf i n dt h a tt h ei n d e xi si na c c o r d a n c ew i t ht h e a p p r o x i m a t i o nq u a l i t y d e f i n e d b yz p a w l a k f o rn o r u l e ，o o r u l e ，n o or u l e ，w ea n a l y z et h ec o m p u t a t i o no ft h e w e i 曲ta n d t h es u f f i c i e n ta n d n e c e s s a r y c o n d i t i o no f t h ei n d e xe q u a lt o0o r1 k e y w o r d s ：r o u g h s e t t h e o r y ；d a t af i l t e r ；d e c i s i o ur u l e ；r u l ei n d u c t i o n ；e v a l u a t i o n 1 1 1 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名：茎翅日期： 丝：坦 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅：本人授权山东大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本 学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：奎翅导师签名：日期： 笪叁i o 山东大学硕士学位论文 第一章租集理论基础知识 粗集理论 1 ，由z p a w l a k 于1 9 8 2 年提出，是一种新的处理模糊和不确定 性知识的数学工具，其主要思想就是在保持分类能力不变的前提下，通过知识约 简，导出问题的决策或分类规则。 粗集理论具有如下特点： ( 1 ) 不需要先验知识。模糊集和概率统计方法是处理不确定信息的常用方 法。但这些方法需要一些数据的附加信息或先验知识，如模糊隶属函数和概率分 布等，这些信息有时并不容易获得。粗集理论仅利用数据本身提供的信息，无须 任何先验知识。 ( 2 ) 粗集理论是一个强大的数据分析工具。应用粗集理论进行数据分析有 如下优点： 能够提供有效的算法来发现数据中隐藏的模式： 发现数据的最小集( 数据约简) ： 评估数据的重要性； 根据数据生成决策规则集； 对计算结果能够提供直接的解释； 基于粗集理论的多数算法特别适于并行运算： 易于理解。 由于粗集理论具有以上特点，它己被应用于各个领域： ( 1 ) 股票数据分析。文 1 2 应用粗集理论分析了十年间股票的历史数据， 研究了股票价格与经济指数之间的依赖关系，获得的预测规则得到了华尔街证券 交易专家的认可。 ( 2 ) 模式识别。文 1 3 中应用粗集理论研究了手写字符识别问题，提取了 特征属性。 ( 3 ) 冲突分析。文 5 中利用粗集理论建立了中东六国关于中东和平问题各 自立场的谈判模型。 ( 4 ) 数据挖掘。数据挖掘是当前人工智能和数据库技术交叉学科的研究热 点之一。粗集理论已成为数据挖掘的一个重要方法，其导出的知识精练且更便于 山东大学硕士学位论文 存储和使用。 ( 5 ) 粗糙控制。文 1 4 中应用粗糙控制研究了“小车一倒立摆系统”，“水泥 窑炉”的控制问题。粗糙控制的优点是简单迅速，实现容易，不需要象模糊控制 那样进行模糊化和反模糊化。 ( 6 ) 专家系统。粗集理论抽取决策规则的特点，为构造专家系统知识库提 供了一条崭新的途径 1 5 3 。 ( 7 ) 决镱分析。粗集方法得到的决策规则是在分析以往经验数据的基础上 得到的。粗集方法允许决策对象中存在一些不太明确，不太完整的属性，弥补了 常规决策方法的不足，较其他方法有一定的优点 1 5 ，1 6 3 。 另外，它还与模糊集理论 4 ，1 7 ，1 8 ，神经元网络 1 0 ，遗传算法 2 0 3 ， 证据理论 9 ，1 9 ，拟阵论 1 1 ，规划理论 7 有一定的联系。 下面我们主要介绍租集理论的基础知识 2 ，3 ，8 。在介绍粗集理论之前， 我们首先介绍信息系统的概念。 信息系统就是一数据表，它的列对应着属性，行对应着对象( 样本) ，表的 元素是属性值，即s = ( u ，a ，y ，f ) ，其中，u 表示对象的有限集合，称为论域： 一称为属性集，对于每一个属性口a ，有一集合圪相关联。它是属性口的值域： y = u k ；厂：【，4 一v 是一个信息函数，它为每个对象的每个属性赋予一个 a e a 信息值，即v a a ，“u ，f ( u ，a ) 。对于属性集a 的子集露在u 上形成一个二 元关系，( b ) ，被称为不可辨关系，定义如下：( z ，y ) ，( 占) 当且仅当正( z ) = 工( y ) ， 对于任意的a b ，显然，i ( b ) 是一等价关系，( 占) 所确定的等价类构成的集合， 记为u i b 。，( b ) 的一个含有对象x 的等价类，则记为 工 。若( 工，y ) ，( 丑) ，则 称x 与y 是b 不可辨的。关系i b ) 的等价类称为b 一基本集。 下面我们给出决策表的定义。 若对于信息系统s = ( u ，a ，v ，f ) ，属性集a 分为不相交的两类属性，即条件 属性，决策属性，则称其为决策表，记为s = ( u ，r u d ，y ，) ，通常我们只考虑 一个决策属性的情况，对于含有多个决策属性的情况，可利用文 2 ，3 ，8 中的方 法转化为只有一个决策属性的情况来处理。 2 山东大学硕士学位论文 设给定了信息系统s = 缈，a ，v ，f ) ，x u ，我们的目的是利用r 中的属性 值来描述集合x 。我们定义两种运算来对每一个x u 分配两个集合墨( x ) ， r ( x ) 分别称为x 的r 一下近似，r 一上近似 星( 柳= u ( 【工k ： 石】。z j r ( z ) = u x 】。： x 。n r 矿) 因此，一个集合x 的r 一下近似( 有时也称为正域，记为p o s 。( x ) ) 就是包 含于该集合的所有r 一基本集的并，r 一上近似是与该集合有非空交的所有r 一 基本集的并。另外，令b n 。( x ) = r ( ) 一星( z ) 表示x 的r 一边界域。 n e g 。( x ) = u r ( x ) 表示x 的r 一负域。若对于b n 。( x ) = ，则称集合x 相对 于r 是精确的，否则，称集合x 相对于r 是租糙的。 籽自等价关和( 雕则始肭近 螨靛蝴舭) = 蹦 其中x 驴，l x l 表示集合x 的基数。 集合z 的粗糙度为：p 。( ) = 1 一盯。( ) 。 设f = ( x 。，x ：，x 。) 是u 的一个分类或划分。这个分类独立于属性r 。f 的 r 一下近似，r 一上近似分别定义为： 墨( f ) = 迅( x 。) ，r ( x ：) ，g ( x 。) r ( f ) = r ( x 。) ，r ( x ：) ，r ( x ) ) i 星( x ) i 定义f 的近似分类精度为： 仃。( ，) = 专l z l 耳( x 。) i i 垦( x ，) i 定义f 的近似分类质量为： ，一( f ) = 秆。 它们将在第二章，第四章中有所应用。 下面我们分析粗集理论中的另一个核心内容知识约简。知识约简就是在保持 分类能力不变的前提下，删除其中不相关或不重要的属性( 知识) 。 设c6 r ，若等价关系j ( r ) = i ( r 一 c ) ) ，则称c 为r 中不必要的，否则称c 为 r 中必要的。 山东大学硕士学位论文 如果每一个c r 都为r 中必要的，则称r 为独立的，否则称r 为依赖的。 设q 譬p ，如果q 是独立的，且，( q ) = i ( p ) ，则称q 为p 的一个约简。显然， p 可以有多种约简。p 中所有必要属性组成的集合称为p 的核，记作c o r e ( ：p ) 。 显然，核与约简有如下关系：c o r e ( p ) = r 7 r e d ( p ) ，r e d ( p ) 表示，的所有约简。 在实际应用中，一个分类相对与另一个分类的关系十分重要，因此，我们将 介绍知识的相对约简与相对核的概念。 设j ( q ) ，( p ) 为u 上的等价关系，9 的p 正域记为p o s ，( q ) ，即 p o s 一( q ) = u e ( x ) x e u a q 的p 正域是【，中所有根据分类u p 的信息可以准确地划分到等价关系 ，( q ) 的等价类中的对象集合。 若p pf 蔫i f ：p o s p ( q ) = p o s p f 时 ( q ) ，则称p 为p 中g 不必要的，否则p 为 p 中q 必要的。p 中每一个p 都为q 必要的，则称p 相对于q 独立的。 设s 量p ，s 为p 的q 约简当且仅当s 是p 的q 独立子族且p o s s ( q ) = p o s p ( q ) 。 尸的q 约简称为相对约简。尸中所有q 必要的属性构成的集合称为p 的q 核，简 称为相对核，记为c o r e 。( p ) 。 另外，在利用决策表进行决策分析时，往往需要根据属性的重要性进行排序， 以便提高搜索的有效性。下面我们分析属性重要性的概念。 在决策表中，不同的属性可能具有不同的重要性，例如：当由症状描述病人 的情况时，对于识别病人的身体状况有些症状具有更重要的意义。 为了找出某些属性( 属性集) 的重要性，我们的方法是从表中去掉一些属性， 再来考虑没有该属性后分类将如何变化。如去掉该属性相应分类变化较大，则说 明该属性的强度大，即重要性高：反之，说明该属性的强度小，即重要性低。 令r 和d 分别为条件属性集和决策属性集，属性子集r r 关于d 的重要 性定义为 c r r d ( g ) = ，r ( d ) 一y “( d ) 。 由上面所介绍的粗集理论基础知识及关于粗集的众多优点，下面几章中，我 们将分析粗集理论在决策规则提取中的应用。第二章，将讨论决策表的预处理； 第三章，讨论决策规则的提取；第四章，讨论决策规则的评价问题。 山东大学硕士学位论文 第二章数据过滤 在第一章中，我们介绍了粗集理论的基本知识。显然，利用粗集理论，我们 可以对决策表进行处理以获得有用的知识。但有时，绘定的决策表，往往我们并 不能直接利用粗集理论来处理，有时决策表中含有连续属性，冗余属性，这时， 我们不能直接利用粗集理论来处理，我们需要对决策表进行预处理，如：连续属 性的离散化，冗余属性的约筒，数据过滤。对于连续属性的离散化可见【6 】。 本章中，我们主要讨论数据过滤问题。 2 1 数据过滤的基础知识1 2 7 1 给定决策表s = ，q ，p a ，记q ，p 引起的等价类划分为u q ， u p 。等价类x u q 与一个或多个等价类z ，i u ，p 相交，这引起如下的 q _ p 规则： 确定的：z 爿 x k 不确定的：x x x y o v xv vy 用，x n k 庐，i = o ，1 ，m 若x 引起的q 寸p 规则是确定的，则称x 是p 一确定的。 我们称满足规则q 寸p 的样本为规则q p 的支持对象。 我们定义规则q _ p 的近似质量f ( q 斗p ) 胞删= 逃竺祥塑 它实际上就是p 关于q 的正区域。在基于粗集理论的数据分析中，我们经常 利用它作为预测能力的一种度量标准( 即利用q 在多大程度上确定p ) 。 有时规则q _ p 只有少量的支持对象，这时规则的预测能力将是十分有限 的，若只采用近似质量来度量，有些情况将很难处理( 具体情况可见文 2 7 1 ) 。 我们将这类规则称为“偶然的”。因此，有必要采取统计方面的知识来检验规则 的随机性。 假设个信息系统是一随机过程的实现形式，其中q ，p 的属性值是相互独立 的，若无其他的信息，我们可假定q ，p 的各自属性值的组合是固定的，而q ，p 之 间的属性值组合是随机的。 山东大学硕士学位论文 设盯为u 的一个交换，p a ，定义一个新的信息函数r 舯 州一一j f , ( c r ( x ) ) 若r p 。 l ，( z ) 其它 在所有的情况中，近似质量的分布情况为 孵”= r ( q 一仃( p ) ) ，a 是u 的一个交换) 设野。为一空假设，我们须估计我们所观测到的近似质量y m = y ( q - + p ) 在 整个贸口，中的位置，即估计概率 p(y，。1日。)=兰!兰二三二坚!塑三；?三型 通常，我们将上式成为规则q 哼p 的统计意义。 若p ( r 。，。l h 。) 的值是低的，通常地小于5 ，则称规则q p 是有意义的， 否则，称规则是“偶然的”。 2 2 简单的数据过滤1 2 8 l 文 2 8 】中提出了一种简单的数据过滤方法来提高规则的统计意义，而保持信 息系统的内在依赖信息不受损失，其基本工具是二元信息系统。首先，将原始的 信息系统转化为二元信息系统，然后，在二元信息系统的基础上，利用一定的方 法对属性值进行合并，以完成数据的过滤，提高规则的统计意义而保持规则的近 似质量不变。 假定信息系统s = ，a = m ，p ，) ，另外，h 只有 o ，1 两个 属性值。我们针对规则 m ，p ) 一日进行计算，下面给出具体的算法： 1 构造二元信息系统s 。 2 寻找满足 ( 垤u ) l ，( 石) = 1 呻厶( x ) = i ( v x u ) - 5 ( x ) = l 叶厶( 工) = 1 】 的二元属性m ，p ，这里m 。，p ，。 分别在m ，p 内构造它们的并，例如：若，m 护，m 。满足上述条件之一， 则定义新的二元属性，定义如下 厶。( 工) 。1 铮l ( ) = l j fo ，) 。 6 山东大学硕士学位论文 同时，用” 代替，埘 ，m h 3 同第二步。对满足条件 ( v x u ) ( x ) = 1 一 ( j ) = 0 】 ( v x u ) l ( x ) = 1 - ( x ) = 0 的属性做类似的处理。 4 在新的系统中，相对于决策属性做依赖性分析。 文 2 8 中i t n 了过滤前后，规则的近似质量保持不变，而规则的统计意义得 到了提高。 2 3 基于过滤矩阵的简单数据过滤 由上面的算法，我们可以发现：在信息系统二元化过程中，需要将每个非二 元属性q 拆成l 1 个属性。因此，当信息系统属性较多且属性的值域较大时，对 l1 象数目较大时，将产生庞大的二元信息系统，占用大量的存储空间，计算复杂性 提高。 为此，我们在文中提出一种利用过滤矩阵的方法，可有效的减少存储空间。 并证明了处理前后，规则的近似质量保持不变，而规则的统计意义得到了提高。 2 3 1 不考虑属性值的序关系 我们定义过滤矩阵m ，柬进行过滤处理。这里，我们将只限于一致的决策表， 对于不一致的决策表将在2 3 4 节加以讨论。 定义1 对于给定的决策系统s ，属性集月= c i ，c ：，c 。 ，若对属性c ，进行过滤 处理，我们构造过滤矩阵，用每行表示属性 c ，1 1s f 蔓”，i j 属性值的不同组合， 列表示属性c 的不同属性值，对于每一个样本“，u ，在过滤矩阵中均有对应的 行指标数u ( “，) ：l i ”，i ， 以及列指标数f ( “，) 。对于过滤矩阵中没有样本 对应的元素我们记为“”，表示不作考虑。 下面我们定j ( p i j 的相容关系，利用它，我们可以对属性c ，的属性值进行过滤 处理。 定义2 对于过滤矩阵m ，中的列口与列b 称为是相容的，若对于每一对样本 “。，“。u 满足正，0 。) = 仉l ，( “。) = b ，正0 。) = 正，姐。) ，1 s i s 月，i j ， 山东大学硕士学位论文 厶以) = 兀( “。) 。对于满足这一要求的样本对，我们称为列口与列b 相容的支持 对象对。列a 与列b 相容的支持对象对的数目，我们称为列a 与列b 的相容度， 记为c p ( a ，b ) 。对于不满足上述要求的列，我们称为是不相容的，且相容度为0 。 显然，对于相容的两列口，b ，我们可以对其进行合并，并标注标签( 口，b ) 。 经过这样的处理，我们可以达到数据过滤的目的，这与文 2 8 1 的简单数据过滤 思想是一致的。 定理1 对于过滤矩阵m ，若对任意两不相容的列，不进行合并，标注相同的 标签，则利用此过滤矩阵得到的决策表与原决策表是一致的。 证明：设列a ，b 是不相容的，则存在样本对“。，u 。u ，满足 厶似，) = 正，( 。) ，1 墨i n ，f j t 正( u ，) = 口，正( “。) = b ，厶( u 。) 厶( “。) ， 若对列a ，b 合并，标注相同的标签( 口，b ) ， 则五0 。) = 五( “) ，l s f s ，f j ，正缸。) = ( 口，b ) = 五( “) ，由于我们是对 一致的决策表进行处理的，所以，l ( u 。) = l ( u 。) ，这与前提条件正扭。) l ( u 。) 是矛盾的。 定理1 给出了进行数据过滤并保持决策表一致性的必要条件，然而，我们需 要在保持决策表一致的前提下，尽量减少属性c ? 进行过滤后的属性取值的数目， 这样可使过滤处理后根据决策表所得的决策规则的统计意义更强一些。 显然，以上的问题就是计算过滤矩阵m ，的列进行最大相容聚类。若过滤矩 阵是比较简单的话，我们可以直接得出聚类结果。有时，过滤矩阵是比较复杂的， 将很难直接得出结果。下面我( f l n 用图论中的染色理论来处理这一问题。首先， 我们定义不相容图。 定义3 对于不相容图g 图的顶点对应着过滤矩阵m ，中的列，则图中两点之 间有边相连当且仅当顶点对应的m ，中的列是不相容的。 显然，对于过滤矩阵中的列进行相容聚类，就是对不相容图g ，进行染色的 着色数目。恰当的着色可保证代表不相窑列的两顶点不着相同的颜色。相同的颜 色只赋予相容的列，因此，最优的着色能得到最大的相容聚类。 我( f i n n 道图的着色问题是n p h a r d 问题只有采用启发式算法来解决。文 3 9 1 中根据递减的连通度来对顶点进行划分，并将顶点着与之相邻的顶点着色的颜 色，以得到最小的着色数目。我们对上述算法做小小的调整：当对顶点v 进行着 山东大学硕士学位论文 色时，与之相容的几个顶点已经着了不同的颜色，则我们选取与顶点v 最相容的 一类已着色顶点v ，h 的顶点颜色来做顶点，的着色，其中，相容度为 芝之d ( v ，v 。) t 我们这样做是为了保证最终提取的决策规则的支持能大一些。 定理2 对于不相容图瓯的最优染色数是为了保持决策表一致性，所需的属性 c 。属性值的最小数目。 证明：若属性c ，的属性值数目小于不相容圈g ，的最优染色数。则至少有不相容 的两列染了相同的颜色。根据定义，存在样本“。，”u ，满足 丘，( “。) = ( ”) ，l s i n ，i j ，正，( u 。) = 口，正( “) = b ，兀似。) 厶( “) 列a ，b 进行了合并。这样，在过滤前，样本“，“。u ，被分配不同的决策值， 而过滤后，两样本赋予了相同的决策值。显然，这与原系统是不一致的。 在实际应用中，有时决策表是稀疏的。此时，若仍采用前面的过滤矩阵的方 法，显然，会浪费大量的存储空间，我们可直接根据决策表来构造不相容图。根 据定义3 若存在样本“。，“【，兀 。) l ( “) ，正 ) = 4 ，正，( “) = b ， 正0 。) = 矗) ，1 s i h ，i j ，则在不相容图q 中对应列a ，b 的顶点v 。，u 之 间有边( v a ，h ) 相连，我们提出种有效构造q 的方法。首先，根据属性c ，的取 值及决策值对样本集【，进行分类，分类后具有相同的属性r 一 c i ) 取值的构成一 类，对应于过滤矩阵中的行，在每一类中，具有相同决策取值的构成一个子类， 对来自于同一大类，不同子类的样本，在不相容图g 中有边相连。 我们只要对属性集r 中的每一个属性进行类似的过滤处理就可以了。 2 3 2 保序的数据过滤 在上面的分析中，我们没有考虑属性值的序关系。有时我们在数据过滤过 程中，需要保持属性值的序关系，也就是说，我们在属性过滤过程中，只能对保 持属性值优势关系的相邻属性值进行合并。这时，上一节的算法需要修正一下。 对于定义1 中的过滤矩阵m 。，我们须要求，各列的列指标数1 ，2 ，l v 。i ， 1 1j l 对应的属性c ，的属性值应该与属性c ，的属性值优势关系保持一致。 另外，我们不能再利用不相容图g ，对属性c ，的属性值进行相容聚类，因为， 构造的不相容图没有考虑属性值是否相邻。我们采用与文 3 6 ，3 7 中类似的方法 来对过滤矩阵进行处理，实现属性值的合并。 9 山东大学硕士学位论文 我们定义如下五种操作。 操作1 若相邻两列的元素是对应相同的，则这两列是相容的，将其合并为一列。 ab d 1 d 2d 2 操作2 若相邻两列的元素是对应相同的，或相邻两列中有一列的是空的，且至少 有一列中的元素不是“”，则这两列是相容的，将其合并为一列。 d 6 d -d t d 2d 2 ( 口，6 ) d 1 d 2 操作3 若一列的所有元素均为“”，且其相邻的两列元素是相同的，则这- - n 是 相容的，将这三列合并为- y u 。 口 6 c d ld i d 2d 2d 2 ( 口，6 ，c ) d i d 2 操作4 若一列的所有元素均为“”，且相邻的两列元素是相同的，或至少有列 的元素不是“一”，则这三列是相容的，将这三列合并为一列。 0 山东大学硕士学位论文 口 b c d l吐 d l d 2d 2 操作5 若一列的所有元素为“”，且相邻的两列元素是不同的，则这列元素可与 其相邻的任意一列元素合并。 口 6 c d ld ， d 1 d 2d i c ( 口，6 ) d id t d 1 d 2d l 下面分析我们所设计的数据过滤方法可以提高决策表的统计意义。 2 3 3 方法的有效性 首先，我们分析一下，存储量的问题。我们假设决策表有【，个对象，m 个属 性，每个属性有n 个属性值。我们所提出的方法：每次对一个属性进行过滤时， 所需存储的矩阵元素为月+ 一= n 。个，共有朋个属性，则过滤过程中，共需存 储历n 。个元素；而传统的过滤方法，需要存储的元素为u 肌x 一个。所以，当 u h ”时，我们提出的方法存储量是小的。我们知道所有可能的情况月。个，而 且n 通常大于等于3 ，决策表中对象数目【，通常占到所有可能情况的4 0 以上， 所以，u n ，在实际应用中是成立的。另外，需要说明的是：我们提出的方 法，每步仅须处理 t 。个元素，且每步完成后，前一步的存储可以删除；而传统 的方法，每一步都基本要处理u x 用n 个元素。从上面这些分析可见，我们所提 出的方法，不仅每一步的处理量要小，而且总的处理量也要小。 山东大学硕士学位论文 下面，我们分析：过滤前后，决策表中规则的统计意义是否得到了提高。 定理3 设置d 为s 的规则，r 呻d 为s 的规则，则 r c r - - d ) = r ( r o d ) 。 证明：因为决策表是一致的，所以，根据决策表中的样本得到的决策规则都是d 确定的。 设c e r ，其两个不同的值a ，b ，相应过滤矩阵中的两列是相容的，则列a ， b 在数据过滤后将进行合并。设“，h 。u 是列d ，b 相容的支持对象对，则 兀0 ) = 兀( ) ，五，( ) = 以丘，。) = b ，丘m 。) = 厶 。) ，1 蔓i s h ，i j 则合并后，由它们对应的合并对象引起的决策规则仍然是确定的。 所以，r ( c 斗d ) = r ( c 一d ) ，从而，r ( r d ) = r ( r - q p d ) 。 定理4 设r 哼d 为s 的规则，r _ d 为s 的规则，则 p ( y ( r d ) 啤。) p c r ( r 一d ) l h 。) 证明：设口e ，首先证明：r ( r 哼叮( d ) ) r ( r 。盯( d ) ) 。 设se p r 上存在满足算法条件的两等价类沁】。和【“，】 则经过数据过滤 后，合并为，中只的一个等价类。由于玎的影响，当分配它们相同的决策值时， 使得吨，”，仍为d 确定的，但也有可能分配它们不同的决镱值，使得它们变为非d 确定的。因此， r ( r 呻似d ) ) 2 r ( r 一吠d ) ) 。 下面证明定理4 。 假设r ( r - - h 盯( d ) ) r ( r + 斗d ) ，由定理3 ， 、 r ( r 斗d ) = r ( r 。d ) 从而，y ( r 斗仃( d ”r ( r 巧( d ) ) r ( r _ d ) = r ( r d ) 即 r ( r 一盯( d ”r ( r d ) 所以，i 驴僻_ 盯( d ”，( r d ) ：盯) i i 钞( f 一盯( d ) ) r ( r + _ + d ) ：盯i e i 根据定义，定理成立。 根据定理4 ，我们可以说：过滤后较过滤前，决策表的统计意义得到了提高。 2 3 4 不一致的情况 实际应用中，决策表经常是不一致的，即具有相同条件描述的对象有不同的 1 2 山东大学硕士学位论文 决策赋值。这时为了在数据过滤过程中，最大限度的保持原决策表的信息，我们 只能就决策表中确定的一部分进行处理。 对于过滤矩阵中的元素，我们定义为扩展的决策函数值。这时，我们称过滤 矩阵中的两列是相容的，不仅要求它们的元素对应相同，而且要求各元素的基数 不大于l ，即要求对应的合并列中样本都是确定的，这与文 2 8 1 1 是一致的。剩下 的工作与2 1 。2 2 节中是一样的。 有时，我们应用这种处理方法收效甚微，若这时规贝提取的目的是提取分类 规则，则只须要求最终提取的决策规则是确定的。这时，我们可采取文【3 8 】中的 方法，对过滤矩阵中不确定的部分也进行过滤，只要能保证过滤后的分类误差有 所降低就行。具体的计算方法有待进一步的研究。 2 3 5 例子分析 我们分析文 2 8 1 中的例子。有决策表如表2 1 所示。 针对属性m ，我们构造过滤矩阵m 。，如表2 2 所示。 【，p x il3o x 2 3 o 和2 1o x 433o 奶2 4l x 6 411 z ，151 砘5 41 表2 t 口m 123 45 1ol 2o 0o 4ll 51 表2 2 针对属性p ，我们构造过滤矩阵m 一如表2 3 所示。 山东大学硕士学位论文 所 p 12345 1o1 20ol 30o 41 5l 表2 3 我们可以得到经过数据过滤后属性州的取值1 ，2 ，3 合并，属性值4 ，5 合 并；属性p 的取值1 ，2 ，5 合并，属性值3 ，4 合并。这与文 2 8 1 中具有相同的 数据过滤结果。 山东大学硕士学位论文 第三章决策规则提取 在第二章中，我们讨论了决策表的预处理，包括连续属性的离散化，简单的 数据过滤。在经过预处理后，我们就可以利用处理后的决策表进行决策规则的提 取。在本章中，我们将分析决策规则提取的几种算法。第一节，我们将介绍一下 决策规则的基本知识；第二节，我们将分析比较几种已有的决策规则提取算法； 第三节，我们将重点分析讨论动态情况下，利用基于支配关系( 优势关系) 粗集 理论进行的决策规则提取。 3 1 决策规则基础知识 决策规则就是对决策表中属性值间依赖关系的一种表现形式。粗集理论作为 处理不确定性的有利工具，它利用决策类的上，下近似来分析，从上，下近似中， 我们得到一定的决策规则：确定的规则，不确定的规则。根据决策类的下近似， 可以得到确定的决策规则，根据决策类的上近似或边界域得到不确定的决策规 则。 给定决策表s = u ，r u d ，v ，厂 。( 口，v ) ，a r ，v 圪，称为基本条件c 。 q 个基本条件的并c ，汜为c = c 。v c ：v vc 。，它的大小记为s i z e ( c ) 。另外， 定义c 的覆盖【c 】，为满足c 所指定条件的所有对象( 样本) 。给定决策类y u d 。 则正覆盖【c 】+ = c l n y 表示所有的由c 覆盖的正样本，负覆盖 c ；= c 】n 缈】，) 表示所有的由c 覆盖的负样本。 一个决策规则就是如下形式： 若足，则 ，。 其中，r 是基本条件的并c 1v c 2v vc 。，满足 刚；妒。 r 称为规则的条件部分，y 称为规则的结论部分。 若规则的条件部分r = c 。v c ：v vc 。满足如下条件： ( 1 ) 一致性：限】；= ( 2 ) 最小性：9 , r 中移去任意一个c 。，则一致性不再成立 则我们称规则是判断式的。 在实际应用中，我们须对规则一进行一定的评价，下面我们介绍几种基本的 山东大学硕士学位论文 度量标准： ( 1 ) 规则的支持 s u p p ( ) = 陋】+ i ( 2 ) 规则的置信度 = 错 ( 3 ) 规则的覆盖度 t 妒群 ( 4 ) 规则的长度 l e n g t h ( r 1 ) = s x z e ( r ) 。 目前已有许多的规则提取算法用来提取不同类型的决策规则，但大体可分 为三类： ( 1 ) 最小数目的决策规则 ( 2 ) 所有的决策规则 ( 3 ) 满足用户要求的决策规则 对于决策规则集r s ( 假设它是针对决策类y 而言的) ，若它满足如下条件： ( 1 ) 每一条规则r j 岱的条件部分满足最小性 ( 2 ) u t r = y ( 3 ) 不存在任何规则，船，使得船一r ，满足条件( 1 ) ( 2 ) 则我们称规则集r s 是最小的。 对于第一类规则，就是说最终提取的判断式决策规则构成的规则集是最小 的； 对于第二类规则，就是说提取所有的判断式决策规则： 对于第三类规则，就是说提取所有的满足用户要求的判断式决策规则。 3 2 几种决策规则提取算法的比较 在本节中，我们将对这三类决策规则的提取算法做一简单比较介绍。 ( 1 ) 最小数目决策规贝k j 2 3 】 山东大学硕士学位论文 对于提取的决策规则的基本条件利用属性值对来表示：( 属性= 值) 。 c 表示基本条件，c 表示决策规则条件部分的侯选集，c ( g ) 表示添加到 c 中的基本条件集合，规则r l 由其条件部分r 来表示，r s 表示规则集，y 表示 决策类。 下面给出具体的l e m 2 算法。 b e g i n g ：- - r ；r s ：= 毋； w h i l e g 西d o b e g i n c ：= ；c ( g ) = c ： c 】ng ) ； w h i l e ( ( c 2 ) o r ( ! c y ) ) d o b e g i n 在c ( g ) 中选择i c 】ng | 最大的c ； i f 多个c 满足要求，t h e n 选取i c i 最小的c ： i f 仍有多个c 满足要求，t h e n 从序列中选取第一个 c ：= c u 【c ；g ：= c ng ； c ( g ) = c ： c 】r 、g 矿 ；c ( g ) ：= c ( g ) 一c ； e n d ； f o rv c cd o i f c - c 】y ，t h e nc ：= c 一 c ； 在c 的基础上生成决策规则r l ，并添加到r s 中。 g ：吖- u m s j r 】； e n d ； f o rv r l r sd o i f u “嘲= y t h e nr s ：= r s - r t ；e n d 它与许多传统的机器学习算法一样，都采用了启发式策略。它的基本思想是 依次从基本条件集中按照某一启发式标准来选取“最好的”基本条件来构造最初 的观则，然后从样本集中去除满足规则的样本，重复这一过程