（计算机软件与理论专业论文）动态约简计算方法研究.pdf

摘要 粗糙集理论是一种新型处理含糊和不确定性知识的数学工具，自 提出以来在众多领域得到成功应用。动态约简作为一种有效的属性约 简方法，现有研究已证明其理论优越性，然而计算复杂、效率低的缺 点限制了其进一步发展。本文基于粗糙集理论，对动态约简优化计算 问题进行较为深入的研究。 详细阐述区分函数的构建和化简流程，指出区分矩阵和真值表方 法的不足。从布尔运算观点出发，甄别论域内对象间的有效分辨信息， 直接构造区分函数的极小合取范式。基于约简特性提出并优化约简树 模型，将约简计算问题转换为约简树的遍历问题，在此基础上改进基 本属性约简算法，可高效获取信息系统的所有约简，为动态约简的计 算提供帮助。 对比分析多种动态约简的优势与不足，通过不断弱化限制条件拓 展其模型。为判断子表约简是否为动态约简，提出约简有效性判定定 理，作为简化动态约简筛选的理论依据。基于分治思想，提出快速动 态约简算法，解决传统算法过多系统开销的问题。在稳定度阈值限制 下，快速算法至多计算i f i 2 个子表的约简，而非全部，极大提高了动 态约简的获取效率。 采用u c i 数据集进行实验仿真，仿真结果与性能分析表明文中 所提算法的有效性和可行性。 关键词粗糙集，动态约简，区分矩阵，约简树 a b s t r a c t r o u g hs e tt h e o r yi san e wm a t h e m a t i c a lt o o lt od e a lw i t hv a g u e n e s s a n d u n c e r t a i n t y i th a sb e e ns u c c e s s f u l l ya p p l i e di nm a n yf i e l d s d y n a m i c r e d u c ti sa ne f f e c t i v er e d u c t i o nm e t h o d ，a n dt h ea d v a n t a g e sh a v eb e e n p r o v e d b u tt h ec o m p u t a t i o no fd y n a m i cr e d u c ti st o oc o m p l e x t og a i ni t e f f e c t i v e l y b a s e do nr o u g hs e tt h e o r y , t h i st h e s i sm a i n l yf o c u s e so nt h e p r o b l e mo fo p t i m i z e dc o m p u t a t i o nf o rd y n a m i cr e d u c t a f t e rd e s c r i b i n gt h ep r o c e s so fc r e a t i n ga n dr e d u c i n gd i s c e m i b i l i t y f u n c t i o ni nd e t a i l s ，t h ed i s a d v a n t a g e so fd i s c e m i b i l i t ym a t r i xa n dt r u t h t a b l em e t h o da r ep o i n t e do u t i nt h ev i e wo fb o o l e a no p e r a t i o n ，t h e e f f e c t i v ed i s c e r n i b i l i t yi n f o r m a t i o no fo b j e c t si nd o m a i ni so b t a i n e d ，a n d t h em i n i m a lc o n j u n c t i v en o r m a lf o r mo fd i s c e m i b i l i t yf u n c t i o ni sa l s o c o n s t r u c t e dd i r e c t l y a c c o r d i n gt ot h eu n i q u ef e a t u r e so fr e d u c t i o n ， r e d u c t i o nt r e em o d e li sg i v e na n do p t i m i z e d t h ep r o b l e mo fc a l c u l a t i n g r e d u c t i o ni sc o n v e r t e di n t ot r a v e l i n gr e d u c t i o nt r e e b a s e do nr e d u c t i o n t r e e ，a ni m p r o v e db a s i cr e d u c t i o na l g o r i t h mi sp r o p o s e d a l lt h e r e d u c t i o n so fi n f o r m a t i o ns y s t e ma r eo b t a i n e de f f e c t i v e l y , s oi ti sh e l p f u l t oc a l c u l a t ed y n a m i cr e d u c t t h ea d v a n t a g e sa n dd i s a d v a n t a g e so fd y n a m i cr e d u c ta r ea n a l y z e d ， a n dd y n a m i cr e d u c tm o d e li sd e v e l o p e db yw e a k e n i n gt h er e s t r i c t i v e c o n d i t i o n s f o rj u d g i n gw h e t h e ras u b - t a b l er e d u c t i o ni sd y n a m i cr e d u c t ， ai u d g e m e n tt h e o r e mi sp r e s e n t e d i ti st h et h e o r e t i c a lf o u n d a t i o no f s c r e e n i n gd y n a m i cr e d u c t b a s e do nd i v i d i n ga n dc o n q u e r i n gt h o u g h t ，a f a s tg e n e r a l i z e dd y n a m i cr e d u c ta l g o r i t h mi sp u tf o r w a r d t h ea l g o r i t h m o v e r c o m e st h es h o r t c o m i n g so ft r a d i t i o n a la l g o r i t h m w i t h i nt h es t a b i l i t y d e g r e et h r e s h o l dl i m i t ，n om o r e t h a nl f i 2s u b t a b l e sn e e dt ob ec a l c u l a t e d ， w h i c hi m p r o v e st h ee f f i c i e n c yo fg e t t i n gd y n a m i cr e d u c tg r e a t l y u c id a t a s e ti su s e df o rt e s t i n go u rm e t h o d s e x p e r i m e n t a lr e s u l t s a n dp e r f o r m a n c ea n a l y s e sd e n o t et h a tt h e ya r ef e a s i b l ea n de f f e c t i v e k e yw o r d s r o u g hs e t ，d y n a m i cr e d u c t ，d i s e e r n i b i l i t ym a t r i x ， r e d u c t i o nt r e e u 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：二匿堕 日期：毕年月丝日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名： 蘸塾星导师签名妞日期：年上月幽 硕士学位论文第一章绪论 第一章绪论 粗糙集理论拓展于经典集合论，是一种研究不确定性知识和数据表达的方 法，借鉴了哲学和逻辑学的部分思想，克服了传统数据分析理论的不足，自问世 以来得到广泛应用和深入发展，逐步建立起一套比较完善的体系。本章首先介绍 粗糙集理论及其相关背景，然后评述国内外相关研究和进展现状，最后指出本文 的主要研究内容和论文的组织结构。 1 1 课题研究背景 随着信息技术的高速发展和大规模数据库的广泛使用，人类积累的数据量正 在以指数速度迅速增长，庞大的信息量已渗透到社会生活和生产的各个领域，由 此导致的信息的不确定性也更加显著。人们日益感觉到信息爆炸、数据过剩的压 力和“丰富数据，贫乏知识的困惑。尽管目前在信息处理方面已提出了用于数 据挖掘的简单统计分析技术，但实用的智能信息处理技术目前仍不成熟。因此， 如何科学、合理、有效地从杂乱无章、强干扰的海量信息中挖掘潜在的、有利用 价值的知识成为当前亟待研究的课题。 粗糙集理论【卜3 】是由波兰数学家p a w l a kz 教授在研究信息系统逻辑特性的基 础上于1 9 8 2 年提出。作为一种处理模糊和不确定性知识的新型数学工具，粗糙 集理论无需提供问题所需处理的数据集合之外的任何先验信息，仅以观测数据的 分类能力为基础，以集合逼近的方法来描述知识，对问题的不确定性的描述或处 理相对客观，克服了传统知识处理和模糊逻辑的缺陷与不足，能够有效地分析和 处理不精确、不一致和不完整等各种不完备信息，并从中发现隐含知识，揭示潜 在规律，成为软计算的重要组成部分。目前已在人工智能、决策系统、知识获取、 模式识别等众多领域取得了较为成功的应用降9 1 。 属性约简是粗糙集理论的核心研究内容，也是应用粗糙集理论的基础。国内 外学者已提出多种约简算法，取得一定成绩，但仍存在不足，主要体现在两个方 面：约简的有效计算问题和处理数据中噪声、缺省值问题【l o 】，目前尚未提出二 者兼顾的好方案。实际问题的采集数据往往规模庞大且随时间不断增量更新，而 现有约简算法均以小容量信息系统为研究对象，效率有限，无法满足应用需求； 此外，由于随机误差影响数据中不可避免存在噪声，易产生过度拟合问题，造成 约简的质量和预测未知对象的能力降低。 为增强粗糙集理论对海量决策信息系统和噪声数据的适应能力，g b a z a n 在 硕士学位论文第一章绪论 粗糙集理论的基础上提出动态约简陋1 3 】模型，实现从小容量信息系统的动态建 模，满足人们学习知识、认识事物的规律。动态约简方法以更加有效的途径获取 决策信息系统中较为稳定的约简，具备较强的容噪能力和鲁棒性，导出的规则泛 化能力更强，满足当前处理海量、增量数据的迫切需求，有力的促进了应用粗糙 集理论的发展。 1 2 国内外研究综述 自1 8 世纪德国数学家gw l e i b n i z 倡导用通用符号语言和逻辑演算来改革 形式逻辑学，到1 9 世纪德国科学家gf r e g e 等人建立命题演算和一阶谓词演算 系统，形成了数学逻辑体系【1 4 】。这种经典逻辑学只有真、假值之分，但现实生 活中有许多含糊现象不能简单的用真、假值来表示。因此，长期以来许多逻辑学 家和哲学家就致力于研究含糊概念。 2 0 世纪6 0 年代l a z a d e h 提出了模糊集理论，运用模糊集合刻画“亦此亦 彼 的现象。由于模糊集处理复杂系统的独特优势，弥补了经典数学与统计数学 的不足，受到了广泛且深入的研究。遗憾的是模糊集中并没有给出严格的数学公 式描述含糊的概念，无法计算出边界线上具体的含糊元素数目，需依据先验知识 给出模糊隶属度或隶属函数，具有很强的主观性。 2 0 世纪7 0 年代初，波兰科学院和华沙大学的研究小组，开始对信息系统逻 辑特性进行长期基础性研究，针对实验数据的不精确、不相容和不完备问题，进 行分类分析，构成粗糙集理论的基础。1 9 8 2 年，波兰学者z p a w l a k 教授发表经 典论文r o u g hs e t s ，标志着粗糙集理论的诞生。但当时并未引起国际计算机界和 数学界的重视，研究地域仅限东欧部分国家。直到1 9 9 0 年前后，由于该理论在 众多领域的成功应用，才逐渐引起各国学者的关注。 1 9 9 1 年z p a w l a k 教授的第一本关于粗糙集专著【1 5 j l 口l 世，系统全面地阐述了 粗糙集理论，奠定了严密的数学基础。1 9 9 2 年在波兰召开第一届国际粗糙集研 讨会，并于会后出版粗糙集理论应用专集，总结了粗糙集理论与实践的成果，促 进其进一步发展。从1 9 9 2 年至今，每年都召开以粗糙集为主题的国际会议，推 动了粗糙集理论的拓展和应用。另外，国际上成立了粗糙集学术研究会，成员来 自波兰、美国、加拿大、日本、俄罗斯、挪威和印度等国家。至今已约有2 0 0 0 篇有关粗糙集的论文在世界各地的学术杂志上发表，也有不少专著阐述粗糙集理 论的各个方面。目前，粗糙集理论与神经网络、演化计算、模糊系统及混沌系统 已被公认为人工智能的五大新兴技术【1 6 1 。 国内众多学者自二十世纪后十年起对粗糙集理论及其应用进行了广泛的研 2 硕士学位论文 第一章绪论 究与探讨，并于2 0 0 1 年5 月在重庆举行了第一届中国粗糙集理论与软计算学术 讨论会，此后，2 0 0 2 年1 0 月在苏州、2 0 0 3 年5 月在重庆、2 0 0 4 年在浙江舟山、 2 0 0 5 年8 月在辽宁鞍山、2 0 0 6 年1 0 在浙江金华、2 0 0 7 年在河南新乡分别召开 了后续各届讨论会。这些会议的成功举办表明我国粗糙集理论研究的队伍在不断 壮大，研究成果在深度和广度上有了更大的发展。 目前，粗糙集的理论研究主要集中数学性质、模型拓展、有效性算法以及与 其它多种不确定只能分析方法的融合方面。研究者多来自计算机科学领域，同时 信息科学、数学、系统科学、管理科学和控制科学等各个领域的学者也积极参与。 研究侧重点也有所不同，欧洲国家比较注重粗糙集的理论研究和模型扩展；北美 学者注重应用，构造出具有实际利用价值的数据分析软件；日本在粗糙集和概率 论结合方面以及医学应用上比较突出【1 7 】；我国则在粗糙集的有效算法、知识不 确定性研究和与信息论结合等方面取得了较大的成功，并逐步扩展到应用领域， 成为粗糙集领域的重要组成部分，并出版多本相关专著【1 8 。2 2 1 。 粗糙集理论作为一种新型的数据分析理论与方法提出以来，在面向海量数据 分析方面表现出独有的特征。粗糙集理论的基本思想就是在保持分类能力不变的 前提下，通过知识约简，导出问题的决策规则，获取更为有效的不同程度的属性 简洁表达。研究表明，决策表中的属性并非同等重要，甚至存在某些冗余，当随 机采集数据时，冗余性更为普遍，删除这些属性，不仅不会改变决策表的分类能 力，反而能提高系统潜在知识的清晰度。目前，国内外众多学者已对属性约简算 法进行了深入研究，根据研究对象模型构造方法的不同，约简算法主要分为静态 约简和动态约简两种。 1 静态约简 静态约简算法只对初始决策信息系统进行操作，认为它能够完全代表全域内 对象，由其推导的约简对全局决策信息系统也有较好的分类能力。经典粗糙集模 型下的属性约简算法多属静态范畴，主要包括基本约简算法和启发式约简算法。 基本约简算法提出较早，以寻求信息系统内所有约简为目标，处理大规模数据时 效率较低，多被用于约简的理论分析；而基于属性重要度的启发式约简算法思想 的提出却有十分重要的意义。 启发式约简算法的思想最早由h u 提出【2 3 1 ，将核属性作为约简的出发点，属 性重要度作为启发规则，按属性重要度从大到小逐个加入直至集合是约简为止， 然后通过反查去掉不必要的属性。目前，对启发式约简的研究主要集中在启发式 信息的选择，即属性重要度的度量策略上，这是由于算法的有效性依赖于属性重 要度而导致的。根据度量角度不同，先后提出基于区分矩阵的属性重要度 2 4 - 2 5 1 、 基于代数观点中相对正域的属性重要度 2 6 - 2 7 1 和基于信息的属性重要度1 2 8 2 9 1 。利用 硕士学位论文 第一章绪论 这些属性重要度作为启发式信息的算法已被提出且多次改良，以满足不同对象的 处理需求，并在医疗数据分析、金融风险控制等多个方面取得成功应用。 总体上来说，启发式约简算法将属性重要度作为启发信息，从已成型的数据 集中导出属性间的约简关系，将全局搜索问题转变为启发式搜索问题，能够计算 出一个最好的或用户指定的最小约简，具有较高效率。但它对决策信息系统有严 格要求，首先，只能处理某特定时刻的信息系统，一旦信息系统内容发生改变， 就必须重新计算约简，以前的结果对新的计算没有任何帮助；其次，对噪声非常 敏感，约简很可能会由于噪声的干扰而改变，偏离其轨道。总之，面对增量数据 和噪声数据时，启发式约简的效率和质量将大打折扣。 另外，遗传算法【3 0 3 2 1 、扩展法则【3 3 1 、并行算法【蚓和决策表分解技术 3 5 - 3 8 1 已 被研究。但这些方法只能处理给定决策表，操作静止的、不发生变化的对象，导 出的规则分类未知对象的能力不足，无法有效分析海量数据和噪声数据，在实际 应用受到种种限制和局限。 2 动态约简 针对约简稳定性不足、规则泛化程度不高的缺陷，g b a z a n 等人提出的动态 约简方法将约简计算从现有决策信息系统扩展到全局决策信息系统，更符合现实 需求。根据抽样理论构造能够代替全局决策信息系统的子表族，依据概率分布寻 找全局决策信息系统最有效的属性简化，在理论上为决策表信息系统寻求稳定约 简奠定了初步基础。 动态约简的特点主要体现在对海量数据的处理，当所给决策信息系统规模较 小时，动态约简的优势可能并不容易体现，但当决策信息系统十分庞大时，动态 约简可实现从小样本到大数据集的建模，从原始决策表随机抽样形成子表族，把 复杂的大型决策表的约简问题转化为若干子表约简交集问题，在某种意义上是给 定决策表中最为稳定的约简，提高了约简的稳定性，这正是动态约简追求的目标。 目前关于动态约简方法的研究主要集中在抽样策略、f 族容量计算和f 族质 量度量等方面，已有一些初步成果，但还很不充分。另一方面，动态约简计算理 论的研究更是空白，有关动态约简快速有效计算的文章屈指可数，在国内的相关 文献更是鲜见，许多问题的研究还有待提高。本文基于动态约简思想，主要对基 本属性约简算法、动态约简模型的拓展和广义动态约简快速获取方法等问题进行 研究与探讨。 ( 1 ) 动态约简的理论拓展。动态约简自提出以来，其模型被多次更新，计算 可行性和实用性不断提高。g b a z a n 在其自定义的f 动态约简、( f ，占) 动态约简 的基础上提出f 广义动态约简、护，占) 广义动态约简，构造了较为完善的体系结 构，并认为动态约简的稳定度系数五 0 ，1 】，文献 3 9 】为得到更为稳定的约简， 4 硕士学位论文第一章绪论 使兄 o 5 ，1 】。f 动态约简是动态约简模型的根基，后续各种相关定义均是其泛 化的结果。由于，动态约简、伊，占) 动态约简的计算必须考虑原始决策信息系统 的约简，有较大局限性，现己很少研究；而广义动态约简基于决策信息系统随机 抽取的子表族的约简，降低了计算复杂度且规则不易产生过度拟合问题，是目前 理论研究和实际应用的重点。 ( 2 ) ，族容量计算。动态约简通过抽样策略将复杂的问题简单化，研究中通 常采用简单随机抽样的方法，获取能够充分代表全局决策信息系统特性的子系统 构成，族。f 族是动态约简的基础，其容量和内部对象的分布对动态约简效果有 显著影响。研究表明，f 族容量过小则无法保证约简的稳定性；，族容量超过一 定阈值后对提高动态约简稳定性的帮助不大，且增加计算复杂度。早期，族容 量是专家指定值，根据先验知识获得，缺乏稳固的理论基础；目前，多从统计学 角度出发，利用中心极限定理与极大似然估计思想推导，族容量最小值，已获 得比较完善的计算模型。另外，也有根据f 族子表正域与原始决策信息系统正 域的相似程度来判断f 族是否合理的研究m 】，实际中取得一定效果，但理论基 础有待进一步完善。 ( 3 ) 信息系统基本属性约简算法。长期以来，众多学者致力于决策信息系统 最优约简的研究，多采用基本约简方法计算出决策信息系统所有的约简，进而根 据需求选择最优约简。基本属性约简算法基于区分矩阵，并据此构造区分函数， 然后应用布尔运算对区分函数进行化简，使之从合取范式变成析取范式，进而得 到约简。但该过程中存在明显不足：一方面区分矩阵占据大量存储空间，且存储 内容多有冗余；另一方面区分函数由合取范式到析取范式的转换尚未研究出有效 的实现方法。 ( 4 ) 动态约简算法研究。动态约简的突出优势表现为实际应用中面对海量数 据、增量数据和噪声数据时能够获取具有较高稳定度的约简，推导高泛化能力的 规则，克服静态约简算法的不足。根据动态约简模型的不同，约简算法也有所差 异，g b a z a n 先后提出基于约简痕迹的算法和基于子表概率抽取算法，在两个方 法磁容量均为根据先验知识确定的专家值，随着礅容量计算方法的演化，计 算方法也发生了改变。 由于不用考虑原始决策信息系统的约简，广义动态约简已成为研究重点。目 前，广义动态约简的计算仍采取传统方法，即先计算磁中所有子表的约简，然 后统计子表约简的稳定度系数，最后判断稳定度系数与稳定度阈值的关系，认为 稳定度系数高于稳定度阈值的子表约简是动态约简。广义动态约简通过抽样将大 型信息系统的约简问题转化为若干子系统的约简交集问题，有效的降低了问题的 难度，但必须计算出磁内全部子表的所有约简，计算量仍然可观。 5 硕士学位论文 第一章绪论 文献 4 1 】认为广义动态约简计算过程中产生的大量冗余子表约简，是造成现 有算法效率不高的重要原因。只有满足稳定度阈值要求的子表约简，才被认为是 动态约简。在威笑容量已知的前提下，可以利用约简稳定度阈值限制礅中需要 计算出所有约简的子表的数量，从而提高计算效率。 属性约简是粗糙集理论重要研究方向之一，动态约简是不同于静态约简的新 型约简方法，可以有效的处理实际应用中的海量数据、增量数据，获得的约简稳 定性高，且具备一定的容噪能力。现有动态约简研究已证明其理论优越性，但相 关高效算法的研究还存在诸多不足，急需提高。 1 3 本文主要研究内容 随着大规模数据库的广泛使用和网络的高速发展，信息资源得到极大的丰 富，人们越来越关注如何开发和利用这些资源，高效地挖掘潜在规律变得越来越 重要，由此粗糙集理论成为智能信息处理领域的研究热点。基于粗糙集理论的静 态约简局部色彩浓重、稳定性不足，而动态约简以寻求最优、最稳定的约简为目 标，能够满足实际中处理海量数据和噪声数据的需要。因此，研究基于粗糙集的 动态约简具有极重要的理论意义和现实意义。 动态约简模型假设子决策信息系统的所有约简是可计算的，但实际上却面临 较大困难，用于计算所有约简的基本约简算法效率较低，只能适用于小容量信息 系统；另外，针对f 族中所有子表的约简要求也有一定难度。这在很大程度上 限制了该理论的发展，须对动态约简计算理论进行优化，发展完善相关算法。本 文分析算法低效性的根源，针对动态约简计算理论与方法的相关问题进行研究， 主要研究工作包括： ( 1 ) 分析区分矩阵的不足，利用布尔运算的观点，评估区分矩阵内存储信息 的价值，提取论域内对象之间必须的、无冗余特征信息构成新的存储结构，从其 出发直接构造区分函数极小合取范式，跨越生成合取范式的阶段。根据新存储结 构与区分矩阵推导出的区分函数合取范式是完全等价的，而前者更为简洁、不可 删除。 ( 2 ) 深入研究区分函数极小合取范式到析取范式的转换过程，揭示基于真值 表的实现方法的不足。利用启发信息降低布尔函数转化过程中的盲目搜索，结合 布尔函数运算规律提出约简树计算模型，并结合析取范式到极小析取范式的转换 原理进行后续优化，提高计算决策信息系统所有约简的效率，为获取动态约简打 下坚实的基础。 ( 3 ) 拓展动态约简模型，使其更适合理论研究和实际应用，并重点研究广义 6 硕士学位论文第一章绪论 动态约简方法。深入分析判断子表约简能否成为动态约简的条件，认为现有判断 方法过于滞后，影响获取效率。结合稳定度阈值，提出约简有效性判定定理，从 子表约简计算过程中获取必须信息，简化广义动态约简的筛选流程。 ( 4 ) 建立广义动态约简的快速计算模型，通过稳定度阈值的限制，在保证f 族有效、合理的基础上，减少其中需要计算出所有约简的子表的数量，进而提出 在约简有效性约束条件下的广义动态约简快速算法，为从海量信息系统中获取具 有较高稳定性的约简提供有效途径。 动态约简是一种有效的数据约简方法，在面向现实数据时体现的尤为明显。 动态约简计算理论发展仍不成熟，受到多方面的制约，算法效率较低，须进行优 化，发展完善相关算法，以提高约简效率。本文基于动态约简模型，针对动态约 简优化计算问题进行研究。 1 4 本文组织结构 本文以动态约简为核心研究内容，对其计算理论进行优化，重点研究高效获 取决策信息系统所有约简的方法和计算动态约简的新策略，在此基础上建立快速 广义动态约简计算模型，并通过实验证明其有效性。论文共分为五章，总体结构 组织如下： 第一章主要介绍粗糙集理论提出的背景，评述国内外相关研究现状，简述本 文主要研究内容，并给出论文各章结构安排。 第二章简要介绍粗糙集理论基本概念，引出属性约简这一主题，并综述当前 基于静态建模的属性约简算法。在此基础上给出g b a z 趾体系下的动态约简模型， 详细分析并归类动态约简的f 族容量计算方法，最后就动态约简计算理论阐述 其适合应用的领域。 第三章以高效计算决策信息系统的所有约简为目标，详细分析基本属性约简 算法的各种不足，将其归结为区分矩阵时空浪费和区分函数合取范式到析取范式 转换的低效与盲目；进而提出一种新的区分信息存储结构，从布尔运算的观点精 简保存论域对象间的有效区分属性，在此基础上提出约简树计算模型，提高获取 决策信息系统中所有约简的效率。 第四章为解决传统算法计算广义动态约简耗时的问题，提出在约简有效性约 束条件下的快速算法，认为动态约简的有效性取决于约简的稳定度系数与稳定度 阈值之间的大小关系。通过稳定度阈值的限制，减少f 族中需要计算出所有约 简的子表的数量，并利用最优稳定度系数过滤掉不可能成为广义动态约简的子表 约简以提高效率。 7 硕士学位论文第一章绪论 第五章归纳总结本文的研究工作，并展望今后进一步的研究工作。 1 5 本章小结 应用粗糙集理论的发展受到海量数据集和含噪数据的挑战日趋严重，动态约 简为此提供了一种有效的处理方法，然而其计算理论仍需继续完善。本章主要简 介粗糙集理论的诞生背景、发展历程；并结合动态约简综述国内外相关研究现状； 简述本文的研究内容；最后给出论文的总体结构组织。 硕士学位论文第二章粗糙集理论概述 第二章粗糙集理论概述 粗糙集理论是一种强大的数学分析工具，能够有效处理各种不完备信息，并 从中发现隐含知识，揭示潜在规律，为机器学习、知识发现、决策分析、专家系 统、模式识别、模糊控制等领域提供了一种新的数据分析方法。作为一种独立的 理论框架，它的提出不仅为信息科学和认知科学提供了新的科学逻辑和研究方 法，而且为智能信息处理提供了有效技术。 2 1 经典粗糙集理论概述 2 1 1 粗糙集理论基本概念 粗糙集理论用二维数据表描述现实世界中的问题，作为研究的样本空间，常 称为信息系统。信息系统的行表示对象，列表示对象的属性，对象的信息通过属 性值刻画。对象、属性和属性值是信息系统的三个基本要素。 定义2 1 信息系统s = ( u ，a ，v ，f ) ，其中u 为样本集合，称为论域；a 为属 性集合；v _ uv o 是属性值的集合，圪为属性a 的值域；f ：u x a 专v 是信息函 a e a 数，为论域中每个对象指定唯一属性值。 定义2 2 给定信息系统s = ( u ，a ，v ，f ) ，对任意等价关系r 冬彳，定义u 上的 不可分辨关系i n d ( s ，r ) 为： i n d ( s ，尺) = ( x ，y ) i ( 工，y ) u 2 ，v c r ，c ( x ) = c ( j ，) ) 不可分辨关系是由等价关系族构成的特殊等价关系，由不可分辨关系划分而 成的论域中相互间不可区分的对象构成基本集。基本集中的对象是无法识别的， 构成知识的粒度，从而产生不确定性。任意有限的基本集的并构成的集合均是可 定义的。 设r c _ a 是论域u 上的等价关系，当x c _ u 能用基本等价类组成的并集表示 时，则称其是可以精确定义的，是精确集；否则，集合x 只能通过逼近的方式 来刻画。 定义2 3 给定信息系统s = ( u ，a ，y ，f ) ，r c a ，y 是u 上按等价关系尺生成 的等价类，则v x c _ u 关于r 的下近似集和上近似集分别定义为： 星( x ) = u r u i n d ( r ) a y x ) 尺( x ) = u r u 1 n d ( r ) a 】，n x g ) 9 硕士学位论文第二章粗糙集理论概述 下近似为所有被包含在z 中的等价类的并集，上近似为所有与x 交集不为 空的等价类的并集。 定义2 4 集合b n r ( x ) = 页( x ) 一星( x ) 为j 的尺边界；集合p o x r ( x ) = 星( x ) 为x 的r 正域；集合n e g r ( x ) = u r ( x ) 为x 的r 负域。 根据定义2 3 、2 4 可知，夏( x ) = p o s ( x ) + 召虬( x ) 。当b n r ( x ) = a 时，称 x 关于r 是清晰的；当b n r ( x ) 囝时，则称x 是关于r 的粗糙集。 正域内包含根据现有知识判断出肯定属于样本空间的对象；负域内包含根据 现有知识判断出肯定不属于样本空间的对象；而边界域包含那些不能确定是否属 于样本空间的对象。边界域是由于知识是粒度性而产生的。若知识的粒度足够细， 每个基本概念仅包含单个样本，此时能够精确定义任何概念，边界域为空。边界 域概念的引入，使粗糙集理论能够描述和处理模糊信息，并最终使其成为分析处 理不确定性信息的有效工到4 2 1 。 粗糙集的不可定义性是由于粗糙集合z 的边界不确定性引起的。集合的边 界区域越大，其确定性程度就越小【2 2 1 。所以可以用集合z 的近似精度和粗糙度 这两个概念来描述粗糙集x 的不确定性程度。由等价关系尺定义的集合x 的近 似精度为： 口r ( z ) = i 星( x ) i i r ( x ) i 其中，若x = 囝，则( x ) = 1 ，粗糙度可记作1 一口。( x ) 。 精度是一个 o ，1 上的实数，定义了彳的确定度，而粗糙度与精度完全相反， 表示知识x 的不完全程度。 定义2 5 假设集合簇f = l ，定义r 对f 的近似分类质量( f ) 为： i = 1 ( f ) ：亨塑 一1 = 1 iuii i 尺对f 的近似分类质量描述的是当使用知识r 对样本进行分类时，能够确定 决策的样本在论域中所在的比例。 定义2 6 决策信息系统s = ( u ，c u d ) ，u 为非空有限论域：c = c 1c 2 ，靠) 为条件属性集合，d 为决策属性集，且c n d = 0 。任意对象a eu 在属性x ( c u d ) 上的取值记作口。当且仅当v x ，y u ( d ( 功d ( y ) ) 一3 a c ( 口( 力口( y ) ) ，称s 为相容决策信息系统，否则，称s 为不相容决策信息系统。 决策信息系统是一种特殊的信息系统，将属性细分为条件属性和决策属性两 个独立且不重合的部分。实际中，在决策信息系统中存在多个决策属性的情况， l o 硕士学位论文第二章粗糙集理论概述 研究表明可以转换为单决策属性进行处理。 定义2 7 给定决策信息系统s = ( u ，c u d ) ，f 是决策属性d 导出的分类， r cc ，则对于任意属性a r 的重要度s g f ( a ，r ，d ) 定义为： s g f ( a ，r ，d ) = r a ( f ) 一- 4 ) ( ，) 表示当属性集彳中增加属性a 对，近似分类的质量的影响。 定义2 8 给定决策信息系统s = ( u ，c u d ) ，若有c c ，满足p l d ( s ，r ) = i n d ( s ，r c ) 则称o 在c 中是可被约去的知识；如果任一c c 是c 中不可约去 的，则属性集c 是独立的，否则称c 是相关的；如果r = c o 是独立的，则称只 是c 中的一个约简。 通常情况下，决策信息系统的约简不是唯一的，但其至少应该有一个，即其 条件属性集本身，称为平凡约简。 定义2 9 给定决策信息系统s = ，c u d ) ，c 中所有必要的、不可删除的 属性构成的集合称为核，记为c o r e ( r ) 。 核是决策信息系统的所有约简的交集，是最重要的条件属性集合，但可能为 空。核属性是由所有的独立的条件属性组成的集合，任意核属性被删除后，由其 余的核属性构成的不可区分关系不同于原来的不可区分关系。属性约简是所有条 件属性的子集，由该子集形成的不可区分关系与原集合的不可区分关系相同，并 且该子集中的每个属性均不能删除。属性约简代表无冗余的完备信息；值约简则 代表了每个实例的无冗余的完备信息。 2 1 2 粗糙集理论的研究 粗糙集理论提出以来，理论研究和实际应用日趋完善，已成为智能信息处理 领域又一研究热点，表现了强大的生命力。通常软计算理论中模糊数据处理系统 建立在经验层次之上，而粗糙集理论完全从给定的问题描述集合出发，通过不可 分辨关系和基本集定义问题的近似域，构成知识粒度，不需要任何先验知识，对 数据规律的描述更为客观。 尽管粗糙集理论具备其它理论不可替代的优越性，但也存在某些片面和不足 之处，突出表现为缺乏对复杂系统的处理机制和对噪声数据的适应能力、未包含 对原始数据本身的模糊性的处理方法、对边界域的刻画比较简单。若与其他处理 不确定性方法的理论相互补充、相互渗透，分析数据的效果将更佳。主要体现在 与概率统计、模糊数学和证据理论等方面，目前已提出多种扩展模型 4 3 - 4 5 】，以可 变精度粗糙集模型m 】为典型代表。 决策信息系统中存在噪声等随机因素干扰情况下，经典粗糙集由于对数据的 过度拟合而降低对未知对象的分类能力。z i a r k o 教授提出一种可用于分析信息系 硕士学位论文第二章粗糙集理论概述 统统计观点上数据模式的可变精度粗糙集模型v p r s ，解决了属性间的弱依赖关 系。通过引入分类错误率系数，将集合论中标准包含关系扩展为多数包含关系， 允许一定程度的分类错误存在，使粗糙集具有一定容错性，增强抗干扰能力。 另外，粗糙集理论有效算法的研究也是值得关注的问题，除了启发式约简算 法外，主要集中在以下三个方耐4 1 7 1 。 ( 1 ) 导出规则的增量式算法。粗糙集原有算法针对某个特定时刻的决策信息 系统进行操作，包括正域、属性核和约简的计算均是如此。当有新的数据增加到 决策信息系统时，必须重新计算进而导出决策规则，不能从以前结果中获得任何 帮助。增量式算法是对原有的规则进行动态修正，从而得到关于新决策信息系统 的规则的方法。另外，动态约简、动态规则【4 9 】也具有良好的增量特性。 ( 2 ) 粗糙集基本运算的并行算法。粗糙集的基本性质决定其很多基本运算都 可以采取并行策略。m u r a s z l d e q i c zm 采用格行数组的s i m d 计算机形式，提出 实现粗糙集中诸如可定义性、不可分辨性以及上、下近似这些基本运算的并行近 似结构。由于粗糙集研究的初衷就是试图为处理大量数据提供一种数学工具，因 此，并行计算的性质就显得非常重要。 ( 3 ) 大数据集的粗糙集计算实现。由于粗糙集在数据挖掘中具有较大的计算 复杂度，受关联规则挖掘算法的启发，有些研究者提出将关联规则的挖掘技巧应 用到粗糙集的确定和可能规则生成中，以减少粗糙集方法的计算复杂度。同时， 决策表分解方法为大数据集的处理提供了帮助。 2 1 3 属性约简算法 知识约简是粗糙集理论的精髓，已成为粗糙集理论的重要研究内容。知识约 简是指在不影响知识表达能力的前提下，通过消除冗余知识以获得知识库简洁表 达的方法，在粗糙集理论中表现为在保持分类或决策能力不变的同时，消除冗余 属性和属性值，最终获得信息系统的分类或决策规则的方法。约简反映了决策信 息系统的本质信息。 目前，决策信息系统中的信息膨胀主要有横向的属性集合不断扩大和纵向的 记录数快速增加，与此相应，知识约简有属性约简和值约简【5 0 - 5 1 】之分。随着数据 的不断快速增加，属性约简比值约简更为有效。由于相对较为简单，属性值约简 目前已较少研究，而属性约简则较为困难，部分内容至今没有完全解决，已成为 知识约简的研究重点，基于此常将知识约简理解为属性约简。 国内外众多学者就属性约简算法和相关问题进行了深入研究，其中基于属性 重要度的启发式约简算法得到广泛认同和高度评价，在实际应用中发挥了重要作 用。逐步形成基于相对正域的启发式约简算法、基于区分矩阵的启发式属性约简 1 2 硕士学位论文第二章粗糙集理论概述 算法和基于信息熵的启发式属性约简算法，思想相似，不同之处主要体现在属性 重要度的度量策略。 ( 1 ) 基于相对正域的属性重要度。粗糙集理论以知识、分类为基础，通过正 域刻画当前知识的确切分类能力，进而定义分类精度和分类质量。基于正区域的 属性重要度以属性集中去掉一个属性前后的分类质量的改变作为度量标准，但定 义并不唯一，文献 2 6 和文献 2 7 分别从统计意义和计算复杂性角度进行了改进， 但没有摆脱利用上、下近似对集合进行刻画的观点。 ( 2 ) 基于区分矩阵的属性重要度。区分矩阵中浓缩了决策表内所有对象的区 分属性信息，属性出现越频繁能够区分的对象就越多，认为其属性重要程度越高， 反之，则认为其属性重要程度越低。基于区分矩阵的属性重要度以属性在矩阵中 出现的频率作为度量标准，称之为属性频率函数。文献 2 5 提出一种改进的计算 方法，既考虑属性出现的频率又考虑属性组合的长度，组合长度越短则分辨能力 越强，达到较好的度量效果，实验中一般能够求出最优或次优约简。 ( 3 ) 基于信息论的属性重要度。此类属性重要度建立在信息论观点的基础 上，将知识看作是定义在论域的子集组成的随机变量，与粗糙集的代数表示是等 价的。文献 2 8 】将条件属性和决策属性的依赖度转变成互信息，将决策表中增加 某个属性所引起的互信息变化的大小作为属性重要性的度量。文献 2 9 采用信道 容量描述属性重要度，突破了互信息量对决策表中的决策属性比例应与实际比例 相同的假设，更具客观性。但基于粗糙集信息论观点的属性重要度都有一种不尽 合理的倾向，过于强调具有较多属性值的属性。 另外，文献 5 2 1 提出一种启发式遗传约简算法，通过构造新的算子引入启发 式信息，使得算法同时具有整体优化特性和较快的收敛速度。 上述属性重要度从不同方面刻画属性的分类能力，以满足不同处理对象的需 求，并在医疗数据分析、金融风险控制等多个方面取得成功应用。但知识约简的 目标是获取最优约简，对属性重要度的度量方式的修改，并不能改变利用启发式 信息的贪心算法易落入局部最优的趋向。 2 2 动态约简方法概述 动态约简是针对基于静态建模的属性约简算法的不足【5 3 】而提出的新型约简 方法，具备较强的容噪能力和鲁棒性，能够满足当前处理海量、增量数据的迫切 需求，有力的促进了应用粗糙集理论的发展。 1 3 硕士学位论文 第二章粗糙集理论概述 2 2 1 动态约简提出背景 约简是知识发现的重要过程，也是寻求最简规则和规则最大泛化的重要手 段。为提高约简计算效率，基于静态模型的启发式算法被广泛研究，从已成型的 数据集中导出属性间的约简关系，取得一定成绩，但仍面临不少问题【5 4 】，如动态 数据库、增量数据处理和数据噪声干扰等，这促使基于粗糙集理论的方法不断完 善与发展。 从理论上来说，基于静态模型的各种约简算法均以当前决策信息系统作为训 练集，认为其与全局决策信息系统具有相同的对象分布规律，然而，由于随机误 差等因素的干扰，当前决策信息系统往往含有噪声，不能够完全有效的代表全局 决策信息系统。因此，从训练集出发，通过计算约简导出的规则能够很好的分类 当前决策信息系统，然而当处理全局决策信息系统中的其它样本时，分类质量明 显降低，产生过度拟合问题。 另一方面，基于粗糙集的数据处理软件的开发和应用表明，目前的属性约简 算法主要针对小容量决策信息系统，无法有效处理大容量数据集( 受计算效率的 影响) 。然而，实际决策信息系统往往规模庞大，具有海量的数据对象和繁多的 属性，选用小容量决策信息系统作为训练集，难以代表全局