数据挖掘算法05 - KNN

￡神魔★判官ぃ 2022-01-27 16:47 229阅读 0赞

## KNN ##

KNN 的英文叫 K-Nearest Neighbor，应该算是数据挖掘算法中最简单的一种。

> KNN 的工作原理

**近朱者赤，近墨者黑**可以说是 KNN 的工作原理。整个计算过程分为三步：

*  计算待分类物体与其他物体之间的距离；
 *  统计距离最近的 K 个邻居；
 *  对于 K 个最近的邻居，它们属于哪个分类最多，待分类物体就属于哪一类。

> K 值如何选择

如果 K 值比较小，就相当于未分类物体与它的邻居非常接近才行。这样产生的一个问题就是，如果邻居点是个噪声点，那么未分类物体的分类也会产生误差，这样 KNN 分类就会产生过拟合。

如果 K 值比较大，相当于距离过远的点也会对未知物体的分类产生影响，虽然这种情况的好处是鲁棒性强，但是不足也很明显，会产生欠拟合情况，也就是没有把未分类物体真正分类出来。

所以 K 值应该是个实践出来的结果，并不是我们事先而定的。在工程上，我们一般采用交叉验证的方式选取 K 值。

**交叉验证**的思路就是，把样本集中的大部分样本作为训练集，剩余的小部分样本用于预测，来验证分类模型的准确性。所以在 KNN 算法中，我们一般会把 K 值选取在较小的范围内，同时在验证集上准确率最高的那一个最终确定作为 K 值。

> 距离如何计算

在 KNN 算法中，还有一个重要的计算就是关于距离的度量。两个样本点之间的距离代表了这两个样本之间的相似度。距离越大，差异性越大；距离越小，相似度越大。

关于距离的计算方式有下面五种方式：

*  欧氏距离；
 *  曼哈顿距离；
 *  闵可夫斯基距离；
 *  切比雪夫距离；
 *  余弦距离。

**欧氏距离**是我们最常用的距离公式，也叫做欧几里得距离。在二维空间中，两点的欧式距离就是：

![f8d4fe58ec9580a4ffad5cee263b1b80.png][]

同理，我们也可以求得两点在 n 维空间中的距离：

![40efe7cb4a2571e55438b55f8d37366a.png][]

**曼哈顿距离**等于两个点在坐标系上绝对轴距总和。用公式表示就是：

![bda520e8ee34ea19df8dbad3da85faaa.png][]

**闵可夫斯基距离**不是一个距离，而是一组距离的定义。对于 n 维空间中的两个点 x(x1,x2,…,xn) 和 y(y1,y2,…,yn) ， x 和 y 两点之间的闵可夫斯基距离为：

![4d614c3d6722c02e4ea03cb1e6653dc5.png][]

其中 p 代表空间的维数，当 p=1 时，就是曼哈顿距离；当 p=2 时，就是欧氏距离；当 p→∞时，就是切比雪夫距离。

二个点之间的**切比雪夫距离**就是这两个点坐标数值差的绝对值的最大值，用数学表示就是：max(|x1-y1|,|x2-y2|)。

**余弦距离**实际上计算的是两个向量的夹角，是在方向上计算两者之间的差异，对绝对数值不敏感。在兴趣相关性比较上，角度关系比距离的绝对值更重要，因此余弦距离可以用于衡量用户对内容兴趣的区分度。比如我们用搜索引擎搜索某个关键词，它还会给你推荐其他的相关搜索，这些推荐的关键词就是采用余弦距离计算得出的。

> KD 树

其实从上文你也能看出来，KNN 的计算过程是大量计算样本点之间的距离。为了减少计算距离次数，提升 KNN 的搜索效率，人们提出了 KD 树（K-Dimensional 的缩写）。KD 树是对数据点在 K 维空间中划分的一种数据结构。在 KD 树的构造中，每个节点都是 k 维数值点的二叉树。既然是二叉树，就可以采用二叉树的增删改查操作，这样就大大提升了搜索效率。

在这里，我们不需要对 KD 树的数学原理了解太多，你只需要知道它是**一个二叉树的数据结构**，**方便存储 K 维空间的数据**就可以了。而且在 sklearn 中，我们直接可以调用 KD 树，很方便。

> 用 KNN 做回归

KNN 不仅可以做分类，还可以做回归。

首先讲下什么是回归。在开头电影这个案例中，如果想要对未知电影进行类型划分，这是一个分类问题。首先看一下要分类的未知电影，离它最近的 K 部电影大多数属于哪个分类，这部电影就属于哪个分类。

如果是一部新电影，已知它是爱情片，想要知道它的打斗次数、接吻次数可能是多少，这就是一个回归问题。

那么 KNN 如何做回归呢？

对于一个新点，我们需要找出这个点的 K 个最近邻居，然后将这些邻居的属性的平均值赋给该点，就可以得到该点的属性。当然不同邻居的影响力权重可以设置成不同的。举个例子，比如一部电影 A，已知它是动作片，当 K=3 时，最近的 3 部电影是《战狼》，《红海行动》和《碟中谍 6》，那么它的打斗次数和接吻次数的预估值分别为 (100+95+105)/3=100 次、(5+3+31)/3=13 次。

> 如何用 KNN 对手写数字进行识别分类

手写数字数据集是个非常有名的用于图像识别的数据集。数字识别的过程就是将这些图片与分类结果 0-9 一一对应起来。完整的手写数字数据集 MNIST 里面包括了 60000 个训练样本，以及 10000 个测试样本。如果你学习深度学习的话，MNIST 基本上是你接触的第一个数据集。

今天我们用 sklearn 自带的手写数字数据集做 KNN 分类，你可以把这个数据集理解成一个简版的 MNIST 数据集，它只包括了 1797 幅数字图像，每幅图像大小是 8\*8 像素。

> KNN 分类的流程

![8af94562f6bd3ac42036ec47f5ad2578.jpg][]

*  数据加载：我们可以直接从 sklearn 中加载自带的手写数字数据集；
 *  准备阶段：在这个阶段中，我们需要对数据集有个初步的了解，比如样本的个数、图像长什么样、识别结果是怎样的。你可以通过可视化的方式来查看图像的呈现。通过数据规范化可以让数据都在同一个数量级的维度。另外，因为训练集是图像，每幅图像是个 8\*8 的矩阵，我们不需要对它进行特征选择，将全部的图像数据作为特征值矩阵即可；
 *  分类阶段：通过训练可以得到分类器，然后用测试集进行准确率的计算。

> 总结

![d67073bef9247e1ca7a58ae7869f390f.png][]

在数据量不大的情况下，使用 sklearn 还是方便的。

如果数据量很大，比如 MNIST 数据集中的 6 万个训练数据和 1 万个测试数据，那么采用深度学习 +GPU 运算的方式会更适合。因为深度学习的特点就是需要大量并行的重复计算，GPU 最擅长的就是做大量的并行计算。

![d08f489c3bffaacb6910f32a0fa600e1.png][]

[f8d4fe58ec9580a4ffad5cee263b1b80.png]: /images/20220127/9508e4426a8b4eeb8f003e7ca9aecc84.png
[40efe7cb4a2571e55438b55f8d37366a.png]: /images/20220127/3004156d134545dfb9ea57c3a485d73e.png
[bda520e8ee34ea19df8dbad3da85faaa.png]: /images/20220127/fbd0addbd8df40b6a3873ddaee5043f8.png
[4d614c3d6722c02e4ea03cb1e6653dc5.png]: /images/20220127/51cda002b65446f881f9608dd02969a9.png
[8af94562f6bd3ac42036ec47f5ad2578.jpg]: /images/20220127/30d7cfe07b564cc5a03d229d6b2cf341.png
[d67073bef9247e1ca7a58ae7869f390f.png]: /images/20220127/01137d8c2ddc436fbfdfff9601169341.png
[d08f489c3bffaacb6910f32a0fa600e1.png]: /images/20220127/47f941c41ba64d3482690ecc008313ca.png