机器学习之 KNN (近邻)算法

算法简介

KNN 算法的英文全程叫做 (K Near Neighbor )也就是 K 个最近的邻居。这是一种分类算法。属于监督式学习。

简单说,KNN 算法就是在预测一个新值 x 时,根据它距离最近的 K 个点是什么类型来判断 x 是属于哪个类别的。()

所以 在这种算法中,K 的数量就至关重要了。如果 K 过少,就意味着整体模型变的复杂(特征空间过多,模型项也越多)。容易发生过拟合。而 K 值过大,也会 造成没有明显分类,没有很好的区分效果。

算法概念

我们已经知道了 KNN 的大概思路。下面来举个例子。

比如下图,在 K=3 时,我们新加了一个绿点,在 3 这个范围内,蓝三角多于红圆点。所以新加入进来的就被归为 蓝三角 这个类别。

这种分类模式 因 K 的不同,产生的结果也不同。比如,当 K 等于 5 时,就产生了如下情况。

此时,新加入的点就变成了 红圆点。

如此来说,此算法至关重要的因素就有两个 ,K 值选取,以及距离计算。

那么如何确定 K 值

那么如何来确定 K 值大小呢? 答案就是 试。通过交叉验证,从比较小的值开始,逐步增大,一个个测试。然后计算验证集的方差,这样最终找到比较合适的 K 值。(方差小,说明结果误差范围越小,越稳定,一定程度上也可以反应错误率)

如上图,就是一个训练结果。我们可以看出,在 K=10 左右的时候获取到的值最大。

如何计算距离

距离只是一个空间的度量,没有什么固定的方式,只要能反映出来两个 “点”之间的距离就行。常用的也就是 曼哈顿距离/L1范数,和欧氏距离/L2范数(什么是范数?

欧氏距离:d(x,y) = \sqrt{\sum_{k=1}^n(x_k-y_k)^2}
曼哈顿距离:d(x,y) = \sqrt{\sum_{k=1}^n|x_k-y_k|}

KNN算法的核心:kd树

假设我们已经给定了 K ,如何快速的找到 距离预测实例最近的 K个邻居?

初学者一般就直接使用暴力破解方法了,因为K 值一般不会取特别大,而且在特征空间维度不高,样本容量小的时候暴力破解也可行。反之则计算过程非常耗时。

kd 树 (K – dimension tree)是一种对 K 维空间中的实例点进行存储,以便后面对其快速检索的树形数据结构。这是一种二叉树,相当于对 K 维空间的一个划分。其每一个节点都对应了一个 K 维的超巨型区域。这样利用 KDTree 可以省去大部分数据点的搜索,从而减少搜索的计算量。

比如以二维为例,就是把坐标轴上的数字,不断的以二分法划开,这样在找指定值时,可以用二分法快速查找。(可以理解为空间二分)

参考文档:
https://www.jianshu.com/p/29b9dd354793
https://blog.csdn.net/hajk2017/article/details/82862788
https://blog.csdn.net/sinat_30353259/article/details/80901746

未经允许不得转载:书生吴小帅 » 机器学习之 KNN (近邻)算法

赞 (7)