特征选择和特征提取

意义

降低维度，后续的分类器设计更容易计算，可以加快速度
消除特征之间可能存在的相关性，减少与分类无关的信息（理解成降噪？），从而更好的分类。

类别可分性质的度量

距离

点到点之间的距离

欧式距离：
$D(a, b) = || a – b ||$
平方形式（向量转置相乘，点积的形式）：
$D^{2}(a,b) = (a - b)^{T}(a - b) = \sum_{k = 1}^{n}{(a_{k} - b_{k})^{2}}$
其中a和b为n维向量，其第k个特征分别是$a_k$和$b_k$。 各自对应的特征维度差的平方之和。
点到点集之间的距离

在n维空间中，点x到点$a^{(i)}$之间的距离平方为：
$D^{2}(x,a^{(i)}) = \sum_{k = 1}^{n}{(x_{k} - a_{k}^{(i)})^{2}}$
因此x到有K个点组合的均方距离，就是到每个点均方距离相加之后取均值。
$\overline{D^{2}(x,\{ a^{(i)}\})} = \frac{1}{K}\sum_{i = 1}^{K}{D^{2}(x,a^{(i)}) =}\frac{1}{K}\sum_{i = 1}^{K}\left\{ \sum_{k = 1}^{n}{(x_{k} - a_{k}^{(i)})^{2}} \right\}$

类内距离

类中每个点到其他点的均方距离累加之后求均值

n维空间中同一类内各模式样本点集$\{a^{(i)}\}_{i=1,2,\ldots{},K}$，其内部各点的均方距离为$\overline{D^{2}(\{ a^{(j)}\},\{ a^{(i)}\})}$，其中$i,j = 1,2,\ldots,K,i \neq j$，即：

$\overline{D^{2}(\{ a^{(j)}\},\{ a^{(i)}\})} = \frac{1}{K}\sum_{j = 1}^{K}\left\lbrack \frac{1}{K - 1}\sum_{\begin{matrix} i = 1 \\ i \neq j \\ \end{matrix}}^{K}{\sum_{k = 1}^{n}{(a_{k}^{(j)} - a_{k}^{(i)})^{2}}} \right\rbrack$

每个点到其他点的平方距离求和，三层循环（点j，点i，维度k）

可证明：

$\overline{D^{2}} = 2\sum_{k = 1}^{n}\sigma_{k}^{2}$

其中$\sigma_{k}^{2}$为样本集合$a^{(i)}$在第k个分量上的无偏方差，即：

$\sigma_{k}^{2} = \frac{1}{K - 1}\sum_{i = 1}^{K}{(a_{k}^{(i)} - \overline{a_{k}})^{2}}$

其中$\overline{a_{k}} = \frac{1}{K}\sum_{i = 1}^{K}a_{k}^{(i)}$为$a^{(i)}$在第k个分量方向上的均值。

无偏估计除以的是K-1，把数据集合用一个完整的$K \times N$矩阵来理解，就可以很方便的对应这些距离公式，均值，方差的计算了。公式可以不用管。

类间距离

两类样本均值质心的均方距离

常用两类样本各自质心间的距离作为类间距离，并假设两类样本出现的概率相等，则：

$D^{2} = \sum_{k = 1}^{n}{(m_{1_{k}} -}m_{2_{k}})^{2}$

其中 $m_1$ 和 $m_2$ 为两类模式样本集各自的均值向量， $m_{1k}$ 和$m_{1k}$为两个均值向量的第k个特征分量，n为维数。

散布矩阵

不管类内还是类间都涉及到与均值向量之差的向量乘以其转置。

类内散布矩阵

每个样本向量减去均值向量后乘以结果的转置(矩阵)，然后将得到的矩阵再相加

考虑一类内模式点集$\{ a^{(i)}\}_{i = 1,2,\ldots,K}$，其类内散布矩阵为：

$S_w = \sum_{i = 1}^{K}\{(a^{(i)} - m)(a^{(i)} - m)^{T}\}$

其中m是样本集合的均值向量

$m = \frac{1}{K}\sum_{i = 1}^{K}a{(i)}$

对属于同一类的模式样本，类内散布矩阵表示各样本点围绕其均值周围的散布情况。

类间散布矩阵

两个质心之差形成的向量与其转置相乘而形成的矩阵，类比与类内散布矩阵，类内是每个样本向量减去该类的均值向量，是所有样本向量都要参与。

$S_{b2} = (m_{1} - m_{2})(m_{1} - m_{2})^{T}$

对三个以上的类别，类间散布矩阵常写成：

$S_{b} = \sum_{i = 1}^{c}{P(\omega_{i})}(m_{i} - m_{0})(m_{i} - m_{0})^{T}$

其中，$m_{0}$为多类模式（如共有c类）分布的总体均值向量，即：

$m_{0} = E\{ x\} = \sum_{i = 1}^{c}{P(\omega_{i})m_{i}},\quad\forall\omega_{i},\mspace{6mu} i = 1,2,\ldots,c$

用质心来代表每一类，多类模式引入概率来取得总体所有样本均值。计算的形式与类内的很相似了，$m_0$对应着类内中一个类的均值向量，每个质心对应这类内中的一个样本向量。

多类模式集散布矩阵

多类情况的类内散布矩阵，可写成各类的类内散布矩阵的先验概率的加权和，即：

$S_{w} = \sum_{i = 1}^{c}{P(\omega_{i})E\{}(x - m_{i})(x - m_{i})^{T}|\omega_{i}\} = \sum_{i = 1}^{c}{P(\omega_{i})C_{i}}$

其中$C_{i}$是第i类的协方差矩阵。E是求期望，也就是每个样本的矩阵计算完了之后相加还要除以样本数目N或者N-1（N-1是无偏估计）。

协方差(两个变量各自与各自均值的差相乘)：

$Cov(X,Y)=E[(X-m_X)(Y-m_Y)]=E[XY]-E[X]\times E[Y]$

协方差矩阵是不同维度之间的相关性的表达，一个d维的样本也能建立协方差矩阵尺度为$d\times d$, 所以一个类的协方差矩阵是每个样本的协方差矩阵相加后取均值得到的。

有时，用多类模式总体分布的散布矩阵来反映其可分性，即：

$S_{t} = E\{(x - m_{0})(x - m_{0})^{T}\},\quad x \in \forall\omega_{i},\mspace{6mu} i = 1,2,\ldots,c$

其中，$m_{0}$为多类模式分布的总体均值向量。

可以证明：$S_{t} = S_{w} +S_{b}$，即总体散布矩阵是各类类内散布矩阵与类间散布矩阵之和。

特征选择

在尽量不降低分类精度的前提下，选择更少的特诊来进行分类。

独立特征的选择准则

不同类的均值向量（质心点）之间的距离最大，而同一类的样本向量的方差之和最小（与其质心的距离较近）。用一个比值来作为度量标准。

假设个特征之间统计独立，那么对每个特征分量都去计算那个标准，就能够知道每个特征对样本可分性的贡献了。

对于$ω_{i}$和$ω_{j}$两类训练样本，假设其均值向量为$m_{i}$和$m_{j}$，其k维方向的分量为$m_{ik}$和$m_{jk}$，方差为$\sigma_{\text{ik}}^{2}$和$\sigma_{\text{jk}}^{2}$，定义可分性准则函数(也就是那个标准)：

$G_{k} = \frac{(m_{\text{ik}} - m_{\text{jk}})^{2}}{\sigma_{\text{ik}}^{2} + \sigma_{\text{jk}}^{2}},\;\;k = 1,2,\ldots,n$

则$G_{K}$为正值。$G_{K}$值越大，表示测度值的第k个分量对分离$ω_{i}$和$ω_{j}$两类越有效。将$\{G_{K},k=1,2,\ldots{},n\}$按大小排队，选出最大的m个对应的测度值作为分类特征，即达到特征选择的目的。

一般特征的散布矩阵准则

回顾类内与类间散布矩阵：

多类类内散布矩阵：

$S_{w} = \sum_{i = 1}^{c}{P(\omega_{i})E\{}(x - m_{i})(x - m_{i})^{T}|\omega_{i}\}$

多类类间散布矩阵：

$S_{b} = \sum_{i = 1}^{c}{P(\omega_{i})}(m_{i} - m_{0})(m_{i} - m_{0})^{T}$

直观上，类间离散度越大且类内离散度越小，则可分性越好。因此，可推导出散布矩阵准则采用如下形式： (矩阵的逆类比于除法)

行列式形式：$J_{1} = \det(S_{w}^{- 1}S_{b}) = \prod_{i}^{}\lambda_{i}$

迹形式：$J_{2} = tr(S_{w}^{- 1}S_{b}) = \sum_{i}^{}\lambda_{i}$

其中，$λ_{i}$是矩阵$S_{w}^{- 1}S_{b}$的特征值。使$J_{1}$或$J_{2}$最大的子集可作为选择的分类特征。

离散K-L变换

前面讨论的直接删去一些特征的做法不理想，因为一般来说，原来的n个数据各自在不同程度上反映了识别对象的某些特征，简单地删去某些特征可能会丢失较多的有用信息。

将样本看成是对应维度D维随机向量的一次采样，对D维向量x用一个完备的正交归一向量系进行展开（理解成用一组正交的基向量来表示）。或者是对D维特征进行正交变换，用变换后的维度中选择少数的几个特征，这几个少数的特征尽可能多地反映各类模式之间的差异，而这些特征间又尽可能相互独立。

展开式的形式

设一连续的随机实函数x(t)，$T_{1} \leq t \leq T_{2}$，则x(t)可用已知的正交函数集$φ_{j}(t),j=1,2,\ldots{\infty}$的线性组合来展开，即公式1：

$\begin{split} x(t) &= a_{1}\varphi_{1}(t) + a_{2}\varphi_{2}(t) + \cdots + a_{j}\varphi_{j}(t) + \cdots\\ &=\sum_{j=1}a_j\varphi_j(t),\qquad T_1\le t \le T_2 \qquad (1)\\ \end{split}$

式中，$a_{j}$为展开式的随机系数，$φ_{j}(t)$为一连续的正交函数，它应满足：

$\int_{T_{1}}^{T_{2}}{\varphi_{n}^{(t)}{\tilde{\varphi}}_{m}(t)dt = \left\{ \begin{matrix} 1, & \text{if}\mspace{6mu} m = n \\ 0 & \text{if}\mspace{6mu} m \neq n \\ \end{matrix} \right.\ }$

其中${\tilde{\varphi}}_{m}(t)$为$φ_{m}(t)$的共轭复数式。

将上式写成离散的正交函数形式，使连续随机函数x(t)和连续正交函数$φ_{j}(t)$在区间$T_{1} \leq t \leq T_{2}$内被等间隔采样为n个离散点，用采n个点的样本，来描绘原来的函数即：

$x(t) \rightarrow \{ x(1),x(2),\cdots,x(n)\}\\ \varphi_{j}(t) \rightarrow \{\varphi_{j}(1),\varphi_{j}(2),\cdots,\varphi_{j}(n)\}$

写成向量形式：

$\begin{split} x &= (x(1),x(2),\cdots,x(n))^{T}\\ \varphi_{j}& = (\varphi_{j}(1),\varphi_{j}(2),\cdots,\varphi_{j}(n))^{T},\mspace{6mu} j = 1,2,\cdots,n \end{split}$

每一个正交函数都要对应的平行采样，而不是一个函数采一个时刻的样。

将公式(1)取n项近似(可以理解成逼近)，并写成离散展开式：

$x = \sum_{j = 1}^{n}{a_{j}\varphi_{j}} = \Phi a,\quad T_{1} \leq t \leq T_{2} \qquad(2)$

其中，a为展开式中随机系数的向量形式，即：$a = (a_{1}, a_{2}, \ldots{},a_{j}, \ldots{},a_{n})^{T}$

$\Phi$为n x n维矩阵，即：

$\Phi = (\varphi_{1},\varphi_{2},\cdots,\varphi_{n}) = \begin{bmatrix} \varphi_{1}(1) & \varphi_{2}(1) & \cdots & \varphi_{n}(1) \\ \varphi_{1}(2) & \varphi_{2}(2) & \cdots & \varphi_{n}(2) \\ \cdots & \cdots & \cdots & \cdots \\ \varphi_{1}(n) & \varphi_{2}(n) & \cdots & \varphi_{n}(n) \\ \end{bmatrix}$

其中，每一列为正交函数集中的一个函数，小括号内的序号为正交函数的采样点次序。因此，$\Phi$实质上是由$φ_{j}$向量组成的正交变换矩阵，它将x变换成a。不应该是a变换成x吗，x变成a应该是用逆矩阵来变换的？

对于每一类正交函数是相同的，但是每一类的展开系数向量则不同

展开式的性质

正交向量集$\varphi_j$的确定

K-L展开式的根本性质是将随机向量x展开为另一组正交向量$\varphi_j$的线性和，且其展开式系数$a_j$（即系数向量a的各个分量）具有不同的性质。

设随机向量x的总体自相关矩阵为$R = E\{xx^{T}\}$。由$x = \sum_{j = 1}^{n}{a_{j}\varphi_{j}} = \Phi a,\quad T_{1} \leq t \leq T_{2}$将$x=\Phi a$代入$R = E\{xx^{T}\}$，得：

${R = E\{Φaa^{T}Φ^{T}\}=Φ(E\{aa^{T}\})Φ^{T}}$

要求系数向量a的各个不同分量应统计独立，即应使$(a_{1},a_{2}, \ldots{}, a_{j}, \ldots{},a_{n})$满足如下关系：(没搞懂)

$E(a_{j}a_{k}) = \left\{ \begin{matrix} \lambda_{j} & \text{if}\mspace{6mu} j = k \\ 0 & \text{if}\mspace{6mu} j \neq k \\ \end{matrix} \right.\$

写成矩阵形式，应使：$E\{a a^{T}\} =D_{λ}$，其中$D_{λ}$为对角形矩阵，其互相关成分均为0，即:

$D_{\lambda} = \begin{bmatrix} \lambda_{1} & 0 & \cdots & \cdots & 0 \\ 0 & \ddots & 0 & \cdots & 0 \\ 0 & & \lambda_{j} & & 0 \\ 0 & \cdots & 0 & \ddots & 0 \\ 0 & \cdots & \cdots & 0 & \lambda_{n} \\ \end{bmatrix}$

则：$R =\Phi D_{λ}Φ^{T}$

由于$\Phi$中的各个向量$\varphi_j$都相互归一正交有性质（$\Phi^T \Phi=\Phi^{-1}\Phi=I$）$\Phi$是正交矩阵？，故有：

${RΦ=ΦD_{λ}Φ^{T}Φ=ΦD_{λ}}$

其中，$\varphi_j$向量对应为：$R\varphi_j=λ_j\varphi_j$

可以看出，$λ_j$是x的自相关矩阵R的特征值，$\varphi_j$是对应的特征向量。因为R是实对称矩阵，其不同特征值对应的特征向量应正交(向量之间的夹角为90度)，即：

$\varphi_{j}^{T}\varphi_{k} = \left\{ \begin{matrix} 1 & \text{if}\mspace{6mu} j = k \\ 0 & \text{if}\mspace{6mu} j \neq k \\ \end{matrix} \right.\$

由式$x = \sum_{j = 1}^{n}{a_{j}\varphi_{j}} = \Phi a,\quad T_{1} \leq t \leq T_{2}$，K-L展开式系数应为：

$a = \Phi^{T}x$

结论：正交向量集$\Phi$是样本的自相关矩阵$R = E\{xx^{T}\}$的特征向量构成的集合。如果选择$\Phi$的维度是$D\times K$即只选择K个特征向量去展开来逼近原来的样本，则应该选择特征值前K大的的K个特征向量来组成。

这段推导没有搞懂，还是模式识别书上的展开后去前n项来逼近原始向量之后求原向量与逼近向量之间的均方误差最小，然后在等式约束下使用拉格朗日发来求极值，解得系数是是$\Phi$的特征值好理解。

K-L展示式系数的计算步骤

求随机向量x的自相关矩阵：$R = E\{xx^{T}\}$
求出矩阵R的特征值$λ_j$和对应的特征向量$\varphi_j，j = 1,2,\ldots{},n$，得矩阵：$\Phi = (\varphi_{1},\varphi_{2},\cdots,\varphi_{n})$
计算展开式系数：$a = \Phi^{T}x$

按K-L展开式选择特征

K-L展开式用于特征选择相当于一种线性变换。

若从n个特征向量中取出m个组成变换矩阵$\Phi$，即$\Phi=(\Phi_1,\Phi_2,\ldots{\Phi_m})\quad m<n$ 得到的$\Phi$矩阵的维度是$n\times m$,样本向量x是n为向量，则通过$a = \Phi^{T}x$得到的系数向量是m维度，系数向量就是降维后得到的新向量。

问题

选取变换矩阵$\Phi$ 后，让降维后得到的新向量a在最小均方误差条件下接近原来的向量x。（不是直接用a与x取比较的，因为维度都不同，是让a乘以变换矩阵去逼近x。换句话说，x是被其自相关矩阵展开的）

对于$x = \sum_{j = 1}^{n}{a_{j}\varphi_{j}}$，现仅取m项，对略去的系数项用预先选定的常数b代替，此时对x的估计值为：

$\hat{x} = \sum_{j = 1}^{m}{a_{j}\varphi_{j}} + \sum_{j = m + 1}^{n}{b\varphi_{j}}$

则产生的误差为：

$\Delta x = x - \hat{x} = \sum_{j = m + 1}^{n}{(a_{j} - b)\varphi_{j}}$

则$\Delta x$的均方误差为：(为什么引入了期望)(为什么没有了$\varphi_j$)

$\overline{\varepsilon^{2}} = E\{||\Delta x||\}^{2} = \sum_{j = m + 1}^{n}{\{ E(a_{j} - b)^{2}\}}$

要使$\overline{\varepsilon^{2}}$最小，对b的选择应满足：

$\frac{\partial}{\partial b}\lbrack E(a_{j} - b)^{2}\rbrack = \frac{\partial}{\partial b}\lbrack E(a_{j}^{2} - 2a_{j}b + b^{2})\rbrack = - 2\lbrack E(a_{j}) - b\rbrack = 0$

因此，$b =E{[}a_{j}{]}$，即对省略掉的a中的分量，应使用它们的数学期望来代替，此时的误差为：

$\begin{equation} \begin{split} {\overline{\varepsilon^{2}} = \sum_{j = m + 1}^{n}{E\lbrack(a_{j} - E\{ a_{j}\})^{2}\rbrack }\\ =\sum_{j = m + 1}^{n}{\varphi_{j}^{T}E\lbrack(x - E\{ x\})(x - E\{ x\})^{T}\rbrack\varphi_{j}}}= { \sum_{j = m + 1}^{n}{\varphi_{j}^{T}C_{x}}\varphi_{j}}\\ \end{split} \end{equation}$

其中，$C_{x}$为x的协方差矩阵。（第二步怎么推出来的？）

设$λ_{j}$为$C_{x}$的第j个特征值，$\varphi_{j}$是与$λ_{j}$对应的特征向量，则$C_{x}\varphi_{j} = \lambda_{j}\varphi_{j}$由于$\varphi_{j}^{T}\varphi_{j} = 1$,从而$\varphi_{j}^{T}C_{x}\varphi_{j} = \lambda_{j}$因此:

$\overline{\varepsilon^{2}} = \sum_{j = m + 1}^{n}{\varphi_{j}^{T}C_{x}}\varphi_{j} = \sum_{j = m + 1}^{n}\lambda_{j}$

由此可以看出，$λ_{j}$值越小，误差也越小。（这里的特征值与自相关矩阵的特征值不同？，所以原来的自相关矩阵的特征应该选择大的。）

结论

按照最小均方差的准则来选择特征，应使得$E[a_j]=0$为什么?。因为$E[a]=E[\Phi^Tx]=\Phi^TE[x]$,所以应使的$E[x]=0$。因此在K-L变换之前，需要先将其均值作为新坐标轴的原点，采用协方差矩阵C或自相关矩阵R来计算特征值。如果$E[x] ≠0$，则只能得到“次最佳”的结果。

为了使误差尽可能小，选择的特征向量对应的特征值要是最大的。

K-L变换是在均方误差最小的意义下获得数据压缩（降维）的最佳变换，且不受模式分布的限制。整个变换使的整个模式分布结构尽可能保持不变。

通过K-L变换能获得互不相关的新特征。主成分分析出发点是变换得到的新特征的方差最大，从而保证原始样本在改维特征上的差异更大，从而更好的区分。PCA使用的变换矩阵是样本的协方差矩阵$C_x=E[(x-E[x])(x-E[x]^T)]$，因此当样本集的均值为0即$[E[x]=0]$，或者对样本进行去均值处理的时候，K-L变换就与PCA等价了。

需要指出的是，采用K-L变换作为模式分类的特征提取时，要特别注意保留不同类别的模式分类鉴别信息，仅单纯考虑尽可能代表原来模式的主成分，有时并不一定有利于分类的鉴别。（这里不同类别的模式分类鉴别信息是什么？）