《线性判别分析》PPT课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,线性判别分析（,LDA,）,基本思想,线性判别分析的基本思想是将高维的模式样本投影到最佳鉴别矢量空间，即把高维空间中的数据点投影到一条直线上去，将多维降为一维。并且要求投影后各样本的类间散布距离最大，同时类内散布距离最小。,LDA,二分类问题公式推导,假设,A,和,B,为分类明确的两类症状。在总体,A,中观察了,P,例，在总体,B,中观察了,q,例，每一例记录了,n,个指标，分别记为,x,1,x,2,x,n,。令,y,是,n,个指标的一个线性函数，即,y=w,1,x,1,+w,2,x,2,+w,n,x,n,y=wTx,其中,w,1,，,w,2,，,，,w,n,是待估计的未知系数。我们称上述线性函数是线性判别法的,判别函数,。,假设用来区分二分类的直线（投影函数,),为：,类别,i,的样本均值,:,类别,i,投影后的均值为：,投影后，类别内点之间的分散程度（方差）为：,最终我们可以得到一个下面的公式，称为,准侧函数,。,为了找到最有利于分类的的方向,W,，还需要建立一个,准侧函数,：,LDA,我们,分类的目标,是找到一个最优化的,W,，使得类别内的点距离越近越好（集中），类别间的点越远越好。,分母表示每一个类别内的方差之和，方差越大表示一个类别内的点越分散，分子为两个类别各自的中心点的距离的平方，我们最大化,J(w),就可以求出最优的,w,定义：,（,1,）样本类内离散度矩阵,S,i,和总类内离散度矩阵,（,2,）样本类间离散度矩阵,S,B,LDA,LDA,然后将,J(w),分子和分母分别化为：,这样目标优化函数可以化成下面的形式：,瑞利商,根据广义,Rayleigh,商的性质,:,J,（,w,）的极值与,w,的大小无关，只与,w,的方向有关。,Fisher,算法步骤总结：,由,Fisher,线性判别式,求解向量,的步骤：,把来自两类,的训练样本集,分成,和,两个子集,和,。,由,，,i=1,2,，计算,m,i,。,由,计算投影后各类的类内离散度矩阵,计算类内总离散度矩阵,计算,Sw,的逆矩阵,。,由,求解,w*,。,月份,/,年龄,男孩体重,(,kg),男孩身高,(,cm),女孩体重,(,kg),女孩身高,(,cm),出生时,3.40,50.8,3.30,50.1,12,个月,4.56,55.2,4.36,54.2,23,个月,5.82,59.0,5.49,58.0,34,个月,6.81,62.5,6.32,61.1,45,个月,7.56,65.2,7.09,63.8,56,个月,7.93,66.8,7.51,65.7,67,个月,8.52,69.0,7.95,67.5,78,个月,8.74,70.4,8.25,69.1,89,个月,9.03,71.9,8.48,70.5,910,个月,9.42,73.5,8.85,72.2,幼儿不同年龄段的身高体重指标：,经典,Fisher,线性判别分析方法,LDA,LDA,LDA,Sw,奇异问题的解决方法：,R-LDA,PCA+LDA,N-LDA,D-LDA,R-LDA,由于,Sw,总是半正定的，为了使之正定，可以将另外一个正定的对角矩阵与之相加，以两者之和代替,Sw,，即是：,上式中,a,为任意正实数，,I,为单位矩阵，显然对于任意的正实数,a,，,Sw,总是非奇异的，用,Sw,代替,Fisher,准则函数中的,Sw,。用上述方法就可以求解最优投影方向矩阵。在,R-LDA,中，对角矩阵的系数,a,的选择没有理论依据，可以选择多个不同的数值进行分类实验，通过实验结果来选择一个最优的值。,用,Sw,代替,Sw,的确可以消除,Sw,的奇异性，但代替之后，通过最大化,Fisher,准则函数选取的最优投影方向矩阵就变成原始最优投影方向矩阵的一个近似矩阵，且选择不同的系数,a,会导致得到不同的最优投影方向矩阵。,Sw,=Sw+a I,为了保证,Sw,是非奇异矩阵,需要,t+c,个训练样本,当特征维数,t,特别大时,在实际应用中往往难以满足要求。为了解决训练样本不够的情况,提出了中间过渡子空间,即先将,t,维的高维空间经过,PCA,降到,f,维的过渡子空间,再在此空间进行,LDA,变换,得到最终的,g,维子空间。更确切地说,可以表示为：,PCA+LDA,N-LDA,S,w,的奇异性意味着,Fisher,准则函数的分母为零，而在,Fisher,准则函数中，若有一投影方向可以使得,Fisher,准则函数分母为零，这样意味着此投影方向可以使得低维空间中的同类数据达到最小的分离。当品为奇异时，意味着有多个投影方向可以使得,Fisher,准则函数分母为零，即意味着有多个投影方向可以使得低维空间中的同类数据达到最小的分离。从这些不同的投影方向中，若能选出一个投影方向，使原始数据集进此投影后能在低维空间中达到不同类数据的最大分离度，就从某种程度上实现了最大化,Fisher,准则函数所需要表达的含义。以上是,N-LDA,解决小样本问题的,基本思想,N-LDA,计算最优投影方向矩阵的方法如下：,N-LDA,对,Sw,进行奇异值分解：,从,Uw,中找出,Sw,的零空间,null(Sw),：,上式中,U,w,1,为,Uw,的前,r,1,列，,U,w,2,为,U,w,的后,m-r,1,列，,r,1,=rank(S,w,),将原始数据集投影到此零空间中，计算零空间内数据集的类间散布矩阵,S,B,：,N-LDA,对,S,B,进行特征值分解：,计算最优投影方向矩阵：,上式中,U,B,=(U,B1,，,U,B2,),，,U,B1,为,U,B,的前,r,2,列，,UB2,为,U,B,的后,r,2,列，,r,2,=rank(S,B,),。,N-LDA,从,Sw,的零空间,null(Sw),中寻求最优投影方向，在某些情况下，,N-LDA,求得的这个投影方向可以保证数据集在投影后的低维空间中类内散布值最小，但却不能保证类间散布值和类内散布值之比达到最大，或者说,N-LDA,求得的这个最优投影方向并不是实际最优的。这种现象产生的根本原因是,N-LDA,只从而的零空间,null(Sw),中寻求最优投影方向，抛弃了品的非零空间,range(Sw),，而事实是在一些情况下最优投影方向却恰恰存在于此品的非零空间,range(Sw),。,N-LDA,D-LDA,D-LDA,的基本思想从某种意义上来说和上述,N-LDA,思想相同，,D-LDA,将,S,B,的零空间,null(S,B,),剔除，从剩余的非零空间,range(S,B,),内寻找使得此空间内数据集类内散布矩阵,Sw,达到最小值得投影方向，选择此投影方向为,D-LDA,所要寻求的最优投影方向。,D-LDA,算最优投影方向矩阵的方法如下：,D-LDA,对,S,B,进行特征值分解：,上式中,U,B,是正交矩阵，,B,是一个对角矩阵。,计算原始数据集在,S,B,的非零空间,range(S,B,),中的类内散布矩阵,Sw,：,上式中,U,B1,为,UB,的前,s,l,列，,U,B2,为,U,B,的后,m-s,l,列，,s,l,=rank(S,B,),。,对,Sw,进行奇异值分解：,D-LDA,上式中,Uw,为正交矩阵，,w,为对角矩阵。,算最优投影方向矩阵：,D-LDA,抛弃,SB,的零空间,null(SB),，而从其非零空间,range(SB),中寻求最优投影方向。与,N-LDA,面临的问题相同，在某些情况下，,D-LDA,求得的这个投影方向只能保证数据集在投影后的低维空间中类间散布值不是最小的情况下类内散布值最小，而不能保证两者比值达到最大值，因为在一些特殊情况下，最优投影方向也可能正位于,SB,的零空间,null(SB),中。同时，,D-LDA,需要频繁的在,SB,的非零空间,range(SB),内进行各项矩阵运算，这导致其计算量过大，因而不适合实际应用。,D-LDA,谢 谢！,