KNN（k近邻详解）

KNN&＃xff08;k近邻详解&＃xff09;

详细链接一
详细链接二

一句话说明白KNN算法原理

下面我们只讲关于分类的KNN&＃xff0c;回归的不讲。

其实很简单&＃xff0c;就是计算你要预测的点的周围最近的K个点&＃xff0c;然后取这k个点中最多的类定义为你要预测的这个点所属的类型。如下图所示&＃xff0c;比如说&＃xff1a;
有两类不同的样本数据&＃xff0c;分别用蓝色的小正方形和红色的小三角形表示&＃xff0c;而图正中间的那个绿色的圆所标示的数据则是待分类的数据。这也就是我们的目的&＃xff0c;来了一个新的数据点&＃xff0c;我要得到它的类别是什么&＃xff1f;好的&＃xff0c;下面我们根据k近邻的思想来给绿色圆点进行分类。
1、如果K&＃61;3&＃xff0c;绿色圆点的最邻近的3个点是2个红色小三角形和1个蓝色小正方形&＃xff0c;少数从属于多数&＃xff0c;基于统计的方法&＃xff0c;判定绿色的这个待分类点属于红色的三角形一类。
2、如果K&＃61;5&＃xff0c;绿色圆点的最邻近的5个邻居是2个红色三角形和3个蓝色的正方形&＃xff0c;还是少数从属于多数&＃xff0c;基于统计的方法&＃xff0c;判定绿色的这个待分类点属于蓝色的正方形一类。

这就是KNN算法&＃xff0c;很简单吧。那我们就来详细解决上述算法中的一些遗留问题。

1、最近的距离度量怎么计算&＃xff1f;

有下面这几种计算方式&＃xff1a;

但是光有这些还不够&＃xff0c;还必须有特征归一化。你比如说&＃xff1a;

首先举例如下&＃xff0c;我用一个人身高(cm)与脚码&＃xff08;尺码&＃xff09;大小来作为特征值&＃xff0c;类别为男性或者女性。我们现在如果有5个训练样本&＃xff0c;分布如下&＃xff1a;

A [(179,42),男] B [(178,43),男] C [(165,36)女] D [(177,42),男] E [(160,35),女]

通过上述训练样本&＃xff0c;我们看出问题了吗&＃xff1f;

很容易看到第一维身高特征是第二维脚码特征的4倍左右&＃xff0c;那么在进行距离度量的时候&＃xff0c;我们就会偏向于第一维特征。这样造成俩个特征并不是等价重要的&＃xff0c;最终可能会导致距离计算错误&＃xff0c;从而导致预测错误。口说无凭&＃xff0c;举例如下&＃xff1a;

现在我来了一个测试样本 F(167,43)&＃xff0c;让我们来预测他是男性还是女性&＃xff0c;我们采取k&＃61;3来预测。

下面我们用欧式距离分别算出F离训练样本的欧式距离&＃xff0c;然后选取最近的3个&＃xff0c;多数类别就是我们最终的结果&＃xff0c;计算如下&＃xff1a;

由计算可以得到&＃xff0c;最近的前三个分别是C,D,E三个样本&＃xff0c;那么由C,E为女性&＃xff0c;D为男性&＃xff0c;女性多于男性得到我们要预测的结果为女性。

这样问题就来了&＃xff0c;一个女性的脚43码的可能性&＃xff0c;远远小于男性脚43码的可能性&＃xff0c;那么为什么算法还是会预测F为女性呢&＃xff1f;那是因为由于各个特征量纲的不同&＃xff0c;在这里导致了身高的重要性已经远远大于脚码了&＃xff0c;这是不客观的。所以我们应该让每个特征都是同等重要的&＃xff01;这也是我们要归一化的原因&＃xff01;
归一化公式如下&＃xff1a;

2、K值的选取

还有一个最大的问题&＃xff0c;K怎么选&＃xff1f;&＃xff1f;&＃xff1f;
选的太小的话&＃xff0c;会造成过拟合&＃xff0c;选的太大的话&＃xff0c;会造成模型太简单&＃xff0c;无法起到分类的作用。

那么我们一般怎么选取呢&＃xff1f;李航博士书上讲到&＃xff0c;我们一般选取一个较小的数值&＃xff0c;通常采取 交叉验证法来选取最优的k值。&＃xff08;也就是说&＃xff0c;选取k值很重要的关键是实验调参&＃xff0c;类似于神经网络选取多少层这种&＃xff0c;通过调整超参数来得到一个较好的结果&＃xff09;

简单地说就是调超参吧。

3、K近邻算法的实现&＃xff1a;KD树的原理讲解

kd 树的结构

kd树是一个二叉树结构&＃xff0c;它的每一个节点记载了【特征坐标&＃xff0c;切分轴&＃xff0c;指向左枝的指针&＃xff0c;指向右枝的指针】。

其中&＃xff0c;特征坐标是线性空间 Rn 中的一个点 (x1,x2,…,xn)切分轴由一个整数 r 表示&＃xff0c;这里 1≤r≤n&＃xff0c;是我们在 n 维空间中沿第 rr维进行一次分割。节点的左枝和右枝分别都是 kd 树&＃xff0c;并且满足&＃xff1a;如果 y 是左枝的一个特征坐标&＃xff0c;那么 yr≤xr&＃xff08;左分支结点&＃xff09;&＃xff1b;并且如果 z 是右枝的一个特征坐标&＃xff0c;那么 zr≥xr&＃xff08;右分支结点&＃xff09;。

给定一个数据样本集 S⊆Rn 和切分轴 r&＃xff0c;以下递归算法将构建一个基于该数据集的 kd 树&＃xff0c;每一次循环制作一个节点&＃xff1a;
−− 如果 |S|&＃61;1&＃xff0c;记录 S 中唯一的一个点为当前节点的特征数据&＃xff0c;并且不设左枝和右枝。&＃xff08;|S| 指集合 S 中元素的数量&＃xff09;
−− 如果 |S|>1

1、将 S 内所有点按照第 r 个坐标的大小进行排序&＃xff1b;
2、选出该排列后的中位元素&＃xff08;如果一共有偶数个元素&＃xff0c;则选择中位左边或右边的元素&＃xff0c;左随便哪一个都无所谓&＃xff09;&＃xff0c;作为当前节点的特征坐标&＃xff0c;并且记录切分轴 r&＃xff1b;
3、将 SL设为在 S 中所有排列在中位元素之前的元素&＃xff1b; SR 设为在 S 中所有排列在中位元素后的元素&＃xff1b;
4、当前节点的左枝设为以 SL 为数据集并且 r 为切分轴制作出的 kd 树&＃xff1b;当前节点的右枝设为以 SR 为数据集并且 r为切分轴制作出的 kd 树。再设 r←(r&＃43;1)modn。&＃xff08;这里&＃xff0c;我们想轮流沿着每一个维度进行分割&＃xff1b;modn 是因为一共有 n 个维度&＃xff0c;在沿着最后一个维度进行分割之后再重新回到第一个维度。&＃xff09;

如果没看懂很正常&＃xff0c;简单地来说&＃xff0c;先将你的训练数据按照第一维排序&＃xff0c;然后取中位数的那个数据x&＃xff0c;根据x把数据集分为左右两部分&＃xff0c;然后再分别对左右两部分按照第二维取中位数分割&＃xff0c;就这样迭代下去&＃xff0c;直到最后一维。

如果你还是不懂&＃xff0c;看一个例子。

给定一个二维空间的数据集&＃xff1a;

T &＃61; {&＃xff08;2,3&＃xff09;&＃xff0c;&＃xff08;5,4&＃xff09;&＃xff0c;&＃xff08;9,6&＃xff09;,&＃xff08;4,7&＃xff09;&＃xff0c;&＃xff08;8,1&＃xff09;&＃xff0c;&＃xff08;7,2&＃xff09;}&＃xff0c; 构造一个平衡kd树。

为了方便&＃xff0c;我这里进行编号A(2&＃xff0c;3)、B&＃xff08;5,4&＃xff09;、C&＃xff08;9,6&＃xff09;、D&＃xff08;4,7&＃xff09;、E&＃xff08;8,1&＃xff09;、F&＃xff08;7,2&＃xff09;

初始值r&＃61;0&＃xff0c;对应x轴。

首先先沿 x 坐标进行切分&＃xff0c;我们选出 x 坐标的中位点&＃xff0c;获取最根部节点的坐标&＃xff0c;对数据点x坐标进行排序得&＃xff1a;

A(2&＃xff0c;3)、D&＃xff08;4,7&＃xff09;、B&＃xff08;5,4&＃xff09;、F&＃xff08;7,2&＃xff09;、E&＃xff08;8,1&＃xff09;、C&＃xff08;9,6&＃xff09;

则我们得到中位点为B或者F&＃xff0c;我这里选择F作为我们的根结点&＃xff0c;并作出切分&＃xff08;并得到左右子树&＃xff09;&＃xff0c;如图&＃xff1a;

对应的树结构如下&＃xff1a;

根据算法&＃xff0c;此时r&＃61;r&＃43;1&＃61;1&＃xff0c;对应y轴&＃xff0c;此时对应算法|S|>1&＃xff0c;则我们分别递归的在F对应的左子树与右子树按y轴进行分类&＃xff0c;得到中位节点分别为B&＃xff0c;C点&＃xff0c;如图所示&＃xff1a;

对应树结构为&＃xff1a;

而到此时&＃xff0c;B的左孩子为A&＃xff0c;右孩子为D&＃xff0c;C的左孩子为E,均满足|S|&＃61;&＃61;1&＃xff0c;此时r &＃61; (r&＃43;1)mod2 &＃61; 0,又满足x轴排序&＃xff0c;对x轴划分&＃xff01;则如图所示&＃xff1a;

对应树结构如下&＃xff1a;

kd树的搜索
输入&＃xff1a;已构造的kd树&＃xff1b;目标点x&＃xff1b;

输出&＃xff1a;x的最近邻.

&＃xff08;1&＃xff09;在kd树中找出包含目标点x的叶结点&＃xff1a;从根结点出发&＃xff0c;递归地向下访问kd树&＃xff0c;若目标点x当前维的坐标小于切分点的坐标,则移动到左子节点&＃xff0c;否则移动到右子结点.直到子结点为叶结点位置.

&＃xff08;2&＃xff09;以此叶结点为“当前最近点”

&＃xff08;3&＃xff09;递归地向上回退&＃xff0c;在每个结点进行以下操作&＃xff1a;

&＃xff08;a&＃xff09;如果该结点保存的实例点比当前最近点距离目标点更近&＃xff0c;则以该实例点为“当前最近点”.

&＃xff08;b&＃xff09;当前最近点一定存在于该结点一个子结点对应的区域.检查该子结点的父结点的另一个子结点对应的区域是否有更近的点.具体地&＃xff0c;检查另一子结点对应的区域是否以目标点为球心、以目标点与“当前最近点”间为半径的超球体相交。

如果不相交&＃xff0c;向上回退.

&＃xff08;4&＃xff09;当回退到根结点时&＃xff0c;搜索结束。最后的“当前最近点”即为最近邻点.

看到这里是不是有点晕了&＃xff0c;哈哈&＃xff0c;不要怕&＃xff0c;下面通过例子&＃xff0c;一步一步走一遍上面所描述的算法过程&＃xff0c;化抽象为具体&＃xff01;

kd树最近邻搜索例题&＃xff1a;

给定一个二维空间的数据集&＃xff1a;

T &＃61; {&＃xff08;2,3&＃xff09;&＃xff0c;&＃xff08;5,4&＃xff09;&＃xff0c;&＃xff08;9,6&＃xff09;,&＃xff08;4,7&＃xff09;&＃xff0c;&＃xff08;8,1&＃xff09;&＃xff0c;&＃xff08;7,2&＃xff09;}&＃xff0c;输入目标实例为K(8.5,1),求K的最近邻。

首先我们由上面可以给出&＃xff0c;T的kd树对应如下&＃xff1a;

我们此时的K&＃xff08;8.5,1&＃xff09;&＃xff0c;根据算法第一步得&＃xff1a;第一层的x轴K点为8大于F点的7&＃xff0c;所以进入F&＃xff08;7,2&＃xff09;的右子树&＃xff0c;进入下面红色线条区域&＃xff1a;

到了第二层&＃xff0c;分割平面坐标为y轴&＃xff0c;K点y轴坐标为1&＃xff0c;小于C点y轴坐标6&＃xff0c;则继续向右走&＃xff0c;在下图红色线条区域内&＃xff1a;

则此时算法对应第&＃xff08;1&＃xff09;部分完成&＃xff0c;我们找到了叶子节点E&＃xff08;8,1&＃xff09;。

我们进行算法第&＃xff08;2&＃xff09;步&＃xff0c;把E&＃xff08;8,1&＃xff09;作为最近邻点。此时我们算一下KE之间的距离为0.5&＃xff08;便于后面步骤用到&＃xff09;.

然后进行算法第&＃xff08;3&＃xff09;步&＃xff0c;递归的往上回退&＃xff0c;每个结点进行相同步骤&＃xff0c;好&＃xff0c;我现在从E点回退到C点&＃xff0c;对应图片如下&＃xff1b;

此时对C点进行第&＃xff08;3&＃xff09;步的&＃xff08;a&＃xff09;操作&＃xff0c;判断一下KC距离与保存的最近邻距离&＃xff08;这时是KE&＃xff09;比较&＃xff0c;KC距离为点K&＃xff08;8.5,1&＃xff09;与点C&＃xff08;9,6&＃xff09;之间的距离√25.25>最近邻0.5&＃xff0c;于是不更新最近邻点。

然后对C点进行第&＃xff08;3&＃xff09;步的&＃xff08;b&＃xff09;操作&＃xff0c;判断一下当前最近邻的距离画一个圆是否与C点切割面相交&＃xff0c;如图所示&＃xff1a;

们很容易看到与C点切割面并没有相交&＃xff0c;于是执行由C点回退到它的父结点F点。如图&＃xff1a;

对F点进行&＃xff08;a&＃xff09;&＃xff0c;&＃xff08;b&＃xff09;操作&＃xff01;

进行&＃xff08;a&＃xff09;步骤&＃xff0c;判断FK的距离是否小于当前保存的最小值&＃xff0c;FK&＃61;√1.25>0.5,所以不改变最小距离

下面我们进行&＃xff08;b&＃xff09;步骤&＃xff0c;为了判断F点的另一半区域是否有更小的点&＃xff0c;判断一下当前最近邻的距离画一个圆是否与F点切割面相交&＃xff0c;如图所示&＃xff1a;

发现与任何分割线都没有交点&＃xff0c;那么执行算法最后一步&＃xff0c;此时F点已经是根结点&＃xff0c;无法进行回退&＃xff0c;那么我们可以得到我们保留的当前最短距离点E点就是我们要找的最近邻点&＃xff01;任务完成&＃xff0c;
并且根据算法流程&＃xff0c;我们并没有遍历所有数据点&＃xff0c;而是F点的左孩子根本没有遍历&＃xff0c;节省了时间&＃xff0c;但是并不是所有的kd树都能到达这样的效果。

总结

1.我们提出了k近邻算法&＃xff0c;算法的核心思想是&＃xff0c;即是给定一个训练数据集&＃xff0c;对新的输入实例&＃xff0c;在训练数据集中找到与该实例最邻近的K个实例&＃xff0c;这K个实例的多数属于某个类&＃xff0c;就把该输入实例分类到这个类中。更通俗说一遍算法的过程&＃xff0c;来了一个新的输入实例&＃xff0c;我们算出该实例与每一个训练点的距离&＃xff08;这里的复杂度为0(n)比较大&＃xff0c;所以引出了下文的kd树等结构&＃xff09;&＃xff0c;然后找到前k个&＃xff0c;这k个哪个类别数最多&＃xff0c;我们就判断新的输入实例就是哪类&＃xff01;

2.与该实例最近邻的k个实例&＃xff0c;这个最近邻的定义是通过不同距离函数来定义&＃xff0c;我们最常用的是欧式距离。

3.为了保证每个特征同等重要性&＃xff0c;我们这里对每个特征进行归一化。

4.k值的选取&＃xff0c;既不能太大&＃xff0c;也不能太小&＃xff0c;何值为最好&＃xff0c;需要实验调整参数确定&＃xff01;
5、kd树的建立以及搜索。

K近邻的优缺点

优点&＃xff1a;

1.KNN分类方法是一种非参数的分类技术&＃xff0c;简单直观&＃xff0c;易于实现&＃xff01;只要让预测点分别和训练数据求距离&＃xff0c;挑选前k个即可&＃xff0c;非常简单直观。

2.KNN是一种在线技术&＃xff0c;新数据可以直接加入数据集而不必进行重新训练

缺点及改进&＃xff1a;

1.当样本不平衡时&＃xff0c;比如一个类的样本容量很大&＃xff0c;其他类的样本容量很小&＃xff0c;输入一个样本的时候&＃xff0c;K个邻近值大多数都是大样本容量的那个类&＃xff0c;这时可能会导致分类错误。

改进方法&＃xff1a;对K邻近点进行加权&＃xff0c;也就是距离近的权值大&＃xff0c;距离远的点权值小。

2.计算量较大&＃xff0c;每个待分类的样本都要计算它到全部点的距离&＃xff0c;根据距离排序才能求得K个临近点。

改进方法&＃xff1a;先对已知样本带你进行裁剪&＃xff0c;事先去除分类作用不大的样本&＃xff0c;采取kd树以及其它高级搜索方法BBF等算法减少搜索时间。