K近邻（KNN）算法
之前一段时间我们了解到的算法中，可以说是一个比一个复杂，本文呢，我们不再增加难度，来说一个最基础、最简单的监督学习算法KNN。
KNN的原理
我们给定一个数据集，对于一个新来的样本，我们在数据集中找到距离该样本最近的K个样本，在这K个样本中，某一类出现的次数最多我们就把这个样本分到这个类别中。
举一个例子：
如图所示，红色的三角和蓝色的方块为我们原有的数据集，绿色的圆即为一个新来到的样本，事先我们并不知道它属于某一类，我们来尝试两种不同的K值下的分类方法：
K=3
当我们选取K=3时，很明显距离绿色圆最近的三个样本为两个红色三角和一个蓝色方块，按照KNN的分类原则我们就可以将绿色圆分为红色三角一类。
K=5
当我们选取K=5时，很明显距离绿色圆最近的五个样本为两个红色三角和一个蓝色方块，同理我们就可以将绿色园分为蓝色方块一类。
也就是这样
根据这个例子我们就能总结出KNN算法的基本步骤：
（1）计算数据集中每个点到测试数据的距离d(i)；
（2）将算得的距离d(i)进行从小到大的排序；
（3）根据我们设定的K值选取排序后的前K个点；
（4）确定选取到的K个点中每一类别出现的频率；
（5）将出现频率最高的一类作为测试样本的预测分类结果。
从这个简单的例子可以看出，当我们选取不同的K值时会有不同的结果，那我们应该如何去选择K值，又应该如何去计算数据集中每个样本到新样本之间的距离呢？下面会给出解答。
KNN距离的度量
在我们数学的学习中关于度量的方式有很多种，我门在了解KNN所需要的距离度量方式的同时，也来了解一下其它的距离度量方式。
闵可夫斯基距离
闵可夫斯基距离是衡量数值点之间距离的一种非常常见的方法，假设数值点P和Q坐标如下：
那么闵可夫斯基距离的定义为：
欧式距离
对于闵可夫斯基距离，当p=2时，我们称之为欧式距离（欧几里得距离）。
曼哈顿距离
对于闵可夫斯基距离，当p=1时，我们称之为曼哈顿距离。
切比雪夫距离
对于闵可夫斯基距离，当P趋近于无穷大时，可以转化为切比雪夫距离。
和之前说到过的k-means算法一样，我们在KNN中也要使用欧式距离来进行距离的度量。
K值的选择
不同K值出现的问题
KNN中如何进行K值的选择是一个让人头大的问题，选的大了小了都会出现一定的问题，我们先来看一下下面的例子产生的问题：
和我们在讲第一个例子的时候同理，同样是将绿色圆作为测试样本，我们分别取K=1，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值取的比较小的条件下去选择得分最高的的就可以了。下面给出一段代码实现：
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树进行最近邻搜索，搜索的过程如下：
1.在KD树中找出包含目标点x的叶结点：从根结点出发，递归地向下访问kd树。若目标点x当前维度的2.坐标小于且分点的坐标，则移动到左子结点，否则移动到右子结点。直到子结点为叶子结点为止。
以此叶结点为“当前最近点”。
3.递归地向上回退，在每个结点进行以下操作：
- 如果该结点保存的实例点比当前最近点距离目标点更近，则以该实例点为“当前最近点”。
- 当前最近点一定存在于该结点的一个子结点的对应区域，检查该子结点的父结点的另一子结点对应的区域是否有更近的点。具体的，检查另一子结点对应的区域是否与目标点为球心，以目标点与“当前最近点”间的距离为半径的球体相交。
- 如果相交，可能在另一个子结点对应的区域内存在距目标点更近的点，移动到另一个子结点。接着递归进行最近邻搜索。
- 如果不相交，向上回退。
4.当回退到根结点时，搜索结束。最后的“当前最近点”即为x的最近邻点。
