（计算机软件与理论专业论文）基于模糊熵的特征选择方法的研究与实现.pdf

独创性声明 j i i i i ii i i iii i i i ii lli i i iii ii 18 0 5 9 01 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写 过的研究成果，也不包含为获得东北师范大学或其他教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名： 鸯想 学位论文版权使用授权书 ， 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定，即：东北师 范大学有权保留并向国家有关部门或机构送交学位论文的复印件和磁盘，允许论文被查阅 和借阅。本人授权东北师范大学可以将学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或其它复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：查垫指导教师签名： 日 期：碰z 应：厶! v o 日期： 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： 目录 摘要i a b s t r a c t i ：【 目录：i i i 第一章引言1 1 1 研究意义，目的及研究背景心1 。1 1 2 研究内容与主要工作3 第二章特征选择概述4 2 1 特征选择的研究现状4 2 2 特征选择的基本概念及一般过程4 2 3 特征选择算法的选择方法7 2 4 特征选择评价标准8 第三章蚁群优化算法与模糊熵理论1 0 3 1 蚁群优化算法的基本理论，1 0 3 1 1 蚁群算法的基本原理1 0 3 1 2 基本蚁群算法的特点1 0 3 1 3 蚁群算法的实现步骤和程序结构流程1 1 3 1 4 参数对蚁群算法性能的影响n 1 4 3 2 模糊理论基础与应用1 4 3 2 1 模糊理论的提出1 4 3 2 2 模糊集基础1 5 3 2 3 模糊熵1 6 第四章基于模糊熵的蚁群算法研究j 1 8 4 1 利用模糊熵对特征子集进行评价1 8 4 2 将模糊熵的蚁群算法应用于特征选择1 9 4 2 1 基于模糊熵的蚁群算法的描述1 9 4 2 2 基于模糊熵蚁群算法实验描述2 3 第五章结束语2 6 5 1 本文工作小结2 6 5 2 未来工作展望一2 6 参考文献2 7 致谢2 9 在学期间公开发表论文及著作情况3 0 摘要 特征选择在模式分类过程中发挥着重要作用，选择的特征正确与否直接关系到分类 结果的正确率，因此特征选择方法直接影响着系统的性能和质量。但是目前的多数特征 选择方法都存在容易陷入局部最优的问题，为了能够快速准确的找到最小特征子集从而 更好的实现分类，本文对特征选择方法进行了大胆的探索和尝试。 蚁群优化算法作为一种群集智能算法，具有群集智能算法能够解决大多数全局优化 算法的优点，蚁群优化算法是一种求解组合优化问题的新型通用启发式方法，蚁群优化 算法具有正反馈、分布式计算和自组织性的特点，它是一种贪婪启发式搜索方法。而在 实际应用中我们发现蚁群优化算法搜索时间较长，所以选择正确有效的信息素和约束条 件变得十分重要。蚁群优化算法可以分为两个基本阶段：适应阶段和协作阶段。在适应 阶段，各个候选解根据所积累的信息不断地调整自身结构。而在协作阶段，各个候选解 之间不断进行信息交流，从而产生性能更好的解。 熵描述了一个概率分布的不确定性程度。将熵概念移植到模糊集理论，可以得到模 糊熵。模糊熵描述了一个模糊集的模糊性程度。一个模糊集合越模糊，它的模糊熵就越 大，反之亦然。模糊熵描述的是概率分布的不确定程度，一个集合的不确定性越大，它 的分布越均匀，信息量也就越大。在本文中，模糊熵作为信息素应用于蚁群优化算法中， 能够帮助蚁群快速准确的找到重要特征子集。首先将整个数据集作为蚁群优化算法的输 入，再随机选择一组特征作为初始特征子集，然后让蚁群按照规则运动，改变各个特征 的信息素，最后获得目标特征子集。 。 关键词：模式分类；模糊熵；特征选择；蚁群算法 a b s t r a c t f e a t u r es e l e c t i o np r o c e s sp l a y sa ni m p o r t a n tr o l ei np a t t e r nc l a s s i f i c a t i o n , w h e t h e ro rn o t t h ec o r r e c tc h o i c eo ff e a t u r e sd i r e c t l yr e l a t e dt ot h ec l a s s i f i c a t i o na c c u r a c yr a t e ，s of e a t u r e s e l e c t i o nm e t h o di sad i r e c ti m p a c to ns y s t e mp e r f o r m a n c ea n dq u a l i t y h o w e v e r , t h ec u r r e n t e x i s t e n c eo ft h em a j o r i t yo ff e a t u r es e l e c t i o nm e t h o d sa r ee a s i l y t r a p p e di n t o l o c a l o p t i m i z a t i o np r o b l e m s ，i no r d e rt ob ea b l et oq u i c k l ya n da c c u r a t e l yf i n dt h es m a l l e s tf e a t u r e s u b s e ti no r d e rt ob e t t e ra c h i e v et h ep u r p o s eo fc l a s s i f i c a t i o n ，f e a t u r es e l e c t i o nm e t h o d si s e x p l o r e da n d t r i e db o l di nt h i sp a p e r a 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 ，a sas w a r mi n t e l l i g e n c ea l g o r i t h m ，w i t has w a r m i n t e l l i g e n c ea l g o r i t h mc a nr e s o l v em o s to ft h ea d v a n t a g e so fg l o b a lo p t i m i z a t i o na l g o r i t h m s a 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 mi sac o m b i n a t o r i a lo p t i m i z a t i o np r o b l e ms o l v i n gt h en e w c o m m o nh e u r i s t i cm e t h o d ，a 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 诵mp o s i t i v ef e e d b a c k ， d i s t r i b u t e dc o m p u t i n ga n ds e l f - o r g a n i z a t i o n a lc h a r a c t e r i s t i c s ；i ti sag r e e d yh e u r i s t i cs e a r c h m e t h o d i np r a c t i c a la p p l i c a t i o n s ，w ef o u n dt h a ta n tc o l o n yo p t i m i z a t i o na l g o n t h mf o rt h e s h o r t c o m i n g so fal o n g e rs e a r c ht i m e ，s oc h o o s et h ec o r r e c ta n de f f e c t i v ep h e r o m o n ea n d c o n s t r a i n t sb e c o m ei m p o r t a n t a 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 mc a nb ed i v i d e di n t ot w o b a s i cs t a g e s ：s t a g ea d a p t a t i o ns t a g ea n dc o l l a b o r a t i o n i nt h ea d a p t a t i o np h a s e ，a l lc a n d i d a t e s o l u t i o n sa c c o r d i n gt ot h ei n f o r m a t i o na c c u m u l a t e db yc o n s t a n t l ya d j u s t i n gi t ss t r u c t u r e i n t h ec o l l a b o r a t i o np h a s e ，e a c hc a n d i d a t es o l u t i o ni nt h ec o n t i n u o u se x c h a n g eo fi n f o r m a t i o n , r e s u l t i n gi nb e t t e rp e r f o r m a n c eo ft h es o l u t i o n e n t r o p yo fap r o b a b i l i t yd i s t r i b u t i o nd e s c r i b i n gt h ed e g r e eo fu n c e r t a i n t y t r a n s p l a n t e dt o t h ee n t r o p yc o n c e p to ff u z z ys e t st h e o r y , c a nb ef u z z ye n t r o p y f u z z ye n t r o p yd e s c r i b e sa d e g r e eo fa m b i g u i t yo ff u z z ys e t s af u z z ys e to ft h ev a g u e r , a n di t sf u z z ye n t r o p y , t h eg r e a t e r a n d v i c ev e r s a f u z z ye n t r o p yd e s c r i b e st h e p r o b a b i l i t yd i s t r i b u t i o no ft h ed e g r e eo f u n c e r t a i n t y , t h eg r e a t e rt h eu n c e r t a i n t yo fac o l l e c t i o n , i t sd i s t r i b u t i o nm o r eu n i f o r m ，t h e g r e a t e rt h ea m o u n to fi n f o r m a t i o n i nt h i sa r t i c l e ，f u z z ye n t r o p ya sap h e r o m o n eu s e di na n t c 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 ea n tc o l o n yq u i c k l ya n da c c u r a t e l yt oh e l pf i n di m p o r t a n t f e a t u r es u b s e t f i r s t ，t h ee n t i r ed a t as e ta sa na 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 mf o rt h ei n p u t ， a n dt h e nr a n d o m l ys e l e c tas e to ff e a t u r e sa st h ei n i t i a lf e a t u r es u b s e t ，a n dt h e nl e tt h ea n t c o l o n ym o v e m e n ti na c c o r d a n c e 、析mt h er u l e st oc h a n g et h ev a r i o u sc h a r a c t e r i s t i c so f p h e r o m o n e s ，f i n a l l yw o nt h eg o a lo ff e a t u r es u b s e t k e yw o r d s ：p a t t e r nc l a s s i f i c a t i o n ；f u z z ye n t r o p y ；f e a t u r es e l e c t i o n ；a n tc o l o n ya l g o r i t h m ； 东北师范大学硕士学位论文 第一章引言 1 1 研究意义，目的及研究背景晗妇 近年来信息量呈现爆炸式增长，如何有效合理地组织和管理海量信息成为一个难 题，人们越来越重视对信息的分类处理。目前，模式分类已经被广泛应用于多个领域， 包括自然语言处理、搜索引擎、信息检索、信息过滤等。 模式识别是人类的一项基本智能，在日常生活中，人们经常在进行“模式识别 。 随着2 0 世纪4 0 年代计算机的出现以及5 0 年代人工智能的兴起，人们当然也希望能用 计算机来代替或扩展人类的部分脑力劳动。( 计算机) 模式识别在2 0 世纪6 0 年代初迅速 发展并成为一门新学科。 模式识别是指对表征事物或现象的各种形式的( 数值的、文字的和逻辑关系的) 信息 进行处理和分析，以对事物或现象进行描述、辨认、分类和解释的过程，是信息科学和人 工智能的重要组成部分。模式识别又常称作模式分类，从处理问题的性质和解决问题的 方法等角度，模式识别分为有监督的分类和无监督的分类两种。二者的主要差别在于， 各实验样本所属的类别是否预先已知。一般说来，有监督的分类往往需要提供大量已知 类别的样本，但在实际问题中，这是存在一定困难的，因此研究无监督的分类就变得十兑 分有必要了。 统计模式识别系统一般由数据获取、预处理、特征提取和选择、分类决策等四部分 组成，如下图所示i l j ： 图1 1 统计模式识别系统的组成 1 、获取信息：是指通过测量、取样、量化得到适合计算机处理的用矩阵或向量表 示的二维图像或一维波形。 2 、预处理：是指去除噪声、加强有用信息、对信号的畸变进行复原。 3 、特征提取和选择：特征提取通常是对原始数据进行变换，将高维的原始数据变 东北师范大学硕士学位论文 换为能反映类别差别的低维输入特征。这种变换的依据是按照对象的可分性来选择的， 也就是说，经过这种变换后得到的特征可以进行分类。特征选择是对输入特征进一步降 维，即在提取的输入特征空间中选择对分类最有效的少数几个特征，以提高分类器的性 能。 4 、分类决策：分类决策就是在特征空间中用统计的方法将被识别对象归为某一类。 基本做法是在样本训练集基础上确定某个判决规则，按这种判决规则，对被识别对象进 行分类所造成的错误概率最小或引起的损失最小。 而特征选择是进行模式分类时的重要步骤，科学有效的特征选择方法不仅可以提高 模式分类系统的运行速度，提高分类的准确度，而且能够大幅度降低处理开销和分类的 复杂度，改善模式分类算法的效果。因此，随着模式分类方法的广泛应用，特征选择方 法也具有了重要的研究价值和实际意义。 特征选择是指从输入特征集合中选择出一个特征子集，并且这个特征子集能够使某 种评估标准达到最优，根据不同的应用需要，评估标准也不尽相同。自从上个世纪六十 年代开始，就有学者对特征选择方法进行研究了，特征选择属于统计学领域，它的重要 意义可以简单概括如下：首先，优秀的特征选择方法能够降低模式分类算法的计算复杂 度，提高分类准确度。目前特征选择方法都会受到不相关或者冗余特征的负面影响，甚 至于有些算法所需训练样本的数目随不相关特征的增多成指数性增长。决策树对逻辑与 概念的样本复杂度随不相关特征线性增加，但对异或概念的样本复杂度却是呈现指数增 长。其次，随着大规模数据处理问题的不断涌现和数据挖掘技术的不断发展，迫切需要 特征选择方法对高维数据进行降维，而目前已有的特征选择方法不能适用于所有的数据 降维问题。 在上个世纪六十年代，人们开始研究统计学和信号处理中的特征选择问题，不过当 时涉及到的特征个数比较少，而且假设特征之间是独立的。而现有的特征选择算法都是 各自针对于某一类型的数据或数据集，大量的线性维度算法不断出现，这些方法都是假 设每个特征维度反映一个潜在的因素，提供一种对数据的新的理解。如果所有特征的权 重都大于零时，线性维度算法不能够有效减少特征的个数。 近十年来，特征选择方法的研究呈现出了多样化和综合性的趋势。各种新搜索算法 和评估标准都应用到特征选择方法中。如粗糙集算法，神经网络剪枝法，支持向量机的 评估标准，马尔可夫算法等。不仅开展了监督式学习的特征选择方法的研究，还开展了 非监督式学习的特征选择方法的研究。另外还出现了特征选择方法融合性的研究。 我国的特征选择的研究主要从上个世纪九十年代开始的，其中有代表意义的是陈彬 网等人于1 9 9 7 年在计算机学报上发表的“最优特征子集选择问题”，该文证明了最优 特征子集的选择是一个n p - h a r d 问题，并给出了一些启发式算法。国内外的各大研究机 构也开展了相关研究。 大多数的特征选择方法都是针对经典集合的，而没有考虑到特征的模糊性，从而不 能够完全刻画出特征的自然属性。因此，急需从特征的模糊集角度对它进行分析。而 h a h n m i n gl e e 等提出了特征集的模糊熵评价方法，这种方法能够比较快速而且准确的 2 东北师范大学硕士学位论文 达到分类的目的。但是，这种方法存在一些问题：首先，文中提出的模糊熵评价方法仅 仅适用于计算数字特征。其次，对该方法进行模拟时发现，如果人工生成一些无用特征， 它们有一部分最终会作为较好的特征而被分类方法采用。本课题力求从特征的模糊性角 度对其进行评价，努力克服已提出方法的不足，从而更好的实现分类。 1 2 研究内容与主要工作 我们在选题时发现，很多研究学者以各种模式分类方法或者模式识别方法为研究课 题，而其中一个重要的步骤就是进行特征选择和特征提取，近年来数据规模的不断增大 特征维数的不断增加对特征选择方法的研究提出了新的挑战，基于以上的原因，我们选 择了研究特征选择方法以解决模式分类问题。经过实验仿真和仔细对比分析我们发现， 基于信息熵的特征选择方法在处理连续数据时通常能够收到很好的效果，但是在处理一 些数据集时确不能得到理想的结果。而目前大多数的特征选择方法都是针对经典集合 的，并没有考虑特征还具有一定的模糊性，所以无法准确的刻画特征的自然属性。因此， 在本文中引入了模糊熵的概念，将模糊熵与蚁群优化算法相结合，尝试了一种新的特征 选择方法研究。因为蚁群优化算法具有极强的鲁棒性，它利用信息的正反馈和分布式计 算和系统的蚂蚁的自组织能力进行并行计算，能够较好的解决组合优化问题。 3 东北师范大学硕士学位论文 2 1 特征选择的研究现状 第二章特征选择概述 机器学习是人工智能的一个子领域，它主要关注于开发那些让计算机可以自主“学 习 的技术。也就是说，机器学习是一种用于创建数据集分析程序的方法。由于机器学 习和统计学都是研究数据分析问题，所以这二者之间存在着重要的关系。机器学习主要 关注的是计算实现的算法复杂度，由于很多推论问题属于无程序可寻难度，所以部分机 器学习的研究是开发容易处理的近似算法。描述数据的属性就是特征，也可以称为变量、 属性、特性等等。在本文中，我们会用模式分类问题来说明所采用的特征选择方法，对 特征选择方法进行评价。 对数据集的衡量包括特征的数目和数据的数目两个方面，如果特征的数目过于庞 ，可能会引发维数灾难，因此特征数目应该被控制在一定的范围内，避免出现维数过 的情况。一般来讲，模式分类时需要估计许多未知的参数，而参数个数与特征数目可 存在某种关系。因此假如特征数目过多，就需要输入大量的样本数据来精确估计未知 参数。如果输入的样本数据数目较少但是特征数目比较大，那么很可能会导致估计的 数不准确，从而影响分类器的性能。由于科技水平的发展，信息获取技术的不断提高， 别是互联网的应用，能够获得的信息数据量越来越大，特征维数越来越高，不相关或 冗余特征也相应增多，因此数据降维问题已经引起大家的关注，出现很多数据降维方 的研究。 数据降维常用的两类方法是特征选择和特征提取。特征选择是指在模式识别时按照 一原则从原始的特征集合中选择出最优的特征子集。主要目标是能够选择出最小的特 子集，使模式分类时能够达到更好的效果。经过特征选择，那些与任务不相关或者冗 的特征会被剔除，伴随着特征维数的降低，有用的信息被保留下来，根据简化后的数 集合我们可以得到更加准确的模型，提高系统的精度、速度和可理解性【2 j 。特征提取 指将原有的特征空间进行某种形式的变换得到新的特征空间。特征提取方法的特点是 以将高维的大数量的数据用低维的小数量的特征来表示，但是得到的新特征空间通常 难理解，可扩展性差。同时工作量并没有显著减少，主要原因是新特征空间通常是由 部原始特征空间变换得到的。 2 特征选择的基本概念及一般过程 特征选择并没有一个统一的定义，根据具体问题不同，特征选择有不同的定义。以 是d a s h 和l i u 总结的不同定义3 1 ： 1 在所有的n 个特征所组成的特征集合中选取一个由m 个特征组成的子集， 4 东北师范大学硕士学位论文 其中m 事先给定，并且m 岛( 磅+ l l ( t ) ( 3 2 ) 其中，她；( t ) = 鼯i k 对于k 圆的计算方法，m a r c 。d 。r i g o 给出亍三种计算方法【1 3 】： 在a n t - c y c l es y s t e m 模型中： i坠 k = k 若蚂蚁l 【在本次循环经过边萄 h否则 ( 3 3 ) 在a n t d e n s i t ys y s t e m 模型中： r旦 蝇j k = d i ) 若蚂蚁k 在本次循环经过边萄 【o ，否则 在a n t q u a n t i t ys y s t e m 模型中： k = i o ， q 否则若蚂蚁k 在本次循环经过边i ； ( 3 5 ) 在上面的三个公式中，q 是定义的一个正常数，表示蚂蚁循环一周或者一个过程在 经过的路径上所释放的信息素总量，k 表示第k 只蚂蚁在本次循环中所经过的路径的长 度。 旅行商问题的蚁群算法流程结构可以用下图表示： 东j l i j i l i 范大学硕士学位论文 图卜1 蚁群算法的流程结构图。 ， 东北师范大学硕士学位论文 3 1 4 参数对蚁群算法性能的影响1 1 1 i 蚁群算法研究的一个关键问题是：既要使算法的搜索空间尽量大，以寻找可能存在 最优解的区域，也要充分利用蚂蚁群体内当前所有的有效信息，使得算法搜索的重点放 在那些很有可能具有较高适应值的个体所在的区域内，从而以较大的概率收敛到全局最 优解。对蚁群算法性能影响的参数主要有： 信息素残留因子l p 、信息启发式因子a 、期望启发式因子8 、信息素强度q 、蚂 蚁数目m 。这些参数的选取方法和选择原则直接影响到蚁群算法的全局收敛性和求解效 率。 ( 1 ) 信息素残留因子l p 对蚁群算法性能的影响。当1 一p 过大时，算法的收敛速 度慢，随机性能和全局搜索能力强；而当l p 过小时，算法的随机性能和全局搜索能力 低，容易陷入局部极值。 ( 2 ) 信息启发式因子饶对蚁群算法性能的影响。越大，蚂蚁选择以前走过路径的 可能性就越大，搜索的随机性减弱；而a 过小，则易使蚁群的搜索过早陷于局部最优。 ( 3 ) 期望启发式因子p 对蚁群算法性能的影响。p 越大，算法的收敛速度加快，但 蚁群搜索最优路径的随机性减弱，易于陷入局部最优；而f 过小，算法的搜索随机性加 强，很难找到最优解。 ( 4 ) 信息素强度q 对蚁群算法性能的影响。在a n t - c y c l e 模型中，q 为蚂蚁循环一 周时释放在所经路径上的信息素总量。q 越大，则在蚂蚁已遍历路径上信息素的累积加 快，可以加强蚁群搜索时的正反馈性能，有助于算法的快速收敛。但是当q 特别大时， 算法容易陷入局部极值。 ( 5 ) 蚂蚁数目m 对蚁群算法性能的影响。m 过多，可以提高蚁群算法的全局搜索 能力及算法的稳定性，但收敛速度减慢；而太少，算法的收敛速度加快，全局搜索的随 机性减弱，稳定性变差，且容易出现过早停滞现象。 3 2 模糊理论基础与应用 3 2 1 模糊理论的提出 1 9 6 5 年，美国加州大学伯克利分校电气工程系的l a z a d e h 教授在杂志 i n f o r m a t i o na n dc o n t r 0 1 ) ) 上发表了一篇开创性的论文f u z z ys e t ) ) 【i 川，文中首 次提出了表达事物模糊性的重要概念：隶属函数，突破了1 9 世纪末笛卡尔的经典 集合理论，奠定了模糊理论的基础，从此模糊理论开始发展，模糊理论的内容包括 模糊集合理论、模糊逻辑、模糊推理和模糊控制等方面的内容 模糊概念来源于自然界中的模糊现象。例如“高”和“矮”这两个概念，如果一个 人的身高是1 7 0 c m ，我们很难说清楚这个人究竟是“高”还是“矮”。因为“高”和“矮” 之间没有一个确定的边界，这两个概念存在模糊性。模糊性是精确性的对立面， 1 4 东北师范大学硕士学位论文 在现实生活中广泛存在，人们经常借助于模糊概念来解决问题。 3 2 2 模糊集基础 对于非模糊问题，在数学中可以用经典集合论来描述，同样的对于模糊性问题，也 可以用模糊理论来描述。 在经典集合论中，我们可以用x 来表示一个集合，x 申的元素表示为x ，x 的经典 子集a 通常可以用这样的特征函数t t a ( x ) x 0 ，王) 来表述： ，h ( x ) = 皓搿i f fx xe 星a 磊 凶 “i 口是当且仅当的意思，x 属于a 或者不属于a ，非常明确，赋值也是明确的：1 或者0 ，毫不含糊。如果赋值集为闭区间 0 ，l 】，那么a 就是模糊集合。定义如下： 定义1 设在论域x 上，给定了映射 眩( x ) ：x _ f 0 , 1 】p x - 阪( x ) ( 3 7 ) 在上面的公式中，称眩确定了一个x 上的模糊子集五，即模糊集，称眩为五的隶属 度函数，蚝为x 对于磊的隶属度。 毂( x ) 的值越接近于1 ，表示x 隶属于五的程度越高，反之越低。当婚( x ) 的值为集合 0 ，1 ) 时，阪( x ) 演化成经典集合的特征函数阪，而五演化成经典集合a 了。由此看矗 出，经典集合是模糊集合的特殊情况。 模糊集可以表示为如下形式： a = 鼍承( x ) ) ，x 霉 ( 3 8 ) 如果x 为有限集 x i ，x 2 ，) ，那么a 可以表示为如下形式： a = 歹浅) 段 x ( 3 9 ) 如果x 为无限级，那么a 可以表示为如下形式： a ：| | 学( x 净 j x 矗 f 3 1 0 ) 这里，和，不是指求和、积分，而是表示各个元素与隶属度函数对应关系的一 个总括。 下面介绍在实际应用中经常用到的几类隶属函数： 1 、s 函数( 偏大型隶属函数) 东北师范大学硕士学位论文 蜘 沪f 是2 ) 2 ，a b 兰c 11 一l 二- 二l ， x k 1 ， x 圣c ( 3 - 1 1 ) n 伍讪，母= t z s 慷( x , b b ，- b a , 砂b ) x x _ 皂 n 3 2 3 模糊熵 熵是信息论中一个非常基本并有重要应用的概念，熵描述了一个概率分布的不确定 性程度。将熵概念移植到模糊集理论，可得到模糊熵。模糊熵描述了一个模糊集的模糊 性程度。一个模糊集合越模糊，它的模糊熵就越大，反之亦然。模糊熵描述的是概率分 布的不确定程度，一个集合的不确定性越大，它的分布越均匀，信息量也就越大。在一 个特征集合中，每个特征的模糊熵由计算得到。对于某一个特征，它的模糊熵越大，表 明它的不确定性越大，这个特征变量的取值越分散，更有利于分类。 模糊熵的定义有很多，但是一个好的定义必须满足l u c a t e r m i n i 公理： 实函数e ：f ( x ) 专r + 叫做f ( x ) 上的模糊熵，若e 满足以下四个性质： ( 1 ) v d 尸( x ) ，p ( d ) = 0 1 ( 2 ) p ( 【争) 2 脒) e ( 么) ( 3 ) v a ，a + f ( x ) ，若么( x ) i i 时，么( x ) a ( x ) ，若么( x ) 去时，贝l je ( a ) p ( 么) ( 4 ) p ( 么) = e ( a ) 这里f ( x ) 表示论域x 熵的全体模糊集之集，p ( i ) 表示x 上的全体分明集之集， r + = 【0 ，叫。 常见的模糊熵公式有： ( 1 ) 设论域 x = 盘l x 2 ， c a 定义 一 e ( a ) = k z i $ ( 眩) = 一弘a ( z i ) i o 式蚝( 硇) 一( 盖一蚝魄) ) l o g ( 1 一魄) ( 3 1 4 ) 这里， i = l ，z 川。，玛l - 是常数，e ( a ) 是f ( x ) 上的模糊熵。 ( 2 )设论域 x = 瓯黾， c a 定义 东北师范大学硕士学位论文 e ( a ) = 。p ( a ，a 玎一) = l i r i i if a 瓴) 一a n 一瓴) 1 p - i i l t p 1 i 1 j d 1 5 ) 是f ( x ) 上的一个模糊熵。且 毛 定义为砥b 。p ( a ，b | 丢l a 魄) 一b ( x t ) l p j 。3 。6 ， fn1 卯 当r 时，成为h a m m i n g 距离，即 = t a ( , q ) - - b 南1 7 ， ( 3 )设论域 x = 冬l x 2 , j v ae 定3 ( e 凶= 将= 群一 b 是f ( x ) 上的模糊熵。 ( 4 )沿诊域x = & x v a 常叟 e ( a ) = 1 一万d p ( a , a e ) 是f ( x ) 上的模糊熵。 ( 5 )设论域 x = 冬l 毪， v a 定义 e 2 鬻= 蒜篓踹黜 2 。， 是f ( x ) 上的模糊熵。 ( 6 )设论域 x = 弘l ， v a 定义 是f ( x ) 上的模糊熵。 疵( 矗瓯) ，岔( 毪) ) 麟( a ( x j a c 魄力 1 7 靠i = 对( e 东北师范大学硕士学位论文 第四章基于模糊熵的蚁群算法研究 4 1 利用模糊熵对特征子集进行评价 利用模糊熵对特征子集进行评价主要基于以下的事实，即经过特征选择得到的最优 特征子集的模糊熵低于没有进行特征选择的特征集合。因此，随着特征选择过程的进行， 特征子集的模糊熵应该会逐渐变小。在 1 6 中，作者提出一种评价特征的方法，本文在 该方法的基础上做了改进，特征子集的模糊熵可以按照下面的方法求得。 ( 1 ) 聚类过程 k m e a n s 聚类算法是一种基于欧氏距离的无监督的学习算法，聚类的用途是非常 广泛的。它的思路是：k m e a n s 算法接受输入量k ，然后将n 个数据对象划分为k 个 聚类使所获得的聚类满足下面条件：同一聚类中的对象相似度较高，而不同聚类中的对 象相似度较小。为了计算特征子集的模糊熵，使用k m e a n s 算法来将输入数据分为m 类， 生成m 个聚类中心( e l ，) 【1 7 】 ( 2 ) 构造隶属度函数 设x = r l ，r 2 ，m ) 表示一个包含n 个数据的全局数据集，元素r i = r i l ，r i 2 , ，坳 表示 一个数据记录，特征的个数为i d 。设彳i 表示x 上的模糊集和，0 j = 0 l ，0 2 ，0 d 表示类 j 的聚类中心，其中j = 1 ，2 ，m 。元素n 在模糊集彳i 上的隶属度可以表示为互纯) ，它 的计算方法如下： 丑( ) = 1 这里，d ( r i ，0 1 ) 表示欧式距离，欧式距离的计算公式为【18 】： j ( ，岛) = ( 4 1 ) ( 3 ) 模糊熵的计算 设c n 表示数据集x 上属于类j 的元素数目，设d j 表示模糊集ai 上类别j 的概率，表 示为 1 6 1 ： 心( ) q = 等一 心( 气) k = l 1 r ( 4 3 ) 盟似 以一烈 兰。阔 东北师范大学硕士学位论文 类别j 的模糊熵嘎j ( 互) 定义如下【2 0 】： f e c j ( 4 ) = 一ql o g q 全局数据集上的模糊熵h 定义如下 2 3 - 船( 互) = 船c ，( 互) “ h ：妻删互) 4 2 将模糊熵的蚁群算法应用于特征选择 4 2 1 基于模糊熵的蚁群算法的描述 ( 4 4 ) ( 4 5 ) ( 4 6 ) 本文中的蚁群算法是基于基本蚁群算法系统模型的，在此基础上引进了模糊熵对特 征子集进行评价。所以算法的实现过程与基本的蚁群算法大体相同。 算法的主要步骤分为初始化阶段、迭代过程和特征子集评价阶段。 算法的结束条件为： ( 1 ) 达到系统设定的最大迭代次数； ( 2 ) 特征子集的模糊熵低于系统设定的最小值。 在初始化阶段，将生成的k 只蚂蚁随机放在m 个特征上，并设置系统的参数； 在迭代阶段，每只蚂蚁都是根据概率转移公式选择下一个特征的，系统对选择后的 特征子集进行评价，如果此时特征子集的模糊熵不再减小，那么就可以结束本只蚂蚁的 搜索过程。搜索过程结束后还需要更新信息素。 在特征子集评价阶段，系统将本次迭代得到的特征子集与目前的最优特征子集进行 比较，如果本次迭代得到的特征子集更优，则需要更新当前的最优子集为本次迭代得到 的特征子集。然后检测是否满足算法的结束条件，若满足则结束算法的迭代过程，输出 运算结果，否则继续迭代。 由于特征和类之间的互信息能够很好的评价特征对于分类的影响，因此可以将特征 和类之间的互信息作为蚁群算法的启发函数【l9 1 。系统的状态转移公式为： 信息素更新公式为： 算法的流程图如下所示： a r ，( t ) = 1 h t ( f + 1 ) = ( 1 一p ) ( f ) + t ( f ) ( 4 7 ) ( 4 8 ) ( 4 9 ) 东北师范大学硕士学位论文 图4 1 算法的流程图 本算法的部分代码如下： 。状态转移规则 ：p u b l i ci n tc h a n g e s t a t e r u l e ( d o u b l eq ，i n ts t a t e _ n o w ) i n ts t a t en e x t = o ； q u e u e q u e u e _ n e x t s t a t e s e t = n e wq u e u e ( a n t c o u n t - 1 ) ； f o r ( i n ti = o ；i e x p l o r a t i o n 部分，蚂蚁则根据每个特征的转移概率来确定，选择具 有最大转移概率的特征 e l s e d o u b l es u m v a l u e = o ； d o u b l em a x v a l u e = d o u b l e m i n v a l u e ； f o r e a c h ( i n tu i nn e x t s t a t e s e t ) d o u b l ev a l u e = b e t a 宰t 【u 】+ ( 1 一b e t a ) 木i t a u ； s u m v a l u e + _ v a l u e ； ) f o r e a c h ( i r asi nn e x t s t a t e s e t ) d o u b l ev a l u e = b e t a 幸t s 】+ ( 1 一b e t a ) 母i t a s ； i f ( v a l u e m a x _ v a l u e ) s t a t e n e x t2s ； ) r e t u r ns t a t e _ n e x t ； ) 更新各个特征节点的信息素 2 】 东北师范大学硕士学位论文 p u b l i cv o i du p d a t e t ( i n tf e a t u r e n o d e ) d o u b l eh = c o m p u t e e n t r o p y 0 ； t h i s 1 0 = 2 m a t h a t a n ( t f e a t u r e n o d e ) m a t h p i ； d o u b l ed e r t = c o n v e a t o d o u b l e ( 1 ) h ； t f e a t u r e n o d e 】= ( 1 一t h i s 1 0 ) 木t f e a t u r e n o d e 】+ d e r t ； 将所有节点信息素的总量限定在一定范围内 d o u b l e t m a x = ( c o n v e g t o d o u b l e ( 1 ) ( 1一t h i s 1 0 ) ) ( c o n v e r t t o d o u b l e ( 1 ) ( h ) ) ； 。 d o u b l el m i n = l m a x ( 2 宰a n t c o u n t ) ； i f ( t f e a t u r e n o d e 】 t - m a x ) t f e a t u r e n o d e 】2t - m a x ； i f ( t f e a t u r e n o d e 】 诗算懒值 p u b l i cd o u b l ec o m p u t e e n t r o p y 0 d o u b l ee n t r o p y v a l u e = 0 ： t h i s g e t s u b f e a t u r e s e t 0 ； i f ( t h