（应用数学专业论文）粗糙集理论的扩展及其在贝叶斯网络建模中的应用.pdf

宁夏大学硕士学位论文李晶晶：粗糙集理论的扩展及其在贝叶斯网络建模中的应用 1 摘要 粗糙集理论是一种处理含糊和不确定性信息的数学工具，其基本思想是在保持分类能力不变 的情况下，通过知识约简导出概念的分类规则经典粗糙集模型要求等价关系以及集合之间的完全 包含关系，限制了它的实际应用，因此，模型的扩展研究具有重要实践意义本文介绍了粗糙集的 三种扩展模型，即用条件概率描述包含关系的概率粗糙集模型、用一般二元关系构造基本集的广 义粗糙集模型和基于包含度的变精度粗糙集模型这三种模型分别解决了具有统计特征的信息系 统、基于非等价关系的决策以及系统中存在噪声等问题 综合以上三种对经典粗糙集模型的扩展，本文定义了一种更广泛意义上的粗糙集模型一广义 变精度概率粗糙集模型，并研究了它的性质然后从决策信息系统出发，说明了如何用粗糙集方法 进行属性约简和属性依赖性分析 贝叶斯网络是一种重要的知识发现工具，变量间的依赖关系是确定网络结构的关键，从数据 集中自动构建贝叶斯网络的结构学习算法已经成为目前的研究热点之一分类器是一种较为经典 而且应用广泛的贝叶斯网络模型本文分别利用经典粗糙集和扩展粗糙集模型的属性分析方法建 立贝叶斯网络分类器通过比较，说明利用扩展粗糙集属性分析方法建立的贝叶斯分类器是一种具 有更好容错性和推广性的分类器模型 关键词：粗糙集；信息系统；属性约简；属性依赖；贝叶斯网络；分类器 宁夏大学硕士学位论文李晶晶：粗糙集理论的扩展及其在贝叶斯网络建模中的应用 2 a b s t r a c t r o u g hs e tt h e o r yi su s e dt od e a lw i t ht h ei n f o r m a t i o no fv a g u ea n du n c e r t a i n t y ，t h ef u n d a m e n t a l i d e ao fw h i c hi st oo b t a i nr e d u c t i o no fc l a s s i f i e rr u l e sw i t h o u tr e d u c t i o no fc l a s s i f i e rp e r f o r m a n c e s i n c e t h ei n d i s e e r n i b i l i t yr e l a t i o na n dp e r f e c tp r e d i c t i o na c c u r a c ye x p e c t e di ni n i t i a lr o u g hs e tt h e o r yl i m i t i t sa p p l i c a t i o n s ，t h er e s e a r c ho ne x t e n s i o no ft h em o d e li so fg r e a ts i g n i f i c a n c e t h r e ee x t e n d e dm o d e l s a r ep r o p o s e di nt h i sp a p e r ，t h o s ea r ep r o b a b i l i s t i cr o u g hs e tm o d e lt h a tc h a r a c t e r i z ei n c l u s i o nr e l a t i o n b yc o n d i t i o n a lp r o b a b i l i t y , g e n e r a l i z e dm o d e lt h a tp r o d u c e sp r i m a r ys e t sb a s e do ng e n e r a lb i n a r y r e l a t i o n ，a n dv a r i a b l ep r e c i s i o nm o d e lb a s e do ni n c l u s i o nd e g r e et h e o r y t h e yr e s p e c t i v e l yo v e r c o m e t h ed i f f i c u l t i e so fi n f o r m a t i o ns y s t e mw i t hs t a t i s t i cf e a t u r e s ，n o n e q u i v a l e n tr e l a t i o na n dn o i s e si ni t o nt h eb a s i so fa b o v et h r e ee x t e n d e dm o d e l so fi n i t i a lr o u g hs e t s ，ag e n e r a l i z e dv a r i a b l ep r e - c i s i o np r o b a b i l i s t i cr o u g hs e tm o d e li sp r e s e n t e di nt h i sp a p e r ，a n ds o m ep r o p e r t i e so ft h i sk i n do f a p p r o x i m a t i o no p e r a t o r sa r ed i s c u s s e ds i m u l t a n e o u s l y a n dt h e n ，s h o wh o wt ou s er o u g hs e tt h e o r y t ot a k ea t t r i b u t er e d u c t i o na n da t t r i b u t ed e p e n d e n c eo fad e c i s i o nt a b l e b a y e s i a nn e t w o r ki sa ni m p o r t a n tt o o lo fk n o w l e d g ed i s c o v e r y , a n dt h ek e yt oe s t a b l i s hn e t w o r k s t r u c t u r ei st h ed e p e n d e n c ya m o n gv a r i a b l e s t h er e s e a r c ho fs t r u c t u r el e a r n i n ga l g o r i t h m st h a tc a n c o n s t r u c tab a y e s i a nn e t w o r kf r o md a t a b a s e sa u t o m a t i c a l l yi sap o p u l a ri n v e s t m e n ts p o ta tp r e s e n t c l a s s i f i e ri sas p e c i a la n dw i d e s p r e a d - u s e db a y e s i a nn e t w o r k ，i nt h i sp a t e r ，it r i e dt oe s t a b l i s hb a y e s i a n n e t w o r kc l a s s i f i e ru s e dt h ea t t r i b u t ea n a l y s i sa p p r o a c ho fi n i t i a lr o u g hs e tt h e o r ya n di t se x t e n s i o n r e s p e c t i v e l y b yc o m p a r i s o n ，w ec a nr e a c hac o n c l u s i o nt h a tab a y e s i a nn e t w o r kc l a s s i f i e rb a s e do n e x t e n s i o nr o u g hs e tt h e o r yi so fb e t t e rp e r f o r m a n c eo nf a u l tt o l e r a n c ea n dg e n e r a l i z a b i l i t ya s p e c t s k e y w o r d s ：r o u g hs e t s ；i n f o r m a t i o ns y s t e m ；a t r i b u t er e d u c t i o n ；a t r i b u t ed e p e n d e n c e ；b a y e s i a nn e t - w o r k ；c l a s s i f i e r 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得宁夏大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文巾作了明确的说明并表示 了谢意。 研究生签名：巷渤函时间：力哆年，月沙日 关于论文使用授权的说明 本人完全了解宁夏大学有关保留、使用学位论文的规定，即：学校有权保留送交论 文的复印件和磁盘，允许论文被查阅和借阅，可以采用影印、缩印或扫描等复制手段保 存、汇编学位论文。同意宁夏大学可以用不同方式在不同媒体上发表、传播学位论文的 全部或部分内容。 ( 保密的学位论文在解密后应遵守此协议) 研究生签名：巷晶函 聊签名：孰切 帅：7 肭日 时间：年卜月如日 宁夏大学硕士学位论文李晶晶：粗糙集理论的扩展及其在贝叶斯网络建模中的应用 3 第一章绪论 1 1 课题研究的背景和意义 基于案例推理( e a s e - b a s e dr e a s o n i n g ，c b r ) 1 】是人工智能的一种重要方法，它是一种基于过去 的实际经验或经历( 案例) 的推理，与人类日常的推理活动非常地接近，来自于人类的心智活动管 理者在长期管理过程中积累了大量的经验和事实，这些经验和事实即是案例，利用这些案例对新 的问题进行决策，就是基于案例推理的基本思想当新出现的问题与以往经验重复时，直接利用以 往的成功经验；当新问题与以往经验有差异时，可以检索类似的经验，并对其进行修正以得到新的 结果与传统的推理方式不同，它使用的是案例而不是规则；它通过案例库中相关( 相似) 案例的 回忆给出新的问题解，而不是通过规则的演绎即链式推理得出结论与c b r 技术密切相关的是数 据挖掘( d a t am i n i n g ) 2 ，它将人工智能技术、数据库技术、数理统计技术、可视化技术交叉融合形 成一个具有广泛应用前景的研究领域 数据库的知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d d ) 3 】是从数据集中识别出有效的、新 颖的、潜在有用的以及最终可为人们理解的非平凡的知识的过程k d d 也简称为知识发现或知识 获取等，是在一个广义的数据库中挖掘潜在的规律，它可以使用完全不同的工具，所得到的结果可 以是规则，也可以是关系基于案例库的知识发现一般称为归纳学习，它以分类为工具，得到的结 果一般情况下都表现为规则 1 9 9 9 年，在国际人工智能联合会议上，将k d d 技术与c b r 相结合进行了专题研究，探讨如 何通过知识发现技术获得案例中的隐含知识，从而降低c b r 对领域专家的依赖性，通过知识发现 建立c b r 的知识库，于是产生了基于案例的规则推理( r u l eb a s e dr e a s o n i n g ，r b r ) 在c b r 研究 的推动下，作为案例库的归纳学习成为2 0 世纪末的一个新热点 由于计算机网络技术的发展，案例库越来越庞大面对堆积如山的案例，如何从中精选出有实 用价值的案例、获得案例库在不同程度上的简洁表示，就成了案例推理亟待深入研究的课题2 0 世 纪5 0 年代以后，人们曾尝试用各种方法发现知识，比如神经网络方法、统计学习方法、遗传算法、 支持向量机方法等，但这些方法得到的知识是人们不能直接理解的隐性知识1 9 8 2 年，p a w l a k 提 出了一个重要概念：粗糙集( r o u g hs e t s ) j 4 ，这个概念对于研究关联规则的知识发现有着重要意义 它的基本思想是通过案例库的分类归纳出概念和规则，通过案例库的条件特征变量将案例库分类 而形成概念，并通过生成的概念去研究目标特征，从而得到关联规则分类是一个基本工具，粗糙 集的贡献是给出特征变量的约简与核心，简化了概念的分类特征，也简化了规则的表示这不仅使 概念和规则表述得更加清晰简明，而且使人们对概念和规则有了本质性的认识由于粗糙集是建 立在分类的基础上的，因此它成为归纳学习和信息融合的重要工具粗糙集的另外一个概念是上 近似和下近似，使其对于不能用已有概念表述的新概念给出某种近似表示，从而利用粗糙集得到 的规则具有某种抗干扰性由于用粗糙集方法得到的知识是可以被人们所理解的关联规则，这些关 联规则符合人类的经验，更适合在管理决策中应用，因此2 0 多年来，粗糙集方法得到了迅速发展 粗糙集方法的优点是易于理解，对获得的结果提供直观的解释，而且，绝大多数基于粗糙集理论的 算法适合并行运算 宁夏大学硕士学位论文李晶晶：粗糙集理论的扩展及其在贝叶斯网络建模中的应用4 概括起来，粗糙集方法主要具有以下功能： ( 1 ) 为寻找数据所隐含的模式提供高效的算法； ( 2 ) 寻找变量集的最简子集( 属性约简) ； ( 3 ) 评估数据的重要性； ( 4 ) 生成数据的决策规则集 1 2粗糙集理论的研究现状与发展趋势 粗糙集理论是建立在数据库基础上的，因此数据库的深入研究推动了粗糙集理论的发展相对 于概率统计、证据理论、模糊集等处理含糊性和不确定性问题的数学工具而言，粗糙集理论既与它 们有一定的联系，又有这些理论不可替代的优越性粗糙集理论的主要优势之一就在于它不需要关 于数据的任何预备的或额外的信息而统计学需要概率分布，证据理论需要基本概率赋值，模糊集 理论需要隶属函数它是利用上、下近似集来处理不确定性问题基于粗糙集的分类算法简单，易 于操作，但是利用粗糙集的分类算法所生成的规则有可能不完整在国内外一些学者将粗糙集和其 他的学科如信息论、遗传算法及神经网络等相结合进行研究，得到一些很有价值的成果目前粗糙 集理论研究主要集中在数学性质、粗糙集拓广、与其他不确定方法的关系和互补、多a g e n t 系统中 粗糙集、粒计算( g r a n u l a rc o m p u t i n g ) 、粗糙集的不确定性度量以及粗糙集的有效算法等 在数学性质方面主要研究粗糙集的代数结构与拓扑结构，以及粗糙集的收敛性等问题 5 ，6 】在 粗糙集理论拓广方面的研究主要有：可变精度粗糙集模型【7 ，8 ，9 】、模糊粗糙集模型与粗糙模糊集 模型【1 0 ，l l 】、概率粗糙集模型【1 2 】、基于优势关系的粗糙集模型【1 3 ，1 4 】等，文献 1 5 】研究了粗糙 集与贝叶斯推理的联系随着粗糙集理论研究的不断深入，它与其他数学分支的联系也更加紧密 例如，从算子的观点看粗糙集理论，与之关系较紧的有拓扑空间、数理逻辑、格与布尔代数、算子 观点等；从构造性和集合的观点来看，它与概率论、模糊数学、证据理论、图论、信息论等联系较 为密切粗糙集理论研究不但需要以这些理论作为基础，同时也相应地带动这些理论的发展 当前粗糙集研究面临的主要问题是应用于实际数据分析时，对有噪音数据集的过拟合现象，以 及数据缺失时，如何“不可区分”大数据量，降低计算复杂度具体地讲，目前粗糙集理论的研究 热点主要集中在以下几个方面： ( 1 ) 经典粗糙集理论的扩展研究针对实际问题的需要，将经典粗糙集理论与其它相关学科如 概率论、图论、证据理论等相结合，构造更加一般意义上的粗糙集模型，促使其得到更加广泛的应 用 ( 2 ) 如何应对大数据集问题，降低算法的执行效率和复杂度 ( 3 ) 如何对具有缺失值的数据集进行知识发现由于现实中大量数据集中存在数据缺失的现象， 需要采用某种方法对缺失值进行处理，建立处理不完备信息系统的粗糙集模型 ( 4 ) 属性约简的问题约简的求解是一个n p 难问题，要在令人可接受的时间内获得约简的通 常做法是基于启发式知识的约简方法，国内外学者在这方面做了大量的研究，现在尚不存在一种 非常有效的方法 ( 5 ) 数据的离散化粗糙集只能处理离散化的数据，而现实中存在的一般是连续型的数据，因 宁夏大学硕士学位论文李晶晶：粗糙集理论的扩展及其在贝叶斯网络建模中的应用 5 此，连续数据的离散化变得极为重要目前已经有了些这方面的相关研究，但是这些方法或多或 少都存在一定的缺陷，如何找到一种比较公理化的方法是一个值得研究的课题 1 3 粗糙集理论与贝叶斯网络 贝叶斯网络作为另外一个成功的对不确定性知识进行表达和推理的建模工具，己成为目前处 理不确定性问题重要的技术手段之一利用贝叶斯网络，人们能够在大规模数据中揭示和发现许 多令人信服的概率依赖关系，因此贝叶斯网络建模技术在数据挖掘、模式识别、智能教学、决策支 持和医疗诊断等领域都有广泛的应用前景但是鉴于贝叶斯网络建模是n p 难问题【1 6 】，国内外学 者陆续提出了很多种方法其中贝叶斯结构学习方法通过计算样本数据集上的信息增益和阈值的 关系，决定变量之间的依赖关系并建立网络结构，该方法的缺点是网络弧的方向难以确定，同时， 由于样本数据集中的数据依赖和冗余属性的存在，导致了在增减弧方面产生计算时间复杂度李玉 玲、吴祈宗等人提出把r o u g hs e t 理论融入贝叶斯结构学习中的方法f 1 7 ，1 8 ，1 9 】，无须提供问题所 需处理的数据集合之外的任何先验信息通过属性约简简化贝叶斯网络结构变量，更好满足条件属 性间的独立性限制，降低结构复杂度；通过非决策属性之间的依赖度方向决定弧的方向，所学习得 到的贝叶斯结构能够用于有效地处理不精确或不确定数据情况，进行不完全信息或不精确概率的 预测和分类，而不必限制非决策节点的父节点的个数，有效地克服了在约简集中属性较多时，简单 分类器、t a n 分类器等所存在的无法反映条件属性之间的依赖关系的局限性 1 4 本文的内容与组织 由于经典粗糙集模型中等价关系以及对集合之间完全包含关系的要求，限制了它的实际应用， 本文针对几种不同情况下，对粗糙集模型的扩展进行了探讨，给出一种更广泛意义上的粗糙集模 型一广义概率粗糙集模型最后，介绍了一种重要的知识发现工具贝叶斯网络，并利用扩展的粗糙 集属性依赖分析方法尝试建立一种具有更好容错性和推广性的贝叶斯网络分类器模型通过数值 例子说明了扩展后的粗糙集模型是可行的而且可以适当地提高分类精度 第一章首先介绍了粗糙集理论的背景、起源和发展过程，以及国内外最新研究动态和趋势阐 述了粗糙集和其它相关学科之间相互推动，相互补充的发展过程对粗糙集的基本思想和特点进行 了概括说明 第二章详细阐述了经典粗糙集的基本概念，近似空间上的上、下近似算子以及它们的性质然 后介绍了信息系统的概念，以经典粗糙集理论为基础，给出信息系统属性约简的区分矩阵法，并且 用上下近似算子定义了信息系统中属性的依赖性 第三章指出经典粗糙集模型的局限性，并针对不同情况分别给出相应的扩展方法针对传统 粗糙集理论中依据等价关系进行论域的划分，以及在确定正域时要求集合间严格的包含关系，导 致它在应用中的局限性，本章分别给出用概率描述包含关系的概率粗糙集模型、用一般二元关系 构造基本集的粗糙集模型和基于包含度概念的变精度粗糙集模型，并在这三种模型的基础上，定 义了一种更广泛意义上的粗糙集模型一一般变精度概率粗糙集模型，并探讨其性质和应用 第四章首先介绍贝叶斯网络的相关背景知识，目前的研究现状然后阐述了其概率论基础和 宁夏大学硕士学位论文李晶晶：粗糙集理论的扩展及其在贝叶斯网络建模中的应用 6 基本概念，并简单介绍了几种经典的贝叶斯网络分类器：朴素贝叶斯网络分类器，树增广朴素贝叶 斯网络分类器和无约束贝叶斯网络分类器 第五章以学生信息决策表为例，介绍了如何利用扩展的粗糙集属性分析方法，建立贝叶斯网 络模型通过实验分析说明将粗糙集理论引入贝叶斯网络，可以简化建模过程，确定网络基本结构， 对解决实际问题具有一定帮助 第六章对全文的工作进行了总结，并给出今后进一步的研究方向 宁夏大学硕士学位论文李晶晶：粗糙集理论的扩展及其在贝叶斯网络建模中的应用 7 第二章粗糙集与信息系统 2 1 粗糙集基本概念 通常将研究的对象全体、方案全体或案例全体称为论域，一般地记为 u = 。l ，z 2 ，2 n ， 其中甄表示某个决策对象、决策方案或案例 定义2 1 【1 ju 上的二元关系r 称为等价关系，若满足以下性质： ( 1 ) 自反性：( z ，z i ) r ( z t 扩) ； ( 2 ) 对称性：( 如，巧) r 时，( 巧，承) r ( 翰，巧) ； ( 3 ) 传递性：( 貌，巧) r ，( 2 ：i ，x k ) r ，则( x i ，x k ) r ( 观，巧，2 ：k 矿) 容易证明，u 上的二元等价关系r 必然产生u 上的一个分划，u 上的一个分划由u 上的一 个等价关系冗产生u 上的等价关系与u 上的分划一一对应 定义2 2 【2 0 】设r 是v 上的等价关系，称a = ( 阢r ) 为p a w l a k 近似空间记 【z 】r = 可u ：( z ，y ) r ， 称其为含z 的基本集，也称等价类称 a = u r = 【z j r ：z u 为由r 导出的己厂上的分划 可以证明，盯( 一4 ) = u 。；x k 】r ：x u 是盯代数 定义2 3 1 2 0 l 设( 配r ) 为p a w l a k 近似空间，对于任意x u ，记 型( x ) = z u ：r 冬x ) = u i z 】r ：纠r 冬x ) ， 两耳( x ) = z u ：rnx o ) = u h r ： x n n x o ) ( 2 1 1 ) ( 2 1 2 ) 分别称为x 关于近似空间( 阢冗) 的下近似和上近似 通俗地讲，x 厂的下近似是所有包含于x 的等价类的并，而上近似是所有与x 相交的等 价类的并若a p r ( x ) = 面( x ) ，则称x 为由r 可定义集；反之，若a p r ( x ) 硒( x ) ，则称x 为 由r 不可定义集，通常称为粗糙集 称p o s ( x ) = a p r ( x ) = z u ：m 兄冬x ) 为x 的r 正域；b n ( x ) = 硒( x ) 一a p r ( x ) 为x 的r 边界域；n e c ( x ) = u 一瓦两( x ) = 互u ：m rnx 西，为x 的r 负域x 的正域即下近 似实际上是由那些根据已有知识( 即基本集) 判断肯定属于x 的对象所组成的最大集合，上近似 指的是那些可能属于x 的对象组成的集合，边界域是由那些可能属于也可能不属于x 的对象组 成的集合，负域是那些根据已有知识判断肯定不属于x 的对象所构成的集合 宁夏大学硕士学位论文李晶晶：粗糙墓理论盹扩展厦基壅恩喧斯网终蕉拱兰堂卫8 设近似空间a = ( 以r ) ，x u ，称x 为u 中的一个概念记 叩( r ，x ) = i a p r ( x ) f 垮币f ( x ) i ； p ( r ，x ) = 1 一l a p r ( x ) l l l - 硒p r c x ) l = 1 ，7 ( r ，x ) ( 2 1 3 ) ( 2 1 4 ) 称叼( r ，x ) 为由关系r 定义的概念x 的精度，表示用等价关系r 所产生的基本集来近似表示x 的精确性称p ( 兄，x ) 为集合x 的粗糙度，表示x 能够被基本集所表示的程度，粗糙度越大，则 这种表示越不精确 定理2 1 2 0 l 设( 以r ) 为p a w l a k 近似空间，下近似算子a p t 与上近似算子a - 面p r 满足以下性质： ( 1 ) a p r ( x ) = 一葡资( 一x ) ，i 唾菇( x ) = 一a p r ( 一x ) ； ( 2 ) a p r ( u ) = 硒( u ) = 阢a p r ( o ) = 硒( o ) = 0 ； ( 3 ) a p r ( x n y ) = a p) n，i 唾资( x) = 丽页( x ) i 疆页( y ) ； ( ) _ 竖r ( x )a p r ( y ) ，西霹( x n uy ) 两冠( x ) n u 4 a p r ( xuya p r ( xua p r ( y )y 瓦霹( y ) ； ( 5 ) a p r ( x ) x 砸( x ) ； ( 6 ) 若x 冬y ，贝0a p r ( x ) ga p r ( y ) ，i i 两( x ) 萄5 j f ( y ) ； ( 7 ) a p r ( x ) 2a p r ( a p r ( x ) ) ，a 面p r ( z ) 瓦f ( 筇 ( x ) ) 2 2 信息系统及其属性特征 信息是人类认识客观世界的结果，同时也是人们行为决策的准则通信与网络技术的发展，为 人们提供了大量的信息，这些信息可以是数字、语言，也可以是声音、图像，如何利用网络信息就 成了一个尖锐的问题 2 2 1 信息系统 首先给出信息系统的定义 定义2 4 【1 】称s = ( u ，a ，f ) 是一个信息系统，其中u 为对象集，即 u = z 1 ，z 2 ，) ， u 中的每个元素黝( i 扎) 称为一个对象a 为属性集，即 a = 8 1 ，a 2 ，口m ) ， a 中的每个元素a l ( 1 m ) 称为一个属性f 为矿与a 之间的关系集，即 f = 五：u m ( f m ) ) ， 其中为口l “m ) 的值域 信息系统是数据库的抽象描述，其中关系集，是对象集与属性集之间的纽带，也是知识发现 的信息基础，l ( ) = t ，表达了对象奶具有属性口l = ”的值属性n l 的取值可以是有限离散值， 也可以是连续数值，可以是语言值，也可以是图像和声音 宁夏大学硕士学位论文李晶晶：粗糙集理论的扩展及其在贝叶斯网络建模中的应用 9 如果属性集可以分为条件属性集和决策属性集，要研究两类属性的关系，则需要定义决策信息 系统的概念 定义2 5 【1 1 设s = ( u ，q ，g ) 是一个信息系统，q = a u d ，a n d = 0 ，a = a 1 ，a 2 ，口。) 是 条件属性集，d = d l ，d 2 ，也是决策属性集g = fuh 是u 与q 之间的关系集，其中f 为u 与a 之间的关系集，即 f = ，l ：u _ ( f m ) ， 为a l ( 1 m ) 的值域日为u 与d 之间的关系集，即 h = h i ：u - 嘶( f 后) m 为d l ( 1 k ) 的值域如果属性d l 取有限值，则称( 以q ，g ) 为决策信息系统，也称决策表，通常 记为( 以a ，f d ，日) 对于决策表有单一决策表与多决策表之分，如果决策属性集d 中只包含一个属性，则称决策 表为单一决策表，此时决策表可简记为s = ( 以a ，f d ) ，d ：u 一，否则称为多决策表由于多 决策表可以分解为单一决策表，因此本文只讨论单一决策表 定理2 2 【1 l 设s = ( 以a ，f , d ) 是一个决策信息系统，对于任意b 4 ，记 r s = ( 规，奶) ：l z ( x , ) = ，l ( 吻) ，a l b ) ， r d = ( z ，巧) ：d ( x , i ) = d ( z j ) ) ， 则r b 和凰都是扩上的等价关系记 【x i s = 巧：( x i ，x j ) r b ) ， k 】d = 巧：( 甄，x j ) n d ， 则c r n b = k 】b ：甄u ) 和叫r d = k j d ：甄) 分别构成u 上的分划 定理2 3 1 1 j 设s = ( 阢a ，f ，d ) 是一个决策信息系统，则： ( 1 ) 当b 1 j 免a 时，有r r b ：r b 。，陋 1 a k t 】b 。【z t 】b ，； ( 2 ) r b = nr 。，其中r 。= r 。) ； a 6 b ( 3 ) 扛t 】占= np t 】。，其中【墨】。= 扛 】 。1 口b 如果r a r d ，则称s = ( 阢a ，f d ) 为协调决策信息系统，否则称为不协调决策信息系统 由于在决策信息系统s = ( 阢a ，f d ) 中，r s ( b a ) 和r d 是等价关系，可以构成论域u 的 捌分，因而( 玑r b ) 和( 阢吼) 构成近似空间通常情况下，我们将信息系统s = ( 阢a ，f d ) 中对 应于属性集b 的近似空间( 阢r b ) 的上、下近似算子分别记为硒b 和型b 定理2 4 f 1 1 设s = ( 阢a ，f d ) 为决策信息系统，任意x u ，b a ，则近似空间( 阢r b ) 上 的近似算子w 两p r b 和a p _ _ r b 具有以下性质： ( 1 ) a p r r ( x ) 五妒f ( x ) ； ( 2 ) a p z r r ( 一x ) = 一硒b ( x ) ； 宁夏大学硕士学位论文李晶晶：粗糙集理论的扩展及其在贝叶斯网络建模中的应用 l o ( 3 ) 若b 1 岛a ，则型口。( x ) 型现( x ) ，硒b 。( x ) 2 硒8 ：( x ) ； ( 4 ) 若xa y = 谚，则型b ( x ) aa p r b ( y ) = o ，但面b ( x ) n 硒b ( y ) = 0 一般不成立 2 2 2 信息系统的属性约简 一般来说，在信息系统中描述不同对象特征的属性集是较大的，但是对于信息系统分类的知 识发现来说有些属性并不总是必要的有些属性是绝对不必要的，去掉这种属性并不影响分类的知 识发现；而有些属性是绝对必要的，去掉这种属性必然会影响分类的知识发现还有一些属性是相 对必要的属性，它们可能与其他一些属性联合起来确定分类的知识发现，但是也存在另外一种不 需要这些属性的属性集也可以确定知识发现属性约简就是要在属性集中寻找一个最小的属性集， 它能完全确定知识发现，也即由这个最小属性集确定的分类知识与用全体属性集确定的分类知识 是相同的同理，对于决策信息系统来讲，不同的条件属性对于决策类来讲作用是不同的决策信 息系统的属性约简就是在条件属性中寻找一个最小的属性集，可以完全确定决策类，使得相同的 决策可以通过更少量的条件得出 定义2 6 1 1 l 设s = ( 玑a ，只d ) 是决策信息系统，召a ，若r b = r a 且对于任意b b ， r b p ，r a ，则称b 为s = ( 阢a ，f d ) 的约简 若r b = r a ，则u r b = w 冗a ，从而用属性集b 对厂的分类与用属性集a 对u 的分类完 全相同 一般说来，信息系统的约简集不是唯一的，用 取：k r ) 表示信息系统s = ( 阢a ，f ) 的所有 约简集则称c = ub k 为信息系统s 的核心一般地，核心不一定构成约简，若核心非空，则任何 七r 约简集都包含核心，且核心中的元素是任何约简都必须的，因而是绝对必要属性k = ub k c 是 k 相对必要属性，它仅出现在某些约简集中而j = a ub k 是绝对不必要属性，它不出现在任何约 七 简中 定理2 5 1 1 1 协调决策信息系统的约简总是存在的 定义2 7 【1 l 设( 矾a ，只d ) 为协调的决策信息系统，等价关系r a 在u 上的分划为u r a = c t ：i t ) ，称 r d ( g ，g ) ： a k e a ：f k ( a ) o ) ) ，烈a ) d ( o ) ia ，d ( c i ) = d ( q ) 为q 与。关于d 的可辨识属性集，称 d = ( d ( g ，q ) ：t ，j t ) 为决策信息系统( 以a ，f ，d ) 的可辨识属性矩阵 定理2 5 保证了协调决策信息系统属性约简的存在性，以下给出协调决策信息系统属性约简 的辨识矩阵方法 定理2 6 2 0 设( 阢a ，f , d ) 为协调决策信息系统，则 ( 1 ) 对于b a ，使口nd ( a ，q ) 毋成立当且仅当尺8 吼； 宁夏大学硕士学位论文李晶晶：粗糙集理论的扩展及其在贝叶斯网络建模中的应用 1 l ( 2 ) 对于b a ，r b r d 当且仅当对于任意d a ，口nd = o ，必有dg7 3 ； ( 3 ) a 是决策信息系统的核心元素当且仅当存在x i ，巧u ，使d d ( c f ，q ) = o ) 证明( 1 ) 假定r b r d ，则当d ( g ) = d ( q ) 时，有d ( c t ，g ) = a 于是b n d ( c _ f ，0 ) o 而 当d ( g ) d ( c j ) 时，则存在x i q 和巧o ，使奶引x i d 由于r b r d ，因此【铂】b k 】d 于 是巧gi x , i s ，从而必存在a t b ，使五( 以) f t ( z j ) 这样就有a l d ( a ，伤) ，即b n d ( c t ，o ) 毋 反之，对于任意瓤u ，记【x i a = g 对于任意即gb 】d ，记b 】a = 伤，则d ( g ) = d ( x i a ) d ( x j l a ) = d ( g ) ，从而由b n d ( g ，c j ) o 知，存在口l b ，使s z ( z i ) 五( ) ，这说明qgk 】b ， 于是【x d b 【戤】d ，即r b r d ( 2 ) 由( 1 ) 知r b r d 当且仅当d 秒时，口nd 口，则得证。 ( 3 ) 设a 为决策信息系统的核心元素假如包含a 的任何可辨识属性集中至少有两个元素，令 b = u ，f ( d ( g ，0 ) 一 o 】) ，则bnd ( a ，g ) o ( v i ，j t ) 从而由( 1 ) 知r b 吼，于是存在 d b 使得c 是决策信息系统的约简显然，agc ，这与a 是核心元素矛盾 反之，若存在g ，q ，使d ( g ，q ) = n ) 若l a l = 1 ，即a = n ) ，则口就是核- t ：- 元素现 假设i a l 1 ，欲证a 属于所有约简集，只须证冠4 一r d 不成立即可，即只须证存在x i 使 k 】 一gk k 事实上，由于d ( g ，g ) = o 】，因此d ( q ) d ( o ) ，即存在戤g 和吻岛， 使奶gb 】d ，但是由d ( g ，q ) = 口) 可知k 】a 一= b 】a 一 。 ，从而叼k j 一 。 ，于是 k 1 a 一 o 1 d 不成立因此，a 是核心 由定理可知，满足此定理( 1 ) 或( 2 ) 的在集合包含意义下的最小集合b 即是约简 例2 1 求表2 1 所示决策表的约筒 表2 1 一个决策表 u r a = c 1 ，c f 2 ，c 3 ，c 4 ，c 5 ) = z l ，x 3 ，z 9 ) ， z 2 ，；9 7 ，x m ， z 4 ) ， z 5 ，z 8 ) ， ) ) 吖r d = d 1 ，d 2 = “z 1 ，z 3 ，z 6 ，黝 ，t z 2 ，a 9 4 ，2 ：5 ，z 7 ，x 8 ，z l o ) ， 由于r a 奶，所以该决策表是协调决策信息系统由定义2 7 可得该决策信息系统的辨识矩 宁夏大学硕士学位论文李晶晶：粗糙集理论的扩展及其在贝叶斯网络建模中的应用 1 2 阵如表2 2 所示 表2 2 决策表的辨识矩阵 c 1q伤a岛 g aa a l ，0 2 ) 口1 ，a 3 ，0 4 ) a c 2 aaaa n 1 ，g 2 ，口3 ) 岛 a l ，口2 ， aaa a e 4 n 1 ，a 3 ，a 4 ) aaa 0 3 ) g a a l ，a 2 ，n 3 ) a 0 3 ) a 根据定理2 6 可知b 1 = 口1 ，0 3 ，或玩= 0 2 ，幻) 为该决策信息系统的约简 对于约简集b 1 = ( a l ，0 3 ) ，得到以下几条决策规则： ( a l ，3 ) ( a 3 ，1 ) _ ( d ，2 ) ； ( 0 1 ，1 ) a ( a 3 ，4 ) _ ( d ，2 ) ； ( a l ，1 ) ( a 3 ，2 ) _ ( d ，1 ) ； ( n l ，2 ) a ( a 3 ，3 ) 一( d ，1 ) v ( d ，2 ) 对于约简集b 2 = 0 2 ，0 3 ) ，得到以下几条决策规则： ( a 2 ，1 ) a ( n 3 ，3 ) _ ( d ，1 ) ； ( a 2 ，2 ) a ( a 3 ，1 ) 一( d ，2 ) ； ( a 2 ，2 ) ( a 3 ，3 ) 一( d ，2 ) ； ( a 2 ，1 ) a ( a 3 ，4 ) _ ( d ，2 ) ； ( a 2 ，1 ) a ( a 3 ，2 ) _ ( d ，1 ) 所得到的决策规则与约简前是一致的，可见约简集不改变原来属性集的分类能力 不协调决策表的属性约简相对复杂，而且方法众多，但是可以和协调决策表的属性约简统一 于以下辨识矩阵方法： 定义2 8 2 1 1 设决策信息系统s = ( 以a ，f ，d ) ，c ，dsa ，( 以) 和( 阢r d ) 为近似空 间由属性集c 产生的划分为u p c = a ，q ，) ，属性集d 产生的划分为u r d = ( d 1 ，d 2 ，d k 记 k七m p o s o ( d ) = up o s c ( d j ) = u u g ：g 功】) ， ( 2 2 1 ) j = lj = li = l 称其为属性集d 在属性集c 下的正区域p o s c ( d ) 表示那些用属性集c 进行的划分叫r c 所描 述的对象中，能够确切地划入w r d 类的对象集合 宁夏大学硕士学位论文李晶晶：粗糙集理论的扩展及其在贝叶斯网络建模中的应用 1 3 定义2 9 【2 2 1 设决策信息系统s = ( 阢a ，f d ) ，其辨识矩阵是一个礼x 札阶方阵，元素为 a ( 毛可) 其中a + ( z ，y ) 由以下方法确定： 任意z ，y u 若满足 ( 1 ) z p o s a ( d ) 且ygp o s a ( d ) ； ( 2 ) zgp o s a ( d ) 且y p o s a ( d ) ； ( 3 ) z ，y p o s a ( d ) 且，ygi n d ( d ) 三种情况之一，则a + ( z ，可) = a i 厶p ) ，口( 可) ) ；否则4 ( z ，y ) = o 定义2 1 0 1 2 2 l 设山= ( z ，y ) ：a ( z ，可) d ，称 + ( s ) = v a + ( z ，可) a ( z ，u ) e a o = v o ：口k a + ( z ，y ) ：a + ( z ，y ) 。4 0 ，( 2 2 2 ) 为决策表的区分函数 定理2 7 2 2 设决策表s = ( 以a ，ed ) 的区分函数+ ( s ) 的极小析取范式为 =pm k s = l m v k = 1) = l 八钆1 i 记 b k = a s ：s = 1 ，2 ，g 七) ， 则 b k ：k = 1 ，2 ，p ) 是所有约简形成的集合 2 2 3 信息系统的属性依赖性 经过粗糙集方法对信息系统进行属性约简后，删除了冗余属性，消除了属性闻的完全依赖关 系，但约简集中的属性间还可能存在部分依赖关系，下面给出属性依赖的定义： 定义2 1 1 【2 1 1 设决策信息系统s = ( 以a ，e d ) ，g d a ，属性集d 对c 的依赖度定义为 弦( d ) = i p o 丽s c ( 一d ) ( 2 2 3 ) 依赖度 y c ( d ) 表示在属性集c 下能够确切划入u r d 的对象占论域u 中总对象数的比率， 反映了属性集d 对属性集c 的依赖程度 例2 2 例2 1 的决策表中，设c = 0 1 ，0 2 ) ，d = n 4 ) ，由它们产生的u 的划分分别为 u p c = 。1 ，z 3 ，知) ， z 2 ，z 7 ，x i o ， z 4 ) ， x 5 ，z 6 ，z 8 ， u r d = z l t x 3 ，9 9 4 ，z 9 ， z 2 ，x 5 ，z 6 ，z 7 ，2 ；8 ，z l o ) 。 根据定义2 1 1 ， w ( 驴 i