模式识别近邻法

模式识别近邻法第1页，课件共63页，创作于2023年2月一最近邻决策规则

假定有c类模式，ω1,ω2,…,ωc,每类有个样本，i=1,2,…,c，总样本数为。对未知样本，找出已知类别的训练样本集中和最近的一个样本，把分到与该样本一样的类。

第2页，课件共63页，创作于2023年2月最近邻决策算法存储训练样本；对一新的样本x，在训练样本集中按某种距离度量找到x的最近邻(xi,yi)，令x的类别y和yi相同。使用欧式距离时：使用平方距离结果是一样的，免去了开方运算：第3页，课件共63页，创作于2023年2月近邻法和使用的距离度量关系很大将所有的特征值规范到相同的范围（比如[-1，1]），否则取值范围大的特征起的作用大。去掉噪声的、不好的特征，它们影响距离度量和性能。利用好的距离度量，如式中是互信息。或利用Mahalanobis距离：●使用k-近邻更可靠。第4页，课件共63页，创作于2023年2月二最近邻法的错误率分析下面先分析近邻法的错误率，然后讨论具体实施近邻法时的一些问题。近邻法错误率分析的思想是把它和贝叶斯错误率联系起来第5页，课件共63页，创作于2023年2月最近邻法的错误率分析

令是要分类的点，是它的最近邻,的真实类是，的真实类别是,对于和，发生错误的概率为

第6页，课件共63页，创作于2023年2月最近邻法的错误率分析假定事件“是类”和“是类”是独立的事件，则最近邻算法的条件错误率为：

第7页，课件共63页，创作于2023年2月最近邻法的错误率分析如果密度函数是连续的，而且样本点相当多，则的最近邻将非常接近，因此可以合理地认为（假定）代入上式，有

(*)第8页，课件共63页，创作于2023年2月最近邻法的错误率分析下面分析这个错误率和贝叶斯错误率间的关系令是根据贝叶斯决策规则将所分的类，即：第9页，课件共63页，创作于2023年2月最近邻法的错误率分析贝叶斯决策的条件错误率为：

(**)或写成

(1)第10页，课件共63页，创作于2023年2月为了导出的界，对(*)式中的平方项，有

(***)

对于固定的值，上式当，，都相等时取最小值。第11页，课件共63页，创作于2023年2月又由(**)式，使(***)式的取最小值的为（2）第12页，课件共63页，创作于2023年2月(***)式可以化为（把（1）和（2）代入）共(c-1)项，消除了一个(c-1)第13页，课件共63页，创作于2023年2月把上式代入(*)式并化简有，（3）第14页，课件共63页，创作于2023年2月最近邻法的错误率分析而近邻法和贝叶斯决策的错误率定义为：

第15页，课件共63页，创作于2023年2月最近邻法的错误率分析第16页，课件共63页，创作于2023年2月取(3)式期望，并利用上式，有由于贝叶斯错误率是最小的，所以完整的上下界是：

第17页，课件共63页，创作于2023年2月最近邻法的错误率分析上式的结果表明，当样本数相当多时，近邻法的错误率在贝叶斯错误率和两倍的贝叶斯错误率之间。第18页，课件共63页，创作于2023年2月的一些特殊情况

当时，第19页，课件共63页，创作于2023年2月当各类的后验概率相等时

的一些特殊情况

第20页，课件共63页，创作于2023年2月4.2K-近邻法

取未知样本的K个近邻，看这K个近邻中哪类的样本数最多，就把未知样本归到该类。

第21页，课件共63页，创作于2023年2月K-近邻法的错误率界

K-近邻的错误率的分析要复杂。当类别数c=2时，K-近邻法的错误率以一族凹函数为上界。具有如下的性质：

第22页，课件共63页，创作于2023年2月K-近邻法的错误率界这些函数的形状如下：

第23页，课件共63页，创作于2023年2月K-近邻法的错误率界第24页，课件共63页，创作于2023年2月*K-近邻法的错误率界证明K-NN法错误率的思路：（对两类，K为奇数的情况）

若，而时则发生错分，其错误率为

①

第25页，课件共63页，创作于2023年2月K-近邻法的错误率界同样，当，而时发生误分类，其错误率为

②

第26页，课件共63页，创作于2023年2月K-近邻法的错误率界所以，给出x时的条件错误率为

①＋②

第27页，课件共63页，创作于2023年2月K-近邻法的错误率界上式可以化为

(3)

第28页，课件共63页，创作于2023年2月K-近邻法的错误率界其中：

（当K为偶数时，有：

,)(4)第29页，课件共63页，创作于2023年2月K-近邻法的错误率界而给出x时的条件贝叶斯风险为

(5)

（Maclaulin）马克劳林级数展开

第30页，课件共63页，创作于2023年2月K-近邻法的错误率界利用上面的③–⑤式，有

(回想过去讲的

和间联系了起来，贝叶斯错误率的Bhattacharyya界，称为B距离。）

第31页，课件共63页，创作于2023年2月K-近邻法的错误率界例

投票法最近邻分类的错误率

第32页，课件共63页，创作于2023年2月K-近邻法的错误率界粗略地说，有些样本落在了其它类的决策区，错了。而这个错的样本又可能把正确地落在区域内的样本弄错，所以最近邻法的错误率在贝叶斯错误率和2倍贝叶斯错误率之间。

第33页，课件共63页，创作于2023年2月最近邻法的决策边界：训练样本的部分VoronoiDiagram近邻法虽然没有直接计算决策边界，然而所得到的决策边界是训练样本VoronoiDiagram的一个子集。每一条线是不同类样本间连线的平分线。样本越多，决策边界越复杂。第34页，课件共63页，创作于2023年2月减少近邻法的计算和存储问题减少训练样本的数量，尽量利用“好”的训练样本。设计好的数据结构和查找算法快速查找x的k近邻。第35页，课件共63页，创作于2023年2月存储所有的训练样本需要大量的存储，要从训练样本中挑选一些好的样本常用的方法有两种：逐步从训练集中删掉一些“坏的”样本。逐步从训练集中挑选出一些“好的”代表样本。第36页，课件共63页，创作于2023年2月4.3剪辑近邻法由前面的图可以看出，在投票法的k－近邻法中，第类的样本落在类的区域后，它可能成为某些类样本的近邻，因而引起额外的错误，这是为什么近邻法的错误率大于贝叶斯错误率的原因。

这些额外的错误可以通过去掉类落在类区域中的样本而减少（上图中的1、3、5、6）。

第37页，课件共63页，创作于2023年2月在实际问题中，由于不知道准确的贝叶斯决策边界，所以不能准确确定类落在类区域中的样本。而代之以去掉被k近邻分错的样本。这样得到的样本集合称为剪辑（Editedset）集。以后的实验样本集用剪辑集按k近邻法分类。这种算法称为剪辑近邻法。

第38页，课件共63页，创作于2023年2月在剪辑近邻法中，类的落在类区域中的有些样本被（正确）分到了类，因而未被剪掉。而类的在区域中的一些样本则有可能被误分类，而被剪辑掉。所以剪辑近邻法的错误率不可能和贝叶斯错误率一样。下面我们分析渐进情况下（即）时的错误率。第39页，课件共63页，创作于2023年2月1剪辑的最近邻法的错误率假定给出x的后验概率为和，在使用投票法的最近邻中，被正确分类和不正确分类的概率为

和

i=1,2第40页，课件共63页，创作于2023年2月剪辑的最近邻法的错误率当剪辑掉被错分的，保留分对的时，在剪辑集中x的后验概率为第41页，课件共63页，创作于2023年2月剪辑的最近邻法的错误率原来样本集若用剪辑集按NN法分类，则错误率为式中利用了，当时。第42页，课件共63页，创作于2023年2月剪辑的最近邻法的错误率可以证明，未剪辑的最近邻法的错误率和贝叶斯错误率分别为上式的上下界：

,()第43页，课件共63页，创作于2023年2月更一般的剪辑近邻法用一近邻剪辑，用一近邻分类第44页，课件共63页，创作于2023年2月更一般的剪辑近邻法重复使用最近邻法，把落在类区域中类的样本剪掉，其错误率的情况为

第45页，课件共63页，创作于2023年2月4.4压缩近邻法近邻法存在的问题计算量大，存储量大，要计算大量的样本间的距离在投票近邻法，靠近贝叶斯决策边界的点对分类有关键作用。而位于各类类中心附近、远离决策边界的点不影响分类，因而可以把它们去掉。这样减少（参考）样本点，可以节省近邻法的时间和空间。这类的算法称为压缩近邻法。第46页，课件共63页，创作于2023年2月压缩近邻法每个样本x的条件风险是表示x是否靠近决策边界的一种度量。因此可设置一个阈值τ，并把小于阈值的样本去掉，。为了避免如剪辑法中讨论的问题，减少额外的错误，应当先剪辑，后压缩。

第47页，课件共63页，创作于2023年2月压缩近邻法下面是一个压缩算法：（这个算法没有计算，另种思路）

Condensingalgor.

设两个存储器Store和Grabbag。把第一个样本放入Store中，把所有其它样本放在Grabbag中

第48页，课件共63页，创作于2023年2月压缩近邻法用当前Store中的样本按一近邻规则对Grabbag中样本进行分类。若分类正确，则该样本仍放回Grabbag中；否则，放入Store中。对Grabbag中的所有样本重复以上过程。

若从Grabbag中转到Store中的样本数为0，或Grabbag中的样本数变为0时，停止。否则转2。压缩后，以Store中的样本作为分类的参考集（设计集）

第49页，课件共63页，创作于2023年2月4.5查找k近邻的快速算法（树搜索）为了减少查找k－近邻的计算量，需要尽量避免穷尽地计算和所有样本间的距离，可把样本组织（分解）成一定的等级如树结构等，尽量排除一些不必要的计算。常用的是k-d树等一类结构和搜索算法。

第50页，课件共63页，创作于2023年2月假定样本集，目的是要在

X

中寻找未知样本x的k个近邻。为了简单，先假定k＝1，即最近邻的搜索。

下面介绍另外一种把样本组织成树结构的算法。算法分两个阶段:第51页，课件共63页，创作于2023年2月把样本集X

分级分解，组织成树结构。可根据样本在特征空间中所占的位置，把样本集分成不相交的一些子集（个），然后把这些样本子集再分解成不相交的子集，如此进行下去，直到每个终端点只含一个样本为止。如下图：第52页，课件共63页，创作于2023年2月第53页，课件共63页，创作于2023年2月树的中间节点都代表一个样本子集，可以用下列参数描述：：节点k所对应的样本子集：中的样本数：中的样本均值，从到中的样本的最大距离（不妨称为的半径）第54页，课件共63页，创作于2023年2月分成子集的方法，可根据样本在特征空间中所占的位置，把相邻样本组织成一个子集。可以用聚类分析的方法（如c均值聚类算法）第55页，课件共63页，创作于2023年2月

可以利用下面两个规则加快搜索。判断xi或xi所属的子集有否可能是x的近邻。2.搜索未知样本的（最，k）近邻（分支限界算法）规则1：令B是算法执行过程中已经找到的x的最近邻离x的距离，程序开始时可设B的初值为∞。第56页，课件共63页，创作于2023年2月令是的半径，若，则不可能是x的最近邻。

这个规则可以排除不可能是x近邻的，不用计算每个，。直观意义如下：

第57页，课件共63页，创作于2023年2月根据三角不等式：

规则1

对于终端节点，可以利用下面的规则2迅速检验它能否成为x的最近邻，省去计算所有的。

第58页，课件共63页，创作于2023年2月规则2：若,