k近邻法/k-NN

k近邻法可以算是机器学习算法中最古老的方法之一,它在1968年被 Cover 和 Hart 提出。除此之外,它也是最容易描述和理解的机器学习算法之一。

算法释义

给定一个已标注输出的训练数据集,对于新的输入实例 x,在训练集中寻找 k 个与其最近邻的实例,根据这 k 个训练实例的类别和分类决策规则对实例 x 做分类。

算法步骤:

输入:训练数据集 T ,输入实例 x输出:实例 x 所属的类 y(1) 找近邻:根据给定的距离度量,在训练集 T 中寻找与实例 x 最近的 k 个近邻(2) 做分类:根据分类决策规则决定 x 的类别 y

重要概念

从 k-NN 的释义中不难看出,该模型主要由三个基本要素构成:用于描述距离远近的距离度量,k 值选择分类决策规则。换句话说,只要k-NN模型中的这三个要素确定了,对于固定的训练集,任何一个新的输入实例,它所属的类唯一地确定。

距离度量

顾名思义,就是指特征空间中两个实例点相似程度的反应,k-NN 中一般使用欧氏距离,但是使用距离度量也是可行的,比如说更一般的 Lp 距离:$$ Lp(xi, xj) = \left(\sum^ { | xi^{(l)} - xj^{(l)} |^p } \right)^\frac $$

这里当 p = 1 时,称之为曼哈顿距离,即:$$ L1(xi, xj) = \sum^ { | xi^{(l)} - xj^{(l)} | } $$

当 p = 2 时,称之为欧氏距离,即:$$ L2(xi, xj) = \left(\sum^ { | xi^{(l)} - xj^{(l)} |^2 } \right)^\frac $$

当 p = ∞ 时,它是各个维度上距离的最大值,即:$$ L∞(xi, xj) = \maxl { | xi^{(l)} - xj^{(l)} | } $$

P.S. 距离度量的选择在聚类算法中更为重要,因此之后还将重点介绍距离度量。

k 值选择

k 值的选择对 k-NN 算法的结果影响很大,我们设想两个极端:1. 当 k = N (训练集样本总数) 时,这时无论输入实例是什么,它们得到的近邻是一样的,所以都会被归为同一个类,这时模型过于简单,很容易造成欠拟合,也就是 Ein 会很大;2. 当 k = 1 时(称作最近邻算法),这时特征空间的划分会很复杂,因为对于任何一个实输入实例,它的分类结果都只和与它最近的那个训练实例点有关,显然,过于复杂的模型会造成 VC 维的增大,从而很容易导致过拟合。那么如何选择 k 这个超参数呢?经验上,一般先取一个较小的 k 值,然后通过交叉验证法来选取合适的 k 值。

分类决策规则

k-NN 中运用最广的分类决策规则是多数表决法(等价于经验风险最小化),即由输入实例的 k 个近邻的训练实例中的多数类决定输入实例的类:$$ y = arg \max\sum,i = 1,2,...,N; j = 1,2,...,N $$

经典实现 —— kd 树

从 k-NN 的算法释义中不难看出,有别于其他的机器学习算法,k-NN 算法不存在明显的“学习”过程,其在训练阶段仅仅是把训练样本保存起来,训练开销为零,但其在判别阶段由于需要计算输入实例和每个样本的距离,因此计算开销很大,这种机器学习方式称作懒惰学习。当训练集很大时,这种方法的计算是非常耗时的,这显然是不可行的,因此为了减少计算距离的次数,可以考虑在存储阶段对训练集进行特殊的处理,从而提高 k 近邻的搜索效率,这其中就有一种比较经典的方法,被称作 kd 树。

构造 kd 树

pass

搜索 kd 树

pass

参考文献

《统计学习方法》,李航《机器学习》,周志华

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180821G1WB7V00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

同媒体快讯

扫码关注云+社区

领取腾讯云代金券