【机器学习】面向特征选择问题的协同演化方法

第12卷第1期 智能系统学报 Vol.12 No.1 2017年2月 CAAI Transactions on Intelligent Systems Feb.2017 D0I:10.1992/tis.201611029 网络出版地址：http://kns.cmki.net/kcms/detail/23.1538.TP.20170302.1522.002.html 面向特征选择问题的协同演化方法 滕旭阳，董红斌，孙静 (哈尔滨工程大学计算机科学与技术学院，黑龙江哈尔滨150001) 摘要：特征选择技术是机器学习和数据挖掘任务的关键预处理技术。传统贪婪式特征选择方法仅考虑本轮最佳 特征，从而导致获取的特征子集仅为局部最优，无法获得最优或者近似最优的特征集合。进化搜索方式则有效地对 特征空间进行搜索，然而不同的进化算法在搜索过程中存在自身的局限。本文吸取遗传算法(GA)和粒子群优化算 法(P$0)的进化优势，以信息嫡度量为评价，通过协同演化的方式获取最终特征子集。并提出适用于特征选择问题 特有的比特率交叉算子和信息交换策略。实验结果显示，遗传算法和粒子群协同进化(GAP$0)在进化搜索特征子 集的能力和具体分类学习任务上都优于单独的演化搜索方式。进化搜索提供的组合判断能力优于贪婪式特征选择 方法。 关键词：特征选择：遗传算法：粒子群优化；协同演化：比特率交叉 中图分类号：TP301文献标志码：A文章编号：1673-4785(2017)01-0024-08 中文引用格式：滕旭阳，董红斌，孙静.面向特征选择问题的协同演化方法[J].智能系统学报，2017,12(1)：24-31. 英文引用格式：TENG Xuyang,DONG Hongbin,SUN Jing.Co-evolutionary algorithm for feature selection[J].CAAI transactions on intelligent systems,2017,12(1):24-31. Co-evolutionary algorithm for feature selection TENG Xuyang,DONG Hongbin,SUN Jing (College of Computer Science and Technology,Harbin Engineering University,Harbin 150001,China) Abstract:Feature selection is a key preprocessing technology of machine learning and data mining.The traditional greed type of feature selection methods only considers the best feature of the current round,thereby leading to the feature subset that is only locally optimal.Realizing an optimal or nearly optimal feature set is difficult.Evolutionary search means can effectively search for a feature space,but different evolutionary algorithms have their own limitations in search processes.The evolutionary advantages of genetic algorithms (GA)and particle swarm optimization(PSO)are absorbed in this study.The final feature subset is obtained by co-evolution,with the information entropy measure as an assessment function.A specific bit rate cross operator and an information exchange strategy applicable for a feature selection problem are proposed.The experimental results show that the co- evolutionary method(GA-PSO)is superior to the single evolutionary search method in the search ability of the feature subsets and classification learning.In conclusion,the ability of combined evaluation,which is provided by an evolutionary search,is better than that of the traditional greedy feature selection method. Keywords:feature selection;genetic algorithm (GA);particle swarm optimization (PSO);co-evolution;bit rate cross 特征选择在数据挖掘和机器学习中不仅可以 减少数据的维度，降低所需处理的数据量，而且还 可以提升某些学习算法的表现山，比如：分类学习、 收稿日期：2016-11-19.网络出版日期：2017-03-02. 聚类、回归问题和时间序列预测等。然而维数据特 基金项目：国家自然科学基金项目(61472095,61502116)：黑龙江省教 育厅智能教育与信息工程重点实验室开放基金项目. 征选择面临着特别庞大的搜索空间等，当存在n维 通信作者：孙静.E-mail:sunjing(@hrbeu..cdu.cn. 特征时解的搜索空间为2“，因此穷举搜索是不可行

第 １２ 卷第 １ 期 智 能 系 统 学 报 Ｖｏｌ．１２ №．１ ２０１７ 年 ２ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｆｅｂ． ２０１７ ＤＯＩ：１０．１９９２ ／ ｔｉｓ．２０１６１１０２９ 网络出版地址：ｈｔｔｐ： ／ ／ ｋｎｓ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１７０３０２．１５２２．００２．ｈｔｍｌ 面向特征选择问题的协同演化方法 滕旭阳，董红斌，孙静 （哈尔滨工程大学 计算机科学与技术学院，黑龙江 哈尔滨 １５０００１） 摘 要：特征选择技术是机器学习和数据挖掘任务的关键预处理技术。 传统贪婪式特征选择方法仅考虑本轮最佳 特征，从而导致获取的特征子集仅为局部最优，无法获得最优或者近似最优的特征集合。 进化搜索方式则有效地对 特征空间进行搜索，然而不同的进化算法在搜索过程中存在自身的局限。 本文吸取遗传算法（ＧＡ）和粒子群优化算 法（ＰＳＯ）的进化优势，以信息熵度量为评价，通过协同演化的方式获取最终特征子集。 并提出适用于特征选择问题 特有的比特率交叉算子和信息交换策略。 实验结果显示，遗传算法和粒子群协同进化（ＧＡ⁃ＰＳＯ）在进化搜索特征子 集的能力和具体分类学习任务上都优于单独的演化搜索方式。 进化搜索提供的组合判断能力优于贪婪式特征选择 方法。 关键词：特征选择；遗传算法；粒子群优化；协同演化：比特率交叉 中图分类号：ＴＰ３０１ 文献标志码：Ａ 文章编号：１６７３－４７８５（２０１７）０１－００２４－０８ 中文引用格式：滕旭阳，董红斌，孙静．面向特征选择问题的协同演化方法［Ｊ］． 智能系统学报， ２０１７， １２（１）： ２４－３１． 英文引用格式：ＴＥＮＧ Ｘｕｙａｎｇ，ＤＯＮＧ Ｈｏｎｇｂｉｎ，ＳＵＮ Ｊｉｎｇ．Ｃｏ⁃ｅｖｏｌｕｔｉｏｎａｒｙ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｆｅａｔｕｒｅ ｓｅｌｅｃｔｉｏｎ［ Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１７， １２（１）： ２４－３１． Ｃｏ⁃ｅｖｏｌｕｔｉｏｎａｒｙ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｆｅａｔｕｒｅ ｓｅｌｅｃｔｉｏｎ ＴＥＮＧ Ｘｕｙａｎｇ， ＤＯＮＧ Ｈｏｎｇｂｉｎ， ＳＵＮ Ｊｉｎｇ （Ｃｏｌｌｅｇｅ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｈａｒｂｉｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ， Ｈａｒｂｉｎ １５０００１， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｆｅａｔｕｒｅ ｓｅｌｅｃｔｉｏｎ ｉｓ ａ ｋｅｙ ｐｒｅｐｒｏｃｅｓｓｉｎｇ ｔｅｃｈｎｏｌｏｇｙ ｏｆ ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ ａｎｄ ｄａｔａ ｍｉｎｉｎｇ． Ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ ｇｒｅｅｄ ｔｙｐｅ ｏｆ ｆｅａｔｕｒｅ ｓｅｌｅｃｔｉｏｎ ｍｅｔｈｏｄｓ ｏｎｌｙ ｃｏｎｓｉｄｅｒｓ ｔｈｅ ｂｅｓｔ ｆｅａｔｕｒｅ ｏｆ ｔｈｅ ｃｕｒｒｅｎｔ ｒｏｕｎｄ， ｔｈｅｒｅｂｙ ｌｅａｄｉｎｇ ｔｏ ｔｈｅ ｆｅａｔｕｒｅ ｓｕｂｓｅｔ ｔｈａｔ ｉｓ ｏｎｌｙ ｌｏｃａｌｌｙ ｏｐｔｉｍａｌ． Ｒｅａｌｉｚｉｎｇ ａｎ ｏｐｔｉｍａｌ ｏｒ ｎｅａｒｌｙ ｏｐｔｉｍａｌ ｆｅａｔｕｒｅ ｓｅｔ ｉｓ ｄｉｆｆｉｃｕｌｔ． Ｅｖｏｌｕｔｉｏｎａｒｙ ｓｅａｒｃｈ ｍｅａｎｓ ｃａｎ ｅｆｆｅｃｔｉｖｅｌｙ ｓｅａｒｃｈ ｆｏｒ ａ ｆｅａｔｕｒｅ ｓｐａｃｅ， ｂｕｔ ｄｉｆｆｅｒｅｎｔ ｅｖｏｌｕｔｉｏｎａｒｙ ａｌｇｏｒｉｔｈｍｓ ｈａｖｅ ｔｈｅｉｒ ｏｗｎ ｌｉｍｉｔａｔｉｏｎｓ ｉｎ ｓｅａｒｃｈ ｐｒｏｃｅｓｓｅｓ． Ｔｈｅ ｅｖｏｌｕｔｉｏｎａｒｙ ａｄｖａｎｔａｇｅｓ ｏｆ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍｓ （ ＧＡ） ａｎｄ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ （ＰＳＯ） ａｒｅ ａｂｓｏｒｂｅｄ ｉｎ ｔｈｉｓ ｓｔｕｄｙ． Ｔｈｅ ｆｉｎａｌ ｆｅａｔｕｒｅ ｓｕｂｓｅｔ ｉｓ ｏｂｔａｉｎｅｄ ｂｙ ｃｏ⁃ｅｖｏｌｕｔｉｏｎ， ｗｉｔｈ ｔｈｅ ｉｎｆｏｒｍａｔｉｏｎ ｅｎｔｒｏｐｙ ｍｅａｓｕｒｅ ａｓ ａｎ ａｓｓｅｓｓｍｅｎｔ ｆｕｎｃｔｉｏｎ． Ａ ｓｐｅｃｉｆｉｃ ｂｉｔ ｒａｔｅ ｃｒｏｓｓ ｏｐｅｒａｔｏｒ ａｎｄ ａｎ ｉｎｆｏｒｍａｔｉｏｎ ｅｘｃｈａｎｇｅ ｓｔｒａｔｅｇｙ ａｐｐｌｉｃａｂｌｅ ｆｏｒ ａ ｆｅａｔｕｒｅ ｓｅｌｅｃｔｉｏｎ ｐｒｏｂｌｅｍ ａｒｅ ｐｒｏｐｏｓｅｄ． Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｃｏ⁃ ｅｖｏｌｕｔｉｏｎａｒｙ ｍｅｔｈｏｄ （ＧＡ⁃ＰＳＯ） ｉｓ ｓｕｐｅｒｉｏｒ ｔｏ ｔｈｅ ｓｉｎｇｌｅ ｅｖｏｌｕｔｉｏｎａｒｙ ｓｅａｒｃｈ ｍｅｔｈｏｄ ｉｎ ｔｈｅ ｓｅａｒｃｈ ａｂｉｌｉｔｙ ｏｆ ｔｈｅ ｆｅａｔｕｒｅ ｓｕｂｓｅｔｓ ａｎｄ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｌｅａｒｎｉｎｇ． Ｉｎ ｃｏｎｃｌｕｓｉｏｎ， ｔｈｅ ａｂｉｌｉｔｙ ｏｆ ｃｏｍｂｉｎｅｄ ｅｖａｌｕａｔｉｏｎ， ｗｈｉｃｈ ｉｓ ｐｒｏｖｉｄｅｄ ｂｙ ａｎ ｅｖｏｌｕｔｉｏｎａｒｙ ｓｅａｒｃｈ， ｉｓ ｂｅｔｔｅｒ ｔｈａｎ ｔｈａｔ ｏｆ ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ ｇｒｅｅｄｙ ｆｅａｔｕｒｅ ｓｅｌｅｃｔｉｏｎ ｍｅｔｈｏｄ． Ｋｅｙｗｏｒｄｓ：ｆｅａｔｕｒｅ ｓｅｌｅｃｔｉｏｎ； ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ （ ＧＡ）； ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ （ ＰＳＯ）； ｃｏ⁃ｅｖｏｌｕｔｉｏｎ； ｂｉｔ ｒａｔｅ ｃｒｏｓｓ 收稿日期：２０１６－１１－１９． 网络出版日期：２０１７－０３－０２． 基金项目：国家自然科学基金项目（ ６１４７２０９５，６１５０２１１６）；黑龙江省教 育厅智能教育与信息工程重点实验室开放基金项目． 通信作者：孙静． Ｅ⁃ｍａｉｌ：ｓｕｎｊｉｎｇ＠ ｈｒｂｅｕ．ｅｄｕ．ｃｎ． 特征选择在数据挖掘和机器学习中不仅可以 减少数据的维度，降低所需处理的数据量，而且还 可以提升某些学习算法的表现［１］ ，比如：分类学习、 聚类、回归问题和时间序列预测等。 然而维数据特 征选择面临着特别庞大的搜索空间等，当存在 ｎ 维 特征时解的搜索空间为 ２ ｎ ，因此穷举搜索是不可行

第1期 膝旭阳，等：面向特征选择问题的协同演化方法 25· 的。特征选择方法大致可分为3类：过滤式 并且D中的每个样本都有特征集合F,F包含n维 (filter)、包裹式(wrapper)和嵌入式(embedding)[)。 特征，x:∈R“。对于分类问题，可将D中样本划分为 过滤式方法与具体学习方法无关，主要依据数据的 目标向量C中的m个不同的类C={C,C2,…, 内在属性对特征进行过滤，再用选择出的特征训练 C{。特征选择的目的，是在原始特征集合N中寻 模型。包裹式方法将最终要使用的学习器的学习 找到一个最佳特征子集P,其中含有p维特征(p< 性能作为评价子集评价标准。嵌入式方法将特征 n),在该特征子集下能最大化分类任务（或其他学 选择过程与学习器训练过程融为一体，两者在同一 习任务)的预测正确率。 过程中优化。wrapper方法对于具体学习器效果好， 特征选择处理包括4个组件：特征子集生成、子 但其计算代价高，泛化能力差。filter方法虽然在具 集评估、终止条件和结果验证。如图1所示，在阶段 体学习方法中精度低于wrapper方法，但其泛化能 1中根据一个确定的搜索策略特征子集生成组件会 力强，计算效率高，在大规模数据集上更加适用。 预先产生候选特征子集。每一个候选特征子集都 因此，本文选用基于信息熵度量的filter评价方式。 会被一个确定的评估方式所度量，并与之前最佳的 为了保证搜索的高效，许多学者选择了贪婪式 候选特征子集做比较，如果新的特征子集表现得更 搜索方法来选择子集，代表性方法有基于信息增益 加优越，那么替换原有的最佳特征子集。当满足设 的方法(IG)【和基于信息比率的方法(GR)[。然 定的终止条件时，生成和评估这两个过程将不再循环。 而贪婪方法无可避免地导致其结果为局部最优，因 在阶段2中，最终所选的特征子集需要被一些给定的学 为其在选择过程中仅考虑当前轮的单个最佳或最 习算法进行结果验证，其中ACC为学习正确率[)」 差特征6。为了解决上述问题，全局搜索的方式则 特征选择 阶段1 成为特征选择问题中一种有效的寻优方式。演化 计算作为一种具有良好全局搜索能力的代表技术 特征子集 子集 终止 近年来被越来越多地使用在特征选择技术中[)。 生成 :评估 条件 训练数据 随着各个领域内数据维度不断地增加，自2007后遗 传算法（genetic algorithm,GA)与粒子群优化 最佳 (particle swarm optimization,PSO)成为特征选择进 测试数据 测试学习 训练学 特征 模型 习模型 子集 化搜索策略中两个主流的全局搜索方法，特别是 模型拟合表现评估 PSO方法因其搜索速度得到了广泛的使用。Peng ACO 阶段2 等[]在2005年提出了最大相关最小冗余的特征选 图1特征选择处理的统一视角 择方法(mRmR),该方法使用了贪婪式搜索方式。 Fig.1 A unified view of feature selection process 在2011年和2012年学者们验证了使用mRmR进行 1.2 遗传算法基本原理 度量并采取群智能进化搜索的方式可以获得更优 遗传算法作为一种自适应全局优化搜索算法， 的特征子集[9,0 其选择、交叉与变异的3个算子成为种群寻优和保 虽然在特征选择问题中演化算法的搜索能力 持解多样性的关键。其基本执行过程如下。 优于贪婪式搜索，但不同的演化算法自身也存在局 I)初始化：确定种群规模N,交叉概率P、变 限性。因此更多的学者开始研究协同演化的方法， 异概率Pion和终止进化准则。 其中包括策略的协同)和种群的协同2]。本文选 2)个体评价：计算每个个体的适应度。 用GA与PS0两种进化种群的协同。PSO的优势 3)种群进化： 在于对解的记忆能力强及高效的收敛速度，但该方 ①选择算子：个体被选中的概率与其适应度函 法极容易陷入到局部最优解，表现出极强的趋同性 数值成正比。 和较低的种群多样性。GA方法中染色体之间共享 ②交叉算子：根据交叉概率P对2条染色体 信息，种群较为均匀地移动并保持多样性，但其收 交换部分基因，构造下一代新的染色体。 敛速度相对较慢。因此，本文提出了一种面向特征 ③变异算子：根据概率Pmim对群体中的不同 选择问题的协同演化方法(GA-PS0),演化过程中 个体指定的基因位进行改造。 既保证了全局搜索能力以防止陷入局部最优，又提 ④终止检验：如已满足终止准则，则输出最优 升了演化速度。 解：否则转到2)。 1 基础知识 1.3二元粒子群优化基本原理 粒子群优化算法，源于对鸟群捕食的行为研 1.1特征选择 究，是由Kennedy和Eberhart等Ia)开发的一种新的 数据集D中含有k个样本D={x1,x2,…,x4}, 进化算法。粒子在搜索空间内寻优，并定位当前路

的［２］ 。 特 征 选 择 方 法 大 致 可 分 为 ３ 类： 过 滤 式 （ｆｉｌｔｅｒ）、包裹式（ｗｒａｐｐｅｒ）和嵌入式（ｅｍｂｅｄｄｉｎｇ） ［３］ 。 过滤式方法与具体学习方法无关，主要依据数据的 内在属性对特征进行过滤，再用选择出的特征训练 模型。 包裹式方法将最终要使用的学习器的学习 性能作为评价子集评价标准。 嵌入式方法将特征 选择过程与学习器训练过程融为一体，两者在同一 过程中优化。 ｗｒａｐｐｅｒ 方法对于具体学习器效果好， 但其计算代价高，泛化能力差。 ｆｉｌｔｅｒ 方法虽然在具 体学习方法中精度低于 ｗｒａｐｐｅｒ 方法，但其泛化能 力强，计算效率高，在大规模数据集上更加适用。 因此，本文选用基于信息熵度量的 ｆｉｌｔｅｒ 评价方式。 为了保证搜索的高效，许多学者选择了贪婪式 搜索方法来选择子集，代表性方法有基于信息增益 的方法（ＩＧ） ［４］和基于信息比率的方法（ＧＲ） ［５］ 。 然 而贪婪方法无可避免地导致其结果为局部最优，因 为其在选择过程中仅考虑当前轮的单个最佳或最 差特征［６］ 。 为了解决上述问题，全局搜索的方式则 成为特征选择问题中一种有效的寻优方式。 演化 计算作为一种具有良好全局搜索能力的代表技术 近年来被越来越多地使用在特征选择技术中［７］ 。 随着各个领域内数据维度不断地增加，自 ２００７ 后遗 传算 法 （ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ， ＧＡ ） 与 粒 子 群 优 化 （ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ，ＰＳＯ） 成为特征选择进 化搜索策略中两个主流的全局搜索方法，特别是 ＰＳＯ 方法因其搜索速度得到了广泛的使用。 Ｐｅｎｇ 等［８］在 ２００５ 年提出了最大相关最小冗余的特征选 择方法（ｍＲｍＲ），该方法使用了贪婪式搜索方式。 在 ２０１１ 年和 ２０１２ 年学者们验证了使用 ｍＲｍＲ 进行 度量并采取群智能进化搜索的方式可以获得更优 的特征子集［９，１０］ 。 虽然在特征选择问题中演化算法的搜索能力 优于贪婪式搜索，但不同的演化算法自身也存在局 限性。 因此更多的学者开始研究协同演化的方法， 其中包括策略的协同［１１］ 和种群的协同［１２］ 。 本文选 用 ＧＡ 与 ＰＳＯ 两种进化种群的协同。 ＰＳＯ 的优势 在于对解的记忆能力强及高效的收敛速度，但该方 法极容易陷入到局部最优解，表现出极强的趋同性 和较低的种群多样性。 ＧＡ 方法中染色体之间共享 信息，种群较为均匀地移动并保持多样性，但其收 敛速度相对较慢。 因此，本文提出了一种面向特征 选择问题的协同演化方法（ＧＡ⁃ＰＳＯ），演化过程中 既保证了全局搜索能力以防止陷入局部最优，又提 升了演化速度。 １ 基础知识 １．１ 特征选择 数据集 Ｄ 中含有 ｋ 个样本 Ｄ ＝ ｛ ｘ１ ，ｘ２ ，…，ｘｋ｝， 并且 Ｄ 中的每个样本都有特征集合 Ｆ，Ｆ 包含 ｎ 维 特征，ｘｉ∈Ｒ ｎ 。 对于分类问题，可将 Ｄ 中样本划分为 目标向量 Ｃ 中的 ｍ 个不同的类 Ｃ ＝ ｛ Ｃ１ ，Ｃ２ ，…， Ｃｍ ｝。 特征选择的目的，是在原始特征集合 Ｎ 中寻 找到一个最佳特征子集 Ｐ，其中含有 ｐ 维特征（ ｐ＜ ｎ），在该特征子集下能最大化分类任务（或其他学 习任务）的预测正确率。 特征选择处理包括 ４ 个组件：特征子集生成、子 集评估、终止条件和结果验证。 如图 １ 所示，在阶段 １ 中根据一个确定的搜索策略特征子集生成组件会 预先产生候选特征子集。 每一个候选特征子集都 会被一个确定的评估方式所度量，并与之前最佳的 候选特征子集做比较，如果新的特征子集表现得更 加优越，那么替换原有的最佳特征子集。 当满足设 定的终止条件时，生成和评估这两个过程将不再循环。 在阶段２ 中，最终所选的特征子集需要被一些给定的学 习算法进行结果验证，其中 ＡＣＣ 为学习正确率 ［３］ 。 图 １ 特征选择处理的统一视角 Ｆｉｇ．１ Ａ ｕｎｉｆｉｅｄ ｖｉｅｗ ｏｆ ｆｅａｔｕｒｅ ｓｅｌｅｃｔｉｏｎ ｐｒｏｃｅｓｓ １．２ 遗传算法基本原理 遗传算法作为一种自适应全局优化搜索算法， 其选择、交叉与变异的 ３ 个算子成为种群寻优和保 持解多样性的关键。 其基本执行过程如下。 １） 初始化：确定种群规模 Ｎ、交叉概率 Ｐｃｒｏｓｓ、变 异概率 Ｐｍｕｔａｔｉｏｎ和终止进化准则。 ２） 个体评价：计算每个个体的适应度。 ３） 种群进化： ①选择算子：个体被选中的概率与其适应度函 数值成正比。 ②交叉算子：根据交叉概率 Ｐｃｒｏｓｓ对 ２ 条染色体 交换部分基因，构造下一代新的染色体。 ③变异算子：根据概率 Ｐｍｕｔａｔｉｏｎ对群体中的不同 个体指定的基因位进行改造。 ④终止检验：如已满足终止准则，则输出最优 解；否则转到 ２）。 １．３ 二元粒子群优化基本原理 粒子群优化算法，源于对鸟群捕食的行为研 究，是由 Ｋｅｎｎｅｄｙ 和 Ｅｂｅｒｈａｒｔ 等［１３］ 开发的一种新的 进化算法。 粒子在搜索空间内寻优，并定位当前路 第 １ 期 滕旭阳，等：面向特征选择问题的协同演化方法 ·２５·

·26 智能系统学报 第12卷 径中的最佳位置。每一个粒子都需要考虑自身当 2.2适应度函数 前的位置和速度，记录它们自己的最优解（最佳位 本文使用互信息嫡理论对特征子集进行整体 置)p,并根据粒子群体内全局最优解ga调整当 评估，两个变量的互信息值越大，则意味着两个变 前自身位置，粒子的具体更新如下： 量相关程度越紧密：当互信息为零时，则意味着两 1=wr片+c1×rand(Phe-xa)+c2× 个变量完全不相关。特征集合F={f,,…,f}中 rand(ghet-xh） (1) 某一特征与类别的互信息度量如下： xl= (2) I(f,C)=H(f)+(C)-H(fi,C) (5) 速度和位置的更新过程中，t是粒子h在第t 式中：H为变量的嫡值，用以度量随机变量信息的不 轮迭代中的速度；0为惯性系数：c1与c2为加速系 确定性。以类别向量为例，H(C)通常用作描述离散 数；x是粒子h在第t轮迭代中的位置；P,是第h 个粒子目前的最佳位置。其中，w提供了粒子的 随机变量C={c1,c2,…,cn}熵值，c是变量C的可能 搜索能力，c,×rand(Pet)和c2,×rand(ge-xi)分 取值，P(c:)为概率密度函数。 别表达了粒子自身的演化和粒子间的合作。 H(C)=- (6) 基于上述研究，学者Kennedy调整了连续PSO p(e,)lgp(ce)） = 方法中速度和位置的更新方式，提出了适用于解决离 当已知特征变量和类别变量∫和C的联合概率 散问题的二元粒子群算法(binary particle swarm 密度时（对于离散数据意味着两个变量对应的属性 optimization,BPSO)[w。该思想中的粒子仅可以在二 值联合出现的频度)，两者的联合嫡为 元空间中进行搜索，粒子的位置向量仅可以用0或1 HU,C)=-∑∑p,c)logp(,c)(7) 表示。BPSO方法中影响其寻优能力的关键之一就是 f月efi,Hec 转换函数，利用该函数将连续的速度值转化为离散的 基于特征与类别向量的信息嫡度量构建适应 位置。在最初的研究中使用式(3)中的sigmoid函数 度函数，适应度函数的度量体现了进化过程对优良 作为转换函数将实值的速度映射为[0,1]之间的值。 个体的保留，对低劣个体的淘汰。本文在设计适应 T((t)=1 (3) 度函数时不仅考虑了特征与类别的相关性，而且将 I +e( 特征子集规模也作为影响个体（粒子）适应度的一 式中：t(t)为粒子h在第t轮迭代中第k维的速 部分，适应度函数的设计试图找出子集规模小，并 度。在将粒子速度转换为概率值后，位置向量将依 且特征与类别高度相关的特征集合。具体适应度 据概率值进行更新： 函数设计如下： (0,rand T((t+1)) x(t+1)= (4) Fit,MI x S (8) 1. rand≥T((t+1) MI Fit,=Mx S (9) 2 求解特征子集的协同演化方法 式中：MI部分为特征与类别关联性度量；S部分为 2.1编码方式 特征子集规模控制。假设当前候选特征子集为在 本文使用了二进制比特串的编码方式，该编码 方式通用于遗传算法和二元粒子群方法，如图2所 全部n维特征中选出的p维特征： 示。将每个二进制串作为一个个体（粒子），个体 MI= I(f,c) (10) (粒子)中的每一维（每一比特）都代表一个候选特 i=1 征，当该位为1时表示该特征被选中，并添加到候选 s=n-p (11) 的特征子集中：当该位为0时表示该特征未被选中。 依据此编码方式将特征选择问题转换为寻找最佳 本文设计式(8)和式(9)两个适应度函数，在寻 个体（粒子）的问题。 优过程中试图寻找最大值。其原理在于，小规模数 01 1 0 1 据集特征维度较少，在进化过程中对特征空间搜索 较为全面。采用式(8)重点考察特征与类别的相关 n bit …●被选中的特征 性。而对于大规模数据集，特征维度较大，进化搜 ……●未被选中的特征 索特征空间的过程中很难控制特征子集规模，并且 图2二元粒子群的编码方式 容易在候选特征较多时形成局部最优，所以在式 Fig.2 Coding scheme of BPSO (9)中增大了对特征子集规模的惩罚系数。假设式

径中的最佳位置。 每一个粒子都需要考虑自身当 前的位置和速度，记录它们自己的最优解（最佳位 置）ｐｂｓｅｔ，并根据粒子群体内全局最优解 ｇｂｅｓｔ调整当 前自身位置，粒子的具体更新如下： ｖ ｔ＋１ ｈ ＝ ｗｖ ｔ ｈ ＋ ｃ１ × ｒａｎｄ（ｐｂｅｓｔｈ － ｘ ｔ ｈ ） ＋ ｃ２ × ｒａｎｄ（ｇｂｅｓｔ － ｘ ｔ ｈ ） （１） ｘ ｔ＋１ ｈ ＝ ｘ ｔ ｈ ＋ ｖ ｔ＋１ ｈ （２） 速度和位置的更新过程中，ｖ ｔ ｈ 是粒子 ｈ 在第 ｔ 轮迭代中的速度；ｗ 为惯性系数；ｃ１ 与 ｃ２ 为加速系 数；ｘ ｔ ｈ 是粒子 ｈ 在第 ｔ 轮迭代中的位置；ｐｂｅｓｔｈ是第 ｈ 个粒子目前的最佳位置。 其中，ｗｖ ｔ ｈ 提供了粒子的 搜索能力，ｃ１ ×ｒａｎｄ（ｐｂｅｓｔｈ －ｘ ｔ ｈ ）和 ｃ２ ×ｒａｎｄ（ ｇｂｅｓｔ －ｘ ｔ ｈ ）分 别表达了粒子自身的演化和粒子间的合作。 基于上述研究，学者 Ｋｅｎｎｅｄｙ 调整了连续 ＰＳＯ 方法中速度和位置的更新方式，提出了适用于解决离 散问 题 的 二 元 粒 子 群 算 法 （ ｂｉｎａｒｙ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ，ＢＰＳＯ） ［１４］ 。 该思想中的粒子仅可以在二 元空间中进行搜索，粒子的位置向量仅可以用 ０ 或 １ 表示。 ＢＰＳＯ 方法中影响其寻优能力的关键之一就是 转换函数，利用该函数将连续的速度值转化为离散的 位置。 在最初的研究中使用式（３）中的 ｓｉｇｍｏｉｄ 函数 作为转换函数将实值的速度映射为［０，１］之间的值。 Ｔ ｖ ｋ ( ｈ（ｔ） ) ＝ １ １ ＋ ｅ －ｖ ｋ ｈ （ｔ） （３） 式中： ｖ ｋ ｈ（ｔ） 为粒子 ｈ 在第 ｔ 轮迭代中第 ｋ 维的速 度。 在将粒子速度转换为概率值后，位置向量将依 据概率值进行更新： ｘ ｋ ｈ（ｔ ＋ １） ＝ ０， ｒａｎｄ ＜ Ｔ ｖ ｋ ( ｈ（ｔ ＋ １） ) １， ｒａｎｄ ≥ Ｔ ｖ ｋ { ( ｈ（ｔ ＋ １） ) （４） ２ 求解特征子集的协同演化方法 ２．１ 编码方式 本文使用了二进制比特串的编码方式，该编码 方式通用于遗传算法和二元粒子群方法，如图 ２ 所 示。 将每个二进制串作为一个个体（粒子），个体 （粒子）中的每一维（每一比特）都代表一个候选特 征，当该位为 １ 时表示该特征被选中，并添加到候选 的特征子集中；当该位为 ０ 时表示该特征未被选中。 依据此编码方式将特征选择问题转换为寻找最佳 个体（粒子）的问题。 图 ２ 二元粒子群的编码方式 Ｆｉｇ．２ Ｃｏｄｉｎｇ ｓｃｈｅｍｅ ｏｆ ＢＰＳＯ ２．２ 适应度函数 本文使用互信息熵理论对特征子集进行整体 评估，两个变量的互信息值越大，则意味着两个变 量相关程度越紧密；当互信息为零时，则意味着两 个变量完全不相关。 特征集合 Ｆ ＝ ｛ｆ １ ，ｆ ２ ，…，ｆ ｎ ｝中 某一特征 ｆ ｉ 与类别的互信息度量如下： Ｉ（ｆ ｉ，Ｃ） ＝ Ｈ（ｆ ｉ） ＋ Ｈ（Ｃ） － Ｈ（ｆ ｉ，Ｃ） （５） 式中：Ｈ 为变量的熵值，用以度量随机变量信息的不 确定性。 以类别向量为例，Ｈ（Ｃ）通常用作描述离散 随机变量 Ｃ ＝ ｛ｃ１ ，ｃ２ ，…，ｃｎ ｝熵值，ｃｉ是变量 Ｃ 的可能 取值，ｐ（ｃｉ）为概率密度函数。 Ｈ（Ｃ） ＝ － ∑ ｍ ｉ ＝ １ ｐ（ｃｉ）ｌｏｇ（ｐ（ｃｉ）） （６） 当已知特征变量和类别变量 ｆ ｉ和 Ｃ 的联合概率 密度时（对于离散数据意味着两个变量对应的属性 值联合出现的频度），两者的联合熵为 Ｈ ｆ( ｉ，Ｃ) ＝ － ∑ ｆ ｊ ｉ ∈ｆ ｉ ， ∑ｃｉ∈Ｃ ｐ ｆ ｊ ｉ ，ｃｉ ( ) ｌｏｇ ｐ ｆ ｊ ｉ ，ｃｉ ( ( ) ) （７） 基于特征与类别向量的信息熵度量构建适应 度函数，适应度函数的度量体现了进化过程对优良 个体的保留，对低劣个体的淘汰。 本文在设计适应 度函数时不仅考虑了特征与类别的相关性，而且将 特征子集规模也作为影响个体（粒子）适应度的一 部分，适应度函数的设计试图找出子集规模小，并 且特征与类别高度相关的特征集合。 具体适应度 函数设计如下： Ｆｉｔ １ ＝ ＭＩ × Ｓ （８） Ｆｉｔ ２ ＝ ＭＩ ｐ × Ｓ （９） 式中：ＭＩ 部分为特征与类别关联性度量；Ｓ 部分为 特征子集规模控制。 假设当前候选特征子集为在 全部 ｎ 维特征中选出的 ｐ 维特征： ＭＩ ＝ ∑ ｐ ｉ ＝ １ Ｉ ｆ( ｉ，Ｃ) （１０） Ｓ ＝ ｎ － ｐ ｎ （１１） 本文设计式（８）和式（９）两个适应度函数，在寻 优过程中试图寻找最大值。 其原理在于，小规模数 据集特征维度较少，在进化过程中对特征空间搜索 较为全面。 采用式（８）重点考察特征与类别的相关 性。 而对于大规模数据集，特征维度较大，进化搜 索特征空间的过程中很难控制特征子集规模，并且 容易在候选特征较多时形成局部最优，所以在式 （９）中增大了对特征子集规模的惩罚系数。 假设式 ·２６· 智 能 系 统 学 报 第 １２ 卷

第1期 膝旭阳，等：面向特征选择问题的协同演化方法 ·27. (8)和式(9)获得相同的适应度函数值，式(9)需要 较容易陷入全局最优解并且过早收敛，进化过程中 尽量减小k值，使得选择特征尽量少以取得关联性 会将搜索引向本次迭代的全局和个体最佳位置，因 度量和子集规模的平衡。 此进化的多样性差。协同的思想对于P$0特征选 2.3比特率交叉算子 择方法的帮助在于，通过本文提出的最佳个体比特 在遗传算法中，交叉算子通过模拟自然界生物 信息位交换策略，每次进化产生最佳个体的比特信 的杂交过程对个体进行交叉操作，不断产生新个 息位不仅仅由PSO决定，事实上它和GA中的最佳 体、增加种群的多样性、扩大寻优范围，从而使得遗 个体共享那些能够引起适应度值增加的优秀比特 传算法具有较强的搜索能力。直观地讲，交叉算子 信息位。将这些优秀的比特基因随机地插入到粒 影响了遗传算法对求解空间影响的搜索能力，并对 子群中最佳个体对应的信息位上。这种方法不仅 能否找到全局最优解发挥了至关重要的作用1]。 有可能使最佳个体变得更优秀，还为PS0算法增加 传统的GA算法交叉操作采用的是单点交叉， 了多样性，避免过早地陷入局部最优解。对于GA 但是在该交叉操作中很可能出现“近亲繁殖”的现 特征选择方法来说，寻优速度较慢，尤其在高维特 象，即进行交叉操作的一对个体基因型相似，减缓 征下往往不能获得令人满意的结果。从信息共享 了遗传算法的搜索速度，或者会出现局部收敛或早 机制来说，遗传算法的信息共享方式主要是通过两 熟收敛，从而影响种群的进化方向。因此本文针对 个个体之间的交叉操作，而粒子群算法的信息共享 特征选择问题提出了比特概率交叉算子，在基因交 方式是通过种群中的最优个体传递信息给其余个 叉的过程中，首先判断两个个体的基因相似比特 体。这两种信息共享机制就相应地决定了两种算 率，并将比特率与交叉概率作比较，若小于该概率 法的表现，粒子群算法每代都选出当前最优个体， 则进行个体基因交叉操作。具体过程如算法1 并进行全局范围的信息共享，使得整个粒子群能向 所示。 着最优的方向快速趋近：而遗传算法的交叉操作具 算法1比特概率交叉算子 有一定的随机性，且由于是一对一进行交叉，每一 输入两个个体的二进制比特基因信息位 次迭代中作用的范围相对较小，使得种群中的优秀 f(i,:)和f(Gj,:),染色体长度n,交叉概率Pmso 基因交流较慢，整个种群的进化比较漫长，所以PS0 输出交叉后两个个体的基因型f(i,:) 特征选择寻优速度较快，效率更高。通过信息交 和f,:)。 互，在迭代过程中种群可以获得更为优秀的个体基 1)m=0. 因型，这有助于加速GA种群的进化过程，提高收敛 2)For k=1:no 速度。同时，通过上文的比特率交叉算子可以避免 3)若两个体的第k位比特位相同则m=m+1。 相近的基因型交叉产生不“健康”的后代个体。具 4)End For 体的GA-PSO协同演化算法如算法2和算法3 5)计算个体间基因型相似比s=m/n。 所示。 6)fs<P交叉概率。 算法2协同演化算法 7)随机选定基因型个体的某一位Posm 输入粒子群和种群初始化参数。 8)For h=Poserom:no 输出最佳个体。 9)交换个体Posm位到第n位的基因。 1)初始化粒子群和种群。 l0)End For。 2)协同演化。 11)End If。 ①计算各个粒子的适应度值。 通过比特率交叉算子可以避免基因型相近的 ②选择粒子群算法最佳个体PSO。 个体进行交叉操作，即可以避免产生“隐性致病基 ③选出遗传算法最佳个体GA 因”，防止相近个体的近亲繁殖，并增强种群个体的 ④最佳个体比特信息位交换。 多样性。 ⑤PS0:更新粒子速度及位置。 2.4GA-PS0协同演化方法的实现 ⑥GA:选择、比特率交叉（算法1）和变异。 本文提出的GA-PSO算法的主要思想是比特位 3)判断终止条件，若不满足返回2)，满足进入4)。 信息交互。传统的PS0特征选择有一定的缺陷，比 4)比较GA与PS0,输出最佳个体

（８）和式（９）获得相同的适应度函数值，式（９）需要 尽量减小 ｋ 值，使得选择特征尽量少以取得关联性 度量和子集规模的平衡。 ２．３ 比特率交叉算子 在遗传算法中，交叉算子通过模拟自然界生物 的杂交过程对个体进行交叉操作，不断产生新个 体、增加种群的多样性、扩大寻优范围，从而使得遗 传算法具有较强的搜索能力。 直观地讲，交叉算子 影响了遗传算法对求解空间影响的搜索能力，并对 能否找到全局最优解发挥了至关重要的作用［１５］ 。 传统的 ＧＡ 算法交叉操作采用的是单点交叉， 但是在该交叉操作中很可能出现“近亲繁殖” 的现 象，即进行交叉操作的一对个体基因型相似，减缓 了遗传算法的搜索速度，或者会出现局部收敛或早 熟收敛，从而影响种群的进化方向。 因此本文针对 特征选择问题提出了比特概率交叉算子，在基因交 叉的过程中，首先判断两个个体的基因相似比特 率，并将比特率与交叉概率作比较，若小于该概率 则进行个体基因交叉操作。 具体过程如算法 １ 所示。 算法 １ 比特概率交叉算子 输入 两个个体的二进制比特基因信息位 ｆ （ｉ，：）和 ｆ （ｊ，：），染色体长度 ｎ，交叉概率 Ｐｃｒｏｓｓ。 输出 交 叉 后 两 个 个 体 的 基 因 型 ｆ （ ｉ，：） 和ｆ （ｊ，：）。 １）ｍ ＝ ０。 ２）Ｆｏｒ ｋ ＝ １：ｎ。 ３）若两个体的第 ｋ 位比特位相同则 ｍ ＝ｍ＋１。 ４）Ｅｎｄ Ｆｏｒ。 ５）计算个体间基因型相似比 ｓ ＝ｍ ／ ｎ。 ６）Ｉｆ ｓ＜Ｐｃｒｏｓｓ交叉概率。 ７）随机选定基因型个体的某一位 Ｐｏｓｃｒｏｓｓ。 ８）Ｆｏｒ ｈ ＝ Ｐｏｓｃｒｏｓｓ：ｎ。 ９）交换个体 Ｐｏｓｃｒｏｓｓ位到第 ｎ 位的基因。 １０）Ｅｎｄ Ｆｏｒ。 １１）Ｅｎｄ Ｉｆ。 通过比特率交叉算子可以避免基因型相近的 个体进行交叉操作，即可以避免产生“隐性致病基 因”，防止相近个体的近亲繁殖，并增强种群个体的 多样性。 ２．４ ＧＡ⁃ＰＳＯ 协同演化方法的实现 本文提出的 ＧＡ⁃ＰＳＯ 算法的主要思想是比特位 信息交互。 传统的 ＰＳＯ 特征选择有一定的缺陷，比 较容易陷入全局最优解并且过早收敛，进化过程中 会将搜索引向本次迭代的全局和个体最佳位置，因 此进化的多样性差。 协同的思想对于 ＰＳＯ 特征选 择方法的帮助在于，通过本文提出的最佳个体比特 信息位交换策略，每次进化产生最佳个体的比特信 息位不仅仅由 ＰＳＯ 决定，事实上它和 ＧＡ 中的最佳 个体共享那些能够引起适应度值增加的优秀比特 信息位。 将这些优秀的比特基因随机地插入到粒 子群中最佳个体对应的信息位上。 这种方法不仅 有可能使最佳个体变得更优秀，还为 ＰＳＯ 算法增加 了多样性，避免过早地陷入局部最优解。 对于 ＧＡ 特征选择方法来说，寻优速度较慢，尤其在高维特 征下往往不能获得令人满意的结果。 从信息共享 机制来说，遗传算法的信息共享方式主要是通过两 个个体之间的交叉操作，而粒子群算法的信息共享 方式是通过种群中的最优个体传递信息给其余个 体。 这两种信息共享机制就相应地决定了两种算 法的表现，粒子群算法每代都选出当前最优个体， 并进行全局范围的信息共享，使得整个粒子群能向 着最优的方向快速趋近；而遗传算法的交叉操作具 有一定的随机性，且由于是一对一进行交叉，每一 次迭代中作用的范围相对较小，使得种群中的优秀 基因交流较慢，整个种群的进化比较漫长，所以 ＰＳＯ 特征选择寻优速度较快，效率更高。 通过信息交 互，在迭代过程中种群可以获得更为优秀的个体基 因型，这有助于加速 ＧＡ 种群的进化过程，提高收敛 速度。 同时，通过上文的比特率交叉算子可以避免 相近的基因型交叉产生不“健康” 的后代个体。 具 体的 ＧＡ⁃ＰＳＯ 协 同 演 化 算 法 如 算 法 ２ 和 算 法 ３ 所示。 算法 ２ 协同演化算法 输入 粒子群和种群初始化参数。 输出 最佳个体。 １）初始化粒子群和种群。 ２）协同演化。 ①计算各个粒子的适应度值。 ②选择粒子群算法最佳个体 ＰＳＯｂｅｓｔ。 ③选出遗传算法最佳个体 ＧＡｂｅｓｔ。 ④最佳个体比特信息位交换。 ⑤ＰＳＯ：更新粒子速度及位置。 ⑥ＧＡ： 选择、比特率交叉（算法 １）和变异。 ３）判断终止条件，若不满足返回 ２），满足进入 ４）。 ４）比较 ＧＡｂｅｓｔ与 ＰＳＯｂｅｓｔ，输出最佳个体。 第 １ 期 滕旭阳，等：面向特征选择问题的协同演化方法 ·２７·

·28 智能系统学报 第12卷 算法3最佳个体比特信息位交换 据的离散化处理采用经典的MDL方法。种群规模为 输入上一代最佳个体和本轮最佳个体。 20,迭代次数为300。GA中交叉概率为0.6，变异概率 输出交换比特信息位后的PSO及HSmo 为0.15；PS0中c1=c2=2,0=0.4。 1)随机选取PS0中引起最佳个体适应度值增 31算法分类准确率的结果分析 加的信息位PSOpito 本文实验部分选用了UCI(UC Irvine machine 2)随机选取GA中引起最佳个体适应度值增 learning repository)数据库中的5个高维多类别数据 加的信息位GAm。 集，特征维度从14维升至240维，不同数据集中样 3)if PSO=优于GAt, 本的类别数目最少为2类，最多为10类。其中， 将GAa中对应的信息位改为PSOm; Australian与Credit Approval为两个信用卡申请类数 else 据集，Dermatology为皮肤病数据集，Synthetic Control 将PSO中对应的信息位改为GA; 是名为合成控制图数据集，Multi-Feature Pixel是名 end 为Multi-feature“0”到“9”手写图数据集中的一个 本文提出的GA-PS0协同演化算法，通过协同 子集合。各数据集的详细信息如表1所示。 共享的思想让PSO和GA互相弥补各自的弱点，互 表1UCI数据集描述 相协助从而产生更强的个体。对于本文面向的特 Table 1 Descriptions of UCI benchmark datasets 征选择问题，更好的个体可以从两个角度进行判 数据集 特征数 样本数 类别数 Australian 14 690 2 断：特征与类别相关性越高，个体适应度值越高：特 Credit Approval 15 690 征子集规模越小，个体适应度值越高。面向特征选 Dermatology 34 366 6 择问题的协同演化方法执行流程如图3所示。 Synthetic Control 60 600 6 Multi-Feature Pixel 240 2000 10 开始 实验对比的特征选择算法有GA、PSO、IG以及 随机初始化粒子群 随机初始化种群 GR。为了验证算法性能，选取SVM、I-NN和Naive Bayes三个分类器，并且使用十折交叉验证的方法 计算各粒子适应度值 测试在不同数据集下各个算法所选择特征子集的 计算各个个体适应度值 分类。对于GA,PSO和GA-PS0三种进化搜索的方 更新个体极值及群体极值 法，实验得出每个算法连续运行20次时的平均分类 准确率。而IG(information gain)信息增益和GR 最佳个体比特信息位交换策略 (gain ratio)增益比率都是以互信息为基础的经典的 排序特征选择算法，因此在实验中分别对每个数据 更新粒子速度和位置 选择、交叉、变异 集的特征进行排序，并且手动地选择与进化算法规 模相近的排名前p个特征，P为选择的特征数量。 达到最大 具体的分类结果如表2~4所示。表2~4中数值表 迭代次数 示各特征选择算法选择的特征子集在相应的数据 TY 结束○ 集下使用分类器得到的分类准确率。Avg表示平均 图3协同演化算法的流程图 分类准确率，括号内数字为平均选择的子集规模。 Fig.3 Flow chart of co-evolution algorithm 从表2中可以看出，本文提出的方法在5个数 据集上均取得了最好的结果，比如在Synthetic 3实验结果与分析 Control数据集中，在选出相近的特征子集下，提出的 为了验证本文提出算法的有效性，实验结果从两 方法的平均分类准确率比其他算法的平均分类准 个方面进行分析：1)分析算法在不同数据集下分类的 确率高出了平均2.98%。同样如表3和表4所示， 准确率：2)提出的算法与GA和PSO进行适应度值和 在1-NN和Naive Bayes分类器中，对于每个数据集本 收敛性比较。本文实验特征选择部分的运行环境为 文提出的方法的平均分类准确率都比其他的算法 MATLAB2014a,分类准确率运行环境为weka3.8。对数 具有优势，在保证特征子集近似的情况下，能够得 到较好的分类效果

算法 ３ 最佳个体比特信息位交换 输入 上一代最佳个体和本轮最佳个体。 输出 交换比特信息位后的 ＰＳＯｂｅｓｔ及 ＨＳｂｅｓｔ。 １） 随机选取 ＰＳＯ 中引起最佳个体适应度值增 加的信息位 ＰＳＯｂｉｔ。 ２） 随机选取 ＧＡ 中引起最佳个体适应度值增 加的信息位 ＧＡｂｉｔ。 ３） ｉｆ ＰＳＯｂｅｓｔ优于 ＧＡｂｅｓｔ， 将 ＧＡｂｅｓｔ中对应的信息位改为 ＰＳＯｂｉｔ； ｅｌｓｅ 将 ＰＳＯｂｅｓｔ中对应的信息位改为 ＧＡｂｉｔ； ｅｎｄ 本文提出的 ＧＡ⁃ＰＳＯ 协同演化算法，通过协同 共享的思想让 ＰＳＯ 和 ＧＡ 互相弥补各自的弱点，互 相协助从而产生更强的个体。 对于本文面向的特 征选择问题，更好的个体可以从两个角度进行判 断：特征与类别相关性越高，个体适应度值越高；特 征子集规模越小，个体适应度值越高。 面向特征选 择问题的协同演化方法执行流程如图 ３ 所示。 图 ３ 协同演化算法的流程图 Ｆｉｇ．３ Ｆｌｏｗ ｃｈａｒｔ ｏｆ ｃｏ⁃ｅｖｏｌｕｔｉｏｎ ａｌｇｏｒｉｔｈｍ ３ 实验结果与分析 为了验证本文提出算法的有效性，实验结果从两 个方面进行分析：１）分析算法在不同数据集下分类的 准确率；２）提出的算法与 ＧＡ 和 ＰＳＯ 进行适应度值和 收敛性比较。 本文实验特征选择部分的运行环境为 ＭＡＴＬＡＢ ２０１４ａ，分类准确率运行环境为 ｗｅｋａ３．８。 对数 据的离散化处理采用经典的 ＭＤＬ 方法。 种群规模为 ２０，迭代次数为 ３００。 ＧＡ 中交叉概率为 ０．６，变异概率 为０．１５；ＰＳＯ 中 ｃ１ ＝ｃ２ ＝２，ｗ＝０．４。 ３．１ 算法分类准确率的结果分析 本文实验部分选用了 ＵＣＩ （ＵＣ Ｉｒｖｉｎｅ ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ ｒｅｐｏｓｉｔｏｒｙ）数据库中的 ５ 个高维多类别数据 集，特征维度从 １４ 维升至 ２４０ 维，不同数据集中样 本的类别数目最少为 ２ 类，最多为 １０ 类。 其中， Ａｕｓｔｒａｌｉａｎ 与 Ｃｒｅｄｉｔ Ａｐｐｒｏｖａｌ 为两个信用卡申请类数 据集，Ｄｅｒｍａｔｏｌｏｇｙ 为皮肤病数据集，Ｓｙｎｔｈｅｔｉｃ Ｃｏｎｔｒｏｌ 是名为合成控制图数据集，Ｍｕｌｔｉ⁃Ｆｅａｔｕｒｅ Ｐｉｘｅｌ 是名 为 Ｍｕｌｔｉ⁃ｆｅａｔｕｒｅ “０”到“９” 手写图数据集中的一个 子集合。 各数据集的详细信息如表 １ 所示。 表 １ ＵＣＩ 数据集描述 Ｔａｂｌｅ １ Ｄｅｓｃｒｉｐｔｉｏｎｓ ｏｆ ＵＣＩ ｂｅｎｃｈｍａｒｋ ｄａｔａｓｅｔｓ 数据集 特征数 样本数 类别数 Ａｕｓｔｒａｌｉａｎ １４ ６９０ ２ Ｃｒｅｄｉｔ Ａｐｐｒｏｖａｌ １５ ６９０ ２ Ｄｅｒｍａｔｏｌｏｇｙ ３４ ３６６ ６ Ｓｙｎｔｈｅｔｉｃ Ｃｏｎｔｒｏｌ ６０ ６００ ６ Ｍｕｌｔｉ⁃Ｆｅａｔｕｒｅ Ｐｉｘｅｌ ２４０ ２ ０００ １０ 实验对比的特征选择算法有 ＧＡ、ＰＳＯ、ＩＧ 以及 ＧＲ。 为了验证算法性能，选取 ＳＶＭ、１⁃ＮＮ 和 Ｎａïｖｅ Ｂａｙｅｓ 三个分类器，并且使用十折交叉验证的方法 测试在不同数据集下各个算法所选择特征子集的 分类。 对于 ＧＡ，ＰＳＯ 和 ＧＡ⁃ＰＳＯ 三种进化搜索的方 法，实验得出每个算法连续运行 ２０ 次时的平均分类 准确率。 而 ＩＧ （ ｉｎｆｏｒｍａｔｉｏｎ ｇａｉｎ） 信息增益和 ＧＲ （ｇａｉｎ ｒａｔｉｏ）增益比率都是以互信息为基础的经典的 排序特征选择算法，因此在实验中分别对每个数据 集的特征进行排序，并且手动地选择与进化算法规 模相近的排名前 ｐ 个特征，ｐ 为选择的特征数量。 具体的分类结果如表 ２ ～ ４ 所示。 表 ２ ～ ４ 中数值表 示各特征选择算法选择的特征子集在相应的数据 集下使用分类器得到的分类准确率。 Ａｖｇ 表示平均 分类准确率，括号内数字为平均选择的子集规模。 从表 ２ 中可以看出，本文提出的方法在 ５ 个数 据集上 均 取 得 了 最 好 的 结 果， 比 如 在 Ｓｙｎｔｈｅｔｉｃ Ｃｏｎｔｒｏｌ数据集中，在选出相近的特征子集下，提出的 方法的平均分类准确率比其他算法的平均分类准 确率高出了平均 ２．９８％。 同样如表 ３ 和表 ４ 所示， 在１⁃ＮＮ和 Ｎａïｖｅ Ｂａｙｅｓ 分类器中，对于每个数据集本 文提出的方法的平均分类准确率都比其他的算法 具有优势，在保证特征子集近似的情况下，能够得 到较好的分类效果。 ·２８· 智 能 系 统 学 报 第 １２ 卷