线性判别函数-Fisher

线性判别函数已知条件贝叶斯决策实际问题利用样本集直接设计分类器，即给定某个判别函数类，然后利用样本集确定出判别函数中的未知参数。条件未知一类简单的判别函数：线性判别函数线性判别函数(discriminantfunction)是指由x的各个分量的线性组合而成的函数，一般表达式为：0()Tgxwxw权向量（weightvector）法向量（normalvector）阈值（threshold）偏置（bias）对于两类问题的决策规则为：如果g(x)0，则判定x属于C1，如果g(x)0，则判定x属于C2，如果g(x)=0，可将x任意分到某一类，或拒绝。两类情况:方程g(x)=0定义了一个判定面，它把归类于C1的点与归类于C2的点分开来。当g(x)是线性函数时，这个平面被称为“超平面”(hyperplane)。若x1,x2在H上，即：1020TTwxwwxw12()0Twxxw和超平面H上任意向量正交，即w是H的法向量。任意x，在H上投影xpX与xp距离r||||pwxxrw00000()()||||||||||||(),()||||||||TpTTpwgxwxr用代入多类的情况：将c类问题转化为c个两类问题，有c个判别函数。把ωi作为一类，其余作为一类，构建c个超平面更复杂一些，用C(C-1)/2个线性判别函数进行判别。TiiioijTiji0j0g(x)=wx+w,G(x)=g(x)-g(x)=0,i,j=1,2..,c(w-w)x+(w-w)=0超平面Hij的法向量决策规则：对一切i≠j有gi(x)gj(x),则把x归为ωi类。判别函数和决策面：广义线性判别函数在一维空间中，线性函数不能解决下述分类问题（黑红各代表一类数据），可见线性判别函数有一定的局限性。为解决上述分类问题，我们建立一个二次判别函数g(x)=(x–a)(x–b)=c0+c1x+c2x*x决策规则仍是：如果g(x)=0，则判定x属于R1，如果g(x)0，则判定x属于R2。如图所示：R1R1R2xg(x)如图：映射y把一条直线映射为三维空间中的一条抛物线01122123321x,cyayyaacxyac2012Tg(x)=c+cx+cx=ay（广义线性判别函数）令：一般对于任意高次判别函数g(x)，都可以通过适当的线性变换化为广义线性函数来处理。aTy不是x的线性函数但却是y的线性函数，它在Y空间确定了一个通过原点的超平面。通过扩维，将高次问题划为线性问题来求解，但是维数增加，会导致维数灾难。0()Tgxwxw线性判别函数的齐次简化令x0=1则：增广特征向量增广权向量一个三维增广特征空间y和增广权向量a（在原点）这是广义线性判别函数的一个特例。y与x相比，虽然增加了一维，但保持了样本间的欧式距离不变。变换得到的y向量仍然都在d维的子空间中，即原X空间中，方程aTy=0在Y空间确定了一个通过原点的超平面H’，它对d维子空间的划分与原决策面wTx+w0=0对原X空间的划分完全相同。Y空间中任意一点y到H’的距离为：ayaaxgrT'设计线性分类器的主要步骤1.给定一组有类别标志的样本集S2.确定准则函数J(S,w,w0)3.用优化技术得到极值解w*,w0*这样就得到线性判别函数g(x)=w*Tx+w0*,对未知样本xk，计算g(xk),然后根据决策规则就可判断xk所属的类别。Fisher线性判别问题中的维数问题把d维空间中的样本投影到一条直线上降低维数Fisher线性判别把同一组样本点向两个不同的方向作投影。（右图更易分开）始于R.A.Fisher(1936年）Fisher法解决的基本问题：如何根据实际情况找到一条最好的、最易于分类的投影线。d维到一维的数学变换,,...,21NxxxdN维样本个的样本集个属于的样本集个属于222111::NXNXinTnNnxwy,...,2,1,其中：对xn的分量作线性组合：得到N个一维样本yn组成的集合，分为两个子集Y1和Y2基本参量1.在d维X空间2,1,1ixNmiXxii212,1,SSSimxmxSwXxTiiiiTbmmmmS2121各类样本均值向量：样本类内离散度矩阵：总类内离散度矩阵：样本类间离散度矩阵：2.在一维Y空间2,1,1~iyNmiYyii2,1,~~22imySiYyii22212~~~SSSw各类样本均值：样本类内离散度：总类内离散度：目的：投影后，在一维Y空间里各类样本尽可能做到：1.分得开2.各类样本内部尽量密集越小越好类内离散度2221~~SS越大越好两类均值之差21~~mm准则函数2221221~~~~JSSmmwFiTYyiTYyTiYyiimwxNwxwNyNmiii111~wSwwmmmmwmwmwmmbTTTTT2121221221~~化简分子：求准则函数的极大值化简分母：wSwwmxmxwmwxwmySiTXxTiiTXxiTTYyiiiii~~222wSwwSSwSSwTT212221~~代入准则函数wSwwSwSSmmwwTbTF2221221~~~~JLagrange乘子法求极值：令：0cwSwwT定义函数：cwSwwSwwLwTBT,对w求偏导并置零：0,wSwSwwLwb**wSwSwbSw非奇异**1wwSSbwxAxTbmmmmS2121RmmwmmmmwSTb21*2121**21wmmRT因为：其中：标量得：代入**1wwSSbwRmmSwSSwwbw211*1*211*mmSRww211*mmSww忽略比例因子w*为准则函数的极大值解，即为X空间到Y空间的最佳投影方向。inTnNnxwy,...,2,1,根据变换公式：把d维空间的样本集X映射成一维空间样本集Y。决策规则：2100*xyyxwyT如何确定阈值y0？几种一维分类问题的基本原则•维数d和样本数N很大时，用贝叶斯决策规则•否则，使用先验知识确定阈值点y0如：2ln2~~~~~2~~21212130212211202110NNPPmmymNNmNmNymmy