（计算机软件与理论专业论文）粗糙集理论应用中若干问题的研究.pdf

山东科技大学硕士学位论丘摘要 摘要 粗糙集理论是一种处理不确定知识的有力工具，在各领域已得到了广泛应用。本文 的研究工作主要集中在粗糙集应用过程中数据预处理和决策表约简两个方面，围绕当前 存在的问题，对现有的算法进行了改进，同时也提出了些新的解决方案。完成的工作 包括： 1 用关系代数重新定义了基本粗糙集模型中的关键概念，建立了粗糙集与关系数据 库之间的内在一致性，为利用关系数据库中的集合运算对决策表进行高效处理奠定了基 础。 2 针对不一致决策表的处理问题，引入了作用的时间因素这一概念，提出了基于移 动平均数的处理方法和基于时序粗糙逻辑的处理方法，并对进行了实验验证。 3 在系统总结现有连续属性离散化算法的基础上，对基于布尔逻辑的连续属性离散 化算法进行了改进，并尝试了多种离散化算法的结合，实验表明这是进一步提高处理效 率的有效途径。 4 对现有的约简算法进行了改进，并提出了一种求取较优约简的启发式算法。 5 针对超大数据集的处理，提出构建集群系统通过并行计算来完成任务和相应的任 务分解方法和计算方法。 6 在前述知识和方法的基础上，给出了一个应用实例。将粗糙集应用于排队系统的 仿真过程，利用粗糙集对由顾客到达原始记录形成的决策表进行约简和决策规则提取， 获取影响顾客到达率的关键因素，在此前提下展开仿真，从而更好的反映了真实系统， 提高了仿真结果的决策价值。 最后对全文进行了总结并指出了下一步的研究方向。 关键词：粗糙集理论；不一致决策表处理；连续属性离散化；约简；机群系统；并行； 仿真；排队系统 山东科技大学硕士学位论文摘要 a b s t r a c t r o u g hs e tt h e o r y , a saf o r c e f u lt o o li np r o c e s s i n gu n c e r t a i n t i e s ，h a sb e e na p p l i e di nw i d e a r e a s t h e d i s s e r t a t i o nf o c u s e so nd a t ap r e t r e a t m e n ta n dr e d u c t i o no fd e c i s i o nt a b l e sa n d p r o p o s e ss o m em e a n i n g f u lm e t h o d sa n di m p r o v e m e n t s ，t h er e s e a r c hw o r k si nt h et h e s i sc a n b ed e s c r i b e da sf o l l o w s ： 1 t h ed i s s e r t a t i o nr e d e f i n et h ek e yc o n c e p t so fb a s i cr o u g hs e tm o d e lb yr e l a t i o na l g e b r a t ob u i l dt h ei d e n t i t yb e t w e e nr o u 曲s e ta n dr e l a t i o nd a t a b a s e ，s ot h a tl a y sas o l i df o u n d a t i o nf o r t h eh i g he f f e c t i v ep r o c e s s i n go f d e c i s i o nt a b l e st ot a k ea d v a n t a g eo f s e tc o m p u t a t i o n s 2 t ot h ep r o c e s s i n go fi n c o n s i s t e n td e c i s i o nt a b l e s ，t i m ef a c t o ro f p r o c e s si si n t r o d u c e d e d t w os t r a t e g i e s ，t r e n da n a l y s i si si n t r o d u c e dt of i n di t ，t h e nv e r i f ya p p l i c a b i l i t yo ft h ef i r s t m e t h o d 。 3 a f t e rs u m m a r i z ep r e s e n td i s c r e t i z a t i o na l g o r i t h m so fc o n t i n u o u sv a r i a b l e s ，t h e n i m p r o v et h ed i s c r e t i z a t i o na l g o r i t h mo fc o n t i n u o u sv a r i a b l e sb a s e do nb o o l e a nl o g i c t h e c o m b i n a t i o n so fa l g o r i t h m sa r ea t t e m p t e da n de x p e r i m e n t sp r o v et h et e c h n i q u ei sa ne f f e c t i v e w a y t oa c h i e v eb e t t e rr e s u l t s 4 t h eg e n e r a lr e d u c ta l g o r i t h mw a si m p r o v e da n dan e wh e u r i s t i co n ew a si n t r o d u c e d 5 t ot h ed i s p o s a lo fs u p e rl a r g ed a t as e t ，t h eb u i l d i n go fc l u s t e rs y s t e m si sp u tf o r w a r d a n dt h ea l g o r i t h m so ft a s kd i s a s s e m b l em a dc o m p u t a t i o na r ed e s i g n e d + 6a ne x a m p l eo ft h ea p p l i c a t i o no fr o u g hs e tt h e o r yi sg i v e n r o u g hs e tt h e o r yi sa p p l i e d i nq u e u es y s t e ms i m u l a t i o nt oc o m p r e s si n f o r m a t i o na n de x t r a c td e c i s i o nr u l e sf r o md e c i s i o n t a b l et h a tc o m e sf r o mo r i g i n a lr e c o r d s 。t h e s er u l e sr e f l e c tt h ef a c t o r st h a ta f f e c tt h ea r r i v a lr a t e o fc u s t o m e r s t h en e ws i m n t a t i o np r o c e s si sc a r r i e do u tb a s e do na b o v er e s u l t s 。t h en e ww a y e n h a n c e st h ev a l u eo f t h eo u t p u to f s i m u l a t i o nt od e c i s i o nm a k i n g f i n a l l y , ar e c a p i t u l a t i v ec o n c l u s i o ni sg i v e n ，a n dt h ef u t u r e r e s e a r c hd i r e c t i o n sa r e p r o p o s e d k e y w o r d s ：r o u g hs e tt h e o r y ；h a n d l i n go fi n c o n s i s t e n td e c i s i o nt a b l e ；d i s c r e t i z a t i o n o f c o n t i n u o u sv a r i a b l e s ；r e d u c t ；c l u s t e rs y s t e m s ；p a r a l l e l ；s i m u l a t i o n ；q u e u es y s t e m s 声明 本人呈交给山东科技大学的这篇硕士学位论文，除所列参考文献和世所公 认的文献外，全部是本人在导师指导下的研究成果。本论文资料尚未呈交于任 何其他的学术机构作鉴定。 a f f i r m a t i o n 硕士生繇爱p 中华 日期： d 土， 6 牛 id e c l a r et h a t t h i sd i s s e r t a t i o ns u b m i t t e di nf u l f i l l m e n to ft h er e q u i r e m e n t sf o r t h ea w a r do fm a s t e ro fp h i l o s o p h yi n s h a n d o n gu n i v e r s i t yo fs c i e n c ea n d t e c h n o l o g y , i sw h o l l ym yo w nw o r ku n l e s sr e f e r e n c e do fa c k n o w l e d g e t h e d o c u m e n th a sn o tb e e ns u b m i t t e df o rq u a l i f i c a t i o na ta n yo t h e ra c a d e m i ci n s t i t u t e y 、 十7 s i g n a t h f e ：芬莎、r 胁。：b j f 牛 山东科技丈学顶士学位论文 1 1 粗糙集理论的起源与现状 1绪论 人类在长期的生产实践和科学研究中，已经形成了一系列适用于确定和完全信息对象 的成熟技术体系，但是随着对复杂系统研究的深入，对有效处理非确定和不完全信息对 象技术的迫切需求呼唤新的理论和方法，粗糙集就是这样一种理论和方法。1 9 8 2 年波兰 数学家z p a w l a k 提出了粗糙集理论，最初的研究论文大多是以波兰文发表的，在当时并 来引起国际上数学界和计算机界的重视，研究的地域仅限东欧各国。八十年代末，这一 理论引起了国际学术界的兴趣，学者们对其做了许多理论和应用方面的研究工作，极大 地推动了它的发展。1 9 9 1 年z p a w l a k 出版的专著系统全面的阐述了粗糙集理论，给出 了严密的数学定义和表达；i 9 9 2 年r s l o w i n s k i 主编的关于粗糙集应用及其相关方法比 较研究的论文集出版，标志着粗糙集理论逐步走向成熟。1 9 9 2 年在波兰k i e k r z 召丌了 第一届国际粗糙集讨论会，从此每年召开一次以粗糙集理论为主题的国际研讨会。1 9 9 6 年底在日本东京召开了第五届国际粗糙集研讨会，这是第一次在亚洲地区召开的范围广 泛的粗糙集研讨会，标志着对粗糙集的研究在全世界范围内进一步扩展开来。国内从 2 0 0 1 年开始，由中国计算机学会和人工智能与模式识别专业委员会主办，每年召开一次 粗糙集与软计算学术研讨会。 粗糙集理论是一种软计算方法。传统的硬计算方法，使用精确、固定和不变的算法来 表达和解决问题，而软计算则是利用所允许的不精确眭、不确定性和部分真实性以得到 易于处理的鲁捧性强和成本较低的解决方案。常用的软计算方法还有模糊集、神经网络、 遗传算法等。 1 2 知识分类的观点 基本粗糙集理论认为知识就是人类和其它物种所固有的分类能力。分类是人类从现1 1 甘= 界得到论断的第一要素，而推理是第二重要要素。实质上，推理是以“当- _ 贝0 ”结构为 基础的，即因果关系律。“1 用粗糙集理论研究论域中的事物时，用论域对象的一些属性取值柬描述它们。依据这 用粗糙集理论研究论域中的事物时，用论域对象的一些属性取值束描述它们。依掘这 虫末辩技大学硕士学垃论文 绪论 魑属性及其取值对论域对象进行分类，不同的属性或它们的组合可以构成对论域对象不 同的分类方法。在粗糙集中用等价关系来划分论域对象。按浆一个或几个渴性组合取值 被划分为一类的论域对象，不论它们在其它属性上取值是否相同，在该等价关系之下， 这些对象之阔是无法区分的。例如，以学生番疑的出f 1 旅行为饿，瑕定能否成行取决于 三个因素，暑假期间是否有项目安排，可达目的地的交通工具和出行者的经济负担能力， 攒此得到以下决策表： 表1 1 学生出行决策表 t a b l e l 1t h ed e c i s i o nt a b l ea b o u tt h et r i po f s t u d e n t s 由上表可以看出，依据项目安排对出行情况进行分类，可分为两类：有安排和无安排， 对于前一类对应了不可出行，而后者则对应了不可出行和可以出行两类情形，这两类情 形按项目安排来分析是无法区分的。此时称关于出 亍可能性的知识是比较粗糙的，当得 剜可达交通工具和学生经济负担能力的信息蜃，就可完全确定能否出行，即知识粒度变 得精细了。 粗糙集理论反映了人们以不完全信息或知识去处理一些不分明现象的能力，1 j 丁以说在 一定程度上粗趱集方法模仿了人类瓣认知过程。 1 3 粗糙集与模糊集 山东科技大学坝士学位论文绪论 传统的集合论认为，一个元素要么属于一个集合，要么不属于一个集合，二者必居其 一。事实上不同种类的事物之间总是存在一些过渡地带，在这些点上总可以发现许多事 物具有亦此亦彼的特点，传统集合论缺乏描述这类客观现象的能力。1 9 6 5 年，z a d e h 提 出了模糊集，其最重要的一个观点就是隶属度的概念，该理论认为个元素总是以某种 程度( 隶属度) 属于某个集合。模糊集为用定量的方法处理事物的过渡性质提供了理论 工具。 经常见到在有的文献中比较模糊集与粗糙集优劣的论述，实际上两者研究的不是同 一类现象。前者关注的是不同种类事物之间的过渡性质，后者则着重解决对象信息不完 全或不确定时的处理。例如在人类学中，即使研究者获知了某些人种的全部人类学特征， 仍然不能将其明确的归类于黄、白、黑、棕四大人种。而在学生暑期出行的例子中，仅 知道假期是否有项目安排时，还无法完全确定可否出行，获知是否有可达的交通工具和 出行者的经济负担能力后，能否出行便可以确定了。随着关于对象信息的增加，对对象 的认识便趋于完全确定。 1 4 粗糙集的应用研究 在粗糙集的研究上有两个主要方向，一个是将粗糙集作为数学的研究范畴和领域，将 其视为一种纯粹的数学方法，侧重于构造粗糙集的数学理论体系。另一个将粗糙集作为 人工智能和知识发现中的一种实用技术，运用到生产生活中的各个方面。涉及的主要研 究内容包括：粗糙集理论的系统化、基于粗糙集的非精确推理、粗糙控制理论及系统开 发、寻找粗糙集的约简算法等。本文的工作遵循第二种思路。 粗糙集理论将无法确认的个体归属于边界区域，边界区域定义为上近似和下近似之 间的差集，由于有确定的数学公式描述，使得含糊元索的数目是可以计算的。随着粗糙 集在理论上趋于完善，许多粗糙集的成功应用相继出现。相对于其它处理不确定性的理 论工具而言，粗糙集有其独特的优越性。 许多专家学者在粗糙集的应用方面已经做了广泛深入的研究，在国际和国内发表了 大量文章。已经有很多基于粗糙集理论的分析系统和工具，其中有代表性的研究系统有： 加拿大r e g i n a 大学的k d d r ；加拿大r e d u c ts y s t e m 有限公司的d a t a l o g i c r ；挪威科技 大学计算机与信息科学系知识系统教研组和波兰华沙大学数学所逻辑教研组的r o s s e t a ； 波兰波兹南科技大学的r o u g h d a s 和r o u g h c l a s s ：波兰工业大学的r o s e ( r o u g hs e td a t a 3 当塞至! 望盔兰鎏圭兰竺笙兰 笙堡 e x p l o r e r ) 波兰国际有限公司的r o u g he n o u g h ；美国堪萨斯大学的l e r s ( l e a r n i n gf r o m e x a m p l e sb a s e do nr o u g hs e t ) ；中科院自动纯研究所的r s l ；中国重庆邮电学院计算机 科学与技术研究所的r i d a s ；西班牙马德里工艺大学语言与系统系的r s d m ( r o u g hs e t d a t am i n i n g ) 。 粗糙集的一般应用领域非常广泛，在生产生活中的不同领域有许多应用成累： 商业上，对银行分类资料迸彳亍预处理，在属性个数及英取值上对数攒压缩，消除冗 余和噪声，提高专孛经网络预测模型翡颈测糕度f 8 】；利用缝粹的糖糙集和模糊粗糙集对股 票价格进行资料挖掘，寻找与股桑价格相关的规则进行预测i 9 】；对电子商务中的网上购 物进行资料挖掘，躅粗糙集对网上购物豹鼷客进行购物行为分丰厅，从中寻找关联娩则， 根据购物习惯向在线购物的顾客提供相应的商晶推荐f l ；将粗糙集与遗传算法中的编码 技术结合起来，对瘸络用户遴行分类【l l 。 在医学上，将粗糙集理论用于对医学临床数据库进行基于规则的建模、分析和规则 提取f 1 2 】；利用l e r s 分析生骥反应、环境因素和不正常言行之闻的关系【i 3 1 。 在地理信息处理瓤琢境检测方面，将粗糙集理论运用于媳理信息系绞的信息处理， 磷完了影响冬小麦产量的地理特性，获得了魑有用的规则和稚识“；用粗糙集方法对 大量的炙规则的地理信息系统中的资誊喜进幸亍筒化，从大曩的汽车运短的轨迹资糕中发撼 车辆经常报警或拥挤的缝段和区域，帮劲公安警察部门合理的分配和布置警力9 ”；嗣用 模糊一粗糙集模型对水中的藻类的数量进行预测“”； 在工妲上，建立基于粗糙集的我翻缓倾斜薄煤层采煤方式选择模型n 7 】；利用粗糙集 处理变电站故障场景中的资料，简化场景模式，提取故簿信息。 1 5 本文所做的主要工作 1 粗糙集理论主要用于处理组织成二维褒格的决策表，而关系数据库是现代最为成 熟的数搽库技术，本文用关系代数运算对基本糖糙集模黧进行了重额定义，建立了数据库 关系模型与纂本粗糙集模缀之间的联系，为利用集合运算束究成粗糙集理论下数据的高 效处理奠定了基硪。 2 针对戍周中决策表上大量出现的不一致现象，引入作用的时间因素这概念，分别 提懑了基于移动平均数的处理方法秘基于时彦糖糙逻辑躺处理方法，并对 i 者避行了实 山东科投 k 学砸l 学位论空 缔论 验验证。这些方法避免了在预处理过程中遗失麓要对象，增强了提取决策规则的有效- 胜。 3 。程鞍为宠整戆慈结魏毒凌繁藩犍离数纯葵法豹薹疆土，改送了蒸予带尔逻辑豹连 续属4 陂离散化算法，并研究了多种离散化方法的结合，指出这进一步掇商效率的有效谂 径。 4 时现有约篱黪法逶幸亍了改遴，给遗了求敬较优约祷豹一耱启发式箨法。 5 针对传统的处理技术在处理超大数据集方面的局限，提出构建集群系统通过并行 计算卷完残 壬务移麴应豹饪务分瓣方法帮诗黧方法。 6 给出了粗糙集理论的一个成用实例，将粗糙集理论成用于排队系统的建模、仿真 和优化控制方面。 山东科技大学颤： 二举证论文 粗糙集理论基础 2 1 耀糙爨憋基本藏念 2 糖糙集理论基綦塞 粗糙集理论是在集爨论中关于等价筵系豹糕念熬磴上发展怒浓的，关系、等徐关 系、划分等概念在其它文献中邑穰详缨论述，在鼗不褥赘述，下藤扶不可分辨关系开始 来奔缮穗关檄念。 2 1 1 集合的不可分辨关系与粗糙集 一个给是的棼空有隈繁会u = 弘，x 2 。，文 ，称为论域，u 酌镁一子集称为u 的一个 概念或者一个辩跨。醪的一键概念拣为u 上豹撞象知谖，筒称为始浓。 定义2 1 ：绘定一令谂域瑟等徐关系蔟震，在笛价关系族震下怼论壤u 戆分， 称为知识，记为u r 。 增鼹元缎s ；影，a ，v ，f ) 来袭示一个知识系统( 务波称为信息系绞，文中将不傲照 分) ，菇中u 为一个非空有限的对象集合，= “，而，x 。) ，集合中经一对象x 使用属性 a ，a 和相成的属性德v a ；g 来描述，魁属性a ，的德域，属性傻集会 v = u 吒，a 陋购。，是一个函数，定义为f ：u x a 砷v ，它为每个对象静簿个疆缝簸 z # - 予了一个属性德a 即对于a ，臣a 和x 岜u 商f ( x ，a ，) k ；。粗糙集中的知识系统用决策表 形式寒表示，决燕表数楚麓潺经，彝受对象( 夯稼为撵本) ，决策淡孛兹一令鬟瞧瓣澎 个等价关系。矮中的属性集a = c u d ，c n d = ，c 为条件属性，d 为决策属性，用于 摊述分类。 对知谖系统s = 秽，a ，v ，) ，每一个属性口a 对应一个等价关系r r ，蹦，当盥汉 巍f ( x i ，4 ) = f ( x ，砧，则麟4 睫集合a 就对应一个等价芙系族。文中等徐关系旗与属性集 将不作嚣分。 6 山东科技人学硕士学位论文 粗糙集理论基础 定义2 2 ：s = u ，a ，r ， 为一知识系统，b a ，定义b 不可分辨关系为 i n d ( b ) ：= ( x ，x ) u2 ：v a b ，a ( x ) = a ( x ) a ( x ) 为元素x 在属性a 上的值。 不可分辨关系是等价关系，如果( z ，x ) i n d ( b ) 说明根据已有的信息已不能将x $ 1 1 x 区分开来。 令x u ，r 为u 上的一个等价关系，当x 能表示为r 等价类的并时，称为r 可 定义的，否则称x 为r 不可定义的。r 可定义集是论域的子集，它可以在知识库中精确 的定义，而斤不可定义集不能在知识库中精确定义。r 可定义集也称为r 精确集，r 不 可定义集称为r 非精确集或r 粗糙集。当存在等价关系使得x 成为u 中的精确集时，爿 称为知识中的精确集，当对于知识库中的任意等价关系，x 都是非精确的，x 称为知识 库的粗糙集。对于知识库中的粗糙集，可以用上近似和下近似的概念来进一步刻画。 定义2 3 ：设集合x u ，称r 一( x ) = u ( r u r ly x ) 为x 的下近似， r - ( x ) = u ( y u r i ，n x 为x 的上近似， b n a ( x ) = r - ( j ) 一只一( x ) 为x 的边界 区域。 r 的下近似由根据r 可确知肯定属于x 的u 中元素组成；r 的上近似由那些根据知 识月判断可能属于x 的u 中元素组成；边界区域是根据知识u r 既不能判断肯定属于 x 又不能判断肯定属于霄的元素组成。 2 1 2 核与约简 核与约简是粗糙集理论中两个最重要的基本概念。从直观上说知识的约简是指知识 的本质部分，它用以定义所考虑的知识中遇到所有基本概念，而核是其中最重要的部分。 定义2 4 ：设r 是一族等价关系，且设，r 。若i n d ( r ) = i n d ( r r ) ，则称关系r 在 r 中是可省的，否则就是不可省的。若族集r 中的每个关系，都是不可省的，则称族集r 是独立的，否则称为依赖的或非独立的。 定义2 5 ：有等价关系族q 、p ，若q p ，q 是独立的，并且i n d ( q ) = i n d ( p ) ，则 称q 是p 的一个约简。记为q = r e d ( p ) 。 7 山东科技大学硕士学位论文 粗j 糙集理论基础 约简不是唯一的，p 可以有多个约简。核与约简之间存在着重要联系。 定义2 6 ：p 的所有约简的交集称为p 的核，用公式表达则为如下形式 c o r e ( p ) = c 、r e d ( p ) 核包含在每一个约简之中，进行知识约简时是不能够被删除的。 2 2 决策表与决策规则 粗糙集适合于处理组织成二维表格形式的数据，此二维表格称为决策表，它与信息系 统存在一一对应的关系，下面将详细描述其概念与处理方法。 2 2 1 信息系统与决策表 定义2 7 ：知识u q 依赖于知识【，p ，记作u p j u q ，i f fi n d ( p ) 呈i n d ( q ) 。 定义2 8 ： 知识u i p 与知识u q 等价，记作u p su q i f f u i p j u q a u q j u i p 。 定义2 9 ： 知识u i p 与知识u q 独立，记作u i p u i q ，i f f u i p 等u q 上j - u q u i p 均不成立。 对于一个论域空间中由两个等价关系所确定的知识系统，当知识u q 依赖于知识 u i p 时，称知识u i p 比知识u q 更精细，或称知识u q 比知识u i p 粗糙，这时论域u 被q 所划分的等价类中每一个元素都可以准确地表示为由p 所划分等价类中元素的并。 对于一个知识系统s = u ，a = c u d ，v ，厂) ，当知识d 依赖于知识c 时，该知识系统称为 是一致的。从一致的粗糙集信息系统中可以导出具有以下形式的决策规则： f ( x ，c i ) 厂( x ，d 1 ) x u ，c l c ，dj d ，i = 1 , 2 ，c a r d ( c ) ，j = 1 , 2 ，c a r d ( d ) 这些规则将条件属性和决策属性的取值对应起来。这些规则要满足协调性，即相同的 r 当窭塑垫查兰璧主兰垡堡塞 垫整叁望婆篓型 溉剡前邦定其有相同的规则蘑部，不同的规划前部允许有不同的或者相同的规则后部， 褶同的规则后部允许有相同或者不同的趣姆蘸部，不闻的规则焉郝只能有不同的蕊则蘸 部。 2 2 2 属性约麓与藩性僮约简 决策表中的每一对象代表了一条基本的决策规则，如果我们把所有这样的决策规剡 罗列出来，就可以得到一个决策规则的集会，实际上就是论域本身。但规购中会存在许 多冗余，另一方西不爨有适应性，不能适应其它的新情况。为了能够筒化决策规则，从 决策表中获褥受具适应性的规则，裁要对决策表进程约筒，使经过约简处理的决策表中 的一个对象可以代表一类具有楣间规律特性的样本。 对决策表豹约篱分为嚣类：对条件涡槛的约筒和对属性镶的约筒。 在羯糙集中对信息系统的属性约简为，从决策表中寻找条件满憔c 的一个子集c 使 得仍能够保持u c u d ，它是建立在芷域基础上的，下丽介绍藤域的概念。 定义2 1 0 ：设u 为一个论域，p 和q 为定义在u 上的两个等价关系族，q 静p 正域 定义为p o s 。( q ) ，定义为： p o s 4 q ) = up x ) z e u ，口 定义2 1 1 ：设u 为一个论域，p 和q 为定义在u 上的两个等价关系族，若 p o s ，( q ) = p o s ，( q ) 同，刚称r 为p 中相对于q 可省暗的；否刘称，为p 中相对于q 不 可省略的。 定义2 。1 2 ：设u 为一个论域，p 鄹q 为定义在u 上的两个等价关系族，羞p 中的每 一个r 都是q 不可省的，则称p 为相对于q 独立的。 定义2 1 3 ：设c ，为一个论域，p 和q 为定义在，上的两个等价关系族，蓉s 为p 的 真子集， 嚣p o s 。( q ) = p o s 。( q ) ，r s 为楣对予q 独立的，则稼s 为p 的约简。 出东科技大学硕士学位论文 粗糙集联论基础 i p , p 的所有q 约麓关系族为r e d q ( p ) a 刚属性约简为在满足关于决策属性d 的知识 依赖于关于祭传属性c 的知识的情况下，寻找条 牛属性c 的掰有约简。 定义2 1 4 ：设为一个论域，p 和q 为定义在u 上的鼹个等价关系族，p 的掰蠢q 约简关系族脚。( p ) 的交定义为p 的q 核，记为c o r e 口( p ) ，韶 c o r e o ( p ) = n r e d o ( p ) 在粗糙集的决策表中，一个属性对应蔫一个等价关系。条件属性和决策属性分别对 论域形成了各自的划分，这两个划分构成了条件属性和决策属性对论域中对象的分类知 识。属性约简就是从条停属性集合中发现都分必要的条馋属性，使得根据这部分条件属 性形成的相对于决策属性的分类和所有条件瘸性所形成的相对于决策属性的分类一致。 简单的说就是删除决策表中冗余的条件瘸性。通常一个决策表中的条件耩性对决策璃性 的相对约箍不是唯一的。人们往往希望寻找具有最少条件属性载约简，即最小条 牛瘸憔。 决策袭经过属性约简后，一感不必要的漏性可以删除，决策表仍然满足一致性。相 对于初始的决策表，表中规则的适应增强了，信息也季譬到了压缩。但是在每条舰则内部 仍然包含了冗余信息，可以去捧规则中某些属性豹取值邸进行筐约篱，在继续保持决策 袭一致性的前提下进一步压缩信患。 2 3 粗糙逻辑语言、语义和推导 粗糙逻辑语畜由原予公式组成，公式是一种属性一取值对，由命题联接词以标准的方 法构成复合公式。耀糙逻辑语富的语言符号定义如下： ( 1 ) a 一溪性集含。 ( 2 ) v u 圪一属性ae a 的属性僮域的集合。 ( 3 ) 一，a ，v ，一，s 分别表示非、合取、孛厅取、蕴含以及等价关系。 对于a a ，v v ，二元有序对( a ，v ) 称为原予公式，表示在属性a 上取馈为v ，是 对属性a 其旁值v 的所有对象的描述。糖糙集知谈系统中，每一个j c 重象对于每一个属瞧 只有个确切的值。 l n 山东科技大学硕士学位论文粗糙集理论基础 关予公式的公理： ( 1 ) v a a ，甜，v g o ，且u v ，鼷h ( 口，u ) ( a ，v ) 篓o ； ( 2 ) v a 一，e 圪，：f f v ( a ，v ) ；l ； 粮糙逻辑语言豹公式集含怒以下的两种集合： ( 1 ) 所有豹原予公式； ( 2 ) 如采移和妒是粗糙逻辑语言豹公式，则护，0 弘0 v 仍0 - - 弘0 z 妒纛怒粗糙逻辑 语言的公式。 对予粗糙集信怠系统s = ( u ，r ，v ，) 中，称x 色u 满足s 中的公式0 ，记傲x 净。护( 筒 记为x 每0 ) ，相应蠢以下定义： ( 1 ) ，( 墨疗) = v x 降( g ，功； ( 2 ) x 卜0 铮一x 口； 妒 x 降矿_ 拶静x | | 0 兰妒； 当0 为一个公式时，集合l0s 定义为： 0 ls = 缸u ，x 净s 拶) ； 称为s 中公式0 的含义，它是所有道过公式0 表达的对象的集合。当虽仅当1 0 ls = u 融，称护谯s 中为真。当且仅当| 0 l 。刊矿b 公式疗和妒在s 中等价。 岜至至! 垫墨兰! ! 占兰丝堡兰 一型丝墨墨堡苎些 粗糙集知识系统中的决策规则 厂( 工，c ) - - a f ( x ，d ，) 可以用糯糙逻辑语言表示为 0jv 。分别称为决策规则的前部和后部。 2 4 知识的不确定性分析 有知识f = z ，x ：，x 。) 其中的任一元素x 。称为知识中的概念，概念z 由等价关 系族月来描述时存在的不精确性是由于边界的存在而引起的，集合的边界越大，精确度 越低，下面给出知识不确定性定量表达。 2 4 1 知识表达系统不确定性 通常用近似精度来描述这种不精确性，定义如下： 、 c a r d ( r ( ) ) 似= c a r a 霄浠 t a i j j 近似精度表示了利用等价关系r 对概念进行描述的精确程度。 对于u r ，评价分类效果时有两个评价标准，分别是近似分类精度和近似分类质量。 近似分类精度定义为： 近似分类质量定义为 ( u r ) = 等 f = i c a r d ( rx o c a r d ( r 一石、 c a r d ( r m ) 弛( u7 尺) 。气丽 近似分类精度描述了当使用知识u r 时，所有决策中正确决策的百分比。近似分类 质量表示的是知识u r 以知识，为标准时的正确程度。 2 4 2 知识表达的概念不确定陆 知识表达不确定的原因之一是因为存在 r 糙集的边界，当边界为空时知识是完全确 1 2 生查型垫盔兰! 坚主兰竺笙塞篓壁垒型堡苎型 定的，边界越大，知识就越粗糙，知识的这种粗糙性称之为系统粗糙性。其次，等价关 系对论域的划分越粗，每个知识块就越大，则知识库中的知识越粗糙，这种粗糙性称之 为概念不确定性。对系统不确定性的处理采用的近似精度等尺度，衡量概念不确定性则 往往采用信息熵方法来处理。 将热力学中熵的概念扩展到知识系统中，用以衡量对象和属性出现的几率，称之为 信息熵，它标志着知识信息量的多少。设根据等价关系胄l 对论域u 的一个划分为 f 1 = x ，x ：，x 。 ，其上概率分布： c zl p ，= p 蔷。，p 翟：，i p 盏， 则概念x 。的信息熵定义为： 日( x ) = 一p ( 形) l o g p ( 石) 信息熵具有以下的性质： ( 1 ) 有界性：0 h ( x 1 l o g n ： ( 2 ) 确定性：当x 是完全确定时，存在x u 使p ( x ) = 1 ，则日( x ) = 0 ； ( 3 ) 最大性：当p i = p 2 = = p 。= 1 n ，h ( x ) 达到最大值； 设根据尺2 对论域u 的另外一个划分为f 2 = x ，e ，l ) ，其上概率分布： iy ly 2 k i xp 】2 p ( y 。) p ( y ：) p ( k ) l 则己知f 1 时知识f 2 的条件熵为： 其中 n h ( y l z ) = p ( x i ) h ( y i 盖 f = i 山末辩技大学颤。l 学位论文 鞋l 糖浆理论基础 n h ( y i x o = 一p ( 巧l 搿) l o g p ( 嚣| 石) f = j 为存在概念x 时y 的条件熵。 薯l 理2 1 ：设s = ( u ，r ，v ，f ) 为知识系统，p ，q r ，若知识i n d ( q ) i n d ( p ) 则h ( p ) 蔓h ( q ) 。 该定理表孵知识豹信怠烧随着知识的粗糙程度的增加面减少。熵标志着翔识系统的 混鼠程度，熵越大，知识系统的概念就越多，系统就显得越潺蘸。 弓| 理2 2 ：设s = ( u ，r ，v ，f ) 为一知识系统，p ，q 互r ，则 ( 1 ) 0 h ( y x ) 1 ； ( 2 ) 等价关系q 依赖于等价关系p 当且仅当h ( y l x ) = 0 ； ( 3 ) 等价关系q 独x r t 等价关系p 当且仪当h ( y l x ) = 1 ； 条 牛熵定量分孝厅了两个等价关系或者两个知识之间的关联和依赖程度。基于熵的定 义，还霹以继续分析等价关系之阔豹各释关联。根据不同的_ 陂雳帮需要，可以自行构造 不同鲍信息熵。信息熵表明了知识的粗糙性，是其所含信息多少的更深层次的刻灏，为 知识粗糙性提供了一种髂惑解释翻一种定量分聿居豹手段，使人们更容易理解其本质。 2 。5 基手关系代数的基本粗糙集模型 程糙集理论在应用中主要处理组织成二维表格形式的决策表，箍数摇库的关系模型将 数据库建摸成二维表格，通过关系代数鼹纂本粗糙集模型进行熏新定义，可以确定两者 之闻存在的一致往。同时关系数据瘁 楚是当前最为成熟的数掘库系统，它提供了强大的 数据掇级能力，可以方便魏实现对数据豹查询、受精以及其它维护工作，在此基础上就 可以借助其强大的数据处理能力，来完成对糖糙集信息系统的商效处理。 引入关系模型中的几个概念： 定义2 1 5 域是一组具有相阏数据类型的德的集合。 1 4 山东科技大学硕士学位论文粗糙集理论基础 定义2 1 6 给定一组域d o r a i ，d o m 2 ，d o r a 。，这些域可以是相同的。 d o m l ，d o m 2 ，d o m 。的笛卡尔积定义为 d o m l d o m 2x d o m h = d v l ，d v 2 ，d v 。1d v f d o m 。，i = 1 , 2 ，一， ) 其中每一个元素叫做一个元组，元素中的每一个值d ，叫做一个分量。 定义2 1 7d o m l d o r a 2 d o r a 。的子集叫做在域d 。小1 ，d o r a 2 ，d o m 。上的关系， 表示为： r ( d o mi ，d o r a2 ，d o 。) 这里r 表示关系的名字， 是关系的目或度。 设有知识系统s = ( u ，a ，v ，f ) ，对用于描述u 中对象的任一属性口，a ，由d ；的所有 可能取值集合构成一个域d j ，取所有域笛卡尔积的子集构成一个关系r ，令r ，中任一 元组( d v 。，d v 2 ，d v 。) 都存在一个工e u 使f ( x ，口f ) = d v f ( d r f ) 。同时r r 满足以下约 定：列是同质的，即每一列中的分量是同一类型的数据，来自同一个域；不同的列可出 自同一个域；列的次序是可以任意交换的；任意两个元组不能完全相同；行的次序也是 可以任意交换的；分量必须取原子值，即每一个分量都必须是不可分的数据项，对关系 中任一元组都有决策表中唯一对象与之对应。这样知识系统就与关系建立了一一对应关 系，这样就可以直接把对决策表的操作转换为对关系的运算。 在此基础上对基本粗糙集模型中的相关概念进行重新定义如下： 定义2 1 6 ：在与知识系统s = ( u ，a ，v ，厂) ) 对应的关系肆上，丑爿，且b ，对坼 中两个元组t u p l e l = ( v 。v 。一v 。) 和t u p l e 2 = ( v ：。，v ：2 ，v ：。) ，若v a f b 有v 。，= “则称 两个元组在日上是不可分辨的。 记， ，d 。为定义在b 上的不可分辨关系，i n d 。中每个元素都是一个元组集合，集合 内元组在b 对应分量上取值相等。 山东辩技人学硕士学位论文穗i 糙集壤论基础 定义2 1 7 ：在与知识系统s = ( u ，a ，v ，力对l 煎的关系墨上，存在一个选择，量r ， b a 称 ( b ( 盯r r ) = w ( y i n d 口| y 口r r ) )为 盯月r的下近似， r 一( 盯r r ) = u ( f i n d 8 yr 、盯* ，妒为盯r r 舱上近似，b n s ( 盯r r ) = 露一( 矿* r ) 一嚣( * r ) 为 仃。，的边界区域。 定义2 1 8 ：在与知识系统s = ( u ，a ，v ，) 对应的关系尺，上，有b 互a ，v e c b ，分别 构造两个关系r ；= ( 辫) 和晨；= ( 磁) ( 万表示投影) ，若i r ；闷r ， 飘lr ；| q r ；l 别称b 怒独立的。 定义2 i 9 ：在与躲识系统s = ( u ，a ，v ，厂) 对应的关系髓上，蛰b a ，b 是独立的，则 称雪是4 的一个约麓。 定义2 2 0 ：在与知识系统s = ( u ，a ，v ，厂) 对应的关系墨上，p ，q 量a ，q 的p 正域 p o s ，( q ) f g 义f f r j ： p o s e ( q ) 掌心s e t 托妇p s e t 轴乩一i n d , , ，n 3 s e t r q , l 。q i n d 曹嵌s e t 孤妇p s e t 托咖0 实际上定义2 2 0 给出了p o s 。( q ) 的计算方法。 2 6 本章小结 本