（计算机应用技术专业论文）信息论在粗糙集连续属性离散化中的应用.pdf

辽j 。师范人学硕十学位论文 摘要 知识发现是当前计算机科学与人工智能领域最为活跃的研究课题之，粗糙集由于 其特有的优势，成为了知识发现领域非常晕要的理论。而连续槿性离散化是利用料糙集 进行知识获取所必要的数据预处理阶段。本文以知识发现为引j 子，以料糙集和信息论为 理论基础，以决策表下连续属性离散化为研究对象，提出了两种基于信息论的决策表连 续属性离散化算法。算法运用了信息论的相关概念，保证了在离散化的过程中信息的低 损失度和数据处理的高效性，并通过合理的实验验证了本文算法的有效性。 本文的主要工作如下： 1 论述研究背景，指出粗糙集在处理连续属性数据时的局限性，并埘离散化算法的 研究现状进行了综合探讨； 2 介绍粗糙集的重要表示形式决策表，指出决策表对知识发现的：蓖要性，并给 出在决策表下连续属性离散化的形式化定义。 3 介绍信息沦的基本概念，给出了知识的信息化表示，在此璀础i ：刈+ 车i i 糙集中的i ： 要概念和运算进行厂信息化的描述，证明了卡h 糙集的代数表示与信息农乃之m 的谯属，陀 约简卜- 的柏火性。 4 提出了两种基于信息论的决策表连续属性离散化算法，两种算法都是运用了信息 论中的统计学概念，并以决策表的不一致率为停止条件，在高效离散的艇稚；卜保证了决 策表的刁i 相容性不发，七改变； 5 在v c + + 6 0 环境下实现了本文提出的两个算法，并对离散化后的数捌利j j d m b e n c h 平台下c 4 5 与s v m 进行分类处理，与其他算法离散后数拥分类结果进f r 比较， 证明了本文提出算法的有效性。 关键词：知识发现；粗糙集；决策表；信息论；连续属性离散化 信息论红粗糙集连续属性离散化中的戍心 d i s c r e t i z a t i o no fr e a lv a l u ea t t r i b u t e sf o rr o u g hs e tu s i n gi n f o r m a t i o n t h e o r y a b s t r a c t t o d a y ，k d di so n eo ft h em o s tp o p u l a rf i e l do fc o m p u t e rs c i e n c ea n da r t i f i c i a l i n t e l l i g e n c e ，a n dr o u g hs e th a sb e c o m eav e r yi m p o r t a n tt h e o r yi nt h ef i e l do fk d dd u et oi t s u n i q u ea d v a n t a g e s d i s c r e t i z a t i o ni st h en e c e s s a r yd a t ap r e - p r o c e s s i n gs t a g ew h e nw e d i s c o v e rk n o w l e d g ef r o md a t a b a s eu s i n gr o u g hs e tt h e o r y i nt h i sp a p e r ，w ep r o p o s e dt w o k i n d so fd i s c r e t i z a t i o nf o rd e c i s i o nt a b l ew h i c hb a s e do ni n f o r m a t i o nt h e o r ya n d r o u g hs e t t h e o r y i no r d e rt ok e e pt h eb o t ha l g o r i t h m sr e l i a b i l i t ya n de f f i c i e n c y ，w eu s et h er e l a t i v e c o n c e p t so fi n f o r m a t i o nt h e o r y s o ，t h ea m o u n to fi n f o r m a t i o ni nd e c i s i o nt a b l ei sn o tl o s t t o om u c h ，a n dt h ee x p e r i m e n tp r o v e dt h a tb o t ha l g o r i t h m sa r ee f f e c t i v e t h em a i n w o r ko ft h i sp a p e ri sa sf o l l o w s ： 1 ) d i s c u s s i n go u rr e s e a r c hb a c k g r o u n d ，a n dp o i n t i n go u td i s c r e t i z a t i o ni san e c e s s a r y p r e p r o c e s s i n gs t e pf o rk d du s i n gr o u g hs e t t h e n ，w ec o n d u c t e dac o m p r e h e n s i v es t u d yo n c u r r e n tr e s e a r c hs t a t u so f d i s c r e t i z a t i o n ； 2 ) i n t r o d u c i n gt h ed e c i s i o nt a b l ew h i c hi si m p o r t a n tf o rd a t ar e p r e s e n t a t i o ni nk d d f i e l d ，a n dt h ef o r m a ld e f i n i t i o no fd e c i s i o nt a b l eb a s e do nr o u g hs e ti sp r o p o s e d 7 f h e p r o c e s so fd i s c r e t i z a t i o ni sf o r m a l l yd e s c r i b e d ，a n dw eh a v ea n a l y z e dt h ee v a l u a t i o nof d i s c r e t i z a t i o n ； 3 ) d e s c r i b i n gt h e b a s i cc o n c e p t so fi n f o r m a t i o nt h e o r y ar e l a t i o n s h i pb e t w e e n k n o w l e d g ea n di n f o r m a t i o ni ss e tu p ，a n dt h e nb a s e do nt h er e l a t i o n s h i pa ni n f o r m a t i o n r e p r e s e n t a t i o no ft h ec o n c e p t sa n do p e r a t i o n sa b o u tr o u g hs e tt h e o r ya r eg i v e n i na d d i t i o n ， t h ee q u i v a l e n c ep r o p e r t i e sb e t w e e ni n f o r m a t i o nr e p r e s e n t a t i o na n da l g e b r a i cr e p r e s e n t a t i o no f k n o w l e d g er e d u c t i o na r ep r o v e d t h e s ec o n c l u s i o n sa r eh e l p f u lf o rp e o p l et ou n d e r s t a n dt h e e s s e n c eo fr o u g hs e ta n ds e e kn e wa l g o r i t h m so fk d d u s i n gr o u g hs e t 4 ) t w oa l g o r i t h m so fd i s c r e t i z a t i o nf o rd e c i s i o nt a b l ea r er a i s e di nt h i sp a p e r b o t ha r e b a s e do nt h es t a t i s t i c a lc o n c e p t so fi n f o r m a t i o nt h e o r y f o rt h ep u r p o s eo fe n s u r i n gt h a tt h e i n c o m p a t i b i l i t yo fd e c i s i o nt a b l ed o e s n tc h a n g e ，t h ei n c o n s i s t e n c yo fd e c i s i o nt a b l ei sa s s t o pc o n d i t i o n sf o rd i s c r e t i z a t i o ni nb o t ha l g o r i t h m s ； 5 ) p r o g r a m m i n gb o t ha l g o r i t h m si nv c + + 6 0e n v i r o n m e n t w ec l a s s i f yt h ed i s c r e t ed a t a u s i n gc 4 5 a n ds v mi m p l e m e n t e da tt h ed m b e n c hp l a t f o r m i ti s p r o v e dt h a t o u r a l g o r i t h m sa r ee f f e c t i v eb yc o m p a r e dw i t ho t h e rd i s c r e t i z a t i o na l g o r i t h m s 辽j 。师范人学硕卜。位论文 k e yw o r d s ：k d d ：r o u g hs e t ：d e c i s i o nt a b l e ：i n f o r m a t i o nt h e o r y ：d i s c r e t i z a t i o n 信息论在祖糙集迩续属性离散化中的心刖 目录 摘要l a b s t r a c t i i l 绪 仑1 1 1 研究背景1 1 2 离散化研究现状h l 1 3 本文工作3 1 4 文章组织结构4 2 粗糙集理论及离散化过程5 2 1 粗糙集定义及其基本理论【1 , 2 l 5 2 2 决策表及其离散化表述7 2 2 1 决策表与知识发现7 2 2 2 粗糙集理论下决策表定义8 2 2 3 决策表连续属性离散化表述10 2 3 连续属性离散化过程11 2 3 1 典型离散化过程ll 2 3 2 离散化结果评价13 3 粗糙集理论中运算与概念的信息形式1 4 3 1 信息论及基本概念1 3 3 】1 4 3 2 知识的信息化表示15 3 2 1 知识的概率分布15 3 2 2 知识的信息熵和。幻：信息1 6 3 3 粗糙集t 要概念与运算的信息表j l6 3 4 本章小结l8 4 基于信息论的决策表连续属性离散化1 9 4 1 决策表中的信息表示19 4 2 算法捕述2 0 4 3 本章小结21 5 信息偏差在决策表连续属性离散化中的应用2 3 5 1 基本概念2 3 5 1 1 相关定义2 3 5 1 2 离散化的信息论表述一2 3 辽j 。师范人学硕 = 学位论文 5 1 3 区问信息量的度量2 4 5 2 算法描述2 5 5 3 本章小结2 6 6 实验及结果分析2 7 6 1 算法及实验数据介绍2 7 6 2 实验平台及分类实验2 8 6 2 1d m b e n c h 介绍2 8 6 2 2c 4 5 分类实验2 9 6 2 3s v m 分类实验3 0 6 3 实验结果分析31 7 结论与展望，3 2 7 1 算法及实验数据介绍3 2 7 2 实验平台及分类实验3 2 参考文献3 4 攻读硕【= 学位期f 日j 发表学术论文情况3 7 j i 迂谓 ：3 8 v 辽j 。师范人学硕十学f 移论文 1绪论 本章对粗糙集和连续属性离散化的研究和发展进行概况性说明，指出粗糙集在知 识发现领域的重要作用及其本身在处理连续数据上的局限性，最后介绍整个文章的卜要 工作和内容组织结构。 1 1 研究背景 料糙集理论【l 2 l 是波兰科学院z p a w l a k 院士于1 9 8 2 年提出的一种关于数据分析和推 理的理论。该理论能有效地处理复杂系统的数据和信息，月由于该理论在处理数掘时无 须提供除数据本身以外其他任何的先验信息，使得对问题的描述和处理相对于其他理论 ( 比如概率论、模糊数学和证据理论等) 比较客观，所以很快被人：r 智能领域所接受， 并发展成为一种处理模糊和不精确问题的新型高效的数学j j 二具【2 1 。经过多年的研究努力， 粗糙集理论已经在数据挖掘、决策分析、模式识别、机器学习和智能控制等智能处理方 面取得j ，很成助的应用1 2 , 3 , 4j ，成为人工智能和信息科学最为活跃的研究领域之。，一 经典p a w l a k 粗糙集模型中的不町分辨关系定义在集合论中等价类基础上的，要求 。数据属性的值域为离散集合，而住实际获取的数据集中，并不能保证数据的离敞性，这 大人限制了半h 糙集模型的应用。为了让该理论能够更为实用，通常在利用料糙集对数拂； 和信息进行分类与学习之前，首先要利用离散化技术对处理对象进行预处理1 2j ，这样就 可以把粗糙集拓展到多种类型数据集上，使得粗糙集的应用范围更加，“泛。伴随料糙集 理论在知识发现和智能数据处理领域不断受到人们的关注，以1 j 红知识发现领域仪被作 为边缘性问题的连续属性离散化也受到人们越来越多的关注和深入研究l 5 l 。 连续属性离散化并不算是新的研究课题，对于早期知谚 发现领域中许多商效的分类 学习算法及规则提取算法，都存在只能处理离散性数据或对连续数据处理效率低卜的| u j 题【5j 。这就需要通过属性离散化手段来对数据进行预处理，以此来简化智能数槲处理器 的结构和设计过程，加快知识的获取速度。另外，对于那砦泛化程度低的离敝属性，为 了使数据处理算法能获得良好的性能，也常常通过离散化手段来提升陔属性的泛化水 平。近年来，粗糙集已经在学术界和行业内的广受推崇，而离散化技术义是粗糙集理沦 处理数据流程中必需的预处理过程 5 , 6 1 ，使得基于粗糙集的连续属性离散化渐渐受剑很多 专家学者的关注，该课题的研究也渐渐系统化、规模化。 1 2 离散化研究现状 连续属性离散化就是住特定的连续属性的值域范围内选取若干个离散划分点，将属 性的值域划分为世氅离散的区间，最后用不同的符号或整数值代表落在每个子区l 日j 中的 信息沦红粗糙集连续属性离散化i l 的戍川 属，陀值【引。对连续属性的离散化过程，本质一卜来说，就是用特定的阈值米对连续的属性 空间进行划分的过程。在早期的知识发现过程中，连续属性的离散化通常是结合领域专 家的评价标准来完成的1 7 1 ，这种离散化算法通常具有比较高的准确性，但是其效率很低， 且不易扩展，在某个领域运用得非常成功的算法无法在其他领域获得同样的效果。随酋 计算机数据量的一i 断增加和软件技术的提高，需要一种通用的处理算法来对数据进ij 二合 理的离散化以提高d b m s 等数据和信息处理软件的通用性和商用化，经过多年来埘连 续属性离散化的广泛而深入的研究，当前已经有很多高效通用的离散化算法被提出，这 些算法按照不同的标准，町以进行如下的分类1 8 , 9 1 。 根据足否使用数据决策类信息，可以把离散化算法非为有监督和无监督。无监督算 法t 叮以用于所有知识表达系统，通过数据连续值本身所具有的特定统计规律来进行离敝 处理，比如等宽区l 、日j 法( e q u a l w i d t h ) 和等频区间法( e q u a l f r e q u e n c y ) 是最常用且效率 最高的两种无监督离散算法1 8 l ；通过鼋采样l l o j ( r e s a m p l i n g ) 技术的数据分布规律也, q - 以对样本数据进行区间划分来实现整体数据的无监督离散化：些比较流彳j ：的聚类算 法，比如k m e a n s 算法】等也常常作为无监督离散化算法来使用。有监督算法! j ! i j 足指代 对某一连续属性进行离散化时考虑决策类对连续属性分布的作用。代表算法仃基f 卡力 统计的c h i m e r g e 系列算法【1 2 - 1 5 1 、基于类属性关联度的c a l m 系列算法| 1 6 - 1 8 峰u 基于信息 熵的系列算法1 1 9 2 2 1 。无监督算法由于其只考虑连续属性的分布，忽略决策值，离散化的 数掘不能很好地运用于分类学习，但是其效率要高。而有监督算法把决策值作为离敝化 霞要的参考依据，经过离散的数据可以更好地用于知识发现的后续处理阶段，使用比较 广泛。 根据离散数据时使用的方式不同，可以把离散化算法分为自底向l l 和自顶向卜两 种，通常也通俗地叫做归并法( m e r g i n g ) 和分裂法( s p l i c i n g ) 。分裂法的思路足，初 始把整个属性取值范围作为一个离散区间，初始化候选断点集合，然后通过达代的方，r i = 从候选断点集巾选出满足判断条件的最优断点，用选h j 的断点对区间进行划分以完成离 散化。这嫩的“判断条件”既可以是根据连续属性本身的统计分布规律( 无监督的) 进 行设定，也可以根据决策属性值来设定条件( 有监督的) ；归并法的思路是，初始把连 续属性值相同的设为同一区间，然后对于相邻的两个区间，考察二者的决策类属性值分 布的关联性，同样通过迭代的方式逐个合并满足条件的相邻区间，卣到达到某种终j l ：条 件，这黾可以看出归并算法足无法根据连续属性本身的统计规律来设定合并条件的，所 以，所有的归并都应该是有监督的，没有无监督的合并离散化算法。 根击| ；f 离散化算法在知识发现过程中是否作为独立的预处理模块，可以把离散化算法 分为静态算法和动态算法，动态算法就是指那螳嵌套到分类学习算法，把离散化j 分类 辽j 。师范人学硕十学位论文 算法自机结合所形成的算法。比如文献【4 7 】中通过定义、。个分配指标来扩展朴素贝叶斯 分类算法，使得算法在分类过程中完成连续属性的离散化，大大提高了朴素贝叶斯分类 算法的正确识别率。 根据属性离散化处理是否考虑其他条件属性的影响，可以把离散化算法分为属性独 立算法和属性相关算法，属性相关所获得的离散效果较佳，但是其效率极为低下，尤其 是对那些数据量大或特征数多的数据，大大违背了离散化作为数据预处理过程高效快速 的准则。对于独立算法，其简单和快速的特点受到业界的广泛认可f 8 】。 另外，根据是直接把连续属性划分为有限区间还是通过一个迭代过程完成简化，可 以离散化算法分为直接离散化和递进离散化：根据在离散化过程判断条件的小同，可以 把离散化算法划分为基于信息论的、基于统计学的、基予类属性关联的和基于精确度度 量的等离散化算法。 根据上面的分类分析，可以对离散化算法进行如下的层次化分类表述： ； 离散化 。 。 辫 ；辱：i 了五j ： l “ f ? f 上一一1 厂l ”- 允 【督 i 柯监督 i 尤舱督 ! ! 钉| | f 督 0 一一准确l ：1 | r ! k ，+ | 膏寥分布 |信童论类属性依赖譬fr 思比 。o r-rtt- 。i 。t， 允： ：c h j 2 系列算法： ： 等宽、等频 ： 信息熵 ：c al m 、c a d d i 精确度j 堑赶 ： ： ? ? ? ：j ：，j 图i 1 离散化算法的层次化分类 f i g 1 1ah i e r a r c h i c a lf r a m e w o r kf o rd i s c r e t i z a t i o nm e t h o d s 图1 1 反映了离敞化算法的整体分类，首先考虑分裂合并对算法的划分，其次从有 无监督对算法进一步分类，最后根掘离散化算法中使用的判断条件的小例，对算法进行 了划分。通过这种层次化分类，町以更深入地理解离散化的本质，为找寻高效町，f j 的离 散化算法具有非常蕈要的指导意义。 1 3 本文工作 本文首先从理论分析出发，以决策表为处理对象对料糙集和信息论进行了简述，并 根据粗糙集理论代数形式表述介绍了如何运用信息论的基本概念对莉l 糙集理沦进7 j ：史 益、 譬 信息论在粗糙集连续属性离散化中的戍l j 为形象化的表述，并从理论上证明了卡h 糙集的代数表示与信息表示具有一定的等价。阽， 为义章后续算法的提出提供了理论支持。 在深入研究粗糙集与信息论的理论基础上，对连属性离散化进行了广泛而深入的探 讨，提出了针对决策表的两个基于信息论的离散化算法，这两种算法的优点在于首先它 能保证在离散化过程中不改变决策表的不相容性，满足了后续分类学习算法对数据表的 要求；其次，算法运用信息论的判断标准保证了数据在离散过程尽可能地降低信息的损 失；最后，算法满足数据预处理中对算法高效性的要求，具有一定的使用价值。 文章最后选取了几种常见的离散化算法与本文提出的算法进行了比较，运用 d m b e n c h 平台卜的c 4 5 和s v m 对其他算法和本文算法离散化的数据进行了分类学习， 验证了本义算法的有效性。 1 4 文章组织结构 第一章绪论，介绍离散化算法的研究背景和现状；对本文的t 要：1 ：作进行了简述， 并给出整个文章内容组织结构； 第：二章介绍半r 糙集的基本理论，分析了决策表在计算机科学与知识表示领域的苇要 意义，并以决策表作为处理对象对离散化过程进行形式表述。在形式化表述的基础 ：， 给出离敝化处理的流程化描述： 第j t 章介绍信息论的基本概念，分析拳h 糙集理沦的信息化表述与代数形式之间的等 价关系，对料糙集中的主要概念和运算进行了信息化表示； 第四章在粗糙集信息化表示基础上具体给出决策表离散化的信息化表述，定义厂决 策表的不一致率，在此基础上提出了一种基于信息论的决策表连续属性离散化算法，给 出了算法的流程描述： 第五章对基于信息论的离散化算法中使用的判断公式进行详细分析，指出常见暴f 信息论的离散化判断公式在处理数据卜的局限性，为了弥补不足把i ，i e l l i n g e r 偏筹引入剑 决策表的离散化过程中，提高了算法的t j 用性和健壮性； 第八蕈存v c + + 6 0 平台上实现了第1 j q 章和第h 卷提出的两个离散化算法，运用 d m b e n c h 平台下的c 4 5 和s v m 对离散后的数据进行分类谚 别，与其他算法离敞后的 数据分类学列结果进行对比，针对实验结果分析了本文算法的优缺点： 第七章总结全文，展望离散化算法的发展，指出该领域后续的研究方向。 4 辽宁师范人学硕十学位论文 2 粗糙集理论及离散化过程 本章给出粗糙集定义及其相关基本理论，分析决策表在计算机科学和知谚 发现领域 的蓖要作用，给出基于粗糙集的决策表定义，对决策表连续属性离散化进行了形式化表 述。另外给出连续属性离散化的流程化过程，并对如何评估离散化结果作了详细的说明。 2 1 粗糙集定义及其基本理论n 2 3 知识是人类在改造客观世界中获得的经验和认识成果的总和。在j f i 糙集理论中，认 为知识直接与真实和抽象世界中不同的分类模式相联系。根据这些知识( 可理解为客观 事物的小同属性或特征) ，可以对客观事物进行分类。 通常。现实世界中的知识分为三类1 2 3j ：一是说明性知识，它叮以被认为是刈。现实世 界客观客体的描述，即区分客观个体的知识；二：是过程性知识，它实质上是通过利川况 明性知识对客观个体进行分类的知识：三是控制性知识，它是关于如何用过程性知识实 现对客观个体进行分类的知识，也叮以被认为是关于过程性知谚 的分类。综合i 种类型 知识的定义，可以把知识被理解为对客观事物的分类能力，而知识的分类能力可用知谚 系统的集合表达形式来表示。下面就从集合论的角度对粗糙集理论中的基小概念进行表 述。 定义2 1 ：( 知识和概念) 设u 是由目标对象组成的非空有限集合，称为一个论域。 论域u 的任何一个子集x u ，称为论域的一个概念或范畴。空集也是一个 ! ：c 念称 为空概念。论域u 中任何。f 集簇( 概念簇) 称为关于u 的抽象知识，称为知谚 。滏域t 的每。4 个概念( 了集) 表示它的一个信息粒度。 在本文巾，为了简化算法，主要讨论能够在论域u 一卜形成划分或覆盖( 即f i 禽。霭蒋 的分类) 的知识。在集合的概念表述中，划分与等价关系可以视为等同，从数学角度讲， 关系的表示和处理比分类的表示和处理简便得多，因此，通常用等价关系或关系米表示 分类及知识。 定义2 2 ：( 知识库) 给定一个论域u 和u 卜的一簇等价关系s ，称为：元组 k = ( u ，s ) 是关于论域u 的一个知识库或近似审间。 定义2 3 ：( 小可分辨关系) 给定一个论域【厂和u 上的一个等价关系s ，符p s ， 且p a ，则n 尸( p 中所有等价关系的交集) 仍然是论域u f ：的个等价关系，称为尸 上的不可分辨关系，记为i n d ( p ) ，也常简记为p 。而且， v x u ，m 刷d ( 尸) = m p = n x 尺。 信息论在粗糙集连续属性离散化中的廊川 料糙集理论就足以不可分辨关系为基础，通过引入i i 近似集和下近似集，存集合运 算上定义的。 定义2 4 ：( 集合的下近似和上近似) 给定知识库( 近似空问) k = ( u ，s ) ，其中 【，为论域，s 表示论域【上的等价关系簇，则 u 和论域u 上的一个等价关系 r i n d ( k ) ，定义子集x 关于知识尺的下近似和上近似分别为： 垦( x ) = xi ( v x u ) 八( i x 尺x ) ) = u yl ( v y u r ) 八( y 至x ) ， r ( x ) = xi ( v x u ) ( x 】尺x 9 ) ) = u rl ( v y u r ) x ( y x g ) 集合6 ，7 拧( x ) = r ( x ) 一丛( ) 称为x 的尺边界域：p o s 凡( x ) = 丛( ) 称为x 的r 旷域； n e g 肛( x ) = u 一尺( x ) 称为x 的尺负域。显然，尺( x ) = p o s 什( x ) ub n 胛( x ) 。集介x 的l ：近 似、卜近似和边界域可用图2 1 来表示： f ， f r 尺s t t b s e t o f a t t r l b n l e s 图2 1 粗糙集示意图 f i g 2 1t h eg r a p h i c a lr e p r e s e n t a t i o no fr o u g hs e t 有了币域、负域与边界域的概念，就可以对粗糙集进行代数形式的定义： 定义2 5 ： ( 尺一粗糙集)给定论域u 和其上的一个等价关系尺，似【，卒芋 r ( x ) = 尺( x ) ，称集合x 是关于论域u 的相对于知识尺的尺一精确集或r 一可定义集：? i l ： r ( x ) 尺( x ) ，则称集合x 是关于论域u 的相对于知识r 的r 一粗糙集或尺一不町定义 集。 集合的不确定性是由于边界域的存在而引起的，它的边界域越大，起精确性则越低。 为了从量化的角度更准确地表达这一点，引入集合的近似精度的概念。 定义2 6 ：( 近似精度和粗糙度) 给定一个论域【，和u 一卜的一个等价关系尺， w u ，称等价关系尺定义的集合x 的近似精度和粗糙度分别为： 辽j 。师范人学硕十学位论文 吲x ) ：醐，和屏( x ) 小嘣x ) l 尺( 爿) i 近似精度和粗糙度都是用来量化描述粗糙集粗糙程度的变量，对于近似精度来讲， 其值越大，说明粗糙程度越小，越小则粗糙程度越大。拳h 糙度则刚好相反。 上面就是对粗糙集的代数形式的表述，可以看出，这种表述的方式过：r 抽象，直观 性差，对于工程上的使用而言可操作性不是很强。由于同一问题在不同的知识表示下的 算法难度是不同的【2 4 】，所以有必要对粗糙集理论从另外角度来进行定义。本文第三章就 从信息论的角度重新理解知识的概念，给出拳h 集理论中基本概念和运算的信息化表示并 证明了信息形式与代数形式在属性约简角度的等价性。 2 2 决策表及其离散化表述 信息与数据通常以列联表的形式进行保存，其中最典犁应用就是关系数据库管理系 统( d b m s ) ：一般来讲，列联表分为两种，一是带有决策属性的，称为决策表，粥 个就足仅有条件属性而无决策属性的信息表( 无特殊说明时，本文提到的信息表即为尤 决策属性的信息表) 。其中，决策表在计算机科学与知识发现领域占据着霞要的地f 讧， 研究针对决策表的处理有着极为重要的现实意义。 2 2 1 决策表与知识发现 决策表 2 5 1 是用来描述和分析过程化决策情形的一种表状表示，表中符：f 条件状念的 组合( 条件属性) 决定着组行动的执行( 决策属性) 。所有小l j 的情形郜以列的形式 显示在表巾，这样每个可能的情形包含在一列且仅在列中。以满足信息农的完备，陀 和互斥性 1 9 5 7 年，决策表的概念在数据处理的应用中首次被提出1 2 6 】。由于决策表具有良好 的表示性能且易于理解，因而它被运用到计算机程序逻辑的构造巾来代替传统的程序流 程设计图。决策表以一种清晰并且易读的方式表示逻辑概念，它具有易于采用、易。r 一 致性检验的性能，因而被认为足解决程序复杂性递增问题的一种可行方法。自从决策表 诞7 扣以来，它在计算机程序丌发中的应用就一。直是个备受关注的重点。这些年来它作为 结构化程序的组成部分，仍具有重要的作用，并没有冈为师向对象的结构编程概念的 现而使它成为多余。 随着决策表技术的小断发展演变，其应用领域也f i 再仪仅局限于计算机编程， n j 足 向其他具有复杂逻辑的领域扩展。其主要的实际应用领域有f 2 5 l ： 1 、复杂的过程化决策情形的模拟与验证： 7 信息论在粗糙集连续属性离散化中的戍用 2 、信息系统分析、设计和编程； 3 、在会融行业中计算利率和奖金： 4 、制造业中检垒技术说明； 5 、法律法规的检验和可视化； 6 、号家系统中的知识发现。 在知识发现领域，决策表担当着两种角色： 方面，决策表是知识发现研究的一种工具。在建立基于知识表示的系统中，信息 的收集足一个非常重要的问题，并且通常在知识获取过程之中或之后，存在着许多尚需 发现且需要解决的矛盾和不足。同时，知识库的维护并不是一件轻松的工作，会引起容 易被忽略的非一致性。目前许多基于知谚 的系统，对支持验证、修改和进行复杂的控制 提供很少或根本没有保证。基于知识的系统的检验和验证正在受到越来越多的关注【2 1 7 1 。 于决策表具有完备性、一致性和j 下确性的性能，因此在绝大多数情况下，对一般枪验 和验证，决策表技术能够提供帮助，它能使得设计者容易地去检验矛盾、完备性、冗余 性等叫题。在问题的说明中，大多数普通的验证可以用决策表来解决【6 l 。 另一方面，作为记录过程化决策情形的一种数据库，决策表是知识发现研究的一个 对象。一个决策表就是一个决策信息系统，表中包含了大量领域样本的信息。决策表中 的一个样本就代表一条基本决策规则，如果我们把所有的基本规则罗列出来，就可以得 剑一个决策规则集合，但是这样的决策规则集合的实际用处并不大，因为其中的基本规 则没自实用性，只是机械地记录了一个样本的情况。为了从决策表获取适用度高的知谚 ， 以妪好地支持决策分析，我们需要对决策进行完备化、离散化和约简等处理，使得经过 处理的决策表中的个址录就代表类具有相同规律特征的样本，这样获得的决策规则 j 具有较商的适应性1 25 | 。 本义将决策表作为拳h 糙集分析处理的对象，来研究粗糙集理论卜的连续属性离散化 的f u j 题。 2 2 2 粗糙集理论下决策表定义 知识表示是人工智能和智能信息处理的首要问题【2 3 】。基于粗糙集理论的知识表达的 着眼点在于“知识是一种对事物的分类能力 ，这可解释为知识的一种语义定义。出于 计算考虑，需要知识的句法表示，所以文献 2 4 1 提出利用列联表，也就是关系数据表来 表达知谚 ，从前面对决策表的描述性说明，可以知道决策表是一种特殊的关系数据表。 如果把关系数据表看成是粗糙集中的知识表达系统，就能埘关系数据表利用粗糙集 的理论进行符号化定义，其中关系表的行对应要研究的对象( 状态，或过程等) ，关系 表的列埘应刈象的属性，对象信息通过指定对象的各属性值来表示。 辽j 师范人学硕十学位论文 根据前述粗糙集的相关定义与表述，可以扩展出对知谚 表达系统的符号化定义，同 时可以对本文算法的处理对象决策表进行定义。这样可以深刻理解决策表并利h j 粗 糙集的特点来对决策表离散化过程进行控制，保证决策表满足决策表的不相容性彳i 发；匕 变化。 定义2 7 ：( 知识表达系统) 四元组k r s = ( u ，a ，v ，f ) 就是一个知识表达系统，其 中： u 表示对象的非空有效集合，称为论域； a 表示属性的非空有效集合； v 表示全体属性的值域，v = f 7 圪，v o 表示属性口a 的值域： 口月 厂表示u ajv 的映射，称为信息函数。 本章为了分析和处理的方便，使用列联表作为知识表达系统，个表就是一个知识 表达系统。根据前述对列联表的分类，知识表达系统也可分为两类，一类足信息系统( 信 息表) ，即1 、= 含决策属性的知识表达系统：另一类是决策系统( 决策表) ，即含有决策 属性的知识表达系统。 在知识表达系统中k b s 的定义中，令a = cud ( cf 7d = g ) ，其中c 称为条件属性 集，d 称为决策属性集。若d = o ，则知识表达系统为一信息系统( 信息表) ：若d g ，一 则知识表达系统是决策表。由此+ 叮给 h 决策表的形式化定义： 定义2 8 - ( 决策表) 一个决策表是由一四元组d t = ( u ，a ，v ，f ) 构成的知识表达系 统，其中是论域，a = cud 是属性集合，子集c 和d 分别称为条件属性集和决策属 性集，且cnd = a ，c = g ，d o ，v 是属性的取值范刖构成的集合，厂足u a v 的映射，表示论域u 中每个对象在各个属性上的取值。 当i n d ( c ) i n d ( d ) 时，称决策表足相容的( 致的或协调的) ，其中i n d ( c ) ， i n d ( d ) 分别表示条件属性上的不可分辨关系( 或条件等价类) 和决策属性上的不町分 辨关系( 或决策等价类) 。 当c a r d ( d ) 2 时，称决策表为多决策表；当c a r d ( d ) = l 时，称决策表为单一决策表。 一般地，多决策表能够被等价地转化为单一决策表【9 1 ，所以本文中提出的离散化算法都 足基于单一决策表的情形。 另外，为了简化算法的设汁，在本文讨论中假设连续变鼍仪出现在条件属性中，决 策属性值为离散的，该假设不失一般性。则决策表的形式一般如表2 1 所j 。 9 信息论在粗糙集连续属性离散化中的席川 表2 1 决策表的一般形式 t a b 2 it h eg e n e r a lf o r mo fd e c i s i o nt a b l e 其中u = x ，x 2 ，吒 ，c = q ，c 2 ，c ， ，d = d ) ，f ( x ，c ，) = u ，厂( 一，d ) = v ，。 定义2 9 ：( 决策表不一致率) 设r ，是按照决策表d t 中条件属性c ，的属性值相等 确定的等价关系，在此等价关系下的等价类子集簇可表示为 x ，x ：，以) ，且 x 。ux ：u u 以= u ，对于某一个子集x 而言，其实例个数用ixi 表示，其中决策属性 为j ( j = 1 ，2 ，r ( d ) ) 的实例个数为k ，则定义该集合的不一致率为： 弘掣( 2 d - 1 ) ， t ， i f l ， 其中im xi - m a x k ，) ，m y 表示集合x 中最大类的类标号。不一致率是数据预处理 t j 一个很自效的准则，在文献 2 8 1 提出的数据预处理算法中，就使用不一致率来完成离 散化和特征选择，并获得了很好的效果。在本文提出的算法中，使用不一致率来对初始 选出的断点进行优化处理，通过定义一个不一致阈值来使离散化算法在保持高效的基础 j ：对冗余断点进行删除处理。 2 2 3 决策表连续属性离散化表述 有r 决策表的形式化定义，就f 叮以在此基础e 对决策表的离散化过程进行形式化表 示，以理解离散化过程的本质。 没d t 是如前所述的决策表，u = x ix ：，x n ) 是论域，a = c u d ，决策属性的值 域为= 1 ，2 ，( d ) ) 。对条件属性口c ，设其值域圪= 乞，乞】，其中有一组点 乞 c ? c ； 选择断点或邻接区间： 排序完后，+ 卜步就是要选择一个最好的断点来实现分裂，或是选择两个最合适的 邻接区间进行合并。这足离散化过程的核心步骤。在绪论中对离散化算法进行分类时， 也足根捌此步骤所使用的理沦或技术不同来进行划分的。 3 分裂合并： 对于白