【机器学习06】kNN 模型的几个超参数: Algorithm、n_neighbors、明科夫斯基距离

了解 kNN 的超参数 。

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

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

与超参数相对应的一个概念是模型参数,二者区别是:

  • 超参数是在模型运行前确定的
  • 模型参数是在算法运行过程自己学习的参数

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

第一个超参数: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。


第三个超参数:距离权重

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

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

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

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

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

  • uniform 不考虑距离权重,默认值

  • distance 考虑距离权重

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


第四个超参数:p

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

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

$$
\sqrt{\sum_{i=1}^{n}\left(X_{i}^{(a)}-X_{i}^{(b)}\right)^{2}}\
$$

$$
变形:\
\left(\sum_{i=1}^{n}\left|X_{i}^{(a)}-X_{i}^{(b)}\right|^{2}\right)^{\frac{1}{\gamma}}
$$

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

$$
\sum_{i=1}^{n}\left|X_{i}^{(a)}-X_{i}^{(b)}\right|
$$

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

这两种格式很像,其实他们有一个更通用的公式:
$$
\left(\sum_{i=1}^{n}\left|X_{i}^{(a)}-X_{i}^{(b)}\right|^{p}\right)^{\frac{1}{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 中专门封装了这样一个函数,只需要把想要调整的超参数都加进去运算之后,它会返回最好的一组超参数组合。比我们自己手写去找方便地多,我们在下一篇文章就来介绍一下网格搜索。

kNN 模型还有一些超参数,可以在官方文档中了解。只有设置好合适的超参数才能建立更好的模型。

sklearn.neighbors.KNeighborsClassifier

本文的 jupyter notebook 代码,可以在我公众号:「高级农民工」后台回复「kNN6」得到,加油!

你一打赏,我就写得更来劲了
0%