线性判别分析LDA与主成分分析PCAppt课件.pptx
线性判别分析（LDA）与主成分分析（PCA）,重庆大学余俊良,第一部分线性判别分析（LDA）,介绍,线性判别分析(LinearDiscriminantAnalysis,LDA)，也叫做Fisher线性判别(FisherLinearDiscriminant,FLD)，是模式识别的经典算法，1936年由Ronald Fisher首次提出，并在1996年由Belhumeur引入模式识别和人工智能领域。,例子,举一个例子，假设我们对一张100*100像素的图片做人脸识别，每个像素是一个特征，那么会有10000个特征，而对应的类别标签y仅仅是0，1值，1代表是人脸。这么多特征不仅训练复杂，而且不必要特征对结果会带来不可预知的影响，但我们想得到降维后的一些最佳特征（与y关系最密切的），怎么办呢？,基本思想,线性判别分析的基本思想是将高维的模式样本投影到最佳鉴别矢量空间，以达到抽取分类信息和压缩特征空间维数的效果。投影后保证模式样本在新的子空间有最大的类间距离和最小的类内距离，即模式在该空间中有最佳的可分离性。因此，它是一种有效的特征抽取方法。使用这种方法能够使投影后模式样本的类间散布矩阵最大，并且同时类内散布矩阵最小。,下面给出一个例子，说明LDA的目标：,可以看到两个类别，一个绿色类别，一个红色类别。左图是两个类别的原始数据，现在要求将数据从二维降维到一维。直接投影到x1轴或者x2轴，不同类别之间 会有重复，导致分类效果下降。右图映射到的直线就是用LDA方法计算得到的，可以看到，红色类别和绿色类别在映射之后之间的距离是最大的，而且每个类别内 部点的离散程度是最小的（或者说聚集程度是最大的）。,LDA,要说明白LDA，首先得弄明白线性分类器(Linear Classifier)：因为LDA是一种线性分类器。对于K-分类的一个分类问题，会有K个线性函数：,当满足条件：对于所有的j，都有Yk Yj,的时候，我们就说x属于类别k。对于每一个分类，都有一个公式去算一个分值，在所有的公式得到的分值中，找一个最大的，就是所属的分类。,权向量（weight vector）法向量（normal vector）,阈值（threshold）偏置（bias）,LDA,上式实际上就是一种投影，是将一个高维的点投影到一条高维的直线上，LDA的目标是，给出一个标注了类别的数据集，投影到了一条直线之后，能够使得点尽量的按类别区分开，当k=2即二分类问题的时候，如下图所示：,红色的方形的点为0类的原始点、蓝色的方形点为1类的原始点，经过原点的那条线就是投影的直线，从图上可以清楚的看到，红色的点和蓝色的点被原点明显的分开了。下面我来推导一下二分类LDA问题的公式：,LDA,假设用来区分二分类的直线（投影函数)为：LDA分类的一个目标是使得不同类别之间的距离越远越好，同一类别之中的距离越近越好，所以我们需要定义几个关键的值:,类别i的原始中心点(均值)为：（Di表示属于类别i的点):类别i投影后的中心点为：衡量类别i投影后，类别点之间的分散程度（方差）为：最终我们可以得到一个下面的公式，表示LDA投影到w后的目标优化函数：,LDA,我们分类的目标是，使得类别内的点距离越近越好（集中），类别间的点越远越好。,分母表示每一个类别内的方差之和，方差越大表示一个类别内的点越分散，分子为两个类别各自的中心点的距离的平方，我们最大化J(w)就可以求出最优的w,LDA,我们定义一个投影前的各类别分散程度的矩阵，其意思是，如果某一个分类的输入点集Di里面的点距离这个分类的中心点mi越近，则Si里面元素的值就越小，如果分类的点都紧紧地围绕着mi，则Si里面的元素值越更接近0.带入Si，将J(w)分母化为：,LDA,同样的将J(w)分子化为：这样目标优化函数可以化成下面的形式：,LDA,这样就可以用拉格朗日乘子法了，但是还有一个问题，如果分子、分母是都可以取任意值的，那就会使得有无穷解，我们将分母限制为长度为1，并作为拉格朗日乘子法的限制条件，带入得到：这样的式子就是一个求广义特征值的问题了。如果Sw可逆，那么将求导后的结果两边都乘以 1 得 这个可喜的结果就是w就是矩阵的特征向量了。 这个公式称为Fisher linear discrimination。,LDA,让我们再观察一下，发现前面SB的公式SB=(m1-m2) (m1-m2)T 那么SBW=(m1-m2) (m1-m2)TW = (m1-m2)代入最后的特征值公式得： 1 SBW=(m1-m2) (m1-m2)TW = 1 (m1-m2) = w由于对w扩大缩小任何倍不影响结果，因此可以约去两边的未知常数和，得到:W = 1 (m1m2),LDA,至此，我们只需要求出原始样本的均值和方差就可以求出最佳的方向w，这就是Fisher于1936年提出的线性判别分析。 看上面二维样本的投影结果图：,LDA,对于N(N2)分类的问题，就可以直接写出以下的结论：这同样是一个求广义特征值的问题，求出的第i大的特征向量，即为对应的Wi。（此处推导过程见附录PDF）,第二部分主成分分析（PCA）,介绍,在实际问题中，我们经常会遇到研究多个变量的问题，而且在多数情况下，多个变量之 间常常存在一定的相关性。由于变量个数较多再加上变量之间的相关性，势必增加了分析问 题的复杂性。如何从多个变量中综合为少数几个代表性变量，既能够代表原始变量的绝大多 数信息，又互不相关，并且在新的综合变量基础上，可以进一步的统计分析，这时就需要进行主成分分析。,基本思想,主成分分析所要做的就是设法将原来众多具有一定相关性的变量，重新组合为一组新的相互无关的综合变量来代替原来变量。通常，数学上的处理方法就是将原来的变量做线性组合，作为新的综合变量，但是这种组合如果不加以限制，则可以有很多，应该如何选择呢？,基本思想,如果将选取的第一个线性组合即第一个综合变量记为F1 ，自然希望它尽可能多地反映原来变量的信息，这里“信息”用方差来测量，即希望Var(F1)越大，表示F1包含的信息越多。因此在所有的线性组合中所选取的F1应该是方差最大的，故称F1为第一主成分。如果第一主成分不足以代表原来p 个变量的信息，再考虑选取F2即第二个线性组合，为了有效地反映原来信息,F1已有的信息就不需要再出现在F2中， 用数学语言表达就是要求Cov(F1 ,F2)=0，称F2为第二主成分，依此类推可以构造出第三、四第p 个主成分。,最大方差理论,在信号处理中认为信号具有较大的方差，噪声有较小的方差，信噪比就是信号与噪声的方差比，越大越好。因此我们认为，最好的k维特征是将n维样本点转换为k维后，每一维上的样本方差都很大。,最大方差理论,比如左图有5个样本点，右图将样本投影到某一维上，这里用一条过原点的直线表示假设我们选择两条不同的直线做投影，那么左右两条中哪个好呢？根据我们之前的方差最大化理论，左边的好，因为投影后的样本点之间方差最大。,最大方差理论,我们要求的是最佳的直线，使得投影后样本点方差最大。设投影后样本点为 , 因此方差为: （1）其中S= 1 i=1 ( ) S就是样本特征的协方差矩阵。令u为单位向量，即uTu=1,用拉格朗日乘子法得： f(u) = uTSu+ (1-uTu)将上式求导，使之为0，得到： Su = u,最大方差理论,Su = u,这是一个标准的特征值表达式了，对应的特征值，u对应的特征向量。由此var = uTSu = var取得最大值的条件就是最大，也就是取得最大的特征值的时候。假设我们是要将一个D维的数据空间投影到M维的数据空间中（M D)， 那我们取前M个特征向量构成的投影矩阵就是能够使得方差最大的矩阵了。同时，由于u是实对称矩阵的特征向量，因此特征向量之间正交，投影得到的综合变量彼此独立，协方差为0。,最大方差理论,因此，我们只需要对协方差矩阵进行特征值分解，得到的前k大特征值对应的特征向量就是最佳的k维新特征，而且这k维新特征是正交的。得到前k个u以后，样例xi通过以下变换可以得到新的样本。其中的第j维就是xi在uj上的投影。通过选取最大的k个u，使得方差较小的特征（如噪声）被丢弃。,PCA小结,PCA技术的一大好处是对数据进行降维的处理。我们可以对新求出的“主元”向量的重要性进行排序，根据需要取前面最重要的部分，将后面的维数省去，可以达到降维从而简化模型或是对数据进行压缩的效果。同时最大程度的保持了原有数据的信息。PCA技术的一个很大的优点是，它是完全无参数限制的。在PCA的计算过程中完全不需要人为的设定参数或是根据任何经验模型对计算进行干预，最后的结果只与数据相关，与用户是独立的。但是，这一点同时也可以看作是缺点。如果用户对观测对象有一定的先验知识，掌握了数据的一些特征，却无法通过参数化等方法对处理过程进行干预，可能会得不到预期的效果，效率也不高。,总结,PCA与LDA对比,PCA与LDA的降维对比：PCA选择样本点投影具有最大方差的方向，LDA选择分类性能最好的方向。,PCA与LDA对比,LDA的全称是Linear Discriminant Analysis（线性判别分析），是一种supervised learning。主成分分析（PCA）与LDA有着非常近似的意思，LDA的输入数据是带标签的，而PCA的输入数据是不带标签的，所以PCA是一种unsupervised learning。LDA通常来说是作为一个独立的算法存在，给定了训练数据后，将会得到一系列的判别函数（discriminate function），之后对于新的输入，就可以进行预测了。而PCA更像是一个预处理的方法，它可以将原本的数据降低维度，而使得降低了维度的数据之间的方差最大。,LDA的一些限制,1、 LDA至多可生成C-1维子空间 LDA降维后的维度区间在1,C-1，与原始特征数n无关，对于二值分类，最多投影到1维。 2、 LDA不适合对非高斯分布样本进行降维。上图中红色区域表示一类样本，蓝色区域表示另一类，由于是2类，所以最多投影到1维上。不管在直线上怎么投影，都难使红色点和蓝色点内部凝聚，类间分离。,
