面向特征选择问题的协同演化方法

发布时间：2019-11-06 09:34

【摘要】：特征选择技术是机器学习和数据挖掘任务的关键预处理技术。传统贪婪式特征选择方法仅考虑本轮最佳特征,从而导致获取的特征子集仅为局部最优,无法获得最优或者近似最优的特征集合。进化搜索方式则有效地对特征空间进行搜索,然而不同的进化算法在搜索过程中存在自身的局限。本文吸取遗传算法(GA)和粒子群优化算法(PSO)的进化优势,以信息熵度量为评价,通过协同演化的方式获取最终特征子集。并提出适用于特征选择问题特有的比特率交叉算子和信息交换策略。实验结果显示,遗传算法和粒子群协同进化(GA-PSO)在进化搜索特征子集的能力和具体分类学习任务上都优于单独的演化搜索方式。进化搜索提供的组合判断能力优于贪婪式特征选择方法。
【图文】：

特征选择,视角,遗传算法,基本原理

以防止陷入局部最优，又提升了演化速度。1基础知识1．1特征选择数据集D中含有k个样本D={x1，x2，…，xk}，并且D中的每个样本都有特征集合F，F包含n维特征，xi∈Ｒn。对于分类问题，可将D中样本划分为目标向量C中的m个不同的类C={C1，C2，…，Cm}。特征选择的目的，是在原始特征集合N中寻找到一个最佳特征子集P，其中含有p维特征(p＜n)，，在该特征子集下能最大化分类任务(或其他学习任务)的预测正确率。特征选择处理包括4个组件:特征子集生成、子集评估、终止条件和结果验证。如图1所示，在阶段1中根据一个确定的搜索策略特征子集生成组件会预先产生候选特征子集。每一个候选特征子集都会被一个确定的评估方式所度量，并与之前最佳的候选特征子集做比较，如果新的特征子集表现得更加优越，那么替换原有的最佳特征子集。当满足设定的终止条件时，生成和评估这两个过程将不再循环。在阶段2中，最终所选的特征子集需要被一些给定的学习算法进行结果验证，其中ACC为学习正确率［3］。图1特征选择处理的统一视角Fig．1Aunifiedviewoffeatureselectionprocess1．2遗传算法基本原理遗传算法作为一种自适应全局优化搜索算法，其选择、交叉与变异的3个算子成为种群寻优和保持解多样性的关键。其基本执行过程如下。1)初始化:确定种群规模N、交叉概率Pcross、变异概率Pmutation和终止进化准则。2)个体评价:计算每个个体的适应度。3)种群进化:①选择算子:个体被选中的概率与其适应度函数值成正比。②交叉算子:根据交叉概率Pcross对2条染色体交换部分基因，构造下一代新的染色体。③变异算子:根据概率Pmutation对群体中的不同个体指定的基因位进行改造。④终止检验:如已?

粒子群,编码方式

，利用该函数将连续的速度值转化为离散的位置。在最初的研究中使用式(3)中的sigmoid函数作为转换函数将实值的速度映射为［0，1］之间的值。Tvkh((t))=11+e－vkh(t)(3)式中:vkh(t)为粒子h在第t轮迭代中第k维的速度。在将粒子速度转换为概率值后，位置向量将依据概率值进行更新:xkh(t+1)=0，rand＜Tvkh((t+1))1，rand≥Tvkh((t+1)){(4)2求解特征子集的协同演化方法2．1编码方式本文使用了二进制比特串的编码方式，该编码方式通用于遗传算法和二元粒子群方法，如图2所示。将每个二进制串作为一个个体(粒子)，个体(粒子)中的每一维(每一比特)都代表一个候选特征，当该位为1时表示该特征被选中，并添加到候选的特征子集中;当该位为0时表示该特征未被选中。依据此编码方式将特征选择问题转换为寻找最佳个体(粒子)的问题。图2二元粒子群的编码方式Fig．2CodingschemeofBPSO2．2适应度函数本文使用互信息熵理论对特征子集进行整体评估，两个变量的互信息值越大，则意味着两个变量相关程度越紧密;当互信息为零时，则意味着两个变量完全不相关。特征集合F={f1，f2，…，fn}中某一特征fi与类别的互信息度量如下:I(fi，C)=H(fi)+H(C)－H(fi，C)(5)式中:H为变量的熵值，用以度量随机变量信息的不确定性。以类别向量为例，H(C)通常用作描述离散随机变量C={c1，c2，…，cn}熵值，ci是变量C的可能取值，p(ci)为概率密度函数。H(C)=－∑mi=1p(ci)log(p(ci))(6)当已知特征变量和类别变量fi和C的联合概率密度时(对于离散数据意味着两个变量对应的属性值联合出现的频度)，两者的联合熵为Hfi(，C)=－∑

【相似文献】