机器学习非参数方法

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

1、非参数方法单击此处添加标题前面的章节中，我们介绍了参数和半参数方法，这两种方法在实际训练前都需要对数据遵从的模型进行一个假定，这个假定可以是一个已知的概率分布或混合分布。参数方法的优点是把估计概率密度、判别式或回归函数问题归结为估计少量参数值，缺点则是模型假定并非总成立，当不成立时就会出现很大的误差。这时我们就需要使用非参数方法，其中我们只需要假定一个事实：即相似的输入具有相似的输出。因为我们一般都认为世界的变化时平稳、量变到质变的，因此无论是密度、判别式还是回归函数都应当缓慢地变化。在这样的非参数估计（nonparamitricestimation）中，局部实例对于密度的影响

2、就显得颇为重要，而较远的实例影响则较小。本节要点如下：k-近邻估计Pazen窗K近邻最简单的分段线性分类器：把各类划分为若干子类，以子类中心作为类别代表点，考查新样本到各代表点的距离并将它分到最近的代表点所代表的类。极端情况，将所有样本都作为代表点－－－－近邻法问题描述:特征向量类别X=(0.1,0.1)?特征向量类别(0.1,0.2)W1(0.2,0.1)W1(0.4,0.5)W2(0.5,0.4)W2最小距离分类器：将各类训练样本划分成若干子类，并在每个子类中确定代表点，一般用子类的质心或邻近质心的某一样本为代表点。测试样本的类别则以其与这些代表点距离最近作决策。该法的缺点

3、是所选择的代表点并不一定能很好地代表各类，其后果将使错误率增加。最近邻法的基本思想：以全部训练样本作为“代表点”，计算测试样本与这些“代表点”，即所有样本的距离，并以最近邻者的类别作为决策。近邻法是由Cover和Hart于1968年提出的，随后得到理论上深入的分析与研究，是非参数法中最重要的方法之一。在二维情况下，最近邻规则算法使得二维空间被分割成了许多Voronoi网格，每一个网格代表的类别就是它所包含的训练样本点所属的类别。最近邻法的错误率是比较难计算的，这是因为训练样本集的数量总是有限的，有时多一个少一个训练样本对测试样本分类的结果影响很大。红点表示A类训练样本，蓝点表示

4、B类训练样本，而绿点O表示待测样本。假设以欧氏距离来衡量，O的最近邻是A3，其次是B1，因此O应该属于A类；但若A3被拿开，O就会被判为B类。这说明计算最近邻法的错误率会有偶然性，也就是指与具体的训练样本集有关。同时还可看到，计算错误率的偶然性会因训练样本数量的增大而减小。因此我们就利用训练样本数量增至极大，来对其性能进行评价。这要使用渐近概念，以下都是在渐近概念下来分析错误率的。当最近邻法所使用的训练样本数量N不是很大时，其错误率是带有偶然性的。下图所示为一个在一维特征空间的两类别情况：X表示一待测试样本，而X'是所用训练样本集中X的最邻近者，则错误是由X与X'分属不同的类别

5、所引起的。由于X‘与所用训练样本集有关，因此错误率有较大偶然性。但是如果所用训练样本集的样本数量N极大，即N→∞时，可以想像X‘将趋向于X，或者说处于以X为中心的极小邻域内，此时分析错误率问题就简化为在X样本条件下X与一个X(X’的极限条件)分属不同类别的问题。如果样本X的两类别后验概率分别为P(ω1

6、X)与P(ω2

7、X)，那么对X值，在N→∞条件下，发生错误决策的概率为：而在这条件下的平均错误率P称为渐近平均错误率，是PN(e)在N→∞的极限。为了与基于最小错误率的贝叶斯决策方法对比，下面写出贝叶斯错误率的计算式：其中若是两类问题，则贝叶斯错误率：最近邻法错误率：可见在一般情

8、况下△P是大于零的值，只要P(ω1

9、X)＞P(ω2

10、X)＞0。有以下两种例外情况△P＝0：P(ω1

11、X)＝1P(ω1

12、X)＝P(ω2

13、X)＝1/2。请想一下，什么情况下P(ω1

14、X)＝1或P(ω2

15、X)=1?P(ω1

16、X)=P(ω2

17、X)会出现什么什么情况？一般来说，在某一类样本分布密集区，某一类的后验概率接近或等于1。此时，基于最小错误率贝叶斯决策基本没错，而近邻法出错可能也很小。而后验概率近似相等一般出现在两类分布的交界处，此时分类没有依据，因此基于最小错误率的贝叶斯决策也无能为力了，近邻法也就与贝叶斯决策平起平坐了。从以上讨论可以看出，当N→∞时，最近邻法的渐近平均错误率

18、的下界是贝叶斯错误率，这发生在样本对某类别后验概率处处为1的情况或各类后验概率相等的情况。最近邻法的错误率高于贝叶斯错误率，可以证明以下关系式成立：由于一般情况下P*很小，因此又可粗略表示成：可粗略说最近邻法的渐近平均错误率在贝叶斯错误率的两倍之内。小结模式识别（机器自动分类）的基本方法有两大类：一类是将特征空间划分成决策域，这就要确定判别函数或确定分界面方程。另一种方法则称为模板匹配，即将待分类样本与标准模板进行比较，看跟哪个模板匹配度更好些，从而确定待测试样本的分类。前面讨论的方法可以说