（计算机应用技术专业论文）粗糙集模型下的进化属性约简算法研究.pdf

南京师范大学硕士研究生毕业论文 摘要 摘要 现实世界的数据是海量数据，大型数据库含有冗余特征及噪音，不仅导致数据挖掘的代 价高，而且导致规则提取的质量低。针对此问题，通过粗糙集工具对海量数据进行知识约简， 可有效提高数据挖掘的效率及质量。粗糙集是一种新的处理不精确、不完全与不相容知识的 数学理论，无需附加先验条件，即- 可对知识进行约简。近年来，该理论在机器学习、数据挖 掘及模式识别等多个领域得到了广泛的应用。本文对粗糙集理论做了深入的研究，力图在一 定程度上解决知识约简中的若干问题。论文工作的主要成果表现在如下几个方面： ( 1 ) 提出两个核的动态求解算法：垂直分布多决策表的增量式求核算法和基于数据修改 的求核算法。核是粗糙集理论的重要研究内容之一，大多数属性约简算法，将求核作为求属 性约简的前一步骤。然而，在知识动态变化的情况下，采用静态方法求核代价高。为此，采 用动态求核方法，可高效维护核的动态变化。 ( 2 ) 提出新的粒子群优化属性约简算法及改进的蚁群优化属性约简算法，并在上述研究 的基础上，又提出结合粒子群和蚁群搜索策略的属性约简算法。采用传统的启发式属性约简 算法虽可提高求解效率，但存在解个数过少及求得的解为次最佳解等问题。为此，引入进化 算法，可有效解决纯粹粗糙集工具得到的解数目过少及求得的解为次最佳解等问题。本文提 出的粗糙集模型下的进化属性约简算法可同时得到多个最小约简，且算法时间复杂度明显降 低，为数据挖掘的后续步骤打下了良好的基础。 ( 3 ) 提出基于粒子群及蚁群优化的并行属性约简算法，以此有效缩短算法的执行时间。 本文的并行机制采用两种数据抽取策略( 随机抽取策略及k dt r e e 抽取策略) 可有效祢补单机 串行进化算法求解效率低的缺点。 关键词：粗糙集；属性约简；进化算法：并行机制 南京师范大学硕士研究生毕业论文 a b s t r a c t a b s t r a c t t h er e a lw o r l di sf u l lo fm a s s i v ea m o u n to fd a t a , w h i c hm a yc o n t a i nr e d u n d a n td a t aa n d n o i s e ，n o to n l yc a u s i n gt h eh i g hc o s to fd a t am i n i n g , b u ta l s oc a u s i n gt h el o wq u a l i t yo fe x t r a c t i n g r u l e s t os o l v et h i sp r o b l e m ，r o u g hs e ti si n t r o d u c e d 笛at o o lo fk n o w l e d g er e d u c t i o n ，w h i c hc a l l r e m a r k a b l yi m p r o v et h ee f f i c i e n c ya n dq u a l i t yo fd a t am i n i n g r o u g hs e tt h e o r yi san e w m _ a t h e m a t i c a lt o o l t od e a lw i t h i m p r e c i s e i n c o m p l e t ea n di n c o n s i s t e n td a t a , w h i c hr e d u c e s k n o w l e d g ew i t h o u ta d d i t i o n a lp r i o rc o n d i t i o n s i nr e c e n ty e a r s ，t h i st h e o r yh a sb e e nw i d e l yu s e di n m a c h i n el e a r n i n g ，d a t am i n i n g , p a t t e r nr e c o g n i t i o na n do t h e rf i e l d s t os o l v ec e r t a i np r o b l e m si n k n o w l e d g er e d u c t i o n ，s y s t e m i ca n dd e e ps t u d yo nt h ef i e l d so fr o u g hs e ti sp e r f o r m e d 1 1 1 em a i n c o n t r i b u t i o n so f t h i st h e s i sa r ea sf o l i o w s ： ( 1 ) t w od y n a m i ca l g o r i t h m sa b o u tc o m p u t i n gc o r ea r ep r o p o s e d ：a ni n c r e m e n t a lu p d a t i n g a l g o r i t h mf o rc o m p u t i n gag l o b a la t m o u mg o r eo fv e r t i c a l l yp a r t i t i o n e dm u l t i - d e c i s i o nt a b l e , a n da l l u p d a t i n ga l g o r i t h mo f ac o r ef o rt h ec a s eo fu p d a t i n g t h ec o r eo fad e c i s i o nt a b l ei st h es t a r tp o i n t t om a n ye x i s t i n ga l g o r i t h m so fa t t r i b u t er e d u c t i o n i nt h ec a s eo fd y n a m i cc h a n g e so ft h e k n o w l e d g e ，s t a t i ca l g o r i t h m sa l ei nl o we f f i c i e n c y t h u s ，i tc a ne f f i c i e n t l ym a i n t a i nt h ed y n a m i c c h a n g e so fc o r eb yu s i n gd y n a m i cm e t h o d s ( 2 ) an e wp a r t i c l es w a r ma t t r i b u t er e d u c t i o na l g o r i t h ma n da l li m p r o v e da n tc o l o n y o p t i m i z a t i o na t t r i b u t er e d u c t i o na l g o r i t h ma r ep r o p o s e d f u r t h e r , a l la t t r i b u t er e d u c t i o na l g o r i t h m c o m b i n i n gp s oa n da c oi sp r o p o s e d t r a d i t i o n a lh e u r i s t i cm e t h o d so fa t t r i b u t er e d u c t i o nc a n i m p r o v et h ee f f i c i e n c y , b u tt h er e s u l ti sn o tt h eo p t i m a ls o l u t i o no rt h en u m b e ro ft h ei n d i v i d u a l s b e i n gt o of e w a f t e ri n t r o d u c i n ge v o l u t i o n a r ya l g o r i t h m s ，t h ep r o b l e m st h a tt h er e s u l ti sn o tt h e o p t i m a ls o l u t i o no rt h en u m b e ro ft h er e s u l t sb e i n gt o of e wc a r lb ee f f e c t i v e l ys o l v e d b y c o m b i n i n gt h ee v o l u t i o n a r ya l g o r i t h ma n dr o u g hs e t , t h et w oa t t r i b u t er e d u c t i o na l g o r i t h m s ，t h a t c a ng e tan u m b e ro ft h es m a l l e s tr e d u c t i o na n dr e d u c et h et i m ec o m p l e x i t yo ft h ea l g o r i t h m s s i g n i f i c a n t l y , a r ep r o p o s e di nt h i st h e s i s t h e r e f o r e ，t h e s en e w l yd e v e l o p e da l g o r i t h m sc a nb eu s e d a st h ep r e p r o c e s so fd a t am i n i n g ( 3 ) ap a r a l l e la t t r i b u t er e d u c t i o na l g o r i t h mb a s e do nt h ep s oa n da c os t r a t e g i e si sp r o p o s e d f o rr e d u c i n gf u r t h e rt h er u n n i n gt i m eo ft h ea l g o r i t h m i nt h i st h e s i s ，t w ok i n d so fd a t ae x t r a c t i o n s t r a t e g i e su t i l i z e di nt h et h e s i s ( r a n d o ms a m p l i n gs t r a t e g ya n dk - dt r e es t r a t e g y ) c a l le f f e c t i v e l y o v e r c o m et h ed i s a d v a n t a g e so ft h ee x i s t i n ge v o l u t i o n a r ya l g o r i t h m sa i m i n ga ts i n g l es i t e k e yw o r d s ：r o u g hs e t ；a t t r i b u t er e d u c t i o n ；e v o l u t i o n a r y a l g o r i t h m ；p a r a l l e lm e c h a n i s m 学位论文独创性声明 本人郑重声明： l 、坚持以“求实、创新一的科学精神从事研究工作 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究 成果。 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构 已经发表或撰写过的研究成果。 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示 了谢意。 作者签名：爰叠签 日 期：2 j q 6 笙盆蛰旦 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆被查阅；有权将学位论文的内容编入有关数据库进 行检索；有权将学位论文的标题和摘要汇编出版。保密的学位论文在 解密后适用本规定。 作者签名：墨塑 日飙2 0 显蜓趔 南京师范大学硕士研究生毕业论文第一章概述 1 1 课题研究的意义 第一章概述 现实世界的数据是海量数据。在数据挖掘领域中，对于海量数据来说，一面含有冗余特 征，处理数据将耗费大量资源，导致数据挖掘的代价高；另一方面含有噪音特征，导致规则 提取的质量低。因此，引入特征选择算法后，一方面可只关注最重要的因素，简化数据模型， 有效减少计算量；另一方面，可排除干扰，使我们得到一个虽简单，但更准确，更容易解释 的模型。在机器学习及模式识别领域中，一方面，在样本有限的情况下，大量的特征对设计 分类器来说，计算开销大；另一方面，特征数量中包含噪音和脏数据，导致分类器的性能下 降。因此，进行正确有效的特征选择是必须的。 经典特征选择定义为从n 个特征集合中选出m 个特征的子集，并满足条件m9 j 。它包括 特征提取和特征选择两个方面。特征提取广义上指的是一种变换，将处于高维空间的样本通 过映射或变换的方式转换到低维空间，达到降维的目的；特征选择指从一组特征中去除冗余 或不相关的特征来降维。二者常联合使用，如先通过变换将高维特征空间映射到低维特征空 间，然后再去除冗余的和不相关的特征来进一步降低维数。 特征选择的目标是对数据进行预处理，得到一个相对较小的子集，同时尽可能地保留数 据的完整性。在经过特征选择后的子集上进行后续工作，不仅可提高处理效率，而且可得到 一个更准确、更易解释的模型。属性约简本质上也就是特征选择。目前，特征选择已广泛应 用在机器学习、模式识别和数据挖掘领域。 目前根据评价函数是否依赖分类器，特征选择算法可以分为两大类：为f i l t e r 型算法，和 w r a p p e r 型算法。f i l t e r 型特征选择算法的评价函数与分类器无关，具有计算代价小，效率高 但降维效果一般等特点：而w r a p p e r 型特征选择算法则需要依赖具体的分类器，一般用分类 的错误率作为评价函数，具有计算代价大，计算分类的错误率难度大，效率低但降维效果好 等特点。从两种方法的比较可看出，在对实时性要求较强的处理操作中，f i l t e r 型方法较优， w r a p p e r 型方法计算代价大。文献【1 】给出w r a p p e r 型的算法，文献【2 】将w r a p p e r 与f i l t e r 型方法 相结合，试图祢补各自的缺点，实际上仍以w r a p p e r 型方法为主，计算代价较大。r o u g hs e t 特征选择算法独立于具体的分类器。因此，r o u g hs e t 属于f i l t e r 型方法。 从实际系统中采集到的数据常常包含着噪声，不够精确甚至不完整。采用纯数学上的假 设来消除或回避这种不确定性，效果往往不理想，多年来，研究人员一直在努力寻找科学地 处理不完整性和不确定性的有效途径。模糊集和基于概率方法的数学理论是处理不确定信息 的两种方法，已应用于一些实际领域。但这些方法有时需要一些数据的附加信息或先验知识， 而这些信息有时并不容易得到。粗糙集理论是一种刻画不完整性和不确定性的数学工具。粗 糙集理论的主要思想是利用已知的知识库，将不精确或不确定的知识用己知的知识库中的知 识来近似刻画，在不需要任何附加信息或先验知识的前提下可以非常有效地处理数据集。粗 糙集诞生至今的2 0 余年来，国内外学者对属性约简的求解做了大量的研究，取得了一定的进 展。现有基于粗糙集的属性约简算法大致可分为基于信息熵的算法p 弓j 、基于正域的差别矩 阵算法睁1 m 、基于正域的属性重要性的算法【1 1 1 6 】和进化属性约简算法1 1 7 - 2 3 1 等，可有效对知识 进行约简。 粗糙集得出的属性约简具有约简个数过少，或者约简长度非最短等缺点，而进化算法提 供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强 的鲁棒性。进化算法从问世至今，已成功应用于多个学科领域，对于n p h a r d 的组合优化问 南京师范大学硕士研究生毕业论文 第一章概述 题非常有效。因此，引入进化算法可有效祢补粗糙集属性约简方法的缺点。 随着网络技术及数据库技术的发展，一方面分布式处理技术的应用越来越广泛，针对现 实数据量过大，处理的时间复杂度过高等问题，在分布式环境中分工协作处理数据，可提高 数据的处理速度，降低时间复杂度。因此，本文引入进化算法的并行处理机制具有重要意义。 本论文在江苏省自然科学基金( b k 2 0 0 5 1 3 5 ) 和江苏省自然科学研究项目基金 ( 0 5 k j b 5 2 0 0 6 6 ) 资助下，通过对粗糙集和进化算法等的深入研究，力图在一定程度上解决 下列三个问题： ( 1 ) 静态求核算法不适合维护核的动态变化： ( 2 ) 大多数启发式属性约简算法得到的解结果单一或为次最佳解等问题； ( 3 ) 进化算法求属性约简效率低等问题。 提出两个动态求核算法，垂直分布多决策表的增量式求核算法和基于数据修改的求核算 法，可有效提高核的动态求解效率；提出改进的基于粒子群优化的属性约简算法和改进的蚁 群优化属性约简算法，在上述研究的基础上，又提出基于粒子群及蚁群搜索策略的属性约简 算法。以此改善目前属性约简求解算法的不足，可得到多个最小约简；引入并行机制，采用 随机抽取及k dt r e e 两种数据抽取策略，提出基于粒子群及蚁群搜索策略的并行属性约简算 法，以此改善进化算法求解效率低的不足。 1 2 粗糙集的国内外研究现状 1 2 1 粗糙集的研究背景 在本世纪7 0 年代，波兰学者z p a w l a k 和一些波兰科学院、波兰华沙理工大学的逻辑学 家们，一起从事关于信息系统逻辑特性的研究。粗糙集理论就是在这些研究的基础上产生的。 1 9 8 2 年，z p a w l a k 发表了经典论文r o u g hs e t s f 引，标志着粗糙集理论的诞生。由于最初关于 粗糙集理论的研究成果主要用波兰语发表。因此，开始并没有引起国际计算机界和数学界的 重视，直到1 9 9 0 年前后，由于该理论在模式识别、数据挖掘及机器学习等方面的成功应用， 才逐渐引起世界各国学者的广泛关注。此后，粗糙集理论引起了许多数学家，逻辑学家和计 算机研究人员的兴趣，他们在粗糙集的理论和应用方面作了大量的研究工作。1 9 9 2 年，第一 届关于粗糙集理论的国际学术会议在波兰召开，会后出版了粗糙集理论应用专集。1 9 9 1 年 z p a w l a k 的专著1 2 习和1 9 9 2 年粗糙集理论应用专集的出版，对这一段时期理论和实践工作的成 果作了总结，促进了粗糙集在各个领域的应用。1 9 9 5 年，a c mc o m m u n i c a t i o n 将其列为新浮 现的计算机科学研究课题。1 9 9 8 年，国际信息科学杂志还为粗糙集理论的研究出了一期专辑。 目前，粗糙集已成为人工智能领域中一个较新的学术热点，该理论在机器学习、数据挖掘及 模式识别等多个领域得到了广泛的应用 2 6 - 2 7 j 。 求核、属性约简是粗糙集的核心研究问题。首先本节概述核的国内外研究现状：其次， 从代数观及信息观两种不同的角度，对经典粗糙集属性约简的国内外研究现状进行介绍，并 且对非粗糙集所解决的问题及研究现状也进行介绍；最后，总结属性约简问题。 1 2 2 核的研究现状 核是属性集中不能被约去的属性子集，大多数属性约简算法把求核作为求属性约简的前 一步骤。对于核的求解，前人做出了很多贡献，大致可分为： ( 1 ) 代数观下基于正域的方法【2 8 】及基于差别矩阵的方法【2 弘3 2 】 2 南京师范大学硕士研究生毕业论文 第一章概述 基于正域的计算方法与基于差别矩阵的方法是等价的，但基于差别矩阵的求核算法实现 更简洁、快速。因此，大多数情况下，涉及代数观下的求核大多采用采用基于差别矩阵的方 法( 差别矩阵首先g a s k o w r o n ! 邛】提出) 。在静态数据下，h u 等人从代数观的角度提出了基于 差别矩阵求核算、法【2 9 】，可快速得到核，但经实验证明在某些情况下可能得到错误的核；叶 东毅教授等人提出的差别矩阵p o j ，可正确求核，但算法时间复杂度高于h u 算法；文献【3 1 3 2 】 提出了改进的差别矩阵求核算法。可快速而准确求核，时间复杂度低于前两者。 ( 2 ) 信息观下基于条件熵的方法m m j 王国胤教授从信息观的角度提出了基于条件熵的求核方法m l ，并对代数观、信息观两 种角度的核差异进行了深入的分析p 引，指出这两种不同的求核方法得到的核结果之间是有 关系的，证明了代数观下的核是信息观下核的真子集。 有些学者从广义表的角度对求核进行了探讨【37 3 8 】，与差别矩阵的表示是等价的，只是 表示形式有所差别。鉴于网络技术的快速发展和分】协作的需要，已有国内学者探讨分布环 境下求核1 3 们，从理论上分析出算法的时间复杂度比单机低，网络计算代价小。 1 2 3 属性约筒的研究现状 从粗糙集诞生至今的2 0 余年来，国内外学者对属性约筒的求解做了大量的研究，取得了 一定的进展。从已发表的研究成果来看，少数研究是针对数据一致性的情况，如文献【1 6 】只 探讨了一致性数据集下的属性约简，虽避免了计算正域，提高了时间复杂度，但不利于算法 的推广。鉴于实际应用中很多采集的数据集是不一致的，只研究一致数据集显然不具有普遍 性。因此，大多研究针对不一致数据集1 4 。目前，对不一致性数据集进行属性约简研究的 成果大部分是针对静态数据，少部分是针对动态数据，大致可分为如下几种方法： ( 1 ) 基于信息熵的属性约简算法p 1 基于信息熵的属性约简算法都需要计算信息熵，苗夺谦提出了m i b a r k 算法1 3 】以属性 条件熵的增量作为挑选属性的标准；王国胤教授提出了两种信息熵算法【4 l ，一种是 c e b a r k c c 算法，从核集出发，选择使当前约简集的条件熵最小的属性加入约简集，另一 种是c e b a r k n c 算法，将所有条件属性作为一个集合，按每个属性的条件熵从大到小排序， 依次考虑是否删除该属性。基于条件熵的属性约简方法实质上是根据属性的重要性求属性约 简，只是以条件熵作为衡量属性重要性的标准。基于条件熵的属性约简算法时间复杂度较高， 约简后保留的属性个数也较多。 ( 2 ) 基于正域的差别矩阵属性约算法 6 q o l 从代数观出发的基于正域的属性约简算法，分为基于差别矩阵的方法和基于属性重要性 的两种方法。文献【2 8 】根据差别矩阵中属性的频率作为属性的重要性选择一个属性加入约简 集，虽然算法简单快捷，但算法是不完备的。文献【3 1 】给出了一个基于差别矩阵属性约简的 完备算法但并不能保证是最小约简。由差别矩阵得到分辨函数可以得到所有约简，但计算量 过大，在大数据集上仅是理论可行。 ( 3 ) 基于正域的属性重要性的属性约简算法【d 6 1 基于属性重要性的方法，一般根据属性的重要性来选择一个属性加入约简集，如文献 【i1 1 4 】，这导致时间复杂度较高且不能保证算法是完备的，文献【1 5 】仅从数据结构及数据排 序上进行优化，得到一个时间复杂度较低的基于属性重要性的约简算法。文献【1 6 】给出了不 需计算正域得到约简集的方法，时间复杂度较低，但只适于一致性数据。 基于条件熵的属性约简算法也称为信息观下的属性约简算法，基于正域的属性约简算法 也称为代数观下的属性约简算法。王国胤教授从代数观和信息观两种角度研究了属性约简之 间的关系【3 们，发现这两种理论得出的约简并不是等价的关系。两种约简方法的约束条件不 3 南京师范大学硕士研究生毕业论文第一章概述 周，后者的约束条件比前者更严格，但前者的计算量较后者更小。因此，一个条件属性子集 若是代数观下的属性约简并不一定是信息观下的属性约简，但若一个条件子集今是信息观下 的属性约简，则一定是代数观下的属性约简。 ( 4 ) 基于进化的属性约简算澍 圆1 求一个最小约简是n p h a r d 问题已被证明1 4 矾，属性个数最少的相对约简称为最小约简， 其复杂性主要是由决策表中的属性组合引起的，若m 为条件属性数，则搜索空间为2 。因 此，目前求属性约简大多采用启发式求解方法，可在有限的迭代时间内找到一个最小约简， 前文提到的各种属性约简算法大都是启发式的搜索方法。然而，采用启发式求解方法注重于 求解效率，导致求解的结果非最佳。般启发式求解方法只得到一个约简结果且很多算法是 不完备鲥引，即求得的约简不满足p a w l a k 约简1 2 4 j 的条件。文献【5 】对目前的几种典型约简策略 分析后得出都是非完备约简算法的结论。鉴于此，目前很多属性约简算法并不能证明是完备 的，如文献【6 、8 、2 9 只是经实验证明在某些数据集上可以找出一个或若干个最小约简。 针对经典粗糙集启发式算法只能找到一个相对约简的缺点，在粗糙集模型中引入进化算 法，可得到多个相对约简。目前已有若干相关成果发表。进化算法包括蚁群算法、遗传算法 及粒子群算法等，这些算法发展至今已成功应用于各学科领域。正是受到进化算法成功应用 于t s p 、二次分配、多次序队列等n p h a r d l 音- j 题1 4 3 - 4 7 j 的启发，许多学者开始讨探进化特征选 择的问题，如文献 2 0 1 采用了结合粗糙集和粒子群的方法，但只是小规模的实验。文献【2 1 】 采用蚁群算法研究特征选择的问题，然而参数不易确定，计算复杂度过高，得出的约简结果 不唯一，有待进一步研究。有些文献提出的算法己非一般r o u g hs e t 意义下的属性约简，只是 通过设定阀值，得到的约简结果是近似的约简，如文献【4 8 】，不在本文的考虑范围之内。 上文介绍的属性约简算法大部分是针对知识库含决策属性的情况，即研究的是相对约 简。然而，现实世界存在知识库不含决策属性的情况，在这种情况下，属性约简称为绝对约 简。目前虽有一部分时间复杂度较低的研究成果1 4 9 咖】是针对绝对约简的。然而在大部分应用 中，知识库都是含决策属性的。因此，研究相对约简更有意义。 前文介绍的属性约简算法大部分针对静态数据，然而在实际应用中，数据往往是动态变 迁。在数据产生动态变化的情况下，静态求解算法代价高。因此，增量式知识发现研究具有 重要的应用价值 5 1 - 5 2 】。粗糙集的增量式求核【3 2 1 ，增量式属性约简算法1 5 3 - 5 5 】及增量式规则提 取p 7 】已取得若干进展，并且已有部分学者探索分布式环境下的属性约简增量式算法1 5 引， 实验结果证明分布并行处理可提高求解效率。 p a w l a k 教授所提出的经典r o u g h 集理论主要是针对知识库的知识表达是完备的情况，然 而现实世界存在知识库的知识表达非完备的情况，如空值数据，重要属性空缺，数据稀疏等， 已非经典r o u g h 集理论的研究内容。在知识库非完备、信息缺损的情况下，很多学者也做了 大量研究，如文献【5 9 从删除空缺属性值及近似角度转换数据集后再用r o u g hs e t 方法处理： 文献【6 0 】从信息熵角度研究非完备知识系统：文献1 6 1 - 6 2 将r o u g hs e t 的等价关系扩充为相似 关系，直接获取规则。 另外，粗糙集处理的数据往往是离散化数据。因此，处理连续性数据时，一般需采用离 散化算法把数值型属性转化为离散化属性f 6 孤。这导致计算处理的结果受到离散化效果的影 响。为解决这一问题，可采用模糊粗糙集1 6 4 】等模型进行研究。 无论是传统的粗糙集方法还是结合了进化算法的属性约简方法，v a f a i e l 6 5 j 将它们归结为 两大类方法，贪心法及随机法。传统的粗糙集方法称为爬山法或者贪心算法，进化属性约简 算法可称为随机法。爬山法多采用属性重要性作为启发信息，如果是向前添加法，则从空集 或核集开始，依次挑选重要的属性加入。直到成为一个约简，如果是向后删除法，则从整个 集合出发，按照属性重要性排序后，依次删除一个不重要的属性，直到成为一个约简。前面 4 南京师范大学硕士研究生毕业论文第一章概述 也指出这种方法的特点就是不能保证得到约简集是完备的，但算法的效率较高，可在有限时 间内得到一个次最佳的约简结果。随机法则是通过进化算法如遗传算法，蚁群算法等的随机 搜索特性来完成自适应调节迭代寻优的过程，经若干次迭代后可找到一个或多个最小约简， 但需付出昂贵的时间代价： 1 3 本文的创新之处 本文旨在将进化算法引入粗糙集，力图在一定程度上解决属性约简中的部分问题，主要 创新点如下： ( 1 ) 提出两个核的动态求解算法：垂直分布多决策表的增量式求核算法和基于数据修改 的求核算法。 核是属性集中不可被约去的属性子集，核是粗糙集的重要研究内容之一，大多数属性约 简算法，将求核作为求属性约简的前一步骤。然而，在知识动态变化的情况下，采用静态方 法求核代价高。为此，采用动态求核方法，可高效维护核的动态变化。经理论分析及实验证 明，本文提出的两个核的动态算法是有效可行的。 ( 2 ) 提出新的基于粒子群优化的属性约简算法及改进的蚁群优化属性约简算法，并在上 述研究的基础上，又提出结合粒子群和蚁群搜索策略的属性约简算法。 求解最小约简是个n p h a r d 问题，采用传统的启发式属性约简算法虽可提高求解效率， 但存在解个数过少及求得的解为次最佳解等问题。为此，引入进化算法，可有效解决纯粹粗 糙集工具得到的解数目过少及求得的解为次最佳解等问题。本文提出的粗糙集模型下的进化 属性约简算法可同时得到多个最小约简，且算法时间复杂度较低，为数据挖掘的后续步骤打 下了良好的基础。 ( 3 ) 提出基于粒子群及蚁群优化的并行属性约简算法。 蚁群算法的求解效率较低，但蚁群算法本身隐含并行机制。因此，通过蚂蚁之间的并行 可有效缩短算法的执行时间。本文的并行机制采用两种数据抽取策略：随机抽取策略及k - d t r e e 抽取策略。各分布式站点在抽取后的子集上搜索路径，可进一步缩短算法的执行时间并 且减少网络的通信量。 1 4 论文的主要内容 根据国内外租糙集属性约简的研究现状及最其最新发展动态，论文工作主要围绕改进榜 的动态求解效率；改进进化模型，使之适用于粗糙集属性约简，降低进化属性约简算法的嗣 间复杂度；引入并行机制，提高进化算化求解效率等核心内容。具体而言，论文将在以下几 个方面介绍论文研究工作的进展和相应成果。 ( 1 ) 首先介绍粗糙集理论的基本概念，从理论上对粗糙集的知识进行系统的介绍；然后 对两种不同粗糙模型下的约简条件进行了比较，并给出相关结果。 ( 2 ) 针对现实世界数据是动态变化的情况，提出了两个核的动态求解算法，一个是垂直 分布多决策表的增量式求核算法，适用于决策表垂直分布在不同站点的情况；另一个是基亍 数据修改的求核算法，适用于对数据库中表的数据进行修改的情况。两个算法均可可有效拐 高核的求解效率。 ( 3 ) 通过在粗糙集中引入进化算法，提出了改进的基于粒子群优化的属性约简算法和西 进的基于蚁群的属性约简算法。在上述研究的基础上，提出了结合粒子群和蚁群搜索策略雕 属性约简算法，以此得到多个最小约简，增加了用户对约简结果的可选择性。 ( 4 ) 在进化属性约简算法的基础上，为了解决进化算法的求解效率较低问题，引入了爿 5 南京师范大学硕士研究生毕业论文 第一章概述 行机制，采用了随机抽取及k - dt r e e 两种数据埘取策略。提出了基了：粒子群及蚁群优化的并 行属性约简算法，并对两种策略下的并行效果进行了比较与分析。 1 5 论文的组织结构 本文的组织结构如下： 第一章概述。从粗糙集的发展和国内外研究现状，介绍现有的解决方案、发展趋势、 研究意义和仍存在的问题；描述论文的研究方法，给出论文的主要研究内容和论文的组织结 构。 第二章粗糙集知识介绍。阐述粗糙集的基本概念，给出了等价类，决策表等概念，给 出两种模型下的粗糙集核的求解条件、属性约简的条件及两种模型之间的关系，并对两种粗 糙集模型下的约简进行了相关结果的比较。 第三章粗糙集求核算法研究。核的求解有静态核求解方法及动态核求解算法，首先介 绍几种静态求核算法，一种动态核的增量式求解算法：其次，提出两个核的动态求解算法， 垂直分布多决策表的增量式求核算法和基于数据修改的求核算法。 第四章进化属性约简算法研究。首先介绍遗传算法、粒子群算法和蚁群算法的起源及 发展；其次介绍传统粗糙集的启发式属性约简算法；最后，以粗糙集模型为基础，提出改进 的基于粒子群优化的属性约简算法，改进的蚁群算法及结合粒子群和蚁群搜索策略的属性约 简算法。 第五章并行的进化属性约简算法。介绍并行的机制，介绍两种数据抽取的策略，随机 抽取和k - dt r e e 映射策略，提出基于粒子群及蚁群优化的并行属性约简算法。 第六章结束语。首先综述本文在粗糙集模型下的进化属性约简算法所取得的成果；然 后指出现有研究工作的局限性和有待提高和改进的方面，阐述本文下一步将要进行的研究工 作。 6 南京师范大学硕士研究生毕业论文第二章器l 糙集基础知识介绍 第二章粗糙集基础知识介绍 为了更好地理解租糙集理论，本章首先介绍粗糙集的基本概念，从理论上对粗糙集知识 加以系统介绍及解释，其次对粗糙集中两种不同模型之间的核及约简约束条件进行比较并给 出相关结论及相关结果。 2 1 粗糙集基本概念 2 1 1 知识表示系统和等价类 知识表达在智能数据处理中占有十分重要的地位，在粗糙集理论中对知识进行表达和 处理的基本工具是信息表。 定义2 1 1 2 7 l 一个知识表达系统是一个四元组s = u ，v ，r ，厂) ，其中， u = 毛，毛，吒 是有限的样本集合，称为论域；r 是属性集合；净 u 圪，v a 为属性c i 的 o c - ( c u d ) 值域集； f ：u r _ v ，指定了系统中每个对象在各个属性上的取值。 定义2 2 1 2 7 i 一个决策表是一个知识表达系统s = u ，v ，r = c ud ，厂 ，其中，子集c 和 d 分别称为条件属性集和决策属性集。 决策表由c 和d 决定，c 表示条件属性集，d 表示决策属性集。在决策表中，如果 能找到两个对象在条件属性集上值相同，而在决策属性集上值不同，那么该决策表被称为不 一致决策表或不相容决策表，否则称为一致决策表或相容决策表。 定义2 3 1 2 7 i 决策表s = u ，v ，r = c u d ， ，属性集合召c u d 。b 在论域【，上定 义不可分辨二元关系1 n d ( b ) = ( 工，y ) i ( ( x ，y ) u u ) 入( v a b ，f ( x ，口) = f ( y ，口) ) ) a 通过i n d ( b ) 将u 划分为若干个等价类x 。( 1 f q u i n d ( b ) 1 ) ，1 表示集合的基。在 不引起混淆的情况下，也用b 来代替i n d ( b ) 。对于同属一个等价类的对象，在基于划分的 属性上应具有相同的属性值。因此，等价类也就是按照属性值进行分类。符号【x b 示u 中 所有与x 在关系召或f n d ( b ) 下的等价类。等价类是粗糙集中最基本的概念，大部分其他的 概念，如下近似，上近似等原理上都是不同标准下等价类的划分。 2 1 2 基本概念 定义2 4 1 2 7 1 决策表s = u ，y ，r = c u d ，厂 ，设x c _ u 为论域的一个子集，尸c ， x 的关于尸的下近似、上近似分别为尸签= 缸ui 【x 】，彳) 、尸彳= i x u l x 。n x 办； 集合b n ，( x ) = 尸x p 基称为x 的p 边界域；集合n e g p ( x ) = u p x 称为x 的p 负域。 下近似p x ，上近似尸x 是对知识尸做不同粗糙度的刻画。下近似尸x 表示对u 中所 有元素按照属性子集p 划分等价类后，每个能被x 完全包含的等价类都属于下近似。因此， 下近似是由那些根据知识尸判断肯定属于x 的【，中对象组成。上近似p x 除了那部分能被 7 南京师范大学硕士研究生毕业论文第二章瓤糙集基础知识介绍 x 完全包含的等价类外，和x 有交集的等价类也属予上近似。因此，上近似表示由知识p 判 断可能属于x 的u 中对象组成。b n p ( x ) 是那些由知识p 判断，即不能肯定属于x 又不能 肯定属于【，x 的【，中对象组成；n e g ，( x ) 是那些根据知识尸判断，肯定不属于x 的u 中 对象组成。下面给出实例2 1 解释定义2 4 。 实例2 1 设u = x l ，x 2 ，x 3 ，x 4 ，x 5 ，x 6 ，x 7 ，x 8 ) ，u r = x l ，x 5 ，x 6 ， x 3 ，x 4 ， x 2 ，x 7 ，x s ) ，集合x = x l ，x 3 ，x 4 ，x 6 ，x 7 ) 。 对实例2 1 可得x 的下、上近似，边界域，负域如下： r x = x 3 ，x 4 ；r x = x 1 ，工2 ，x 3 ，x 4 ，x 5 ，x 6 ，x 7 ，x s ； b n 月( x ) = r x r 墨= x l ，工2 ，x 5 ，工6 ，x 7 ，x 8 ；n e g r ( x ) = u r x = 。 2 1 3 核与约简 知识约简是粗糙集理论的核心内容之一。众所周知，知识库中知识也就是属性并不是同 等重要的，有的属性是冗余的，不仅影响了数据挖掘的效率，还影响到决策提取的质量。为 此，在保持知识库分类能力不变的条件下，删除不重要的属性有利于效率的提高，及决策质 量的提高。知识约简从两种不同角度出发，可分为代数观及信息观两种模型。首先介绍代数 观下的核与属性约简模型，然后介绍信息观下的核与属性约简模型。 1 代数观下的核与约简 定义2 5 1 2 7 决策表s = u ，矿，r = c ud ， ，设x cu 为论域的一个子集，p c ， 若i n d ( p ) ：1 n d ( c ) ，则称尸为c 的一个绝对约简。 所有条件属性集c 得到一个论域的划分uic = x 。，x ：，以) 。若条件属性集c 的某 个子集p 得到一个论域u 的划分u l p = x i ，x ：，以 ，则【，l c = u l 尸，这两个划分是 等价的。因此，子集尸是决策表s 一个绝对约简。绝对约简只是从条件属性集上对论域上的 划分进行分析，未考虑条件与决策的依赖关系，这显然是不妥的。因此，大多数情况下，我 们研究的是相对约简，考虑决策的作用。 定义2 6 1 2 7 1 给定决策表s = u ，v ，r = c u d ，f 。属性集合君c 对决策属性d 的正 域为：p o s 。( d ) = u 丝。 j _ u ，d 条件属性集c 在论域【，上的划分为ulc = x 。，x 2 ，l ，同样，决策属性集d 在论 域u 上也形成一个划分u l d = i ，艺，z ) 。这两个划分形成了条件属性和决策属性在对 论域样本分类上的知识，若x 。r ( 1 f m ，1 js 门) ，则置正域。只有条件属性值相同 时，决策上不存在冲突的对象属于正域。因此，在决策系统中，正域是论域中信息表达确定、 清晰的那一部分。 定义2 7 1 2 7 i 若属性集b c 是决策表s = u ，v ，r = c ud ，f j 的一个相对约简，则b 要满足两个条件：( d p o s 。( d ) = p o s r ( d ) ：( 2 ) v a b ，p o s n - l a l ( d ) p 0 叉( d ) 通常，如果一个属性约简算法求得的约简集同时满足条件( 1 ) 和( 2 ) ，则该算法称为属性 8 南京师范大学硕士研究生毕业论文第二章瓤糙集基础知识介绍 约简完备算法 6 1 ，也就是p a w l a k 约简：如果只满足条件( 1 ) ，则称为属性约简非完备算法。此 相对约简的定义通常也称为代数观下的属性约简，另外一种相对约简的定义为信息观下的属 性约简，该方面的内容见下部分。对于两个划分u l c ，u l d ，代数观下属性约简的目标是 要从条件属性集c 中发现c 的一个真子集尸，使得【，lp 相对于uld 的分类与uc 相对于 u ld 的分类一致。 定义2 8 m j 给定决策表s = u ，v ，r = c u d ，厂 。该决策表为一致性决策表，当且仅当 。 ， p o s c ( d 1 = u 一致性决策表代表论域表示的信息是确定的、清晰的。正域代表了论域中信息确定，清 晰的那一部分。因此，如果整个论域都是正域，那么决策表就是一致性决策表。 定义2 9 1 2 7 i 给定决策表s = u ，v ，r = c ud ，f ，集合b c ，a b ，如果 p o s b - i 口l ( d ) = p o s b ( d ) ，则称口为b 中不必要的，否则称为b 中必要的。 如果一个属性在约简集中是不必要的，就表示这个属性是约简集中可约的部分。属性约 简的目的就是从条件属性集中发现部分必要属性的集合尸，以此来代替原条件属性集c 。 定义2 1 0 田给定决策表s = u ，v ，r = c u d ，f ，c 的核c o r e ( c ) = a r e d ( ，( d ) ，其 中，r e d o (