非参数判别分类方法

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

1、3.6近邻法自动分类的基本方法有两大类近邻法则在原理上属于模板匹配（1）将特征空间划分成决策域（2）模板匹配近邻法的缺点：计算量大，存储量大近邻法的优点：在模板数量很大时其错误率指标还是相当不错的。近邻法的改进方法9/8/20211中国矿业大学计算机科学与技术学院重点弄清楚近邻法的定义(包括k近邻法)，与基本做法弄清“近邻法性能好”是在什么意义上讲的。知道渐进平均错误率的定义快速搜索方法是使用怎样的原理？剪辑近邻法的原理是什么?而压缩近邻法与剪辑近邻法有什么不同之处？9/8/20212中国矿业大学计算机科学与技术学院3.6.1近邻法原理及其决策规则近邻法是由Cover和Hart于196

2、8年提出的，随后得到理论上深入的分析与研究，是非参数法中最重要的方法之一。这一节将讨论其基本原理，错误率分析及若干改进方法。9/8/20213中国矿业大学计算机科学与技术学院将与测试样本最近邻样本的类别作为决策的方法称为最近邻法。对一个C类别问题，每类有Ni个样本，i＝1,…,C,则第i类ωi的判别函数最近邻法决策规划其中Xik表示是ωi类的第k个样本。如果则决策X∈ωj决策规则为：9/8/20214中国矿业大学计算机科学与技术学院基本规则是，在所有N个样本中找到与测试样本的k个最近邻者，其中各类别所占个数表示成ki,i＝1,…,c，则决策规划是：k—近邻法决策规划如果则决策X∈ωjk

3、近邻一般采用k为奇数，跟投票表决一样，避免因两种票数相等而难以决策。9/8/20215中国矿业大学计算机科学与技术学院计算错误的偶然性：因为训练样本集的数量总是有限的，有时多一个少一个训练样本对测试样本分类的结果影响很大。利用训练样本数量增至极大，来对其性能进行评价。渐近平均错误率3.6.2近邻法错误率分析9/8/20216中国矿业大学计算机科学与技术学院如果所用训练样本集的样本数量N极大，即N→∞时，可以想像X'将趋向于X，或者说处于以X为中心的极小邻域内，此时分析错误率问题就简化为在X样本条件下X与一个X(X'的极限条件)分属不同类别的问题。如果样本X的两类别后验概率分别为P(ω1

4、

5、X)与P(ω2

6、X)，那么对X值，在N→∞条件下，发生错误决策的概率为：最近邻法错误率分析9/8/20217中国矿业大学计算机科学与技术学院(3.6-1)9/8/20218中国矿业大学计算机科学与技术学院渐近平均错误率，是PN(e)在N→∞的极限。与基于最小错误率的贝叶斯决策方法对比其中而则(3.6-2)(3.6-3)9/8/20219中国矿业大学计算机科学与技术学院由可得上式减去从式(3.6-5)可见在一般情况下△P是大于零的值，只要P(ω1

7、X)＞P(ω2

8、X)＞0。有以下两种例外情况△P＝0，这两种情况是P(ω1

9、X)＝1或P(ω1

10、X)＝P(ω2

11、X)＝1/2。(3.6-4)

12、(3.6-5)9/8/202110中国矿业大学计算机科学与技术学院思考什么情况下P(ω1

13、X)＝1或P(ω2

14、X)=1?P(ω1

15、X)=P(ω2

16、X)会出现什么什么情况？答：一般来说，在某一类样本分布密集区，某一类的后验概率接近或等于1。此时，基于最小错误率贝叶斯决策基本没错，而近邻法出错可能也很小。而后验概率近似相等一般出现在两类分布的交界处，此时分类没有依据，因此基于最小错误率的贝叶斯决策也无能为力了，近邻法也就与贝叶斯决策平起平坐了。9/8/202111中国矿业大学计算机科学与技术学院当N→∞时，最近邻法的渐近平均错误率的下界是贝叶斯错误率，这发生在样本对某类别后验概率处处为1的

17、情况或各类后验概率相等的情况。在其它条件下，最近邻法的错误率要高于贝叶斯错误率，可以证明以下关系式成立。一般情况下P*很小最近邻法错误率上下界与贝叶斯错误率的关系9/8/202112中国矿业大学计算机科学与技术学院k—近邻法错误率分析对于两类别问题k-邻域的情况，则错误出现在k个邻域样本中，正确的类别所占样本未过半数，得到(3.6-6)其中(3.6-7)9/8/202113中国矿业大学计算机科学与技术学院将(3.6-7)与(3.6-6)相比较，(3.6-6)相当于(3.6-7)中k＝1的情况，而在(3.6-7)中当k增大时PkN→∞(e

18、X)是单调递减的。因此可以得出结论，在N→∞的条

19、件下，k-近邻法的错误率要低于最近邻法，从图中也可看出，无论是最近邻法，还是k-近邻法，其错误率的上下界都是在一倍到两倍贝叶斯决策方法的错误率范围内。K-近邻法错误率上下界与贝叶斯错误率的关系9/8/202114中国矿业大学计算机科学与技术学院3.6.3改进的近邻法近邻法的严重弱点与问题：需要存储全部训练样本，以及繁重的距离计算量。改进的方法大致分为两种原理：（1）对样本集进行组织与整理，分群分层，尽可能将计算压缩到在接近测试样本邻域的小范围内