1、误差与维数 例子 贝叶斯误差概率 r增加，误差概率 减小 ， 假设各特征独立：( |)(, ),1,2jipNj x 12()()PP2/2/21( )urP eedu211212()()tr 到 的马氏距离12( )P er ( )0P e 12(,)ddiag 22121diiiir引入新的特征可使r增大，进而降低误差概率( )P e维度灾难 在实际应用中 当特征个数增加到某一个临界点后，继续增加反而会导当特征个数增加到某一个临界点后，继续增加反而会导致分类器的性能变差致分类器的性能变差“维度灾难维度灾难”（curse of dimensionality） 原因？ 假设的概率模型与真实模型
2、不匹配 训练样本个数有限，导致概率分布的估计不准 对于高维数据，“维度灾难”使解决模式识别问题非常困难，此时，往往要求首先降低特征向量的维度降维 降低特征向量维度的可行性可行性特征向量往往是包含冗余信息冗余信息的！ 有些特征可能与分类问题无关无关 特征之间存在着很强的相关性相关性 降低维度的方法 特征组合特征组合把几个特征组合在一起，形成新的特征 特征选择特征选择选择现有特征集的一个子集降维 降维问题 线性变换线性变换 vs. 非线性变换非线性变换 利用类别标记（有监督有监督） vs. 不用类别标记（无监督无监督） 不同的训练目标 最小化重构误差（主成分分析主成分分析，PCA） 最大化类别可分
3、性（线性判别分析线性判别分析，LDA） 最小化分类误差（判别训练判别训练，discriminative training） 保留最多细节的投影（投影寻踪投影寻踪，projection pursuit） 最大限度的使各特征之间独立（独立成分分析独立成分分析，ICA）主成分分析（PCA） 用一维向量表示d维样本 用通过样本均值m的直线（单位向量为e）上的点表示样本 最小化平方重构误差()tkka e xmkkaxme221111222111(, )()()2()nnnkkkkkknnntkkkkkkkJ aaaaaaemexexmee xmxmkx 唯一决定了kakx11( , )22 ()0tn
4、kkkJ aaaaee xm(xk-m)在在e上的投影上的投影主成分分析（PCA） 用一维向量表示d维样本eakxkm主成分分析（PCA） 寻找e的最优方向()tkka e xm22211111(, )2()nnntnkkkkkkkJ aaaaeee xmxm2221111221121121( )2 ()()()nnnkkkkkknntkkkknnttkkkkkntkkJaa exme xmxme xm xm exme Sexm1()()ntkkkSxm xm散布矩阵散布矩阵（scatter matrix）(1)nC主成分分析（PCA） 使 最小的e最大化 拉格朗日乘子法（约束条件 ） 结论：
5、结论：e为散布矩阵最大的本征值对应的本征向量为散布矩阵最大的本征值对应的本征向量(1)ttue See e1( )J ete Se220uSeee1te eSee 是S的本征值（eigenvalue）e是S的本征向量（eigenvector）tte See e最大本征值 对应 的最大值te Se主成分分析（PCA） 将一维的 扩展到 维空间 用 来表示 最小化平方误差1dkkiiiaxmeka()ddd12kkkkdaaaykx211( )nddkiikkiJaemex主成分分析（PCA） 将一维的 扩展到 维空间 结论：结论： 使得平方误差最小的向量 分别为散布矩阵S的 个最大本征值对应的本
6、征向量 S为实对称矩阵，所以 相互正交 可被视为特征空间的一个子空间的单位向量基 为 对应于基 的系数，或在 上的投影 称为主成分主成分（principal component） 几何意义 为沿数据云团方差最大的方向方差最大的方向的直线 利用PCA，可以将d维数据降维降维到 维，同时使得降维后的数据与源数据的平方误差最小ka()ddd12,de eed12,de ee12,de eekiakxieiekia12,de ee()ddd主成分分析（PCA） 主成分分析步骤（d维降为 维）1. 计算散布矩阵S2. 计算S的本征值和本证向量3. 将本征向量按相应的本征值从大到小排序4. 选择最大的d个
7、本征向量作为投影向量 ，构成投影 矩阵W，其中第i列为5. 对任意d维样本x，其用PCA降维后的d维向量为()ddd1()()ntkkkSxm xmSee12,de eeietyW xdd主成分分析（PCA） 通常，最大的几个本征值占据了所有本征值之和最大的几个本征值占据了所有本征值之和的绝大部分的绝大部分 少数几个最大本征少数几个最大本征值对应的本征向量值对应的本征向量即可表示原数据中即可表示原数据中的绝大部分信息，的绝大部分信息，而剩下的小部分（而剩下的小部分（即对应较小的本征即对应较小的本征值的本征向量所表值的本征向量所表示的信息），通常示的信息），通常可以认为是数据噪可以认为是数据噪声
8、而丢掉声而丢掉主成分分析（PCA）主成分分析（PCA） 数据集：Iris 原维度：4主成分分析（PCA）用用PCA降到降到2维维用用PCA降到降到3维维奇异值分解（SVD） PCA中对散布矩阵S的本征值分解计算量较大，如特征向量维度较高，直接对S进行本征值分解十分困难。 例如对图像的PCA分析： 图像： 散布矩阵： 的矩阵本征值分解？100 1001()()ntkkkSxm xm10000 10000See10000 10000空间复杂度和时间复杂度均无法接受！空间复杂度和时间复杂度均无法接受！奇异值分解（SVD） 解决方案：不直接对S进行本征值分解，而利用SVD对一个较小的矩阵进行本征值分解
9、 SVD定理定理 设A是一个秩为n的 矩阵，则存在两个正交矩阵以及对角阵满足其中： 为矩阵 和 的非零本征值， 和 分别为 和 对应于 的本征向量。该分解称为矩阵A的奇异值分解奇异值分解（Singular Value Decomposition，SVD）， 为A的奇异值。dn12,d nTnUu uuU UI12,n nTdVv vv V VI1212,n nnndiag 12TAU V(1,2, )iinTAATA AiuivTAATA Aii奇异值分解（SVD） 推论散布矩阵其中，令若 ，则对R进行本征值分解要比直接对S进行本征值分解快。12TAU V12UAV1()()ntTd dkkk
10、Sxm xmAA12,d nnAxm xmxmTn nRA Adn例如，对绝大多数图像训练集来讲，图像的像素例如，对绝大多数图像训练集来讲，图像的像素数要远远大于训练集中的样本个数，即数要远远大于训练集中的样本个数，即dn奇异值分解（SVD） 对R进行本征值分解 本征值： 本征向量： 根据 ，得出 的本征向量为(1,2, )iiniv12UAVTSAA1iiiuAv 矩阵的矩阵的本征值分解本征值分解dd 矩阵的矩阵的本征值分解本征值分解nnFisher线性判别分析 PCA方法寻找用来有效表示有效表示数据（从最小平方误差的意义上讲）的主轴方向 线性判别分析（linear discriminant
11、 analysis, LDA）寻找的是用来有效分类有效分类的方向Fisher线性判别分析 假设 n个d维样本 ，他们分属两个类别 和 其中，n1个属于类别 的样本组成样本子集 ， n2个属于类别 的样本组成样本子集 单位向量w方向上的投影 投影点 根据源数据的类别也分成两个子集 和 目标：投影到w上后，投影点更易分类 不同类的投影点尽量分开不同类的投影点尽量分开 同一类的投影点尽量靠近同一类的投影点尽量靠近Fisher线性判别分析 不同类的投影点尽量分开不同类的投影点尽量分开 设 为第i类的样本均值 投影后的样本均值 投影后的两类样本均值之间的距离1ittix Dinw xw m此距离越大，说
12、明两类投影点分得越开此距离越大，说明两类投影点分得越开Fisher线性判别分析 同一类的投影点尽量靠近同一类的投影点尽量靠近 投影类内散布 各类的投影类内散布之和此总类内散布体现了投影后类内的此总类内散布体现了投影后类内的“紧致紧致”程度，程度，其越小，说明同一类内的投影点越靠近其越小，说明同一类内的投影点越靠近Fisher线性判别分析 Fisher准则函数总类内散布总类内散布两类样本均值之间的距离两类样本均值之间的距离最大化最大化J(w)即使得即使得类间差距类间差距（分子）最大化同时（分子）最大化同时类内类内差距差距（分母）最小化（分母）最小化Fisher线性判别分析 把J(w)表示为w的表
13、达式 原数据空间类内散布矩阵 总类内散布矩阵 推导Fisher线性判别分析 把J(w)表示为w的表达式 总类间散布矩阵 推导221212ttmmw mw mFisher线性判别分析 Fisher准则函数 Fisher准则函数最大化，w需满足广义本征值问题广义本征值问题Sw非奇异非奇异普通本征值问题普通本征值问题Fisher线性判别分析 2类推广到c类多重判别分析 总类内散布矩阵Fisher线性判别分析 2类推广到c类多重判别分析 总体均值向量 总体散布矩阵Fisher线性判别分析 2类推广到c类多重判别分析 推导类间散布矩阵类间散布矩阵Fisher线性判别分析 2类推广到c类多重判别分析 类间
14、散布矩阵 投影原样本点原样本点投影点投影点变换矩阵变换矩阵Fisher线性判别分析 2类推广到c类多重判别分析 在由W张成的投影子空间中Fisher线性判别分析 2类推广到c类多重判别分析 将 代入，得到 求能够最有效分类的W：使得类间离散度离散度和类内离散度离散度的比值最大 离散度度量：散布矩阵的行列式Fisher线性判别分析 2类推广到c类多重判别分析 准则函数 使J(W)最大化的W的列向量由如下广义本征值问题中最大本征值对应的本征向量组成SB为为c个秩为个秩为1或或0的矩阵之和，其中只有的矩阵之和，其中只有c-1个矩阵相互独立，所个矩阵相互独立，所以以SB的秩不大于的秩不大于c-1所以如
15、上广义本征值问题最多有所以如上广义本征值问题最多有c-1个非零本征值，对应个非零本征值，对应c-1个本个本征向量，所以征向量，所以W最多有最多有c-1列列Fisher线性判别分析Fisher线性判别分析投影到主成分方向投影到主成分方向投影到投影到LDA方向方向降维实例：卫星图像分析原卫星图像以及前原卫星图像以及前6个个PCA主成分投影方向主成分投影方向降维实例：卫星图像分析原卫星图像以及前原卫星图像以及前6个个LDA投影方向投影方向降维实例：卫星图像分析原卫星图像以及前原卫星图像以及前6个个PCA主成分投影方向主成分投影方向降维实例：卫星图像分析原卫星图像以及前原卫星图像以及前6个个LDA投影
16、方向投影方向降维实例：人脸识别典型人脸图像集合典型人脸图像集合降维实例：人脸识别人脸图像的前人脸图像的前15个个PCA主成分投影方向，又称主成分投影方向，又称为为“本征脸本征脸”（eigenface）Ch 06.特征降维和选择Part 2 特征选择降维 降低维度的方法 特征组合特征组合把几个特征组合在一起，形成新的特征 特征选择特征选择选择现有特征集的一个子集特征选择 特征选择方法包含两个主要组成部分 搜索过程搜索过程 选择准则选择准则 搜索过程搜索过程 在所有候选特征子集中进行系统搜索的过程 原则上，穷尽搜索（exhaustive search）即能够找到最优子集。实践中，往往采用更高效的非
17、穷尽搜索算法，找到次优解 选择准则选择准则 用于判断某个特征子集是否优于另一个特征子集的标准 原则上，选择准则即为系统性能的评价准则，如分类错误率等。实践中，往往采用简化的选择准则。搜索过程 循序向前选择法循序向前选择法（Sequential Forward Selection，SFS） 首先，最好的单个特征被选出 然后，用所有其他特征与第一个选出的特征组合成候选特征对，找出最好的一对 再用剩下的特征分别与上一步选出的最好特征对组成候选特征三元组，找出最好的三元组 该过程知道选出足够多的特征停止搜索过程 循序向前选择法循序向前选择法（Sequential Forward Selection，S
18、FS）搜索过程 循序向前选择法循序向前选择法（Sequential Forward Selection，SFS） 缺点 单个特征区分力很差，但两个特征结合区分力强，在此情况下，SFS失效最优子集中的每个特征分别单独最优子集中的每个特征分别单独考虑时，并不一定都为最优考虑时，并不一定都为最优搜索过程 循序向前选择法循序向前选择法：实例：实例卫星图像分析卫星图像分析搜索过程 循序向后选择法循序向后选择法（Sequential Backward Selection，SBS） 首先，选择所有d个特征 然后，从所有特征中任意去掉一个形成d个候选的d-1特征集，从中选出最好的一个 再从上一步得到的d-1特
19、征集中任意去掉一个特征形成d-1个d-2特征集，从中选出最好的一个 该过程直到特征集中的特征个数到达预先设定的值时停止搜索过程 循序向后选择法循序向后选择法（Sequential Backward Selection，SBS）因为因为SBS考虑的特征数目大于等于期望的特征数目，所以考虑的特征数目大于等于期望的特征数目，所以SBS通常通常比比SFS需要更多的选择准则计算需要更多的选择准则计算搜索过程 循序向后选择法循序向后选择法：实例：实例卫星图像分析卫星图像分析搜索过程 其他搜索过程 单个最佳特征子集单个最佳特征子集 直接搜索最佳的单个特征（每次仅用一个特征，计算选择准则），用它们构成的集合作
20、为特征选择结果 虽然简单，但是往往不可靠 只有当各特征之间完全独立的情况下能找到最优特征子集 选择准则 理想方法 用选定的特征子集表示训练样本，训练分类器，然后测试该分类器的泛化误差泛化误差（如采用交叉验证等方法） 因为对每个特征子集都需要训练一个分类器，因此计算量很大 简化方法 定义某种类内距离度量类内距离度量来描述采用某个特征子集时的类可分度可分度 不需要为每个特征子集训练一个分类器，因此计算量较小选择准则 类内距离类内距离 类内散布度类内散布度选择准则 类内距离类内距离 均方距离均方距离2,2(1)iia biia bDabn n1cWiiDD小结 误差与维度 误差随特征数增加而减小，而
21、当特征个数增加到某一个临界点后，继续增加反而会导致分类器的性能变差“维度灾难维度灾难” 解决“维度灾难维度灾难”的办法：降低维度的方法 特征组合特征组合把几个特征组合在一起，形成新的特征 特征选择特征选择选择现有特征集的一个子集小结 降维方法的选择依赖于应用领域以及训练数据的基本情况 特征组合特征组合降维有可能提供较好的分类能力分类能力，但是新的特征往往丧失具体的物理意义物理意义 特征选择特征选择能够在降低维度的同时保留特征的物理物理意义意义小结 特征组合降维方法 主成分分析（PCA） 寻找用来有效表示有效表示数据的投影 无监督 线性判别分析（LDA） 寻找用来有效分类有效分类的投影 有监督小结 特征选择降维方法 搜索过程搜索过程 循序向前选择法循序向前选择法SFS 循序向后选择法循序向后选择法SBS 选择准则选择准则 泛化误差泛化误差 类内距离度量类内距离度量
