5第五章 近邻法

《5第五章 近邻法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章近邻法5.1引言5.2距离度量5.3最近邻法5.4k-近邻法5.5近邻法的改进5.6可作拒绝决策的近邻法1第五章近邻法郝红卫引言最小距离法中用均值作为每一类的“代表点”很多情况下，均值不一定能很好地代表各类代表点的选择很关键将全部样本都作为代表点——近邻法2第五章近邻法郝红卫引言除代表点外，另一个要素是距离到目前为止，我们主要使用了欧式距离实际上，距离的概念要广泛得多先来讨论距离度量的性质3第五章近邻法郝红卫距离度量度量D(·,·)本质上是一个函数，该函数给出了两个模式之间的标量距离的大小。一个度量必须满足4个性质：对于任意的向量a，b，和c，有非负性：D(a,b)≥

2、0自反性：D(a,a)=0当且仅当a=b对称性：D(a,b)=D(b,a)三角不等式D(a,b)+D(b,c)≥D(a,c)4第五章近邻法郝红卫距离度量d维空间中的欧式距离能够满足这些性质5第五章近邻法郝红卫距离度量更为一般的d维空间的度量为Minkowski距离度量通常也被称为Lk范数欧式距离就是L2范数6第五章近邻法郝红卫距离度量L1范数也被称为Manhattan距离或街区距离、绝对距离显然，欧式距离和绝对距离是明氏距离的两个特例手工运算时，为简便起见，通常采用绝对距离7第五章近邻法郝红卫最近邻法最近邻决策规则假定有c个类别1,2,…,c的分类问题，每类有标明类别

3、的样本Ni个，i=1,2,…,c，我们可以定义i类的判别函数为其中xik的角标i表示i类，k表示i类Ni个样本中的第k个。决策规则：若则决策8第五章近邻法郝红卫最近邻法最近邻法对未知样本x，比较x与所有已知样本之间的欧式距离，并决策x与离它最近的样本同类。9第五章近邻法郝红卫最近邻法最近邻法的错误率令P为最近邻法的错误率，P*为贝叶斯错误率，c为类别数。可以证明，存在下述关系或近似为P*≤P≤2P*10第五章近邻法郝红卫k-近邻法对最近邻法的推广取未知样本x的k个近邻，看这k个近邻中多数属于哪一类，就把x归为哪一类。11第五章近邻法郝红卫k-近邻法假定有c个类别1,

4、2,…,c的分类问题，每类有标明类别的样本Ni个，i=1,2,…,c，若k1,k2,…,kc分别是k个近邻中属于1,2,…,c类的样本数，我们可以定义i类的判别函数为gi(x)=ki,i=1,2,…,c决策规则为：若则决策12第五章近邻法郝红卫k-近邻法错误率13第五章近邻法郝红卫k-近邻法特点简单错误率在贝叶斯错误率和两倍贝叶斯错误率之间需要存储所有样本，每次决策都要计算待识别样本与全部训练样本之间的距离并进行比较，存储量和计算量都很大14第五章近邻法郝红卫k-近邻法51近邻分类器示例.pdf52近邻分类器示例.doc15第五章近邻法郝红卫近邻法的改进快速算法

5、剪辑近邻法压缩近邻法16第五章近邻法郝红卫近邻法的改进快速算法基本思想是将样本分级，分成一些不相交的子集，并在子集的基础上进行搜索把样本集分级分成多个子集（树状结构）每个子集（结点）可用较少几个量代表通过将新样本与各结点比较排除大量候选样本只有最后的结点（子集）中逐个样本比较，找出近邻17第五章近邻法郝红卫近邻法的改进令X={x1,x2,…,xN}表示样本集，我们的目的是在X中寻找样本x的k个近邻，为简单起见，先看最近邻的情况(k=1)。算法分为两个阶段：将X分级分解用搜索算法找出x的最近邻18第五章近邻法郝红卫近邻法的改进第一阶段：样本集分级分解首先将X分为l个子集，每个

6、子集再分成l个子集。依次进行下去，就可以得到一个树结构。19第五章近邻法郝红卫近邻法的改进分级示意图L=0L=1L=3L=220第五章近邻法郝红卫近邻法的改进令：Xp：结点p对应的样本子集Np：Xp中的样本数Mp：样本子集Xp中的样本均值rp：从Mp到xi∈Xp的最大距离21第五章近邻法郝红卫近邻法的改进第二阶段：搜索首先给出两个规则，利用它们可以检验x的最近邻是否在Xp中。规则1：如果存在B+rp

7、近邻法的改进树搜索算法置B＝∞，L＝0，p＝0（L是当前水平，p是当前结点）将当前结点的所有直接后继结点放入一个目录表中，并对这些结点计算D(x,Mp)对步骤2中的每个结点p，根据规则1，如果有D(x,Mp)>B+rp，则从目录表中去掉p23第五章近邻法郝红卫近邻法的改进如果步骤3的目录表中已经没有结点，则后退到前一个水平，即置L=L-1。如果L=0则停止，否则转步骤3。如果目录表中有一个以上的结点存在，则转步骤5在目录表中选择最近结点p′，它使D(x,Mp)最小化，并称该p′为当前执行结点，从目录表中去掉p′。如