k-近邻法综述

1、KNN（K-Nearest Neighbor），代表k 个最近邻分类法，通过K 个最与之相近的历史记录的组合来辨别新的记录。KNN 是一个众所周知的统计方法，在过去的40 年里在模式识别中集中地被研究7。KNN 在早期的研究策略中已被应用于文本分类，是基准Reuters 主体的高操作性的方法之一。其它方法，如LLSF、决策树和神经网络等。K-近邻算法的。K-近邻法的概念K-近邻算法的思想如下：首先，计算新样本与训练样本之间的距离，找到距离最近的K个邻居；然后，根据这些邻居所属的类别来判定新样本的类别，如果它们都属于同一个类别，那么新样本也属于这个类；否则，对每个后选类别进行评分，按照某种规则确

2、定新样本的类别。取未知样本X的K个近邻，看着K个近邻多数属于哪一类，就把X分为哪一类。即，在X的K个样本中，找出X的K个近邻。K-近邻算法从测试样本X开始生长，不断的扩大区域，直到包含进K个训练样本，并且把测试样本X的类别归为着最近的K个训练样本中出现频率最大的类别。例如，图3.1中K=6的情况，根据判定规则，测试样本X被归类为黑色类别。.。 .。 . . . . . 图3.1 K-近邻法近邻分类是基于眼球的懒散的学习法，即它存放所有的训练样本，并且知道新的样本需要分类时才建立分类。这与决策数和反向传播算法等形成鲜明对比，后者在接受待分类的新样本之前需要构造一个一般模型。懒散学习法在训练时比急

3、切学习法快，但在分类时慢，因为所有的计算都推迟到那时。优点:简单，应用范围广；可以通过SQL语句实现；模型不需要预先构造。缺点:需要大量的训练数据；搜索邻居样本的计算量大，占用大量的内存；距离函数的确定比较困难；分类的结果与参数有关。 K-近邻法算法研究K-近邻法的数学模型用最近邻方法进行预测的理由是基于假设：近邻的对象具有类似的预测值。最近邻算法的基本思想是在多维空间Rn 中找到与未知样本最近邻的k 个点，并根据这k个点的类别来判断未知样本的类。这k个点就是未知样本的k-最近邻。算法假设所有的实例对应于n 维空间中的点。一个实例的最近邻是根据标准欧氏距离定义，设x的特征向量为：其中，ar(x

4、)表示实例x的第r个属性值。两个实例xi和xj间的距离定义为d(xi，xj)，其中：d(xi，xj)=在最近邻学习中，离散目标分类函数为f：Rn-V 其中V是有限集合v1，v2，vs，即各不同分类集。最近邻数k值的选取根据每类样本中的数目和分散程度进行的，对不同的应用可以选取不同的k值。如果未知样本si的周围的样本点的个数较少，那么该k个点所覆盖的区域将会很大，反之则小。因此最近邻算法易受噪声数据的影响，尤其是样本空间中的孤立点的影响。其根源在于基本的k-最近邻算法中，待预测样本的k个最近邻样本的地位是平等的。在自然社会中，通常一个对象受其近邻的影响是不同的，通常是距离越近的对象对其影响越大8

5、。近邻法研究方法该算法没有学习的过程，在分类时通过类别已知的样本对新样本的类别进行预测，因此属于基于实例的推理方法。如果取K等于1，待分样本的类别就是最近邻居的类别，称为NN算法。只要训练样本足够多，NN算法就能达到很好的分类效果。当训练样本数趋近于-时，NN算法的分类误差最差是最优贝叶斯误差的两倍；另外，当K趋近于时,KNN算法的分类误差收敛于最优贝叶斯误差。下面对K-近邻算法描述：输入：训练数据集D=(Xi,Yi),1iN，其中Xi是第i个样本的条件属性，Yi是类别,新样本X，距离函数d。输出:X的类别Y。for i=1 to N do 计算X和Xi之间的距离d(Xi,X)；end for

6、对距离排序，得到d(X,Xi1) d(X,Xi2) d(X,XiN)；选择前K个样本：S=(Xi1,Yi1)(XiK,YiK)；统计S中每个类别出现的次数，确定X的类别Y 。K-近邻法需要解决的问题(1) 寻找适当的训练数据集训练数据集应该是对历史数据的一个很好的覆盖，这样才能保证最近邻有利于预测，选择训练数据集的原则是使各类样本的数量大体一致，另外，选取的历史数据要有代表性。常用的方法是按照类别把历史数据分组，然后再每组中选取一些有代表性的样本组成训练集。这样既降低了训练集的大小，由保持了较高的准确度。(2) 确定距离函数距离函数决定了哪些样本是待分类本的K个最近邻居，它的选取取决于实际的数据和决策问题。如果样本是空间中点，最常用的是欧几里德距离。其它常用的距离函是由绝对距离、平方差和标准差。(3) 决定K的取值邻居的个数对分类的结果有一定的影响，一般先确定一个初始值，再进行调整，直到找到合适的值为止。(4) 综合K个邻居的类别多数法是最简单的一种综合方法，从邻居中选择一个出现频率最高的类别