《线性判别分析课件》由会员分享，可在线阅读，更多相关《线性判别分析课件（60页珍藏版）》请在金锄头文库上搜索。
1、误差与维数例子贝叶斯误差概率r增加，误差概率 减小 ， 假设各特征独立： 到 的马氏距离引入新的特征可使r增大，进而降低误差概率维度灾难在实际应用中当特征个数增加到某一个临界点后，继续增加反而会导当特征个数增加到某一个临界点后，继续增加反而会导致分类器的性能变差致分类器的性能变差“维度灾难维度灾难”（curse of dimensionality）原因？假设的概率模型与真实模型不匹配训练样本个数有限，导致概率分布的估计不准对于高维数据，“维度灾难”使解决模式识别问题非常困难，此时，往往要求首先降低特征向量的维度降维降低特征向量维度的可行性可行性特征向量往往是包含冗余信息冗余信息的！有些特征可能
2、与分类问题无关无关特征之间存在着很强的相关性相关性降低维度的方法特征组合特征组合把几个特征组合在一起，形成新的特征特征选择特征选择选择现有特征集的一个子集降维降维问题线性变换线性变换 vs. 非线性变换非线性变换利用类别标记（有监督有监督） vs. 不用类别标记（无监督无监督）不同的训练目标最小化重构误差（主成分分析主成分分析，PCA）最大化类别可分性（线性判别分析线性判别分析，LDA）最小化分类误差（判别训练判别训练，discriminative training）保留最多细节的投影（投影寻踪投影寻踪，projection pursuit）最大限度的使各特征之间独立（独立成分分析独立成分分析
3、，ICA）主成分分析（PCA）用一维向量表示d维样本用通过样本均值m的直线（单位向量为e）上的点表示样本最小化平方重构误差 唯一决定了(xk-m)在在e上的投影上的投影主成分分析（PCA）用一维向量表示d维样本eakxkm主成分分析（PCA）寻找e的最优方向散布矩阵散布矩阵（scatter matrix）主成分分析（PCA）使 最小的e最大化拉格朗日乘子法（约束条件 ）结论：结论：e为散布矩阵最大的本征值对应的本征向量为散布矩阵最大的本征值对应的本征向量 是S的本征值（eigenvalue）e是S的本征向量（eigenvector）最大本征值 对应 的最大值主成分分析（PCA）将一维的 扩展到
4、 维空间用 来表示最小化平方误差主成分分析（PCA）将一维的 扩展到 维空间结论：结论：使得平方误差最小的向量 分别为散布矩阵S的 个最大本征值对应的本征向量S为实对称矩阵，所以 相互正交 可被视为特征空间的一个子空间的单位向量基 为 对应于基 的系数，或在 上的投影 称为主成分主成分（principal component）几何意义 为沿数据云团方差最大的方向方差最大的方向的直线利用PCA，可以将d维数据降维降维到 维，同时使得降维后的数据与源数据的平方误差最小主成分分析（PCA）主成分分析步骤（d维降为 维）1.计算散布矩阵S2.计算S的本征值和本证向量3.将本征向量按相应的本征值从大到小
5、排序4.选择最大的d个本征向量作为投影向量 ，构成投影 矩阵W，其中第i列为5.对任意d维样本x，其用PCA降维后的d维向量为主成分分析（PCA）通常，最大的几个本征值占据了所有本征值之和最大的几个本征值占据了所有本征值之和的绝大部分的绝大部分少数几个最大本征少数几个最大本征值对应的本征向量值对应的本征向量即可表示原数据中即可表示原数据中的绝大部分信息，的绝大部分信息，而剩下的小部分（而剩下的小部分（即对应较小的本征即对应较小的本征值的本征向量所表值的本征向量所表示的信息），通常示的信息），通常可以认为是数据噪可以认为是数据噪声而丢掉声而丢掉主成分分析（PCA）主成分分析（PCA）数据集：Ir
6、is原维度：4主成分分析（PCA）用用PCA降到降到2维维用用PCA降到降到3维维奇异值分解（SVD）PCA中对散布矩阵S的本征值分解计算量较大，如特征向量维度较高，直接对S进行本征值分解十分困难。例如对图像的PCA分析：图像：散布矩阵： 的矩阵本征值分解？空间复杂度和时间复杂度均无法接受！空间复杂度和时间复杂度均无法接受！奇异值分解（SVD）解决方案：不直接对S进行本征值分解，而利用SVD对一个较小的矩阵进行本征值分解SVD定理定理设A是一个秩为n的 矩阵，则存在两个正交矩阵以及对角阵满足其中： 为矩阵 和 的非零本征值， 和 分别为 和 对应于 的本征向量。该分解称为矩阵A的奇异值分解奇异
7、值分解（Singular Value Decomposition，SVD）， 为A的奇异值。奇异值分解（SVD）推论利用利用利用利用SVDSVD简化简化简化简化S S的本征值分解的本征值分解的本征值分解的本征值分解散布矩阵其中，令若 ，则对R进行本征值分解要比直接对S进行本征值分解快。例如，对绝大多数图像训练集来讲，图像的像素例如，对绝大多数图像训练集来讲，图像的像素数要远远大于训练集中的样本个数，即数要远远大于训练集中的样本个数，即奇异值分解（SVD）对R进行本征值分解本征值：本征向量：根据 ，得出 的本征向量为 矩阵的矩阵的本征值分解本征值分解 矩阵的矩阵的本征值分解本征值分解Fisher
8、线性判别分析PCA方法寻找用来有效表示有效表示数据（从最小平方误差的意义上讲）的主轴方向线性判别分析（linear discriminant analysis, LDA）寻找的是用来有效分类有效分类的方向Fisher线性判别分析假设n个d维样本 ，他们分属两个类别 和其中，n1个属于类别 的样本组成样本子集 ， n2个属于类别 的样本组成样本子集 单位向量w方向上的投影投影点 根据源数据的类别也分成两个子集 和目标：投影到w上后，投影点更易分类不同类的投影点尽量分开不同类的投影点尽量分开同一类的投影点尽量靠近同一类的投影点尽量靠近Fisher线性判别分析不同类的投影点尽量分开不同类的投影点尽量
9、分开设 为第i类的样本均值投影后的样本均值投影后的两类样本均值之间的距离此距离越大，说明两类投影点分得越开此距离越大，说明两类投影点分得越开Fisher线性判别分析同一类的投影点尽量靠近同一类的投影点尽量靠近投影类内散布各类的投影类内散布之和此总类内散布体现了投影后类内的此总类内散布体现了投影后类内的“紧致紧致”程度，程度，其越小，说明同一类内的投影点越靠近其越小，说明同一类内的投影点越靠近Fisher线性判别分析Fisher准则函数总类内散布总类内散布两类样本均值之间的距离两类样本均值之间的距离最大化最大化J(w)即使得即使得类间差距类间差距（分子）最大化同时（分子）最大化同时类内类内差距差
10、距（分母）最小化（分母）最小化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类多重判
11、别分析类间散布矩阵投影原样本点原样本点投影点投影点变换矩阵变换矩阵Fisher线性判别分析2类推广到c类多重判别分析在由W张成的投影子空间中Fisher线性判别分析2类推广到c类多重判别分析将 代入，得到求能够最有效分类的W：使得类间离散度离散度和类内离散度离散度的比值最大离散度度量：散布矩阵的行列式Fisher线性判别分析2类推广到c类多重判别分析准则函数使J(W)最大化的W的列向量由如下广义本征值问题中最大本征值对应的本征向量组成SB为为c个秩为个秩为1或或0的矩阵之和，其中只有的矩阵之和，其中只有c-1个矩阵相互独立，所个矩阵相互独立，所以以SB的秩不大于的秩不大于c-1所以如上广义本征
12、值问题最多有所以如上广义本征值问题最多有c-1个非零本征值，对应个非零本征值，对应c-1个本个本征向量，所以征向量，所以W最多有最多有c-1列列Fisher线性判别分析Fisher线性判别分析投影到主成分方向投影到主成分方向投影到投影到LDA方向方向降维实例：卫星图像分析原卫星图像以及前原卫星图像以及前6个个PCA主成分投影方向主成分投影方向降维实例：卫星图像分析原卫星图像以及前原卫星图像以及前6个个LDA投影方向投影方向降维实例：卫星图像分析原卫星图像以及前原卫星图像以及前6个个PCA主成分投影方向主成分投影方向降维实例：卫星图像分析原卫星图像以及前原卫星图像以及前6个个LDA投影方向投影方
13、向降维实例：人脸识别典型人脸图像集合典型人脸图像集合降维实例：人脸识别人脸图像的前人脸图像的前15个个PCA主成分投影方向，又称主成分投影方向，又称为为“本征脸本征脸”（eigenface）Ch 06.特征降维和选择Part 2 特征选择降维降低维度的方法特征组合特征组合把几个特征组合在一起，形成新的特征特征选择特征选择选择现有特征集的一个子集特征选择特征选择方法包含两个主要组成部分搜索过程搜索过程选择准则选择准则搜索过程搜索过程在所有候选特征子集中进行系统搜索的过程原则上，穷尽搜索（exhaustive search）即能够找到最优子集。实践中，往往采用更高效的非穷尽搜索算法，找到次优解选择
14、准则选择准则用于判断某个特征子集是否优于另一个特征子集的标准原则上，选择准则即为系统性能的评价准则，如分类错误率等。实践中，往往采用简化的选择准则。搜索过程循序向前选择法循序向前选择法（Sequential Forward Selection，SFS）首先，最好的单个特征被选出然后，用所有其他特征与第一个选出的特征组合成候选特征对，找出最好的一对再用剩下的特征分别与上一步选出的最好特征对组成候选特征三元组，找出最好的三元组该过程知道选出足够多的特征停止搜索过程循序向前选择法循序向前选择法（Sequential Forward Selection，SFS）搜索过程循序向前选择法循序向前选择法（S
15、equential Forward Selection，SFS）缺点单个特征区分力很差，但两个特征结合区分力强，在此情况下，SFS失效最优子集中的每个特征分别单独最优子集中的每个特征分别单独考虑时，并不一定都为最优考虑时，并不一定都为最优搜索过程循序向前选择法循序向前选择法：实例：实例卫星图像分析卫星图像分析搜索过程循序向后选择法循序向后选择法（Sequential Backward Selection，SBS）首先，选择所有d个特征然后，从所有特征中任意去掉一个形成d个候选的d-1特征集，从中选出最好的一个再从上一步得到的d-1特征集中任意去掉一个特征形成d-1个d-2特征集，从中选出最好的
16、一个该过程直到特征集中的特征个数到达预先设定的值时停止搜索过程循序向后选择法循序向后选择法（Sequential Backward Selection，SBS）因为因为SBS考虑的特征数目大于等于期望的特征数目，所以考虑的特征数目大于等于期望的特征数目，所以SBS通常通常比比SFS需要更多的选择准则计算需要更多的选择准则计算搜索过程循序向后选择法循序向后选择法：实例：实例卫星图像分析卫星图像分析搜索过程其他搜索过程单个最佳特征子集单个最佳特征子集直接搜索最佳的单个特征（每次仅用一个特征，计算选择准则），用它们构成的集合作为特征选择结果虽然简单，但是往往不可靠只有当各特征之间完全独立的情况下能找
17、到最优特征子集选择准则理想方法用选定的特征子集表示训练样本，训练分类器，然后测试该分类器的泛化误差泛化误差（如采用交叉验证等方法）因为对每个特征子集都需要训练一个分类器，因此计算量很大简化方法定义某种类内距离度量类内距离度量来描述采用某个特征子集时的类可分度可分度不需要为每个特征子集训练一个分类器，因此计算量较小选择准则类内距离类内距离类内散布度类内散布度选择准则类内距离类内距离均方距离均方距离小结误差与维度误差随特征数增加而减小，而当特征个数增加到某一个临界点后，继续增加反而会导致分类器的性能变差“维度灾难维度灾难”解决“维度灾难维度灾难”的办法：降低维度的方法特征组合特征组合把几个特征组合在一起，形成新的特征特征选择特征选择选择现有特征集的一个子集小结降维方法的选择依赖于应用领域以及训练数据的基本情况特征组合特征组合降维有可能提供较好的分类能力分类能力，但是新的特征往往丧失具体的物理意义物理意义特征选择特征选择能够在降低维度的同时保留特征的物理物理意义意义小结特征组合降维方法主成分分析（PCA）寻找用来有效表示有效表示数据的投影无监督线性判别分析（LDA）寻找用来有效分类有效分类的投影有监督小结特征选择降维方法搜索过程搜索过程循序向前选择法循序向前选择法SFS循序向后选择法循序向后选择法SBS选择准则选择准则泛化误差泛化误差类内距离度量类内距离度量
