资源描述：
《《b非线性分类器》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、4.3近邻法4.3.1最近邻法4.3.2K-近邻法及错误率分析4.3.3减少计算量和存储量的方法问题的提出及解决前面利用每一类的“代表点”设计分段线性分类器是最简单而直接的设计方法,这类方法的缺点是所选择的“代表点”不一定能很好的代表各个类,其结果是使所设计分类器的错误率增加.需要用其他方法来降低错误率…本章讨论的方法是将各类中全部样本都作为“代表点”的情况,这样的决策方法称为近邻法.下面我们首先详细介绍一般的近邻法,然后讨论几种改进的方法.4.3.1最近邻法1最近邻决策规则假定有c个类别ω1,ω2,…,ωc的模式识别问题,每类有标
2、明类别的样本Ni个,i=1,2,…,c.我们可以规定ωi类的判别函数为gi(x)=min
3、
4、x–xki
5、
6、,k=1,2,…,Nik其中xki的下标i表示ωi类,k表示ωi类Ni个样本中的第k个.则决策规则可以写为:若gj(x)=mingi(x),i=1,2,…,ci则决策x∈ωj最近邻法的直观解释相当简单,就是说对未知样本x,我们只要比较x与已知样本数为N,类别为c的样本群之间的欧氏距离,并决策x与离它最近的样本同类.如图:假设有N个样本,被分为3类.★x则有:x∈ω3ω1ω2ω3x1x2对于未知样本x,用最近邻法进行分类.2最近邻
7、法的错误率分析设N个样本下的平均错误率为PN(e),且样本x的最近邻为x’则,PN(e)=∫PN(e
8、x)P(x)d(x)=∫[∫PN(e
9、x,x’)p(x’
10、x)dx’]p(x)d(x)我们定义最近邻法的渐进平均错误率P为当N→∞时,PN(e)的极限,则有cP=limPN(e)=∫[1-∑P2(ωi
11、x)]p(x)dxN→∞i=1此时我们可以证明以下关系P*≤P≤P*(2-c/(c-1)P*)其中P*为贝叶斯错误率,c为类数最近邻法的错误率显然大于或等于贝叶斯错误率P*,但在某些特定情况下,可以等于贝叶斯错误率.均有P=P*①当P
12、(ωm
13、x)=1,P(ωi
14、x)=0,i=1,2,…,c,i≠m时如:②当P(ωm
15、x)=1/c,i=1,2,…,c时或根据贝叶斯条件错误率,我们可得以下式子:c1-∑P2(ωi
16、x)≤2p*(e
17、x)-c/(c-1)[p*(e
18、x)]2i=1(P*)2≤∫[p*(e
19、x)]2p(x)dx根据以上结果我们可得P≤p*[2-c/(c-1)p*]下面用图形来说明最邻近法错误率上下界与贝叶斯错误率的关系P(c-1)/c(c-1)/cp*P=p*P=p*[2-c/(c-1)p*]4.3.2k-近邻法k-近邻法是最近邻法的一个推广.这个方法就
20、是取未知样本x的k个近邻,看这k个近邻多数属于哪一类,就把x归为哪一类.在N个样本中,若k1,k2,…,kc分别是k个近邻中属于ω1,ω2,…,ωc的样本数,则我们可以定义判别函数为:决策规则为:若gj(x)=maxki则决策x∈ωjgi(x)=ki,i=1,2,…,c1.k-近邻法决策规则2.k-近邻法的错误率分析将近邻法推广到k近邻法的一个重要目的就是可以降低决策的错误率,下面我们先给出一个图形来直观说明一下ω1ω2★x由最近邻法,可得x∈ω1结论,但似乎不正确…贝叶斯决策面ω1ω2贝叶斯决策面用k近邻法决策★xk1k2由于k2
21、>k1,所以x∈ω2,这也和贝叶斯决策面决策的相同.k=k1+k2k2>k1根据最近邻法错误率分析,当样本数N趋于∞时,P=limPN(e)N∞则有p*<=p<=p*[2-c/(c-1)]下面我们给出当k递增的时候,k-邻近法的错误率p与贝叶斯错误率p*的关系K=1K=3K=7PP*(c-1)/c(C-1)/c贝叶斯错误率当k=1时,k-近邻法的错误率对应于最近邻法的错误率.当k增加时,上限逐渐靠近下限-贝叶斯错误率p*,当k趋于无穷时,上下限碰在一起,从而k-近邻法趋于最优.近邻法有方法简单的优点,且错误率在贝叶斯错误率p*和两倍
22、贝叶斯错误率2p*之间,正是近邻法这种优良性质,使它成为模式分类的重要方法之一.1需要将所有样本存入计算机中,每次决策都要计算识别样本x与全部训练样本之间的距离并进行比较,因此使得存储量和计算量都很大.2虽然在所有情况下,对未知样本x都可以进行决策,但当错误代价很大时,会产生较大的风险.3上述分析都是渐进的,就是说要求样本数N趋于无穷,这是在任何实际场合都无法实现的.?如何解决…但是近邻法还存在下列问题…4.3.3减少计算量和存储量的方法近邻法的一个缺点就是计算量大,未知样本x要逐个与全体样本X中每个样本计算欧氏距离.为了减少计算的
23、次数,也就是不必计算x到样本集X中每个样本xi的距离,只需要计算其中一部分的距离就可以找出最近邻,于是引出了快速搜索近邻法.快速近邻法的基本考虑是将样本分级分成一些不相交的子集,并且在子集的基础上进行搜索.1快速搜索算法法几种算法:快
