（计算机应用技术专业论文）粗糙集和蚁群优化方法在特征选择中的应用研究.pdf

摘要 帆ii l l l lt 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 y 17 4 6 6 3 6 摘要 特征选择已经成为数据挖掘、机器学习、模式识别等领域的研究热点。 特征选择用更稳定的特征集合以适当的精度表示原始特征集合。特征选择的 研究主要集中在两个方面，一是搜索特征子集时所需要的搜索策略，二是特 征子集的性能评价方面。因此，研究更为有效的特征选择算法，有效地获取 较优的特征子集，降低算法的时间复杂度和寻求快速的特征选择算法仍然是 特征选择研究的重点。本文根据基于粗糙集的特征选择和基于蚁群优化方法 的特征选择算法两种方法所具有的优势和存在的不足，提出一种将粗糙集方 法和蚁群优化方法相结合的特征选择算法。其主要工作包括以下几个方面： 首先，简要介绍了粗糙集理论和蚁群优化算法的相关知识，包括信息表 达系统，上近似和下近似，属性约简与核，属性依赖度和重要度等概念和对 蚁群算法的理论知识的总结概述。 其次，对特征选择算法的进行了概要性分析。着重对基于粗糙集属性重 要度的特征选择算法( 贪婪法) 和基于蚁群优化方法的特征选择算法进行了深 入研究。 再次，在分析基于粗糙集的特征选择方法和基于蚁群优化方法的特征选 择算法所具有的优势和存在不足的基础上，本文提出了一种基于粗糙集蚁群 优化方法的特征选择算法。所提出的算法通过引入粗糙集相对核属性作为特 征选择的起点，以便提高算法的准确性；在转移规则和信息素更新策略中， 引入了粗糙集属性依赖度和属性重要度，用于指导蚂蚁的搜索过程，以便提 高算法的性能；此外，将粗糙集理论的分类精度和特征子集长度两个参数应 用于评价函数中，以衡量特征子集的优劣；通过选择不同数据个数和属性个 数的数据集对所提出的方法进行了测试，同时与基于粗糙集的特征选择方法 和基于蚁群优化方法的特征选择算法进行了比较实验。测试与比较实验结果 表明，所提出的方法可行的，并且对具有核属性的数据集在特征子集长度和 精度两个指标上具有明显优势。 最后，对论文的研究工作进行了总结，并提出了下一步的工作展望。 关键词：粗糙集；蚁群优化方法；特征选择；属性依赖度；属性重要度 a b s t r a c t a b s t r a c t f e a t u r es e l e c t i o nh a sb e c o m et h ef o c u sr e s e a r c hi nt h ef i e l do fd a t am i n i n g , m a c h i n el e a r n i n g ，p a t t e r nr e c o g n i t i o na n ds oo n f e a t u r es e l e c t i o nu s e sam o r es t a b l e s e ta n d a p p r o p r i a t ep r e c i s i o n c h a r a c t e r i s t i c st od e s c r i b et h e o r i g i n a l f e a t u r e s e t f e a t u r es e l e c t i o nr e s e a r c hh a sf o c u s e do nt w oa s p e c t s ：o n ei sf o rt h es e a r c h s t r a t e g yo ft h es u b s e ta n dt h eo t h e ro n ei st h ep e r f o r m a n c ee v a l u a t i o nf e a t u r es u b s e t t h e r e f o r e ，t h er e s e a r c ho nm o r ee f f e c t i v ef e a t u r es e l e c t i o na l g o r i t h m ，t oo b t a i nt h e b e t t e rf e a t u r es u b s e t ，t or 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 ma n dt of i n dt h e f a s tf e a t u r es e l e c t i o n a l g o r i t h m i ss t i l lf o c u so ft h e s t u d yo ff e a t u r es e l e c t i o n a c c o r d i n gt ot h e d e f e c t sa n dd e f i c i e n c i e so ft h ec u r r e n ta l g o r i t h m ，t h i sp a p e r p r o p o s e dan e wm e t h o df o rf e a t u r es e l e c t i o nw h i c hc o m b i n e dt h er o u g hs e tm e t h o d a n da n tc o l o n yo p t i m i z a t i o na l g o r i t h m t h em a i nc o n t r i b u t i o no ft h i st h e s i si n c l u d e s ： f i r s t l y , t h et h e s i s r e v i e w st h et h e o r i e sa n dm e t h o d so fr o u g hs e t ，i n c l u d e i n f o r m a t i o ne x p r e s s i o ns y s t e m ，t h ea p p r o x i m a t i o na n dl o w e ra p p r o x i m a t i o n ，a t t r i b u t e r e d u c t i o na n dc o r e ，a t t r i b u t ed e p e n d e n c y , a n dt h ec o n c e p t so fi m p o r t a n c ea n dt h e s u m m a r yo v e r v i e wo f t h et h e o r e t i c a lk n o w l e d g eo f t h ea n tc o l o n ya l g o r i t h m s e c o n d l y , w eh a v es t u d ya n da n a l y s i st h e f e a t u r e s e l e c t i o na l g o r i t h m s i n p a r t i c u l a r , f e a t u r es e l e c t i o na l g o r i t h m sb a s e do nr o u g hs e t s ( g r e e d ym e t h o d ) a n dt h e a n tc o l o n yo p t i m i z a t i o nh a v eb e e ns t u d i e d t h i r d l y , b ya n a l y z i n g t h e a d v a n t a g e s a n d d i s a d v a n t a g e s o ft h e e x i s t i n g a l g o r i t h m s ，t h ec u r r e n ts h o r t c o m i n g sa n dd e f i c i e n c i e so fm e t h o d sh a v eb e e nf o u n dt o p r o p o s ean e w m e t h o df o rf e a t u r es e l e c t i o nw h i c hc o m b i n e dt h er o u g hs e tm e t h o d a n da n tc o l o n yo p t i m i z a t i o na l g o r i t h m t oi m p r o v et h ea l g o r i t h m sp e r f o r m a n c e ，t h e c o r ea t t r i b u t ea st h es t a r to ft h ef e a t u r es e l e c t i o n i nt h et r a n s f e rr u l e sa n dt h e p h e r o m o n eu p d a t es t r a t e g y , t h i sa l g o r i t h mu s e sr o u g hs e td e p e n d e n c ya n da t t r i b u t e s s i g n i f i c a n c et og u i d et h ea n t s s e a r c hp r o c e s st o i m p r o v et h ep e r f o r m a n c eo ft h e a l g o r i t h m i na d d i t i o n ，t h eq u m i t yo fc l a s s i f i c a t i o nb a s e do nr o u g hs e tm e t h o da n dt h e l e l , g t ho ft h ef e a t u r es u b s e ta r eu s e dt om e a s u r et h es t r e n g t h sa n dw e a k n e s s e so f a b s t r a c t f e a t u r es u b s e t b yc h o o s i n gad a t as e tw i t hc e r t a i nn u m b e ro fd a t aa n da t t r i b u t e st h e p r o p o s e dm e t h o di st e s t e dt oc o m p a r ew i t ht h e f e a t u r es e l e c t i o nm e t h o db a s e do n r o u g hs e ta n dt h ef e a t u r es e l e c t i o nm e t h o db a s e do na n tc o l o n yo p t i m i z a t i o n t e s t i n g a n dc o m p a r i s o nr e s u l t ss h o wt h a tt h ep r o p o s e dm e t h o di sf e a s i b l ea n dt h i sm e t h o dh a s o b v i o u sa d v a n t a g e si nt h ei n d i c a t o r sf e a t u r es u b s e tl e n g t ha n da c c u r a c yw h e nt h ed a t a s e th a v ec o r ea t t r i b u t e s f i n a l l y , t h ep a p e rr e s e a r c hw a ss u m m a r i z e d ，a n dt h ef u t u r ew o r kp r o s p e c t e d k e yw o r d s ：r o u g hs e t ；a n t c o l o n yo p t i m i z a t i o n ；f e a t u r es e l e c t i o n ； d e p e n d a b i l i t yo f a t t r i b u t e ；s i g n i f i c a n c eo f a t t r i b u t e i v 目录 目录 摘要t t a b s t r a c t t t t 第l 章绪论l 1 1 研究的背景及意义1 1 2国内外研究现状2 1 3 论文的主要研究内容4 1 4 论文的组织与结构5 第2 章粗糙集和蚁群算法的相关知识一6 2 1 粗糙集的基本理论6 2 1 1 信息表知识表达系统6 2 1 2 上近似、下近似和粗糙集7 2 1 3 属性约简与核8 2 1 4 属性依赖度和属性重要度9 2 2 蚁群算法的理论基础9 2 2 1 蚁群算法的基本原理9 2 2 2 蚁群算法的基本模型及其实现1 l 2 2 3 蚁群算法的研究与应用1 4 2 2 4 蚁群算法存在的问题l5 2 3 本章小结15 第3 章特征选择算法的研究与分析1 6 3 1 特征选择研究的历史与现状1 6 3 2 特征选择的定义及一般过程1 8 3 3 特征选择算法的研究与分析1 9 3 3 1 一般特征选择算法概述1 9 3 3 2 典型特征选择算法介绍2 0 3 4 本章小结2 5 v 目录 第4 章基于粗糙集和蚁群优化的特征选择2 7 4 1基于粗糙集和蚁群优化的特征选择算法的基本思想2 7 4 2 基于粗糙集和蚁群优化的特征选择算法的模型”2 8 4 2 1 算法模型“2 8 4 2 2 基于粗糙集方法的转移规则和信息素更新策略2 9 4 2 3 基于特征子集长度和属性依赖度的评价函数3 1 4 3 算法描述及流程图一3 l 4 4 算法中各参数选取分析”3 3 4 4 1 信息素挥发系数3 4 4 4 2 启发式因子一3 4 4 4 3 蚂蚁数量3 5 4 5 算法的实验比较与结果分析“3 5 4 5 1 实验环境3 5 4 5 2 不同特征选择方法的比较测试- 3 6 4 5 3 算法中主要参数分析实验4 0 4 6 本章小结一4 2 第5 章总结与展望4 3 5 1 本文工作总结4 3 5 2 未来工作思考4 4 致谢4 5 参考文献4 6 攻读学位期间的研究成果5 0 第一章绪论 1 1 研究的背景及意义 第1 章绪论 在数据挖掘( 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 n ) ，机器学习 ( m a c h i n el e a r n i n g ) 和信号处理( s i g n a lp r o c e s s i n g ) 等研究领域，数据集通常 含有大量的特征。因此，从原始数据集中进行特征选择就显得尤为必要n 屯1 。特 征选择是指从一个给定数据集的原始特征集合中选择一个特征子集的过程。该 特征子集应该必须能够充分地表现出潜在的知识或者规律，以适当高的精度表 示原始特征集合。特征选择的重要性在于降低学习算法所处理的问题的规模和 结果搜索空间大小。尤其是在模式识别中的分类器设计中，特征选择可以提高萨：一 分类质量和速度1 。 由于现实的数据集中存在大量的噪声、不相关性和易误解的特征，因此越 来越需要特征选择具有处理现实问题中的不精确、不一致信息的能力。粗糙集门1 ( r o u g hs e t ) 理论是波兰数学家z p a w l a k 于1 9 8 2 年提出的，是一种新的处理 含糊性和不确定性问题的数学工具。目前，粗糙集己成为人工智能领域的一个， 研究热点，在机器学习、模式识别、智能控制、决策分析、知识获取、数据挖 掘等许多领域得到了广泛的应用。 粗糙集可以处理不确定性和含糊性问题，可以在不一致数据中发现模式。 粗糙集已经成为模式识别中一个有用的特征选择方法h 1 。基于粗糙集方法的特征 选择就是要选择一个具有和原始特征集合一样的预测决策概念能力的特征( 或 属性) 子集。基于粗糙集方法的特征选择的优势在于找到最短或最小约简，而同 时基于所选特征可以构造较高质量的分类器哺，。 蚁群优化算法是近年来才发展起来的一种新型的仿生型的智能优化算法， 具有正反馈、分布计算和鲁棒性强等特点。蚁群优化算法的思想来源于现实世 界中的蚂蚁群体觅食行为的智能特性。在现实中，单个蚂蚁并不具备通过最短 路径寻找食物的智能行为，然而由许多蚂蚁所构成的蚁群在经过一段时间的调 整以后，通过个体之间的相互配合与协作，最后能够使整个蚁群沿着某条最短 的路径将食物搬回到蚁巢。作为计算智能和群智能的重要分支之一，蚁群优化 第一章绪论 算法的研究方兴未艾，备受瞩目。 特征选择是分类系统中最重要的一个步骤。在目前各种分类问题中，尤其 是文本分类中如何有效降低特征空间的维数是这些分类系统需要解决的主要问 题。粗糙集理论是有效处理不确定问题的有效数学工具，而蚁群优化算法是新 颖的仿生型的智能优化算法。本课题将两种先进方法有机结合，能发挥各自的 优势和弥补对方的不足，从而为不确定分类问题的特征选择提供一种有效的解 决方案。因此，探索二者之间的有机结合，无疑具有较好的理论意义和较高的 应用价值。 1 2 国内外研究现状 目前，有许多基于粗糙集理论的算法用于特征选择。最小约简的办法是首 先通过约简得到所有可能的约简，然后选出具有最小势的约简。这可以通过从 数据中构造区分函数( d i s c e r n i b i l i t yf u n c t i o n ) ，然后化到最简。s t a r z y k 使 用强等价关系来简化区分函数n 利。很明显，这种解决问题的办法代价是昂贵的， 并且不适合于大规模的数据集。已经证明，产生最小约简问题是n p h a r d ，并且 产生所有约简的问题是指数的h 吖一3 。因此，就必须考虑启发式方法。 通常，有两类基于粗糙集理论的方法用于特征选择，爬山法( h i l 卜c l i m b i n g ) 或称为贪婪( g r e e d y ) 算法，以及随机方法n0 l 。爬山法通常用粗糙集的属性重要 度作为启发式信息，从一个空集或属性核开始，然后采用前向选择或后向删除 方法。爬山法在处理具有较少噪声和小数量的特征时会很有效，然而不能保证 最优。随机方法能提供一个更稳健的方案，但是以增加计算量为代价u 。对于 要求最优或最小特征子集的系统( 例如由于特征评估代价的昂贵) ，就需要使用 随机特征选择。 前向选择依次添加特征，每次从候选集合选择一个最重要的属性，添加到 特征子集中去。直到所选的特征子集是一个约简为止。后向删除方法却相反， 是从一个全属性集合开始，不断删除属性，直到集合满足约简要求。h ux 给 出一个约简算法，使用基于正域的属性重要度作为启发式信息n 2 q 们。王国胤提出 一个基于条件信息熵的约简算法，使用基于条件信息熵的启发式信息。近似约 简和近似熵约简的方法也同样被人们研究过，这在强调得到更! 扮条件属性而不 是高的分类耗皮搿u 情况下会徽有用。 h jk 利崩来白区分矩阵的启发式思想计算 2 第一章绪论 属性重要度，并提出了一个启发式约简算法。s u s m a g a 同时考虑了属性约简算法 中的区分关系和不可区分关系n 引。 基于正域和条件熵的方法选择一个能完全描述给定数据集中所有概念和潜 在规律的最小特征子集。基于区分矩阵的方法的目的是要选择一个有较高区分 能力的特征子集，以确保最大类简分离性。这些方法考虑最佳候选属性，尽力 发现一个最小约简。然而，爬山法方法并不能保证找到最优或最小约简，因为 不存在完备的启发式信息，因此最优性不能保证。使用属性重要性区分候选属 性会导致搜索沿着一条非最小的途径下去。难以预测通过添加或删除单一属性， 哪一个属性子集组合最终会导致一个最优约简。 一些研究者使用随机方法进行粗糙集特征选择n 引。w r o b l e w s k i 使用遗传算 法寻找最小约简。他将遗传算法和贪婪搜索算法相结合以产生最小约简。然而 使用了高度耗时的操作算子，而且不能保证最终结果子集是一个真正的约简。 b j o r v a n d 用遗传算法计算近似约简。他以w r o b l e w s k i 的工作为基础，做了一 些变更并确实改善了速度和近似质量。为了获得一个好的遗传算法初始种群， 他把属性核包括在所有候选个体中。并运用领域知识获得实际约简的平均大小， 令候选个体中的属性个数接近于约简大小。而且，他允许用于为每个属性指定 一个相对权重。为了避免在一些错误的搜索方向上浪费太多处理时间，采用了 一个与种群中冗余成比例的动态变异率，禁止所有的个体变得一样。z h a i 基于 粗糙集理论和遗传算法提出了一个整体特征提取方法。粗糙集用来执行一致性 检测，概念形成和近似。通过计算下近似和上近似，训练数据被分为确定训练 数据和可能训练数据。然后，遗传算法从数据集中发现最佳规则，适应度函数 定义为所提取规则的分类质量。最后，选择规则所覆盖的具有最高指标的特征 或属性。粗糙集系统r s e s 中所实现的基于遗传算法和特定数据结构的约简产生 算法是非常有效的。 爬山法在处理具有较少噪声和小数量的特征时会很有效，然而不能保证最 优。随机方法能提供一个更稳健的方案，但是以增加计算量为代价。对于要求 最优或最小特征子集的系统( 例如由于特征评估代价的昂贵) ，就需要使用随机 特征选择。 i 蚁群算法是一种新型的优化算法，其本质上是一个复杂的智能系统，比较 。有代表性的研究有等d o r i g o 人使用蚁群算法解决t s r 问题，然后进_ 步把它们 - 勺方法扩展到了解决不均衡的r s r 、q a p 和j s p 问题中呦1 ；为了克服在a n t - q 中 3 第一章绪论 可能出现的停滞现象，s t u t z l e 和h o o t s 提出了m a x m i n 蚁群算法，称作删a s ， 它对基本蚂蚁算法( a s ) 进行了三点改进：( 1 ) 为了更加充分地进行寻优，各路 径信息素初值设为最大值rm a x ；( 2 ) 一次循环后只有最短路径的蚂蚁才进行信 息素增加；( 3 ) 为了避免算法过早收敛到非全局最优解，将各路经的信息素浓 度限制在( 【m i n ，tm a x ) 之间；g a m b a r d e l l a 和d o r i g o 等提出了一种被称作 h a s q a p 的蚁群算法，这个算法主要的不同之处是它直接修改解决方案：b o t e e 和b o n a b e a u 对参数m ，q ，8 ，p 的选择进行了深入的研究，用遗传算法求得这 些参数最优组合；吴庆洪晗u 等人提出了具有变异特征的蚁群算法，在基本蚁群 算法中引入变异机制，充分利用了2 一交换法简洁高效的特点；陈峻等人提出了 提出一种基于分布均匀度的自适应蚁群算法该算法根据优化过程中解的分布均 匀度，自适应地调整路径选择概率的确定策略和信息量更新策略；段海滨在蚁 群算法原理及其应用一书中系统研究蚁群算法的机理原理、理论分析及其在 离散域和连续域的若干改进测量的基础上，阐述了蚁群算法在多个优化领域的 典型应用，探讨了蚁群算法的硬件实现，研究了蚁群算法与其他仿生优化算法 的融合策略，展望了蚁群算法的发展方向。目前，蚁群算法已经在众多领域得 到了有效应用旧争砑1 。 1 3 论文的主要研究内容 本文系统综述了粗糙集理论和蚁群优化方法的一本概念、基本原理和研究 新进展。在分析比较基于粗糙集属性重要度的特征选择算法和基于蚁群优化方 法的特征选择算法之后，对基于蚁群优化方法和粗糙集方法两者结合的特征选 择算法进行了研究。着重分析了粗糙集属性依赖度和重要度对蚁群算法转移规 则的影响，特征子集长度和分类效果对信息素更新策略控制和特征提取效果等 问题，并通过实验数据进行测试，证明了算法的有效性和可行性。本文将要研 究的主要工作包括以下几个方面： 1 进一步深入理解粗糙集理论和蚁群优化算法的基本概念和基本原理和目 前的研究新进展。 2 对目前的特征选择算法的进行研究与分析。着重对基于粗糙集属性重要 度的特征选择算法( 贪婪法) 和基于蚁群优化方法的特征选择算法进行深入研 究。 4 第一章绪论 3 在分析基于粗糙集的特征选择方法和基于蚁群优化方法的特征选择算法 所具有的优势和存在不足的基础上，本文提出了一种基于粗糙集蚁群优化方法 的特征选择算法。所提出的算法通过引入粗糙集相对核属性作为特征选择的起 点，以便提高算法的准确性；在转移规则和信息素更新策略中，引入了粗糙集 属性依赖度和属性重要度，用于指导蚂蚁的搜索过程，以便提高算法的性能； 此外，将粗糙集理论的分类精度和特征子集长度两个参数应用于评价函数中， 以衡量特征子集的优劣。 4 对所提出的特征选择算法在给定的数据集上进行测试，证明算法的性能。 通过比较分析，验证该算法的可行性和合理性。 1 4 论文的组织与结构 第一章是绪论。主要介绍了本文的研究背景及意义，特征选择方法的研究 秽i 。 现状和本文研究的主要内容。 第二章是粗糙集理论和蚁群优化算法的相关知识。在本章中详细介绍了粗 糙集理论的基本概念，包括信息表达系统，上近似和下近似，属性约简与核， 属性依赖度和重要度等概念；此外，对蚁群算法的理论知识进行了总结概述。 第三章是特征选择算法的研究与分析。本章对特征选择的一般算法进行了 比较，着重对基于粗糙集属性重要度的特征选择算法( 贪婪法) 和基于蚁群优化 方法的特征选择算法进行了深入研究，通过分析各种算法的优劣，本文提出了 一种将粗糙集和蚁群优化算法各自优势相结合的特征选择算法。 第四章是基于粗糙集和蚁群优化算法的特征选择算法。本章对粗糙集一蚁群 优化方法的特征选择算法进行了详细的介绍和分析。包括算法的基本思想，算 法具体步骤设计和实现方法。为了减少搜索的盲目性，增加结果的准确性，本 为将相对核作为特征选择的起点。另外，利用粗糙集的属性依赖度和属性重要 度方法来构建蚁群遍历的转移规则，增强了算法的性能；利用特征子集长度和 分类性能结合控制信息素的更新策略，不仅发挥了蚁群算法的正反馈优势，而 且可以使特征选择的任务朝着最优的方向进行。最后通过实验分析证明了算法 的可行性。 第五章是总结与展望。包括对本文工作的总结和下一步工作的方向， 5 第二章粗糙集理论和蚁群算法的相关知识 第2 章粗糙集理论和蚁群算法的相关知识 粗糙集理论( r o u g hs e tt h e o r y ) 是由波兰学者z p a w l a r k 教授提出的一 种处理不完备、不确定、不确定和模糊问题的数学工具h 1 。粗糙集的主要思想是 在保持分类能力不变的前提下，通过知识约简，导出问题的决策和分类规则。 其优势在于不需要任何先验知识，就可以发现信息系统中潜在的知识，揭示隐 含的规律。经过短短2 0 余年的发展，粗糙集理论在理论和应用领域都取得了显 著的研究成果。目前，粗糙集理论已经成功应用于决策分析、医疗诊断、信息 检索、机器学习和模式识别等方面。 。 蚁群优化算法( a c o ) 是一种近年来才发展起来的新颖的仿生型的智能优化 算法，具有正反馈、分布计算和启发性搜索等特点。蚁群优化算法的思想米源 于我们真实世界中的蚂蚁群体觅食行为的智能特性。在现实生活中，许多蚂蚁 所构成的蚂蚁群体在经过一段时间的调整以后，通过个体之间的相互配合与协 作，最后能够使整个蚁群沿着某条最短的路径将食物搬回到蚁巢。作为计算智 能和群智能的重要分支之一，蚁群优化算法的研究方兴未艾，备受瞩目。 本章将介绍粗糙集理论和蚁群算法的相关知识，为后文研究粗糙集和蚁群 优化方法相结合的特征选择方法提供理论基础。 2 1 粗糙集的基本理论舢7 1 2 1 1 信息表知识表达系统 智能系统的关键之一就是知识表达。 形式转化为另一种目标表达形式的过程， 有规律的信息。 所谓知识获取是指将知识从一种表达 从而从原始海量的信息中提取有价值、 知识表达系统又称为信息系统，是用关系表的形式表达的。关系表的行对 应要研究的对象，列对应对象的属性，对象的信息通过指定对象的各属性值来 表达。 形式上，p 1 元组j = ( u ，4 ；v ，f ) 是一个知识表达系统，其中u ：对象的非空 6 第二章粗糙集理论和蚁群算法的相关知识 有限集合，称为论域；a ：属性的非空有限集合；矿= uv a ，y a 是属性a 的值 域；正u x 彳jv 是一个信息函数，它为每个对象的每个属性赋予一个信息值， 即v a 彳，x u ，f ( x a ) v a ；通常a = c u d ，c 为条件属性的集合，d 为决策属性 的集合。通常也用s = ( u ，彳) 来代替s = ( u ，a ，v ，) 。 粗糙集理论认为知识与分类是密不可分的，知识是基于对研究对象的一种 分类的能力，分类的过程就是将相差不大的对象分为一类，他们的关系就是不 可分辨关系，也称为等价关系。等价关系定义如下：令s = ( u ，4 ，圪) 是一个信 息系统，令p 彳，定义p的不可区分关系i n d ( p ) 为 i n d ( p ) = ( x ，力u x ulv a p ，f ( x ，口) = f ( y ，口) 。如果( 五y ) i n d ( p ) ，则称x 和 y 是p 不可区分的。用符号【x 】p 表示x u 的p 等价类。 由此可见，在信息系统中，一个属性对应一个等价关系，一个表可以看做 是定义的一簇等价关系，即知识库。 ， 警c 三一0 ，、 2 1 2 上近似、下近似和粗糙集 一- 粗糙集用上近似和下近似两个精确集来表示不精确，不确定的概念。给鼎瞎j r 定知识库k = ，r ) ，对于每个子集x u 和一个等价关系r i n d ( k ) ，定义两 个子集： 。+ ，： b _ s _ x = u y u 尺lyex ) ， 1 一 r x = u 】，u rfynx o 分别称为x 的r 下近似集和r 的上近似集。集合b n r ( x ) = r x 一丛称为x 的r 边界域。 显然，丛是由那些根据知识r 判断肯定属于x 的u 中的元素组成的集 合；r x 是由那些根据知识r 判断可能属于x 的u 中的元素组成的集合；b n r ( x ) 是那些根据知识r 既不能判断肯定属于x 又不能判断肯定属于 - - x 的u 中元 素组成的集合。 为更好描述集合的精确性，得出由等价关系r 定义的集合x 的近似精度 为( x ) = c a r d ( r x ) c a r d ( r x ) ，ixi 表示集合x 的基数。显然，0 ( x ) 1 。 x 的r 粗糙度定义如下风( x ) = 1 一( x ) 。x 的r 粗糙度表示集合x 的知识 的不完全程度。粗糙集上近似、下近似和边界之间的关系如图1 1 所示。 7 第二章粗糙集理论和蚁群算法的相关知识 图2 1 粗糙集上近似、下近似和边界之间的关系 2 1 3 属性约简与核 令r 为一族等价关系，r e r ， 必要的；否则称r 为r 中必要的。 如果i n d ( r ) = i n d ( r 一 r ) ) ，则稍；r 为r 不 如果每个r er 都为r 中必要的，则称r 为独立的；否则称r 为依赖的。设q p 如果q 是独立的，且i n d ( q ) = i n d ( p ) ，则称q 为p 的一个约简，用r e d ( p ) 来表示。p 中所有必要关系组成的集 合成为p 的核，即所有约简的交集。c o r e ( p ) = n 陀d ( p ) 。由此可见，核是所有 约简计算的基础，也可以说成是在约简时它是不能消去的知识特征的集合。 在应用中，相对约简和相对核体现了一个分类相对于另一个分类的关系的 重要性。令p 和q 为u 中的等价关系，q 的p 正域记为p o s v ( q ) ，即 p o s p ( q ) = u 丛，p o s e ( q ) 表示u 中所有根据分类u p 的信息可以准确地划分 到关系q 前等价类中去的对象的集合。当r e p ，且p o s p ( q ) = p o s ( p - r 1 ) ( q ) 时， 称r 为p 中q 不必要的，否则r 为p 中q 必要的。若r ep 都为p 中q 必要的， 则p 相对于q 独立。 2 1 4 属性依赖度和属性重要度 一 如果知识q 是出知识p 导。i 的，则知识q 依赖于氮：识、p 在知识库中， 8 第二章粗糙集理论和蚁群算法的相关知识 我们认为知识q 是多余的。令k 产( u ，r ) 为一个知识库，且p , q r ，若 i n a ( p ) i n d ( q ) ，则称知识q 依赖于知识p ，也就是说知识q 可以由知识p 完全推导出来，记为p o 。但在有些情况下，知识的依赖性可能是部分的， 这意味着知识q 仅有部分是由知识p 导出的，我们用知识依赖性的量度k 来 定义，k = 7 p ( q ) = p o s p ( q ) i iul ，我们称知识q 是k ( 0 后1 ) 度依赖于知识 p 的，记作pj 。o 。k = l 时，知识q 完全依赖于知识p ；k - - o 时，知识q 完 全独立于p ；o k l 时，称知识q 粗糙( 部分) 依赖于p 。我们通过k 来确定 属性之间的依赖关系。 在决策表t = ( u ，a cud ) ，令c 和d 分别为条件属性集和决策属性集， 属性子集c c 关于d 的重要性定义为 q _ d ( c ) = ( d ) 一始f ( d ) 例如，当c7 = a 时，属性a e c 关于d 的重要性为 o r c d ( a ) = 7 c ( d ) 一y c a ( d ) 2 2 蚁群算法的理论基础 蚁群算法( a n tc o l o n ya l g o r i t h m ) 是一种模拟进化算法【2 8 1 。蚁群算法来源于， 现实中的蚂蚁觅食行为。在2 0 世纪9 0 年代中期，意大利学者多里戈、马尼佐 和科洛龙等人从生物进化和仿生学的角度出发，研究蚂蚁寻找路径的自然行为， 提出了蚁群算法。目前该方法已经成功应用于t s p 问题、二次分配问题和作业 调度等问题中，并取得了良好的效果。尤其在求解复杂的优化问题方面，蚁群 算法已经成为一种很有发展前景的计算智能方法。 2 2 1 蚁群算法的基本原理 在现实生活中，单个蚂蚁的行为及其简单，但是由单个蚂蚁组成的蚁群却 表现出及其复杂的行为，每只蚂蚁在寻找食物的过程中，总能寻找到一条从巢 穴到食物源的最短路径。仿生学家经过大量的观察研究发现，蚂蚁之间进行信 息传递是通过一种称为外激素( p h e r o m o n e ) 的物质。单个蚂蚁在运动的过程中， 会在它所经过的路径上残留下这种物质，后面的蚂蚁在运毒 j 的过程中能够感知 9 破；o n _ ：2 笔，二。 第二章粗糙集理论和蚁群算法的相关知识 这种物质，并以此控制自己的运动方向。因此，蚁群的集体行为表现出一种智 能的信息正反馈现象：某一路径上被蚂蚁选择的次数越多，那么它被后来的蚂 蚁选中的概率也越大。 下面以多里戈的实验为例来具体说明蚁群系统的基本原理。如图2 1 所示， 假设a 点是蚂蚁的巢穴，e 点是食物源。由于存在障碍物h c ，蚂蚁只能向左或 者向右绕经h 或c 由a 点到达e 点，或者由e 点到达a 点。蚂蚁选择向左或 者向右路径的概率由前面已经经过的蚂蚁留下的信息素决定，如果障碍物h c 左 边信息素的浓度大于右边信息素浓度，那么向左的路径被蚂蚁选中的概率就会 更大一些。但是第一只到达b 点或者d 点的蚂蚁，不受信息素浓度的影响，它 选择左右两边路径的概率是一样的。 在图2 2 中，a 点是蚂蚁的巢穴，e 点是食物源，h c 为障碍物。各点之间 的距离如图所示。设单位时问内分别有3 0 只蚂蚁从a 到达b 或者从e 到达d ， 设单个蚂蚁经过后在路径上残留的信息素浓度为l 。为简单起见，设信息素停留 的时间为l 。在初始时刻，b h ，b c ，d h ，d c 上信息素的浓度为0 ，所以位于b 点 和d 点的蚂蚁可以随机地选择路径。经过一个单位时间以后，在路径b c d 上的 信息素浓度是路径b h d 上的信息素浓度的两倍。在t = l 时刻，将有2 0 只蚂蚁选 择b d c 路径，有l o 只蚂蚁选择b d h 路径。随着时间的推移，蚂蚁选择路径 b c d 的概率越来越大，并最终找到从巢穴到食物源的最短路径。由上述内容可 以看出，蚁群的集体行为是一个智能的行为，单个蚂蚁之间的信息素传递是一 个正反馈的过程。 h c a ) 路锈零愆嘲 ( a ) f i g u r eo fr o u t e ( b ) t 口孵刻 ( b ) t = t a 图2 2 蚁群系统示意图 2 2 2 蚁群算法的基本模型及其实现 1 0 ( c ) t l 孵刻 ( c ) i t - - l l ；1 第二章粗糙集理论和蚁群算法的相关知识 蚁群算法的模型取决于求解问题的性质。当求解问题的性质不同时，蚁群算 法的模型也有所不同。蚁群算法的基本思想就是：含有一定数量蚂蚁的蚁群， 通过路径的搜索构造可行解。每只蚂蚁从初始节点开始出发，通过概率公式选 择下一个节点，最后得到的路径就是一个可行解。每只蚂蚁通过评价测度评价 解的好坏，并且使得所经过路径上的信息素加强或者减弱，以便下一次迭代搜 索到全局最优解。 下面以求解n 个城市t s p 问题为例来说明蚁群系统模型【2 9 1 。t s p 问题的实 质就是在n 个节点的完全图上，寻找一条最短路径，是一个n p 难问题。为了 模拟现实中蚂蚁的行为，引入下列符号： m 表示蚁群中蚂蚁的数量； 办( f ，= i 2 ，咒) 表示城市i 和城市j 之间的距离；。 岛( ，) 表示t 时刻位于城市i 中的蚂蚁个数，聊= b i ( t ) ； ( f ) 表示t 时刻在i j 连线上残留的信息素的浓度：1 在初始时刻，设( o ) = c ( c 为常数) ，各个路径上的信息素的浓度相等。 蚂蚁k ( k - - 1 ，2 ，m ) 在运动的过程中，根据各条路径上的信息素的浓度决定转 移方向。p ；( f ) 表示在t 时刻蚂蚁由位置i 转移到位置j 的概率： 笔 p ；( f ) = 乓霉j a l i d 。 7 7 黝 严” 0 ， o t h e r w i s e 其中，a l l o w e d k = 0 , 1 ，n - 1 表示蚂蚁k 下一步允许选择的城市。随着时间 的推移，残留的信息素浓度开始挥发，参数( 1 一p ) 表示信息素挥发系数，经过n 个时刻，蚁群完成一次迭代。各路径上的信息素根据下式进行更新： r i j ( t + n ) = p 乃( f ) + 乃 ( 2 2 ) = 砧 ( 2 3 ) 砧表示第k 只蚂蚁在经过路径i j 上的信息素浓度，气表示蚁群一次迭代 后在路径i j 上的信息素浓度： 砖：詈，若蚂蚁碰过路径 j ( 2 4 ) 【0 ，其他。? ，。，? p 。4 一。、 ， ：们 ， 虹， ， 碜 ； 第二章粗糙集理论和蚁群算法的相关知识 其中，q 为常数，l 。表示第k 只蚂蚁在一次迭代中所选择的路径的长度。初始 时刻，( o ) = c ( e o n s t ) ，a r o = 0 ，其中i j = o ，l ，n - 1 。口和分别表示信息素 浓度和启发信息在蚂蚁路径选择中所起的不同作用。不同的问题中，由城市i 转移到城市j 的期望值纪，是不同的，可以根据某种具体启发式算法具体确定。 而终止条件可以根据最大迭代次数和最优解收敛到同一路径来确定。 从上面对蚁群算法的说明论述中，可以得到基本蚁