Ch7 特征提取与特征变换

[TOC]

引言

特征提取的目的	特征变换的目的
提取观测数据的内在特性	降低特征空间的维度，增加数据密度、降低过拟合风险
减少噪声影响	便于分析和减少后续步骤的计算量
提高稳定性	减少特征之间可能存在的相关性、有利于分类

特征提取

提取对象	提取方式
语音特征提取	局部特征提取方法：`LBP`, `SIFT`
文本特征提取	全局特征提取方法：`词袋模型`, `HoG`
视觉特征提取	---

特征变换：根据特征变换关系不同

线性特征变换	非线性特征变换
采用线性映射将原特征变换至一个新的空间（通常维度更低）	采用非线性映射将原特征变换至一个新的空间（通常性能更好）
`PCA`,`LDA`,`ICA`	`KPCA`,`KLDA`,`Isomap`,`LLE`,`HLLE`,`LSTA`

特征提取

文本特征提取

将文本内容转化为向量的过程。将一个文档表示成一个向量，向量的相似性反应文档的相似性。

向量空间模型(BOW, TF-IDF)

词向量模型(word2vec)

视觉特征提取

局部二值模式（LBP）

特征变换

对已有向量特征进行变换，得到新特征的过程。

维数缩减

维度灾难是指当数据的维度（特征数）过高时，模型计算复杂度高、存储开销大、距离计算变得不准确，甚至模型性能下降的问题。

缓解维数灾难：降维。通过维数缩减，可以将原始高维空间的数据投影到一个低维子空间中。

在低维子空间里，数据的密度通常会大幅度提高。
数据的距离计算、分类、聚类等操作会变得更容易、更准确。

Q: 为什么能降维？

A: 在很多情况下，尽管我们采集的数据是高维的，但这些高维数据的本质特征通常只分布在低维空间内。这种现象是因为：

冗余特征：许多特征是高度相关的，含有重复信息。

任务相关特征嵌入低维空间：与学习任务密切相关的特征往往位于某个低维子空间内，而不相关的特征只会引入噪声。

通俗理解：高维数据往往有很多“水分”（冗余和噪声），通过降维可以提取出核心信息，就像将大海捞针简化为池塘捞针。

非均匀性祝福：数据在高维空间中的分布可能看起来稀疏，但实际上，它们大多集中在一个低维流形（低维嵌入空间）上。

线性降维法

对高维空间中的样本$x$进行线性变换：

$y = W^Tx$，其中$x\in R^m$，$W\in R^{m\times d}$，$y\in R^d$，$d < m$。
变换矩阵$W = [w_1,w_2,\cdots,w_d]$可视为$m$维空间中由$d$个基向量组成的矩阵。
$y = W^Tx$可视为样本$x$与$d$个基向量分别做内积而得到，即$x$在新坐标系下的坐标。新空间中的特征是原空间中特征的线性组合，这就是线性降维法。
不同降维方法的差异：对低维子空间的性质有不同的要求，即对$W$施加不同的约束。

PCA

给定条件：$n$个样本$x_1,x_2,\cdots,x_n$，每个样本$x_i\in R^d$。

目标：我们想要在投影数据中捕获最大可能的方差，即把数据从$d$维投影到$m$维，其中$m < d$。

设$w_1,w_2,\cdots,w_m\in R^d$是主成分，假设$w$满足正交性：$(w_i)^Tw_j = 0$，$\forall i\neq j$，且$(w_i)^Tw_i = 1$，$i,j = 1,2,\cdots,m$。我们只需要前$m$个主成分。

成分	对应公式
数据点$x_i$沿$w_1$的投影$y_i$	$y_i = w_1^Tx_i$
均值$\overline{x}$沿$w_1$的投影$\overline{y}$	$\overline{y}=w_1^T\overline{x},\ \overline{x}=\frac{1}{n}\sum_{i = 1}^{n}x_i$
投影数据（沿投影方向$w_1$）的方差	$\text{var}=\frac{1}{n}\sum_{i = 1}^{n}(w_1^Tx_i - w_1^T\overline{x})^2$
想要获得使投影数据方差最大化的方向$w_1$	$\max\frac{1}{n}\sum_{i = 1}^{n}(w_1^Tx_i - w_1^T\overline{x})^2,\ w_1^Tw_1 = 1$

\[ \begin{align} \text{var}&=\frac{1}{n}\sum_{i = 1}^{n}(w_1^Tx_i - w_1^T\overline{x})^2\\ &=\frac{1}{n}\sum_{i = 1}^{n}(w_1^Tx_i - w_1^T\overline{x})(w_1^Tx_i - w_1^T\overline{x})^T\\ &=\frac{1}{n}\sum_{i = 1}^{n}w_1^T(x_i - \overline{x})(x_i - \overline{x})^Tw_1\\ &=w_1^T\left(\frac{1}{n}\sum_{i = 1}^{n}(x_i - \overline{x})(x_i - \overline{x})^T\right)w_1\\ &=w_1^TCw_1 \end{align} \]

其中$C=\frac{1}{n}\sum_{i = 1}^{n}(x_i - \overline{x})(x_i - \overline{x})^T$是数据的协方差矩阵。则有： \[ \max w_1^TCw_1\\ s.t.\ w_1^Tw_1 = 1 \] 现在引入拉格朗日乘子$\lambda$到这个问题中，得到如下目标函数： \[ \text{obj}=w_1^TCw_1-\lambda(w_1^Tw_1 - 1)\\ \frac{\partial\text{obj}}{\partial w_1}=2Cw_1 - 2\lambda w_1 = 0\\ Cw_1=\lambda w_1 \] 这只是一个特征值方程。因此，$w_1$必须是$C$的一个特征向量。

我们现在知道$w_1$必须是$C$的一个特征向量，$\lambda$是相应的特征值。但是，$C$有多个特征向量，哪一个是$w_1$呢？

考虑： \[ w_1^TCw_1 = w_1^T\lambda w_1=\lambda w_1^Tw_1=\lambda \] 我们想要最大化投影数据方差$w_1^TCw_1=\lambda$：因此$\lambda$应该是最大的特征值，$w_1$是$C$的第一个特征向量（具有特征值$\lambda$），这是第一个主成分（数据中方差最大的方向）。

若A是对称阵，此时左特征空间=右特征空间、U=V：

算法实现

步骤	公式
计算数据均值	$\overline{x}=\frac{1}{n}\sum_{i = 1}^{n}x_i$
计算数据的协方差矩阵	$C=\frac{1}{n}\sum_{i = 1}^{n}(x_i - \overline{x})(x_i - \overline{x})^T$
对矩阵$C$进行特征值分解	取最大的$m$个特征值$\lambda_1\geq\lambda_2\geq\cdots\geq\lambda_m$对应的特征向量$w_1,w_2,\cdots,w_m$，组成投影矩阵$W = [w_1,w_2,\cdots,w_m]\in R^{d\times m}$
将每一个数据进行投影	$y_i = W^Tx_i\in R^m$，$i = 1,2,\cdots,n$

进一步的分析

Q: 如何仅用一个超平面从整体上对所有样本$\{x_1,x_2,\cdots,x_n\}\subseteq R^m$进行恰当的表示？

A: 通常有如下两种思路：

可区分性：样本点在这个超平面上的投影能够尽可能地分开。（方差最大化）

可重构性：样本到这个超平面的距离都足够近。（重构误差最小化）

PCA －采用最大可分性观点

PCA——采用重构的观点

由$W$定义新坐标系：假定投影变换是正交变换，即新坐标系由$W = [w_1,w_2,\cdots,w_d]\in R^{m\times d}$来表示（$d < m$），$w_i$的模等于1，$w_i$与$w_j$两两正交。

设样本点$x_i$在新坐标系下的坐标为： \[ y_i = [y_{i1},y_{i2},\cdots,y_{id}]^T\in R^d\\ y_{ij}=w_j^Tx_i,\quad w_j\in R^m,\quad j = 1,2,\cdots,d\\ \iff y_i = W^Tx_i \] 在旧坐标系下，可得$x_i$的重构表示： \[ \hat{x}_i=\sum_{j = 1}^{d}y_{ij}w_j = Wy_i,\quad i = 1,2,\cdots,n \] 重构误差： \[ \begin{align} \sum_{i = 1}^{n}\|x_i - \hat{x}_i\|^2&=\sum_{i = 1}^{n}\|x_i - Wy_i\|^2\\ &=\sum_{i = 1}^{n}((Wy_i)^TWy_i - 2x_i^TWy_i + x_i^Tx_i)\\ (\because W^TW = I)&=\sum_{i = 1}^{n}(y_i^Ty_i - 2y_i^Ty_i + x_i^Tx_i)\\ (\because y_i = W^Tx_i)&=-\sum_{i = 1}^{n}y_i^Ty_i+\text{const}=-\sum_{i = 1}^{n}(W^Tx_i)^T(W^Tx_i)+\text{const}\\ &=-\text{tr}\left(\sum_{i = 1}^{n}(W^Tx_i)^T(W^Tx_i)\right)+\text{const}\\ (\because \text{tr}(AB)=\text{tr}(BA))&=-\text{tr}\left(W^T\sum_{i = 1}^{n}x_ix_i^TW\right)+\text{const}\\ (\because tr(A)+tr(B)=tr(A+B)) \end{align} \] 令$X = [x_1,x_2,\cdots,x_n]\in R^{m\times n}$: \[ \begin{align} \sum_{i = 1}^{n}\|x_i - \hat{x}_i\|^2&=tr(W^T\sum_{i = 1}^{n}x_ix_i^TW)+\text{const}\\ &=-\text{tr}\left(W^TXX^TW\right)+\text{const} \end{align} \] 假定数据已经零均值化，即$\overline{x}=\frac{1}{n}\sum_{i = 1}^{n}x_i = 0$ \[ XX^T=\sum_{i = 1}^{n}x_ix_i^T=\sum_{i = 1}^{n}(x_i - \overline{x})(x_i - \overline{x})^T=nC \] 于是，获得主成分分析的最优化模型： \[ \max_{W\in R^{m\times d}}\text{tr}(W^TCW)=\sum_{i = 1}^{d}w_i^TCw_i\\ s.t.\ W^TW = I \]

讨论： - 降低至多少维：$\frac{\sum_{i = 1}^{d}\lambda_i}{\sum_{i = 1}^{t}\lambda_i}\geq t$（比如，$t = 95\%$） - 也可以采用交叉验证，结合最近邻分类器来选择合适的维度$d$。 - 舍弃$m - d$个特征值对应的特征向量导致了维数缩减。 - 舍弃这些信息之后能使样本的采样密度增大，这正是降维的重要动机。 - 另外，当数据受到噪声影响时，最小的特征值所对应的特征向量往往与噪声有关，将它们舍弃可在一定程度上起到去噪的效果。

LDA

线性判别分析（Linear Discriminant Analysis，LDA）是一种经典的线性判别学习方法。

算法思想：对于两类分类问题，给定训练集，设法将样本投影到一条直线上，使得同类样本的投影点尽可能接近，不同类样本的投影点尽可能相互远离。对新样本分类时，将其投影到这条直线上，再根据投影点的位置来判断其类别。

样本集$D = \{(x_1,y_1),(x_2,y_2),\cdots,(x_n,y_n)\}$，$y_i\in\{0,1\}$，令$X_i$、$\mu_i$、$\Sigma_i$分别表示第$i\in\{0,1\}$类的样本集合、均值向量、协方差矩阵。

若将数据投影到方向$w$上，则两类样本的中心在直线上的投影分别为$w^T\mu_0$和$w^T\mu_1$；两类样本的协方差分别为$w^T\Sigma_0w$和$w^T\Sigma_1w$。

欲使同类样本的投影点尽可能接近，可让同类样本投影点的方差尽可能小，即$w^T\Sigma_0w + w^T\Sigma_1w$尽可能小。
欲使异类样本的投影点尽可能远离，可让类中心点之间的距离尽可能大，即$(w^T\mu_0 - w^T\mu_1)^2$尽可能大。

最大化如下目标函数： \[ J=\frac{\|w^T\mu_0 - w^T\mu_1\|^2_2}{w^T\Sigma_0w + w^T\Sigma_1w}\\ =\frac{(u_0-u_1)^Tww^T(u_0-u_1)}{w^T(\Sigma_0+\Sigma_1)w}\\ =\frac{w^T(\mu_0 - \mu_1)(\mu_0 - \mu_1)^Tw}{w^T(\Sigma_0+\Sigma_1)w} \] 主要因为$w^T(u_0-u_1)$得到的数，所以才可以交换。分子使两个类的中心距离尽可能远；分母使两类的类内方差尽可能小。

定义矩阵形式：

类内散度矩阵	类间散度矩阵
$\begin{align}S_w&=\Sigma_0+\Sigma_1\\&=\sum_{x\in X_0}(x - \mu_0)(x - \mu_0)^T+\sum_{x\in X_1}(x - \mu_1)(x - \mu_1)^T\end{align}$	$S_b=(\mu_0 - \mu_1)(\mu_0 - \mu_1)^T$

目标函数重写为（广义Rayleigh商）： \[ J=\frac{w^T S_b w}{w^T S_w w} \] 注意：$J$的值与向量的长度无关，只与其方向有关，不失一般性可令$w$为单位长度的向量。

由于目标函数值与长度无关（只与方向有关），因此可采用一种更直观的方法：令$w^T S_w w = 1$： \[ \max w^T S_b w,\quad s.t.\quad w^T S_w w = 1 \] 根据拉格朗日乘子法，于是有： \[ S_b w=\lambda S_w w\Rightarrow S_w^{-1}S_b w=\lambda w \] 上式表明：$w$为是矩阵$S_w^{-1}S_b$的特征向量。

构造性求解方法 : \[ S_b=(\mu_0 - \mu_1)(\mu_0 - \mu_1)^T\\ S_b w=(\mu_0 - \mu_1)(\mu_0 - \mu_1)^T w=s\cdot(\mu_0 - \mu_1),\quad s = (\mu_0 - \mu_1)^T w\in R \] 上式表明：$S_b w$方向与$\mu_0 - \mu_1$的方向相同。不妨令$ S_b w=(_0 - _1)$:

我有想：为什么$\lambda$可以等价于$s$?

但想了一下，假使$\lambda'=s'=\lambda\cdot s$就可以了。

\[ S_b w=\lambda(\mu_0 - \mu_1)\\ \because S_b w=\lambda S_w w\\ w = S_w^{-1}(\mu_0 - \mu_1) \]

所以最终的结果就是得到投影：$w= S_w^{-1}(\mu_0 - \mu_1)$

投影后，可以对两类数据进行分类：$z=w^Tx$

多类LDA算法(设类别数为c)

局部线性判别分析

LDA局限性

LDA假设数据是高斯分布的，这在很多真实数据中不一定成立。
LDA希望类间距离大（分类区分性高），同时使 类内距离小（紧凑性强）。但对于复杂的、高维数据，这种方法可能无法捕捉到数据的局部结构，导致投影结果并不能有效区分类别。

局部线性判别分析旨在克服LDA的局限性，主要考虑数据的局部几何结构，即通过局部近邻关系，改善分类能力和特征提取效果。

核心思想： 修改LDA中的类内散度矩阵$S_w$和类间散度矩阵$S_b$，引入局部近邻约束或加权机制来更准确地描述数据的分布。 \[ S_w=\sum_{y_i = y_j,x_j\in N(x_i),x_i\in N(x_j)}(x_i - x_j)(x_i - x_j)^T\\ S_b=\sum_{y_i\neq y_j,x_j\in N(x_i),x_i\in N(x_j)}(x_i - x_j)(x_i - x_j)^T \]

局部分析技术

Neighborhood constraints（方法一,近邻判别分析）
Locally weighting（方法二,局部Fisher判别分析）
- Weighting for 1 - NN
- Local Fisher discriminant analysis

近邻判别分析（NNDA）

近邻约束中的一个问题是近邻数$k$的选择。

此图展示了两类最近邻加权的示意图，分别用浅蓝色和紫色表示不同类别的数据点，$x_i$和$x_j$是不同类中的数据点，$d_1$和$d_2$是距离。

展示了多类最近邻加权的示意图，分别用浅蓝色、橙色和紫色表示不同类别的数据点，$x_i$和$x_j$是不同类中的数据点，$d_1$和$d_2$是距离。

对相关矩阵修改： - 类内散度矩阵： \[ S_w=\sum_{y_i = y_j,x_j\in N_{I - nn}(x_i),i = 1,2,\cdots,n}W_{i}(x_i - x_j)(x_i - x_j)^T \] - 类间散度矩阵： \[ S_b=\sum_{y_i\neq y_j,x_j\in N_{I - nn}(x_i),i = 1,2,\cdots,n}W_{i}(x_i - x_j)(x_i - x_j)^T \]

局部Fisher判别分析（LFDA）

动机:

LFDA不强制要求同一类中相距较远的数据对接近，这样可以更好地保留数据的局部几何结构。
通过邻域加权机制，强调局部的关系而不是全局的特性。

构建仿射矩阵A \[ \begin{align} A&=\begin{pmatrix} A_{11} & A_{12} & \cdots & A_{1n}\\ A_{21} & A_{22} & \cdots & A_{2n}\\ \cdots & \cdots & \cdots & \cdots\\ A_{n1} & A_{n2} & \cdots & A_{nn} \end{pmatrix}\\ A_{ij}&=\begin{cases} 1, & \text{if } x_j \text{ is a neighbor of } x_i\\ 0, & \text{otherwise} \end{cases}\\ \text{or}\ A_{ij}&=\begin{cases} \exp(-\left\|x_j - x_i\right\|^2/(2\sigma^2)), & \text{if } x_j \text{ is a neighbor of } x_i\\ 0, & \text{otherwise} \end{cases} \end{align} \] 修改相关矩阵：

类内散度矩阵 \[ S_w=\frac{1}{2}\sum_{i,j}\overline{A}_{ij}^{(w)}(x_i - x_j)(x_i - x_j)^T\\ \overline{A}_{ij}^{(w)}=\begin{cases} A_{ij}/n_c, & \text{if } y_i = y_j = c\\ 0, & \text{if } y_i\neq y_j \end{cases} \]
类间散度矩阵 \[ S_b=\frac{1}{2}\sum_{i,j = 1}^{n}\overline{A}_{ij}^{(b)}(x_i - x_j)(x_i - x_j)^T\\ \overline{A}_{ij}^{(b)}=\begin{cases} A_{ij}(1/n - 1/n_c), & \text{if } y_i= y_j = c\\ 1/n, & \text{if } y_i \neq y_j \end{cases} \]

特征选择

特征变化和特征选择是处理高维数据的两大主流技术。

任务：给定一个学习任务、对于给定的特征数据特征集，从中选出与任务相关(对学习任务有利)的特征子集。

目的：降维、去除冗余、选择与任务相关的特征。

评价准则

“理想”评价准则：对分类任务，评价准则$J_{ij}$反映在一组特征下，第$i$类和第$j$类的可分尺度。

基于距离的评价准则

记$x_i^{(k)}\in R^d$和$x_j^{(l)}\in R^d$分别为类别$\omega_i$和$\omega_j$的两个样本。记两者之间的距离为：$d(x_i^{(k)},x_j^{(l)})$。

定义所有类别上的总距离为： \[ J_d(x)=\frac{1}{2}\sum_{i = 1}^{c}\sum_{j = 1}^{c}P_iP_j\sum_{k = 1}^{n_i}\sum_{l = 1}^{n_j}d(x_i^{(k)},x_j^{(l)}) \] 其中，$P_i$：第$i$类的先验概率；$n_i$：第$i$类的样本数。

若采用平方欧氏距离：$d(x_i^{(k)},x_j^{(l)})=(x_i^{(k)} - x_j^{(l)})^T(x_i^{(k)} - x_j^{(l)})$，则有： \[ J_d(x)=\sum_{i = 1}^{c}P_i\left[\frac{1}{n_i}\sum_{k = 1}^{n_i}(x_i^{(k)} - m_i)^T(x_i^{(k)} - m_i)+(m - m_i)^T(m - m_i)\right] \] 其中，$m_i$：第$i$类的中心；$m$：所有数据点的中心。

利用散度矩阵，可将上式整理成更简单的形式。

定义类间/类内散度如下： \[ S_b=\sum_{i = 1}^{c}P_i(m_i - m)(m_i - m)^T\\ S_w=\sum_{i = 1}^{c}P_i\frac{1}{n_i}\sum_{k = 1}^{n_i}(x_i^{(k)} - m_i)(x_i^{(k)} - m_i)^T\\ J_d(x)=\text{tr}(S_b + S_w) \]

特别地，上述计算可以定义在任何特征子集上！

类似于线性判别准则，可定义如下的评价准则，其核心思想是使类内散度尽可能小，类间、散度尽可能大。常用的5个判据： \[ \begin{align} J_1(x)&=\text{tr}(S_b + S_w)\\ J_2(x)&=\text{tr}(S_w^{-1}S_b)\\ J_3(x)&=\frac{\text{tr}(S_b)}{\text{tr}(S_w)}\\ J_4(x)&=\frac{\vert S_b\vert}{\vert S_w\vert}\\ J_5(x)&=\frac{\vert S_b + S_w\vert}{\vert S_w\vert} \end{align} \]

基于分布的评价准则：基于类条件概率密度函数

假设定义了基于类条件概率密度函数$p(x\vert \omega_i)$和$p(x\vert \omega_j)$之间的一个“距离”函数：

该“距离”函数应该是非负的；
该距离应反映这两个条件分布之间的重合程度；
- 当这两个条件分布不重叠时，该距离函数取得最大值；
- 当这两个条件分布一样时，该距离函数应该取零值。

定义$x$点处的对数似然比： \[ L_{ij}(x)=\ln\frac{p(x|\omega_i)}{p(x|\omega_j)} \] KL散度：也称为相对熵(relative entropy)，定义为对数似然比的数学期望： \[ KL_{ij}\triangleq E[L_{ij}(x)]=\int p(x|\omega_i)\ln\frac{p(x|\omega_i)}{p(x|\omega_j)}dx \] 注意，KL散度不是一个度量：$KL_{ij}\neq KL_{ji}$。可将其变成一个度量： \[ J_{ij}=KL_{ij}+KL_{ji}=\int\left[p(x|\omega_i)-p(x|\omega_j)\right]\ln\frac{p(x|\omega_i)}{p(x|\omega_j)}dx \]

基于熵的评价准则：基于类后验概率分布

后验概率$P(\omega_i\vert x)$反映特征$x$刻画类别$i$的有效性。

两个极端例子：

如果后验概率对于所有的类别都一样，即$P(\omega_i\vert x)=\frac{1}{c}$，则说明该特征对类别没有任何鉴别性；

如果后验概率对于类别$i$为$1$，对其他类别均为$0$，即$P(\omega_i\vert x)=1$，则说明特征非常有效。

对于某个给定特征，样本属于各类的后验概率越平均，越不利于分类；如果越集中于某一类，则越有利于分类。因此，可利用后验概率的信息熵来度量特征对类别的可分性。

信息熵：可用来衡量一个随机事件发生的不确定性，不确定越大，信息熵越大。

香农熵	平方熵
$H(x)=-\sum_{i = 1}^{c}P(\omega_i\vert x)\log_2P(\omega_i\vert x)$	$H(x)=2\left[1-\sum_{i = 1}^{c}(P(\omega_i\vert x))^2\right]$

使用时要求期望：$E[H(x)]=\int p(x)H(x)dx$

最优特征选择方法

穷举法

从给定的$d$个特征中，挑选出$m$个特征，若采用穷举法，需要遍历$\frac{d!}{(d - m)!m!}$个子集。当$d$很大时，该方法计算量巨大。能否有更聪明的搜索方法？

分支界定法

基本思想：将所有可能的特征组合以树的形式进行表示，采用分枝定界方法对树进行搜索，使得搜索过程尽早达到最优解，而不必搜索整个树。

基本前提：特征评价准则对特征具有单调性，即特征增多时，判据值不会减少： \[ X_1\subseteq X_2\subseteq\cdots\subseteq X_m\Rightarrow J(X_1)\leq J(X_2)\leq\cdots\leq J(X_m) \] 基于KL散度和基于信息熵的评价准则满足上述要求。

特征子集的树表示

根节点包含全部特征；
每一个节点，在父节点基础上去掉一个特征，并将去掉的特征序号写在节点的旁边；
对$d$维特征，若选择$m$个特征，每一级去掉一个特征，则需要$d - m$层达到所需特征数量，即树的深度为$d - m$。($d = 4,m = 2$)

树的生长过程（树的构造）

将所有特征组成根节点，根节点记为第0层；
对于第1层，分别计算“去掉上一层节点单个特征后”剩余特征的评价判据值，按判据值从小到大进行排序，按从左到右的顺序生成第1层的节点；
对于第2层，针对上一层最右侧的节点开始，重复第2步；
依次类推，直到第$d - m$层，到达叶子节点，记录对应的判据值$J$，同时记录对应的特征选择集合。

回溯：从第一个叶子结点开始，对树进行回溯

树的回溯的总体思路：对树搜索时进行分枝限界，从右到左、从上到下

特征选择的次优方法

过滤式选择方法

基本思想：过滤式方法先对数据集进行特征选择，再训练分类器。

核心任务：如何定义特征的评价准则和搜索策略

算法特点：

特征选择过程与后续学习器无关；
启发式特征选择方法，无法获得最优子集；
与包裹式选择方法相比，计算量降低了

单独特征选择：Relief方法

假设：特征相互独立，子集性能=包含各特征性能之和。

二分类：

对于样本$x_i$:

猜中近邻(nearest-hit): 其同类样本中的最近邻$x_{i,nh}$
猜错近邻(nearest-miss): 其不同类样本中的最近邻$x_{i,nm}$

特征性能判据：

多分类

包裹式特征选择方法

过滤式特征选择方法	包裹式特征选择方法
先对数据集进行特征选择，然后再训练分类器	对给定分类方法，选择最有利于提升分类性能的特征子集
特征选择过程与分类单独进行，特征选择评价判据间接反应分类性能	特征选择过程与分类性能相结合，特征评价判据为分类器性能

通常采用交叉验证来评价选取的特征子集的好坏。
$k$折交叉验证($k$-fold cross validation)，留一法(Leave - one - out)
包裹式特征选择方法对分类器的基本要求：
- 分类器能够处理高维特征向量；
- 特征维度很高、样本个数较少时，分类器依然可以取得较好的效果。

主要方法

直观方法：给定特征子集，训练分类器模型，以分类器错误率为特征性能判据，进行特征选择。
- 需要大量尝试不同的特征组合，计算量大。
替代方法(递归策略)：首先利用所有的特征进行分类器训练，然后考查各个特征在分类器中的贡献，逐步剔除贡献小的特征。
- 递归支持向量机（R - SVM：Recursive SVM）
- 支持向量机递归特征剔除（SVM - RFE）
- Adaboost

嵌入式特征选择--基于$L_1$范数的特征选择

基本思路：在学习 w 的时候，对 w 进行限制，使其不仅能满足训练样本的误差要求，同时使得 w 中非零元素尽可能少（只使用少数特征）。

总结

特征选择的一般技术路线

确定特征子集
评价特征子集性能

评价特征子集性能常用的可分性判据

基于类内类间距离的可分性判据
基于熵的可分性判据
基于SVM模型的可分性判据

确定特征选择子集的方法

基于树的方法（最优算法）：基于分枝限界技术对特征子集的树表示进行遍历，只需要查找一小部分特征组合，即可找到全局最优的特征组合
遍历法（次优算法）：顺序前向法、顺序后向法、增减r法
稀疏约束

根据特征选择与分类器的结合程度

过滤式特征选择方法：“选择”与“学习”独立
包裹式特征选择方法：“选择”依赖“学习”
嵌入式特征选择方法：“选择”与“学习”同时进行

成分	对应公式
数据点\(x_i\)沿\(w_1\)的投影\(y_i\)	\(y_i = w_1^Tx_i\)
均值\(\overline{x}\)沿\(w_1\)的投影\(\overline{y}\)	\(\overline{y}=w_1^T\overline{x},\ \overline{x}=\frac{1}{n}\sum_{i = 1}^{n}x_i\)
投影数据（沿投影方向\(w_1\)）的方差	\(\text{var}=\frac{1}{n}\sum_{i = 1}^{n}(w_1^Tx_i - w_1^T\overline{x})^2\)
想要获得使投影数据方差最大化的方向\(w_1\)	\(\max\frac{1}{n}\sum_{i = 1}^{n}(w_1^Tx_i - w_1^T\overline{x})^2,\ w_1^Tw_1 = 1\)

模式识别-Ch7-特征提取与特征选择