降维与特征选择

机器学习算法的有效性和计算复杂度是敏感于数据的特征表达和维度,数据的降维表示方法,主要包括特征选择和特征提取两种方法。

  • 特征抽取:在已有的特征上,采用特征变换的方法,生成新的特征集合。
  • 特征选择:使用某些方法,从当前特征集合中选择出特征子集。

特征选择

特征选择的处理过程:

特征子集生成

  • 穷举法:计算特征的所有可能组合,并逐一评价,选择的特征数为 $d$, 可能的组合数为 $C_D^d$,只适用于 $D$ 比较小的场景。

  • 贪心法(单独最优特征组合):对每个特征分别评估,找前 $d$ 个单独最优特征,算法简单但没有考虑特征之间的关系,存在特征冗余。

  • SFS(前向序贯):每次加入 $1$ 个特征,该特征使得新的特征组合最优,其特点是一旦增加,无法删除。

  • GSFS(广义前向序贯):每次加入 $k$ 个特征,使加入特征后的组合最优,显然该算法的计算量比 $SFS$ 要大。

  • SBS(后向序贯):每次减掉 $1$ 个特征,使剩余特征组合最优,其特点是一旦删除,无法增加。

  • GSBS(广义后向序贯):每次减掉 $k$ 个特征,使剩余特征组合最优,显然该算法的计算量比 $SBS$ 要大。

  • L-R法::每次先增加 $L$ 个再减 $R$ 个,或者每次先减少 $R$ 个再增加 $L$ 个。

  • 广义L-R法:增 $L$ 和减 $R$ 分 $Z$ 步进行。

特征评价准侧

  • 可分性度量:在选择的特征集下,采用类别可分性的程度,评价特征选择的好与坏。常用于 $Filter$ 框架下,评价准则为距离准则、概率可分、熵可分准则。

  • 学习算法精度的度量:在选择的特征集下,通过学习算法的精确度,评价特征选择的好与坏。 常用于 $wrapper$ 框架下。

可分性度量

基于距离的可分性判据

常用的数据统计量包括类内散度矩阵,总类内散度矩阵以及类间散度矩阵等。

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

从类别概率密度的角度,讨论两个类别的交叠程度。

基于熵的可分性判据

特征选择方法

Filter 方法

不依赖于分类器,只是用数据来确定分类好坏。这里的数据要求是带标签数据,不然需要依赖分类器。

  1. 基本方法:$Filter$ 框架 + 特征子集生成 + 距离评价。


  1. $Relief$ 算法

Wrapper 方法

选择特征后,通过分类器分类来进行评估。
$LVM$ 方法:随机产生一个特征子集,计算错误率,若错误率小于之前选好的特征集合的最小错误率,则合并到选好的特征集中。



Embedded 方法

特征选择过程在学习算法中完成,目标是完成学习过程。
特点:不是专门的特征选择过程(岭回归)
缺点:计算复杂度高

特征提取

线性变换

特征提取的目标:学习变换矩阵

左边的 $L$ 代表样例的低维表示,中间 $X$ 代表样例,右边的 $W$ 代表新的特征空间。其实质是求一个 $W$ ,使得样本映射到 $W$ 上,使得各个特征长度变化最小。

$$ \bf X \approx \hat X = L · R $$

$\hat X$ 表示近似矩阵,$L$ 和 $R$ 分别为左右子矩阵,无损压缩时为等号,通常会有有损压缩。

主成分分析

$PCA$ 的作用就是分析选出最重要的特征,本质上是将方差最大的方向作为主要特征,并且在各个正交方向上将数据“去相关”,也就是让它们在不同正交方向上没有相关性。通常我们认为信息具有较大的方差,而噪声有较小的方差,信噪比就是信号与噪声的方差比,所以我们希望投影后的数据方差越大越好。因此我们认为,最好的 $k$ 维特征是将 $n$ 维样本点转换为 $k$ 维后,每一维上的样本方差都很大。

$$ Pattern \approx low-dimensional\;representation * eigen \; pattern $$

其目标就是学习 $eigen \; pattern$,目标函数为均方误差最小(求最优重构子空间)。

所以目标函数可以重写为:

$$ \min_{L,W} ||X-LW^T||^2
\\ s.t. W^TW = I$$


求解目标函数:

样本标准化

主成分分析事先对所有样本进行标准化。因为其用于高维数据的降维,它可以将原来高维的数据投影到某个低维的空间上并使得其方差尽量大。如果数据其中某一特征(矩阵的某一列)的数值特别大,那么它在整个误差计算的比重上就很大,那么可以想象在投影到低维空间之后,为了使低秩分解逼近原数据,整个投影会去努力逼近最大的那一个特征,而忽略数值比较小的特征。

算法过程

  • 输入数据
  • 归一化数据
  • 求协方差矩阵
  • 求协方差矩阵的特征值
  • 将特征值降序排列
  • 选择得到最大的 $k$ 个特征值
  • 转化得到降维后的数据

需要注意的问题

协方差矩阵中,主对角线上的元素代表这一维度上数据的方差,而副对角线上的元素代表元素之间的协方差

线性鉴别分析

$PCA$ 不能保证类别区分的有效性。
$LDA$ 特征的优点:类内最小、类间最大。

非线性变换

核方法的特征提取

流形学习

局部线性变换 $LLE$ 算法流程:

非负矩阵分解

基本思想:通过矩阵分解,进行数据降维;分解后的矩阵为非负矩阵
目标函数可以是范数误差最下,也可以是 $K-L$ 误差最小

参考文献:
[1] 周晓飞,《统计机器学习》,中国科学院大学2017年秋季研究生课程