数据挖掘十大算法之k近邻算法。

k近邻简述

概述

简单地说，k近邻算法采用测量不同特征值之间的距离的方法进行预测。

工作机制

给定测试样本，基于某种距离量度找出训练集中与其最靠近的k个训练样本，然后基于这k个“邻居”的信息来进行预测。（近朱者赤，近墨者黑）

懒惰学习

k近邻学习是没有显式的训练过程。它是“懒惰学习”（lazy learning）的著名代表，此类学习技术在训练阶段仅仅是把样本保存起来，训练时间开销为零，待收到测试样本后再进行处理；相应的，那些在训练阶段就对样本进行学习处理的方法，称为“急切学习”（eager learning）。

例图

k近邻算法例子。测试样本（绿色圆形）应归入要么是第一类的蓝色方形或是第二类的红色三角形。如果k=3（实线圆圈）它被分配给第二类，因为有2个三角形和只有1个正方形在内侧圆圈之内。如果k=5（虚线圆圈）它被分配到第一类（3个正方形与2个三角形在外侧圆圈之内）。

k近邻模型

k值的选择，距离度量及分类决策规则是k近邻法的三个基本要素。

距离度量:$L_{p}$距离

设特征空间向量$\chi$是n维实数向量空间$R^{n}$，$x_{i}$，$x_{j}$$\in $ $\chi$，$x_{i}=\left(x^{\left( 1\right) }_{i,}x^{\left( 2\right) }_{i},\ldots x^{\left( n\right) }_{i}\right)^{T}$,$ x_{j}=\left(x^{\left( 1\right) }_{j,}x^{\left( 2\right) }_{j},\ldots x^{\left( n\right) }_{j}\right)^{T}$。$x_{i},x_{j}$的$L_{p}$距离定义为：

$$L_{p}\left( x_{i},x_{j}\right)=\left( \sum ^{n}_{l=1}\left| x^{\left( l\right) }_{i}-x^{\left( l\right) }_{j}\right| ^{p}\right) ^{\dfrac {1}{p}}$$

当p=2时，称为欧氏距离(Euclidean distance)，即

$$L_{2}\left( x_{i},x_{j}\right)=\left( \sum ^{n}_{l=1}\left| x^{\left( l\right) }_{i}-x^{\left( l\right) }_{j}\right| ^{2}\right) ^{\dfrac {1}{2}}$$

当p=1时，称为曼哈顿距离，即

$$L_{1}\left( x_{i},x_{j}\right)=\sum ^{n}_{l=1}\left| x^{\left( l\right) }_{i}-x^{\left( l\right) }_{j}\right|$$

当p=$\infty$时，它是各个坐标距离的最大值，即

$$L_{\infty}\left( x_{i},x_{j}\right)=\max _{l}\left| x^{\left( l\right) }_{i}-x^{\left( l\right) }_{j}\right|$$

p取不同值时与原点$L_{p}$距离为1的点的图形

k值的选择

k值的减小就意味着整体模型变得复杂，容易发生过拟合。

k值的增大就意味着整体模型变得简单。

在应用中，k值一般取一个较小的数值，通常采用交叉验证法来选取最优的k值。等一个后续详解更新

决策分类规则

k近邻中的分类决策往往是多数表决。

多数表决规则有以下解释：如果分类的损失函数为0-1损失函数，分类函数为

$$f:R^{n}\rightarrow \left\{ c_{1},c_{2},\ldots ,c_{k}\right\}$$

那么误分类的概率是：

$$P\left( Y\neq f\left( x\right) \right) =1-P\left( Y= f\left( x\right) \right)$$

对给定的实例$x \in \chi$，其最近邻的k个训练实例点构成集合$N_{k}\left( x\right)$，如果涵盖$N_{k}\left( x\right)$的区域的类别是$c_{j}$，那么误分类率是

$$\dfrac {1}{k}\sum _{x_{i}\in N_{k}\left( x\right) }I\left( y_{i}\neq c_{j}\right) = 1 - dfrac {1}{k}\sum _{x_{i}\in N_{k}\left( x\right) }I\left( y_{i}= c_{j}\right)$$

要使误分类率最小即经验风险最小，就要使$\sum _{x_{i}\in N_{k}\left( x\right) }I\left( y_{i}= c_{j}\right)$最大，所以多数表决规则等价于经验风险最小化。

k近邻实现

kNN的一大缺点需要存储全部训练样本，以及繁重的距离计算量。

改进的方案有两个

• 对样本集进行组织与整理，分群分层，尽可能将计算压缩到在接近测试样本邻域的小范围内，避免盲目地与训练样本集中每个样本进行距离计算。

• 在原有样本集中挑选出对分类计算有效的样说本，使样本总数合理地减少，以同时达到既减少计算量，又减少存储量的双重效果。

kd树

kd树是k-dimension tree的缩写，是对数据点在k维空间（如二维(x，y)，三维(x，y，z)，k维(x，y，z..)）中划分的一种数据结构，主要应用于多维空间关键数据的搜索（如：范围搜索和最近邻搜索）。本质上说，kd-树就是一种平衡二叉树。

创建kd树

有很多种方法可以选择轴垂直分区面（ axis-aligned splitting planes ），所以有很多种创建k-d树的方法。 最典型的方法如下：

• 随着树的深度轮流选择轴当作分区面。（例如：在三维空间中根节点是 x 轴垂直分区面，其子节点皆为 y 轴垂直分区面，其孙节点皆为 z 轴垂直分区面，其曾孙节点则皆为 x 轴垂直分区面，依此类推。）
• 点由垂直分区面之轴座标的中位数区分并放入子树

这个方法产生一个平衡的k-d树。每个叶节点的高度都十分接近。然而，平衡的树不一定对每个应用都是最佳的。

例：

假设有6个二维数据点{（2,3），（5,4），（9,6），（4,7），（8,1），（7,2）}，数据点位于二维空间内，构造一个平衡kd树。

搜索kd树

k-d树最邻近搜索的过程如下：

• 从根节点开始，递归的往下移。往左还是往右的决定方法与插入元素的方法一样(如果输入点在分区面的左边则进入左子节点，在右边则进入右子节点)。
• 一旦移动到叶节点，将该节点当作”目前最佳点”。
• 解开递归，并对每个经过的节点运行下列步骤：
  • 如果目前所在点比目前最佳点更靠近输入点，则将其变为目前最佳点。
  • 检查另一边子树有没有更近的点，如果有则从该节点往下找
• 当根节点搜索完毕后完成最邻近搜索

例：

查询（2，4.5）

通过二叉搜索，顺着搜索路径很快就能找到最邻近的叶子节点（4,7），首先假设（4,7）为当前最近邻点，计算其与目标查找点的距离为3.202。

回溯到（5,4），计算其与查找点之间的距离为3.041，小于3.202，所以“当前最近邻点”变成（5,4）。以目标点（2,4.5）为圆心，以目标点（2,4.5）到“当前最近邻点”（5,4）的距离（即3.041）为半径作圆，如下图左所示。可见该圆和y = 4超平面相交，所以需要进入（5,4）左子空间进行查找，即回溯至（2,3）叶子节点，（2,3）距离（2,4.5）比（5,4）要近，所以“当前最近邻点”更新为（2,3），最近距离更新为1.5。回溯至（7,2），以（2,4.5）为圆心1.5为半径作圆，并不和x = 7分割超平面交割，如下图右所示。至此，搜索路径回溯完。返回最近邻点（2,3），最近距离1.5。

压缩近邻算法

利用现有样本集，逐渐生成一个新的样本集，使该样本集在保留最少量样本的条件下，仍能对原有样本的全部用最近邻法正确分类，那么该样本集也就能对待识别样本进行分类，并保持正常识别率。

算法实现

首先定义两个存储器，一个用来存放即将生成的样本集，称为Store；另一存储器则存放原样本集，称为Grabbag。其算法是：

1. 初始化。Store是空集，原样本集存入Grabbag；从Grabbag中任意选择一样本放入Store中作为新样本集的第一个样本。

2. 样本集生成。在Grabbag中取出第i个样本用Store中的当前样本集按最近邻法分类。若分类错误，则将该样本从Grabbag转入Store中，若分类正确，则将该样本放回Grabbag中。

3. 结束过程。若Grabbag中所有样本在执行第二步时没有发生转入Store的现象，或Grabbag已成空集，则算法终止，否则转入第二步。

参考：

https://my.oschina.net/u/1412321/blog/194174
https://blog.csdn.net/misaiya1/article/details/78704113

《统计学习方法》 李航

《机器学习》 周志华