本部分主要为机器学习理论入门_K近邻法(KNN)，书籍参考 “ 统计学习方法（第二版）”。

学习目标： 了解k近邻算法的基本概念、原理、应用；熟悉k近邻算法重要影响要素；熟悉kd树原理与优化应用。

开始本算法之前我们首先直观的感受一下本算法的具体场景。
首先回顾一下感知机算法：感知机是二类分类的线性分类模型，是对应于特征空间中将实例划分为正负两类的分离超平面。有对比就有差距了，超过两类的数据如何处理呢，那么就有了K近邻算法：kNN是一种基本的分类与回归方法，可以适用与多类分组，当然了KNN不仅局限于分类问题。

一、K近邻算法原理

1.1 基本概念

邻近算法，或者说K最近邻(kNN，k-NearestNeighbor)分类算法是数据挖掘分类技术中最简单的方法之一。所谓K最近邻，就是k个最近的邻居的意思，说的是每个样本都可以用它最接近的k个邻居来代表。Cover和Hart在1968年提出了最初的邻近算法。KNN是一种分类(classification)算法，它输入基于实例的学习（instance-based learning），属于懒惰学习（lazy learning）即KNN没有显式的学习过程，也就是说没有训练阶段，数据集事先已有了分类和特征值，待收到新样本后直接进行处理。

k近邻算法是一种基本分类和回归方法，通过测量不同特征值之间的距离进行分类。

K近邻算法，即是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例，这K个实例的多数属于某个类，就把该输入实例分类到这个类中。

如上图所示，有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所标示的数据则是待分类的数据。这也就是我们的目的，来了一个新的数据点，我要得到它的类别是什么？好的，下面我们根据k近邻的思想来给绿色圆点进行分类。

• 如果K=3，绿色圆点的最邻近的3个点是2个红色小三角形和1个蓝色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。
• 如果K=5，绿色圆点的最邻近的5个邻居是2个红色三角形和3个蓝色的正方形，还是少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。

上边便是k近邻算法的核心思想了，简单实用。

下边来看一下书上的标准定义：

K近邻并没有显式的学习过程，也就是不需要对训练集进行学习。预测过程中直接遍历预测点与所有点的距离，并找到最近的K个点即可。找到K个最近点后，使用多数表决（即投票）的方式确定预测点的类别。式3.1I(yi=ci)中的I为指示函数，当括号内条件为真时I(true)=1，I(false)=0。argmax表示令后式数值最大时的参数，例如argmax(-X^2 + 1)的结果为0，因为x=0时-X^2 + 1结果为1，为最大值。

式3.1表示对于每一个类Cj，进行I(yi=cj)进行求和，就是计算这K个点中有多少个标记为Cj的点，例如K=25，一共有四个类分别为C1、C2、C3、C4，25个点中他们的个数分别有10、5、1、9个，那么最多数目的类别C1就是样本点的预测类别。

1.2 算法流程

根据上述算法思想给出起对应的实现步骤：

1. 计算测试数据与各个训练数据之间的距离；
2. 按照距离的递增关系进行排序；
3. 选取距离最小的K个点；
4. 确定前K个点所在类别的出现频率；
5. 返回前K个点中出现频率最高的类别作为测试数据的预测分类

1.3 应用场景

• 推荐系统： 基于用户之前的喜好推荐相似电影；推荐用户可能喜欢的曲目或歌手

• 文本分类: 区分垃圾邮件和正常邮件。

• 图像识别: 识别包括上的手写邮政编码，分类投递邮件包裹

• 医疗诊断： 预测患者可能的疾病风险。

• 信用评分： 预测客户的信用风险。

• 欺诈检测： 识别信用卡中的异常交易。

• 位置基服务： 基于位置提供餐厅或服务推荐。

二、KNN算法重点要素

上述算法实现步骤是不是很简单？但是其中各参数如何选取也是调参中的重要技术活呀，所以就有了k近邻算法的三要素：距离度量，K值的选择。

2.1 距离度量

在上文中说到，k近邻算法是在训练数据集中找到与该实例最邻近的K个实例，这K个实例的多数属于某个类，我们就说预测点属于哪个类。

定义中所说的最邻近是如何度量呢？我们怎么知道谁跟测试点最邻近。这里就会引出我们几种度量俩个点之间距离的标准。

书中给出了以下几种度量方式：

其中当p=2的时候，就是我们最常见的欧式距离，我们也一般都用欧式距离来衡量我们高维空间中俩点的距离。在实际应用中，距离函数的选择应该根据数据的特性和分析的需要而定，一般选取p=2欧式距离表示。

2.2 K值选择

K：临近数，即在预测目标点时取几个临近的点来预测。

K值得选取非常重要，因为：

• 如果当K的取值过小时，一旦有噪声得成分存在们将会对预测产生比较大影响，例如取K值为1时，一旦最近的一个点是噪声，那么就会出现偏差，K值的减小就意味着整体模型变得复杂，容易发生过拟合；
• 如果K的值取的过大时，就相当于用较大邻域中的训练实例进行预测，学习的近似误差会增大。这时与输入目标点较远实例也会对预测起作用，使预测发生错误。K值的增大就意味着整体的模型变得简单；
• 如果K==N的时候，那么就是取全部的实例，即为取实例中某分类下最多的点，就对预测没有什么实际的意义了；

K的取值尽量要取奇数，以保证在计算结果最后会产生一个较多的类别，如果取偶数可能会产生相等的情况，不利于预测。

K的取法：

常用的方法是从k=1开始，使用检验集估计分类器的误差率。重复该过程，每次K增值1，允许增加一个近邻。选取产生最小误差率的K。

一般k的取值不超过20，上限是n的开方，随着数据集的增大，K的值也要增大。

通用的K值确定方法如下：

• 交叉验证： 这是确定 k 值的最常用方法。对于每一个可能的 k 值，使用交叉验证计算模型的预测错误率，选择错误率最低的 k 值。
• 启发式方法： 有时，可以选择 sqrt(n)作为起始点，其中 n 是训练样本的数量。这只是一个粗略的估计，通常需要进一步验证。
• 误差曲线： 画出不同 k 值对应的误差率曲线，选择误差变化开始平稳的点。
• 领域知识： 在某些应用中，基于领域知识和经验选择 k 值可能更为合适。

三、KD树效率优化

上述原始算法复杂度为0(n)比较大，所以引出了下文的kd树结构优化KNN是算法。

现实生活中有许多问题需要在多维数据的快速分析和快速搜索，对于这个问题最常用的方法是所谓的kd树。在k-d树中进行数据的查找也是特征匹配的重要环节，其目的是检索在k-d树中与查询点距离最近的数据点。

说到KD树优化就不赘述了，老本行3D渲染中常用的三维空间加速结构，重点就是根据KD树结构快速定位节点，突发奇想是不是BVH、R-Tree等能够更加优化KNN算法，有时间的话实践一下试试。

四、小结

具体py实现建议采用sklearn库应用，详细代码可见其他代码实现的文章