（计算机软件与理论专业论文）基于tabu搜索的粗糙集属性约简算法研究.pdf

哈尔滨理t 大学工学硕上学位论文 基于t a b u 搜索的粗糙集属性约简算法研究 摘要 粗糙集理论是z p a w l a k1 9 8 2 年提出的一种处理不精确、噪音的、或 不完整的不确定问题的强大工具，在人工智能，认知科学，或者在不精确知 识表示及推理，机器学习，知识发现等众多领域都有重大的方法论意义。 信息系统的约简是粗糙集理论的关键，为了从信息系统中提取出知识规 则，我们必须把信息约简。约简是在不损失信息表述能力的前提下，求得一 个最小属性集。显然，属性约简是一个提取子集的过程，但同时也是保留了 表述能力，具有最小冗余。许多研究者正在研究高效的特征提取算法。这些 技术已经成功的应用在数据约简，文本分类，文本分析中。 基于记忆的启发式搜索是一种很有前景的智能计算工具，如t a b u 搜 索，在许多组合搜索问题中都表现了优异的性能。然而，在信息系统和数据 挖掘中，他的贡献仍然逊于其他智能工具，如遗传算法、神经网络。本文， 我们提出了一种基于t a b u 搜索的方法，称为t s a r ( t a b us e a r c hf o ra t t r i b u t e r e d u c t i o n ) 来解决信息系统的属性约简问题。t a s r 使用o 1 变量来表示约 简过程中的解，粗糙集的依赖度函数用来度量解的质量，t s a r 的搜索过程 是个长期记忆的高性能禁忌搜索，除了使用的邻域搜索方法，t s a r 还运用 了广泛性和集中性的搜索模式。 本文中的t s a r 算法使用t s 邻域搜索来解决信息系统的属性约简问 题，主要基于两个主要概念：避免访问已经访问过的解；接受下山移动方法 跳出局部最优。保留一些历史信息使搜索进程更智能化，显然，广泛性和集 中性机制通过保存实时的最优约简和每个属性的选择频率而选择更好的解， 期间t s a r 调用三个过程：产生多样解，最优解震动来减小约简集的势， 产生精英解。与文献中算法在1 0 个经典数据集上比较，从试验结果看来， 本文提出的t s a r 算法在约简质量上很有竞争力，且依赖度函数的计算开 销比较小。 关键字粗糙集；属性约简；启发式搜索；禁忌搜索：决策表 哈尔滨理工大学工学硕士学位论文 r e s e a r c ho na t t r i b u t er e d u c t i o n a l g o r i t h mi n r o u g hs e tb a s e d o nt a b us e a r c h a b s t r a c t t h et h e o r yo fr o u g hs e t ( r s ) p r o p o s e db yp a w l a ki n19 8 2e m e r g e sa sa p o w e r f u l t o o lf o rm a n a g i n gu n c e r t a i n t yt h a ta r i s e sf r o m i n e x a c t ，n o i s y ，o r i n c o m p l e t ei n f o r m a t i o n i ti ss h o w nt ob em e t h o d o l o g i c a l l ys i g n i f i c a n ti nt h e d o m a i n so fa r t i f i c i a li n t e l l i g e n c ea n dc o g n i t i v es c i e n c e ，e s p e c i a l l yi nr e s p e c to f t h er e p r e s e n t a t i o no fa n dt h er e a s o n i n gw i t hi m p r e c i s ek n o w l e d g e ，m a c h i n e l e a r n i n g ，a n dk n o w l e d g ed i s c o v e r y r e d u c t i o no fa ni n f o r m a t i o ns y s t e mi sa k e yp r o b l e mi nr st h e o r y w en e e d t og e tr e d u c t so fa ni n f o r m a t i o ns y s t e mi no r d e rt oe x t r a c tr u l e - l i k ek n o w l e d g e f r o ma ni n f o r m a t i o ns y s t e m 。r e d u c ti sam i n i m a la t t r i b u t es u b s e to ft h eo r i g i n a l d a t aw h i c hh a st h es a m ed i s c e r n i b l ep o w e ra sa l lo ft h ea t t r i b u t e si nt h er o u g hs e t f r a m e w o r k o b v i o u s l y ，r e d u c t i o ni sap r o c e s so fe x t r a c t i n ga t t r i b u t es u b s e t ， w h i c hm a i n t a i n st h er e p r e s e n t a t i o n a lp o w e ra n dh a sm i n i m a lr e d u n d a n c y m a n y r e s e a r c h e r sa r em a k i n gt h e i re f f o r t st od e v e l o pe f f i c i e n ta l g o r i t h m sf o rt h e r e d u c t i o no fi n f o r m a t i o ns y s t e m s ，t h e s e t e c h n i q u e sh a v e b e e ns u c c e s s f u l l y a p p l i e dt od a t ar e d u c t i o n ，t e x tc l a s s i f i c a t i o na n dt e x t u r ea n a l y s i s o n eo ft h ep r o m i s i n gc it o o l si sm e m o r y b a s e dh e u r i s t i c s ，s u c ha st a b u s e a r c h ( t s ) ，w h i c hs h o w se x c e l l e n tp e r f o r m a n c ei ns o l v i n gm a n yc o m b i n a t o r i a l s e a r c hp r o b l e m s h o w e v e r ，t h ec o n t r i b u t i o n so fm e m o r y b a s e dh e u r i s t i c st o i n f o r m a t i o ns y s t e m sa n dd a t am i n i n ga p p l i c a t i o n sa r es t i l ll i m i t e dc o m p a r e dw i t h o t h e rc it o o l sl i k ee v o l u t i o n a r yc o m p u t i n ga n dn e u r a ln e t w o r k s t h i sp a p e r p r o p o s e sat s b a s e da p p r o a c h ，c a l l e dt a b us e a r c hf o ra t t r i b u t er e d u c t i o n ( t s a r ) ，t os o l v et h ep r o b l e mo fa t t r i b u t er e d u c t i o no fa ni n f o r m a t i o ns y s t e m t s a ru s e sa0 1v a r i a b l ea st h er e p r e s e n t a t i o no fs o l u t i o n si ns e a r c h i n gf o r r e d u e t s ad e p e n d e n c yd e g r e ef u n c t i o no fr o u g hs e ti si n v o k e dt om e a s u r et h e s o l u t i o nq u a l i t y t h es e a r c hp r o c e s si nt s a ri sah i g h l e v e lt sw i t hl o n gt e r m m e m o r y t h e r e f o r e ，t s a ri n v o k e sd i v e r s i f i c a t i o na n di n t e n s i f i c a t i o ns e a r c h 1 1 哈尔滨理工大学工学硕：i ：学位论文 b e s i d e st h et sn e i g h b o r h o o ds e a r c h t h et s a rm e t h o dp r o p o s e di nt h i sp a p e ru s e st h et sn e i g h b o r h o o ds e a r c h f o rt h er e d u c t i o no fa ni n f o r m a t i o ns y s t e m t sn e i g h b o r h o o ds e a r c hi sm a i n l y b a s e do nt w oc o n c e p t s ，w h i c ha r ea v o i d i n gr e t u r n i n gt oa r e c e n t l yv i s i t e ds o l u t i o n a n da c c e p t i n gd o w n h i l im o v et oe s c a p ef r o ml o c a lm a x i m u mi n f o r m a t i o n s o m e s e a r c hh i s t o r yi n f o r m a t i o ni sr e s e r v e dt oh e l pt h es e a r c hp r o c e s st ob e h a v em o r e i n t e l l i g e n t l y s p e c i f i c a l l y ，t h eb e s tr e d u c t sf o u n ds of a ra n dt h ef r e q u e n c yo f c h o o s i n g e a c ha t t r i b u t ea r es a v e dt o p r o v i d e t h ed i v e r s i f i c a t i o na n d i n t e n s i f i c a t i o ns c h e m e sw i t hm o r ep r o m i s i n gs o l u t i o n s t s a ri n v o k e st h r e e d i v e r s i f i c a t i o na n di n t e n s i f i c a t i o ns c h e m e s ，w h i c ha r ed i v e r s es o l u t i o ng e n e r a t i o n ， b e s tr e d u e ts h a k i n gw h i c ha t t e m p t st or e d u c ei t sc a r d i n a l i t y ，a n de l i t er e d u c t s i n s p i r a t i o n t h ep e r f o r m a n c eo ft s a ri st e s t e dt h r o u g h10w e l l k n o w nd a t a s e t s a n dc o m p a r e dw i t ha n o t h e ra t t r i b u t er e d u c t i o nm e t h o do fr o u g hs e ta ss h o w ni n t h el i t e r a t u r e t h eo b t a i n e dn u m e r i c a lr e s u l t si n d i c a t et h a tt h ep r o p o s e dt s a r m e t h o di sc o m p e t i t i v ef o rt h ea r p r o b l e mi nt e r m so fr e d u c tq u a l i t y m o r e o v e r ， t s a rs h o w sas u p e r i o rp e r f o r m a n c ei ns a v i n gt h ec o m p u t a t i o n a lc o s t so ft h e d e p e n d e n c yd e g r e ef u n c t i o n k e y w o r d sr o u g hs e t ，a t t r i b u t er e d u c t i o n ，h e u r i s t i c ss e a r c h ，t a b us e a r c h ， d e c i s i o nt a b l e i i i 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文基于t a b u 搜索的粗糙集属 性约简算法研究，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期 间独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包 含他人已发表或撰写过的研究成果。对本文研究工作做出贡献的个人和集体， 均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 一 ，卜 作者签名： 梁：建半 日期： 力p 口罗年多月2 t g u 哈尔滨理工大学硕士学位论文使用授权书 基于t a b u 搜索的粗糙集属性约简算法研究系本人在哈尔滨理工大学 攻读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈 尔滨理工大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全 了解哈尔滨理工大学关于保存、使用学位论文的规定，同意学校保留并向有关 部门提交论文和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学 可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内 容。 本学位论文属于 保密 门， 在年解密后适用授权书。 不保密吲。 ( 请在以上相应方框内打) 作者签名：浓建半 导师签名：丁备未磊 日期： 钞罗年多月加日 日期： 钞。夕年岁月2 。日 哈尔滨理工人学工学硕士学位论文 第1 章绪论 1 1 本论文研究的背景及意义 随着计算机应用及i n t e m e t 的日益普及，世界上的数据正以惊人的速度增 长，堆积如山。在这些海量数据中蕴含着大量有价值的信息，如何从大量的、 动态的、不确定的、模糊的甚至是有噪声的数据中快速、有效地挖掘出潜在 的、有利用价值的知识，这需要专门技术与工具。因此，数据挖掘方法和技术 成为数据挖掘研究领域的一个热点。 粗糙集理论与方法是诸多数据挖掘技术中较为有效的一种方法。粗糙集概 念最早是由波兰数学家z p a w l a k 于1 9 8 2 年在计算机与信息科学国际杂 志上发表的论文( ( r o u g hs e t s ) ) 中提出来的。由于最初关于粗糙集理论的研究 大都是用波兰语发表的，因此当时没有引起国际计算机学界和数学界的重视， 研究仅限于东欧的一些国家。直到1 9 9 1 年，z p a w l a k 发表了专著粗糙集 一关于数据推理的理论n 1 ，奠定了粗糙集理论的基础，从此粗糙集理论及其 应用的研究进入了一个新的阶段。 粗糙集理论作为一种处理不精确( i m p r e c i s e ) 、不一致( i n c o n s i s t e n t ) 、不完整 ( i n c o m p l e t e ) 等各种不完备的信息有效的工具，一方面它有成熟数学基础、不需 要先验知识；另一方面易于掌握和使用。粗糙集理论处理不确定性问题时，直 接从给定问题出发，通过不可分辨关系和不可分辨类确定给定问题的近似域， 从中发现隐含的知识，揭示潜在的规律，因此是一种天然的数据挖掘或者知识 发现方法，它与基于概率论的数据挖掘方法、基于模糊理论的数据挖掘方法和 基于证据理论的数据挖掘方法等其他处理不确定性问题理论的方法相比较，最 显著的区别是它不需要提供问题所需处理的数据集合之外的任何先验知识，而 且与处理其他不确定性问题的理论有很强的互补性。 1 2 国内外研究现状 随着粗糙集一关于数据推理的理论一文的发表，国际上掀起了粗糙集 的研究热潮。1 9 9 2 年，在波兰召开了第一届国际粗糙集研讨会，这次会议着重 讨论了集合近似的基本思想及其应用，其中粗糙环境下的机器学习的基础研究 是这次会议的专题之一。1 9 9 3 年在加拿大召开了第二届国际粗糙集与知识发现 哈尔滨理工人学工学硕十学位论文 研讨会，这次会议积极推动了国际上对粗糙集应用的研究。一些著名的知识发 现学者参加了这次会议，并且介绍了许多应用扩展粗糙集理论的数据挖掘的方 法与系统。1 9 9 5 年a c mc o m m u n i c a t i o n 将粗糙集列为新兴的计算机科学的研 究课题。1 9 9 6 年在日本东京召开了第五届国际粗糙集研讨会。1 9 9 8 年在波兰 华沙召开了“第1 届粗糙集和计算的当前趋势”学术会议。1 9 9 9 年在日本召开 了“第7 届粗糙集、f u z z y 集、数据挖掘和粒度一软计算的国际学术研讨会 ， 阐明了当前粗糙集、模糊集的研究现状和发展趋势，指出将着重在软计算、数 据库、削和近似推理定理论和应用方面发展。现在，美国、加拿大、波兰、 日本都有粗糙集研究的专门机构。 粗糙集研究在我国虽然起步晚，但发展较快。1 9 9 6 年王珏、苗夺谦等在 模式识别与人工智能晗1 发表了关于粗糙集理论与应用的论述，介绍了粗糙 集理论的主要原理、基本算法和在知识发现、决策分析等方面的应用，开始了 国内粗糙集理论的研究和应用；1 9 9 8 年曾黄麟编写的粗集理论与应用口3 是 国内第一本关于粗糙集理论的专著；2 0 0 1 年“第1 届中国粗糙集与软计算学术 研讨会 在重庆邮电大学举办。邀请了粗糙集理论创始人z p a w l a k 教授做 大会报告。举行的研讨会推动了亚洲地区和我国对粗糙集理论与应用的研究。 2 0 0 3 年中国人工智能学会粗糙集与软计算专业委员会成立。在2 0 0 5 年9 月在 加拿大举办的粗糙集研究国际会议上，中国学者的论文甚至超过了会议采用论 文总数的四分之一。2 0 0 6 年7 月首届粗糙集与知识技术国际会议在重庆举行。 2 0 0 7 年8 月在山西大学召开了第七届中国粗糙集与软计算学术研讨会。2 0 0 8 年8 月在河南师范大学召开第八届中国粗糙集与软计算学术研讨会。目前，国 内学者从事粗糙集研究的人员越来越多，己形成了一支较为稳定的学术队伍， 中国学者在这一领域的影响也越来越大，正成为这一领域的重要科研力量。 随着粗糙集理论广泛深入地研究以及每年国际国内研讨会成功地召开，粗 糙集理论有了长足地发展。近几年来，粗糙集理论己广泛地在机器学习、数据 库知识发现、决策支持与分析、专家系统、模式识别等领域取得了重大突破。 本文中，对于粗糙集的约简算法的研究正是当前粗糙集领域中一个非常重要的 课题。 粗糙集理论的生命力在于它具有较强的实用性，从诞生到现在虽然只有2 0 多年的时间，但其已在许多领域得到了广泛的应用，并取得了令人鼓舞的成 果。具体表现在以下几个方面： 1 粗糙集应用于智能控制粗糙集根据观测数据获得控制策略的方法称为 从范例中学y - - - j ( l e a r n i n gf o re x a m p l e s ) ，属于智能控制的范畴。基本步骤是：把 哈尔滨理工人学t 学硕士学位论文 控制过程中的一些有代表性的状态以及操作人员在这些状态下所采取的控制策 略都记录下来，形成决策表，然后对其分析化简，总结出控制规则h 5 】。 2 人工神经元网络( a r tif iciain e u r ai n e t w o r k s ，a n n ) 训练时间过于漫 长的固有缺点是制约a n n 实用化的因素之一。j e l o n e kj 等人m 应用r s 化 简神经网络训练样本数据集，在保留重要信息的前提下消除了多余的数据，使 训练速度提高了很多，获得了较好的效果。张赢等口1 将粗糙集和神经网络结合 起来，提出一种用于数据挖掘的粗糙集神经网络结构。通过利用粗糙集理论来 对神经网络的构建及参数选择进行指导，提高了神经网络的工作性能，并为今 后从神经网络中提取语义规则打下了基础。 3 粗糙集应用于医疗诊断在医疗诊断方面，用粗糙集方法根据以往病例 归纳出诊断规则，用来指导新的病例。人工预测早产准确率只有1 7 3 8 ，应 用粗糙集理论可提高到6 8 9 0 哺1 。文献 9 】将粗糙集理论应用于临床医学的诊 断，降低了肺部肿瘤诊断的误诊率。秦中广等n 将粗糙集理论应用于中医类风 湿症状诊断，并在类风湿病的各症状诊断上临床应用。诊断结果显示应用粗糙 集的诊断类风湿准确率大大高于一般的模糊数学方法。陈真诚等3 采用一种基 于粗糙集理论实现胸部x 线数字图象增强的新方法，给临床上的医学工作者提 供清晰的图像。 4 粗糙集应用于决策分析在决策分析方面，粗糙集理论的决策规则是在 分析以往经验数据的基础上得到的，它允许决策对象存在一些不太明确的属 性。王家星等n 2 1 将该方法用于对企业客户进行分类，为客户关系管理的决策支持 提供了新的解决方法。魏建国等n 3 1 对诸如识别银行客户流失的主要表现、影响 金融产品质量的重要因素等进行分析和决策，表现出较高的专业水平。王娟n 铂 提出了一种基于粗糙集理论的操作风险判别方法，对我国国内银行业操作风险 管理提供一个参考模型。 5 粗糙集应用于设备和系统故障检测在设备故障检测方面，要求能快速 发现设备所发生的故障，以便检修。孙海军n 5 3 针对旋转机械故障诊断问题，计 算旋转机械振动故障数据库中的频域征兆，使用粗糙集理论对其进行约简，根 据约简的结果生成规则。利用得到的规则对故障样例进行诊断，提高了故障诊 断的准确率。侯媛彬n 明应用粗糙集约简理论，根据煤矿安全规程分析了煤矿胶 带运输机的l o 种安全保护措施和统计的故障样本，提出了一种以决策表作为 主要工具，直接从故障样本集中导出诊断规则及其故障分类的方法。龚兵等n 刀 利用粗糙集理论应用于网络故障诊断系统中，该方法对解决网络故障特征提 取，提高故障分类正确性等问题有较好的效果。张邦礼等n 8 3 在内燃机神经网络 哈尔滨理t 大学工学硕士学位论文 故障诊断系统的基础上，引入粗糙集理论，对其在内燃机故障诊断特征参数属 性优化中的运用进行了探索。利用差别矩阵算法对决策表进行属性约简，剔除 其中不必要的属性，揭示了故障诊断条件属性内在的冗余性，降低了神经网络 构成的复杂性。徐德友n 钔提出了一种基于粗糙集和神经网络的错误诊断方法， 其根据粗糙集相关理论提取原始错误信息的关键信息，作为神经网络训练集。 该方法提高了神经网络的噪音容忍能力，并且有效地降低了侦测系统的误警 率。 6 网络安全中的应用随着计算机网络信息系统逐渐成为国民经济发展的 支柱，网络信息安全成为世界各国共同关注的焦点。实践证明，仅仅依靠防火 墙、用户身份认证系统等安全措施，难以完全保证网络和计算机系统安全。蔡 忠闽等啪1 将粗糙集理论应用于异常检测正常模型的建模过程，从较小的正常系 统调用序列样本中提取出预测规则作为正常模型来进行异常检测，建立 s e n d m a i l 进程的简单正常模型，进行高效的在线异常检测。实验表明，该模型 可以将进程的正常行为和异常行为( 包括攻击行为和配置错误下的行为) 区分开 来，检测效果要好于以前提出的模型。马洪江乜1 1 将粗糙集与关联规则结合作为 数据挖掘的工具，对入侵检测中采集的网络数据集进行分析、知识约简，从中 挖掘出一些对用户有用的潜在规则，不再依赖专家的经验，使入侵检测具有更 好的灵活性、智能性。网络安全在军事上越来越受到各国军方的重视，网络攻 击效果评估技术的研究具有重要意义。进行网络攻击效果评估需要建立一套评 估指标体系，针对具体的攻击，评估体系中指标的重要性各不相同。王会梅等 乜羽运用粗糙集理论确定体系中各指标之间的关系，使评估指标的权重分配赋值 更加科学、合理。s u r a ts r i n o y 瞳3 1 利用支持向量机和粗糙集相结合的方法维 护计算机网络安全。 7 粗糙集在电力系统的应用复杂电力系统是一个巨维的典型动态大系 统，它所面临的问题，或者无法建立精确的数学模型，或者不能单纯用数学模 型来描述晗钔。r s 理论在电力系统的研究起步较晚，1 9 9 7 年，巴西学者 l a m b e r t 发表了第一篇将r s 理论运用于电力系统的文章口副。近几年，r s 在 电力系统领域的研究逐渐显示出广阔的应用前景，其应用研究可概括为电力设 备故障诊断陋蚓，配电网故障诊断幽1 ，暂态稳定评估，电力系统燃料管理啪1 ， 电压无功综合控制口，电力能源消费欺诈的侦测口2 1 ，空间负荷预测口3 3 等方面。 粗糙集理论的应用领域还包括：图象处理3 、商业数据挖掘跚、材料科学 中的晶体结构分析啪1 、预测建模 、结构建模啪1 、军事作战口们，银行信用评估 【蚰】乃宣 弋to 哈尔滨理下大学工学硕上学位论文 1 3 本文研究内容 信息系统的约简是粗糙集理论的关键，为了从信息系统中提取出知识规 则，我们必须把信息约简。约简是在不损失信息表述能力的前提下，求得一个 最小属性集。本文的研究目的就是在保留信息系统表述能力的前提下，提取属 性集的子集，且具有最小冗余，并且验证算法在数据集比较大、解维数比较高 的情况下，时间开销的变化情况。 t a b u 搜索h 是一种基于记忆的启发式搜索，是一种很有前景的智能计算工 具，在许多组合搜索问题中都表现了优异的性能。本文，我提出了一种基于 t a b u 搜索的方法，称为t s a r ( t a b us e a r c hf o ra t t r i b u t er e d u c t i o n ) 来解决信息系 统的属性约简问题，并和其他属性约简算法做对比。本文的主要研究工作如 下： 1 本文深入分析禁忌搜索算法的基本原理，结合算法的基本流程和影响算 法结果的若干参数，将要设计出独特的算法优化策略。 2 本文使用0 1 变量来表示约简过程中的解，解向量中的1 表示属性集中 含有这个属性，否则不存在此属性。0 1 表示使得文本的预处理和文本向量化 过程简单化，但是简单化的解表示是否损失信息系统的表述能力，在大数据集 和高维数的情况下，算法性能变化如何。 3 本文使用粗糙集的依赖度函数度量解的质量，粗糙集的理论基础可以保 证依赖度函数度量解的质量时不丢失信息的表述能力，本文在试验分析中对此 进行验证，并且分析各个数据集在求依赖度函数值时的计算开销。 4 本文把全0 解、全1 解、经常访问的解放在t a b u 列表中，设计一个过 程来产生邻近候选解，运用了广泛性和集中性的搜索模式，最后借助精英约简 方法得到最小约简。广泛性把搜索过程带到新的解区域，使其逃离局部最优的 过程。在经过数次迭代，仍旧没有找到改进解的情况下，应用集中机制进一步 提炼已经找到的最优约简。得到了属性核以后，我们用精英约简方法反其道而 行往属性核中增加属性，最终得到最小约简。 5 本文使用多个参数控制各个算法模块的执行，且根据不同的数据集和初 始解智能化设置算法参数，进而优化算法，使试验结果与初始解的选择不敏 感。 哈尔滨理1 二大学工学硕士学位论文 1 4 本文组织结构 本论文主要分为5 个章节，各章的内容安排如下： 第1 章绪论 主要介绍了论文的研究背景和研究意义、粗糙集理论的产生、发展以及国 内外研究现状，论文的主要研究内容和组织结构。 第2 章粗糙集理论基础与属性约简 本章介绍了粗糙集理论的背景知识和基本概念：集合论基本概念，知识的 含义、信息系统、不可分辨关系、上下近似的定义等，重点阐述了信息系统中 属性约简，由属性的依赖性和重要性来判断属性是否是必需的，从而约简属性 集，得到属性核，最后用一个决策表实例说明其定义及决策规则的生成和决策 表的简化。 第3 章禁忌搜索算法及其优化策略 本章首先概述一般的禁忌搜索算法，然后从禁忌搜索的基本思想，基本流 程，影响算法结果的几个参数详细论述。禁忌搜索是一个启发式搜索算法，具 体实现有许多变形，具有很大的弹性，本文又针对邻域和邻域搜索，禁忌表和 禁忌表的大小，短期记忆和长期记忆，改变搜索路径的方法和期望指标，停止 准则这几个关键参数来讨论禁忌搜索算法的优化策略。最后说明了禁忌搜索算 法在众多领域的广泛应用。 第4 章基于t a b u 搜索的粗糙集属性约简算法 本章主要研究粗糙集的属性约简问题，首先简单介绍了两个常见的一般性 粗糙集属性约简算法，并对算法优缺点进行简单的分析。然后，结合禁忌搜索 和粗糙集的基本理论，本文提出了一种新的属性约简算法t s a r 算法，从该算 法中解的表示，解的度量，禁忌列表，初始解的选择展开论述，深入分析了算 法的核心广泛性和集中性模式，最后提出了完整的t s a r 算法。 第5 章算法评价及试验分析 本章主要是t s a r 算法的仿真试验，对算法进行评价验证。文中从算法数 据集的选取，具体的实验环境，智能化多参数的设置都做了详细的说明，对数 值试验的结果进行分析，并与文献中的算法结果进行比较。 最后是本文的结束语，对所做工作加以总结，展望下一步工作重点。 哈尔滨理工火学- t 学硕士学位论文 第2 章粗糙集理论基础与属性约简 粗糙集理论是由波兰数学家z p a w l a k 在1 9 8 2 年提出的。自提出以来， 已经经历了十多年的发展，在系统理论、计算模型建立和应用系统研制开发 上，都己取得了很多成果，建立了一套较为完善的粗糙集理论体系。它是一种 处理含糊和不精确的新型数学工具。其主要思想是在保持分类能力不变的前提 下，通过知识约简，导出问题的决策或分类规则。近年来由于在知识发现等领 域得到了成功的应用而受到国际上广泛关注。不可分辨关系是粗糙集理论中的 一个重要概念。粗糙集理论就是以不可分辨关系为基础，将属性分为条件属性 和决策属性，对数据库中的实例根据各个属性不同的属性值分成相应的子集， 然后对条件属性划分的子集与决策属性划分的子集之间的上下近似关系生成判 定规则。 为了引出粗糙集理论，首先介绍一下经典集合理论的一些基本概念及定 义。然后主要对知识和信息系统，不可分辨关系，上近似和下近似等粗糙集基 本概念，信息系统中属性的依赖性，重要性，属性约简和核的定义，决策表的 概念及决策规则的生成，决策表的简化的几个方法都进行了详尽的介绍。以便 为以后各章的展开做好铺垫。 2 1 集合论基本概念及定义 粗糙集理论h 3 3 是由经典集合理论发展而来的，在讨论粗糙集理论之前，首 先介绍一下经典集合理论的一些基本概念及定义。 定义2 1 集合：按照某一目的或特点，将被研究对象组合在一起形成的整 体，就叫做集合。集合中的每一个对象称为集合的一个元素。 定义2 2 论域玑在对现实问题进行处理时，局限在某一个特定区域范围 之内的现实个体( 或称元素、对象、样本) 所构成的非空有限集合，称为论域， 记为u 。 定义2 3 有序对：设有集合a 和b ，a a ，b b ，则称( 口，6 ) 为有序对。有 序对与顺序有关，( 口，6 ) 和( 6 ，口) 是两个不同的有序对。当么和b 是同一个集合 时，有序对中的两个元素来自同一个集合。 定义2 4 笛卡儿积：集合4 、b 的笛卡尔积a xb ，是二元组集合 ( 口，6 ) la ar 、b b ) 。 哈尔滨理工火学工学硕士学位论文 定义2 5 二元关系：集合彳、b 的笛卡尔积a xb 的子集叫做彳到b 的一 个二元关系只。 对于集合彳和b 之间存在二元关系r ，a a ，b b ，通常记为：a r b 。当 彳和b 是同一个集合时，就称为集合么上的一个关系尺。由此看出，二元关系 尺是一个集合。除了二元关系外，还有三元关系、四元关系等，其中二元关系 最为重要，在不作特别说明的情况下，关系通常都指的是二元关系。 定义2 6 关系的性质：设尺是彳上的二元关系， 1 自反性：如果么中的每一个元素x 与其自身之间都有关系r ，记为 x r x ，则称r 是自反的； 2 对称性：如果彳中的任意元素x 和y 都有x r y 蕴涵着y r x ，则称r 是对 称的； 3 传递性：如果a 中的任意元素想x 、y 、z ，有x r y 且y r z 蕴涵着x r z ， 则称尺是传递的。 根据集合的基本概念和集合之间的关系及特性，我们可以得到以下比较重 要的概念。 定义2 7 等价关系：如果集合4 上的关系尺是自反的、对称的和传递的， 则称尺是等价关系。 定义2 8 等价类：所有与元素a 具有等价关系r 的元素构成的集合，称为 a 所生成的等价类，记为【口k ，即 口】r = 和ix a ，且( 口，x ) r 。 对于同一个集合彳上的等价关系，显然存在性质：对于v 玩a ，或者相 等，【q 】r - - a j 尺且o ，) ；或者交集为空，当u q k = u ，f ，时， h 】r n a j r = 囝。 2 2 粗糙集基本概念 在传统的数学集合理论中，一个对象与集合的关系只有两种：存在和不存 在。而在粗糙集理论中，对象和集合之间的关系变为三种：在集合中、不在集 合中、可能在集合中。 粗糙集理论假定知识是一种对对象进行分类的能力，也就是说，知识必须 与具体或抽象世界的特定部分相关的各种分类模式联系在一起，这种特定部分 称之为论域，简称为域。对于论域及知识的特性并没有任何特别假设，事实 上，知识构成了某一感兴趣领域中各种分类模式的一个族集，这个族集提供了 关于现实的显事实，以及能够从这些显事实中推导出隐事实的推理能力。 哈尔滨理工大学下学硕1 ：学位论文 2 2 1 知识和信息系统 定义2 9 给定一定有限的非空对象集合矾称为论域。v x u ，称为u 中的一个概念( c o n c e p t ) 或范畴( c a t e g o r y ) 。r u u 表示u 上的一个等价关 系。等价关系r 将所有集合u 划分为不相交的子集，记为 u r = 五，五，以) ，表示r 的等价类的族，关于u 的一个知识。 】_ 秒ui 脚) 表示关系r 下包含元素x 的等价类。( u ，r ) 称为近似空间。 定义2 1 0 一个信息表知识表达系统s h 3 1 可以表示为： s = ，a ，v ，厂)( 2 1 ) 其中， u = 而，镌9 oo s 毛 为对象的非空有限集合，即论域； a = a i ，a 2 ， 为属性的非空集合；v 为属性值域，v = u g o ；f ：u xa 寸v 为一信息函数，表示对每一个口a ，x u ，f ( x ，口) 圪。当信息系统中属性 a = c u d 是属性集合，c 和d 分别称为条件属性集和决策属性集，信息系统 也称为决策系统，故s 也叫决策表。 2 2 2 不可分辨关系 定义2 1 1 不可分辨关系i n d ( p ) h 鄹：对于每个属性子集p 尺且p f 2 j ， 则p 中的全部等价关系的交集称为p 上的一个不可分辨二元关系，也叫不分明 关系，记为i n d ( p ) 。 i n d ( p ) = ( x ，y ) l ( x ，y ) u xu ，v a p ，f ( x ，口) = f ( y ，口) ( 2 2 ) 如果( x ，y ) i n o ( p ) ，则称x 和y 是p 不可区分的，且有v 尸么。从上可 以看出不可分辨关系i n d ( p ) 也是u 上的一个等价关系。它把u 划分为有限个 集合，称为等价类。在每一个等价集合中，对象间是不可分辨的。由不可分辨 关系导出的等价类构成了知识的粒度，从而产生了不确定性。这种不确定性和 模糊集所产生的不确定性不同，是由于知识的不完备性产生的，而模糊集的不 确定性是由一于自身概念的不确定性产生的。 粗糙集之所以能够描述知识的不确定性，正是基于知识表达中的不可分辨 关系。通过一个不可分辨关系，可以得到决策系统的一个划分，我们称划分后 的等价类为不可分辨类。基于某个属性集彳的所有等价记录的集合，被定义为 等价类。【叫p 表示包含元素的尸等价类，对于v x u ，它的尸等价类定义为： 【x 】p = j ，ui ( x ，y ) i n d ( p ) ( 2 3 ) 哈尔滨理工人学工学硕十学位论文 即表示与记录x 具有等价关系p 的记录归为一类，此分类成为p 基于属性 集彳的划分，表示为u i n d ( p ) = 置，最9 , e * 9 只) 。 在粗糙集理论中，我们所要表达的某个子集是完全确定的。但是由于知识 粒度的存在，完全确定的子集不能被表达成由这些粒度产生的基本模块的并 集。这样的子集，我们就称为粗糙集。而对于能够由这些粒度产生的基本模块 的并集所表达成的子集，则称为精确集。 粗糙集不能被表示成基本模块的并集，只能包含这些基本模块中的一部 分。即对于粗糙集石一个基本模块要么属于集合疋要么不属于集合丘下 面涉及到的粗糙集的上近似和下近似就是定义粗糙集的方法。 2 2 3 上近似和下近似 定义2 1 2 粗糙集对不确定概念的描述是通过下近似( 记为星( x ) ) 和上近似 ( 记为尺( x ) ) h 3 1 这两个精确概念来表示的。上近似和下近似构成了粗糙集研究中 的两个基本运算。 对于每个集合x 互u 和不分明关系r ，x 的上近似和下近似可以用下列式 子来表示： 包含在x 中的最大可定义集称为x 的r 下近似： 墨( x ) = x ui 【x 】r x )( 2 4 ) 即所有包含在集合彳中的等价类的并集。 包含x 的最小可定义集称为x 的r 上近似： r ( x ) = x ui 【x 】rn x a )( 2 - 5 ) 即所有与x 的交集不为空且不包含在集合x 中的等价类的并集。 上面给出的粗糙集定义可以通过上下近似来解释： x 为r 的精确集，当且仅当宣( x ) = r ( x ) ； x 为r 的粗糙集，当且仅当r ( x ) r ( x ) 。 通过粗糙集的上下近似可以将一个论域u 划分为三个不同的区域，分别 是：正区域、负区域和边界区域。正区域中的元素完全属于集合咒负区域中 的元素完全不属于集合x ；边界区域中的元素可能属于、也可能不属于集合 丘下面是三个区域的定义： 定义2 1 3 一个集合x u 和不可分辨关系尺，x 的尺的正域( p o s i t i v e r e g i o n ) 、负域( n e g a t i v er e g i o n ) 和边界域( b o u n d a r yr e g i o n ) 定义： 哈尔滨理工大学工学硕士学位论文 正域： 负域： 边界域： p o s r ( x ) = 垦( x ) n e g r ( x ) = u r ( x ) b n r ( x ) = 尺( x ) 一星( x ) ( 2 6 ) ( 2 - 7 ) ( 2 8 ) 论域u 边界域 糙集x 图2 - 1 粗糙集概念关系图不 f i g 2 - 1r e l a t i o no f c o n c e p ti nr o u 曲s e t 在实际应用中，人们通常要考虑的一个重要问题是：信息系统中的各个属 性之间是否具有某种依赖关系，即从一个给定的知识中能否导出另一知识? 这 就是所谓的属性依赖性问题。 定义2 1 4 设集合彳是论域u 上的一个关于尺的粗糙集，定义x 关于尺的 近似精度为： 州) = 黜( 2 - 9 ) 其中x 彩，i 1 表示集合中所含元素的数目，称集合的基数或势 ( c a r d i n a l i t y ) 。 显然，o ( x ) 1 。当( x ) = 1 时，表示不存在边界域，则称集合x 相 对于r 时清晰的；当a r ( x ) 0 ，则集合x 关于r 是粗糙集合。 x 的r 粗糙度与精确度恰恰相反，表示的是集合x 的知识不完全程度。 定义2 1 6 信息系统论域中元素x 对集合x 的粗糙隶属函数定义为： 小，= 罐群 ( 2 1 1 ) 粗糙隶属函数表示在关系足下元素x 对集合x 的隶属程度。显然， , u x ( x ) 【o ，1 】。 2 3 属性的约简和依赖性 在信息系统中，判断属