（计算数学专业论文）基于粗糙集理论的不完备信息系统属性约简研究.pdf

基于粗糙集理论的不完备信息系统属性约简研究 基于粗糙集理论的不完备信息系统属性约简研究 计算数学专业 研究生阳恋指导教师冯山 摘要：数据挖掘是目前信息决策领域最前沿的研究方向之一，它融合了机 器学习、神经网络、模式识别、粗糙集等多种理论及技术。粗糙集理论是一种 处理不精确、不确定知识的数学方法，近年来，因其在模式识别、数据挖掘、 决策分析等方面的广泛应用而备受关注。经典粗糙集理论以等价关系为基础， 它假设每个对象的所有属性值都已知。然而不完备信息系统大量存在此时， 由于等价关系不再成立，经典粗糙集模型的应用受到限制。因此，如何在不完 备信息系统中进行数据挖掘，特别是在尽量不改变原系统信息成分的前提下从 信息系统中获取知识是一个重要的研究课题。 本文主要研究不完各信息系统下的属性约简方法。首先，对数据挖掘和经 典粗糙集理论作了系统阐述。其次，对不完备信息系统中的几种粗糙集扩展模 型及其属性约简算法进行了分析和比较。再次，将粒度计算理论与粗糙集理论 相结合，给出了不完备信息系统下的一种知识约简算法。最后，给出了不完备 信息系统下知识和粗集不确定性度量的一种新方法，该定义考虑到了边界域对 不确定性的影响。它为不完备信息系统下的属性约简和知识获耿提供了有力工 具。 关键词：数据挖掘；粗糙集理论：不完备信息系统：属性约简；粒度理论； 不确定性 s t u d yo i la t t r i b u t er e d u c t i o ni ni n c o m p l e t e i n f o r m a t i o ns y s t e m sb a s e d r o u g h s e tt h e o r y m a j o rc o m p u t em a t h e m a t i c s g r a d u a t es t u d e n t y a n gl i a ns u p e r v i s o rf e n gs h a h a b s t r a c t ：p r e s e n t l y , o n eo ft h ef r o n t e s td i r e c t i o n si n i n f o r m a t i o n d e c i s i o n - m a k i n gr e s e a r c hi st h ed a t am i n i n gi nw h i c hm a n yk i n d so ft h e o r i e sa n d t e c h n o l o g i e sa r ec o m b i n e ds u c ha st h em a c h i n el e a r n i n g ，t h en e u r a ln e t w o r k ，t h e p a t t e r nr e c o g n i t i o n ，r o u g hs e t ，a n ds oo n r o u g hs e tt h e o r yi sak i n do fm a t h e m a t i c a l m e t h o du s e dt op r o c e s si m p r e c i s ea n di n d e f i n i t ek n o w l e d g e i nr e c e n ty e a r s ，r o u g h s e tt h e o r yi sn o t i c e dh i g h l yb e c a u s eo fi t sw i d e l ya p p l i c a t i o n si ns u c ht h ef i e l d sa s p a t t e r nr e c o g n i t i o n ，d a t am i n i n g , a n dd e c i s i o na n a l y s i s i nt h ec l a s s i cr o u g hs e tt h e o r y , e q u i v a l e n tr e l a t i o n s h i pi st a k e na sf o u n d a t i o na n da 1 1t h ea t t r i b u t ev a l u eo fe v e r y o b j e c ti nt h ed o m a i ni ss u p p o s e dt ob ek n o w n h o w e v e r , i n c o m p l e t ei n f o r m a t i o n s y s t e me x i s t sm a s s i v e l yi nd a t am i n i n g , w h i c hr e s t r i c t e st h ea p p l i c a t i o no fc l a s s i c r o u g hs e tt h e o r ys i n c et h et r a d i t i o n a le q u i v a l e n tr e l a t i o n s h i pn ol o n g e re x i s t s t h e r e f o r e ，h o wt oc a r r i e so nd a t am i n i n gf r o ma ni n c o m p l e t ei n f o r m a t i o ns y s t e m ， e s p e c i a l l yc a r r i e so nd a t am i n i n gw h i l en o tc h a n g i n gt h ei n c o m p l e t ei n f o r m a t i o n s y s t e mm e n t i o n e da b o v ei sas i g n if i c a n tr e s e a r c ht a s k a t t r i b u t er e d u c t i o nm e t h o d so fi n c o m p l e t ei n f o r m a t i o ns y s t e m sa r et h em a i n c o n t e n t st ob er e s e a r c h e di nt h i sp a p e r f i r s t l y , d a t am i n i n ga n dc l a s s i cr o u g hs e t t h e o r ya r ee l a b o r a t e ds y s t e m a t i c a l l y s e c o n d l y , s o m ee x t e n d e dm o d e l so fr o u g hs e t t h e o r ya n dt h ea t t r i b u t er e d u c t i o na l g o r i t h m so fi n c o m p l e t ei n f o r m a t i o ns y s t e ma r e a n a l y s e d a n d c o m p a r e d f u r t h e r m o r e ，ar e d u c t i o na l g o r i t h mo fi n c o m p l e t e i n f o r m a t i o ns y s t e m si sp r e s e n t e db a s e do nb o t hg r a n u l a rc o m p u t i n gt h e o r ya n d r o u g hs e tt h e o r y f i n a l l y , an e wm e a s u r e m e n tm e t h o df o r u n c e r t a i n t y a b o u t n 基于粗糙集理论的不完备信息系统属性约简研究 k n o w l e d g ea n dr o u g hs e to fi n c o m p l e t ei n f o r m a t i o ns y s t e m si sp r e s e n t e d t h e i n f l u e n c eo fb o u n d a r yr e g i o nt ou n c e r t a i n t yi sc o n s i d e r e db yt h en e wd e f i n i t i o n w h i c hp r o v i d e sa ne f f e c t i v et o o lf o rt h ea t t r i b u t er e d u c t i o na n dt h ek n o w l e d g e a c q u i s i t i o no fi n c o m p l e t ei n f o r m a t i o ns y s t e m s k e y w o r d s ：d a t am i n i n g ；r o u g hs e tt h e o r y ；i n c o m p l e t ei n f o r m a t i o ns y s t e m s ； a t t r i b u t er e d u c t i o n ；g r a n u l a r t h e o r y ；u n c e r t a i n t y 四川师范大学学位论文独创性及 使用授权声明 本人声明：所呈交学位论文，是本人在导师迢出指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含任 何其他个人或集体已经发表或撰写过的作品或成果。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。 本人承诺：已提交的学位论文电子版与论文纸本的内容一致。如因不符而 引起的学术声誉上的损失由本人自负。 本人同意所撰写学位论文的使用授权遵照学校的管理规定： 学校作为申请学位的条件之一，学位论文著作权拥有者须授权所在大学拥 有学位论文的部分使用权，即：1 ) 已获学位的研究生必须按学校规定提交印 刷版和电子版学位论文，可以将学位论文的全部或部分内容编入有关数据库进 行检索；2 ) 为教学和科研目的，学校可以将公开的学位论文或解密后的学位 论文作为资料在图书馆、资料室等场所或在校园网上供校内师生阅读、浏览。 论文作者签名：p 国恋 2 。8 年4 月日 基于粗糙集理论的不完备信息系统属性约简研究 第一章绪论 数据挖掘出现于二十世纪八十年代后期，是目前数据库和信息决策领域最 前沿的研究方向之一。它不仅仅是对数据集的一些简单检索和调用，而是要对 这些数据进行微观、中观乃至宏观的统计、分析、综合和判断推理，以指导实 际的应用问题，发现事件间的相互联系和客观规律，对未来的活动进行预测。 粗糙集理论作为一种处理含糊性和不确定性的新的数学方法，是由波兰学 者z p a w l a k 于上世纪八十年代初提出的。它根据对一个系统观察和测量所得的 数据信息，从分类的观点，以集合近似和不可区分的概念为基础，通过粗糙集 简化方法，确定给定问题的知识约简，导出问题的决策或分类规则，为信息系 统或决策系统提供潜在知识和决策支持。近年来，随着理论的不断完善及在数 据挖掘中的成功应用，粗糙集理论受到了国际上的广泛关注。 1 1 数据挖掘概述 1 1 1 数据挖掘的产生背景及概念 随着计算机技术和信息技术的发展，信息量呈现出超指数趋势的急剧增 长，基于传统数据库技术的数据信息检索查询机制和统计分析方法已远远不能 满足现实需要，许多数据还来不及分析就已经过时了，即使没有过时，也有许 多数据因其数据量极大而难以分析数据间的关系。面对海量的存储数据，如何 从中发现有价值的信息或知识成为一项非常艰巨的任务，数据挖掘技术就是为 迎合这种需求而产生并迅速发展起来的。 由于数据挖掘的研究历史较短，迄今为止，对于数据挖掘的定义还没有完 全统一。一般地，可以从广义和狭义两个方面对数据挖掘进行定义：广义的 观点定义数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的数据集 中识别有效的、潜在有用的，以及最终可理解的模式的非平凡过程；狭义的观 点定义数据挖掘是从特定形成的数据集中提炼知识的过程。 数据挖掘的概念也可从商业角度进行定义口3 ，即定义数据挖掘是一种新的 商业信息处理技术，其主要特点是对商业数据库中的大量业务数据进行抽取、 转换、分析和其它模型化处理，从中提取辅助商业决策的关键性数据。 数据挖掘常常被视为数据库知识发现的同义词，也有学者认为数据挖掘仅 基于粗糙集理论的不完备信息系统属性约简研究 仅是数据库知识发现过程中的一个重要步骤1 。数据库知识发现一般在科研领 域使用较多，在工程应用领域多使用数据挖掘一词。 1 1 2 数据挖掘的过程 数据挖掘的过程可以粗略地分为三个阶段：数据准备，数据挖掘和结果的 评估与解释。 数据准备阶段 数据准备阶段是数据挖掘的基础，数据准备工作的好坏直接影响到数据挖 掘的效率和准确率，以及最终模式的有效性。数据准备工作一般包括数据选取、 数据预处理和数据变换。数据选取的目的是确定数据挖掘任务相关的操作对 象，即目标数据；数据预处理一般包括消除噪声、推导计算缺失数据、消除重 复记录以及完成数据类型转换等；数据变换是指将源数据格式转换成适合挖掘 的形式。 数据挖掘阶段 数据挖掘阶段是数据挖掘过程中最为核心的一步，该阶段采用数据挖掘算 法提取数据模式。数据挖掘任务一般可以分两类：描述和预测。描述性挖掘任 务刻画数据的一般特性；预测性挖掘任务在当前数据上进行推断，以进行预测。 结果的评估与解释阶段 对数据挖掘阶段得到的模式的实用价值进行模式评估，以确定哪些是有效 的、有意义的模式。最后需要以一种易于理解的方式将模式呈现给用户，并对 得到的结果做相关解释和描述。 1 1 3 数据挖掘的应用领域 从数据挖掘的产生背景可以看出，数据挖掘技术一开始就是面向应用的， 如金融、电信、零售、生物医学等领域。目前，国内外的研究人员都在加紧研 制有关领域的数据挖掘工具，不断扩大数据挖掘技术的应用领域。以下是几个 数据挖掘的典型应用领域口，： 金融业 数据挖掘在金融领域应用广泛，包括金融市场分析和预测、客户分类、银 2 基于粗糙集理论的不完备信启、系统属性约简研究 行担保和信用评估等。这些金融业务的处理都需要收集和处理大量数据，很难 通过人工的方法或使用一般的软件进行分析和预测，而数据挖掘技术通过对已 有数据的模式提取，找到数据对象的特征及彼此之间的关系。如利用聚类分析、 估计及预测等方法对客户进行分类以阻止产生坏账及防范金融欺诈，也可进行 市场动向分析和预测金融市场的变化趋势。 保险业 保险是一项风险业务，保险公司的一个重要工作就是对风险进行评估。在 保险公司建立的保单及索赔信息数据库的基础上，可以利用数据挖掘技术进行 风险分析，寻找风险较大的保险领域，获取一些实用的风险规则以指导保险公 司业务中的决策工作。 通信网络管理 在通信网络运行过程中可能产生一系列警告，有的警告如果不及时采取措 施进行处理，会带来不可挽回的损失。哪些警告可以不予理睬，哪些警告必须 迅速处理，这往往很难判断。一般需要由人工根据经验来进行处理，效率不高。 通过数据挖掘技术对己发生过的警告信息的正确处理方法以及警告之间的前 后关系进行分析，获得警告之间的关联规则，可提高警告的处理效率，确保网 络运行顺畅。 其他领域 零售业利用数据挖掘进行促销活动的有效性分析、货篮子分析和顾客的保 持力与忠诚度分析；市场营销领域将数据挖掘用于市场策略、市场定位和购物 模式等分析；制药业通过挖掘巨大的化学物质和基因对疾病的影响的数据库来 判断哪些物质可能对治疗某种疾病产生疗效；信用卡公司可以使用数据挖掘来 增加信用卡的应用，做购买授权决定、分析持卡人的购买行为、并侦测欺诈行 为等。 1 1 4 数据挖掘理论与技术的研究展望 作为一个新兴的领域，数据挖掘在理论研究和技术应用方面都面临着许多 挑战，有待进一步的发展和完善，主要涉及以下几方面叫j ： 可视化数据挖掘。可视化是数据挖掘的研究方向之一，是从大量数据中 基于粗糙集理论的不完备信息系统属性约简研究 发现知识的有效途径。挖掘出来的各种规则是否能以一种简明的、图形化的方 式表达给终端用户，将直接影响用户对数据挖掘技术的兴趣，也将直接影响到 这门技术的发展前景。多位数据的可视化、多位数据挖掘任务的可视化、模式 可视化、模式比较和分析可视化是数据挖掘在可视化方面的进一步研究目标。 数据挖掘中的安全性问题。随着数据挖掘工具和电信与计算机网络的日 益普及，数据挖掘要面对的一个重要问题是隐私保护和信息安全。需要进一步 开发有关方法，以便在适当的信息访问和挖掘过程中确保隐私保护和信息安 全。 o w e b 挖掘。随着计算机硬件和软件的升级，w e b 数据的结构也将会发生变 化，数据量将会更多更复杂，有关w e b 内容挖掘、w e b 日志挖掘和因特网上的数 据挖掘服务，将成为数据挖掘中一个最为重要和繁荣的子领域。 可伸缩的数据挖掘方法。与传统的数据分析方法相比，数据挖掘必须能 够有效的处理大量数据，而且尽可能是交互式的。由于数据量在不断的激增， 因此针对单独的和集成的数据挖掘功能的可伸缩算法显得十分重要。 复杂数据类型挖掘的新方法。复杂数据类型挖掘是数据挖掘中一项重要 的前沿研究课题，目前已在地理空间挖掘、多媒体挖掘、时序挖掘、序列挖掘 以及文本挖掘方面取得一些进展，但它们与实际应用的需要仍存在很大距离， 需要作进一步的研究。 数据挖掘算法。为了提高数据挖掘系统的可用性、可扩展性、高效性， 及其在新知识环境下的适应性，对现有数据挖掘算法的改进和新的数据挖掘算 法的探索将是未来数据挖掘领域的研究热点。 1 2 粗糙集理论概述 1 2 1 粗糙集理论的发展概况 粗糙集理论是波兰数学家z p a w l a k 为开发自动规则生成系统及研究软计 算问题于1 9 8 2 年提出的【副。由于最初关于粗糙集理论的研究大部分是用波兰文 发表的，因此当时并未引起国际学术界的重视，研究区域仅限于东欧各国。直 n s o 年代末，这一理论才引起各国学者的注意。9 0 年代初，人们才逐渐认识到 它的重要性。 4 基于粗糙集理论的不完备信息系统属性约简研究 1 9 9 1 年，z p a w l a k 出版了第一本关于粗糙集理论的专著3 ，为粗糙集理论 的发展奠定了基础。1 9 9 2 年，r s l o w i n s k i 出版了关于粗糙集应用研究的论文 集 1 ，推动了国际上对粗糙集理论与应用的深入研究。1 9 9 5 年，z p a w l a k 概括 性地介绍了粗糙集理论的基本概念及具体研究进展1 ，对粗糙集的研究工作和 成果作了极好的总结。自1 9 9 2 年以来，每年都有以粗糙集为主题的国际会议召 开，推动了粗糙集理论的进一步发展。2 0 0 3 年1 0 月，第九界“粗糙集、模糊集、 数据挖掘与粒度计算国际会议( r s d f g r c ) ”在重庆邮电学院成功召开，此 次学术会议涉及的研究领域包括粗糙集理论、模糊集理论、神经网络、进化计 算、数据挖掘、模式识别、网络智能等。2 0 0 4 ，年第四界粗糙集与计算趋势的 专题国际会议( r s c t c ) 在挪威b i o n i n f o r m a t i c su p p s a l au n i v e r s i t y 召开。 我国从1 9 9 4 年开始对粗糙集理论进行研究，主要讨论了它的数学性质和有 效算法，如粗糙集理论的知识表示、知识约简算法、粗糙逻辑等旧3 。为了促进 这一理论在中国的发展，2 0 0 1 年5 月，“第一届粗糙集与软计算学术研讨会”在 重庆邮电学院召开，此后每年召开一次，国内外知名专家学者都有出席会议， 共同探讨和交流粗糙集方法的理论研究和实际应用。 现在，粗糙集理论已成为人工智能领域中的研究热点之一，其在医疗诊断、 经济、金融、商业、环保、工程设计、信息科学、决策分析、分子生物学和材 料科学等诸多领域的应用均取得了可喜的成绩n 。 1 2 2 粗糙集理论的特点 粗糙集理论从诞生到现在虽然时间很短，但发展很快。作为一种新兴的数 据挖掘工具，粗糙集理论具有以下一些特点m 1 ，使得它适用于数据分析： 粗糙集理论应用于数据挖掘领域时，其处理数据对象所采用的信息表与 关系数据库中的关系数据模型相似，使得将粗糙集的相关算法嵌入到关系数据 库管理系统中非常方便；同时，粗糙集理论完善的数学理论基础便于更深刻地 揭示问题的本质，也可作为数据库知识发现过程开发的理论基础。 粗糙集理论认为知识的粒度是造成使用已有知识不能精确表示某些概 念的原因。它通过不可区分关系来衡量知识粒度大小。粒度越小，刻画分类越 精确；粒度越大，分类的模糊性越大。 基于粗糙集理论的不完备信息系统属性约简研究 粗糙集理论使用两个精确集( 上近似集和下近似集) 来描述不精确概念。 上近似集包含可能属于该概念的元素，下近似集包含一定属于该概念的元素。 粗糙集理论能求得知识的最小表达和知识的各种不同颗粒层次。上、下 近似的差集即是该概念的边界，包含不能肯定是否属于该概念的元素。边界体 现概念的模糊性。 粗糙集理论能够对属性和属性值进行约简。它在不降低分类精度的条件 下，识别和删除冗余的、不相关的数据，仅保留关键信息，并求得知识的最小 表达。 运用粗糙集理论时，无需提供除数据本身以外的任何先验信息，避免了 主观因素的影响。 粗糙集理论下的数据挖掘算法适合于并行执行，极大地提高了大数据集 的数据挖掘效率。 1 2 3 粗糙集理论的研究现状 目前，国内外对粗糙集理论的研究主要集中在粗糙集模型的扩展、与其它 处理不确定问题的理论的关系、有效算法、与其它数学理论的联系及粗糙集理 论的度量等方面n 2 1 钔： 在粗糙集的模型扩展方面，研究内容主要涉及模糊粗糙集模型、变精度 粗糙集模型、不完备信息系统下的粗糙集模型、基于一般关系的粗糙集模型及 基于优先关系的粗糙集模型等。 在研究粗糙集理论与其它处理不确定性问题的理论的关系时，主要讨论 它与模糊数学、模糊统计、证据理论和信息论的相互渗透与补充。 关于有效算法的研究，主要体现在约简的启发式算法、并行算法、遗传 算法及导出规则的增量式算法等方面。 与其它数学理论的联系方面，主要研究粗糙结构与代数结构、拓扑结构 和序结构的融合，并获得了一些成果，如粗糙逻辑、粗糙理想、粗糙半群等新 的数学概念的不断涌现。 在粗糙集度量方面，研究主要集中在知识不确定性度量、粗糙集数据分 析中的度量、粗糙集与粗糙关系数据库的信息度量等。 6 基于粗糙集理论的不完备信息系统属性约简研究 1 2 4 粗糙集理论的应用及发展前景 粗糙集理论的生命力正是在于它具有很强的实用性3 ，仅二十多年的发展 时间，便在诸多领域取得了令人鼓舞的成果，例如：在模式识别方面，文 1 5 应用粗糙集方法研究手写字符识别问题，提出了特征属性；在医疗诊断方面， 粗糙集方法根据以往的病例归纳出诊断规则，用来指导新的病例，例如，现有 的人工预测早产的准确率只有1 7 至3 8 ，而利用粗糙集理论可提高到6 8 至 9 0 n 6 1 ；在股票数据分析方面，文 1 7 应用粗糙集方法分析了十年间股票的历 史数据，研究了股票价格与经济指数之间的依赖关系，获得的预测规则得到了 华尔街证券交易专家的认可；在决策分析方面，粗糙集允许决策对象中存在一 些不太明确、不太完整的属性，弥补了常规决策方法的不足n 引。 粗糙集理论以其独特的优势和广泛的应用正在赢得越来越多的研究者的 青睐，围绕其在数据挖掘和智能计算方面的应用，今后的研究热点将主要集中 在以下几方面u 引： 大数据集的处理。随着信息技术的发展，现实中的数据库越来越大，如 何应付这一挑战是粗糙集理论面临的一个问题，虽然现在已有一些探索，- 但是 还没有找到一种令人满意的方法。 高效的约简算法。高效的约简算法是粗糙集应用于知识发现的基础，目 前还不存在一种非常有效的方法，因此寻求快速的约简算法仍然是粗糙集理论 的主要研究方向之一。 多方法的融合。实验表明，虽然现在有多种数据挖掘技术，却没有一种 能在所有的测试集上都比其它技术表现出色，因此多方法的融合可能是进一步 提高分类效率的方法之一。 1 3 不完备信息系统中知识获取的研究现状 在对样本数据进行处理时，某些样本的属性值可能会遗失，这些遗失的属 性值称为缺失值或未知值( 即遗失数据) 。我们把含有缺失值的信息系统称为 不完备信息系统，否则称为完备信息系统。粗糙集理论以信息系统作为研究对 象，z p a w l a k 提出的经典粗糙集理论是基于完备信息系统的，为了使该理论适 合于不完备信息系统，传统的做法是先对缺失值进行处理，将不完备信息系统 基于粗糙集理论的不完备信息系统属性约简研究 转化为完备信息系统，再应用经典粗糙集理论对数据进行处理。处理缺失值的 方法一般有两种：一种是删去带有缺失值的对象，另一种是用最可能的取值来 代替缺失值。由于缺乏对缺失值的直接处理，前一种方法会丢失其它属性值提 供的有用信息，使获得的规则失去了一定的可信度；后一种方法可能产生错误 的推断，使得获得的规则不正确。因此，有必要对经典粗糙集理论进行扩充， 使之能够直接处理不完备信息系统，从不完备信息系统中直接获取知识。 1 9 9 7 年，m k r y s k i e w i c z 提出了不完备信息系统的基于相容关系的粗糙集 模型及其知识约简算法啪。，为粗糙集的实用化迈出了可喜的一步。同时，在文 2 1 中m k r y s k i e w i c z 还对几种不完备信息系统的数据分析方法作了比较，得 出如下结论：( 1 ) 如果一个规则在原不完备信息系统的每个完备拓展中是确定 的，则该规则是确定的；( 2 ) 从不完备决策表中删除包含空值的对象后，挖掘 的知识可能为伪规则( 即对原不完备系统不一定成立) 。 1 9 9 9 年，j s t e f a n o w s k i 等人区分了不完备信息系统的两个不同语义：“遗 失值 和“缺省值 ，引入了非对称相似关系“缺省值 语义，并在此基础上 提出了基于非对称相似关系的粗糙集扩展模型1 。2 0 0 1 年，j s t e f a n o w s k i 又 提出了基于量化容差关系的粗糙集模型口朝。 2 0 0 2 年，王国胤在对以上三个模型进行分析的基础上提出了基于限制容差 关系的粗糙集扩展模型乜4 1 。而基于m k r y s k i e w i c z 的容差关系，文 2 5 将传统 的粗糙集理论在不完备信息系统下进行了初步的拓展，文 2 6 提出了不完备信 息系统下的变精度粗糙集模型。 虽然国内外众多学者对不完备信息系统中的缺失值做了大量研究，但基于 粗糙集理论的不完备信息系统的研究还很薄弱，对如何利用粗糙集方法从不完 备信息系统中获取有用知识的探讨仍具有重要的理论和现实意义，特别是在不 改变原信息系统的前提下从不完备信息系统中获取知识的理论与方法仍是未 来粗糙集理论研究的重点。 1 4 本文的组织结构 本文主要基于粗糙集理论对不完备信息系统的属性约简作了探究，具体组 织结构如下： 基于粗糙集理论的不完备信息系统属性约简研究 第一章：从数据挖掘的产生背景及概念、挖掘过程、应用领域等方面对数 据挖掘的相关知识作了详细阐述，并对粗糙集理论的发展历程、特点与应用、 研究现状与发展前景作了总结，最后概括介绍了不完备信息系统中知识获取的 研究现状。 第二章：系统讨论了粗糙集理论的基本概念及基于粗糙集理论的完备信息 系统的属性约简算法。 第三章：主要阐述了经典粗糙集模型在不完备信息系统中的几种扩展模 型，对它们的优缺点作了比较分析；接着研究了几种直接处理不完备信息系统 属性约简的方法。 第四章：基于粗糙集理论，借鉴粒度计算的一些思想与方法，重新定义了 不完备信息系统中属性的重要度，设计了不完备信息表及不完备决策表的一种 启发式约简算法，并对算法的时间复杂度作了分析，最后通过实例说明了算法 的有效性。 第五章：基于一般二元关系，结合信息论观点，重新定义了不完备信启、系 统中知识粗糙熵和粗集粗糙熵的概念。新定义区别于传统的以整个论域为基础 定义的粗糙熵，考虑到了边界域对知识和粗集不确定性的影响，从而更准确的 度量了知识和粗集的不确定性。同时，论文给出了新定义的粗糙熵的基本性质， 为在不完备信息系统下更加准确地获取知识提供了理论依据。 最后，对论文工作进行了总结，对后续研究作了展望。 9 基于粗糙集理论的不完备信息系统属性约简研究 第二章粗糙集理论 粗糙集理论因其在数据挖掘方面的成功应用而备受关注，己发展成为数据 挖掘和数据库知识发现研究领域中的重要分支乜引。其主要思想是在保持知识库 分类能力不变的前提下，导出问题的决策和分类规则。本章主要讨论z p a w l a k 经典粗糙集理论中的一些基本概念和基本算法，为后面各章节作准备。 2 1 基本概念 粗糙集理论是建立在分类的机制上的，与模糊集理论和证据理论相比，它 最大的优点是在处理不确定性问题时不需要关于数据的任何先验信息，对不确 定性问题的描述比较客观。 2 1 1 信息系统和不可区分关系 基于粗糙集理论的数据挖掘研究的主要对象是以表格形式表述的一个信 息系统。 定义2 1 1 c 5 】一个知识表达系统是一个四元有序组s = ( u ，a ，v ，厂) ，其中 u 是论域，是对象的非空有限集合；一是属性集合；v 是属性值的集合， vj u 。v o ，圪为属性a 的值域：f ：u x a - v 是一个信息函数，它为每个对 象的每个属性赋予一个信息值，即v a a ，x u ，f ( x ，a ) 圪。 知识表达系统也称为信息系统或信息表，通常简记为s = ( u ，a ) 。 定义2 1 2 设信息系统s = ( u ，a ) ，a = c u d ，c n d = 矿，c 为条件属性 集，d 为决策属性集。具有条件属性和决策属性的信息系统称为决策系统或决 策表。 信息系统的数据以关系表的形式表示。关系表的行对应研究对象，列对应 对象的属性，对象的信息通过指定对象的各属性值来表达。一个属性对应一个 等价关系，一个表可以看作是定义的一簇等价关系，即知识库。 定义2 1 3 设信息系统s = ( u ，a ) ，p a ，则属性集p 决定的不可区分 关系i n d ( p ) 定义如下： i n d ( p ) = ( 耳，工j ) 童u uv a p ，4 ( t ) = 4 ( 一) ，t i ，j i ( dp u 口) ) 。该增量越大，表明在 己知知识p 的条件下，属性a 对决策集d 越重要。因此，互信息增量可作为属 性a 的重要度的度量。 定义2 2 6 设决策表s = f u ，a ) ，a = c u d ，cnd = ，p c ， a c p ，属性a 相对于决策属性集d 的重要度定义如下： 踞( 口，p ，d ) = h ( dp ) - h ( dp u a ) 。 s i g ( a ，p ，d ) 越大，表明在已知尸的条件下，属性a 对决策集d 越重要。 因此可将蹿( 口，p ，d ) 作为属性约简算法中的启发信息，以减少约简过程中的 搜索空间。 基于互信息的属性约简算法如下陷引： 基于粗糙集理论的不完备信息系统属性约简研究 输入：s = ( u ，a ) ，a = c ud ，c nd = 矽 输出：s 的一个相对约简 算法步骤： ( 1 ) 计算s 中c 与d 的互信息，( c ；d ) ； ( 2 ) 计算c 相对于d 的核c o = c o r e ( c 1 ； ( 3 ) 令p = c o ，对c p 重复以下步骤： v a c p ，计算，( 口】；d l p ) ； 选择使，( 口1 ；d l p ) 最大的属性口7 ( 若同时有多个属性达到最大值， 选择与尸属性组合数最少的属性作为口7 ) ，令p = 尸u 以，1 ； 如果i ( p ；d ) = j r ( c ；d ) ，算法结束；否则，转； ( 4 ) 得到c 相对于d 的一个相对约简p 。 该算法的复杂性主要由决策表的属性组合引起，在最坏情况下，每次考虑 的属性个数依次为f c l ，c - 1 ，1 ，则总次数为i c l ( c l + 1 ) 2 ，因此，如果忽略 对象个数对计算时间的影响，算法的最坏时间复杂度为o ( i c l 21 【3 3 1 。 从以上分析可以知道，各种算法根据不同的思想对信息系统进行约简且各 有优缺点。基于区分矩阵的属性约简算法不用求核，但在决策表较复杂和条件 属性较多时，对存储空间需求过大；基于正域的启发式属性约简算法和基于互 信息的属性约简算法虽然较基于区分矩阵的属性约简算法有所改进，减小了搜 索空间，却需要求核，而在大数据集中求核是一个繁琐的过程。因此，寻求高 效的完备的属性约简算法仍然是未来粗糙集理论的研究热点。 2 3 小结 本章从信息系统和不可区分关系、集合近似、约简和核、区分矩阵和区分 函数等方面系统地介绍了粗糙集理论的基本概念，并从算法方面对粗糙集理论 应用于数据挖掘领域的属性约简问题做了分析。 1 9 基于粗糙集理论的不完备信息系统属性约简研究 第三章不完备信息系统的粗糙集扩展模型及属性约简 经典粗糙集理论以完备信息系统为研究对象，以等价关系为基础进行属性 约简与规则提取，但现实生活中的系统经常是不完备的。当经典粗糙集理论用 于不完备信息系统时，常用的处理方法是通过各种数据补齐方法把不完备信息 系统转化为一个完备信息系统，再用经典的模型和算法对其进行处理口钔。由于 数据补齐只是对原信息系统的近似猜测，其结果与原数据的不完全一致性很可 能会破坏原信息系统中所包含的知识。如果能将经典粗糙集模型扩充，并用它 直接对不完备信息系统进行处理，就可以避免由数据补齐方法带来的近似猜测 问题。为此，下面对不完备信息系统下的几种粗糙集拓展模型和属性约简算法 进行研究和分析。 3 1 不完备信息系统的概念 经典粗糙集理论以等价关系的基础上，通过定义上、下近似运算来建立粗 糙集模型，它研究的对象是完备信息系统，即论域中的所有对象在任意属性下 的属性值都是己知的。但是由于各种条件和因素的影响，现实生活中的某些属 性值是未知的，即信息系统是不完备的。此时如果仍然用基于等价关系的经典 粗糙集理论来处理是不行的，有两种方法解决这一问题：要么使不完备信息系 统恢复成完备的或近似完备的，然后用经典方法论处理：要么对经典方法进行 改进或拓展以适应不完备信息系统的处理要求。对于前者，问题的焦点集中在 数据补齐的方法研究上；对于后一种思想，必须对粗糙集模型加以扩展。本文 后面的研究主要从后者出发! 为此，定义3 1 1 和定义3 1 2 主要对不完备信息 系统的相关概念作了阐述。 定义3 1 1 一个信息系统是一个四元有序组s = ( u ，a ，v ，f ) ，其中【厂是论 域，表示对象的非空有限集；彳表示属性的非空有限集；y 表示属性值的集合， 记作v = u 能。圪，圪表示属性a 的值域；f 表示u x a v 的一个信息函数，它 为每个对象在每个属性上赋予一个属性值，即v x eu ，a a ，f ( x ，a ) v o 。 如果玉u ，a a ，使得f ( x ，a ) = 木( 木表示空值，即未知的属性值) ，称该信 息系统为不完备信息系统，否则称信息系统为完备信息系统。 可见，不完备信息系统其实就是含有未知值的信息系统。区分一个信息系 2 0 基于粗糙集理论的不完备信息系统属性约简研究 统是完备的还是不完备的，关键是看该信息系统是否含有未知属性值。 信息系统也称为信息表，通常简记为s = f u ，a 1 ，故( 不) 完备信启、系统 s = ( u ，a ) 又称为( 不) 完备信息表。 定义3 1 2 设不完备信息系统s = ( u ，a ) ，其中a = c ud ，c n d = ，c 为 条件属性集，d 为决策属性集。具有条件属性和决策属性的信息系统称为决策 系统或决策表。进而，具有条件属性和决策属性的( 不) 完备信息系统称为( 不) 完备决策系统或( 不) 完备决策表。 第二章中关于粗糙集理论的基本概念和基本算法的研究都是基于完备信 息系统的，属于经典粗糙集理论的范畴。下面将主要对不完备信息系统下的粗 糙集理论进行研究。 3 2 不完备信息系统中的粗糙集模型扩展 将完备信启、系统中经典的粗糙集模型在不完备信息系统中拓展，其基本的 出发点是将等价关系( 满足自反性、对称性和传递性) 推广到非等价关系，针 对属性值未知的不同情形，提出了各种不同的二元关系模型哺2 2 吨6 6 1 。 3 2 1 相容关系 m k r y s z k i e w i c z 把未知的属性值理解为是暂时遗漏的值，认为它可以与任 意已知的属性值相同。基于这种思想，m k r y s z k i e w i c z 提出了基于相容关系 的粗糙集模型，并定义了其上、下近似运算陋2 屯3 1 。 定义3 2 1 设不完备信息系统s = ( u ，a ) ，b a ，v x ，y u ，论域u 上 关于属性集b 的相容关系r ( b 1 定义如下： r ( b ) = ( 石，y ) i v b b ，6 ( x ) = b ( y ) o r b ( x ) = * o r b ( y ) = 水) 显然，相容关系r ( 8 1 是自反、对称和非传递的，即相容关系不是等价关 系。 定义3 2 2 设不完备信息系统s = ( u ，a ) ，x u ，b a ，v x ，y u ， 乃( x ) = yi ( x ，y ) r ( b ) ) 表示工在相容关系r ( b ) 下的相容类，毛和墨分别表 示相容关系r ( b ) 下的上、下近似算子，分别定义x 在相容关系r ( b ) 下的上、 下近似集如下： 2 1 基于粗糙集理论的不完备信息系统属性约简研究 上近似集私= x l 瓦( 工) n x 矽) 下近似集瓦工= 石i 瓦( 工) x ) 从定义3 2 2 和定义2 1 5 可以看出，不完备信息系统的上、下近似集定义 与完备信息系统的上、下近似集定义类似，即上近似集表示论域u 上可能属 于x 的对象集，下近似集表示论域u 上肯定属于x 的对象集。 3 2 2 非对称相似关系 j s t e f a n o w s k i 等人认为对象被不完全描述的原因可能是由于知识的不精 确，还可能是由于对象根本不能用已有的属性来描述，即是说，未知属性值不 是确不确定的问题，而是存不存在的问题，因此不允许比较未知值，从而在这 种观点下提出了非对称相似关系心屯3 5 1 。 定义3 2 3 设不完备信息系统s = ( u ，a ) ，b a ，v x ，y u ，论域u 上 关于属性集b 的非对称相似关系s ( b 1 定义如下： s ( b ) = ( 工，y ) iv 6 b ，b ( x ) = b ( y ) o r b ( x ) = 水) 进而可以用s b ( 石，y ) 或砖占y 表示工关于b 非对称相似关系于少。一般地， 非对称相似关系也可简称为相似关系心钔。 由定义3 2 3 可知，非对称相似关系是自反、传递和非对称的。在此基础 上，j s t e f a n o w s k i 定义了两个非对称相似集合嘲1 。 定义3 2 4 设不完备信息系统s = ( u ，a ) ，b a ，魄u ，论域u 上非 对称相似于x 的对象构成的集合及x 与之非对称相似的对象构成的集合分别 定义如下： s b ( x ) = yy u s b ( y ，工) j s ；1 ( x ) = yy ua 品( z ，y ) 通过s b ( x ) 与西1 ( x ) 可以定义非对称相似关系下的上、下近似集。 定义3 2 5 设不完备信息系统s = f u ，a ) ，x u ，b 量a ，x 在非对 称相似关系s ( b ) 下的上、下近似集可定义如下： 上近似集品x = u 。z s 口( x ) 下近似集& x = 工l 嵌u ，写1 ( 工) x 与相容关系相比较，我们可以发现基于非对称相似关系得到的集合x 的上 下近似其实是基于相容关系得到的集合x 的上下近似的改进_ 引。 基于粗糙集理论的不完备信息系统属性约简研究 例如，设z = ( 口，b ，c ，c ，牛，牛) ，y = ( 丰，丰，丰，1 ，2 ，3 ) 。在相容关系下，对象z 和y 属 于同一个相容类，即对象x 和) ，在相容关系下是不可区分的，但对象x 和y 的 已知属性值没有任何一个是相同的。可见，相容关系条件太过宽松，容易导致 没有任何相同的已知属性值的两个对象被同一个类所包含，而无法区分。而在 非对称相似关系下，由定义3 2 3 可知，对象z 和y 不会被包含在同一个类中， 因此，在非对称相似关系下它们是可以区分的。 虽然非对称相似关系较相容关系有所改进，但其条件却过于严格，容易将 本应属于同一个类的两个对象误判为属于不同类。 例如，设工= ( 1 ，2 ，3 ，4 ，o ，木) ，y = ( 1 ，2 ，3 ，4 ，木，b ) 。从直观上很容易判定对象x 和 y 的绝大部分己知属性值相同，即对象x 和y 是不可区分的，应当属于同一类。 但是由定义3 2 3 知，对象工和y 不满足非对称相似关系，即在非对称相似关 系下对象x 和y 被认为是可以区分的，这显得不太合理。 3 2 ，3 限制容差关系 如前所述，相容关系过于宽松，容易使本来不属于同一类的两个对象被归 成同一类，而非对称相似关系过于严格，会误使明显具有大量相同的己知属性 值的两个对象被划分到不同类中。鉴于此，王国胤提出了限制容差关系m 3 来克 服相容关系过于宽松和非