机器学习｜KNN

之前一段时间我们了解到的算法中，可以说是一个比一个复杂，本文呢，我们不再增加难度，来说一个最基础、最简单的监督学习算法KNN。

KNN原理

我们给定一个数据集，对于一个新来的样本，我们在数据集中找到距离该样本最近的K个样本，在这K个样本中，某一类出现的次数最多我们就把这个样本分到这个类别中。

举一个例子：

如图所示，红色的三角和蓝色的方块为我们原有的数据集，绿色的圆即为一个新来到的样本，事先我们并不知道它属于某一类，我们来尝试两种不同的K值下的分类方法：

K=3当我们选取K=3时，很明显距离绿色圆最近的三个样本为两个红色三角和一个蓝色方块，按照KNN的分类原则我们就可以将绿色圆分为红色三角一类。

K=5当我们选取K=5时，很明显距离绿色圆最近的五个样本为两个红色三角和一个蓝色方块，同理我们就可以将绿色园分为蓝色方块一类。

也就是这样

K值的选取	蓝色方块个数	红色三角个数	绿色圆分类
K=3	■	▲▲	▲
K=5	■■■	▲▲	■

根据这个例子我们就能总结出KNN算法的基本步骤：

（1）计算数据集中每个点到测试数据的距离d(i)；

（2）将算得的距离d(i)进行从小到大的排序；

（3）根据我们设定的K值选取排序后的前K个点；

（4）确定选取到的K个点中每一类别出现的频率；

（5）将出现频率最高的一类作为测试样本的预测分类结果。

从这个简单的例子可以看出，当我们选取不同的K值时会有不同的结果，那我们应该如何去选择K值，又应该如何去计算数据集中每个样本到新样本之间的距离呢？下面会给出解答。

KNN距离的度量

在我们数学的学习中关于度量的方式有很多种，我们在了解KNN所需要的距离度量方式的同时，也来了解一下其它的距离度量方式。

闵可夫斯基距离

闵可夫斯基距离是衡量数值点之间距离的一种非常常见的方法，假设数值点P和Q坐标如下：

K值的选择

KNN中如何进行K值的选择是一个让人头大的问题，选的大了小了都会出现一定的问题，我们先来看一下下面的例子产生的问题：

不同K值出现的问题

和我们在讲第一个例子的时候同理，同样是将绿色圆作为测试样本，我们分别取K=1，K=7，K=N进行训练。

K值的选择	蓝色方块个数	红色三角个数	绿色圆的分类
K=1	■	None	■
K=7	■	▲▲▲▲▲▲	▲
K=N	■■■■■■■	▲▲▲▲▲▲	■

很显然当K=1的时候，我们使用了一个复杂的模型，该模型下我们很容易的学习到了训练样本中的噪声，从而导致了模型过拟合现象的出现；将K值增大，当K=7时，可以看出我们得到了一个相对正确的分类；再继续增大K值为N(训练集所有样本的个数)，这种做法会导致我们将模型设计的过于简单，从而导致预测结果发生错误，由此可见选择一个合适的K值是多么的重要。

如果选择较小的K值，就相当于用较小的领域中的训练实例进行预测，“学习”近似误差会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是“学习”的估计误差会增大，换句话说，K值的减小就意味着整体模型变得复杂，容易发生过拟合；

如果选择较大的K值，就相当于用较大领域中的训练实例进行预测，其优点是可以减少学习的估计误差，但缺点是学习的近似误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，且K值的增大就意味着整体的模型变得简单。

K=N，此时无论输入实例是什么，都只是简单的预测它属于在训练实例中最多的类，模型过于简单，忽略了训练实例中大量有用信息。

在实际应用中，K值一般取一个比较小的数值，例如采用交叉验证法（简单来说，就是一部分样本做训练集，一部分做测试集）来选择最优的K值。

交叉验证选择K值

在进行K值选择的时候，我们通过经验去找当然是没有问题的，但是对于没有经验的人来说，可以使用交叉验证的方法去找到一个最佳的K值，简单的说交叉验证法就是把我们的数据分为n份，每次拿出其中的1份当作测试集，其它的当作训练集来进行n次训练，最终对这n次训练的得分进行平均。我们选择K值的做法就是给定一段K的范围，在这个范围内对于每一个K值都进行一次交叉验证，最终我们在K值取的比较小的条件下去选择得分最高的的就可以了。下面给出一段代码实现：

代码语言：javascript复制

from __future__ import print_function
from sklearn.datasets import load_iris
from sklearn.model_selection import cross_val_score
import matplotlib.pyplot as plt
from sklearn.neighbors import KNeighborsClassifier

iris = load_iris()
x = iris.data
y = iris.target
k_range = range(1, 31)
k_score = []
for k in k_range:
    # n_neighbors:KNN算法中K的取值
    knn = KNeighborsClassifier(n_neighbors=k)
    # cv：选择每次测试折数  accuracy：评价指标是准确度,可以省略使用默认值
    score = cross_val_score(knn, x, y, cv=10, scoring='accuracy')
    k_score.append(score.mean())

plt.plot(k_range, k_score)
plt.xlabel("Value of k for KNN")
plt.ylabel("accuracy")
plt.show()

从图像中我们就可以看出，当K取13的时候就能达到一个很高的得分了，此时我们选择K=13就可以了。

KD树

KD树是一种对K维空间中的实例点进行存储以便对其进行快速检索的树形结构。KD树是二叉树，表示对K维空间进行划分，构造KD树相当于不断地用垂直于坐标轴的超平面将K维空间划分，构成一些列的K维超矩形区域，KD树的每个节点对应于一个K维超矩形区域。

KD树的构建过程举例

给定二维空间的数据集：T={(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)},构建一个KD树。

（1）找到划分的特征。6个数据点在x,y维度上的数据方差分别为6.97，5.37，所以X轴上方差更大，用第一维特征建树。

（2）确定划分点(7,2)。根据X维上的值将数据排序，6个数据的中值（奇数个数据的时候为中值，偶数个数据的时候为中值向下取存在的整数）为7，所以划分点的数据是(7,2),此时节点的分割超平面就是通过该点并且垂直于X轴，即：直线X=7。

（3）确定左子空间和右子空间。直线X=7将空间划分为左右：左子空间[(2,3),(5,4),(4,7)]，右子空间[(9,6),(8,1)]。

（4）重复上述方法继续划分，直到不能划分为止，得到KD树。

最终得到的KD树的结果如下：

特征空间的划分如下：

我们构建KD树的目的是为了使用KD树进行最近邻搜索，搜索的过程如下：

在KD树中找出包含目标点x的叶结点：从根结点出发，递归地向下访问kd树。若目标点x当前维度的坐标小于且分点的坐标，则移动到左子结点，否则移动到右子结点。直到子结点为叶子结点为止。
以此叶结点为“当前最近点”。
递归地向上回退，在每个结点进行以下操作：

如果该结点保存的实例点比当前最近点距离目标点更近，则以该实例点为“当前最近点”。
当前最近点一定存在于该结点的一个子结点的对应区域，检查该子结点的父结点的另一子结点对应的区域是否有更近的点。具体的，检查另一子结点对应的区域是否与目标点为球心，以目标点与“当前最近点”间的距离为半径的球体相交。
如果相交，可能在另一个子结点对应的区域内存在距目标点更近的点，移动到另一个子结点。接着递归进行最近邻搜索。
如果不相交，向上回退。

当回退到根结点时，搜索结束。最后的“当前最近点”即为x的最近邻点。

knn

0 人点赞