Ch 06.特征降维和选择 Part 1 特征降维 1

误差与维数 例子 贝叶斯误差概率 r增加，误差概率 减小 ， 假设各特征独立： 到 的马氏距离 引入新的特征可使r增大，进而降低误差概率

维度灾难 在实际应用中 对于高维数据，“维度灾难”使解决模式识别问题非常困难，此时，往往要求首先降低特征向量的维度 当特征个数增加到某一个临界点后，继续增加反而会导致分类器的性能变差——“维度灾难”（curse of dimensionality） 原因？ 假设的概率模型与真实模型不匹配 训练样本个数有限，导致概率分布的估计不准 …… 对于高维数据，“维度灾难”使解决模式识别问题非常困难，此时，往往要求首先降低特征向量的维度

降维 降低特征向量维度的可行性 降低维度的方法 特征向量往往是包含冗余信息的！ 特征组合 特征选择 有些特征可能与分类问题无关 特征之间存在着很强的相关性 降低维度的方法 特征组合 把几个特征组合在一起，形成新的特征 特征选择 选择现有特征集的一个子集

降维 降维问题 线性变换 vs. 非线性变换 利用类别标记（有监督） vs. 不用类别标记（无监督） 不同的训练目标 最小化重构误差（主成分分析，PCA） 最大化类别可分性（线性判别分析，LDA） 最小化分类误差（判别训练，discriminative training） 保留最多细节的投影（投影寻踪，projection pursuit） 最大限度的使各特征之间独立（独立成分分析，ICA）

主成分分析（PCA） 用一维向量表示d维样本 用通过样本均值m的直线（单位向量为e）上的点表示样本 最小化平方重构误差 唯一决定了 (xk-m)在e上的投影

主成分分析（PCA） 用一维向量表示d维样本 e xk ak m

主成分分析（PCA） 寻找e的最优方向 散布矩阵（scatter matrix）

主成分分析（PCA） 使 最小的e最大化 拉格朗日乘子法（约束条件 ） 结论：e为散布矩阵最大的本征值对应的本征向量 拉格朗日乘子法（约束条件 ） 结论：e为散布矩阵最大的本征值对应的本征向量 是S的本征值（eigenvalue） e是S的本征向量（eigenvector） 最大本征值 对应 的最大值

主成分分析（PCA） 将一维的 扩展到 维空间 用 来表示 最小化平方误差

主成分分析（PCA） 将一维的 扩展到 维空间 结论： 使得平方误差最小的向量 分别为散布矩阵S的 个最大本征值对应的本征向量 将一维的 扩展到 维空间 结论： 使得平方误差最小的向量 分别为散布矩阵S的 个最大本征值对应的本征向量 S为实对称矩阵，所以 相互正交 可被视为特征空间的一个子空间的单位向量基 为 对应于基 的系数，或在 上的投影 称为主成分（principal component） 几何意义 为沿数据云团方差最大的方向的直线 利用PCA，可以将d维数据降维到 维，同时使得降维后的数据与源数据的平方误差最小 e_k称为第k个PC的负荷loading

主成分分析（PCA） 主成分分析步骤（d维降为 维） 计算散布矩阵S 计算S的本征值和本证向量 将本征向量按相应的本征值从大到小排序 选择最大的d’个本征向量作为投影向量 ，构成投影 矩阵W，其中第i列为 对任意d维样本x，其用PCA降维后的d’维向量为

主成分分析（PCA） 通常，最大的几个本征值占据了所有本征值之和的绝大部分 少数几个最大本征 值对应的本征向量 即可表示原数据中 的绝大部分信息， 而剩下的小部分（ 即对应较小的本征 值的本征向量所表 示的信息），通常 可以认为是数据噪 声而丢掉

主成分分析（PCA）

主成分分析（PCA） 数据集：Iris 原维度：4 UCI数据集

主成分分析（PCA） 用PCA降到2维 用PCA降到3维

奇异值分解（SVD） PCA中对散布矩阵S的本征值分解计算量较大，如特征向量维度较高，直接对S进行本征值分解十分困难。 图像： 散布矩阵： 的矩阵本征值分解？ 空间复杂度和时间复杂度均无法接受！

奇异值分解（SVD） 解决方案：不直接对S进行本征值分解，而利用SVD对一个较小的矩阵进行本征值分解 SVD定理 设A是一个秩为n的 矩阵，则存在两个正交矩阵 以及对角阵 满足 其中： 为矩阵 和 的非零本征值， 和 分别为 和 对应于 的本征向量。 该分解称为矩阵A的奇异值分解（Singular Value Decomposition，SVD）， 为A的奇异值。

奇异值分解（SVD） 推论 利用SVD简化S的本征值分解 散布矩阵 其中， 令 若 ，则对R进行本征值分解要比直接对S进行本征值分解快。 例如，对绝大多数图像训练集来讲，图像的像素数要远远大于训练集中的样本个数，即

奇异值分解（SVD） 对R进行本征值分解 本征值： 本征向量： 根据 ，得出 的本征向量为 矩阵的本征值分解 矩阵的本征值分解

Fisher线性判别分析 PCA方法寻找用来有效表示数据（从最小平方误差的意义上讲）的主轴方向 线性判别分析（linear discriminant analysis, LDA）寻找的是用来有效分类的方向

Fisher线性判别分析 假设 目标：投影到w上后，投影点更易分类 n个d维样本 ，他们分属两个类别 和 其中，n1个属于类别 的样本组成样本子集 ， n2个属于类别 的样本组成样本子集 单位向量w方向上的投影 投影点 根据源数据的类别也分成两个子集 和 目标：投影到w上后，投影点更易分类 不同类的投影点尽量分开 同一类的投影点尽量靠近

Fisher线性判别分析 不同类的投影点尽量分开 设 为第i类的样本均值 投影后的样本均值 投影后的两类样本均值之间的距离 此距离越大，说明两类投影点分得越开

Fisher线性判别分析 同一类的投影点尽量靠近 投影类内散布 各类的投影类内散布之和 此总类内散布体现了投影后类内的“紧致”程度，其越小，说明同一类内的投影点越靠近

Fisher线性判别分析 Fisher准则函数 最大化J(w)即使得类间差距（分子）最大化同时类内差距（分母）最小化 两类样本均值之间的距离 总类内散布 最大化J(w)即使得类间差距（分子）最大化同时类内差距（分母）最小化

Fisher线性判别分析 把J(w)表示为w的表达式 原数据空间类内散布矩阵 总类内散布矩阵 推导

Fisher线性判别分析 把J(w)表示为w的表达式 总类间散布矩阵 推导

Fisher线性判别分析 Fisher准则函数 Fisher准则函数最大化，w需满足 Sw非奇异 广义本征值问题 普通本征值问题

Fisher线性判别分析 2类推广到c类——多重判别分析 总类内散布矩阵

Fisher线性判别分析 2类推广到c类——多重判别分析 总体均值向量 总体散布矩阵

Fisher线性判别分析 2类推广到c类——多重判别分析 推导 类间散布矩阵

Fisher线性判别分析 2类推广到c类——多重判别分析 类间散布矩阵 投影 变换矩阵 投影点 原样本点

Fisher线性判别分析 2类推广到c类——多重判别分析 在由W张成的投影子空间中

Fisher线性判别分析 2类推广到c类——多重判别分析 将 代入，得到 求能够最有效分类的W：使得类间离散度和类内离散度的比值最大 将 代入，得到 求能够最有效分类的W：使得类间离散度和类内离散度的比值最大 离散度度量：散布矩阵的行列式

Fisher线性判别分析 2类推广到c类——多重判别分析 准则函数 使J(W)最大化的W的列向量由如下广义本征值问题中最大本征值对应的本征向量组成 SB为c个秩为1或0的矩阵之和，其中只有c-1个矩阵相互独立，所以SB的秩不大于c-1 所以如上广义本征值问题最多有c-1个非零本征值，对应c-1个本征向量，所以W最多有c-1列

Fisher线性判别分析

Fisher线性判别分析 投影到主成分方向 投影到LDA方向

降维实例：卫星图像分析 原卫星图像以及前6个PCA主成分投影方向

降维实例：卫星图像分析 原卫星图像以及前6个LDA投影方向

降维实例：卫星图像分析 原卫星图像以及前6个PCA主成分投影方向

降维实例：卫星图像分析 原卫星图像以及前6个LDA投影方向

降维实例：人脸识别 典型人脸图像集合

人脸图像的前15个PCA主成分投影方向，又称为“本征脸”（eigenface） 降维实例：人脸识别 人脸图像的前15个PCA主成分投影方向，又称为“本征脸”（eigenface）

Ch 06.特征降维和选择 Part 2 特征选择 44

降维 降低维度的方法 特征组合 把几个特征组合在一起，形成新的特征 特征选择 选择现有特征集的一个子集

特征选择 特征选择方法包含两个主要组成部分 搜索过程 选择准则 在所有候选特征子集中进行系统搜索的过程 原则上，穷尽搜索（exhaustive search）即能够找到最优子集。实践中，往往采用更高效的非穷尽搜索算法，找到次优解 用于判断某个特征子集是否优于另一个特征子集的标准 原则上，选择准则即为系统性能的评价准则，如分类错误率等。实践中，往往采用简化的选择准则。

搜索过程 循序向前选择法 （Sequential Forward Selection，SFS） 首先，最好的单个特征被选出 然后，用所有其他特征与第一个选出的特征组合成候选特征对，找出最好的一对 再用剩下的特征分别与上一步选出的最好特征对组成候选特征三元组，找出最好的三元组 该过程知道选出足够多的特征停止

搜索过程 循序向前选择法 （Sequential Forward Selection，SFS）

搜索过程 循序向前选择法 （Sequential Forward Selection，SFS） 缺点 最优子集中的每个特征分别单独考虑时，并不一定都为最优

搜索过程 循序向前选择法：实例——卫星图像分析

搜索过程 循序向后选择法 （Sequential Backward Selection，SBS） 首先，选择所有d个特征 然后，从所有特征中任意去掉一个形成d个候选的d-1特征集，从中选出最好的一个 再从上一步得到的d-1特征集中任意去掉一个特征形成d-1个d-2特征集，从中选出最好的一个 该过程直到特征集中的特征个数到达预先设定的值时停止

搜索过程 循序向后选择法 （Sequential Backward Selection，SBS） 因为SBS考虑的特征数目大于等于期望的特征数目，所以SBS通常比SFS需要更多的选择准则计算

搜索过程 循序向后选择法：实例——卫星图像分析

搜索过程 其他搜索过程 单个最佳特征子集 … 直接搜索最佳的单个特征（每次仅用一个特征，计算选择准则），用它们构成的集合作为特征选择结果 虽然简单，但是往往不可靠 只有当各特征之间完全独立的情况下能找到最优特征子集 …

选择准则 理想方法 简化方法 用选定的特征子集表示训练样本，训练分类器，然后测试该分类器的泛化误差（如采用交叉验证等方法） 因为对每个特征子集都需要训练一个分类器，因此计算量很大 简化方法 定义某种类内距离度量来描述采用某个特征子集时的类可分度 不需要为每个特征子集训练一个分类器，因此计算量较小

选择准则 类内距离 类内散布度

选择准则 类内距离 均方距离

小结 误差与维度 解决“维度灾难”的办法：降低维度的方法 误差随特征数增加而减小，而当特征个数增加到某一个临界点后，继续增加反而会导致分类器的性能变差——“维度灾难” 解决“维度灾难”的办法：降低维度的方法 特征组合 把几个特征组合在一起，形成新的特征 特征选择 选择现有特征集的一个子集

小结 降维方法的选择依赖于应用领域以及训练数据的基本情况 特征组合降维有可能提供较好的分类能力，但是新的特征往往丧失具体的物理意义 特征选择能够在降低维度的同时保留特征的物理意义

小结 特征组合降维方法 主成分分析（PCA） 寻找用来有效表示数据的投影 无监督 线性判别分析（LDA） 寻找用来有效分类的投影 有监督

小结 特征选择降维方法 搜索过程 循序向前选择法SFS 循序向后选择法SBS 选择准则 泛化误差 类内距离度量