（计算机软件与理论专业论文）可变精度粗糙集合模型研究与应用.pdf

摘要 可变精度粗糙集合模型是经典租糙集理论的一个扩展模型，它是 在经典粗糙集合模型中引入了分类正确率，其分类是部分的。本文 首先比较全面地介绍了可变精度粗糙集合模型的基本概念，然后以此 为基础，对可变精度粗糙集合的以下几个重要问题进行了深入细致地 研究。 已知一个决策表，如何评价属性的重要性，关于这一问题目前已 有不少文献进行了相关研究，但这些研究多足针对经典粗糙集理论进 行的，本文讨论了基于可变精度粗糙集模型的属性重要性评价方法， 同时将该方法应用于组合预测中。 分类正确率和分类能力y 是可变精度粗糙集合模型的两个重要 参数。本文详细论述了两者的相互关系及相互影响，并提出了域观 点，试图以对域的研究代替传统的对特定值的关注。 属性约简是采用可变精度粗糙集合模型生成有效规则的关键。传 统的约简定义的核心是保持卢分类能力不变，笔者在研究中发现依 照该定义求得的约简存在规则不一致现象，并针对这一现象进行深入 研究，给出新的约简定义及相应的约简方法。核属性是采用启发式 式算法求解属性约简的关键。本文针对不相容决策表核属性的计算问 题，提出了两种基于粗糙集代数观的核属性计算新方法。 最后，本文还研究了基于可变精度粗糙集合理论的数据挖掘模 型，运用该模型并采用自行开发的系统对u c i 数据库中的m n e 数据 集进行仿真实验，实验结果比较理想。 关键词粗糙集，可变精度粗糙集合模型，属性约简，数据挖掘 a b s t r a c t t h e i r i a b i ep r e c i s i o n r o u 幽 s e tm o d e l( v p r s m )遗a g e n e m l i z a t i o no fm er o u 曲s e tt 1 1 e o r y ( r s t ) i td e a l sw i mp a r t i a l c i a s s i f i c a t i o nb yi n t r o d u c i n gap r o b a b i l i t yv a l u e w h i c hd e n o t e s l e p m p o r t i o n o fc o m j c tc l a s s i f i c a t i o n s 。h e r e ，i nt h i s p 印e r ，t h em a i n c o n c e p t so fv p r s ma r ei n t m d u c e df o m a l l y b a s e do nm e s e ，s o m e i m p o r t a mp m b l e m si nv p r s m a r ef o c u s e d h o wt oe s t i m a t em es i g n i f i c 锄c eo fa t t r i b u t e si nd e c i s i o nt a b l ei sa p o pp r o b l e m m a n yl i t e r a t u r e sh a v ea l r e a d yr e s e a r c h e do ni t w h i l et h e r e s e a r c h e sa r em o s t l yb a s e do nt 1 1 et r a d i t i o n a lr s t h e r ew eb r i n g f o n a r dan e wm e t h o db a s e do nv p r s ma n d 印p l yi tt 0t l l e c o m b i n a l i o n a lf o i e c a s t a i l d ，a r em oi m p o n a i l tp a r a m e t e r si nv p r s m s h o w st t l e p r o p o r t i o no fc o r r e c tc i a s s i f i c a t i o na r i d ，i sd e f i n e da sm eq u a l i t yo f c l a s s i f i c a t i o n w 色d i s c u s st h e m t e r r e l a t i o nb e t w e e nt l l e 觚os v m b o l sa n d g i v ea 一d o m a i nc o n c 印tt r 锄s f o m l i n gt h et r 甜i t i o n a lc o n c e p tb a s eo n t l l e v a l u e o f 卢t o m e d o m a i n o f t h en e e df o rt l l er e d u c ti si m p o r t a mt ot h ef i n a lo b j e c t i v eo f c o n s 1 j c t i n gas e r i e so fm l e st oc l a s s i 母t h eo b i e c t sm m ev p r s m t h e t r a d i t i o n a ld e 6 n i t i o no f - r e d u c ti s k e e p i n g t l l es 锄eq u a l i 哆o f c l a s s i f i c a t i o n w h i l ew ef i n ds o m e t i m e sm ed e f i n i t i o nw i l lc a u s e a b n o n i l i t ) r s oa c c o r d i n gt om ea b n o m i 够w es h o wan e w - r e d u c t d e f i n i t i o n t h ec o r ea t t r i b m e si st l l eb a s eo fm eh e u r i s t i ca l g o r i m m s i n t i l i sp 印e r a c c o r d i n gt om ep m b l e mo fc a l c u l a t i n gt 1 1 ec o r ea t t r i b u t e so f a nm c o n s i s t e n td e c i s i o n 协b l e ，铆on e wa l g o r i m m sa r ep r e s e m e d f i n a l l y ，w es h o wad a t am i n i n gm o d e lb a s e do nm ev p r s m a n d t l l e nw ea l s oa n a l y s et i l ew 【n ed a t as e t so fu c id a t a b a s eb yt i l em o d e l t h i se x p e r i m e n ts h o w sm em o d e l i su s e 如1 k e yw o r d sr o u 曲s e t ，v 撕a b i ep r e c i s i o nr o u 曲s e tm o d e l ， r e d u c t ，d a 协m i n i n g 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在在论文中作了明确的说 明。 作者签名： 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文；学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名： 导师签名：玉立丛西日期：丝g 年上月鲨日 硕十学伊论文 第一章绪论 第一章绪论 本章首先介绍了本论文的研究背景、研究成果及意义，最后对本文的组织结 构作了简明扼要的介绍。 1 1 课题研究的背景 信息产业是现代社会的三大支柱产业之一，信息是现代社会的基础，而数据 库技术则又是信息处理技术的基石。随着科技的发展，各种数据库规模越来越大， 数据库中数据越来越多，人们对数据库的应用己不能仅仅限于对数据库进行查询 和检索。仅用查询和检索已不能提取数据中满足用户需求的带有启发性和结论性 的信息，数据库中蕴涵的丰富知识在这种情况下也得不到充分的发掘和应用。数 据挖掘和知识发现【”】就是应目前的社会发展需要新崛起的一个活跃的研究领 域。 数据挖掘，作为数据库中知识发现的核心部分，运用统计分析、模糊集、粗 糙集、神经网络、遗传算法等方法从原始数据或处理后的数据中挖掘有价值的知 识和模式，指导人们的生产和实践。由于它挖掘出来的知识以较大的概率服从于 原数据，而同时其表现形式也较原数据简练、直观，因而在商业、企业、政府决 策等各个方面都表现了其突出的优势。 粗糙集( r 0 u g i is e t s ，r s ) 理论m 】( 下称经典粗糙集理论) 是2 0 世纪8 0 年 代初波兰数学家p a w l a k 提出的是一种用于处理不精确和不完整信息的数学工 具，常用于数据挖掘。由于该理论的处理对象主要为信息表，其概念与关系数据 表基本一致，且无需提供相关数据集合外的任何先验信息，适合于发现数据中隐 含的、潜在有用的规律，因此经典粗糙集理论和其它处理不精确与不确定性的方 法相比具有独特之处。尽管如此，该理论仍然存在某些片面性与不足之处。 在经典粗糙集理论中，“知识”被认为一种将现实或抽象的对象进行分类的 能力【5 l ，经典粗糙集理论是假设对于已知的对象全域拥有必要知识的前提之下进 行数据处理的。但一般而占，由于信息的缺乏，人们对知识的了解和认识往往不 够充分，已知的知识通常只够产生部分分类，经典租糙集理论可以处理这一类型 的分类，但要求分类必须是完全正确或可靠的，不可靠或不正确的分类不能采用 该方法解决。但事实上，现实世界中存在的分类规则往往不是完全可靠的，如果 对于大部分已知数据采用该规则导出的分类是正确的，那么这些包含部分错误的 分类规则就能提供有用的导向信息。例如：若9 0 德国制造的汽车属于高质量汽 硕十学伊论文第一章绪论 车，那么对于分类规则“德国制造汽车商质量”可以给予较高的可信度。换 言之，当我们已知一辆汽车为德国制造，即可推测该汽车质量好，同时可以肯定 这一推测的错误率较低( 1 0 ) 。由此可见，该分类规则可以提供有用的导向信 息，这些导向信息应该被提取并采用一定的方法进行分析，此时。若采用经典粗 糙集理论分析这些数据，那么这些导向信息则会被视为无用信息。也就是说，在 数据集中存在噪声等干扰情况下，经典理论会由于对数据的过拟合而使其对新信 息的预测能力大大地降低。而在实际应用中，噪声是在所难免的。基于这一考虑， 为增强粗糙集合模型的抗干扰能力，加拿大科学家z i a r k o 对经典粗糙集理论进 行扩展，于1 9 9 3 年提出了可变精度粗糙集模型( v a r i a b l ep r c c i s i o nr o u g i is e t m o d e l ，v p r s m 。简称v p r s m 或v p 模型) 1 8 9 “】。 可变精度粗糙集模型是在经典租糙集理论的基础上引入了分类正确率b ，即 允许一定程度的错误分类率存在，从而具有一定的容错性，增强了对噪声数据的 适应能力。因此，可变精度粗糙集合模型在对不确定信息的处理上具有较大的研 究空问。 1 2 本文的主要工作及研究成果 本文首先系统地介绍了数据挖掘、经典粗糙集相关理论和可变精度粗糙集合 模型的基本概念：然后分别就可变精度租糙集合模型的几个核心问题进行了深入 研究，主要包括：属性重要性、分类正确率、分类能力、属性约简及核属性计算 等；最后研究了可变精度租糙集模型在数据挖掘中的应用，并做了相关的仿真实 验。本文主要的研究成果列举如下。 ( 1 ) 讨论了基于可变精度租糙集模型的属性重要性评价方法，并将该方法 应用于组合预测中，将组合预测中的加权系数确定问题转化为可变精度裉糙集理 论属性重要性评价问题。仿真实验表明，基于可变精度粗糙集合模型的组合预测 方法计算量小、不带主观性、预测精度高。 ( 2 ) 详细论述了分类正确率与分类熊力之问的相互关系及楣互影响，提出 了域观点，以对卢域的研究代替传统的对单个值的关注。 ( 3 ) 针对不相容决策表核属性的计算问题，提出了两种基于粗糙集代数观 的核属性计算新方法，并分别与传统代数定义下以及信息熵定义下核属性计算方 法进行比较，分析了各方法之间的异同、相互日j 的关系及各方法的不同适应范围。 ( 4 ) 研究了可变精度粗糙集合模型的属性约简，指出依照z i a r k o 定义的约 简方法求得的约简存在与原决策表规则不一致现象，并对这一现象进行深入研 究，给出一种新的可变精度粗糙集约简定义及相应的约简方法。 2 硕士学付论文 第一章绪论 ( 5 ) 讨论了基于可变精度粗糙集的数据挖掘模型，并开发了基于该模型的 数据挖掘软件v r p s m d m ( 仅完成了论文相关的核心部分) ，并采用u c i 数据库 进行了仿真实验，实验结果比较理想。 以上研究进一步完善了可变精度粗糙集合模型的理论体系，使其可以更好地 处理不精确、不确定知识：开发的数据挖掘软件虽不够完善，但仍可为后继的研 究提供方便和借鉴，同时相关的仿真实验将有助于理论与实践相结合，扩大该模 型的应用范围。 1 3 本文的组织结构 本论文分为八章，第一章对本课题的研究背景、研究成果及意义和本文的组 织结构作了简明扼要的介绍；为了保持本文的相对独立性和完整性，第二章对本 文所涉及的理论，包括数据挖掘、经典粗糙集的相关理论以及可变精度粗糙集合 模型的基本概念和相关知识作了较为基础和全面的介绍；第三章讨论了基于可变 精度租糙集合模型的属性重要性测评方法，并将其应用于组合预测中；第四章， 研究可变精度粗糙集合模型中的两个重要参数分类正确率和分类能力，之间 的关系，提出了口域的新观点；第五章，研究不相容决策表的核属性计算，给出 了基于代数定义下的两种新的核属性计算算法；第六章，研究可变精度粗糙集合 模型属性约简，提出了一种新的属性约简定义及相应的约简方法；第七章，研究 可变精度粗糙集合模型在数据挖掘中的应用；最后，总结全文，并给出了关于可 变精度粗糙集合模型的进一步研究建议。 由于水平有限，错误与疏漏在所难免，敬请批评指正。 硕十学伊论文第：章理论概述 第二章理论概述 数据挖掘是应目前社会发展需要新崛起的一个活跃的研究领域，粗糙集理论 是数据挖掘的一个有效工具。经典粗糙集用完全包含来定义集合上近似集和下近 似集，其分类足精确的。可变精度租糙集合模型是经典粗糙集理论的一个扩展模 型，它是在经典粗糙集模型的基础上引入了分类正确率，即允许一定程度的错误 分类存在，从而增强了对噪声数据的适应性。本章作为全文的基础，分别对上述 理论进行了简明扼要的介绍。 2 1 数据挖掘概论 2 1 1 数据挖掘产生的背景 信息产业是现代社会的三大支柱产业之一，信息足现代社会的摹础，而数据 库技术则又是信息处理技术的基石。随着科技的发展，各种数据库规模越来越丈， 数据库中数据越来越多，人们对数据库的应用已不能仅仅限于对数据库进行查询 和检索。仅用查询和检索已不能提取数据中有利于用户实现目标的带有结论性的 信息，数据库中蕴涵的丰富知识在这种情况下足得不到充分的发掘和应用的。因 此迫切地要求新的知识发现工具来对数据进行分析、推理、发现数据间的联系、 提取有用特征、简化信息处理、减少信息的浪费进而推动社会的发展。因此研究 不精确、不确定知识的表达、学习、归纳等方法已成为智能信息处理中的重要研 究课题。 数据挖掘和知识发现l l 司就是应目i ； 的社会发展需要新崛起的一个活跃的研 究领域。知识发现这个术语首先出现在1 9 8 8 年美国第l l 届国际人工智能联合会 议的专题讨论会上。一般公认的定义为：从目标数据集中识别出有用的、新颖的、 潜在有用的，以及最终可理解的模式的高级( 非平凡) 过程。知识发现的对象主 要足数据库，因此我们也称知识发现为数据库知识发现( 鼬m w l c d g ed i s c o v e r yo f d a 咖嬲e ，k d d ) 。对于数据库来说，知识发现的研究内容是，能自动地去处理数 据库中大量的原始数据，从中挖掘搜索出具有必然性、富有意义的模式。 数据挖掘( d a t a m i n i n g ，d m ) 这个概念是进入9 0 年代才提出的，定义为从 大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其 中的、人们事先不知道的、但又是潜在有用的信息合知识的过程。一般说来，数 据挖掘是知识发现过程中一个核心步骤。在广义的概念下，二者并没有什么区别。 4 硕十学付论文 第j 二章理论概述 在本文中，对二者并没有加以区别。 2 1 2 数据挖掘模型 数据挖掘过程可粗略地理解为三个过程；数据准备、数据挖掘以及结果的解 释评估f l 埘。如图2 1 所示。 l数据准备阶段 i l数据挖掘阶段 l l结果评估与解释 图2 1 知识发现( 数据挖掘) 模型 ( 1 ) 数据准备 数据准备又可分为三个子步骤：数据选取、数据预处理和数据变换。数据选 取的目的是确定发现任务的操作对象，即目标数据，它是根据用户的需要从原始 数据库中抽取的一组数据。数据预处理一般可能包括消除噪声、推导出缺值数据、 消除重复记录、完成数据类型转换。数据预处理一般可能包括消除噪声、推导出 缺值数据、消除重复记录、完成数据类型转换。比如，把连续值数据转换为离散 型数据，以便于符号归纳，或是把离散型的转换为连续值，以便于神经网络分析。 在粗糙集理论中，由于处理的数据通常为离散型的，所以在这一步中通常是连续 值数据转换为离散型的数据。 ( 2 ) 数据挖掘阶段 数据挖掘阶段首先要确定挖掘的任务或者说是目的是什么，如数据总结、分 类、聚类、关联规则发现等。确定了挖掘任务后，就要决定使用什么样的挖掘算 法。同样的任务可以用不同的算法来实现，选择实现算法有两个考虑因素；一是 不同的数据有不同的特点，因此需要用与之相关的算法来挖掘；二是用户或实际 运行系统的要求，有的用户可能希望获取描述型的、容易理解的知识，这种情况 下采用规则表示的挖掘算法显然要好于神经网络之类的算法，而有的用户或者系 统的目的是获取预测准确度尽可能高的预测型知识。 粗糙集理论由于自身的特点，通常我们将它应用于分类任务研究。 完成了上述准备工作后，就可以实施数据挖掘操作了。需要说明的是，尽管 数据挖掘算法是知识发现的核心，也是目前研究人员的主要努力方向，但要获得 硕十学伊论文 第一= 章珲论概述 好的挖掘效果，必须对各种算法的要求、前提假设以及特点有充分的理解。 ( 3 ) 结果解释和评估 数据挖掘阶段发现出来的模式，经过用户或机器的评价，可能存在冗余或暂 无关的模式，这是需要将其剔除；也有可能模式不能满足用户要求，这时则需要 整个发现过程退回到发现阶段之前，如重新选择数据、采用新的数据处理算法， 设定新的数据挖掘参数值，甚至换一种挖掘算法( 比如说，有多种分类方法，不 同的方法对不同的数据有不同的效果) 。另外，知识发现由于最终足面向人类用 户的，因此可能要对发现的模式进行可视化，或者把结果转换为用户易懂的一种 表示，如把分类决策树转换为“i f t l l e n ”规则。 2 2 经典租糙集理论概述 粗糙集理论的数学基础是集合论，利用集合的上、下近似概念描述不确定性， 即利用不可分辨笑系导出的论域划分来描述论域的新子集。经典粗糙集用完全包 含来定义集合上近似集和下近似集，其分类足精确的。 2 2 1 经典粗糙集理论的基本概念 知识表达是智能信息系统的关键部分。基于粗糙集理论的知识发现，主要是 借助于信息表这样一种有效的数据表知识表达方式。 信息表知识表达系统( 简称信息系统) 的基本成分是研究对象的集合，关于 这些对象的知识是通过指定对象的属性( 特征) 和它们的属性值( 特征值) 来描 述的。 粗糙集理论利用信息系统来描述论域中的对象，它是一张二维表，每一行描 述一个对象，每一列描述对象的一个属性。 定义2 1 信息系统四= ( 【，4 ，y ，f ) ，其中u 为论域，彳为有限属性集合， 矿= u 圪：口4 是属性值的集合，圪为属性口4 的值域，f 是u 与彳的关系集， ，= ，：u _ 匕，口一 。 在粗糙集理论中，信息系统又称为信息表。 定义2 2 信息系统尽= ( u ，彳，矿，d ，v b 4 ，定义一个不可分辨关系 如= ( x ，j ，) ：无( x ) = 无) ，v 口毋，【x 】。= j ，：化y ) ) 为x 关于口的等价类。 【x 】( 为条件等价类，简称条件类；n l 为决策等价类，简称决策类。 不可分辨关系是二值关系，满足自反性、对称性、和传递性，显然该关系是 一等价关系，它揭示出论域知识的颗粒状结构，是租糙集理论的出发点。 定义2 3 信息系统俗= ( u ，爿，矿，f ) ，曰彳，【x 】。为x 关于曰的等价类，对 6 硕十学伊论文 第_ 二章理论概述 于 u ，集合x 关于口的下近似集和上近似集分别定义为： 尻( x ) = u 口】。：【x 】。x ， b ( x ) = u 口】口：b k n j 妒 a b f 抑实际上是由那些根据已有知识判断肯定属于x 的对象所组成的最大的 集合，也称为x 的正区或正域，记作p 0 s 口p 。b + 实际上是由所有与x 相交非 空的等价类，k 肠的并集，是那些可能属于x 的对象组成的最小集合。 由根据已有知识判断肯定不属于z 的对象组成的集合称为x 的负区或负域， 记作 ，e g f 殉。显然，砸g p p = 弘丑。口p 。 集合x 的边界区定义为：b n d ( x 产b 。( x ) b ( x ) 。 b j v d 为集合z 的上逼近与下逼近之差。如果脚，d 闭是空集，则称| 】| 关于 曰是精确的，即z 可表示为一定数量的防b 的并集：反之如果b m ) 圆不是空集， 则称集合x 为关于b 的粗糙集，并利用b 仞和占来近似。 决策表是一种特殊的信息系统，它表示当满足某种条件时，决策( 行为、操 作、控制) 应当如何进行。 定义2 4 决策表d r = ( u ，丘y ，f ) ，其中u 为论域，彳= c u d ，c 为有限 条件属性集合，d 为有限决策属性集合，d 妒，矿= u 圪：口椰是属性值的集 合，圪为属性口4 的值域，是u 与彳的关系集，= 坼：u 专圪，口椰。 一般地决策属性只有一个( 多个决策属性可以转换成一个决策属性) ，即 彳= c u 讲，其中d 芒c 为决策属性。 2 2 2 经典租糙集理论研究的主要问题 建立租糙集合模型，涉及到不完全信息的处理、连续属性的离散化、决策表 的约简、规则获取等问题。 ( 1 ) 不完全信息的处理 基于不可分辨关系的租糙集方法要求决策表是完全的，然而，不完全的数据 集是普遍存在的。处理不完全信息的主要方法是将不完全决策表转化为完全决策 表【1 2 】。方法主要有三种：a 将包含空值的对象删除；b 均值众数填入( 众数即 出现频率高的数或符号) ；c 组合填入，就是将每个对象的每个空值扩展成可 能值的集合，即一个对象扩展成几个对象，包含了所有对象空值的组合。 有关不完全信息的处理，仍是粗糙集应用的难点。 ( 2 ) 连续属性离散化 粗糙集理论的数学基础足集合论，难以直接处理连续的属性，故要求输入的 属性值是离散的。离散化改变了属性值的粒度，使我们“粗糙”地观察世界，可 以有效地减少信息表的大小，提高分类的准确性。连续属性的离散化的根本出发 7 硕十学伊论文 第二章理论概述 点是在尽量减少决策衷信息损失的前提下，得到简化的和浓缩的决策衷，以便用 粗糙集理论进行分析，获得决策所需要的知识。最优离散化问题己被证明足 n p h a r d 问题，但利用一些启发式算法可以得到较满意的结果。目前离散化策略 主要利用统计学、栉尔推理、信息熵和聚类技术【1 3 1 4 ，15 1 。 ( 3 ) 决策表约简 约简是粗糙集理论的核心问题之一。约简是原始数据属性集的一个子集，并 且这个子集和整个属性集的分类能力是一样的。约简通常不唯一，一个数据集的 所有约简可以通过构造辨别矩阵及辨别函数得到。但寻找所有约简或者最小约简 已经证明是n p - h a r d 问题i 嘲，解决这类问题的一般方法是启发式搜索m 。常用 的约简算法主要有：穷尽算法、属性重要性启发式算法【l s l 、互信息约简算法f 1 9 】、 动态约简算法【2 0 ，2 l 】、j o l l n s o n 贪婪算法【2 2 1 、遗传算法【引、二维约简算澍卅等。 约简是根糙集理论研究的热点和难点。 ( 4 ) 规则获取 从决策表中导出规则的主要问题是决定哪唑属性应包含在规则的前件部分。 获取规则最一般的方法是构造决策表的决策矩阵。基于不同测度的规则获取算法 有：缩小边界域【刖，在给定的阀值下保持正域【2 5 1 ，熵口6 1 等，这些算法提高了决策 舰则的泛化能力。m o l l e s t a d 和k o m o r o w s k i 提出了在粗糙集框架下可能性规则生 成的格搜索算法，并给出一组启发式搜索策略唧。s h 鲫和z i a l ( o 讨论了基于r s 的 从数据中发现规则的增量自适应算法【2 吼。 2 2 3 经典粗糙集理论的特点及应用 经典粗糙集理论与其它软计算方法相比有其独特之处( 5 i 。 ( 1 ) 不需要先验知识： ( 2 ) 是一个强大的数据分析工具； ( 3 ) 与模糊集分别刻划了不完备信息的两个方面。 r s 理论的生命力在于它具有较强的实用性，从诞生到现在虽然只有短短二 十年的时间，但已经在许多领域取得了令人鼓舞的成果。如：模式识别【2 9 l 、冲 突分析啪l 、决策分析口1 。3 1 、图像处理口4 1 、预测建模d 5 j 6 1 、结构建模p 7 1 等。 当前，r s 理论与其它软计算方法结合是应用研究的热点。主要的结合对象 有：模糊集、遗传算法、人工神经网纠3 8 越1 等。 2 3 可变精度租糙集合模型概述 可变精度租糙集足经典r o u 曲s e t 模型的扩展。经典r o u g hs e t 模型用精确集 8 颈十学伊论文 第一二章理论概述 合包含来定义上近似集和下近似集。其分类是完全的。v p r s m 在经典r s 模型 上引入了系数，用多数包含来定义上近似集和下近似集，其分类为部分 的，即允许一定程度的错误分类率存在。 2 3 1 可变精度租糙集合模型的基本概念 关于卢的取值有两种方式，z i a r k 0 【8 1 9 1 把定义为分类错误率，其取值范围 为( o ，o 5 】；而a n 等人【可则定义为分类正确率，其取值范围为( o 5 ，l 】，本文采 用后一种定义，当卢= l 时，经典r o i l g l ls e t 模型是v p r s m 的一个特例。 定义2 s 信息系统嚣= ( 彩，4 ，矿，f ) ，芦( o 5 ，l 】，君爿，记为u 上的不 可分辨关系，【胡。为x 关于b 的等价类，p ( x l 口】。) = 翻脚( xn 【x k ) 伽r d ( 【x 】。) ， 那么，对于啷u 和尺。，x 的下近似集和上近似集分别定义为： 鼠口x = u b k ：j p ( z f p k ) 2 p ； 曰；x = u p k ：尸( x l 【工k ) l 一卢 。 见。工实际上是由那些根据已有知识判断，以不小于罗的正确率属于z 的对 象所组成的最大的集合，也即p 正域，记作p o 酲( x ) 。足：x 实际上是由那些根 据已有知识判断，以不小于1 口的正确率属于z 的对象所组成的最大的集合。 由根据已有知识判断，以大于或等于口的正确率被排除在x 之外的对象组 成的集合称为x 的负域，记作脚f ( x ) ，定义为： e g g ( x ) = u 口b ：户( 【，一x l 口k ) ) 显然r ：x + 蜘善( 石) = 仉 集合x 的口边界域定义为： b r 善= u 【z k ：l 一p ( x l 叫b ) ) 。 显然，b n r 2 = 嘛x - r b x 图2 1 为可变精度粗糙集概念示意图。 图2 一l 可变精度粗链集模型示意图( = o 7 ) 9 硕十学仲论文 第二章理论概述 例2 i举例说明v p r s m 的基本概念。 表2 一l 为一决策表，论域u = o l ，0 2 ，0 3 ，0 4 ，0 5 ，0 6 ，0 7 ， 条件属性集合c c ，o ) ， 决策属性集合d e 田。 表2 1 一个决策表 ! 型! ! 堡 ! l望生 0 ，l1m 仍 l 0m ( b l lm 仉 o 1f ( b 1 of 伉 o0f d 710f 根据等价关系c = “o ) 分类，得 x l = 0 0 3 ， x 2 = 0 l o k d 7 ， j 6 = 0 4 ， 蜀= 仇) ； 同理，根据决策属性d 分类，得 y m = o ，0 _ 仍 y f = 瓯以以d 7 ； 根据上述定义，计算得 p ( 匕i z ) = c 删( n x 。) c 删( 五) = 尸( i 以) = p ( f 丘) = 1 ， j p ( i 置) = c 训( n 五) ，c 甜d ( 丘) = 1 ，3 = 0 3 3 3 ； 当o 5 5 时，得 尸畔”( ) = d l ，d 3 ， 删”( ) = 0 2 ，d 4 ，q ，d 6 ，d 7 ， 删”( ) = ； 当= o 7 时，得 p 删7 ( ) = q ，d ， ，心7 ( ) = d 4 ，仇 ，删7 ( ) = d 2 ，q ，0 7 。 2 3 2 可变精度粗糙集合模型的特点及应用 变精度粗糙集合模型不仅具备上述经典粗糙集合模型的全部特点，同时，与 1 0 硕+ 学位论文 第l 二章理论慨述 经典粗糙集合模型相比，它还具备其独有的特点。 ( 1 ) 经典粗糙集模型用精确集合包含来定义上近似集和下近似集，其分类 是完全的。可变精度粗糙集合模型在经典r s 模型上引入了系数，用多数包含 来定义上近似集和卢下近似集，其分类为部分的，即允许一定程度的错误分 类率存在。因此v p r s m 比经典r s 具有更强的容错性。 ( 2 ) 在数据分析应用中，v p r s m 的主要优势在于它能发现标准r s 中被认 为是独立的数据元素问的数据依赖关系。对于同一系列数据元素，采用标准r s 分析，元素日j 相互独立，无依赖关系，而采用v p r s 理论，则可能发现其间存在 数据依赖关系，这种情况往往发生在数据间无函数依赖时。在近似决策规则中发 现无函数或非决定性依赖特征是可变精度粗糙集合模型的主要特点。 ( 3 ) 经典粗糙集模型中，所有的知识都已经全部得到，最终通过算法处理 后得到的结论也仅限于被处理的论域中；可变精度粗糙集模型下，可以仅从少量 的样本中得到结果并把结论应用到更广泛的范围中。 ( 4 ) g r z i ，m a i a b 惦和z o u 比较了同时使用可能规则及确定规则和只使用 确定规则的性能，发现前者产生较小的错误率i l 碉。由于采用可变精度粗糙集理 论求得的规则为可能性规则，因此就产生有效规则这一点而言，可变精度粗糙集 理论将优于传统p a w l a r kz 粗糙集理论。 作为r s 理论的重要扩展，v p r s 由于产生较晚，关于其在各领域中应用的文 献不多，主要为决策分析【4 3 朋1 和预测建模【4 5 1 等，故其仍具有广泛的应用研究空间。 2 3 4 可变精度租糙集合模型的扩展模型 z i a r k o 等人在【1 0 ，1 1 1 中对v p r s m 的基本概念进行了扩展，即用不对称系数 f 和“来分别代替1 8 ，9 1 中的1 卢和卢，分别表示分类正确率的下限和上限，称为 不对称v p r s m 。现将其基本概念做如下简要介绍。 定义2 6 信息系统俗= ( 【，矿，f ) ，口彳， o ，o 5 ) ，材( o 5 ，l 】，如为 u 上的不可分辨关系，【工】。为工关于口的等价类，那么，对于锻u 和，集 合x 的正域、负域和边界域分别定义如下： 尸( ) 瓯( r ) = u 降k ：，( xj 【x 1 口) “ ； e g ，( x ) = u 恤k ：p ( u x i 【x k ) 2 l 一毋； b 蜀，= u 口k ：，以z i 陋k ) “ 显然，边界域中的对象因概率太小( _ f ) 而不能被排除在x 之外( 即x 负域) 。 堕兰堡垒茎一 笙三皇翌堡堕堕 2 4 本章小结 本章作为全文的基础，简明扼要地介绍了本文所涉及的基本理论，包括数据 挖掘、经典粗糙集理论和可变精度粗糙集合模型的基本概念及相关知识，并以简 单的例子予以说明。 硕十学 奇论文第= 章属性毛要性分析及其在组合预测中的府用 第三章属性重要性分析及其在组合预测中的应用 如何评价属性的重要性，目前已有不少文献进行了相关研究。但这些研究多 是针对经典粗糙集理论进行的，本章讨论了基于可变精度粗糙集模型的属性重要 性评价方法，同时将该方法应用于组合预测中，将组合预测中的加权系数确定问 题转化为可变精度粗糙集理论属性重要性评价问题。仿真实验表明，基于v p r s m 的组合预测方法计算量小、不带主观性、预测精度高。 3 1 经典粗糙集理论下的属性重要性判别 对于一个实际的应用系统，采用属性( 特征参数) 越多，描述越详尽，对 该应用系统的认识也越深刻。但大量的属性( 特征参数) 往往让用户无所适从， 如何发现及刻画该系统的主要属性( 特征参数) 是粗糙集研究的重要课题之一。 众所周知，用症状描述病人的情况、识别病人的健康状况时，有些症状会比其他 一些症状具有更重要的意义。在专家系统中，也会遇到类似的问题，即权重问题， 重要性高的属性在作决策时赋予大的权重。但是，若我们仅仅根据经验来选择权 重，这就依赖于人的先验知识，带有主观性，其可信度往往不高。利用租糙集理 论我们就可以对属性的重要性进行数值上的度量，这个度量是根据论域中的样例 来得到的，不依赖于人的先验知识i 舶i 。 定义3 1 决策表d r = ( u ，爿，y ，f ) ，4 = c u | d ，口s c ，决策属性集d 对 论域( ，的划分记作u = d l ，d 2 ，d ， ，那么，属性集b 对d 的分类能力定 义为： 二， ，( 鼠d ) = 芝：耐( 尻( d f ) ) 阳耐( u ) 百， 其中，d e u r 。，c n 耐( ) 为集合中的元素个数。 ，( b ，d ) 表示通过属性集合口被正确分类的对象的相对比率。分类能力又叫 近似质量，主要用于属性重要性分析和属性约简。 定义3 2 决策表d r = ( u ，彳，矿，f ) ，4 = c u d ，曰c ，( b ，d ) 为属性集b 对d 的分类能力，那么，属性子集占在属性集合c 中的重要性定义为： s ，g ( c ，口，d ) = ，( c ，d ) 一，( c 一口，d ) 。 该定义表示当我们从属性集c 中去掉属性子集b 后对分类能力的影响。 例3 1 计算表3 1 所示决策表中条件属性的属性重要性。 论域u = d ，仍，仍，仇，仍，仇 ， 硕十学伊论文 第j 章属性重要性分析及其任组合预测中的府用 条件属性集合c t c j ，o ，d ，臼 ，决策属性集合d = 田。 表3 i 一个决策表 根据定义3 2 计算属性c 的属性重要性，得 田g ( c ，c l ，d ) = ，( c ，d ) 一，( c c l ，d ) = 1 2 ，3 = l ，3 ； 同理，计算属性q 、c 3 、“的属性重要性，得 s i g c 2 现文f 3 ， s i g c h 印， s i g l c c 4 d _ 尸q 。 通过上述计算我们可以认为，属性c ，和。的霞要性相同，属性旬和臼的重 要性相同，且属性c ，和。的重要性要高于属性。和臼。但仔细观察表3 1 可以 发现，显然属性c ，对决策属性的影响力要大于属性旬，即属性c ，的蘑要性要高 于属性旬。由此看来，此方法难于细致地判断属性的重要程度，该方法还有待进 一步改进。 3 2 可变精度粗糙集合模型属性重要性判别 根据上节内容可知，经典基于粗糙集理论的属性重要性分析方法并不能准确 地判断属性的重要性，为此，本节我们提出了基于可变精度辊糙集合模型的属性 重要性判别方法。 定义3 3 决策表d 7 1 = ( u ，彳，矿，) ，一= c u d ，( 0 5 ，l 】，b 彳，决策 属性集d 对论域u 的划分记作u ，= d l ，d 2 ，d ， ，属性集b 对d 的分类 能力定义为： ， ，9 ( b ，d ) = c 口r d ( 尻，( 口) ) 如耐( u ) 扣i， 若对于r c ，有，4 ( c ，d ) = ，9 ( c 一 r ，d ) ，则称，为d 的可省略。 定义3 4 决策表d r = ( u ，一，矿，f ) ，彳= c u d ，( o 5 ，1 】，定义条件属性 集合c 去除属性r 后对分类的影响为：k ( c ， r ，) = 沪4 ( c ，d ) 一，4 ( c 一 r ) ，圳。 1 4 硕+ 学何论文第三章属性垂要性分析及其在钮合预测中的廊用 单属性 r 对分类的影响表示为：，4 ( r ，d ) 。那么，属性，c 的重要性定义为： 5 1 ，g ( c ， ， ，历= k ( c ， ， ，历+ ，( r ，d ) 由上式可知，册( c ， ， ，卢) 的值越大，表示该属性对分类的影响越大，因而 越重要。 例3 2 本例中我们仍以表3 1 为决策表，采用定义3 4 定义的属性重要性评 价方案进行分析。取口= o 5 5 ，计算得 s ，g ( c ，c l ，) = k ( c ， c l ，) + ，( c 1 ) ，) = l ，3 + l 6 = 1 ，2 ； 同理，计算得 5 ：，g ( c ，包，) = l ，3 + 2 3 = 1 ； 故可由此得出属性c ，的重要性低于o 。 3 3 基于可变精度粗糙集的组合预测模型 所谓组合预测，就是将不同的预测模型进行适当的组合，综合利用各种方法 所提供的信息，从而尽可能地提高预测精度。采用组合预测的关键是确定各个单 模型预测方法的加权系数。传统的方法有：相关分析、误差和最小、人工神经网 络、小波分析等【4 7 4 8 删。这些方法追求的都足某种精确，在理论分析方面是很有 用的。但在实际的定量预测中，这些方法由于包含矩阵求逆等运算，计算量非常 大，严重妨碍其在实际中的应用。粗糙集理论给我们提供了一种新的思路，即人 们应该在精确性的追求上后退一步，而力图在整体上把握事物的发展规律，追求 一种满意解而非最优解。依据这一思想，本节首先给出了一种基于标准粗糙集理 论的组合预测方法，将加权系数确定问题转化为标准粗糙集理论中属性重要性评 价问题，然后对该算法进行改进，通过引入目标函数，提出一种基于可变精度粗 糙集模型的寻找更优组合预测加权系数的新方法，该方法计算量小，预测精度高。 仿真结果表明，该方法是可行的。 3 3 1 组合预测模型 定义3 5 选用m 种不同的预测方法c 。，c ：，c ，分别对已知预测对象j ，的一 个历史数据弘( f = l ，2 ，哟进行预测，设第f 种预测方法的第f 个预测值为兀 o = i z ，埘；r = i ，2 ，甩) ， u = l ，2 ，肼；) 为第，种预测方法的权系数。那么， 组合预测模型定义为： t = 九t ，。 ， i 若各个预测方法的权系数丑( 扛l ，2 ，m ；) 已知，则可以根据定义3 5 对y 进 硕十学伊论文第二章属性草耍性分析及其在组合预测中的府用 行预测。 3 3 2 目标函数 通常，采用目标函数来检验预测结果优劣，常用的目标函数有：误差平方和 最小、绝对误差和最小、绝对百分误差和最小等。本文以平均绝对百分误差最小 作为目标。 定义3 6 选用m 种不同的预测方法c l ，c 2 ，c 。分别对已知预测对象y 的疗 个历史数据y ，o = 1 ，2 ，行) 进行预测，设第i 种预测方法的第f 个预测值为兀 ( f ；l ，2 ，脚；f = l ，2 ，盯) ，丑( f = 1 ，2 ，用；) 为第f 种预测方法的权系数。那么， 目标函数定义如下： 下面将在算法3 2 中对上述目标函数求解，当其取到最小值( 或满足实际需 要) 时的权系数丑( f = l ，2 ，肌；) 即为所求权系数。显然通过定义3 6 给出的目标 函数可以达到优化求精的目的。 3 4 组合预测模型中加权系数确定算法 算法3 1 组合预测模型中加权系数确定算法( 基于标准r s ) 输入：预测对象y 的各个单模型预测值； 输出