第9章

特征选择

9.1 引言

前面几章中讨论了多种分类器的设计方法。在这些方法中，我们都假定已经有一组用来描述对象性质的特征，每个样本就是用一组特征来表示的。我们考虑较多的是数值特征，即每一个特征是一个实数，决策树等方法则可以处理非数值特征。

这些特征都是通过对研究对象的直接或间接观察得到的。一个模式识别系统的成败，首先取决于所利用的特征是否较好地反映了将要研究的分类问题。因此，如何设计和获取特征是一个实际模式识别系统的第一步。这一步工作需要结合分类的目标根据相应领域的专业知识来决定，同时也受到有关领域的观测手段和技术的影响。我们把这一过程称作特征的生成或特征获取，所得到的特征可以称作一次特征或原始特征。这些特征可以是由仪器直接测量出来的数值，例如对象的一些物理量，也可以是根据仪器的数据进行了计算后的结果。例如，如果要利用图像对细胞进行分类，区分正常的细胞和异常的细胞，则可以直接把CCD得到的图像像素作为特征，如果图像大小是 $ 256 \times 256 $像素，则特征就是65536维；而更多的情况下，是根据对细胞图像的认识计算出一些新的特征，例如细胞总面积、总光密度、胞核面积、核浆比、细胞形状、核内纹理等，这些特征的维数可能远小于像素数，但却可以更好地反映样本的性质。

特征的获取是依赖于具体的问题和相关专业的知识的，无法进行一般性的讨论。从模式识别角度，很多情况下人们面对的是已经得到的一组特征，或者是利用当时的技术手段把所有有可能观测到的特征都记录下来。这时，这些特征中可能有很多特征与要解决的分类问题关系并不密切，它们在后续的分类器设计中可能会影响分类器的性能。另外，有时即使很多特征都与分类关系密切，但是特征过多会带来计算量大、推广能力差等问题，在样本数目有限时很多方法甚至会因为出现病态矩阵等问题而根本无法计算，因此人们也往往希望

在保证分类效果的前提下用尽可能少的特征来完成分类。

模式识别中的特征选择的问题，就是指在模式识别问题中，用计算的方法从一组给定的特征中选择一部分特征进行分类。这是降低特征空间维数的一种基本方法。本章只讨论数量型特征的选择。在第8章介绍的决策树方法实际是把非数量特征的选择与分类同时考虑。

另一种把特征空间降维的方法是特征提取，将在第10章进行讨论。

9.2 用于分类的特征评价准则

要进行特征选择，首先要确定选择的准则，也就是如何评价选出的一组特征。确定了评价准则后，特征选择问题就变成从D个特征中选择出使准则函数最优的d个特征 $ (d

从概念上，我们希望选择出的特征能够最有利于分类，因此，利用分类器的错误率作为准则是最直接的想法。但是，这种准则在很多实际问题中并不一定可行：从理论上，即使概率密度函数已知，错误率的计算也非常复杂，而实际中多数情况下样本的概率密度未知，计算分类器的错误率就更困难；如果用样本对错误率进行实验估计，则由于需要采用交叉验证等方法，将大大增加计算量。

因此，需要定义与错误率有一定关系但又便于计算的类别可分性准则 $ J_{ij} $，用来衡量在一组特征下第 i 类和第 j 类之间的可分程度。这样的判据应该满足以下几个要求：

（1）判据应该与错误率（或错误率的上界）有单调关系，这样才能较好地反映分类目标。

（2）当特征独立时，判据对特征应该具有可加性，即

$$ J_{ij}(x_{1},x_{2},\cdots,x_{d})=\sum_{k=1}^{d}J_{ij}(x_{k}) $$

这里 $ J_{ij} $ 是第 i 类和第 j 类的可分性准则函数， $ J_{ij} $ 越大，两类的分离程度就越大， $ x_{1}, x_{2}, \cdots, x_{d} $ 是一系列特征变量。

（3）判据应该具有以下度量特性

$$ J_{ij}>0,\quad 当 \;i\neq j\; 时 $$

$$ J_{ij}=0,\quad 当 \;i=j\; 时 $$

$$ J_{ij}=\boldsymbol{J}_{ji} $$

（4）理想的判据应该对特征具有单调性，即加入新的特征不会使判据减小，即

$$ J_{ij}(x_{1},x_{2},\cdots,x_{d})\leqslant J_{ij}(x_{1},x_{2},\cdots,x_{d},x_{d+1}) $$

如果类别可分性判据满足上述条件且比较便于计算，就可以较好地用来作为特征选择的标准。但实际情况下，其中的某些要求并不一定容易满足。在过去的研究中，人们提出了很多不同的判据，下面介绍几类常用的判据。

9.2.1 基于类内类间距离的可分性判据

在第5章中介绍的 Fisher 线性判别方法，采用了样本投影到一维使投影后的类内离散度尽可能小、类间离散度尽可能大的准则来确定最佳的投影方向，这其实就是一个直观的类

别可分性判据。在特征选择问题中，我们可以借鉴类似的思想来定义一系列基于样本在特征上的类内类间距离的判据。

直观上考虑，可以用两类中任意两两样本间的距离的平均来代表两个类之间的距离。现在推导多类情况下的这种判据。

令 $ x_{k}^{(i)} $, $ x_{l}^{(j)} $ 分别为 $ \omega_{i} $ 类及 $ \omega_{j} $ 类中的 D 维特征向量， $ \delta(x_{k}^{(i)}, x_{l}^{(j)}) $ 为这两个向量间的距离，则各类特征向量之间的平均距离为

$$ J_{d}(x)=\frac{1}{2}\sum_{i=1}^{c}P_{i}\sum_{j=1}^{c}P_{j}\frac{1}{n_{i}n_{j}}\sum_{k=1}^{n_{i}}\sum_{l=1}^{n_{j}}\delta(x_{k}^{(i)},x_{l}^{(j)}) $$

式中 c 为类别数， $ n_{i} $ 为 $ \omega_{i} $ 类中样本数， $ n_{j} $ 为 $ \omega_{j} $ 类中样本数， $ P_{i} $、 $ P_{j} $ 是相应类别的先验概率。

多维空间中两个向量之间有很多种距离度量，在欧氏距离情况下有

$$ \delta(\mathbf{x}_{k}^{(i)},\mathbf{x}_{l}^{(j)})=(\mathbf{x}_{k}^{(i)}-\mathbf{x}_{l}^{(j)})^{\mathrm{T}}(\mathbf{x}_{k}^{(i)}-\mathbf{x}_{l}^{(j)}) $$

用 $ m_{i} $表示第i类样本集的均值向量

$$ m_{i}=\frac{1}{n}\sum_{k=1}^{n_{i}}x_{k}^{(i)} $$

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

$$ m=\sum_{i=1}^{c}P_{i}m_{i} $$

将式(9-2)、式(9-3)、式(9-4)代入式(9-1)得

$$ J_{d}(x)=\sum_{i=1}^{c}P_{i}\left[\frac{1}{n_{i}}\sum_{k=1}^{n_{i}}(x_{k}^{(i)}-m_{i})^{\mathrm{T}}(x_{k}^{(i)}-m_{i})+(m_{i}-m)^{\mathrm{T}}(m_{i}-m)\right] $$

上式中括号内的第二项是第i类的均值向量与总体均值向量m之间的平方距离，用先验概率加权平均后可以代表各类均值向量的平均平方距离

$$ \sum_{i=1}^{c}P_{i}\left(m_{i}-m\right)^{\mathrm{T}}\left(m_{i}-m\right)=\frac{1}{2}\sum_{i=1}^{c}P_{i}\sum_{j=1}^{c}P_{j}\left(m_{i}-m_{j}\right)^{\mathrm{T}}\left(m_{i}-m_{j}\right) $$

也可以用下面定义的矩阵写出 $ J_{d}(x) $的表达式。

令

$$ \widetilde{S}_{\mathrm{b}}=\sum_{i=1}^{c}P_{i}\left(m_{i}-m\right)\left(m_{i}-m\right)^{\mathrm{T}} $$

以及

$$ \widetilde{S}_{\mathrm{w}}=\sum_{i=1}^{c}P_{i}\frac{1}{n_{i}}_{k=1}^{n_{i}}(x_{k}^{(i)}-m_{i})(x_{k}^{(i)}-m_{i})^{\mathrm{T}} $$

则

$$ J_{d}(x)=\mathrm{t r}(\tilde{S}_{w}+\tilde{S}_{b}) $$

上面的推导是建立在有限样本集上的，式中的 $ m_{i} $、 $ m_{i} $、 $ \tilde{S}_{b} $、 $ \tilde{S}_{w} $ 是对类均值 $ \mu_{i} $、总体均值 $ \mu $、类间离散度矩阵 $ S_{b} $ 和类内离散度矩阵 $ S_{w} $ 在样本基础上的估计， $ \mu_{i} $、 $ \mu $、 $ S_{b} $ 和 $ S_{w} $ 的表达式如下

$$ \mu_{i}=E_{i}[x] $$

$$ \mu=E[x] $$

$$ S_{\mathrm{b}}=\sum_{i=1}^{c}P_{i}(\boldsymbol{\mu}_{i}-\boldsymbol{\mu})(\boldsymbol{\mu}_{i}-\boldsymbol{\mu})^{\mathrm{T}} $$

$$ S_{\mathrm{w}}=\sum_{i=1}^{c}P_{i}E_{i}\left[(\boldsymbol{x}-\boldsymbol{\mu}_{i})(\boldsymbol{x}-\boldsymbol{\mu}_{i})^{\mathrm{T}}\right] $$

各类之间的平均平方距离也可表示为

$$ J_{d}(x)=\mathrm{t r}(S_{w}+S_{b}) $$

除了这种平均平方距离判据，还可以定义一系列类似的基于类内类间距离的判据。较常见的有

$$ \begin{aligned}&J_{1}=\mathrm{tr}(\boldsymbol{S}_{\mathrm{w}}+\boldsymbol{S}_{\mathrm{b}})\\&J_{2}=\mathrm{tr}(\boldsymbol{S}_{\mathrm{w}}^{-1}\boldsymbol{S}_{\mathrm{b}})\\ \end{aligned} $$

$$ J_{3}=\ln\frac{\left|S_{\mathrm{b}}\right|}{\left|S_{\mathrm{w}}\right|} $$

$$ J_{4}=\frac{\mathrm{t r}\pmb{S}_{\mathrm{b}}}{\mathrm{t r}\pmb{S}_{\mathrm{w}}} $$

$$ J_{5}=\frac{\left|S_{\mathrm{b}}-S_{\mathrm{w}}\right|}{\left|S_{\mathrm{w}}\right|} $$

其中， $ J_{1} $ 就是 $ J_{d} $。这些判据都有一个共同的特点，就是定义直观、易于实现，因此比较常用。而且，不同判据计算的数值虽然不同，但是对特征的排序是相同的，因此，选用其中不同的具体形式只是会在计算上不一样，结果是一致的。

这些基于距离的判据也有自身的缺陷，就是很难在理论上建立起它们与分类错误率的联系，而且当两类样本的分布有重叠时，这些判据不能反映重叠的情况。当各类样本分布的协方差差别不大时，使用这些特征可以取得较好的效果。

9.2.2 基于概率分布的可分性判据

上面介绍的类别可分性判据是基于样本间的距离的，没有直接考虑样本的分布情况，很难与错误率建立直接的联系。为了考查在不同特征下两类样本概率分布的情况，人们定义了基于概率分布的可分性判据。

先研究两类的情况：如图9-1所示，其中图9-1(a)为完全可分的情况，图9-1(b)为完全不可分情况。

假定先验概率相等，若对所有使 $ p(x|\omega_{2})\neq0 $ 的点有 $ p(x|\omega_{1})=0 $，如图9-1(a)所示，则两类为完全可分的；相反，如果对所有 x 都有 $ p(x|\omega_{1})=p(x|\omega_{2}) $，如图9-1(b)所示，则两类完全不可分。

分布密度的交叠程度可用 $ p(x|\omega_{1}) $ 及 $ p(x|\omega_{2}) $ 这两个分布密度函数之间的距离 $ J_{p} $ 来度量。任何函数 $ J(\cdot)=\int g[p(x|\omega_{1}),p(x|\omega_{2}),P_{1},P_{2}]\mathrm{d}x $，如果满足下述条件：

（1） $ J_{p} $ 为非负，即 $ J_{p} \geqslant 0 $；

（2）当两类完全不交叠时 $ J_{p} $ 取最大值，即若对所有 x 有 $ p(x|\omega_{2})\neq0 $ 时 $ p(x|\omega_{1})=0 $ 则 $ J_{p}=Max $;

（3）当两类分布密度相同时， $ J_{p} $ 应为零，即若 $ p(x|\omega_{1})=p(x|\omega_{2}) $，则 $ J_{p}=0 $，则都可用来作为类分离性的概率距离度量。

下面列出几种常用的概率距离度量。

Bhattacharyya 距离

$$ J_{\mathrm{~B~}}=-\ln\int\left[p\left(x\mid\omega_{1}\right)p\left(x\mid\omega_{2}\right)\right]^{\frac{1}{2}}\mathrm{d}x $$

直观的分析可以看出，当两类概率密度函数完全重合时， $ J_{B}=0 $；而当两类概率密度完全没有交叠时， $ J_{B}=\infty $。经过简单的推导可以得出，理论上的错误率 $ P_{e} $ 与 Bhattacharyya 距离之间有如下关系

$$ P_{\mathrm{e}}\leqslant\left[P(\omega_{1})P(\omega_{2})\right]^{\frac{1}{2}}\exp\{-J_{\mathrm{B}}\} $$

推导过程读者可以作为课外练习。

Chernoff 界限

$$ J_{c}=-\ln\int P^{s}\left(x\mid\omega_{1}\right)P^{1-s}\left(x\mid\omega_{2}\right)\mathrm{d}x $$

其中，s 是在 [0,1] 区间内的一个参数。显然，当 s=0.5 时，Chernoff 界限与 Bhattacharyya 距离相同。

散度

在第2章已经看到，两类概率密度函数的似然比对于分类是一个重要的度量，人们在似然比的基础上定义了以下的散度作为类别可分性的度量

$$ J_{D}=\int_{x}\left[p\left(x\mid\omega_{1}\right)-p\left(x\mid\omega_{2}\right)\right]\ln\frac{p\left(x\mid\omega_{1}\right)}{p\left(x\mid\omega_{2}\right)}\mathrm{d}x $$

不难得出，在两类样本都服从正态分布的情况下，散度为

$$ J_{\mathrm{~D~}}=\frac{1}{2}\mathrm{t r}\left[\mathbf{\Sigma}_{1}^{-1}\mathbf{\Sigma}_{2}+\mathbf{\Sigma}_{2}^{-1}\mathbf{\Sigma}_{1}-2I\right]+\frac{1}{2}(\boldsymbol{\mu}_{1}-\boldsymbol{\mu}_{2})^{\mathrm{~T}}(\mathbf{\Sigma}_{1}^{-1}+\mathbf{\Sigma}_{2}^{-1})(\boldsymbol{\mu}_{1}-\boldsymbol{\mu}_{2}) $$

其中， $ \mu_{1} $、 $ \mu_{2} $、 $ \Sigma_{1} $、 $ \Sigma_{2} $ 分别是两类的均值向量和协方差矩阵。特别地，当两类协方差矩阵相等时，Bhattacharyya 距离和散度之间有如下关系

$$ \boldsymbol{J}_{\mathrm{~D~}}=(\boldsymbol{\mu}_{1}-\boldsymbol{\mu}_{2})^{\mathrm{~T~}}\boldsymbol{\Sigma}^{-1}(\boldsymbol{\mu}_{1}-\boldsymbol{\mu}_{2})=8\boldsymbol{J}_{\mathrm{~B~}} $$

这也等于两类均值之间的 Mahalanobis 距离。

上面给出的是考查两类概率密度函数之间距离的一些准则，与此类似，也可以定义类条件概率密度函数与总体概率密度函数之间的差别，用来衡量一个类别与各类混合的样本总体的可分离程度。考查特征 x 与类 $ \omega_{i} $ 的联合概率密度函数

$$ p\left(x,\omega\right)=p\left(x\mid\omega_{i}\right)P\left(\omega_{i}\right) $$

如果 x 与类 $ \omega_{i} $ 独立，则 $ p(x,\omega_{i})=p(x)P(\omega_{i}) $，即 $ p(x)=p(x|\omega_{i}) $，特征 x 不提供分类 $ \omega_{i} $ 的信息。 $ p(x|\omega_{i}) $ 与 $ p(x) $ 差别越大，则 x 提供的分类信息越多。因此，可以用 $ p(x|\omega_{i}) $ 与 $ p(x) $ 之间的函数距离作为特征对分类贡献的判据

$$ J_{i}=\int g(p(x|\omega_{i}),p(x),P(\omega_{i}))\mathrm{d}x $$

称作概率相关性判据。对上面介绍的每一种概率密度距离判据，都可以得到对应的概率相关性判据，只需把式(7-12)、式(7-14)、式(7-15)中的 $ p(x|\omega_{1}) $ 换成 $ p(x|\omega_{i}) $、 $ p(x|\omega_{2}) $ 换成 $ p(x) $ 即可。

9.2.3 基于熵的可分性判据

特征对分类的有效性也可以从后验概率角度来考虑。

现在来看一个极端的例子。设有 c 个类别，对特征的某一取值 x，若样本属于各类的后验概率相等，即

$$ P\left(\omega_{i}\mid x\right)=\frac{1}{c} $$

则从该特征无法判断样本属于哪一类，错误概率为 $ (c-1)/c $。若对另外一种情况，有

$$ P(\omega_{i}\mid\boldsymbol{x})=1,\quad 且 P(\omega_{j}\mid\boldsymbol{x})=0,\quad\forall j\neq i $$

则此时样本肯定属于 $ \omega_{i} $类，错误概率为0。

因此，在特征的某个取值下，如果样本属于各类的后验概率越平均，则该特征越不利于分类；如果后验概率越集中于某一类，则特征越有利于分类。

为了衡量各类后验概率的集中程度，人们借用信息论中熵的概念定义了类别可分性的判据。下面来看熵的概念。

把类别 $ \omega_{i}, i=1,\cdots,c $ 看作是一系列随机事件，它的发生依赖于随机向量 x，给定 x 后 $ \omega_{i} $ 的后验概率是 $ P(\omega_{i}|x) $。如果根据 x 能完全确定 $ \omega $，则 $ \omega $ 就没有不确定性，对 $ \omega $ 本身的观察就不会再提供信息量，此时熵为 0，特征最有利于分类；如果 x 完全不能确定 $ \omega $，则 $ \omega $ 不确定性最大，对 $ \omega $ 本身的观察所提供信息量最大，此时熵为最大，特征最不利于分类。

人们常用的熵度量有：

Shannon 摘

$$ H=-\sum_{i=1}^{c}P(\omega_{i}\left|\boldsymbol{x}\right)\log_{2}P(\omega_{i}\left|\boldsymbol{x}\right) $$

平方熵

$$ H=2\left[1-\sum_{i=1}^{c}P^{2}(\omega_{i}\left|x\right.)\right] $$

在这些熵的基础上，对特征的所有取值积分，就得到基于熵的可分性判据

$$ J_{E}=\int H(x)p(x)\mathrm{d}x $$

$ J_{E} $ 越小，可分性越好。

9.2.4 利用统计检验作为可分性判据

在统计学中，检验某一变量在两类样本间是否存在显著差异是一个经典的假设检验问题，有很多成熟的方法，例如在数据正态分布假设下的 t-检验方法、不对数据分布做特殊假设的秩和检验方法等。这些方法可以给出一个统计量来反映两类样本间的差别，并给出一个 p-值来反映这种差异的统计显著性，即在两类样本没有差异的前提下，有多大的概率能够在一组随机的样本中出现实际得到的差别。

从分类角度看，显然希望用于分类的特征是在两类间有显著差别的，因此可以使用这些统计量来作为特征选择时衡量特征分类能力的度量。下面简要介绍t-检验和秩和检验的基本思想，更多统计检验的内容请读者学习有关统计学教材。

统计检验的基本思想是从样本计算某一能反映待检验假设的统计量，在比较两组样本（两类样本）时就是用这个统计量来衡量两组样本之间的差别。把所研究的问题定义为待检验的假设，例如两类样本在所研究特征上有显著差异。首先假定不存在这样的差异，这称作空假设（null hypothesis），根据对数据分布的一定的理论模型，计算在这种空假设下统计量取值的分布，称作统计量的空分布。待检验的假设称作备择假设（alternative hypothesis），在这里就是两类样本存在显著的差异。考查在实际观察到的样本数据上该统计量的取值，根据空分布计算在空假设下有多大的概率会得到这样的取值，如果这个概率很小，则可以推断空假设不成立，拒绝空假设，接受备择假设；反之则接受空假设，认为在这些样本上没有表现出两类间有显著差别。这一概率值称作p-值（p-value）。对样本分布采用不同的模型，就得到不同的统计检验方法。

最常用的比较两组样本差别的方法是 t-检验(t-test)，其基本假设是两类样本都服从正态分布，且方差相同。设有两类分别有 m 个和 n 个样本， $ \{x_{i}, i=1,\cdots,m\}, x_{i} \sim N(\mu_{x}, \sigma^{2}) $ 和 $ \{y_{i}, i=1,\cdots,n\}, y_{i} \sim N(\mu_{y}, \sigma^{2}) $。注意，它们都是在同一特征上的观测，我们用 x、y 来表示是为了讨论方便。它们的总体样本方差是

$$ s_{\mathrm{p}}^{2}=\frac{(n-1)S_{\mathrm{x}}^{2}+(m-1)S_{\mathrm{y}}^{2}}{m+n-2} $$

其中， $ S_{x}^{2} $ 和 $ S_{y}^{2} $ 分别是两类样本各自的估计方差，两类样本的均值分别记为 $ \bar{x} $ 和 $ \bar{y} $。t-检验的统计量是

$$ t=\frac{\bar{x}-\bar{y}}{s_{\mathrm{p}}\sqrt{\frac{1}{n}+\frac{1}{m}}} $$

它服从自由度为 $ n+m-2 $ 的 t 分布。双边 t-检验的空假设是两类均值相同，即 $ \mu_{x}=\mu_{y} $，备择假设是 $ \mu_{x}\neq\mu_{y} $。计算出在实际样本上的 t 值后，根据 t 分布可以查出在空假设下取得该 t 值的 p-值，根据适当的显著性水平（如 0.05 或 0.01）来决定是否拒绝空假设，推断在该特征上两类样本的均值是否有显著差异。在模式识别中，就可以依据这种差异来进行特征选择。如果期待该特征在一类中的均值大于在另一类中的均值，则可以使用单边 t-检验，此时空假设是 $ \mu_{x}\leq\mu_{y} $，而备择假设是 $ \mu_{x}>\mu_{y} $。

t-检验属于参数化检验方法，此类方法对数据分布有一定的假设，必要时需要首先检验

样本分布是否符合该假设。另一类统计检验方法是非参数检验，它们不对数据分布作特殊假设，因而能适用于更复杂的数据分布情况。其中最有代表性的是 Wilcoxon 秩和检验 (rank-sum test)，有时也叫做 Mann-Whitney U 检验。当数据实际上满足正态分布时，用 t-检验更有效。

秩和检验的做法是，首先把两类样本混合在一起，对所有样本按照所考查的特征从小到大排序，第一名排序为1，第二名排序为2，依次类推，如果出现特征取值相等的样本时则并列采用中间的排序。在两类样本中分别计算所得排序序号之和 $ T_{1} $和 $ T_{2} $，称作秩和。两类的样本数分别为 $ n_{1} $和 $ n_{2} $。秩和检验的基本思想就是，如果一类样本的秩和显著地比另一类样本小（或大），则两类样本在所考查的特征上有显著差异。秩和检验的统计量就是某一类（例如第一类，秩和为 $ T_{1} $）的秩和。

为了考查某一类的秩和是否显著小于（或大于）另一类的秩和，需要研究当两类没有显著差异时由于随机因素造成的秩和的分布。不同样本数目情况下T的空分布是不同的。对于小的样本数，人们预先计算出了T的分布，在常用的统计教科书中即可查到。当 $ n_{1} $和 $ n_{2} $较大时（例如都大于10），人们可以用正态分布 $ N(\mu_{1},\sigma_{1}) $来近似秩和 $ T_{1} $的空分布，其中

$$ \mu_{1}=\frac{n_{1}(n_{1}+n_{2}+1)}{2},\quad\sigma_{1}=\sqrt{\frac{n_{1}n_{2}(n_{1}+n_{2}+1)}{12}} $$

与 t-检验相比，秩和检验没有对样本分布做任何假设，适用于更广泛的情况。但是，如果样本服从正态分布，则秩和检验在敏感性上逊色于 t-检验。另外一个区别是，t-检验的目的是检验两类样本在特征的均值上是否有系统差别，而秩和检验不但受两类分布的均值的影响，也受到分布形状的影响。

在统计学中还有很多其他的检验，它们各自有自己的特点和适用范围，读者可以进一步学习相关的统计学教材。

与前面介绍的类别可分性判据不同的是，基于统计检验来判断特征对分类的贡献通常都是只能针对单个特征。虽然也有一些针对多变量的统计检验方法，但是当特征维数很高时往往很难实现。因此，人们如果用统计检验的方法来选择特征，通常就是按照每一个特征的统计检验结果排序，不考虑特征之间可能的相关性或共同作用。

在一些近年来的文献中，尤其是在生物信息学领域利用特征选择方法来选择有意义的基因的问题里，人们往往把这类特征选择方法称作过滤方法(filtering methods)，指依据一定的统计量来过滤出与所研究的分类问题密切相关的特征，再采用一定的分类方法进行分类。这种方法实现起来比较简单，但是，所采用的过滤准则与后期分类器所采用的准则并不一定有很好的联系。

9.3 特征选择的最优算法

一个理想的特征选择方法，应该能够从给定的 D 个特征中根据某种判据准则选择出 d < D 个特征，使在这 d 个特征上该准则最优。在上一节介绍的可分性判据中，除了逐一考虑每个单独的特征的统计检验判据外，其余判据都是定义在特征向量上的，需要从 D 个特

征选择出最优的特征组合。

在确定了选择的标准后，这就是一个搜索问题。在 D 个特征中选择 d 个，共有 $ C_{D}^{d}=\frac{D!}{(D-d)!d!} $ 种可能，最基本的方法就是穷举所有这些可能，从中选择判据最优的组合。显然，这只有在特征总数不大，或者在 d 或 D-d 很小的情况下才有可能。例如，如果有 D=100 个候选特征，如果选择 d=2，则需要比较 4950 种组合；如果 d=3，则组合数为 161700；但是如果 d=10，组合数为 $ 1.73\times10^{13} $；如果 d=50，则组合数为 $ 1.01\times10^{29} $。因此，一般情况下，穷举的策略是不可行的。

一种不需要进行穷举但仍能取得最优解的方法是分枝定界(branch and bound)法。这是一种自顶向下的方法，即从包含所有候选特征开始，逐步去掉不被选中的特征。这种方法具有回溯的过程，能够考虑到所有可能的组合。

分枝定界法的基本思想是，设法将所有可能特征选择组合构建成一个树状的结构，按照特定的规律对树进行搜索，使得搜索过程尽可能早地可以达到最优解而不必遍历整个树。

要做到这一点，一个基本的要求是准则判据对特征具有单调性，即，如果有互相包含的特征组的序列

$$ \overline{X}_{1}\supset\overline{X}_{2}\supset\cdots\supset\overline{X}_{i} $$

则

$$ J\left(\overline{X}_{1}\right)\geqslant J\left(\overline{X}_{2}\right)\geqslant\cdots\geqslant J\left(\overline{X}_{i}\right) $$

即特征增多时判据值不会减小。理论上，前面介绍的基于距离的可分性判据和基于概率密度函数距离的判据都满足这一性质。

下面以从 D=6 个特征中选 d=2 个特征为例来描述用分枝定界法选择特征的步骤。

整个过程可以用一棵树来表示，如图 9-2 所示。树的根节点包含全部特征，称作第0级。每一级的节点在其父节点基础上去掉一个特征，我们把去掉特征的序号写在节点旁边。例如在图9-2中，在A节点上已经去掉了特征2和3。每一级去掉一个特征，所以共需要D-d级即达到所需要的特征数目，最底层的每个节点（叶节点）就代表最终特征选择的一种组合。在整个过程中，不出现相同组合的树枝和叶节点。

特征选择的过程就是生长这棵树的过程。对于第l层节点i，假定它包含 $ D_{i} $个候选特征，我们在同一层中按照去掉单个特征后的准则函数值来对各个结点排序，如果去掉某个特征后准则函数的损失量最大，则认为这个特征是最不可能被去掉的，把它放在该层的最左侧节点，把去掉之后带来损失量第二大的特征排在左侧第二个节点，依此类推。在图9-2的例子中，第一层生长3个节点。假定单个特征对可分性判据的影响从大到小排序是特征1、2、3、4、5、6，那么，第一层节点从左到右就应该是特征1、2、3。

第 $ l+1 $层的展开沿最右侧节点开始，在同层

上已经在左侧节点上的特征在本节点之下不再进行舍弃，因此，第 $ l+1 $层的一个节点上的候选特征就是它上一层的 $ D_{i} $个候选特征减去本节点上舍弃的特征以及它同层左侧节点上的特征。从每一树枝的最右侧开始向下生长，当到达叶节点时计算当前达到的准则函数值，记作界限B。

到达叶节点后算法向上回溯，每回溯一步把相应节点上舍弃的特征回收回来。遇到最近的分枝节点时停止回溯，从这个分枝节点向下搜索左侧最近的一个分枝。如果在搜索到某一个节点时，准则函数值已经小于界限B，则说明最优解已不可能在本节点之下的叶节点上，因此停止沿本树枝的搜索，从此节点重新向上回溯。如果搜索到一个新的叶节点，则更新界限B值，向上回溯。如果回溯过程一直到了根节点，而且根据界限B不能再向下搜索其他树枝，则算法停止，最后一次更新B时取得的特征组合就是特征选择的结果。

图9-2里画出的是一棵完整的树的例子。通常，并不会在把全部树都生长完毕后才找到最优解，而是在回溯过程的中间即会遇到终止条件。例如在图9-3中，算法在搜索完大约一半的节点后就停止了，最后得到的解是在搜索到的叶节点中最左侧的节点上的特征组合。这种树的生长和搜索策略使得算法能够尽可能早地终止，而且得到的组合是所有可能组合中最优的。

通常，在 d 大约为 D 的一半时，分枝定界法比穷举法节省的计算量最大。例如在某一个具体的例子中，从 12 个特征中选择 4 个，穷举法需要比较 495 种组合，而分枝定界法只比较了 42 种组合就得到了同样的结果；另外一个例子中，从 24 个特征里选择 12 个，穷举需要比较 2704 156 种组合，而分枝定界法只比较 13369 种组合就得到了最优解。在实际应用中，分枝定界法的计算量是与具体问题和数据有关的。

9.4 特征选择的次优算法

很多情况下，即使采用分枝定界法，最优搜索方法的计算量可能仍然很大，因此，人们在很多情况下会放弃采用最优方法，而采用一些计算量更小的次优搜索方法。这些方法都是基于一些直观的分析，实现起来很方便，在很多实际问题中也能取得很好的效果。

1. 单独最优特征的组合

最简单的特征选择方法就是对每一个特征单独计算类别可分性判据，根据单个特征的判据值排队，选择其中前d个特征。这种做法的假设就是单独作用时性能最优的特征，它

们组合起来也是性能最优的。显然，这种假设与很多实际情况可能不相符。即使是特征间统计独立时，单独最优特征的组合也不一定是最优的，这还与所采用的特征选择的准则函数有关，只有当所采用的判据是每个特征上的判据之和或之积时，这种做法选择出的才是最优的特征。

显然，如果采用7.2.4节介绍的基于单特征统计检验的判据作为特征选择的准则，实际上就是采用了选择单独最优特征的策略。

2. 顺序前进法 (sequential forward selection, SFS)

这是一种从底向上的方法。第一个特征选择单独最优的特征，第二个特征从其余所有特征中选择与第一个特征组合在一起后准则最优的特征，后面每一个特征都选择与已经入选的特征组合起来最优的特征。

与单独最优特征的选择方法相比，顺序前进法考虑了一定的特征间组合的因素，但是其第一个特征仍然是仅靠单个特征的准则来选择的，而且每个特征一旦入选后就无法再剔除，即使它与后面选择的特征并不是最优的组合。当然，SFS方法的计算量也比单独最优特征的选择要大。

还有一种广义顺序前进法（generalized sequential forward selection, GSFS），就是每一次不是选择一个新特征，而是选择 l 个新特征。这样可以考虑更多特征间的相关性，但计算量也比顺序前进法更大一些。

3. 顺序后退法（sequential backward selection, SBS）

这是一种从顶向下的方法，与顺序前进法相对应。从所有特征开始逐一剔除不被选中的特征。每次剔除的特征都是使得剩余的特征的准则函数值最优的特征。

同样也有广义顺序后退法(generalized sequential backward selection, GSBS)，每次不是剔除一个特征，而是剔除r个特征。

顺序后退法也考虑了特征间的组合，但是由于是从顶向下的方法，很多计算在高维空间进行，计算量比顺序前进法大些。顺序后退法在一旦剔除了某一特征后就无法再把它选入。

4. 增 l 减 r 法 (l-r 法)

顺序前进法的一个缺点是，某个特征一旦选中则不能再被剔除；而顺序后退法的一个缺点则是，某个特征一旦被剔除则不能再重新被选中。两种方法都是根据局部最优的准则挑选或者剔除特征，这样的缺陷就可能导致选择不到最优的特征组合。一种改善的方法是将两种做法结合起来，在选择或剔除过程中引入一个回溯的步骤，使得依据局部准则选择或剔除的某个特征有机会被因为与其他特征间的组合作用而重新被考虑。

如果采用从底向上的策略，则使 l > r，此时算法首先逐步增选 l 个特征，然后再逐步剔除 r 个与其他特征配合起来准则最差的特征，以此类推，直到选择到所需要数目的特征；如果采用从顶向下的策略，则 l < r，每次首先逐步剔除 r 个特征，然后再从已经被剔除的特征中逐步选择 l 个与其他特征组合起来准则最优的特征，直到剩余的特征数目达到所需的数目。

与广义顺序前进法和广义顺序后退法类似，我们在增 l 减 r 法中也可以不采用逐步增

选或剔除特征的策略，而是每次选择或剔除多个特征。这种做法称作 $ (Z_{l},Z_{r}) $法。这样做与l-r法相比能够既考虑到特征间的相关性又保持适当的计算量。

9.5 遗传算法

在确定了用何种类别可分性判据作为准则后，特征选择问题就是一个搜索的问题。穷举法和分枝定界法的出发点是比较所有可能的组合，从中选择出一组使准则最优的特征。上一节介绍的次优搜索方法都属于确定性的启发式方法，根据对特征直观的假设设计一定的搜索策略，使其在该假设下可以取得接近最优的结果。近些年来，人们发展了另外一类方法，就是随机搜索的方法。这类方法既不采用穷举的策略，也不采用确定的启发式搜索策略，而是对可能的解进行多次随机抽样，通过巧妙地设计随机采样的策略，使算法能够较快地搜索到最优或次优的解。遗传算法（genetic algorithm，GA）就是其中最有代表性的方法。

我们在本节中扼要介绍一下遗传算法的基本思想和特点。

遗传算法的思路来自人们对生物进化过程的认识。关于生物进化，人们目前比较普遍接受的认识是，每种生物的染色体都在以一定的概率发生各种突变和重组，这些突变和重组是随机发生的，它们统称为变异。生物生存的环境对变异的结果有选择的作用，如果一种变异导致生物能更好地适应环境，则这种变异就被保留下来传给后代；而如果一种变异导致生物对环境的适应性变差，这种变异就会逐渐消失。

这一思想在20世纪60年代被当时正在读博士研究生的John H. Holland借鉴到优化问题中，他把优化问题比喻为在无数可能的重组和突变组合中发现适应性最强的组合的问题，设计了一种特殊的搜索算法，模拟自然界中通过有性繁殖迅速增加群体多样性以更快地出现适应性强的组合的过程。当时有人戏称他的工作是“teaching computers how to have sex”。他的专著在1975年出版 $ ^{①} $，之后多次再版。遗传算法很快成为最有影响的优化算法之一，并且开创了一个新的领域——“进化计算”(evolutionary computing)。

遗传算法把候选的对象编码为一条染色体(chromosome)，例如在特征选择中，如果目标是从D个特征中选择d个，则把所有特征描述为一条由D个0/1字符组成的字符串，0代表该特征没有被选中，1代表该特征被选中，这个字符串就叫做染色体，记作m。显然，要求的是一条有且仅有d个1的染色体，这样的染色体共有 $ C_{D}^{d} $种。

优化的目标被描述成适应度(fitness)函数，每一条染色体对应一个适应度值 $ f(m) $。可以用前面定义的类别可分性判据作为适应度。针对不同的适应度有不同的选择概率 $ p(f(m)) $。

遗传算法的基本步骤是：

（1）初始化，t=0，随机地产生一个包含L条不同染色体的种群M(0)；

(2) 计算当前种群 $ M(t) $ 中每一条染色体的适应度 $ f(m) $;

（3）按照选择概率 $ p(f(m)) $ 对种群中的染色体进行采样，由采样出的染色体经过一定的操作繁殖出下一代染色体，组成下一代的种群 $ M(t+1) $;

(4) 回到(2)，直到达到终止条件，输出适应度最大的染色体作为找到的最优解。终止

条件通常是某条染色体的适应度达到设定的阈值。

在第(3)步产生后代的过程中，有两个最基本的操作，一是重组(recombination)，也称交叉(crossover)，是指两条染色体配对，并在某个随机的位置上以一定的重组概率 $ P_{co} $进行交叉，互换部分染色体，如图9-4所示，这也就是遗传算法中模拟有性繁殖的过程。另一个基本操作是突变(mutation)，每条染色体的每一个位置都有一定的概率 $ P_{mut} $发生突变(从0变成1或从1变成0)。

可以看到，在这个基本步骤中，有很多可以调节的因素，例如种群大小 L、选择概率、重组概率、突变概率等。对这些因素采用不同处理就得到不同的遗传算法。人们还可以把生物遗传与进化中的更多概念引入到这一基本算法中，例如基因组的反转（inversion）、转座（transposition）等，目的都是加快种群进化过程。

遗传算法虽然不能保证收敛到全局最优解，但是在多数情况下可以至少得到很好的次优解。当选择的空间很大（特征维数很高）且对特征间的关系缺乏认识时，尝试使用遗传算法往往会得到不错的效果。

9.6 包裹法：以分类性能为准则的特征选择方法

以上介绍的特征选择方法的基本做法，都是定义一定的类别可分性判据，用适当的算法选择一组在这一判据意义下最优的特征。然而，选择特征的目的是为了后续分类，因此，如果分类方法能够处理全部候选特征，那么就可以直接用分类器的错误率来作为特征选择的依据，即从候选特征中选择使分类器性能最好的一组特征。

当特征数目很多时，用穷举的办法尝试所有的特征组合显然是不可行的。一种解决方法是，开始利用所有的特征设计分类器，然后考查各个特征在分类器中的贡献，逐步剔除贡献小的特征。这样得到的结果也属于次优结果。

这种把分类器与特征选择集成来一起、利用分类器进行特征选择的方法通常被称作包裹（wrapper）法，与此相对应，前面已经提到过，利用单独的可分性准则来选择特征再进行分类的方法被称作过滤（filtering）法。

并不是所有的分类器都能够采用这种策略。要采用这种方法，对分类器有两个基本要求：一是分类器应该能够处理高维的特征向量；二是分类器能够在特征维数很高但样本数有限时仍能得到较好的效果。在前面介绍的各种方法中，支持向量机方法能较好地满足这两个要求。因此，人们对支持向量机的包裹法进行了很多研究。

下面介绍两种非常相似的方法：递归支持向量机(R-SVM；recursive SVM) $ ^{①} $和支持向量

机递归特征剔除(SVM recursive feature elimination, SVM-RFE) $ ^{①} $。与前面几节相同，这里也只介绍两种方法的基本做法，更多的原理分析读者可以学习原始参考文献。

R-SVM 和 SVM-RFE 的核心都是线性的支持向量机，特征选择与分类采用的是同样的算法步骤。在算法开始前，需要首先确定特征选择的递归策略。常用的做法有每次选择（或剔除）特征总数的一个比例（例如一半），或者人为规定一个逐级减小的特征数目序列（例如10000，5000，1000，500，200，100，50，20，10）。

两种算法的基本步骤都是：

（1）用当前所有候选特征训练线性支持向量机；

（2）评估当前所有特征在支持向量机中的相对贡献，按照相对贡献大小排序；

（3）根据事先确定的递归选择特征的数目选择出的排序在前面的特征(SVM-RFE中描述为剔除排序在后面的特征)，用这组特征构成新的候选特征，转(1)，直到达到所规定的特征选择数目。

两种算法的不同在于它们评估特征在分类器中贡献的方法不同。

回顾第4章内容，支持向量机的输出函数是

$$ f(x)=w\cdot x+b=\sum_{i=1}^{n}\alpha_{i}y_{i}(x_{i}\cdot x)+b $$

对于在算法第(1)步中已经训练好的 SVM 模型，R-SVM 方法把特征选择的目标看作是，寻找那些使两类样本在这个 SVM 的输出上分离最开的特征，用两类样本的平均 SVM 输出值作为代表，R-SVM 定义两类在当前特征上的分离程度为

$$ S=\frac{1}{n_{1}}\sum_{x^{+}\in\omega_{1}}f(x^{+})-\frac{1}{n_{2}}\sum_{x^{-}\in\omega_{2}}f(x^{-}) $$

其中， $ n_{1} $ 是训练集中 $ \omega_{1} $ 类样本的数目， $ n_{2} $ 是训练集中 $ \omega_{2} $ 类样本的数目。考虑到式(9-26)，很容易把这个分离程度写成各个特征之和的形式

$$ S=\sum_{j=1}^{d}w_{j}m_{j}^{+}-\sum_{j=1}^{d}w_{j}m_{j}^{-}=\sum_{j=1}^{d}w_{j}\left(m_{j}^{+}-m_{j}^{-}\right) $$

其中，d 是当前候选特征的维数， $ w_{j} $ 是权向量 w 的第 j 个分量， $ m_{j}^{+} $、 $ m_{j}^{-} $ 分别是两类样本在第 j 维特征上的均值。这样，每个特征在式(9-27)中的贡献就是

$$ s_{j}=w_{j}\left(m_{j}^{+}-m_{j}^{-}\right),\quad j=1,\cdots,d $$

R-SVM 就是用式(9-29)来衡量各个特征在当前 SVM 模型中的贡献，它不但取决于每个特征在线性分类器中对应的权重，而且考虑到两类样本在各个特征上均值的差别。

SVM-RFE 采用了灵敏度的方法来推导各个特征在 SVM 分类器中的贡献。它把 SVM 输出与正确类别标号 y 之间平均平方误差作为 SVM 分类的损失函数

$$ J=\sum_{i=1}^{n_{1}+n_{2}}\left\|\boldsymbol{w}\cdot\boldsymbol{x}_{i}-y_{i}\right\|^{2} $$

考查各个权值对这个损失函数的影响，得到各个特征的贡献应该用

$$ s_{j}^{\mathrm{R F E}}=w_{j}^{2} $$

来衡量。

在很多实际应用中，R-SVM与SVM-RFE从分类上看性能基本相同，但R-SVM在选择特征的稳定性和在对未来样本的推广能力方面有一定优势，尤其是当训练样本中存在较大的噪声和野值时优势更明显。

包裹法递归进行特征选择与分类的做法可以推广到SVM采用非线性核的情况。回顾6.5节的内容，SVM对偶问题的目标函数是

$$ Q=\sum_{i=1}^{n}\alpha_{i}-\frac{1}{2}\sum_{i,j=1}^{n}\alpha_{i}\alpha_{j}y_{i}y_{j}K(x_{i},x_{j}) $$

用 $ x^{(-k)} $表示去掉第k维特征后的样本，去掉第k个特征对这一目标函数的影响是

$$ D Q(k)=\frac{1}{2}\sum_{i,j=1}^{n}\alpha_{i}\alpha_{j}y_{i}y_{j}\left[K(x_{i},x_{j})-K(x_{i}^{(-k)},x_{j}^{(-k)})\right] $$

可以用这个量作为对特征 k 在非线性 SVM 分类器中的贡献，并利用前面介绍的递归方法来进行包裹法特征选择。

9.7 讨论

在一个模式识别系统中，最基础的因素是用来描述研究对象的特征。如果特征与所研究的分类问题没有关系或关系很弱，那么无论采用怎样的分类器，都很难取得理想的分类效果。同时，如果特征之间有很大冗余，也会影响分类器的性能。

特征选择的方法要回答两个层面的问题，一是对特征的评价：怎样衡量一组特征对分类的有效性；二是寻优的算法：怎样更快地找到性能最优或比较好的特征组合。本章的主要内容就是讨论这两个问题的典型解决方法。

在讨论特征选择问题时，目的是从 D 维特征中选择 d<D 个特征，即假定要选择的特征数目 d 是事先确定的。实际上，一般并不知道一个实际问题中应该选择多少特征，最终选择特征的数目是由分类器性能、特征获取和计算成本等多方面共同决定的。通常，人们追求在能够达到满意的分类效果的前提下使用尽可能少的特征，有时也会在不超过某个可接受的特征数目的前提下追求尽可能高的分类性能。

需要说明的是，本章讨论的一些方法要求在特征数目增加时类别可分性不减小，这在样本数有限且原始特征维数很高时通常并不成立。一种常见的情况是，如果特征组合中包含很多对分类没有贡献的特征，会加剧分类器的过学习，导致分类器测试错误率或交叉验证错误率的增加。在一个原始特征维数较高的问题中，当逐步选择特征时往往可以看到，随着特征数目的减少，分类器性能逐渐提高，但如果特征数目减小到一定程度后继续减少，则分类器性能又会逐渐恶化。在这一过程中，可以观察到一个比较合理的特征数目，使分类器性能达到或接近最优。在利用高维的基因表达数据进行疾病或疾病亚型分类时经常会遇到这种情况。

如果特征之间存在冗余，通常在特征选择中会希望去掉这样的冗余，因为冗余的特征不能提供更多的分类信息。但是，在某些情况下，例如在利用基因表达数据进行疾病分类时，目的不仅仅是构造分类器把两类分开，而且希望通过这种分类鉴别出哪些基因的表达与所研究的

疾病分类有关，也就是发现哪些特征与分类有关，此时就需要把所有包含分类信息的特征都保留下来进行下一步的分析，即使其中某些特征之间存在冗余。

总之，特征选择是一个与具体问题高度关联的问题，本章讨论的只是一些通用的思路和典型的方法，实际应用中需要根据具体目标，与分类器设计相配合，灵活地选择或设计合理的特征选择方法。

本章介绍的特征选择方法包括过滤法和包裹法两大类，前者是在分类器前端“外接”一个特征选择的方法模块，用一定的可分性判据和寻优算法来选择最优或次优的特征；后者是把特征选择模块与分类器包裹在一起，用分类器性能作为特征选择的判据，进行迭代的特征选择和分类。除此之外，还有一种把特征选择融合到分类器之中的方法，通常称作“嵌入法”（Embedded methods）。嵌入法特征选择的基本原理是，修改分类器（或其他类型的学习机器）的目标函数和优化算法，使机器学习的目标中不但包括分类或预测的正确率，而且包括对特征选择的目标项。最典型的嵌入式特征选择方法就是在7.7.3节中曾简要介绍的 $ L_{0} $正则化（即压缩感知）方法和 $ L_{1} $正则化（Lasso回归）方法。压缩感知方法在目标函数中增加对所采用特征数目的惩罚项，强制学习算法用尽可能少的特征来达到最好的学习效果，从而实现对特征的选择。Lasso回归方法用 $ L_{1} $范数代替 $ L_{0} $范数，解决了 $ L_{0} $范数不便于计算和优化的问题，同样可以强制算法用尽量少的特征来完成学习任务。