k邻近法

k-Nearest Neighbors Algorithm

Posted by Jerry on December 24, 2016

“给定一个训练数据集,对新的输入实例,在训练数据集汇总找到与该实例最邻近的k个实例,这k个实例的多数属于某个类,就把该输入实例分为这个类。”

概述

在模式认知中,k邻近算法是用于分类和回归的非参数算法(a non-parametric method )。在这两种情况下,输入由特征空间中的k个最接近的训练样本组成。输出取决于k-NN是否用于分类或者回归:

  1. 在k-NN分类中,输出是类别的成员(比如约会网站例子中的,三种类型(或者说标签),1,2,3,输出结果确定为1,2,3中一种)。 对象通过其邻居的多数投票来分类,其中对象被分配给在其k个最近邻居中最常见的类(k是正整数,通常是小的)。 如果k = 1,则将对象简单地分配给该单个最近邻的类。
  2. 在k-NN回归中,输出是对象的属性值。 该值是其k个最近邻居的值的平均值。

k-NN是一种基于实例的学习(又称记忆学习,通过将新问题实例与在训练中看到的实例进行比较,这些实例已经存储在存储器中)或惰性学习(直到给定一个测试元组才开始构造分类模型),其中函数仅在本地近似,并且所有计算被推迟到分类。k-NN算法是所有机器学习算法中最简单的算法之一。 k-NN没有显示的学习过程

k邻近算法模型

kNN算法有三要素:距离度量、k值选择和分类决策规则决定。k邻近发中,当训练集、距离度,k值及分类规则(如多数表决)确定后,对于任何一个新的输入实例,它所属的类唯一确定。只是预测出的类可能不是我们所想要的即预测失败。

距离度量

特征空间中两个实例点的距离是两个实例点的相似程度的反映,k邻近模型的特征空间一般是n维实数向量空间Rn。使用的距离一般是欧式距离,但也可以是其他距离如Lp距离或Minkowski距离。 distance

k值选择

通常选择较小的k值,就相当于用较小的邻域中的训练实例进行预测,“学习”误差的近似误差(approximation error)会减小,只有与输入实例较近的(相似的)训练实例才会对预测结果起作用。但缺点是“学习”估计误差(estimation error)会增大,预测结果会对邻近的实例点非常敏感。如果邻近的实例点恰巧为噪声,预测就会出错。

如果选择较大的k值,就相当于用较大邻域的训练实例进行预测,优点在于减少估计误差,增大学习误差。这时与输入实例较远的(不相似的)训练实例也会对预测起作用,使预测发生错误,k值的增大是的整体模型变得简单。如果k=N,那么无论输入实例是什么,都简单地预测属于在训练实例中最多的类。

k值一般取一个比较小的数值,通常用交叉验证法来选取最优的k值。

分类决策规则

k-NN中的决策规则往往是多数表决,即有输入实例的k个邻近训练实例中的多数决定输如的实例的类(或者说标签)。

算法流程

  1. 准备数据,对数据进行预处理
  2. 选用合适的数据结构存储训练数据和测试元组
  3. 设定参数,如k
  4. 维护一个大小为k的的按距离由大到小的优先级队列,用于存储最近邻训练元组。随机从训练元组中选取k个元组作为初始的最近邻元组,分别计算测试元组到这k个元组的距离,将训练元组标号和距离存入优先级队列
  5. 遍历训练元组集,计算当前训练元组与测试元组的距离,将所得距离L 与优先级队列中的最大距离Lmax
  6. 进行比较。若L>=Lmax,则舍弃该元组,遍历下一个元组。若L < Lmax,删除优先级队列中最大距离的元组,将当前训练元组存入优先级队列。
  7. 遍历完毕,计算优先级队列中k 个元组的多数类,并将其作为测试元组的类别。
  8. 测试元组集测试完毕后计算误差率,继续设定不同的k值重新进行训练,最后取误差率最小的k 值。

k-NN算法细节

  1. 注意属性在向量空间的规范化、规范化公式和聚类[0,1]规范化公式一样,即归一化数据。
  2. 比较的属性如果是2元变量或者分类变量,设定好差值。(注意最大差区间仍要在规范化空间内部)。
  3. 确实属性值的处理:

①分类(2元变量)变量直接设置差值为规范化空间的最大值。

②数值类型属性 若:Ⅰ:2个元组对应属性均缺失,差值直接为规范化空间最大值。Ⅱ:如果只有一个缺失,另一个取值为V,则距离差值为|1-V| 和|0-V| 的最大值 (即Max(|规范化空间的上下界-V|))

  1. 确定K的值:通过对样本的实验(多次和人工结合),取出误差最小的分类结果。
  2. 对噪声的处理:在训练的过程中对噪声的元组直接Kill掉。

k-NN算法优缺点

优点:

  • 简单有效,容易理解,计算时间和空间线性于训练集的规模
  • 重新训练的代价较低(类别体系的变化和训练集的变化,在WEB环境和电子商务应用中是常见的)

缺点:

  • 输出的可理解性不够强(无法给出像决策树那样的规则),类别评分不规格(不像概率评分)
  • 计算量大,因为对每一个待分类点都要计算它到全体已知样本点的距离才能得到K个最邻近点。此问题可用KD Tree 或者Ball Tree进行优化
  • 样本不平衡时,如某一类一家独大时,新样本点的K个邻近中该类占据多数,可以采用加权方法,样本距离小的邻居权值大来加以改进

Reference

  • 统计学习方法–李航
  • 机器学习实战
  • 沈超博客