（管理科学与工程专业论文）基于粗糙集的流网络和决策算法研究.pdf

独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得( 注：如 没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示谢意。 学位论文作者签名： 王洙帛 导师签 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权堂撞可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在 解密后适用本授权书) 学位论文作者签名：王】肇钵 签字日期：2 0 0 8 年岁月2 7 日 导师签字退压1 签字日期：2 0 08 年妒夕日 山东师范大学硕士学位论文 基于粗糙集的流网络和决策算法研究 摘要 从数据集中对对象进行归纳学习和分类是人工智能中很重要的领域，旨在发 现数据中隐藏的、未知的、潜在有用的知识，本质是在大的数据集合中寻找数据 间的规则及普遍模式。近几年来，已经研究了很多基于归纳学习的理论，发展了 许多技术来处理不精确的数据，其中最成功的是粗糙集理论，它是关于数据推理 的一个强大的工具，已经被成功地应用于机器学习、知识获取、模式识别和决策 支持系统等领域。 粗糙集理论是1 9 8 2 年由波兰数学家z p a w l a k 教授提出来的，它是一种处理 不完整、不确定信息的新型数学工具。由于粗糙集理论是利用数据集上的等价关 系对知识的不确定程度进行度量，而无需提供所需处理的数据集合之外的任何先 验信息，这样就避免了对知识的主观评价所带来的误差。所以利用粗糙集理论进 行决策研究具有十分广泛的应用前景。 属性约简和属性值约简是利用粗糙集理论从决策表中挖掘决策规则的基础， 挖掘决策规则是粗糙集理论的重要研究领域之一。本文根据条件属性的重要度和 区分矩阵来进行条件属性约简，找出有效约简。同时定义了决策表的不一致度， 并根据条件属性重要度来进行属性值约简，在保持决策表不一致度不增加的前提 下挖掘出决策规则，该决策规则集满足独立性、覆盖全域性、可接受性和一致性， 即决策规则集为决策算法。本文还对粗糙集流网络进行了研究，并将粗糙集流网 络、决策算法和贝叶斯定理结合了起来，最后构建了基于粗糙集和贝叶斯定理相 结合的风险规则挖掘模型。 本文主要做了以下工作： ( 1 ) 研究了粗糙集理论的基本知识，介绍了粗糙集理论的几个核心概念，提 出了条件属性重要度和决策表不一致度的概念，为以后的属性约简和决策算法的 挖掘奠定了基础。 ( 萄详细讨论了决策算法的性质，通过研究发现，决策算法满足全概率公式 和贝叶斯定理。通过基于粗糙集的贝叶斯公式，只需要计算决策规则的强度，然 后再计算每条决策规则的置信度和覆盖度即可，大大简化了计算的过程。 ( 3 ) 在区分矩阵的基础上，利用条件属性重要度进行属性约简，在保证不改 变决策表不一致度的前提下，给出了一种基于粗糙集的决策算法挖掘方法。该方 法提取的决策算法是由决策表生成的覆盖所有对象的最小规则集。这也是本文的 一个创新点。 基于粗糙集的流网络和决策算法研究 ( 4 ) 研究了一种新的决策进程的数学模型一粗糙集流网络，整个流网络就是 一个决策算法，流网络满足贝叶斯公式，还研究了流网络的性质，并且把分支中 强度、置信度和覆盖度的概念扩展到了路径和连接当中。 ( 5 ) 利用粗糙集对数据进行约简，利用贝叶斯定理训练约简后的数据，将粗 糙集理论和贝叶斯定理相结合，运用到i t 项目的风险管理中，构建了基于粗糙 集与贝叶斯定理相结合的风险规则挖掘模型。 利用粗糙集理论进行决策分析还有许多问题值得探讨，本论文的研究肯定还 有许多不完善的地方，相关工作还有待进一步研究。 关键词：粗糙集；决策算法；流网络；数据挖掘；贝叶斯定理 分类号：1 p 1 8 2 山东师范大学硕l 学位论文 r e s e a r c ho ff l o wn e t w o r ka n dd e c i s i o na i g o r i t h m b a s e do nr o u g hs e t a b s t r a c t i n d u c t i v el e a m i n ga n dc l a s s i f k a t i o n o b j e c lf 硒md a t as c ta r cv e 巧i m p o f t a n t a r e a si l la r t i f i c i a li n t e l l i g c n c e ，i no r d e rt 0d i s c o v e rh i d d e n ，u n k n o w n ，p o t e n t i a l l yu s e f u l l 【i l o w l e d g ei nt h ed a t 如a n dt 0s e a r c ht h em l ea n d t h eg e n e r a lm o d ef 幻mt h el a 唱ed a t a s e ti i le s s c n c e i nr e c e n ty e a r s ，al o t0 ft h e o r i e sb a s e d0 ni n d u c t i v el e 锄i i l gh a v eb e e n r c s e a r c h e d ，a n dan u m b e ro ft e c l l i l i q u e s 缸ed e v e l o p e dt od e a lw i t hi m p r e c i s ed a t a 1 1 l em o s ts u c c e s s f u l t e c h n i q u ei sr o u g l ls e tt h e o 彤w h i c hi sap o w e r f u l t o o la b o u td a t a r c a s o n i n g r o u g l ls e tt h e o r yh 弱b e c ns u c c e s s f l l l l yu s e di nm a c h i n el e a m i n 岛 k n o w l e d g ea c q u i s i t i o n ，p a t t e mr e c 0 弘i t i o na n dd c d s i o ns u p p o r ts y s t e m s ，e t c i b u g hs e tt h e o r ) rt h a tw a sp u tf o r w a r db yp o l ez p a w l a ki n1 9 8 2i san e wd a t a 雒a l y s i st h e o r yo f 勰a l y z i n ga i l dd e a l i n gw i t h 蛐c e n a i na n di n c o m p l e t ed a t a i tm a k e s u s eo ft h ee q u i v a l e n c er e l a t i o n st 0m e a s u r ct h ei n d e t e m l i n a t i o nd e 伊e eo fl 【i l o w l e d g e 卸di td o c s n tn e e d 彻yl 【n o w l e d g c0 u t s i d e0 ft h ed a t aw h i c hn e e d st 0b ep r o c e s s e d 1 1 l e r e f 0 他t h ee r r o rc a u s e db ys u b j e c t i v ea p p r a i s a lc a i lb ea v o i d e d s ot h es t l l d i e s0 f d e c i s i 一m a l 【i n gb 硒e do nr o u g l ls e tt h e o r ) ，h a v ew i d e s p r e a da p p l i c a t i o np r o s p e c t r e d u c t i o no fa t t r i b u t e sa i l dr e d l l c t i o n0 fa t r i b u t v a l u ea r et h eb a s eo fm i n i n g d e c i s i o nn l i e s 舶md e c i s i o nt a b l eu s i n gr o u g h 驼tt h e o 锄dm i l l i n gd e c i s i o nm l e si s o n eo ft h em o s ti m p o n a n tr e s e a r c hf i e l d si nr o u g hs e tt h e o r y b a s e do nt h ei m p o r t a n t d e g r e eo fc o n d i t i o na t t m u t e sa n dd i s c e m i b l em a t r i x ，a i le 骶c t i v ec o n d i t i o na t t 曲u t e s r e d u c t i o ni so b t a i n e d an o t a t i o no fi n c o n s i s t e i l c yo fd e c i s i o nt a b l ei s 百v e n ，t h e a t t r i b u t e s v a l u er e d u c t i o ni sg o tb yt h ei m p o r t a n td e 擎e e0 fa t t r i b u t e s 觚dd e c i s i o n n l l e sa r eo b t a i n e di nt h ep r e m i s eo fm a i n t a i n i n gt h ei n c o n s i s t e n c yo ft h ed e c i s i o nt a b l e u s i i l gt h i sm e t h o d ，t h es e to fd e c i s i o nm l e sw h i c ha r em i n e df 幻md e c i s i o nt a b l e s a t i s f i e st h ep r o p e r t i e so fi n d e p e n d e n t ，c o v e r i n gu n i v e r s e ，a d m i s s i b l e 如dc o n s i s t e n c y ， t h a ti s ，i ti sad e c i s i o na l g o r i t h mi nt h ed c c i s i o nt a b l e a n d ，r o u 曲s e tf l o wn e m o r ki s s t u d i e di i lt h i sp a p e r ，w h i c hc o m b i l l e sr o u g l ls c tn o wn e 觚o r k ，d e c i s i o na l g o r i t l u na i l d b a y e s t h e o r e m l a s t l y am o d e lo fr i s km l em i n i n gb a s e do nr o u g l ls e t 锄db a y e s t h e o r e mi s 舀v 1 1 l ew o r k sd o n ei l lt h ep a p c r 缸e 勰f o l l o w s ： ( 1 ) n ee l e m e n t a r yh o w l e d g e o fr o u g l ls c tt h e o r yi ss t u d i e d ，s e v e r a l r cc o n c e p t s 3 基于粗糙集的流网络和决策算法研究 o fr o u 曲s e tt h e o r ya r ei n t 刚u c e d ，a n dt h ec o n c e p to ft h ei m p o n a n td e 笋e eo f c o n d i t i o na t t r i b u t ea n dt h en o t a t i o no fi n c o n s i s t e n c yo fd e c i s i o nt a b l ea r eg i v e ni nt h i s p a p e r w h i c hh a v el a i dt h ef o u n d a t i o nf o f t h er e d u c t i o n0 fa t t r i b u t e sa n d t h em i n i n g0 f d e c i s i o na l g o r i t h mi nt h el a t e l ( 2 ) t h ep r o p e r t i e so fd e c i s i o na l g o r i t h ma r ed i s c u s s e di nd e t a i li nt h i sp a p e l t h r o u 曲t h er e s e a r c h ，w ef i n dt h a td e c i s i o na l g o r i t h ms a t i s f i e st h et o t a lp r o b a b i l i t y t h e o r e ma n dt h eb a y e s t h e o r e m b yu s i n gt h eb a y e s t h e o r e mb a s e do nm u g l ls c t ，w e o n l yn e e dt oc a l c u l a t et h es t r e n 舀ho ft h cd e c i s i o nm l e ，锄dt h e nc a l c u l a t et h ec e r t a i n t y f a c t o r 卸dt h ec o v e r a g ef k t o ro ft h ed e c i s i o nn l l e t h ec o m p u t a t i o nc o m p l e x i t yi s s i m p l i f i e d 黟e a t l y ( 3 ) r e d u c ea t t r i b u t eb yu s i n gt h ei j l l p o r t a n td e 酉e eo fc o n d i t i o na t t r i b u t ei nt h e d i s c e m i b l em a t r i x am e t h o d0 fr o u g hs e tb a s e dd e c i s i o na l g o r i t l l i i lm i n i n gi s 百v e ni n t h ep r e m i s eo fn o tc h a n 酉n gt 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 e n ea 1 9 0 r i t h mw h i c h i sm i n e di nt h i sm e t h o di st h es m a l l e s ts e to ft h ed e c i s i o nm l e sw h i c hc o v e ra uo b j e c t s r n l i sm e t h o di sa l s oav e 巧i m p o n 锄ti n n o v a t i o no ft h i sp a p e l ( 4 ) r o u 曲s e tn o wn e 锕o r kw h i c hi s an e wm a t h e m a t i c a lm o d e lo fd e c i s i o n p r o c e s s e si ss t u d i e d t l l ew h o l en e 铆o r kr e p r e s e n t sad e c i s i o na l g o r i t h m a n dt h e p r o p e n i e so fn o wn e 铆o r k 缸er e s e a r c h e d t h ec o n c e p t so fs t r e n 昏h ，c e n a i n t y 觚d c 0 v e r a g ef a c t 0 娼a e x t e n d e dt 0t h ep a t h 柚d c o 衄e c t i o n ( 5 ) t h ed a t ai sr e d u c e db yr o u 曲s e t 柚dt h ed a t aw h i c hi sr e d u c e di st r a i n e db yt h e b a y e s t h e o r e m am o d e lo fr i s kn l l em i i l i n gb a s e do nr o u g hs e t 卸db a y e s t h e o r e mi s 西v e n t h em o d e lc o m b i n e sr o u g hs e ta n db a y e s t h e o r e m 觚di sa p p l i e di l lt h er i s k m a n a g e m e n to f t h en p r o j e c t m a i l yp r o b l e m si nt h ed e c i s i o n 锄a l y s i sb yr o u g hs e tt h e o r yn e e dt ob ed i s c u s s e d a n dt h e r ea r em a i l yp r o b l e m si nt h es t u d yo ft h i sp a p e l1 1 l ea c c o r d i n gw o r kw i l lb e d o n ei nt h ef u t u r e k e yw o r d s ：r o u g l ls e t ；d e c i s i o na 1 9 0 r i t h m ；f l o wn e 铆o r k ；d a t am i n i n g ；b a y e s t h e o r e m c l a s s i f i c a t i o n ：t p l 8 4 山东师范大学硕上学位论文 1 1 本文研究背景 第1 章引言 信息是决策的基础，如何从大量的、不确定的、模糊的甚至是不完整的信息 中获得有用的信息，即知识，是当前人工智能、数据挖掘及智能决策等领域研究 的热点。由波兰科学家z p a w l a k 教授于2 0 世纪8 0 年代初提出的粗糙集理论为 解决此类问题提供了有力的数学工具。 粗糙集理论是一种新型的处理不完整性和不确定性的数学工具【1 1 。租糙集理 论具有一些独特的观点。这些观点使得粗糙集特别适合于进行数据分析。如【捌： 知识的粒度性。粗糙集理论认为知识的粒度性是造成使用已有知识不能精确 地表示某些概念的原因。通过引入不可区分关系作为粗糙集理论的基础，并在此 基础上定义了上下近似等概念，粗糙集理论能够有效的逼近这些概念。 新型成员关系。和模糊集合需要指定成员隶属度不同，粗糙集的成员是客观 计算的，只和已知数据有关，从而避免了主观因素的影响。 采用粗糙集理论作为研究知识发现的工具具有许多优点。粗糙集理论将知识 定义为不可区分关系的一个族集，这使得知识具有了一种清晰的数学意义，并可 使用数学方法进行处理。粗糙集理论能够分析隐藏在数据中的事实而不需要关于 数据的任何附加信息。其核心思想是在保持分类能力不变的前提下，通过属性约 简和属性值约简，推导出问题的分类或决策规则。该理论建立在经典的集合论的 基础之上，运用分类手段对数据进行处理，可以有效地进行信息处理，挖掘有用 信息，从而简化决策规则，提高分类效率。粗糙集的主要优势在于它不需要关于 数据的任何预备的或额外的信息瞄l 。粗糙集理论现在已经在数据挖掘、模式识别、 机器学习、专家系统以及决策分析等领域得到了广泛的应用，并取得了良好的效 果。 利用粗糙集理论进行数据挖掘，获取决策规则，最重要的一点就是基于粗糙 集的属性约简和属性值约简。通过约简操作，可以降低属性的维数，挖掘出适于 决策支持的决策算法，是粗糙集理论的最重要应用之一，基于粗糙集理论挖掘出 的决策规则比较精练且便于储存和使用i 矧。国内学者对利用粗糙集从决策表中挖 掘分类规则或决策规则进行了很多的研究，文献【3 1 】、【3 3 】、【3 6 】、【4 3 】、【4 4 】、 f 4 5 】、【4 6 1 分别进行了阐述，本文在决策表不一致度、条件属性重要度和决策算 法的基础上，提出了一种新的决策规则的挖掘方法，该方法挖掘出的决策规则的 集合是由决策表生成的能够覆盖所有对象的最小规则集。 基于粗糙集的流网络和决策算法研究，定义决策算法和流网络的概念并分析 研究了决策算法、流网络和贝叶斯定理之间的关系。决策算法满足贝叶斯定理， 5 基于粗糙集的流网络和决策算法研究 而又优于贝叶斯定理。这可以使我们以一种新的视角来认识贝叶斯定理，并且可 以给出贝叶斯规则在数据分析中新的应用。用流网络来分析研究决策算法，给出 了决策算法分析的一种新数学模型。用流网络来表述决策算法，并根据相应的流 网络中的流量分配来表示决策算法的一些基本性质。 1 2 粗糙集理论研究现状 粗糙集理论是波兰数学家z p a w l a l 【于1 9 8 2 年首先提出的，该理论刚刚被提 出时并未受到国际智能研究领域的广泛重视，当时的研究也仅限于波兰等几个东 欧国家。到了9 0 年代，数据仓库和数据挖掘逐渐引起了广大学者的重视，在这 种情况下，粗糙集理论被广泛认识并迅速发展起来幽j 。 1 9 9 1 年z p a w l a k 发表了专著r o u 曲s e t s ：t 1 l e o r c t i c a l 舡p e c t so fr e a s o n i n g a b o u td a t a 【，奠定了粗糙集理论的基础，从而掀起了粗糙集的研究热潮。1 9 9 2 年在波兰召开了关于粗糙集理论的第一届国际学术会议，这次会议着重讨论了粗 糙集理论的基本思想及其应用。以后每年都召开一次以粗糙集理论为主题的国际 研讨会。1 9 9 3 年在加拿大召开了第二届国际粗糙集与知识发现研讨会，这次会 议积极推动了国际上对粗糙集应用的研究。由于这次会议正值知识发现成为热门 研究话题，一些著名知识发现学者参加了这次会议，并且提出了许多应用粗糙集 理论的数据挖掘的方法与系统，至此，粗糙集理论与知识发现和数据挖掘紧密地 联系在了一起。1 9 9 4 年在美国召开了第三届国际粗糙集与软计算研讨会，这次 会议广泛地探讨了粗糙集与模糊逻辑、神经网络、进化计算等的融合问题。1 9 9 5 年a c mc o m m u n i c a t i o n 将粗糙集列为新浮现的计算机科学的研究课题。1 9 9 9 年 在日本召开了第七届粗糙集、模糊集、数据挖掘和粒度软计算国际会议，主 要阐述了当前粗糙集、模糊集的研究现状和发展趋势。2 0 0 0 年在加拿大召开了 第二届粗糙集和计算的当前趋势学术会议。2 0 0 1 年5 月第一届中国粗糙集理论 与软计算学术研讨会在重庆举行，以后每年举办一次。2 0 0 6 年7 月首届粗糙集 与知识技术国际会议在重庆召开。当前许多重要的国际学术会议都把粗糙集理论 的研究列入主要内容之一1 3 2 j i 删。 近几年来，粗糙集理论已经应用于机器学习、决策支持、知识发现、专家系 统、模式识别等领域【2 7 j 。国内外学者也对粗糙集理论的模型进行了拓展，例如， 文献【1 0 】、【1 2 】、【1 4 】、【1 9 】、【2 0 】、【3 7 】、【3 8 】、【4 2 】和【5 0 】等。目前对粗糙集理 论的研究主要集中在求解属性的最小约简、较小约简和最简规则集。粗糙集有效 算法方面的研究包括如何求等价类、上近似、下近似、正区域、约简和核等等。 现在国际上已经研制出了一些粗糙集工具应用软件，如l d r 是由加拿大 r e 盟i a 大学研制开发的基于可变精度粗糙集扩展模型的数据库知识发现k d d 系 6 山东师范大学硕士学位论文 统。l ( d d r 系统曾成功应用于医学数据分析和电信市场的决策分析等。u ! r s 是美国勋n s a s 大学开发的基于粗糙集的实力学习系统，u ! r s 系统曾用于医学研 究、气候预测和环境保护等。r o u 曲d a s & r o u g l lc l a s s 是波兰p o z n a n 工业大学 开发的基于粗糙集的k d d 决策分析系统。r o u g l le n o u 曲是挪威1 r 0 1 1d a t ah l c 公司开发的，它包括数据输入、预处理、编辑、生成可辨识矩阵、集合近似、约 简、生成规则、预测和分析功能。r o s e t t a 是波兰华沙大学和挪威科技大学联合 开发的基于粗糙集的l ( d d 决策分析系统。该软件目前应用较广，r o s e t t a 可以 处理多种格式的数据，如文本和数据库等，这些数据以决策表的形式存在于 r o s e t t a 系统中。当决策表成功装载入p r o j e c t 后，系统使用粗糙集理论逐步分析 数据，最后得到决策规则。除了以上介绍的几种系统外，还有一些其它系统，例 如加拿大r e d u c ts y s t e mh l c 开发的d a t al o 西c 瓜，中科院计算技术研究所开发的 l 江t ，南京大学研制的k n i g l l t 等【4 9 l 。 粗糙集的研究在我国虽然起步晚，但发展较快。其研究主要集中于理论方面， 成功开发及应用的实例几乎没有。而关于流网络和决策算法的研究目前在国内还 几乎是一片空白。 1 3 粗糙集在数据挖掘中的应用 粗糙集理论的应用十分广泛，例如，文献【9 】、【1 3 1 、【1 8 1 、【2 1 1 、【2 2 1 、【2 9 1 、 【3 0 】和【4 7 】等分别将粗糙集应用到冲突分析、规则学习、多目标决策分析、区间 值信息系统、区间值模糊信息系统、软件开发风险评估、证据推理和化学药品的 合成中，近几年来，粗糙集理论在数据挖掘方面的应用倍受关注，并且粗糙集理 论的应用研究得到了长足发展。这里从几个方面简述有代表性的应用【2 3 1 。 数据缩减与规则生成。( k 0 h a v i 勰df i r a s c a ，1 9 9 4 ) 用实验证明，数据库中最 有用的子集并不一定是粗糙集中的相对核，甚至可能不包括完全的核属性集。 ( s h 锄卸dz i a r k o ，1 9 9 5 ) 则讨论了基于r s 的从数据中发现规则的增量自适应算 法。( g 眩y m a l a b u s s e 锄dz o u ，1 9 9 8 ) 比较了同时使用可能规则及确定规则和只使 用确定规则的性能，发现前者产生较小的错误率。( c h o u b e ya n dd e o u g u n e t a l ，1 9 9 6 ) 的研究得出了同样的结论。他们还在属性选择的题目下研究了近似约简问题，并 给出了几个启发式算法。( k n a r c i k 卸dp i a s t a ，1 9 9 8 ) 研究了在每个对象的c o s t 不 一样时的粗糙分类器。他们的主要方法是对所有的对象定义一个新的c o s t 属性。 ( m o l l e s t a da n dk o m o r o w s l 【i ，1 9 9 9 ) 提出了在粗糙集框架下缺省规则生成的格搜索 算法，并给出一组启发式搜索策略。 大数据集。由于粗糙集在数据挖掘中具有较大的计算复杂度，受关联规则挖 掘算法的启发，有些作者提出了将关联规则挖掘技巧应用于粗糙集的确定和可能 7 基于粗糙集的流网络和决策算法研究 规则生成中来，以减小粗糙集方法的计算复杂度( “n ，1 9 9 6 ) 。( n g l l y e na n d s k o w r o n e t a l ，1 9 9 7 ) 描述了一种决策表分解方法。他们首先使用遗传算法在决策 表中寻找代表性的模板( 类似如一条支持度最大的规则) ，然后将决策表一分为 二。满足模板的为一个部分，不满足的为另一部分。将该过程递归进行，直至决 策表的大小满足要求为止，然后再对小决策表生成规则。当新对象到来时，从顶 部开始匹配，直至叶子的规则。 多方法融合。( j e l 伽e k ，a w i e ca n ds l o w i i l s k i ，1 9 9 5 ) 研究了将r s 理论用于 神经网络训练数据的预处理。上述处理有利于提高学习效率，并且保持了较低的 稳定的近似分类误分类差错率。首先使用面向属性的概念树爬升技术对属性进行 泛化，然后使用r s 方法计算缩减并生成规则。由于在泛化过程中消除了不必要 的属性值和在缩减过程中去掉了不相关的属性，最后的规则是很一般的形式并且 可用高层次抽象概念表达。饵u ，1 9 9 5 ) 提出了一种将基于属性的归纳概念方法和 r s 结合的方法。( l i n g r a sa n dd a v i e s ，1 9 9 9 ) 研究了粗糙集和遗传算法的结合，提 出了一种粗糙遗传算法。在该算法中，基因用粗糙数表示。 信息检索。( b e a u b o u e fa n dp e t r y ，1 9 9 3 ) 在r s 理论基础上提出了一种r 0 u g l l 关系数据库模型，并定义了各种r o u 曲关系算子。该模型将r s 的重要性质引入 到基本关系模型中，从而使之具有更好的检索能力和适应性。在此模型中，查询 结果返回的是基于属性的r o u g l i 关系，它不仅包含一个查询的确定应答，还包 含可能的应答，例如上近似所包含的元组等。 粗糙逻辑。( u n ，u 觚dy a 0 ，1 9 9 4 ) 基于拓扑学观念定义了r o u g l l 下近似算 子l 和r 0 u g l l 上近似算子h 。这2 个算子的语法性质分别与模态逻辑中的必然 算子和可能算子十分相似，因而带l 和h 算子的逻辑公式被称为r d u 曲逻辑公 式，并且建立了与模态逻辑相似的公理化r 0 u g l l 集的逻辑演绎系统和相平行的 演绎规则。f y a oa i l dl i n ，1 9 9 6 ) 研究了粗糙集和模态逻辑的关系，通过使用不同 的二元关系作为粗糙集的基础，可以导出不同的粗糙集代数模型，相应为不同的 模态逻辑。 决策支持。决策分析不仅仅是分类任务，它还要求对属性的评价的标准。为 使经典粗糙集理论适用决策支持的要求，( g r e c o ，m a t a r a z z oa n ds l o w i n k s i ，1 9 9 8 ) 给出了扩展经典粗糙集的方法。主要是采用一种和评价准则有关的支配关系代替 等价关系的方法，并提出以模糊属性评估方法代替粗糙集中的属性重要性方法。 原型系统。典型系统如k d d r ，u r s ，r o u g l l d a s & r o u 曲c l a s s ，r o s e t t a ， r o u 曲e n o u g l l ，g r o b i a n 等。这些系统一般对经典理论有所扩展。 其它。有字符识别，医疗诊断，市场预测等。这些主要是利用粗糙集及其扩 展方法进行规则获取后在具体领域的应用。 8 山东师范大学硕十学位论文 1 4 本文组织结构 本文对粗糙集流网络和决策算法进行了研究，提出了一种基于粗糙集的决策 算法挖掘方法，并将粗糙集流网络、决策算法和贝叶斯定理结合了起来，构建了 基于粗糙集和贝叶斯定理相结合的风险规则挖掘模型。本文的具体结构如下： 第1 章：引言。 介绍了本论文的研究背景，粗糙集理论的研究现状及其在数据挖掘中的应 用。 第2 章：粗糙集理论的基本知识。 介绍了粗糙集理论的基本概念和知识，并对本论文的一些概念和符号进行了 统一和描述。 第3 章：粗糙集决策算法。 引入z p a w l a k 关于决策算法的概念，分析决策算法的性质和在实际当中的 应用，并且把决策算法和贝叶斯定理进行了比较，提出了一种基于粗糙集的决策 算法挖掘方法。 第4 章：粗糙集流网络。 介绍粗糙集流网络的相关概念，每一个流网络都是一个决策算法，整个流网 络满足贝叶斯公式，并且对流网络进行改进和创新。 第5 章：粗糙集理论和贝叶斯定理在 项目风险管理中的应用。 将粗糙集理论和贝叶斯定理相结合，利用粗糙集对数据进行约简，利用贝叶 斯定理训练约简后的数据，得到了粗糙集贝叶斯规则挖掘模型，采用真实的数 据集对i t 项目风险进行了分析。 第6 章：总结与展望。 对本论文的主要工作进行了总结，并对未来的工作进行了展望。 9 基于粗糙集的流网络和决策算法研究 第2 章粗糙集理论的基本知识 粗糙集理论是一种新的处理模糊和不确定知识的数学工具。其主要思想就是 在保持决策表分类能力不变的前提下，从决策表中挖掘出最小决策规则，并且能 够利用这些决策规则的集合进行决策分析和预测。本章将介绍粗糙集理论的基本 知识，作为以后各章的基础。 2 1 粗糙集理论的基本概念 2 1 1 知识与分类 一般认为，知识是人类实践经验的总结和提炼，具有抽象和普遍的特性，是 属于认识论范畴的概念。任何知识，都是对其事物运动状态及变化规律的概括性 描述。这对知识的定义不能算是一个完全的、精确的表达，因为知识是具有多种 意义的。 粗糙集理论从认知科学的一些观点来理解知识，正是由于这一点使得粗糙集 理论在数据推理、经济决策等领域有了新的突破，才得到广泛应用。 知识是源于人类及其他物种的分类能力。关于环境的知识，从生存的观点看， 就是感觉信号的复杂分类，它是动物的基本功能对不同情况的分类能力而来的。 更为抽象层次的分类是推理、学习、决策的关键，是一种基础知识【2 1 。 例如，在某种环境下，机器人表现得像是有知识、有智慧，实质上是它们将 外部环境和内部状态的传感信号分类，得出可能的情况并由此支配行动，知识直 接与真实或抽象世界有关的不同分类模式联系在一起。 因此，任何一个物种都是由一些知识来描述的，根据这些知识可以把它们分 类，利用不同的属性知识描述，对物种产生不同的分类。 定义2 1 【1 l 设u 是我们感兴趣的对象组成的非空有限集合，称为论域( 全 域) 。任何子集x u ，称为u 中的一个概念或范畴。u 的一组概念称为u 上的 抽象知识，简称为知识。 本文主要是对在u 上能形成划分的那些知识感兴趣。u 中的对象按照某一 个或几个属性进行分类，从而得到一个划分，在此一个划分z 定义为： z = x l ，x 2 ，丑】，其中，彪u ，石一彩，石n 曷a 囝( f 乒_ ，f ，j = 1 ，2 ，以) ， 力 u 石= u 。 f = 1 1 0 山东师范大学硕士学位论文 定义2 2 【1 】u 上的一个划分称为关于u 的一个知识库( k n o w l e d g eb a s e ) 。一 个知识库就是一个关系系统k = 缈，尺) ，其中u 是非空有限集，尺为u 上等价关 系的一个族集。 圳尺表示尺的所有等价类( 或者【，上的分类) 构成的集合，【x k 表示的是 包含元素石u 的r 等价类。 下面举例说明： 玩具积木的集合u = 仁l ，x 2 ，z 3 ，z 4 ，泓，x 6 ，z 7 ，工8 。现在假设这些积木有不同的颜 色( 红、黄、蓝) 、形状( 方、圆、三角) 、体积( 大，小) 。因此，这些积木都 可以用颜色、形状、体积这些知识来描述。如果我们根据某一属性描述这些积木 的情况，就可以按颜色、形状、体积分类： 按颜色分类： 红： x l ，z 3 ，工矗；黄：扛5 ，z 6 ，z 吐；蓝：如2 ，茗d ； 按形状分类： 方：伽2 ，x 6 ；圆：伽l ，石5 ；三角：扛3 ，x 4 ，x 7 ，x 磅； 按体积分类： 大： x 2 ，工7 ，工8 ；爿、： x l ，工3 ，x 4 ，x 5 ，工6 。 换言之，我们定义了三个属性：颜色风、形状r z 、体积尺，通过这些属性， 就可以得到下面三个分类： 圳尺l = 伽1 ，z 3 ，茗7 ， 黔，石6 ，x 8 ，仁2 x 4 ， 【，r2 = 缸1 ，工5 ，协2 ，x d ，仁3 z 4 ，z 7 ，x 8 ) ， z 7 r 3 = 0 1 ，z 3 石4 ，石5 ，z 6 ，缸2 ，工7 ，x 8 。 2 1 2 不可分辨关系和上、下近似集 粗糙集理论拓展了经典的集合论，把用于分类的知识嵌入集合内，作为集合 组成的一部分。一个对象口是否属于集合z ，需要根据现有的知识来判断，可 以分为三种情况l l l j ： ( 1 ) 对象口肯定属于集合x ； ( 2 ) 对象口肯定不属于集合x ； ( 3 ) 对象口可能属于也可能不属于集合x 。 基于粗糙集的流网络和决策算法研究 集合的划分密切依赖于我们所掌握的关于论域的知识，是相对的而不是绝对 的。二元对k 一缈，尺) 成为一个近似空间( a p p r o x i m a t i o ns p a c e ) ，设x 为论域u 中 的一个对象，x 为u 的一个子集，则瞵k 表示所有与x 不可分辨的对象所组成 的集合，换句话说，是由x 决定的等价类，即k 中的每个对象都与x 有着相同 的特征属性( a t t r i b u t e ) 。 定义2 3 【1 】若p 尺，且p ，tf 2 j ，则p 中所有等价关系的交集也是一个等价 关系，称为p 上的不可辨识关系( i n d i s c e m i b l er e l a t i o n ) ，记为删d ( p ) ，且有 【z k ( 一5 9 x 】异。 这样，u 胁r d ( p ) ( 即等价关系d ( p ) 的所有等价类) 表示与等价关系p 相 关的知识，称为k 中关于【，的尸基本知识( p 基本集) 。为简单起见，我们用叫p 代替圳胁r d ( p ) ，删d ( p ) 的等价类称为知识p 的基本概念或基本范畴。特别地， 如果q 尺，则称q 为k 中关于u 的q 初等知识，q 的等价类为知识尺的q 初等 概念或q 初等范畴。 同样，当ka 缈，尺) 为一个知识库， r d ( k ) 定义为k 中所有等价关系的族。 不可分辨关系是粗糙集理论的核心概念，根据不可分辨关系，论域被划分为一个 类族，而每个类内部的对象都是不可区分的。 对于粗糙集可以近似地定义，我们使用两个精确集，即粗糙集的上近似 ( u p p e ra p p r o x i m a t i o n ) 集和下近似( 1 0 w e ra p p r o x i m a t i o n ) 集来描述。 定义2 4 【1 l 设集合x u ，尺饿d 僻) ，定义两个子集： 丛= u 明恹l y x ) ， 砝= 岬叩i y n x 彩 分别称它们为x 的尺下近似集和r 上近似集。 集合跏仁) = 砝一丛称为x 的j c c 边晃域；p 弧( x ) = 丛称为x 的r 正 域；e 瓯僻) = 【，一戤称为x 的r 负域。 显然，融一呱俾) u 剧( x ) 。丛或鹏伍) 是由那些知识r 判断肯定 山东师范大学硕士学位论文 属于x 的u 中元素所组成的集合；砑是由那些知识尺判断可能属于x 的u 中 元素所组成的集合：删矗( x ) 是由那些知识尺既不能判断可能属于石又不能判断 肯定属于一x 的u 中元素所组成的集合；慨( x ) 是由那些知识尺判断肯定不 属于x 的u 中元素所组成的集合。 下面的性质是显而易见的： 定理2 1 【1 】 ( 1 ) x 为r 可定义的当且仅当肷a 麟； ( 2 ) x 为r 粗糙的当且仅当砝一心； 我们也可以将斛描述为x 中的最大可定义集，将砝描述为含有x 的最小 可定义集。根据集合x 的上近似和下近似的不同情况，可以定义四种不同的重 要的粗糙集【1 5 】： ( 1 ) 如果丛一g 且砝乒u ，则称x 为尺粗糙可定义； ( 2 ) 如果鲋；彩且砝一u ，则称x 为尺内不可定义； ( 3 ) 如果丛f 2 i 且面一u ，则称石为尺外不可定义； ( 4 ) 如果丛一彩且砝= u ，则称x 为尺全不可定义。 这种划分的直观意义是这样的： 如果集合工为尺粗糙可定义，则意味着我们可以确定u 中的某些元素属于 x 或一x 。 如果集合x 为尺内不可定义，则意味着我们可以确定u 中的某些元素是否 属于一x ，但不能确定u 中的任一元素是否属于石。 如果集合x 为尺外不可定义，则意味着我们可以确定u 中的某些元素是否 属于x ，但不能确定u 中的任一元素是否属于一x 。 如果集合x 为r 完全不可定义，则意味着我们不能确定u 中的任一元素是 否属于x 或一x 。 粗糙集理论与传统的集合论有着相似之处