线性判别函数-Fisher.ppt

线性判别函数,已知条件,贝叶斯决策,实际问题,利用样本集直接设计分类器，即给定某个判别函数类，然后利用样本集确定出判别函数中的未知参数。,条件未知,一类简单的判别函数：线性判别函数,线性判别函数(discriminant function)是指由x的各个分量的线性组合而成的函数，一般表达式为：,权向量（weight vector）法向量（normal vector）,阈值（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上，即：,w和超平面H上任意向量正交，即w是H的法向量。,任意x，在H上投影 xpX与xp距离r,多类的情况：,将c类问题转化为c个两类问题，有c个判别函数。,把i作为一类，其余作为一类，构建c个超平面,更复杂一些，用C(C-1)/2个线性判别函数进行判别。,超平面Hij的法向量,决策规则：对一切i j有gi(x)gj(x),则把x归为i类。,判别函数和决策面：,广义线性判别函数,在一维空间中，线性函数不能解决下述分类问题（黑红各代表一类数据），可见线性判别函数有一定的局限性。,为解决上述分类问题，我们建立一个二次判别函数 g(x)=(xa)(xb)=c0+c1x+c2x*x决策规则仍是：如果g(x)=0，则判定x属于R1，如果g(x)0，则判定x属于R2。,如图所示：,如图：映射y把一条直线映射为三维空间中的一条抛物线,令：,一般对于任意高次判别函数g(x)，都可以通过适当的线性变换化为广义线性函数来处理。aTy不是x的线性函数但却是y的线性函数，它在Y空间确定了一个通过原点的超平面。通过扩维，将高次问题划为线性问题来求解，但是维数增加，会导致维数灾难。,线性判别函数的齐次简化,令x0=1则：,增广特征向量,增广权向量,一个三维增广特征空间y和增广权向量a（在原点）,这是广义线性判别函数的一个特例。y与x相比，虽然增加了一维，但保持了样本间的欧式距离不变。,变换得到的y向量仍然都在d维的子空间中，即原X空间中，方程aTy=0在Y空间确定了一个通过原点的超平面H，它对d维子空间的划分与原决策面wTx+w0=0对原X空间的划分完全相同。,Y空间中任意一点y到H的距离为：,设计线性分类器的主要步骤,1.给定一组有类别标志的样本集S,2.确定准则函数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维到一维的数学变换,其中：,对xn的分量作线性组合：,得到N个一维样本yn组成的集合，分为两个子集Y1和Y2,基本参量,1.在d维X空间,各类样本均值向量：,样本类内离散度矩阵：,总类内离散度矩阵：,样本类间离散度矩阵：,2.在一维Y空间,各类样本均值：,样本类内离散度：,总类内离散度：,目的：投影后，在一维Y空间里各类样本尽可能做到：,1.分得开,2.各类样本内部尽量密集,准则函数,化简分子：,求准则函数的极大值,化简分母：,代入准则函数,Lagrange乘子法求极值：,令：,定义函数：,?,对w求偏导并置零：,Sw非奇异,因为：,其中：,标量,忽略比例因子,w*为准则函数的极大值解，即为X空间到Y空间的最佳投影方向。,根据变换公式：,把d维空间的样本集X映射成一维空间样本集Y。,决策规则：,如何确定阈值y0？,几种一维分类问题的基本原则,维数d和样本数N很大时，用贝叶斯决策规则,否则，使用先验知识确定阈值点y0如：,