KNN的英文叫K-Nearest Neighbor，应该算是数据挖掘算法中最简单的一种。
我们先用一个例子体会下。
假设，我们想对电影的类型进行分类，统计了电影中打斗次数、接吻次数，当然还有其他的指标也可以被统计到，如下表所示。
| 电影名称 | 打斗次数 | 接吻次数 | ······ | 电影类型 |
|---|---|---|---|---|
| 《战狼》 | 100 | 5 | ······ | 动作 |
| 《红海行动》 | 95 | 3 | ······ | 动作 |
| 《碟中谍6》 | 105 | 31 | ······ | 动作 |
| 《前任3》 | 2 | 59 | ······ | 爱情 |
| 《春娇救志明》 | 3 | 60 | ······ | 爱情 |
| 《泰坦尼克号》 | 10 | 80 | 爱情 |
我们很容易理解《战狼》《红海行动》《碟中谍6》是动作片，《前任3》《春娇救志明》《泰坦尼克号》是爱情片，但是有没有一种方法让机器也可以掌握这个分类的规则，当有一部新电影的时候，也可以对它的类型自动分类呢？
KNN的工作原理
“近朱者赤，近墨者黑”可以说是KNN的工作原理。整个计算过程分为三步：
- 计算待分类物体与其他物体之间的距离；
- 统计距离最近的K个邻居；
- 对于K个最近的邻居，它们属于哪个分类最多，待分类物体就属于哪一类。
K值如何选择
你能看出整个KNN的分类过程，K值的选择还是很重要的。那么问题来了，K值选择多少是适合的呢？
如果 K 值比较小，就相当于未分类物体与它的邻居非常接近才行。这样产生的一个问题就是，如果邻居点是个噪声点，那么未分类物体的分类也会产生误差，这样KNN分类就会产生过拟合。
如果K值比较大，相当于距离过远的点也会对未知物体的分类产生影响，虽然这种情况的好处是鲁棒性强，但是不足也很明显，会产生欠拟合情况，也就是没有把未分类物体真正分类出来。
所以K值应该是个实践出来的结果，并不是我们事先而定的。在工程上，我们一般采用交叉验证的方式选取 K 值。
交叉验证的思路就是，把样本集中的大部分样本作为训练集，剩余的小部分样本用于预测，来验证分类模型的准确性。所以在KNN算法中，我们一般会把K值选取在较小的范围内，同时在验证集上准确率最高的那一个最终确定作为K值。
距离如何计算
在KNN算法中，还有一个重要的计算就是关于距离的度量。两个样本点之间的距离代表了这两个样本之间的相似度。距离越大，差异性越大；距离越小，相似度越大。
关于距离的计算方式有下面五种方式：
- 欧氏距离；
- 曼哈顿距离；
- 闵可夫斯基距离；
- 切比雪夫距离；
- 余弦距离。
那么切比雪夫距离怎么计算呢？二个点之间的切比雪夫距离就是这两个点坐标数值差的绝对值的最大值，用数学表示就是：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次。
