特征提取与选择

对分类器设计来说，使用什么样的特征描述事物，也就是说使用什么样的特征空间是个很重要的问题。这个问题称之为描述量的选择问题，意思是指保留哪些描述量，删除哪些描述量的问题。
本章节研究对特征空间进行改造,目的在于提高其某方面的性能，因此又称特征的优化问题。

---

引言

对特征空间的改造、优化,主要的目的是降维，即把维数高的特征空间改成维数低的特征空间，降维主要有两种途径：

• 一种是筛选掉一些次要的特征，问题在于如何确定特征的重要性，以及如何筛选。
• 另一种方法是使用变换的手段，限定在线性变换的方法上，通过变换来实现降维。

特征的选择与提取

• 分析各种特征的有效性并选出最有代表性的特征是模式识别系统设计的关键步骤。
• 降低特征维数在很多情况下是有效设计分类器的重要课题。

特征空间的优化

对初始的特征空间进行优化是为了降维。即初始的特征空间维数较高。能否改成一个维数较低的空间，称为优化。

特征优化两种方法

假设有D维特征向量空间，$y={y1,y2,…yD}$:

1. 特征选择是指从原有的D维特征空间，删去一些特征描述量，从而得到精简后的特征空间。在这个特征空间中，样本由降维后的d维的特征向量描述：$x={x1,x2,…xd}，d < D$。由于x只是y的一个子集，因此每个分量$x_i$必然能在 原特征集中找到其对应的描述量$x_i=y_j$。
2. 特征提取则是找到一个映射关系：$A:Y→X$，使新样本特征描述维数比原维数降低。其中每个分量$x_i$是原特征向量各分量的函数，即$x_i=W^Ty_i$。

---

类别可分离性判据

概述

特征选择或特征提取任务是从n个特征中求出对分类最有效的m个特征(m＜n)。

1. 对于特征选择来讲，从n个特征中选择出m个特征， 有$C_n^m$种组合方式。哪一种特征组的分类效果最好？这需要有一个比较标准，即需要一个定量的准则来衡量选择结果的好坏。
2. 对于特征提取来讲，把n维特征向量变换 成m维特征向量，有各种变换。哪一种变换得到的m维特征向量对分类最有效？需要用一个准则来衡量。

用以定量检验分类性能的准则称为类别可分性准则$J_{ij}$, 需要满足以下几点：

1. 与错误概率有单调关系，这样使准则取最大值的效果一般来说其错误率也较小。
2. 度量特性：
   • $J_{ij} > 0$，当$i\ne j$时
   • $J_{ij} = 0$，当$i = j$时
   • $J_{ij} = J_{ji}$
   • 这里$J_{ij}$是第$i$类和第$j$类的可分性准则函数，$J_{ij}$越大，两类的分离程度就越大。
3. 单调性：即加入新的特征时候，准则函数不减小。
4. 当特征独立时有可加性。

基于距离的可分性判据

基于距离的可分性判据的实质是Fisher准则的延伸，即综合考虑不同类样本的类内聚集程度与类间离散程度这两个因素。
判据的优化体现出降维特征空间较好地体现类内密集。一些不能体现类间分隔开的特征很可能被排除掉了。
基于距离度量是常用来进行分类的重要依据，因为一般情况下同类物体在特征空间呈聚类状态，即从总体上说同类物体内各样本由于具有共性，因此类内样本间距离应比跨类样本间距离小。
Fisher准则是以使类间距离尽可能大同时又保持类内距离较小这一种原理为基础的。同样在特征选择与特征提取中也使用类似的原理，这一类被称为基于距离的可分性判据。
为了度量类内、类间的距离，可用其他方法描述方法，即描述样本的离散程度的方法。

$$J_d(x)=\frac{1}{2}\sum_{i=1}^{c}{P_i}\sum_{i=1}^{c}{P_j}\frac{1}{n_in_j}\sum_{k=1}^{n_i}{}\sum_{l=1}^{n_j}{\delta(x_k^{(i)},x_l^{(j)})}$$

各类样本之间的距离越大，则类别可分性越大。因此，可以用各类样本之间的距离的平均值作为可分性准则：

$$J_d(x)=\sum_{i=1}^{c}{P_i}\left[ \frac{1}{n_i}\sum_{k=1}^{n_i}{\left( x_k^{(i)}-m_i \right)^T\left( x_k^{(i)}-m_i \right)+(m_i-m)^T(m_i-m)} \right]$$

即

$$\tilde{S_b}=\sum_{i=1}^{c}{P_i}(m_i-m)(m_i-m)^T \\ \tilde{S_w}=\sum_{i=1}^{c}{P_i}\frac{1}{n_i}\sum_{k=1}^{n_i}{\left( x_k^{(i)}-m_i \right)\left( x_k^{(i)}-m_i \right)^T} \\ J_d(x) = tr(\tilde{S_w}+\tilde{S_b})$$

优点：
定义直观、易于实现，因此比较常用。
缺点：
没有直接考虑样本的分布情况，很难在理论上建立起它们与分类错误率的联系，而且当两类样本的分布有重叠时，这些判据不能反映重叠的情况。

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

显然不同类别在特征空间x中的分布要尽可能不一样，则分类就比较容易，通俗的讲，则不同类别在特征空间的不同区域聚集，则分类就容易，它们重迭的程度越低，越有别于分类。
为了考查在不同特征下两类样本概率分布的情况，定义了基于概率分布的可分性判据。
分布密度的交叠程度可用$p(X|\omega_1)$及$p(X|\omega_2)$这两个分布密度函数之间的距离$J_p$来度量，距离$J_p$有以下几个共同点：

1. $J_p$是非负，即$J_p \leq 0$
2. 当两类完全不交迭时$J_p$达到其最大值
3. 当两类分布密度相同时，$J_p = 0$

常用的概率距离度量：

1. Bhattacharyya距离（巴氏距离）：
   • $J_B=-\ln \int_{}^{}\left[ p(x|\omega_1)p(x|\omega_2) \right]^{1/2}dx$
   • 显然，当$p(X|\omega_1)=p(X|\omega_2)$对所有X值成立时$J_B＝0$，而当两者完全不交迭时$J_B$无穷大。巴氏距离与错误率的上界有直接关系，因此$J_B$不仅用来对特征空间进行降维优化，而且也用来对分类器的错误率作出估计。
2. Chernoff（切诺夫）界限：
   • $J_C=-\ln \int_{}^{}p^s(x|\omega_1)p^{1-s}(x|\omega_2) dx$
   • 其中S取$[0，1]$区间的一个参数，显然在$S=0.5$时就变为$J_B$式，因此$J_B$是$J_C$的一个特例。
3. 散度：区分$i，j$两类总的平均信息
   • $w_i，w_j$对数似然比：$l_{ij}(x)=p(x|\omega_i)/p(x|\omega_j)$
   • 对$w_i$类的可分信息：$I_{ij}(x)=E(l_{ij}(x)]=\int_{x}p(x|\omega_i)In(p(x|\omega_i)/p(x|\omega_j))dx$
   • 对$w_j$类的可分信息：$I_{ji}(x)=E(l_{ji}(x)]=\int_{x}p(x|\omega_j)In(p(x|\omega_j)/p(x|\omega_i))dx$
   • 散度$J_d$为两类平均可分信息之和：$J_D{x}=I_{ij}+I_{ji}=\int_{x}[p(x|\omega_i)-p(x|\omega_j)In(p(x|\omega_i)/p(x|\omega_j))dx$