特征选择在机器学习、数据挖掘和模式识别等领域中有着重要的应用.由于数据收集技术的不断完善, 一些专业领域中数据量不断积累, 导致在机器学习和数据挖掘中要处理的数据特征总数变大.在这些特征中, 选取能够描述目标概念的特征子集就尤为重要.特征选择就是从原始特征集合中选取有效的特征子集来减少数据特征维数的过程^[1].因此, 特征选择自然就成为了机器学习和数据挖掘领域中一个重要的数据预处理手段^[2].

特征选择算法有很多种, 总的来讲可以分为3类:过滤式方法、包裹式方法以及嵌入式方法^{[3, 4]}.过滤式方法不依赖于其他学习算法, 首先将数据特征按照一定的标准进行排序, 然后选择那些表现比较好的特征, 由于这种方式具有很高的计算效率^[1], 因此普遍被用来处理一些高维数据; 包裹式方法通过引入一个学习算法来评估所选的特征子集^[5], 因为直接对目标进行优化, 所以包裹式方法具有更好的性能; 嵌入式方法试图将特征选择和分类器学习整合在同一个过程中, 从而综合了包裹式方法和过滤式方法的优点.

特征选择在分类任务中是NP-hard的, 由于搜索空间会随着特征个数的增加呈指数级增长.对于包含n个特征的实例, 其搜索空间就会有2ⁿ个可能的结果^{[4, 6]}.关于特征选择的方法已经进行了许多工作, 根据产生特征子集所采用搜索策略的不同, 特征选择方法可以分为穷举法、启发法和随机法.

穷举法试图枚举搜索空间中的解来寻找一个能够正确区分所有类别的最小特征集合.当数据特征个数较多时, 评价所有特征子集在计算上是不可行的, 因此在包含大量特征的数据集中, 穷举法很少用于特征选择.

启发式特征选择算法主要包括贪婪爬山算法^[7]、分支限界法、定向搜索以及最佳优先算法.SFS(sequential forward selection)和SBS(sequential backward selection)是两种经典的爬山算法, 但这两种方法容易陷入局部最优解.为克服这一缺点, SFFS算法、SBFS算法被提出^[8].另外, 基于支持向量机并应用启发式搜索策略的特征选择方法是近年发展起来的通用方法, 它本身是一种有监督学习算法.Moustakidis等人提出了一种新的基于模糊互补准则的支持向量机特征选择方法SVM-FuzCoC^[9].

随机法的主要优点是具有可接受的时间复杂性, 特别是一些自然启发式算法, 由于其出色的全局搜索能力在特征选择问题中引起了大量的关注^[10].具体的, Zhu等人将遗传算法和局部搜索方法结合起来, 提出了FS- NEIR算法^[11].同年, Xue等人提出了基于粒子群优化的特征选择算法PSO^[12].Tabakhi等人提出了基于蚁群优化的无监督特征选择算法UFSACO^[13].近年来, 关于演化算法在特征选择问题中的应用也有很多, 例如Ghaemi等人提出的基于森林优化算法的特征选择方法FSFOA^[14]、Zhang等人基于萤火虫算法提出的Rc-BBFA^[15]、Marwa等人提出的混合过滤和包裹方法的多目标演化特征选择算法FW-NSGA-II^[16]、Hancer等人基于差分进化提出的特征选择方法DE-FLS^[17]、Chen等人基于细菌觅食算法提出ISEDBFO^[18]及ACBFO^[18]、Qian等人基于进化帕累托优化提出的POSS算法^[19].之后, Qian等人又提出了基于帕累托优化的无监督特征选择算法POCSS^[20].POCSS采用随机迭代过程来最小化重建误差和所选择的特征数量.此外, 基于多种群的协同演化算法也被用于处理特征选择问题, 例如J.Derrac等人提出的基于协同进化算法的特征选择方法IFS-CoCo^[21]等.

相比于传统的特征选择方法, 基于演化计算方法的明显优势在于其通常不需要领域内的相关知识和对搜索空间做任何的假设, 并且由于它基于种群机制, 能够在一次运行中产生多种结果, 使其更适合用来进行多目标特征选择, 以确保在特征数量和分类性能中取得平衡.因此, 将演化计算引入特征选择取得了不错的效果.尽管如此, 目前演化计算方法仍存在一些不足之处.

●  首先, 演化计算过程中随机性较高, 算法每次运行产生的结果不能够保证, 并且算法在迭代中不能够准确地控制种群的搜索范围和强度, 这使得算法的鲁棒性不足;

●  其次, 演化计算方法是通过个体在搜索空间进行探索来寻求最优解, 当搜索空间比较大时, 算法容易陷入局部最优解, 这导致演化计算方法对于高维数据的处理能力不足.

因此, 特征选择算法上仍存在较多可改进和完善之处, 特别是在处理高维数据的特征选择问题上.

作为进化算法的一种, 进化策略(ES)^{[22, 23]}在一些强化学习任务中的成功案例证明了进化策略能够有效适用于评价学习^[24].评价学习不同于监督学习和非监督学习, 算法通常需要从一些离散的、有噪音的、延迟的标量信息中学习.作为强化学习中一种重要的学习算法, 策略迭代通常会使用神经网络作为决策机制^[25], 并使用误差反向传播来优化策略函数.文献[24]中替代了策略迭代中误差反向传播优化参数的方式, 直接使用进化策略对决策网络进行优化, 最后达到了预期的目标效果.

包裹式的特征选择方法首先选取特征子集, 然后使用学习算法对其进行评估, 因此, 特征选择也可以看作是一种评价学习.受此启发, 本文使用ES作为全局搜索算法进行特征选择, 之后的工作证明了ES能够完成特征选择任务, 同时, 与其他的特征选择方法相比也有一定的竞争力, 并且能够有效地以分布式的方式进行多种群竞争进化^[26].

本文算法的具体实现过程为:在自然进化策略的基础上, 通过采用一种新的编码方式使其能够适应于特征选择问题; 然后, 结合模型分类准确率和特征维度缩减设计了一种新的适应度函数; 同时, 基于新的适应度函数提出一种适应度塑造方法用于构造目标优化函数; 之后, 为了有效处理高维数据, 在算法模型中引入亚种群合作协同进化的思想; 更进一步, 以多种群分布式竞争进化的方式加速算法的收敛, 并设计种群重启策略来防止种群陷入局部最优解; 最后, 使用GPU-Tensorflow作为算法运行框架实现多种群分布式进化.我们将提出的算法记为MCC-NES(multi-group cooperative coevolution feature selection algorithm based on natural evolution strategy).同时, 我们将本文提出的算法与近几年提出的其他比较高效的特征选择算法在16个UCI^[27]的数据集中进行了对比实验, 验证了我们算法的有效性和优越性, 尤其是在处理一些高维数据时有出色的表现.具体体现在:

首先, 本文的方法可以高度并行化, 通过引入特定的通信机制, 可以使得多个工作线程在运行时并行加速; 其次, 本文提出的方法表现出一种很好的探索能力, 因为在已知均值和方差的情况下, 正态分布是一种信息熵最大、最不稳定的分布, 算法在迭代中, 通过正态分布生成搜索点能够保证算法对于搜索空间进行有效的探索; 最后, 本文的方法有很好的鲁棒性, 算法能够根据搜索情况自适应改变分布均值和方差来调整搜索的强度和范围.

1 相关工作 1.1 特征选择问题

特征选择问题可以描述为:用S表示K个样本D个特征的数据集, F为D个特征的集合.特征选择任务就是从集合F中选取d个特征, 其中, d < =D, 使得目标函数f(·)取最大值, 这里的目标函数一般表示为模型分类准确率.也就是说, 特征选择的目的是通过选取最少特征数的特征子集X(X∈F)来使目标函数最大化.

我们采用如下二进制编码方式来表示选取的特征子集:

$ {X_i} = (x_1^i, ..., x_D^i), x_j^i \in \{ 0, 1\} $

(1)

其中, $x_j^i = 1$表示第i个特征子集X_i中第j个特征被选取; 相应的, $x_j^i = 0$表示这个特征不会被选取.那么, 特征选择问题就可以表示成如下的优化问题^[15]:

$ \left\{ {\begin{array}{*{20}{l}} {\max f(X)}\\ {{\rm{s}}{\rm{.}}\;{\rm{t}}{\rm{. }}{X_i} = (x_1^i, ..., x_D^i), x_j^i \in \{ 0, 1\} , j = 1, 2, ..., D}\\ {1 \le |X| \le D} \end{array}} \right. $

(2)

其中, |X|表示在特征子集X中所选取的特征数量.

1.2 进化策略

进化策略是一种黑盒优化算法, 首次由Ingo等人提出^{[28, 29]}, 并被设计用来处理高维连续性优化问题.如文献[30]所述, ES是自然启发优化算法的一种, 那么ES中同样包含基因突变、重组以及选取候选解的过程, 并以迭代的方式进化越来越好的解.进化策略中包含一个用于评估种群个体基因序列的适应度函数, 每次选取候选解的时候, 最好的个体将会被保留, 其他的个体直接舍去.然后, 在保留下来的个体中, 通过扰动基因序列来生成下一代的个体, 整个过程通过迭代就会找到较优的结果.

其中, 公式(3)为给定优化问题的一般形式, 那么进化策略可以应用于优化问题的所有领域, 包括无约束和有约束以及混合约束的搜索空间Y中:

$ {y^*} = {\rm{argop}}{t_y}_{ \in Y}f\left( y \right) $

(3)

进化策略又有两种候选解选取策略:(μ, λ)-ES和(μ+λ)-ES.这两种策略的不同之处在于:前者每次迭代产生λ个新解, 选择较好的μ个成为下一次迭代的父代(μ≤λ), 其他的直接舍去, 其中, 每个个体只存活一代, 随即被新的个体代替; 而后者每次迭代产生λ个新解, 通过和父代中的个体进行比较, 选择较好的μ个成为下一次迭代的父代, 其他的直接舍去.本文采用第一种候选解选取策略, 因为前者能够更有效地对搜索空间进行探索而不容易陷入局部最优.ES中每个个体x的一般形式为

$ {\rm{ES}}\;{\rm{individual}}\;x: = (y, \theta , F\left( y \right)) $

(4)

其中, y∈Y表示需要优化的目标序列; θ表示策略参数, 并且θ中相关参数在ES算法中会自适应的进行调整; F(·)为目标函数.使用这种表述形式, 特征选择问题(2)也可以看作是进化策略的一种优化问题进行求解.

1.3 进化策略的框架

近年来, 进化策略的框架已被广泛开发, 包括使用完全协方差矩阵作为分布模型表示相关突变, 这使得算法框架在变异生成下一代个体时能够利用属性之间的协方差关系来捕获它们的相关性, 因此, 突变可以自适应局部搜索情况, 并且可以显著增加向最优解的收敛性能.协方差矩阵自适应进化策略(CMA-ES)^[31]已在多项研究中证明是成功的^[32-34].

我们的工作是基于自然进化策略(NES)^{[35, 36]}展开的, NES也是进化策略在框架上的一种扩展.NES通过使用样本的估计梯度来迭代地更新搜索分布.算法过程如下:搜索分布采样用于生成一批搜索点(即每代种群), 然后根据适应度函数评估每一个搜索点(种群中的每个个体), 之后计算搜索点的搜索梯度并使用梯度上升的方法, 通过最大化种群适应度均值来自适应地调整模型中相关的参数.

NES的核心就是使用搜索梯度^{[37, 38]}来更新搜索分布中的参数.我们将搜索梯度定义为样本预期适应度的梯度, 其中, 搜索分布采用多元正态分布.如果用π(x|θ)表示参数为θ的分布策略, 用f(·)表示的样本适应度函数, 我们可以将搜索分布下的预期适应度表示如下:

$ J(\theta ) = {E_\theta }[f(x)] = \int {f(x)\pi (x|\theta ){\rm{d}}x} $

(5)

然后对公式(5)求导, 并采用对数似然表示:

$ {\nabla _\theta }J(\theta ) = {E_\theta }\left[ {f\left( x \right)} \right]{\nabla _\theta } \rm{log}\pi (x|\theta ) $

(6)

使用公式(6), 我们可以从种群个体(x₁, x₂, …, x_λ)得到搜索梯度的估计值:

$ {\nabla _\theta }J(\theta ) \approx \frac{1}{\lambda }\sum\limits_{i = 1}^\lambda {f({x_i}){\nabla _\theta }\ \rm{log} \pi ({x_i}|\theta )} $

(7)

公式(7)中, λ表示种群的大小, 样本预期梯度在搜索分布空间中提供搜索方向, 采用梯度上升来迭代更新搜索分布:

$ \theta \leftarrow \theta + \eta {\nabla _\theta }J(\theta ) $

(8)

公式(8)中, η表示学习率.算法1表示在搜索分布上使用搜索梯度.

算法1. Search-gradient-algorithm.

Initialize parent population $p_\mu ^0 = \{ {x_1}, ..., {x_\mu }\} $

Initialize distribution parameters θ⁽⁰⁾, fitness function f(·)

Repeat

  For generation g=1, 2, …, τ do

    Sample λ independent points from distribution p(x|θ^(g))→x₁, …, x_λ

    Evaluate the sample (x₁, …, x_λ) on f(·)

    Calculate log-derivatives ${\nabla _\theta } \rm{log} \pi (x|\theta )$

End for

$ \begin{array}{l} {\nabla _\theta }J(\theta ) \leftarrow \frac{1}{\lambda }\sum\nolimits_{g = 1}^\lambda {f({x_g}){\nabla _\theta }\log \;\pi ({x_g}|\theta )} \\ F \leftarrow \frac{1}{\lambda }\sum\nolimits_{g = 1}^\lambda {{\nabla _\theta }\log \;\pi ({x_g}|\theta ){\nabla _\theta }\log \;\pi {{({x_\theta }|\theta )}^T}} \end{array} $

$\theta \leftarrow \theta + \eta {F^{ - 1}}{\nabla _\theta }J(\theta )$

Until termination criterion met

NES将普通随机梯度替换为自然梯度, 自然梯度首先被Amari引入机器学习领域, 并且已被证明自然梯度比普通梯度更有优势^{[39, 40]}.自然梯度能够加速梯度在平原地区的收敛速率, 并减缓梯度在高原地区的收敛速率.

2 MCC-NES

ES能够有效地进行评价学习, 并且具有良好的全局搜索能力和并行化能力.进一步地, NES可以通过使用样本梯度信息来更新参数.由于NES需要处理梯度, 我们使用GPU-Tensorflow作为NES运行框架, 同时引入一些优化策略, 提出了一种新的特征选择算法(MCC-NES).之后, 通过实验验证MCC-NES算法在特征选择问题中的性能.实验结果表明:MCC-NES算法能够有效地完成特征选择问题, 而且在处理高维数据时有着出色的表现.

2.1 MCC-NES算法建模及特征编码

结合前文分析, 本文的工作采用了基于协方差矩阵建模的自然进化策略.分布模型中的参数包括分布均值向量m和分布协方差矩阵C, 其中, |m|=rank(C)表示数据集中特征的个数.当特征个数较小时, 对完全协方差矩阵建模是非常有益的.但是面对高维数据时, 使用完全协方差矩阵复杂度就会很高.因为协方差矩阵的大小和数据特征维数相关, 对于n维数据来说, 完全协方差矩阵中元素的个数就会有n²个.当n取值增大时, 其计算复杂度就会呈指数级增长.因此, 为了有效处理高维数据, 我们选择保留矩阵主要信息, 只关心每个特征的发散性而不去考虑特征之间的相关性, 使用对角协方差矩阵代替完全协方差矩阵进行建模, 从而降低算法时间复杂度.

在算法的初始化阶段, 通过在超参数α上重复添加高斯扰动(扰动强度σ=0.01)来初始化分布均值向量m, 对于分布协方差矩阵C, 选择使用单位矩阵进行初始化, 使得算法模型中每个特征对应于分布均值向量m中的一个元素和分布协方差矩阵C中的一个对角元素.在算法迭代时, 将向量m中的每个元素与矩阵C中对应的对角元素作为正态分布的参数做高斯采样, 生成关于每个特征的分布取值, 然后, 将得到的数值结果通过使用一种新的编码方式映射到布尔型的特征选择上, 具体的特征编码方式如下:

$ x_i^g = \left\{ {\begin{array}{*{20}{l}} {1, {\rm{ }}\frac{1}{{1 + {e^{ - y_i^g * 2}}}} > 0.5}\\ {0, {\rm{ otherwise}}} \end{array}} \right. $

(9)

ES算法一般用于解决连续型优化问题, 为了处理特征选择问题, 文中使用公式(9)将特征高斯采样的结果映射到{0, 1}序列中, 其中, $y_i^g$表示在第g次迭代中第i个特征的高斯采样结果.使用公式(9)进行特征映射, 如图 1所示.若映射后的结果大于0.5, 就选取该特征(用二进制1表示选取该特征); 否则的话, 就不进行选择(用二进制0来表示不选取该特征).

通过这种编码方式, 我们希望在迭代过程中对于那些已经确定的特征尽量使其保持稳定(在图 1中表现为两端较为平缓的部分), 而对于不确定的特征提供更多的探索(在图 1中表现为中间部分的曲线, 有较高的斜率, 对于梯度信息更为敏感).

2.2 新的适应度函数及适应度塑造方法

在计算样本适应度时, 传统的适应度函数具有潜在的局限性.一般而言, 大多数算法中对于样本的评估都是基于测试集的分类准确率的, 也就是说, 每一次更新都会选取表现最好的一些特征序列, 因此就会忽略维度缩减的重要性.但是有时候在处理一些高维数据的时候, 能够选择更少的特征也是具有实际应用价值的, 所以本文就传统适应度函数的弊端提出了一个新的适应度函数, 将特征缩减也加入特征选取的考虑范围.

新的适应度函数如公式(10)所示:

$ \left\{ {\begin{array}{*{20}{l}} {f({x_i}) = \rho \cdot CA + (1 - \rho ) \cdot DR}\\ {\rho = \frac{{9 + 0.99\left( {\frac{\varphi }{{100}}} \right)}}{{10}}\;\;\;\;\;\;\;\;\;\;\;\;\;} \end{array}} \right. $

(10)

φ表示数据特征维数; 关于参数ρ的取值与数据特征个数相关, 其函数图像由图 2给出; 式中CA和DR为分类准确率和维度缩减率(CA和DR的定义在第3.1中进行详细说明).

如图 2所示:当数据特征维数较小时, ρ的取值接近于1, 适应度函数的考察主要以分类准确率为主; 而随着特征维数增加, ρ取值减小, 直至接近0.9, 维度缩减的重要性也随之提高.因此在新的适应度函数下, 算法既考虑了模型的分类准确性, 也考虑了特征维度缩减, 但是分类准确率依然是最主要的.

进一步地, 为了防止一些异常的适应度值导致不准确的梯度信息而增加算法陷入局部最优解的可能, 我们使用了一种适应度塑造的方法, 如公式(11)所示, 将样本的真实适应度f(x_i)依据排名映射到一个均匀分布的离散空间中作为样本的有效适应度u(x_i)来求解梯度, 这使得梯度信息不依赖于具体的适应度值.同时, 我们提出了一种自适应调整分布空间的方式, 就是在每次迭代中, 根据样本中最优的适应度值与最差的适应度值之间的差距来调整分布空间的取值范围, 这使得当种群中个体表现差异比较大的时候, 能够增加参数调整的幅度; 而当种群中个体表现相似时, 减小参数调整的步长:

$ \left\{ {\begin{array}{*{20}{l}} {u(x{}_i) = u({x_1}) + (i - 1)\delta }\\ {\delta = \frac{{f({x_\lambda }) - f({x_1})}}{{\lambda - 1}}}\\ {u({x_1}) = - \frac{{f({x_\lambda }) - f({x_1})}}{2}} \end{array}} \right., f({x_{1:\lambda }}) \le ... \le f({x_{\lambda :\lambda }}) $

(11)

2.3 种群内的亚种群合作协同进化

我们使用ES算法解决特征选择问题最直接的想法就是基于数据集中所有的特征进行建模, 但是这种建模方式在处理一些高维数据时就会显现出弊端(因为搜索空间随数据维度呈指数级增长, 由于计算资源的限制无法完成矩阵建模).因此, 我们在算法中引入了亚种群合作协同进化的思想^[41].合作协同进化通过将原始特征集划分成相对较小的子特征集, 然后在每个子特征集中独立应用进化策略进行局部搜索, 子特征集完成搜索后, 将通过合作协同进化来组合优化原特征选择问题的解决方案.

具体的, 首先对数据集D按照特征随机划分成若干组A={A₁, …, A_n}, 各组包含的特征相互独立且唯一, 然后初始化n个对角协方差矩阵C={C₁, …, C_n}、n个分布均值向量M={m₁, …, m_n}以及n个亚种群S={S₁, …, S_n}, 并使每个亚种群S_i对应一个子特征子集A_i、一个均值向量m_i以及一个对角协方差矩阵C_i(|A_i|=|S_i|=|m_i|=rank(C_i)).初始化完成之后, 让n个亚种群同步进行迭代更新.由于每个亚种群只维护一个子特征集的信息, 而原特征选择问题需要在原始特征集合中进行全局搜索, 因此需要在每次迭代中, 在n个亚种群间进行信息交互.具体的, 每次迭代时, 每个亚种群随机产生m个搜索点, 对于n个亚种群来讲, 就会有mⁿ个子特征序列的组合, 如果完整评估所有特征序列的组合, 当n和m增大时, 很容易陷入组合爆炸.不失一般性, 我们保留一定的历史信息, 在组合的过程中, 我们保留种群历史表现最好的全局特征序列, 每个亚种群的搜索就可以看成是对当前全局最优特征序列的一次局部探索, 每个亚种群产生的搜索点只改变当前亚种群在全局最优特征序列中所对应的这一部分特征, 同时对局部改动的全局最优特征序列进行评估, 作为对当前亚种群采样的评估.如此, 通过保留历史最优全局特征序列, 就会极大地降低算法搜索复杂度O(m*n).进一步地, 为了防止搜索过程中陷入局部最优解的情况, 每次迭代时选择保留表现排名前三的全局特征序列和一个随机产生的全局特征序列.这里, 随机特征序列的产生是由当前全局最优特征序列决定的, 根据当前全局最优特征序列中特征的个数, 随机地在原始特征集合中选取相同数量的特征构成随机特征序列, 然后, 每次迭代时, 每个亚种群同时在这4个特征序列上进行局部搜索.以上过程是在一个种群中, 通过亚种群协同进化的方式来实现种群优化的完整过程.

协同进化是一种进化算法, 算法一般通过种群间相互激励来提升种群各自的性能.如在IFS-CoCo^[21]算法中, 通过特征选择与实例选取协同进化来提升分类器准确率.我们所采用的方式与一般的协同进化方法不同:它类似于分治法的思想, 将原始集合划分为多个分组, 通过分组与原始集合间协同进化来指导搜索.具体, 算法在迭代过程中, 每个分组采用ES算法进行搜索, 在分组进化过程中, 我们会保留历史前三全局最优序列, 同时使用一个全局随机序列, 每个分组在进化过程中都会和这4个全局序列进行交互, 并更新全局最优序列.通过这种方式, 一方面为了防止算法陷入局部最优解, 同时解决分组间组合爆炸的问题.

2.4 多种群间竞争进化及种群重启策略

第2、3节详细描述了一个种群使用合作协同进化解决特征选择问题的完整过程, 进一步的, 我们通过分布式操作将这个过程扩展到多个种群实现多种群竞争进化.同时, 为了防止种群陷入局部最优解, 提出了一种种群重启策略:

因为在算法初始阶段种群采用随机初始化, 所以一个种群在迭代中的收敛速率和性能都很依赖于种群在搜索空间中的初始化位置.引入一种种群重启机制, 当一个种群的整体性能表现不好或者当种群性能上升停滞时, 就会采取相应的重启策略, 包括重新初始化该种群的分布协方差矩阵C, 并将其分布均值m向最优种群的分布均值转移.算法采用这种重启机制来使种群跳出局部最优解, 不断将表现差的种群向表现好的种群方向转移, 并使其在当前最优解附近进行新的探索.之后的实验中也验证了这种方式的有效性.

种群性能评价函数定义为

$ F(p_i^g) = (1 - \beta )\nabla f(p_i^g) + \beta F(p_i^{g - 1}) $

(12)

其中, $\nabla f(p_i^g)$表示种群p_i在第g次迭代时的适应度变化量(使用当前样本适应度均值和上一代样本适应度均值之差表示), β为超参数表示历史信息的利用率.这种设定是为了综合考虑种群的历史累积表现.同时, 种群重启概率设计如下:

$ \left\{ {\begin{array}{*{20}{l}} {{\rm{True}}, {\rm{ }}0.01 + 0.99 \cdot \frac{{{{\rm{e}}^{10 \cdot \frac{{\tilde g}}{\varpi } - 1}}}}{{{{\rm{e}}^{10}} - 1}} > rand}\\ {{\rm{false}}, {\rm{ otherwise}}} \end{array}} \right. $

(13)

其中, $\tilde g$表示当前迭代次数与上一次策略重启时迭代次数之差; ϖ是一个超参数, 当种群p_i使用公式(13)返回为True并且其性能$F(p_i^g)$在所有种群中最小时, 种群p_i就会进行重启, 并将$\tilde g$重置为0.

公式(13)的概率曲线如图 3所示.

由于使用多种群竞争进化提供了更多的探索性, 所以极大地提升了算法的探索能力, 之后的实验中也验证了这一观点.

2.5 MCC-NES算法伪代码

基于以上分析, MCC-NES的伪代码在算法2中给出.其中:第1行~第3行是关于算法参数、适应度函数以及适应度塑造方法的初始化过程; 第5行完成每个种群中的3个最优全局特征序列和1个随机全局特征序列的初始化工作; 第6行是将原始特征集合根据设定的大小进行划分; 第7行~第9行初始化每个种群中每个亚种群的分布参数; 第12行开始算法的迭代过程; 第14行~第37行表示每个种群的进化过程, 具体的, 第15行~第36行是每个亚种群的进化操作, 其中包括分布采样(第16行、第17行)、生成种群随机特征序列(第18行)、评估每个样本适应度(第19行~第31行)、实现亚种群的更新操作, 使用样本的搜索梯度来更新分布参数(第32行~第35行).第38行~41行检测是否有种群满足重启条件, 如果存在满足条件的种群, 就对该种群进行重启操作.

算法2. MCC-NES.

1:  Input: The number of population σ, the size of subpopulation m, the number of individuals

insubpopulation λ, the number of iterations τ, the Initialization parameters α, restart threshold ϖ, historical utilization β;

2:  Initialize: fitnessfunction f(·) as equation 10, fitnessfunction u(·) as equation11, set $\tilde g$ to 0

3:  Initialize: the number of population genes φ

4:  For population p=1, 2, …, σ do

5:  Initialize population feature sequence with zero $\xi _p^1, \xi _p^2, \xi _p^3, \xi _p^4$

6:  Randomly divide the population gene into m Subpopulation

7:  For subpopulation s=1, 2, …, m do

8:  Initialize distribution parameters $\theta _{p, s}^{(0)}$

9:  End for

10: End for

11: Repeat

12: For generation g=1, 2, …, τ do

13: $\tilde g \leftarrow \tilde g + 1$

14:   For population p=1, 2, …, σ do

15:     For each subpopulation s=1, 2, …, m do

16:       Sample λ individual from distribution $p(x|\theta _{p, s}^{(g)}) \to {x_1}, ..., {x_\lambda }$

17: Feature selection for generated individuals according to Eq.9

18: Generating random sequences $\xi _p^4$ according $\xi _p^3$

19: For each individual μ=1, 2, …, λ do

20:       Local exploration on four feature sequences $\xi _p^1, \xi _p^2, \xi _p^3, \xi _p^4$ to generates four new feature sequences $\tilde \xi _p^1, \tilde \xi _p^2, \tilde \xi _p^3, \tilde \xi _p^4$

21: Evaluate four new feature sequences $\tilde \xi _p^1, \tilde \xi _p^2, \tilde \xi _p^3, \tilde \xi _p^4$ using fitness function f(·)

22:       Choose best fitness value on four feature sequences as individual fitness

23: For each new feature sequences $\tilde \xi _p^i(1 \le i \le 4)$ do

24: If $f(\tilde \xi _p^i) > f(\xi _p^3)$ do

25: $\xi _p^1 \leftarrow \xi _p^2, \;\xi _p^2 \leftarrow \xi _p^3, \;\xi _p^3 \leftarrow \tilde \xi _p^i$

26: Else If $f(\tilde \xi _p^i) > f(\xi _p^2)$ do

27: $\xi _p^1 \leftarrow \xi _p^2, \;\xi _p^2 \leftarrow \tilde \xi _p^i$

28:       Else if $f(\tilde \xi _p^i) > f(\xi _p^1)$ do

29: $\xi _p^1 \leftarrow \tilde \xi _p^i$

30: End for

31:   End for

32:     Fitness shaping for each individual fitness value using function u(·)

33:     Calculate log-derivatives ${\nabla _\theta }{\rm{log}}\pi (x|\theta )$

34: ${\nabla _\theta }J(\theta ) \leftarrow \frac{1}{\lambda }\sum\nolimits_{g = 1}^\lambda {u({x_g}){\nabla _\theta }\log \pi ({x_g}|\theta )} $

35:     Update distribution parameters using Adam

36:   End for

37: End for

38:   Evaluate all populations performance F(p_i)(i=1, 2, …, σ) by Equ.12

39:   IF Eq.13 returns true and F(p_i) has the worst overall performance do

40:     Reset the exploration ability of p_i, Transfer the distribution of p_i to the optimal population and reset $\tilde g$ to 0

41:    End If

42: End for

43: Until termination criterion met

3 实验结果与分析

在实验中, 我们使用公开的机器学习工具包scikit-learn.编程语言为python.实验电脑的配置是Intel Core i7 CPU(3.60GHz), 8G内存; 使用显卡为NVIDIA GeForce GTX 1050.

3.1 数据集

我们在16个UCI公开数据集上对MCC-NES算法的性能予以测试, 涵盖了6个小维数据集(Glass, Heart, Cleveland, Wine, Vehicle, Segmentatin)、2个中维数据集(Ionosphere, Dermatology)和8个高维数据集(Spambase, Sonar, Musk2, LSVT, SRBCT, Arcene, RNA-Seq, Dorothea).根据文献[42], 如果数据集中的特征数量是[0, 19], [20, 49], [50, ∞], 那么对应数据集的规模分别是小维数据集、中维数据集、高维数据集.关于数据集的具体信息由表 1给出.

根据对比算法, 我们对每个数据集的划分采用70%作为训练集30%作为测试集、10-折交叉验证、2-折交叉验证这3种方式.测试集的分类准确率CA(classification accuracy)和维度缩减能力DR(dimensionality reduction)作为MCC-NES算法及对比算法的评价准则.分类准确率的具体定义如公式(14), 其中, N_CC(number of correct classification)是正确分类的实例数, N_AS(number of all samples)是数据集实例总数; 维度缩减率的定义如公式(15), 其中, N_SF(number of selected features)是被选择的特征数, N_AF(number of all features)是数据集的特征总数:

$ CA = N\_CC/N\_AS $

(14)

$ DR = 1 - \left( {N\_SF/N\_AF} \right) $

(15)

3.2 对比算法和参数设置

将提出的MCC-NES算法与其他的经典算法进行比较, 这些算法的具体信息由表 2给出.

用于对比的特征选择算法有:Ghaemi等人利用分类器准确率作为评估标准提出的FSFOA^[14]、Hu等人基于邻居软间隔评估特征子集而提出的NSM^[43]、Moustakidis等人提出的SVM-FuzCoc^[9]、Huang等人提出的FS混合基因算法(HGAFS)^[44]、Zhu等人利用邻居有效信息率评价准则提出的FS-NEIR^[11]、Tabakhi等人基于特征之间的相似性评估准则提出的UFSACO^[13]、Xue等人提出的将分类器准确率和特征子集规划作为评价准则的PSO(4-2)^[12]、Zhang等人基于成本收益萤火虫算法提出的Rc-BBFA^[15]、J. Derrac等人基于协同进化算法提出的IFS-CoCo^[21]、贪婪爬山算法SFFS^[8]、Khan A等人基于mRMR增强的蚁群多目标特征选择算法ACOFSS+mRMR^[45]、Marwa等人提出的混合过滤和包裹方法的多目标演化特征选择算法FW-NSGA-II^[16]、Hancer等人基于差分进化提出的特征选择方法DE-FLS^[17]、Chen等人基于细菌觅食算法提出ISEDBFO^[18]及ACBFO^[18]等.

实验中, MCC-NES算法相关的参数设定由表 3给出^[46].其中, 在处理不同维度数据集时, 设定了不同的种群个数、子种群的大小以及子种群中个体的数量等.其原因是:随着数据维数的增加, 出于计算资源的限制, 相应减少种群个数以及子种群中个体的数量; 而增加子种群的个数是为了让每个种群能够尽可能多地探索局部搜索空间, 以此避免种群过早陷入局部最优解.同时, 随着特征维数的增加, 我们不断减小种群初始化参数, 使得种群在高维数据上能够发掘出更关键的特征信息.最后, 通过给高维数据设定更高的重启阈值和迭代次数, 以此让种群在高维搜索空间中进行更充分的探索.

3.3 算法迭代过程

关于算法的迭代过程, 我们选取了两个比较有代表性的数据集Sonar和Ionosphere, 图 4表示MCC-NES算法在Sonar以及Ionosphere数据集上采用5-NN分类器时的迭代搜索过程.拿Sonar数据集为例, 算法在开始阶段, 分类器有最低的分类性能以及最高的维度缩减, 这是由于算法开始迭代时最优全局特征序列为空, 每个亚种群不会与全局特征序列进行联系.所以在亚种群性能评估时, 最优特征序列上只有每个亚种群中选取的特征, 而其他亚种群位置上的特征均为0, 因此维度压缩率就会很高; 另一方面, 也导致一开始算法的分类性能比较低.但是随着迭代, 之后的迭代过程中会保存历史最优的特征序列, 每个亚种群进行评估时都会与历史最优特征序列进行联系, 所以就会包含其他亚种群的历史特征信息, 维度压缩率迅速降低, 而性能则迅速上升.在到达最优解附近时, 算法就会加大局部搜索力度, 如算法在7th~10th迭代时接近最优解, 在11st迭代达到最优解, 之后算法继续迭代, 就会对那些已选择的但是冗余的特征进行删除, 比如在12nd以及15th时维度缩减率得到进一步提升.

3.4 多种群协同进化

图 5表示MCC-NES算法在Sonar以及Ionosphere数据集上采用Rbf-SVM分类器搜索过程中, 3个分布式种群的最佳性能表现.

由于算法中设计了重启机制, 当某个种群迭代达到阈值而且种群性能停滞时, 就会让该种群的搜索点向表现最优的种群转移.例如, Sonar数据集中的红色种群在11st迭代的时候达到阈值, 而且此时该种群历史性能表现最差, 说明种群搜索极有可能陷入局部最优解.选择重启后, 种群在12nd次迭代中性能大幅提高.当种群达到全局最优解的时候, 种群性能就会趋于稳定.算法通过引入竞争重启机制来实现种群间的信息交互, 防止种群陷入局部最优, 并提高种群全局寻找最优解的能力, 加速算法收敛速率.

图 6表示MCC-NES算法在Sonar以及Ionosphere数据集上采用1-NN分类器时, 3个分布式种群的平均性能表现.在开始阶段种群平均性能波动性较大, 这是因为算法在开始时具有较强的探索性, 在搜索空间中的搜索范围比较大, 所以搜索点的差异比较明显.随着迭代次数增加, 搜索范围逐渐向最优解附近靠近, 因此种群间个体表现的差异就会减小, 种群就会减小搜索范围.所以, 在图 6中就会表现为种群的平均搜索性能趋于稳定.这也说明了算法可以根据种群的搜索性能来自适应调整搜索范围.

3.5 种群内合作协同进化

图 7中表示MCC-NES算法在Ionosphere数据集上采用CART分类器时, 一个种群中的各个亚群之间的进化搜索过程.由于种群使用随机划分, 所以算法开始的时候每个亚群的准确率表现差异较大; 之后通过迭代, 算法通过保留历史最优序列, 使得所有的亚群准确率大致相似.图 7中, 在2nd迭代之后, 所有的亚群准确率在92%左右.通过亚种群之间的合作协同进化, 在5th时到达最优解解附近.所有亚群准确率开始稳定波动, 随着分布参数的逐渐收敛, 波动也逐渐趋于稳定.

3.6 实验结果对比分析

本文提出的特征选择算法MCC-NES是在NES的基础上使用了一些优化策略, 为了验证这些策略的有效性, 我们对比了原始NES, NES+F(在NES的基础上使用新的适应度函数), NES+CC(在NES基础上使用合作协同进化策略), MNES(基于NES的分布式多种群进化策略), MNES+RE(在MNES基础上使用重启策略)在5个数据集(按照特征维数分别代表低维数据、中维数据、高维数据以及更高维度数据)上的表现, 实验中使用1-NN分类器, 实验结果由表 4给出.表 4中的粗体部分对应了该组实验中最佳分类准确率(CA)和维度缩减率(DR).如表 4中数据所示:在NES的基础上, 通过采用相关的优化策略, 可以有效地提高算法的性能.分析其原因分别为:在引入新的适应度函数后, 因为综合考虑了维度缩减的影响, 因此大幅提升了算法的DR值; 在采用子种群合作协同进化策略后, 通过将原始特征集合划分成多个子块进行协同进化, 使得种群能更充分地探索局部搜索空间并发掘出关键信息, 因此大幅提升了算法的分类准确率和维度压缩率; 通过使用多种群分布式进化策略, 实现多个种群并行搜索, 更大程度地在搜索空间进行探索, 因此提升了算法的性能; 而通过引入种群重启策略后, 让种群能够跳出局部最优解, 并不断地将表现差的种群向表现好的种群进行转移, 因此对分类准确率也有一定的改进.

同时, 我们将MCC-NES算法与其他17个特征选择算法进行比较.对比算法详情已由表 2给出.表 5~表 7依据数据集维度大小的划分总结了全部实验结果, 并用粗体标出了不同分类器对应的表现最佳的分类准确率和维度缩减率.按照文献[14]中给出的一般做法, 为了确保对比实验结果的准确性, 部分数据结果均采用了文献[14-18, 21, 45]中公开发表的实验结果.实验中使用的分类器主要包括KNN(1-NN, 3-NN, 5-NN), CART和Rbf- SVM.

对比分类准确率, 通过表 5~表 7不难看出:当分类器和数据集划分方法相同时, 对比其他所有算法, MCC- NES在Glass, Heart, Cleveland, Dermatology, Spambase, Musk2, LSVT, SRBCT, Arcene, RNA-Seq, Dorothea等11个数据集上, 其分类准确率都是最高的; 而在Wine数据集的Rbf-SVM分类器上, 分类准确率仅低于HGAFS算法0.6%;在Vehicle数据集的Rbf-SVM分类器上, 低于HGAFS算法3%;在Segmentatin数据集的3-NN分类器上, 低于FAFOA算法2.6%;在Ionosphere数据集的Rbf-SVM分类器上, 低于ISEDBFO算法0.9%;在Sonar数据集的Rbf-SVM分类器上, 低于ACBFO算法12%.其中:在Sonar数据集中, 当分类器为1NN时, MCC-NES分类准确率比SBS高出35%.

在处理更高维的数据时, 很多特征选择方法就显得无能为力了, 比如在面对LSVT, SRBCT, Arcene, RNA-Seq, Dorothea数据集时.我们在设定的最大迭代时间内(24 hours)内测试了本文提出的方法, 并与最新提出的几个特征选择方法FSFOA, UFSACO, Rc-BBFA(该算法最适应于1-NN分类器, 所以只选取了1-NN分类器的实验结果)进行比较.实验结果表明:在处理高维问题时, 我们算法的准确率几乎都是最优的, 并且特征数量即使达到100 000时仍能给出令人满意的解.其中, 在Arcene的CART分类器上更是比次优的准确率高出25%, 比UFSACO算法高出30%左右.而且与Rc-BBFA, FSFOA相比, 我们的算法在解决高维问题时的分类准确率和维度缩减表现更为出色.

比较表 5~表 7中各算法的DR值, MCC-NES在Cleveland, Wine, Vehicle, Segmentatin, Dermatology, Musk2, SRBCT, RNA-Seq和Dorothea数据集上有最高的维度压缩率.对于其他的数据集, 虽然不能在所有分类器上达到最高, 但是MCC-NES的DR值仍具有很强的竞争力, 特别是在处理高维数据时, 在Ionosphere数据集70%-30%划分条件下, 分类器为CART时, MCC-NES要比效果最好的FSFOA算法高出较接近40%;在Arcene数据集70%- 30%划分条件下, 分类器为1-NN时, MCC-NES比次优DR的算法高出36%;在RNA-Seq的1-NN分类器下, MCC- NES的DR值高出Rc-BBFA算法40%;在Dorothea的CART分类器下, MCC-NES的DR值高出FSFOA算法70%.

表 8中列出了MCC-NES算法在14个数据集上使用1-NN分类器时, 关于分类准确率及维度缩减率的标准差.同时, 表中添加参数D^*用来表示算法最终选择的特征个数.分析表中数据可以看出, 算法在所有数据集上均有稳定的分类准确率(这也侧面体现出算法的适应度函数主要以分类准确率为评价标准).除了在Vehicle数据集上的2.18和LSVT数据集上的2.3之外, 算法在大多数数据集上分类准确率的标准差均在1左右, 特别是在高维数据集上标准差更小, 这反映出算法处理高维数据时出色的性能.另一方面, 分析维度缩减的标准差, 由于在低维数据集上特征总数较少, 所选特征子集轻微变动就会导致比较明显的DR值差异, 因此在低维数据集上表现为D^*值标准差较小; 同时, DR值的标准差较高.而在高维数据集上, 由于特征个数较多, 所选择的特征子集间差异就会增大, 但是这些差异相对于庞大的原始特征集合而言影响不大, 这也导致在高维数据集上特征子集的DR值比较相似, 因此算法在高维数据集上表现为D^*的标准差变大, 而DR值标准差变小.但是总体而言, 算法在特征维数缩减上也有稳定的表现.最后, 通过结合分类准确率、维度缩减率以及所选子集特征个数给出算法在处理每个数据集时的显著性测试结果.

4 总结

本文提出了一种基于自然进化策略的特征选择算法MCC-NES, 算法在使用自然进化策略的基础上提出了几点优化方案.在MCC-NES的初始化阶段, 我们使用基于对角协方差矩阵建模的自然进化策略, 并通过初始化函数将特征高斯采样结果编码为{0, 1}特征序列; 在种群进化阶段, 为了使算法能够扩展到高维数据, 在种群内部采用了合作协同进化的思想, 并通过多种群分布式竞争进化的方式来提供更多的探索; 针对算法陷入局部最优解的问题, 采用种群重启机制, 不断地将表现差的种群转移到表现好的种群周围, 并为其提供新的探索能力; 在算法更新阶段, 克服传统更新机制的局限性, 提出新的适应度函数, 将维度缩减也纳入到特征选取的考虑范围, 从而提高了特征子集的选取精度; 进一步, 基于新的适应度函数提出了一种适应度塑造方法, 通过降低梯度对于适应度值的依赖来提高算法的更新精度; 最后, 使用GPU-Tensorflow作为算法的运行框架进行并行计算.之后, 将MCC-NES算法在16个数据集和17个特征选择算法上进行测试、比较, 实验结果表明:MCC-NES普遍提高了数据集的分类准确率和维度缩减能力, 特别是在高维数据中有出色的表现.今后的工作中, 我们尝试将我们的算法应用到更多的优化领域, 特别是一些可以并行的优化过程中来检验我们算法的性能.同时, 尝试将我们的算法应用到实际的工业领域来考察算法的适用性.