线性判别分析课件

1、误差与维数例子贝叶斯误差概率r增加，误差概率 减小 ， 假设各特征独立： 到 的马氏距离引入新的特征可使r增大，进而降低误差概率维度灾难在实际应用中当特征个数增加到某一个临界点后，继续增加反而会导致分类器的性能变差“维度灾难”（curse of dimensionality）原因？假设的概率模型与真实模型不匹配训练样本个数有限，导致概率分布的估计不准对于高维数据，“维度灾难”使解决模式识别问题非常困难，此时，往往要求首先降低特征向量的维度降维降低特征向量维度的可行性特征向量往往是包含冗余信息的！有些特征可能与分类问题无关特征之间存在着很强的相关性降低维度的方法特征组合把几个特征组合在一起，形成

2、新的特征特征选择选择现有特征集的一个子集降维降维问题线性变换 vs. 非线性变换利用类别标记（有监督） vs. 不用类别标记（无监督）不同的训练目标最小化重构误差（主成分分析，PCA）最大化类别可分性（线性判别分析，LDA）最小化分类误差（判别训练，discriminative training）保留最多细节的投影（投影寻踪，projection pursuit）最大限度的使各特征之间独立（独立成分分析，ICA）主成分分析（PCA）用一维向量表示d维样本用通过样本均值m的直线（单位向量为e）上的点表示样本最小化平方重构误差 唯一决定了(xk-m)在e上的投影主成分分析（PCA）用一维向量表示d

3、维样本eakxkm主成分分析（PCA）寻找e的最优方向散布矩阵（scatter matrix）主成分分析（PCA）使 最小的e最大化拉格朗日乘子法（约束条件 ）结论：e为散布矩阵最大的本征值对应的本征向量 是S的本征值（eigenvalue）e是S的本征向量（eigenvector）最大本征值 对应 的最大值主成分分析（PCA）将一维的 扩展到 维空间用 来表示最小化平方误差主成分分析（PCA）将一维的 扩展到 维空间结论：使得平方误差最小的向量 分别为散布矩阵S的 个最大本征值对应的本征向量S为实对称矩阵，所以 相互正交 可被视为特征空间的一个子空间的单位向量基 为 对应于基 的系数，或在

4、上的投影 称为主成分（principal component）几何意义 为沿数据云团方差最大的方向的直线利用PCA，可以将d维数据降维到 维，同时使得降维后的数据与源数据的平方误差最小主成分分析（PCA）主成分分析步骤（d维降为 维）计算散布矩阵S计算S的本征值和本证向量将本征向量按相应的本征值从大到小排序选择最大的d个本征向量作为投影向量 ，构成投影 矩阵W，其中第i列为对任意d维样本x，其用PCA降维后的d维向量为主成分分析（PCA）通常，最大的几个本征值占据了所有本征值之和的绝大部分少数几个最大本征值对应的本征向量即可表示原数据中的绝大部分信息，而剩下的小部分（即对应较小的本征值的本征向

5、量所表示的信息），通常可以认为是数据噪声而丢掉主成分分析（PCA）主成分分析（PCA）数据集：Iris原维度：4主成分分析（PCA）用PCA降到2维用PCA降到3维奇异值分解（SVD）PCA中对散布矩阵S的本征值分解计算量较大，如特征向量维度较高，直接对S进行本征值分解十分困难。例如对图像的PCA分析：图像：散布矩阵： 的矩阵本征值分解？空间复杂度和时间复杂度均无法接受！奇异值分解（SVD）解决方案：不直接对S进行本征值分解，而利用SVD对一个较小的矩阵进行本征值分解SVD定理设A是一个秩为n的 矩阵，则存在两个正交矩阵以及对角阵满足其中： 为矩阵 和 的非零本征值， 和 分别为 和 对应于

6、的本征向量。该分解称为矩阵A的奇异值分解（Singular Value Decomposition，SVD）， 为A的奇异值。奇异值分解（SVD）推论利用SVD简化S的本征值分解散布矩阵其中，令若 ，则对R进行本征值分解要比直接对S进行本征值分解快。例如，对绝大多数图像训练集来讲，图像的像素数要远远大于训练集中的样本个数，即奇异值分解（SVD）对R进行本征值分解本征值：本征向量：根据 ，得出 的本征向量为 矩阵的本征值分解 矩阵的本征值分解Fisher线性判别分析PCA方法寻找用来有效表示数据（从最小平方误差的意义上讲）的主轴方向线性判别分析（linear discriminant analy

7、sis, LDA）寻找的是用来有效分类的方向Fisher线性判别分析假设n个d维样本 ，他们分属两个类别 和其中，n1个属于类别 的样本组成样本子集 ， n2个属于类别 的样本组成样本子集 单位向量w方向上的投影投影点 根据源数据的类别也分成两个子集 和目标：投影到w上后，投影点更易分类不同类的投影点尽量分开同一类的投影点尽量靠近Fisher线性判别分析不同类的投影点尽量分开设 为第i类的样本均值投影后的样本均值投影后的两类样本均值之间的距离此距离越大，说明两类投影点分得越开Fisher线性判别分析同一类的投影点尽量靠近投影类内散布各类的投影类内散布之和此总类内散布体现了投影后类内的“紧致”程

8、度，其越小，说明同一类内的投影点越靠近Fisher线性判别分析Fisher准则函数总类内散布两类样本均值之间的距离最大化J(w)即使得类间差距（分子）最大化同时类内差距（分母）最小化Fisher线性判别分析把J(w)表示为w的表达式原数据空间类内散布矩阵总类内散布矩阵推导Fisher线性判别分析把J(w)表示为w的表达式总类间散布矩阵推导Fisher线性判别分析Fisher准则函数Fisher准则函数最大化，w需满足广义本征值问题Sw非奇异普通本征值问题Fisher线性判别分析2类推广到c类多重判别分析总类内散布矩阵Fisher线性判别分析2类推广到c类多重判别分析总体均值向量总体散布矩阵Fi

9、sher线性判别分析2类推广到c类多重判别分析推导类间散布矩阵Fisher线性判别分析2类推广到c类多重判别分析类间散布矩阵投影原样本点投影点变换矩阵Fisher线性判别分析2类推广到c类多重判别分析在由W张成的投影子空间中Fisher线性判别分析2类推广到c类多重判别分析将 代入，得到求能够最有效分类的W：使得类间离散度和类内离散度的比值最大离散度度量：散布矩阵的行列式Fisher线性判别分析2类推广到c类多重判别分析准则函数使J(W)最大化的W的列向量由如下广义本征值问题中最大本征值对应的本征向量组成SB为c个秩为1或0的矩阵之和，其中只有c-1个矩阵相互独立，所以SB的秩不大于c-1所以

10、如上广义本征值问题最多有c-1个非零本征值，对应c-1个本征向量，所以W最多有c-1列Fisher线性判别分析Fisher线性判别分析投影到主成分方向投影到LDA方向降维实例：卫星图像分析原卫星图像以及前6个PCA主成分投影方向降维实例：卫星图像分析原卫星图像以及前6个LDA投影方向降维实例：卫星图像分析原卫星图像以及前6个PCA主成分投影方向降维实例：卫星图像分析原卫星图像以及前6个LDA投影方向降维实例：人脸识别典型人脸图像集合降维实例：人脸识别人脸图像的前15个PCA主成分投影方向，又称为“本征脸”（eigenface）Ch 06.特征降维和选择Part 2 特征选择降维降低维度的方法特

11、征组合把几个特征组合在一起，形成新的特征特征选择选择现有特征集的一个子集特征选择特征选择方法包含两个主要组成部分搜索过程选择准则搜索过程在所有候选特征子集中进行系统搜索的过程原则上，穷尽搜索（exhaustive search）即能够找到最优子集。实践中，往往采用更高效的非穷尽搜索算法，找到次优解选择准则用于判断某个特征子集是否优于另一个特征子集的标准原则上，选择准则即为系统性能的评价准则，如分类错误率等。实践中，往往采用简化的选择准则。搜索过程循序向前选择法（Sequential Forward Selection，SFS）首先，最好的单个特征被选出然后，用所有其他特征与第一个选出的特征组合

12、成候选特征对，找出最好的一对再用剩下的特征分别与上一步选出的最好特征对组成候选特征三元组，找出最好的三元组该过程知道选出足够多的特征停止搜索过程循序向前选择法（Sequential Forward Selection，SFS）搜索过程循序向前选择法（Sequential Forward Selection，SFS）缺点单个特征区分力很差，但两个特征结合区分力强，在此情况下，SFS失效最优子集中的每个特征分别单独考虑时，并不一定都为最优搜索过程循序向前选择法：实例卫星图像分析搜索过程循序向后选择法（Sequential Backward Selection，SBS）首先，选择所有d个特征然后，从

13、所有特征中任意去掉一个形成d个候选的d-1特征集，从中选出最好的一个再从上一步得到的d-1特征集中任意去掉一个特征形成d-1个d-2特征集，从中选出最好的一个该过程直到特征集中的特征个数到达预先设定的值时停止搜索过程循序向后选择法（Sequential Backward Selection，SBS）因为SBS考虑的特征数目大于等于期望的特征数目，所以SBS通常比SFS需要更多的选择准则计算搜索过程循序向后选择法：实例卫星图像分析搜索过程其他搜索过程单个最佳特征子集直接搜索最佳的单个特征（每次仅用一个特征，计算选择准则），用它们构成的集合作为特征选择结果虽然简单，但是往往不可靠只有当各特征之间完全独立的情况下能找到最优特征子集选择准则理想方法用选定的特征子集表示训练样本，训练分类器，然后测试该分类器的泛化误差（如采用交叉验证等方法）因为对每个特征子集都需要训练一个分类器，因此计算量很大简化方法定义某种类内距离度量来描述采用某个特征子集时的类可分度不需要为每个特征子集训练一个分类器，因此计算量较小选择准则类内距离类内散布度选择准则类内距离均方距离小结误差与维度误差随特征数增加而减小，而当特征个数增加到某一个临界点后，继续增加反而会导致分类器的性能变差“维度灾难”解决“维度灾难”的办法：降低维度的方法特征组合把几个特征组合在一