线性判别分析非参数判别分类方法第四次课.ppt

《线性判别分析非参数判别分类方法第四次课.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、本章内容3.1线性判别函数3.2线性分类器Fisher线性判决感知准则函数3.3分段线性分类器3.4近邻分类器总结习题3.2.2Fisher线性判决Fisher线性判决的基本思想是寻找一个最好的投影方向,当特征向量x从d维空间映射到这个方向上时,两类能最好地分开。这个方法实际上涉及特征维数的压缩问题。3.2线性分类器分析w1方向之所以比w2方向优越,可以归纳出这样一个准则：即向量w的方向选择应能使两类样本投影的均值之差尽可能大些,而使类内样本的离散程度尽可能小。这就是Fisher准则函数的基本思路。

2、第一步：计算参量。(1)各类样本的均值向量μi:(2)样本类内离散度矩阵Si：总类内离散度矩阵Sw:第二步：计算最优投影方向，并将样本往该方向上投影。第三步：决策。在投影空间内的决策准则为:若y>y0,则x∈ω1,否则x∈ω2。Fisher线性判决步骤采用类似于人认知错误、纠正错误、通过自学习改善自己认识事物本领的过程，随意确定判别函数初始值，该值在对样本分类训练过程中逐步修正直至最终确定。基本思想：寻找一个权向量，使规范化增广样本向量集的错分类样本数最少。3.2.3感知准则函数一、基本概念1.线

3、性可分性已知来自ω1和ω2两类的样本集{x1,x2,…,xN},两类的线性判决函数为yi为增广样本向量,v为增广权向量。线性可分：如果存在一个线性分类器能把每个样本正确分类,即若存在一个权向量v,使得对于任何yi∈ω1,都有vTyi>0,而对于任何yi∈ω2,都有vTyi<0,则称这组样本集线性可分;否则称为线性不可分。反过来,若样本集是线性可分的,则必然存在一个权向量v,能将每个样本正确地分类。2.样本的规范化如果样本集{y1,y2,…,yN}线性可分,则一定存在某个或某些权向量v,使如果令，则vT

4、zi>0。规范化增广样本向量经过这样的变换后,我们可以不考虑样本原来的类别标志,只要找到一个对全部样本zi都满足vTzi>0(i=1,2,…,N)的权向量即可。样本的规范化3.解向量和解区满足vTzi>0(i=1,2,…,N)的权向量称为解向量。若把v看成是权向量空间中的一点,对于任一zi,vTzi=0在权向量空间确定了一个超平面,这个超平面把权空间分为两个半空间,该超平面的法向量为zi,超平面正侧的向量满足vTzi>0。相应地,N个样本确定了N个超平面,每个超平面把权空间分为两个半空间。所以,满足vT

5、zi>0(i=1,2,…,N)的权向量必在这N个超平面正侧的交叠区,称这一交叠区为解区,解区中的任意向量都是解向量v*。二、感知准则函数感知准则函数方法利用错分类对现决策权向量进行修正直至收敛。这种方法只对线性可分情况适用，并且只适用于两类判决。感知准则函数方法的思路是：先随意找一个初始向量v，写作v(0)，然后用训练样本集中的每个样本来计算。一旦发现有的zi，使vTzi<0，则说明当前的广义权向量v(0)不适合还需要进一步修正。设Z={z1,z2,…,zN}是经过规范化的一组样本集,定义感知准则函数:其

6、中,Zk是被权向量v错分类的样本集合,当z∈Zk时,有显然,Jp(v)≥0。梯度下降算法求Jp(v)准则函数的极小值。迭代公式为其中即Zk为第k步被错分的样本集。ρk为正，是步长系数。两点说明：感知准则函数方法只是对线性可分样本集有效，而对线性不可分的样本集，该算法不能收敛。这一节对感知准则函数的讨论，只是很初步的。但这种利用错误提供的信息，进行自修正的思想意义是十分深远的。这种只解决线性分类的感知器称为单层感知器，在此基础上发展起来的多层感知器在原理上能解决非线性分类、多类划分，以及非线性拟和非线性

7、映射等多种问题。3.2.4最小平方误差准则函数设由X={x1,x2,…,xN}得到的规范化增广向量集合为{z1,z2,…,zN},分类器设计的任务就在于寻找一个矢量v,满足:引入余量bi,用超平面:代替zTiv>0,则引入余量后的解区在原解区之内。将上式写成矩阵形式即为定义误差向量:定义平方误差准则函数:Js(v)是一个非负函数,当有解时,Js(v)达到最小值0,此时的矢量v*满足:v*能将所有样本正确分类。若v*不能使某个样本zj正确分类,即(v*)Tzj≠bj,则e2j=(vTzj－bj)2。错分样

8、本的结果是使Js(v)增大,因此,Js(v)越小越好,其最小值0为理想分类结果,实现所有样本的正确分类。求使Js(v)最小的v*有两种方法:梯度下降法和解析法。1.梯度下降法对Js(v)求梯度(3-78)相应地,梯度下降算法为其中，ρk为学习速率;初值v(0)可任意选取。2.解析法解析法得到的是伪逆解。令Js(v)=0得(3-79)其中(3-80)ZTZ为(d+1)×(d+1)方阵,一般是满秩的,因此有唯一解:(3