简述特征选择

Brief Description of Feature Selection

摘要: 特征选择是通过寻找对于目标函数有突出贡献的特征来达到降维的效果，该方法希望可以尽可能多的去掉冗余特征，能够更加准确合理地解释这些数据。研究者们对于特征选择的研究历史也比较悠久，从而特征选择也变得越来越准确、有效。本文介绍特征选择概念之后，简单综述了特征选择在方法和理论上的发展，并且重点介绍了支持向量机在特征选择上的应用。

Abstract: Feature selection is to reduce dimension by finding features that contribute significantly to the ob-jective function. This method hopes to remove redundant features as much as possible and inter-pret these data more accurately and reasonably. Researchers have a long history of research on feature selection, so feature selection is becoming more and more accurate and effective. After in-troducing the concept of feature selection, this paper briefly reviews the development of feature se-lection methods and theories, and focuses on the application of support vector machines in feature selection.

1. 引言

特征选择在模式识别领域的地位至关重要 [1]。在模式识别系统中，一般都为模式获取，预处理，特征选择或特征提取，采用回归分析、分类研究或描述性研究处理数据，后处理这五个部分。其中，特征选择与特征提取也是人们经常混淆的概念。其实这两者有着本质的区别。

特征提取是在高维样本空间中，通过映射或变换的方法来降低样本维度，该映射或变换通过将原始特征作某种组合来形成新特征，该新特征被称为二次特征。特征提取的本质为一种变换，通过将测量空间中的变量通过变换转化为新特征空间中的变量，该变换称为特征提取器。常见的特征提取方法为主成分分析(PCA)，独立主成分分析(ICA)等。

特征选择则是在高维特征空间中挑选出一些最有效的特征从而实现降维的目的 [2] [3]。在特征选择的过程中，一方面，在样本有限的前提下，不管是从开销成本还是从分类器性能来设计分类器都不是很理想；另一方面，线性关系在分类器性能和特征之间并不存在，当特征数量超出一定阈值时，将破坏分类器性能。因此，正确且有效地进行特征选择则在模式识别中显得尤为重要。

本文首先对文中涉及的标记和符号进行说明，其次简单介绍特征选择的基本知识及求解方法，接下来重点叙述特征选择的稀疏模型及其发展，最后对全文进行了总结。

2. 符号

$X\in R^{n\times p}$ 是标准化的数据矩阵，n为样本数量，p为特征数量，不失一般性，假设X的列均值为0。

单位矩阵记为I。 $\alpha ={\left(a_1,a_2,\cdots ,a_p\right)}^{\text{T}}\in R^p$ ， ${\Vert \alpha \Vert }_2={\left({\displaystyle \underset{i=1}{\overset{p}{\sum }}{a}_i^2}\right)}^{1/2}$ ， ${\Vert \alpha \Vert }_1={\displaystyle \underset{i=1}{\overset{p}{\sum }}\left|a_i\right|}$ ， $X=\left(\begin{array}{c}{x}_1^{\text{T}}\\ x_2^{\text{T}}\\ ⋮\\ x_n^{\text{T}}\end{array}\right),x_i\in R^p$ ，矩阵 $A=\left(a_{ij}\right)\in R^{p\times k}$ ， $B\in R^{p\times n}$ 为数据矩阵， $e={\left(\begin{array}{cccc}1& 1& \cdots & 1\end{array}\right)}^{\text{T}}\in R^{n\times 1}$ ， ${\Vert x\Vert }^{\prime }=\underset{\Vert y\Vert =1}{\max }{x}^{\text{T}}y$ 。

3. 特征选择

特征选择的方法可如文献 [4] 中所述由特征子集形成方式和特征评价方法来分为两大类，本文将由这两大类为出发点介绍特征选择的算法。

3.1. 特征子集形成方式

3.1.1. 采用全局最优搜索策略的特征选择算法

分支定界算法策略运用到的两个分支规则 [5] ：

最低下界优先，即选择具有最低下界的子集进行分支，它能提供寻求最优值的最好机会，并且通过探测来排除大量非最优点。但如果问题规模较大，寻找最优子集则相当的耗费时间。

最新下界优先，即选择最新形成的子集进行分支，该方法避免了算法流程反复在对应的搜索树中跳转，并且缩短了定界的时间，从而可以提高算法的效率，如果当前考察的子问题对应的可行解与最优解差别很大时，那么将会进行大量不必要的界估计运算。

各类样本可以分开是因为它们位于特征空间中的不同区域, 显然这些区域之间距离越大，类别可分性就越大 [6]。

令 $x_k^{\left(i\right)}$ 、 $x_l^{\left(j\right)}$ 分别为 $w_i$ 、 $w_j$ 类中的特征向量， $d\left(x_k^{\left(i\right)},x_l^{\left(j\right)}\right)$ 为它们之间的欧氏距离，则类别间的平均距离(类间距离)为

$J_d\left(x\right)=\frac{1}{2}{\displaystyle \underset{i=1}{\overset{C}{\sum }}{P}_i}{\displaystyle \underset{i=1}{\overset{C}{\sum }}{P}_j}\frac{1}{n_i{n}_j}d\left(x_k^{\left(i\right)},x_k^{\left(j\right)}\right)$ (1)

式中：C为类别数； $n_i$ 、 $n_j$ 分别为 $w_i$ 、 $w_j$ 类的样本数； $P_i$ 、 $P_j$ 是相应的先验概率。若 $m_i$ 表示第i类样本集特征的均值：

$m_i=\frac{1}{n_i}{\displaystyle \underset{k=1}{\overset{n_i}{\sum }}{x}_k^{\left(i\right)}}$ (2)

m表示所有各类的样本集特征的总平均向量：

$m={\displaystyle \underset{i=1}{\overset{C}{\sum }}{P}_i{m}_i}$ (3)

$d\left(x_k^{\left(i\right)},x_l^{\left(j\right)}\right)={\left(x_k^{\left(i\right)}-x_l^{\left(j\right)}\right)}^T\left(x_k^{\left(i\right)}-x_l^{\left(j\right)}\right)$ (4)

将(2)、(3)、(4)代入(1)中得：

${J^{\prime }}_d\left(x\right)={\displaystyle \underset{i=1}{\overset{C}{\sum }}{P}_i\left[\frac{1}{n_t}{\displaystyle \underset{k=1}{\overset{n_i}{\sum }}{\left(x_k^{\left(i\right)}-m_t\right)}^{\text{T}}}\left(x_k^{\left(i\right)}-m_t\right)+{\left(m_i-m\right)}^{\text{T}}\left(m_t-m\right)\right]}=tr\left(S_w+S_b\right)$

其中， $S_b={\displaystyle \underset{i=1}{\overset{C}{\sum }}{P}_i\left(m_i-m\right)}{\left(m_i-m\right)}^{\text{T}}$ 为类间散度矩阵； $S_w={\displaystyle \underset{i=1}{\overset{C}{\sum }}{P}_i\frac{1}{n_i}}{\displaystyle \underset{k=1}{\overset{n_i}{\sum }}\left(x_k^{\left(l\right)}-m_i\right){\left(x_k^{\left(l\right)}-m_i\right)}^{\text{T}}}$ 为类内散度矩阵。

易知，类间样本散度越大，类内样本散度越小，则类别之间越可分。

3.1.2. 采用随机搜索策略的特征选择算法

采用随机搜索策略进行特征选择其本质上是一个组合优化问题，它通常将特征选择与模拟退火算法、禁忌搜索算法、遗传算法等结合起来进行求解。其中，最常使用的，还是遗传算法(Genetic Algorithm，简称GA) [7]。

通过对特征集 $F=\left\{f_1,f_2,\cdots ,f_N\right\}$ 中的每一个特征利用二进制进行遗传编码，得到一个码长为N的二进码串： $H=\left\{h_1{h}_2\cdots h_N|h_i\in \left\{0,1\right\},i=1,\cdots ,N\right\}$ 为所有特征子集的集合，称为个体空间。个体空间的大小可由组合数求得： $C_N^1+C_N^2+\cdots +C_N^N=2^N-1$ 。每一个个体都可表示为 $h_1,h_2,\cdots ,h_N\in H$ ，同时将样本分为训练集和测试集两部分，用训练集训练模型，然后再测试其分类的正确率，最后计算平均分类正确率。易知，想要分类更准确，则需要让平均分类正确率达到最高，故可将平均分类正确率作为目标函数，并

求其最大值。设 $r^1,r^2,\cdots ,r^M$ 表示M类分类问题中的每一类正确分类率，则此类问题可归结为： $\underset{h\in H}{\max }f\left(h\right)$ ，其中， $f\left(h\right)=\frac{1}{M}{\displaystyle \underset{i=1}{\overset{M}{\sum }}{r}_i}$ 。在遗传算法中，经常使用适应度分配进行概率选择，一般情况下，我们都想利用

使目标函数达到最大值的最优解来进行选择，但由于我们想要得到较少的特征，故同时想到了惩罚函数

法： $f_1\left(h\right)=\frac{1}{M}{\displaystyle \underset{i=1}{\overset{M}{\sum }}{r}_i-c\cdot l\left(h\right)}$ ，其中， $l\left(h\right)$ 为个体h中1的位数。惩罚参数c的大小则根据需要进行选择。

3.1.3. 采用启发式搜索策略的特征选择算法

采用启发式搜索策略进行特征选择的方法有：单独最优特征选择(通过计算特征每个单独使用时的判据值对特征进行排序)、序列前向选择方法(把需要的特征集合先初始化成一个空集，每一次向特征集合中增加一个特征直到达到最后的特征集。)、序列后向选择方法(首先假定整个特征集合就是所需要的优化特征集，然后在算法的每一步运行过程中删除一个对准则函数没有贡献的特征，直到剩余特征的个数符合问题要求。)、增l去r选择方法(其本质为序列前向以及后向的结合，但该方法比序列后向选择方法运算速度更快，比序列前向选择方法运算效果更好)。

3.2. 集合评价策略

3.2.1. 基于滤波(Filter)评价策略 [8] 的特征选择算法

在滤波评价策略中，其中一种为Fscore方法 [9] [10]，首先对特征进行评分，其中利用到的是费舍尔准则，然后根据特征被评的分数来确定特征的好坏。类内距离越小，类间距离则越大，则特征分值越高，这意味着该特征有越强的分类特征。在选择子集时，将每个特征的得分由高到低的进行排序，最后根据问题的要求，选取分值最高的k个特征作为选择出的最优特征集。

Fscore评估准则可利用以下公式：

$S{C}_F\left(f_i\right)=\frac{{\displaystyle \underset{j=1}{\overset{C}{\sum }}{n}_j{\left({\mu }_j^i-{\mu }^i\right)}^2}}{{\displaystyle \underset{j=1}{\overset{C}{\sum }}{n}_j{\sigma }_j^{i2}}}$

其中， $f_i$ 表示第i个特征， ${\mu }^i$ 是特征 $f_i$ 的均值， $n_j$ 是第j类样本的数目， ${\mu }_j^i$ 表示第j类的特征 $f_i$ 的均值 ${\sigma }_j^i$ 表示第j类的特征 $f_i$ 的方差。Fscore特征选择算法具体表示为以下步骤：

1) 计算每类训练样本集总体均值： ${\mu }_j^i$ ；

2) 计算训练样本集总体均值： ${\mu }^i$ ；

3) 计算每个特征的评分： $S{C}_F\left(f_i\right)$ ；

4) 根据特征评分，对特征进行降序排列；

5) 选取前k个特征作为最终的特征集。

3.2.2. 基于打包(Wrapper)评价策略的特征选择算法

打包方法和其所使用的分类器息息相关，在筛选特征的过程中，它直接利用所选的特征来训练分类器，并且根据这个分类器在验证集上的特点来评价所选择的特征。其中，有利用决策树进行特征选择、Fisher判别分析结合遗传算法、结合极大似然模型进行特征选择、用遗传算法结合人工神经网络等进行特征选择的方法都取得了良好的效果 [11] [12]。最值得注意的是，Wrapper方法进行特征选择时都需要有良好的分类器作为基础，接下来，本文主要介绍目前的一项热点研究：用支持向量机进行特征选择。

4. 支持向量机(SVM)

支持向量机为一种二分类方法，目的是构造一个超平面能够使得样本点距离该超平面的距离能够最大化，超平面通常构造为线性方程： ${\omega }^{\text{T}}x+b=0$ 。样本中距离超平面最近的一些点叫做支持向量，支持

向量与超平面之间的距离为： $d=\frac{\left|{\omega }^{\text{T}}x+b\right|}{\Vert \omega \Vert }$ ，变量y用来判断分类正确与否，正确时 $y=1$ ，错误时，则

有 $y=-1$ 。我们想要最大化这个距离：

$\max \frac{y\left({\omega }^{\text{T}}x+b\right)}{\Vert \omega \Vert }$

通过转换，我们得到最优化问题：

$\begin{array}{l}\min \frac{1}{2}{\Vert \omega \Vert }^2\\ \text{s}\text{.t}.y_i\left({\omega }^{\text{T}}{x}_i+b\right)\ge 1\end{array}$ 。

一般情况下，我们用Lagrange乘子法进行求解。

5. 基于支持向量机(SVM)与凹函数构造的特征选择

前文中提到求解支持向量机模型通常采用Lagrange乘子法，在求对偶问题时，研究者们发现，稀疏变量 $\alpha$ 可利于样本稀疏化，达到提高运算效率，减少运算时间的目的。同样可得到：稀疏变量 $\omega$ 可得到特征稀疏化，Shao等人 [13] 同时加入特征稀疏项 $\omega$ 和样本稀疏项 $\alpha$ ，得到了稀疏的对偶最小二乘支持向量机(SPDLSSVM)：

$\begin{array}{l}\underset{\omega ,\alpha }{\min }\frac{1}{2}{\Vert \omega \Vert }_2^2+C_1{\Vert \omega \Vert }_1+\frac{C}{2}{\Vert B^{\text{T}}\omega -e\Vert }_2^2+C_2{\Vert \alpha \Vert }_1+\frac{1}{2}{\alpha }^{\text{T}}\left(YX{X}^{\text{T}}{Y}^{\text{T}}+\frac{1}{C}I\right)\alpha -e^{\text{T}}\alpha \\ \text{s}\text{.t}\text{.}\omega -B\alpha =0\end{array}$

其中， $\omega$ 和 $\alpha$ 都采用了 $l_1$ 范数进行稀疏化，接着使用交替方向乘子法(ADMM)求出了模型的最优解，并且用MATLAB进行数值实验在多个数据集上SPDLSSVM模型虽然训练时间比其余模型长一点，但都筛选到了最少的特征以及样本，同时分类准确率也是最好的，所以SPDLSSVM模型在特征选择、样本选择，以及分类效果上都有着优异的表现。

在文章 [14] 中，作者介绍了用凹函数法和SVM进行特征选择，凹函数法将目标函数转化成了：

$\begin{array}{l}\underset{\omega ,\gamma ,y,z,v}{\min }\left(1-\lambda \right)\left(\frac{e^{\text{T}}y}{m}+\frac{e^{\text{T}}z}{k}\right)+\lambda e^{\text{T}}\left(e-{\epsilon }^{-\alpha v}\right)\\ \text{s}\text{.t}\text{.}-A\omega +e\gamma +e\le y,\\ B\omega -e\gamma +e\le z,\\ y\ge 0,z\ge 0,\\ -v\le \omega \le v\end{array}$

基于这个出发点，作者用SVM的方法同样得到了特征选择的模型：

$\begin{array}{l}\underset{\omega ,\gamma ,y,z,v}{\min }\left(1-\lambda \right)\left(e^{\text{T}}y+e^{\text{T}}z\right)+\frac{\lambda }{2}{\Vert \omega \Vert }^{\prime }\\ \text{s}\text{.t}\text{.}-A\omega +e\gamma +e\le y,\\ B\omega -e\gamma +e\le z,\\ y\ge 0,z\ge 0\end{array}$

其中， ${\Vert \omega \Vert }^{\prime }$ 表示为对偶范数，以此来获得较少的特征。

该文用连续线性算法对凹函数模型进行了求解，并且与 $l_1$ 、 $l_2$ 、 $l_{\infty }$ 范数下的SVM模型、序列化方法(RLP)在6个公开数据集上进行了实验对比，可以看出该文章提出的凹函数模型在6个公开数据集上都选择出了最少的特征并且在其中3个数据集上都取得了最高的测试分类准确率，由此可得出该凹函数模型不仅能够得到最少的特征个数，还能够保证一定优秀的分类效果。

在文章 [15] 中，通过建立非线性核支持向量机来进行特征选择，本质上是引入了一个核函数 $K\left(A,A^{\prime }\right)$ ，将 $R^{m\times n}\times R^{n\times l}$ 映射到 $R^{m\times l}$ 中，从而将分类问题转化为以下的线性规划问题：

$\begin{array}{l}\underset{u,\gamma ,y,s}{\min }v{e}^{\prime }y+e^{\prime }s\\ \text{s}\text{.t}\text{.}D\left(K\left(A,A^{\prime }\right)u-e\gamma \right)+y\ge e\\ -s\le u\le s,\\ y\ge 0\end{array}$

其中，v是一个用来测量误分率的非负参数，易知： $e^{\prime }y={\Vert y\Vert }_1$ ， $e^{\prime }s={\Vert s\Vert }_1$ ，为使输入空间中样本的维数尽可能得小，引入了一个对角矩阵 $E\in R^{n\times n}$ ，其中主对角线上元素为0或1，0对应的是被删除掉的样本特征，1对应的是被保留的样本特征，则此时分类器变为： $K\left(x^{\prime }E,E{A}^{\prime }\right)u-\gamma =0$ ，上面的线性规划也就变成了下面的混合整数规划：

$\begin{array}{l}\underset{u,\gamma ,y,s,E}{\min }v{e}^{\prime }y+e^{\prime }s+\sigma e^{\prime }Ee\\ \text{s}\text{.t}.D\left(K\left(AE,E{A}^{\prime }\right)u-e\gamma \right)+y\ge e,\\ -s\le u\le s,\\ y\ge 0,\\ E=diag\left(1\text{or}0\right)\end{array}$

其中， $\sigma$ 是一个对特征抑制项进行加权的非负参数， $e^{\prime }Ee={\displaystyle \underset{i=1}{\overset{n}{\sum }}{E}_{ii}}$ 。混合整数规划也是一个NP-难问题，

文章 [15] 也提出了一种减少特征支持向量机(RFSVM)来对模型进行求解。在此文中，作者在UCI数据集上对比了在(RFSVM)、回归特征消除法(RFE)和浮雕法(Relief) (一种用于特征筛选的方法)这三种算法下特征选择个数与分类结果，结果显示该模型都得到了更少的特征和更高的分类准确率。

文章 [16] 提出了MICReliefF算法并且以支持向量机模型分类的准确率作为评价指标，实现了MICReliefF算法和分类模型的交互优化，并且在多个UCI公开数据集上对该算法的性能做了实验。结果表现出MICReliefF-SVM自动特征选择算法不仅可以筛除更多的冗余特征，而且可以选择出具有良好稳定性和泛化能力的特征子集。与随机森林、最大相关最小冗余、相关性特征选择等特征选择算法相比，此算法具有更高的分类准确率。

6. 结论

本文主要介绍了特征选择的相关概念及模型，并且介绍了当前研究的重点内容：支持向量机模型 [17]，然后将二者结合起来，即由支持向量机作为分类器进行特征选择的模型 [18]，为了进行特征选择，研究者们构建了线性规划模型、混合整数规划模型、二次规划模型等 [19]，但目前随着对于支持向量机模型对于特征选择应用的研究越来越深入 [20] [21] [22] [23] [24]，研究者们发现可以用稀疏优化支持向量机的系数来进行特征选择，即构建出加入 $l_0$ 范数的模型，但由于目标函数因此变得非凸非光滑，该问题也就成为了NP-难问题。很多学者将 $l_0$ 范数近似为 $l_1$ 范数来进行求解 [25]，而直接求解 $l_0$ 范数问题取决于非凸优化的发展理论，同时此类问题的研究也成为了当前研究的热点问题。 $l_0$ 范数也具有较强的模型解释性以及实用性，因此在 $l_0$ 范数上进行理论与计算创新也是本文作者今后的努力方向。