《线性判别分析》PPT课件.ppt
线性判别分析（LDA）,基本思想,线性判别分析的基本思想是将高维的模式样本投影到最佳鉴别矢量空间，即把高维空间中的数据点投影到一条直线上去，将多维降为一维。并且要求投影后各样本的类间散布距离最大，同时类内散布距离最小。,LDA 二分类问题公式推导,假设A和B为分类明确的两类症状。在总体A中观察了P例，在总体B中观察了q例，每一例记录了n个指标，分别记为x1,x2,xn。令y是n个指标的一个线性函数，即 y=w1x1+w2x2+wnxn y=wTx 其中w1，w2，wn 是待估计的未知系数。我们称上述线性函数是线性判别法的判别函数。,假设用来区分二分类的直线（投影函数)为：类别i的样本均值:类别i投影后的均值为：投影后，类别内点之间的分散程度（方差）为：最终我们可以得到一个下面的公式，称为准侧函数。,为了找到最有利于分类的的方向W，还需要建立一个准侧函数：,LDA,我们分类的目标是找到一个最优化的W，使得类别内的点距离越近越好（集中），类别间的点越远越好。,分母表示每一个类别内的方差之和，方差越大表示一个类别内的点越分散，分子为两个类别各自的中心点的距离的平方，我们最大化J(w)就可以求出最优的w,定义：（1）样本类内离散度矩阵Si和总类内离散度矩阵,（2）样本类间离散度矩阵 SB,LDA,LDA,然后将J(w)分子和分母分别化为：这样目标优化函数可以化成下面的形式：,瑞利商,根据广义Rayleigh商的性质:,J（w）的极值与w的大小无关，只与w的方向有关。,Fisher算法步骤总结：由Fisher线性判别式 求解向量 的步骤：把来自两类 的训练样本集 分成 和 两个子集 和。由，i=1,2，计算 mi。由 计算投影后各类的类内离散度矩阵 计算类内总离散度矩阵 计算 Sw 的逆矩阵。由 求解w*。,幼儿不同年龄段的身高体重指标：,经典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,Sw的奇异性意味着Fisher准则函数的分母为零，而在Fisher准则函数中，若有一投影方向可以使得Fisher准则函数分母为零，这样意味着此投影方向可以使得低维空间中的同类数据达到最小的分离。当品为奇异时，意味着有多个投影方向可以使得Fisher准则函数分母为零，即意味着有多个投影方向可以使得低维空间中的同类数据达到最小的分离。从这些不同的投影方向中，若能选出一个投影方向，使原始数据集进此投影后能在低维空间中达到不同类数据的最大分离度，就从某种程度上实现了最大化Fisher准则函数所需要表达的含义。以上是N-LDA解决小样本问题的基本思想,N-LDA计算最优投影方向矩阵的方法如下：,N-LDA,对Sw进行奇异值分解：,从Uw中找出Sw的零空间null(Sw)：,上式中Uw1为Uw的前r1列，Uw2为Uw的后m-r1列，r1=rank(Sw),将原始数据集投影到此零空间中，计算零空间内数据集的类间散布矩阵SB：,N-LDA,对SB进行特征值分解：,计算最优投影方向矩阵：,上式中UB=(UB1，UB2)，UB1为UB的前r2列，UB2为UB的后r2列，r2=rank(SB)。,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将SB的零空间null(SB)剔除，从剩余的非零空间range(SB)内寻找使得此空间内数据集类内散布矩阵Sw达到最小值得投影方向，选择此投影方向为D-LDA所要寻求的最优投影方向。,D-LDA算最优投影方向矩阵的方法如下：,D-LDA,对SB进行特征值分解：,上式中UB是正交矩阵，B是一个对角矩阵。,计算原始数据集在SB的非零空间range(SB)中的类内散布矩阵Sw：,上式中UB1 为UB的前sl列，UB2为UB的后m-sl 列，sl=rank(SB)。,对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,谢 谢！,
