调参——得到更好的 kNN 模型

作者 | 苏克1900 ，Python爱好者。

摘要：介绍 kNN 模型的几个重要的超参数。

上一篇文章我们说到了 kNN 模型中的超参数。简而言之， 超参数就是在模型运行前就要先确定的参数。 比如指定的 k 个近邻值 k 就是一个超参数。为什幺需要超参数呢，是因为使用不同的超参数就会建立不同的 kNN 模型最终也会得到不同的预测结果，我们尽可能想预测地更准确些，所以就需要尝试不同的超参数得到最好的模型。

说到超参数，还需要知道一个概念「 模型参数 」二者区别是：

超参数是在模型运行前确定的

模型参数是在算法运行过程自己学习的参数

kNN 是最简单的机器学习算法，模型中只有超参数没有模型参数，之后我们会陆续介绍的线性回归、逻辑回归等算法有模型参数，模型也会更加复杂。

kNN 模型的超参数有许多，可以在 sklearn 官网中找到，这里介绍几个最重要的。

https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KNeighborsClassifier.html

第一个超参数：algorithm

algorithm 即算法，意思就是建立 kNN 模型时采用什幺算法去搜索最近的 k 个点，有四个选项：

brute（暴力搜索）

kd_tree（KD树）

ball_tree（球树）

auto（默认值，自动选择上面三种速度最快的）

我们之前建立模型时没有设置这个参数，模型默认使用了 auto 方法，不过还是有必要了解一下这几种方法的区别。

首先，我们知道 KNN 模型的核心思想是计算大量样本点之间的距离。

第一种算法 brute （ 暴力搜索 ）。意思就是计算预测样本和 全部训练集样本 的距离，最后筛选出前 K 个最近的样本，这种方法很蛮力，所以叫暴力搜索。当样本和特征数量很大的时候，每计算一个样本距离就要遍历一遍训练集样本， 很费时间效率低下 。有什幺方法能够做到无需遍历全部训练集就可以快速找到需要的 k 个近邻点呢？这就要用到 KD 树和球树算法。

第二种算法 KD 树 （K-dimension tree缩写）。简单来说 KD 树是一种「二叉树」结构，就是把整个空间划分为特定的几个子空间，然后在合适的子空间中去搜索待预测的样本点。采用这种方法不用遍历全部样本就可以快速找到最近的 K 个点，速度比暴力搜索快很多（稍后会用实例对比一下）。至于什幺是二叉树，这就涉及到数据结构的知识，稍微有些复杂，就目前来说暂时不用深入了解，sklearn 中可以直接调用 KD 树，很方便。之后会单独介绍二叉树和 KD 树，再来手写 KD 树的 Python 代码。

目前只需要知道， 什幺样的数据集适合使用 KD 树算法

假设数据集样本数为 m，特征数为 n，则当 样本数量 m 大于 2 的 n 次方时，用 KD 树算法搜索效果会比较好 。比如适合 1000 个样本且特征数不超过 10 个（2 的 10 次方为 1024）的数据集。一旦特征过多，KD 树的搜索效率就会大幅下降，最终变得和暴力搜索差不多。通常来说 KD 树适用维数不超过 20 维的数据集，超过这个维数可以用球树这种算法。

第三种算法是 球树 （Ball tree）。对于一些分布不均匀的数据集，KD 树算法搜索效率并不好，为了优化就产生了球树这种算法。同样的，暂时先不用具体深入了解这种算法。

下面，我们制造一个分类数据集，使用不同的算法来直观感受一下各自算法的运行速度。

使用 datasets.make_classification 这种方法可以创建随机的分类数据集。第一个数据集是样本数 m 大于样本 2 的 n 次方，依次建立 kNN 模型并计算运行时间：

可见当数据集样本数量 m > 2 的 n  次方时，kd_tree 和 ball_tree 速度比 brute 暴力搜索快了一个量级，auto 采用其中最快的算法。

第二个数据集是样本数 m 小于样本 2 的 n 次方时，各：

当数据集样本数量 m 小于 2 的 n 次方 时，KD 树和球树的搜索速度大幅降低，暴力搜索算法相差无几。

我们介绍了第一个超参数 algorithm，就 kNN 算法来说通常只需要设置 auto 即可，让模型自动为我们选择合适的算法。

第二个超参数：n_neighbors

n_neighbors 即要选择最近几个点，默认值是 5（等效 k )。

回忆一下此前我们在建立 kNN 模型时传入的参数 n_neighbors 是随机选了一个 3，但这个 3 建立的模型不一定是最好的。

举个例子，看下面一组对比图。

红绿两种圆点代表不同类别，黄色点是待预测的点。左图中，k =3 时红绿点比例是 2:1，所以黄色点大概率属于红色类别。

右图中 k =5 时，黄色点大概率又属于绿色类别了。到底应该选择哪一个 k 值，黄色才能正确分类呢？

再以之前的葡萄酒数据集实际测试下，k 值分别选择 3 和 5 时的模型得分：

加载、划分数据集和建模相信你已经很熟悉了，不再多说，重点看红色箭头处的模型得分。k = 3 时，模型得分 0.76，k=5 时模型得分只有 0.68。所以 k =3 是更好的选择，但可能还存在其他 k 值比 3 效果更好，怎幺才能找到最好的 k 值呢？

最简单的方式就是递归搜索，从中选择得分最高的 k 值。

下面，我们设置一个 k 值范围，把刚才的代码封装到 for 循环中来尝试下：

可以看到，当 k 取 1-10，建立的 10 个模型中，k =3 时的模型得分最高。这样我们就找到了合适的超参数 k。

第三个超参数：距离权重 weights

刚才在划分黄色点分类时，最近的 3 个点中红绿色点比例是 2:1，所以我们就把黄色点划分为红色点了。

这样做忽略了点与点之间的距离问题：虽然红点数量多于绿点，但显然绿点距离黄点更近，把黄点划分为绿色类可能更合适。因此，之前的模型效果可能并不好。

所以，在建立模型时，还可以从距离出发，将样本权重与距离挂钩，近的点权重大，远的点权重小。怎幺考虑权重呢，可以用 取倒数 这个简单方法实现。

以上图为例，绿点距离是 1，取倒数权重还为 1；两个红点的距离分别是 3 和 4，去倒数相加后红点权重和为 7/12。绿点的权重大于红点，所以黄点属于绿色类。

在 Sklearn 的 kNN 模型中有专门考虑权重的超参数：weights，它有两个选项：

uniform 不考虑距离权重，默认值

distance 考虑距离权重

从这两个维度，我们可以再次循环遍历找到最合适的超参数：

第四个超参数：p

说到距离，还有一个重要的超参数 p。

如果还记得的话，之前的模型在计算距离时，采用的是欧拉距离：

除了欧拉距离，还有一种常用的距离， 曼哈顿距离 ：

这两种距离很好理解，举个例子，从家到公司，欧拉距离就是二者的直线距离，但显然不可能以直线到公司，而只能按着街道线路过去，这就是曼哈顿距离，俗称出租车距离。

这两种格式很像，其实他们有一个更通用的公式：

这就是 明可夫斯基距离 （Minkowski Distance），曼哈顿距离和欧拉距离分别是 p 为 1 和 2 的特殊值。

使用不同的距离计算公式，点的分类很可能不一样导致模型效果也不一样。

在 Sklearn 中对应这个距离的超参数是 p，默认值是 2，也就是欧拉距离，下面我们尝试使用不同的 p 值建立模型，看看哪个 p 值得到的模型效果最好， 这里因为考虑了 p，那幺 weights 超参数需是 distance，外面嵌套一个 for 循环即可：

可以看到，找出的最好模型，超参数 k 值为 15 ，p 值为 1 即曼哈顿距离，模型得分 0.81。

比我们最初采用的超参数：k=3、weights = uniform 得到的 0.76 分要好。但这里要注意 k=15 很可能是过拟合了，这样即使得分高这个模型也是不好的，以后会说。

小结一下，本文介绍了 algorithm、n_neighbors、weights、p 等超参数，通过循环搜索超参数（也就是 调参 ）获得了得分更高的模型。这种循环搜索的方式，有一个专门的名称叫： 网格搜索（Grid Search） ，以 k 和 p 两个超参数为例，循环遍历就像是在网格中搜索参数组合。

网格搜索是一个各种模型都很常用的模型调参方法，在 Sklearn 中专门封装了这样一个函数，只需要把想要调整的超参数都加进去运算之后，它会返回最好的一组超参数组合。比我们自己手写去找方便地多，我们在下一篇文章就来介绍一下网格搜索。