随着信息技术的飞速发展, 高维数据的监督分类问题在生产、生活和科研活动中大量涌现. 理论上讲, 增加特征的个数可以提供更多的分辨能力, 但研究表明: 数据维数的线性增加将使得问题的假设空间成指数增长, 特征每增加一维, 为确保学习算法的性能不变, 样本量亦需成倍增加. 另一方面, 在样本量一定的情况下, 由于无关或冗余特征的存在, 过多的特征不仅降低学习算法的效率, 还可能导致过拟合, 致使模型的泛化能力下降^[1]. 特征选择是解决前述问题的有效手段之一, 它根据某种评价标准, 从原始特征集中挑选一些最有效的特征以达到降低特征空间维数的目的, 并取得与原始特征集相似甚至更好的分类性能. 特征选择已成功应用在文本分类^[2]、癌症识别^[3]、设备故障检测^[4]、贷款风险预测^[5]等领域.

纵观现有特征选择方法, 均包含特征子集生成和子集评价两个构成要素^[6]. 前者采用一定的策略搜索特征空间中的全部或部分子集, 常用的方法有穷举搜索、启发式搜索和随机搜索. 后者使用某一标准评价搜索到的子集, 依据该标准是否独立于后续的学习算法, 可将特征选择方法分为过滤式(filter)、包装式(wrapper)和嵌入式(embedded)三类. 相比过滤式, 包装式选择的子集通常拥有更优的分类性能, 因其直接使用特征子集的分类精度作为评价标准^[7].

近年来, 国内外学者对基于随机搜索策略的包装式特征选择开展了广泛的研究, 大量新颖的群智能优化算法被用于特征选择^[8], 其中较为典型的方法有粒子群优化^[9]、蜻蜓算法^[10]、灰狼优化^[11]、鲸鱼优化^[12]、引力搜索算法^[13]等. 这些方法大多从搜索策略的角度对原算法进行了有益的改进, 而有关子集评价的研究则较少.

量子进化算法(quantum-inspired evolutionary algorithm, QEA)是一种基于量子计算原理的概率进化算法, 具有种群规模小、收敛速度快和全局寻优能力强等优点^[14]. 目前, 仅检索到一篇与本文主题密切相关的文献[15], 该文将QEA作为特征子集的搜索策略, 并使用Fisher比评价其性能, 因而它属于一种过滤式的特征选择方法. 综上所述, 将QEA与包装式特征选择结合的相关研究尚处于空白, 本文将从子集评价和搜索策略两个方面开展工作, 力图提出一种具有竞争力的包装式特征选择方法.

1 问题描述

为结构完整性, 给出特征选择的形式化描述. 假定 ${\boldsymbol{D}} = \left\{ {\left( {{{\boldsymbol{s}}_1}, {y_1}} \right), \left( {{{\boldsymbol{s}}_2}, {y_2}} \right), \cdots, \left( {{{\boldsymbol{s}}_m}, {y_m}} \right)} \right\}$ 为原始数据集, ${\boldsymbol{S}} = $ $ {\left( {{{\boldsymbol{s}}_1}, {{\boldsymbol{s}}_2}, \cdots, {{\boldsymbol{s}}_m}} \right)^{\rm{T}}}$ 为样本矩阵, 行和列分别代表不同的样本和特征, ${\boldsymbol{Y}} = {\left( {{y_1}, {y_2}, \cdots, {y_m}} \right)^{\rm{T}}}$ 为各样本对应的真实类别. ${{\boldsymbol{s}}_i} = \left( {{s_{i1}}, {s_{i2}}, \cdots, {s_{in}}} \right)$ 是n维特征空间 $ \chi $ 的一个向量, 即 ${{\boldsymbol{s}}_i} \in \chi$ , $ \chi = span\left\{ {{f_1}, {f_2}, \cdots, {f_n}} \right\} $ , 其中 $ {f_j} $ 表示第 $ j $ 个特征, 元素 $ {s_{ij}} $ ( $ 1\leqslant i \leqslant m $ , $ 1 \leqslant j \leqslant n $ )为样本 ${{\boldsymbol{s}}_i}$ 在特征 $ {f_j} $ 上的取值. 类别 ${y_i} \in {\boldsymbol{C}}$ , ${\boldsymbol{C}} = \left\{ {{c_1}, {c_2}, \cdots, {c_k}} \right\}$ 为类别集合. $ m $ 、 $ n $ 和 $ k $ 分别为样本、特征和类别的个数.

基于上述定义, 监督分类的任务是: 利用给定的学习算法从D中学习一个分类模型h: $ \chi \to {\boldsymbol{C}} $ , 它对采样自 $ \chi $ 的新样本具有良好的泛化能力. 然而, 并不是所有特征都对分类有贡献, 为提高模型的训练效率和泛化能力, 特征选择从原始特征集 $ {\boldsymbol{F}} = \left\{ {{f_1}, {f_2}, \cdots, {f_n}} \right\} $ 中找出一个子集X, $ {\boldsymbol{X}} \subseteq {{F}} $ , 它使得评价函数 $ J\left( {\boldsymbol{X}} \right) $ 尽量大, X包含的特征数尽量少. $ J\left( {\boldsymbol{X}} \right) $ 量化了X分类性能的好坏, 不失一般性, 假定 $ J\left( {\boldsymbol{X}} \right) $ 值越大, X越优. 不难看出, 分类性能和特征个数是该问题最重要的两个优化目标.

基于现有研究, 归纳出包装式特征选择的一般框架如图1所示.

由图1可以看出, 数据集被分为训练集和测试集, 特征选择在训练集上进行, 测试集不参与该过程. 特征选择结束, 需验证最优子集在测试集上的分类精度.在特征选择过程中, 子集的分类性能通过K折平均分类精度来衡量, 分类器被视为一个封闭的黑盒.

2 量子进化算法

基本量子进化算法包含种群初始化、随机观测、种群进化等3个主要步骤^{[14, 16]}. 它采用量子比特编码, 一个量子比特可表示为:

$ \left| \psi \right\rangle = \alpha \left| 0 \right\rangle + \beta \left| 1 \right\rangle $

(1)

其中, $ \left| 0 \right\rangle $ 和 $ \left| 1 \right\rangle $ 表示两个不同的量子态, $ \alpha $ 和 $ \;\beta $ 分别表示状态 $ \left| 0 \right\rangle $ 和 $ \left| 1 \right\rangle $ 的概率幅. 一个量子比特可能处于 $ \left| 0 \right\rangle $ 或 $ \left| 1 \right\rangle $ 两个基态, 或者两基态的任意叠加态, $ {\left| \alpha \right|^2} $ 和 $ {\left| \beta \right|^2} $ 表示该量子比特处于 $ \left| 0 \right\rangle $ 和 $ \left| 1 \right\rangle $ 的概率大小.

设第t代的种群为 ${\boldsymbol{Q}}\left( t \right) = \left\{ {{\boldsymbol{q}}_1^t, {\boldsymbol{q}}_2^t, \cdots, {\boldsymbol{q}}_G^t} \right\}$ , 其中 $ G $ 为种群规模, ${\boldsymbol{q}}_j^t$ 为第j ( $ 1 \leqslant j \leqslant G $ )个采用量子比特编码的染色体, 其表达式如下:

$ {\boldsymbol{q}}_j^t = \left[ \begin{gathered} \alpha _{j1}^t \hfill \\ \beta _{j1}^t \hfill \\ \end{gathered} \right.{\text{ }}\left| \begin{gathered} {\text{ }}\alpha _{j2}^t \hfill \\ {\text{ }}\beta _{j2}^t \hfill \\ \end{gathered} \;\;\right| \begin{gathered} \cdots \\ \\ \end{gathered}\left. {\left| \begin{gathered} {\text{ }}\alpha _{jl}^t \hfill \\ {\text{ }}\beta _{jl}^t \hfill \\ \end{gathered} \right.} \right] $

(2)

式中, $ {\left| {\alpha _{jk}^t} \right|^2} + {\left| {\beta _{jk}^t} \right|^2} = 1 $ , $ 1 \leqslant k \leqslant l $ , l为染色体长度. 采用量子比特编码, 一个长度为l的染色体能够同时表达 $ {2^l} $ 个状态的叠加, 因而更容易保持种群的多样性.

通过对 ${\boldsymbol{Q}}\left( t \right)$ 的随机观测, 得到一组二进制状态 ${\boldsymbol{P}}\left( t \right) = \left\{ {{\boldsymbol{x}}_1^t, {\boldsymbol{x}}_2^t, \cdots, {\boldsymbol{x}}_G^t} \right\}$ , 其中 ${\boldsymbol{x}}_j^t = \left( {x_{j1}^t, x_{j2}^t, \cdots, x_{jl}^t} \right)$ 为观察 ${\boldsymbol{q}}_j^t$ 的结果. 具体过程为: 对 ${\boldsymbol{q}}_j^t$ 的每个量子比特 ${\left[ {\alpha _{jk}^t, \beta _{jk}^t} \right]^{\rm{T}}}$ , 产生一个随机数Rnd, Rnd $ \in $ (0, 1), 若 $ Rnd < {\left| {\beta _{jk}^t} \right|^2} $ , 则 $ x_{jk}^t $ =1, 否则, $ x_{jk}^t $ =0.

${\boldsymbol{P}}\left( t \right)$ 通常代表问题的一组解, 计算每个 ${\boldsymbol{x}}_j^t$ 的适应度 $f\left( {{\boldsymbol{x}}_j^t} \right)$ , 然后使用量子旋转门更新种群 ${\boldsymbol{Q}}\left( t \right)$ . 设 ${\boldsymbol{B}}\left( t \right) = \left\{ {{\boldsymbol{b}}_1^t, {\boldsymbol{b}}_2^t, \cdots, {\boldsymbol{b}}_G^t} \right\}$ , 其中 ${\boldsymbol{b}}_j^t = \left( {b_{j1}^t, b_{j2}^t, \cdots, b_{jl}^t} \right)$ 为 ${\boldsymbol{q}}_j^t$ 截至第 $ t $ 代搜索到的个体最优解, 整个种群搜索到的全局最优解记为 ${{\boldsymbol{b}}^t} = \left( {b_1^t, b_2^t, \cdots, b_l^t} \right)$ . 对于 ${\boldsymbol{q}}_j^t$ , 第 $ k $ ( $ 1 \leqslant k \leqslant l $ )位量子比特的更新方式如下:

$ \left[ \begin{gathered} \alpha _{jk}^{t + 1} \hfill \\ \beta _{jk}^{t + 1} \hfill \\ \end{gathered} \right] = \left[ \begin{gathered} \cos \left( {\Delta {\theta _k}} \right){\text{ }} - \sin \left( {\Delta {\theta _k}} \right) \hfill \\ \sin \left( {\Delta {\theta _k}} \right){\text{ }}\cos \left( {\Delta {\theta _k}} \right) \hfill \\ \end{gathered} \right]\left[ \begin{gathered} \alpha _{jk}^t \hfill \\ \beta _{jk}^t \hfill \\ \end{gathered} \right] $

(3)

式中, ${\left[ {\alpha _{jk}^{t + 1}, \beta _{jk}^{t + 1}} \right]^{\rm{T}}}$ 为 ${{q}}_j^{t + 1}$ 的第 $ k $ 位量子比特, $ \Delta {\theta _k} $ 为旋转角, 其取值由式(4)决定^[16]:

$ \Delta {\theta _k} = \left\{ \begin{array}{l} \theta \times \left\{ {{\rm{sign}}\left( {\alpha _{jk}^t\beta _{jk}^t} \right)\left( {b_k^t - x_{jk}^t} \right)} \right\}, \;\; f\left( {{\boldsymbol{x}}_j^t} \right) < f\left( {{{\boldsymbol{b}}^t}} \right) \\ 0,\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \text{otherwise} \\ \end{array} \right. $

(4)

其中, ${\rm{sign}}\left( \cdot \right)$ 为符号函数, $ \theta $ 为 $ \Delta {\theta _k} $ 的旋转角幅值大小, 其取值一般为0.001 $ \pi $ ~0.05 $ \pi $ . 按照式(3)和式(4)更新 ${\boldsymbol{q}}_j^t$ 的所有量子比特即得到 ${\boldsymbol{q}}_j^{t + 1}$ . 重复上述步骤, 实现整个种群的更新.

3 特征选择方法 3.1 种群初始化

算法开始时, 设置进化代数t=0, 初始化种群 ${\boldsymbol{Q}}\left( 0 \right) = \left\{ {{\boldsymbol{q}}_1^0, {\boldsymbol{q}}_2^0, \cdots, {\boldsymbol{q}}_G^0} \right\}$ , 其中 ${\boldsymbol{q}}_j^0$ ( $ 1 \leqslant j \leqslant G $ )为第j个量子染色体, 其形式如式(2), 设置染色体的长度为原始数据集的特征个数n, 且其中的 $ \alpha _{jk}^0 $ 和 $ \beta _{jk}^0 $ ( $ 1 \leqslant k \leqslant n $ )均初始化为 ${1 \mathord{\left/\right. }{\sqrt 2 }}$ . 按照这种初始化方法, 意味着t=0时每种特征组合以相同的概率( $ {1 \mathord{\left/ {\vphantom {1 {{2^n}}}} \right. } {{2^n}}} $ )叠加, 随机观测时, 每种特征组合出现的概率亦相等.

3.2 特征子集评价和性能比较

第t代, 通过对种群的随机观测, 得到P(t)= $ \left\{ {{\boldsymbol{x}}_1^t, {\boldsymbol{x}}_2^t, \cdots, {\boldsymbol{x}}_G^t} \right\}$ , 则 ${\boldsymbol{x}}_j^t$ 代表一个特征子集, 若 $ x_{ji}^t = 1 $ , 表示特征 $ {f_i} $ ( $ 1 \leqslant i \leqslant n $ )选中, 否则 $ {f_i} $ 未选中. 利用 ${\boldsymbol{x}}_j^t$ 和学习算法在训练集上进行K折交叉验证, 其结果记为 ${\boldsymbol{R}}_j^t = \left( {a{c_1}, a{c_2}, \cdots, a{c_K}} \right)$ , 其中 $ a{c_k} $ 为第k折的分类精度. 定义 $ {\boldsymbol{x}}_j^t $ 的K折平均分类精度 $ Ave_j^t $ 和特征个数 $ N_j^t $ 分别如式(5)所示:

$ Ave_j^t = \frac{1}{K}\sum\limits_{i = 1}^K {a{c_i}} $

(5)

$ N_j^t = \sum\limits_{i = 1}^n {x_{ji}^t} $

(6)

设 $f\left( {{\boldsymbol{x}}_j^t} \right)$ 为 ${\boldsymbol{x}}_j^t$ 的适应度函数, ${\boldsymbol{x}}_i^t$ 为不同于 ${\boldsymbol{x}}_j^t$ 的任意一个特征子集, 为评价和比较 $ {\boldsymbol{x}}_i^t $ 和 $ {\boldsymbol{x}}_j^t $ 的优劣, 现有文献采用的主要方法如下:

方法1^[17]: $f\left( {{\boldsymbol{x}}_j^t} \right) = Ave_j^t$ , 仅考虑特征子集的分类精度. 若 $ f\left( {{\boldsymbol{x}}_j^t} \right) > f\left( {{\boldsymbol{x}}_i^t} \right) $ , 则 $ {\boldsymbol{x}}_j^t $ 优于 $ {\boldsymbol{x}}_i^t $ .

方法2^[18]: $ f\left( {{\boldsymbol{x}}_j^t} \right) = \left( {Ave_j^t, N_j^t} \right) $ , 由 $ Ave_j^t $ 和 $ N_j^t $ 两个分量构成, 但前者的优先级更高. 若 $ Ave_j^t > Ave_i^t $ , 或者 $ Ave_j^t = Ave_i^t $ , 且 $ N_j^t < N_i^t $ , 则 $ {\boldsymbol{x}}_j^t $ 优于 $ {\boldsymbol{x}}_i^t $ .

方法3^[9-13]: $ f\left( {{\boldsymbol{x}}_j^t} \right) = \alpha \cdot \left( {1 - {{Av}}e_j^t} \right) + \beta \cdot {{N}}_j^t/n $ , 通过加权的方式兼顾分类精度和特征个数, $ \alpha $ 和 $\; \beta $ 为两者的权重, 取值分别为0.99和0.01. 若 $ f\left( {{\boldsymbol{x}}_j^t} \right) < f\left( {{\boldsymbol{x}}_i^t} \right) $ , 则 $ {\boldsymbol{x}}_j^t $ 优于 $ {\boldsymbol{x}}_i^t $ .

通过实验发现: 相比方法1, 在一些数据集上, 后两种方法确能得到分类精度高且特征个数更少的子集, 但仍旧偏好分类精度高的特征子集. 若 $ Ave_j^t > Ave_i^t $ , 方法2直接判定 $ {\boldsymbol{x}}_j^t $ 优于 $ {\boldsymbol{x}}_i^t $ ; 根据 $ \alpha $ 和 $\; \beta $ 的取值, 方法3大多情况下也会得到相同的结论. 考虑这样的情形, 虽然 $ Ave_j^t > Ave_i^t $ , 但两者并无显著的差异, 这时仅仅根据这种严格的大小关系就判定 $ {\boldsymbol{x}}_j^t $ 优于 $ {\boldsymbol{x}}_i^t $ 并不合理, 因为这种微小的差异可能是由K的取值及K折数据集的划分方式等因素造成, 而不是 $ {\boldsymbol{x}}_j^t $ 和 $ {\boldsymbol{x}}_i^t $ 分类性能差异的一种真实反映. 在两者分类精度无显著差异的情况下, 选择特征个数更小的子集有助于减小分类模型的复杂度, 增强其泛化能力, 更好的兼顾分类精度和特征个数这两个优化目标.

根据以上分析, 提出两种新的子集评价方法:

方法4: $ f\left( {{\boldsymbol{x}}_j^t} \right) = \left( {Ave_j^t, N_j^t} \right) $ , 若 $ Ave_j^t - Ave_i^t $ > $ \varepsilon $ , 或者 $ abs\left( {Ave_j^t - Ave_i^t} \right) $ $\leqslant $ $ \varepsilon $ 且 $ N_j^t < N_i^t $ , 则 $ {\boldsymbol{x}}_j^t $ 优于 $ {\boldsymbol{x}}_i^t $ , 其中 $ abs\left( \cdot \right) $ 为绝对值函数.

该方法采用固定阈值 $ \varepsilon $ 来判断两个子集的分类精度是否有显著差异. 当 $ Ave_j^t $ 和 $ Ave_i^t $ 的差值大于 $ \varepsilon $ , 则认为 $ {\boldsymbol{x}}_j^t $ 和 $ {\boldsymbol{x}}_i^t $ 的分类精度有显著差异, 直接判定 $ {\boldsymbol{x}}_j^t $ 优于 $ {\boldsymbol{x}}_i^t $ ; 当 $ Ave_j^t $ 和 $ Ave_i^t $ 之差的绝对值不大于 $ \varepsilon $ , 则认为 $ {\boldsymbol{x}}_j^t $ 和 $ {\boldsymbol{x}}_i^t $ 的分类精度相似, 特征个数越小的子集更优.

方法5: $ f\left( {{\boldsymbol{x}}_j^t} \right) = \left( {{\boldsymbol{R}}_j^t, N_j^t} \right) $ , 若 $ Ave_j^t > Ave_i^t $ , 且 $ p < delta $ 或者 $ p \geqslant delta $ , 且 $ N_j^t < N_i^t $ , 则 $ {\boldsymbol{x}}_j^t $ 优于 $ {\boldsymbol{x}}_i^t $ , 其中p为 $ {\boldsymbol{R}}_j^t $ 和 $ {\boldsymbol{R}}_i^t $ 进行威尔科克森秩和检验(Wilcoxon rank-sum test)的P值, $ delta $ 为显著性水平.

该方法采用统计检验来判断两个子集的分类精度是否有显著差异. 第一种情况表示 $ Ave_j^t $ 显著的大于 $ Ave_i^t $ , 第二种情况表示 $ Ave_j^t $ 和 $ Ave_i^t $ 无显著差异, 但 $ N_j^t < N_i^t $ , 满足这两种情况均判定 $ {\boldsymbol{x}}_j^t $ 优于 $ {\boldsymbol{x}}_i^t $ . 注意, 此处引入非参数统计检验的目的是提出一种比较子集分类性能的启发式准则, 并非一般意义上的统计检验.

3.3 种群进化策略

为避免QEA早熟, 文献[15]采取随机初始化、两次观测取优和动态调整旋转角幅值等措施. 文献[16]指出: 在QEA中, 使用 $ {{\boldsymbol{b}}^t} $ 作为各个量子染色体的进化目标, 虽能使整个种群快速地向全局最优子集靠拢, 但容易陷入局部最优. 受此启发, 将整个算法的进化过程分为两个阶段, 前一阶段随机选择一个更优的个体极值作为进化目标, 以维持种群的多样性; 后一阶段使用 $ {{\boldsymbol{b}}^t} $ 作为所有个体的进化目标, 加速算法收敛.

(1) 随机选择更优个体极值的种群更新

Step 1. 对量子染色体 $ {\boldsymbol{q}}_j^t $ ( $ 1 \leqslant j \leqslant G $ )进行随机观测, 得到二进制状态 $ {\boldsymbol{x}}_j^t $ , 并计算 $ {\boldsymbol{R}}_j^t $ , 再由式(5)和式(6)计算 $ Ave_j^t $ 和 $ N_j^t $ .

Step 2. 按照第3.2节的方法4或5更新 $ {\boldsymbol{b}}_j^t $ 和 $ {{\boldsymbol{b}}^t} $ .

Step 3. 使用方法4或5依次比较 $ {\boldsymbol{x}}_j^t $ 与所有的个体极值 $ {\boldsymbol{b}}_j^t $ ( $ 1 \leqslant j \leqslant G $ ), 记性能优于 $ {\boldsymbol{x}}_j^t $ 的个体极值构成的集合为temp.

Step 4. 从temp中随机选择一个个体极值 $ {\boldsymbol{b}}_{j'}^t $ 作为 $ {\boldsymbol{x}}_j^t $ 的进化目标, 按照式(3)和式(4)更新 $ {\boldsymbol{q}}_j^t $ .

Step 5. 重复Step 1~Step 4, 直至完成1次种群进化.

(2) 基于全局极值的种群更新

Step 1. 按照前述相同的方法观测 $ {\boldsymbol{q}}_j^t $ , 得到 $ {\boldsymbol{x}}_j^t $ , 并计算 $ {\boldsymbol{R}}_j^t $ 、 $ Ave_j^t $ 和 $ N_j^t $ .

Step 2. 更新 $ {\boldsymbol{b}}_j^t $ 和 $ {{\boldsymbol{b}}^t} $ .

Step 3. 选择 $ {{\boldsymbol{b}}^t} $ 作为进化目标, 更新 $ {\boldsymbol{q}}_j^t $ .

Step 4. 重复Step 1~Step 3, 直至完成1次种群进化.

(3) 旋转角幅值的确定

在QEA中, $ \theta $ 为一个固定值, 不能很好的兼顾全局和局部搜索. 针对该问题, 提出如下方法:

$ \theta = {\theta _{\max }}{{ - }}\left( {{\theta _{\max }} - {\theta _{\min }}} \right) \times \frac{t}{T} $

(7)

其中, $ {\theta _{\max }} $ 和 $ {\theta _{\min }} $ 分别为 $ \theta $ 的最大和最小可能取值, T为算法的最大进化代数. 算法前期, $ \theta $ 取值较大, 使得算法专注于全局范围的搜索; 算法后期, $ \theta $ 取值较小, 使得算法集中于 ${{\boldsymbol{b}}^t}$ 邻域内的搜索. 经过多次测试, 实验中 $ {\theta _{\max }} $ 和 $ {\theta _{\min }} $ 的取值分别为0.04 $ {\text{π}} $ 和0.0025 $ {\text{π}} $ .

3.4 整个算法流程

综合第3.2节和第3.3节的改进措施和图1, 得到整个特征选择方法的流程如图2所示.

由图2可知, 实验中利用分层采样将数据集分为训练集和测试集. 在特征选择过程中, 两种进化策略分别执行T/3和2T/3代.

4 实验与结果分析 4.1 实验方案

选取UCI^[19]中的15个数据集作为实验数据, 其中大多已被用于验证各种特征选择方法, 关于这些数据集的详细信息如表1所示. 注意, 前11个数据集以一个整体的形式提供, 实验中利用分层采样将其分为70%的训练集和30%的测试集; 后4个加“*”号的数据集以训练集和测试集的形式提供, 实验中直接使用训练集做特征选择, 测试集用于验证, 不再进行划分.

包装式特征选择方法使用分类器来评价特征子集, 后续实验均使用K近邻(K-nearest neighbor, KNN)学习算法, 这有利于算法之间公平的比较^[9-13]; KNN的距离度量使用欧氏距离, 近邻个数为5. 所有实验均在同一台PC机上进行, 配置为: Intel(R) Core(TM) i7-9700 CPU@ 3.00 GHz, 8 GB内存, Win10 64位操作系统, 编程环境为Matlab 9.9 (R2020b). 为了结果的客观性, 若无特别说明, 对于每个数据集, 算法均独立运行20次, 以便评估算法的性能, 表中所示分类精度和特征个数是20次独立试验后的平均值.

4.2 重要参数的选择

子集评价方法4和5分别依赖于参数 $ \varepsilon $ 和 $ delta $ 的取值, 它们直接影响显著性的判定. 选取表1中的前5个数据集进行参数的讨论, 假定 $ \varepsilon $ 的可能取值为{0.001, 0.005, 0.010, 0.050, 0.100, 0.500}, $ delta $ 的可能取值为{0.05, 0.10, 0.15, 0.20}. 为选择一组合适的参数, 进化策略采用基本QEA, 将其分别与子集评价方法4和5相结合构成2种特征选择算法. 其它的算法参数为: 种群规模G=10, 最大进化代数T=50, 交叉验证次数K=10, 旋转角幅值 $ \theta $ =0.01 $ \pi $ . 不同参数取值对应的平均分类精度和特征个数如图3所示.

从图3(a)可以看出, 除了waveform, 在其它数据集上平均特征个数随 $ \varepsilon $ 增大而减小, $ \varepsilon $ 的值越小越好; 考察分类精度, 其值亦呈现相同的趋势, 但前3种 $ \varepsilon $ 值对应的分类精度在5个数据集上均无显著差异, 后3种 $ \varepsilon $ 值对应的分类精度则显著下降. 综合考虑, 选取 $ \varepsilon $ 的值为0.010. 同理分析图3(b), 平均特征个数随 $ delta $ 增大而增大, $ delta $ 的值越小越好; 从分类精度的角度, 仅有 $ delta $ =0.10时对应的分类精度在5个数据集上与 $ delta $ 的其余4种取值的最优分类精度均无显著差异, 故选取 $ delta $ 值为0.10.

4.3 子集评价方法对比

为对比不同的子集评价方法, 搜索策略采用基本QEA, 将其分别与5种子集评价方法相结合构成5种特征选择算法, 算法参数同第4.2节. 表2为5种特征选择方法的运行结果, 其中 $ {P_{ij}} $ 表示对方法 $ i $ ( $ i $ =1, 2, 3)和方法j ( $ j $ =4, 5)的20次分类精度进行威尔科克森秩和检验的P值, 显著性水平为0.05. “+”和“–”分别表示前者的分类精度显著好于和差于后者, 而“=”则表示两者的分类精度相似, 没有显著差异, 表中最后一行统计了对应列“+”“–”和“=”的个数.

由表2可知, 相比子集评价方法1、方法2和方法3, 方法4至少在13个数据集上取得相似甚至更好的分类精度; 而方法5仅在8个数据集上表现出同样的性能, 在其余7个数据集上分类精度要显著的差于方法1、方法2和方法3. 从特征个数的角度, 不难看出方法5总是取得最优的结果, 其次是方法4. 为更具体的说明, 以breast数据集为例, 给出其20次实验中的分类精度和特征个数的箱线图, 如图4所示.

从图4(a)可以看出, 前4种方法对应分类精度的中位值和平均值大致相当, 难以直观判断哪种方法更优, 但均优于方法5的分类精度; 从图4(b)可以很容易看出方法5选择的特征个数最少, 其次是方法4. 综合两者, 方法4能在确保分类精度无显著差异的情况下, 选择特征个数更小的子集, 表明针对子集评价方法的改进是有效的, 后续实验均采用方法4作为子集评价方法.

4.4 进化策略的有效性验证

采用子集评价方法4, 将其分别与基本QEA和改进QEA相结合构成2种特征选择方法, 算法参数同第4.2节. 为叙述方便, 分别简记为BQEA和IQEA, 其运行结果如表3所示, 其中 $ P $ 为针对分类精度的威尔科克森秩和检验的P值, “+”和“–”分别表示BQEA的分类精度显著的好于和差于IQEA, 而“=”则表示两者的分类精度相似.

由表3可以看出, 在Semeion和Landsat数据集上, BQEA的分类精度显著优于IQEA, 在Ionosphere和Hillvalley数据集上的结论正好相反, 在其余数据集上两者的分类精度均相似. 从特征个数来看, IQEA的结果总是优于BQEA对应的结果. 同样以Breast数据集为例, 其分类精度和特征个数的箱线图如图5所示.

由图5(a)可以看出, BQEA和IQEA的分类精度大致相当, 无法直观判断哪种方法更优; 从图5(b)却可以直观的看出IQEA选择的特征个数小于BQEA对应的结果. 由实验的设置可知, BQEA和IQEA的差异仅在于进化策略的不同, 表明针对进化策略的改进措施是有效的.

4.5 特征选择方法的对比

选取近年来新提出的包装式和过滤式特征选择方法作为对比, 包括HPSOSSM^[9]、SBDA^[10]、ABGWO^[11]、HMNWOA^[12]、HGSA^[13]和FS-IQEA^[15], 其中前5种方法属于包装式, 后1种方法为过滤式. 为比较的公平性, 设置所有算法的种群规模G=20、进化代数T=60, 交叉验证次数K=10, 每种方法其余的参数按照对应文献给定的值设置. 这些方法连同IQEA的运行结果如表4所示, 其中 $ {P_i} $ (i=1, 2, 3, 4, 5, 6)分别表示6种对比方法和IQEA的分类精度做威尔科克森秩和检验的P值, “+”“–”和“=”的含义同前.

由表4可知, 分类精度方面, IQEA显著优于HPSOSSM 、SBDA、ABGWO、HMNWOA、HGSA和FS-IQEA的数据集占比分别为26.67%、20.00%、26.67%、13.33%、20.00%和66.67%; 取得相似分类精度的数据集占比分别为53.33%、66.67%、60.00%、73.33%、66.67%和33.33%. 综合两者, IQEA与比较方法取得相似甚至更好分类性能的数据集占比分别为80.00%、86.67%、86.67%、86.67%、86.67%和100%.

从特征个数来看, 除了Semeion数据集, FS-IQEA选择的子集总是包含最少的特征, 但其对应的平均分类精度亦小于包装式方法对应的结果, 从而证实了“相比过滤式, 包装式选择的子集通常拥有更优的分类性能”的一般结论. 若仅考察包装式方法, 不难看出, 除了LSVT和hillvalley数据集 , IQEA在其余数据集上选择的特征个数均最少, 占总数据集的86.67%.

综合考虑分类精度和特征个数, 相比现有包装式特征选择方法, 可以看出IQEA在大多数情况下能取得相似甚至更好的分类性能, 并且选择的特征个数更少, 降维效果更加明显.

5 结论与展望

子集评价和搜索策略是构成包装式特征选择方法的两个关键要素, 论文从这两个角度出发, 分别提出了改进的子集评价方法和搜索策略, 进而设计了一种

基于量子进化算法的包装式特征选择方法. 大量的实验结果表明, 相比现有特征选择方法, 本文方法在大多数情况下能搜索到更小的特征子集, 并能取得相似甚至更好的分类精度, 降维效果突出. 同时表明, 要提高包装式特征选择方法的性能, 除了现有文献广泛关注的搜索策略, 子集评价方法也应重点关注.

需要指出, 随着样本量和特征个数的增加, 包装式特征选择方法的计算量将显著增加, 甚至根本不适用. 实验中所用数据集的特征个数均不超过1000, 因此如何进一步提高算法的性能, 使其适用于更高维(特征个数>1000)数据的场合, 例如基因选择, 将是下一步要研究的内容.