[TOC]
## **1. k近邻算法的基本概念，原理以及应用**
* k近邻算法是一种**基本分类和回归方法**。本篇文章只讨论分类问题的k近邻法。
* K近邻算法，即是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例**最邻近**的K个实例，**这K个实例的多数属于某个类**，就把该输入实例分类到这个类中。（**这就类似于现实生活中少数服从多数的思想**）根据这个说法，咱们来看下引自维基百科上的一幅图：
* :-: 
* 如上图所示，有**两类**不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所标示的数据则是**待分类的数据**。这也就是我们的目的，来了一个新的数据点，我要得到它的类别是什么？好的，下面我们根据k近邻的思想来给绿色圆点进行分类。
* 如果K=3，绿色圆点的最邻近的3个点是2个红色小三角形和1个蓝色小正方形，**少数从属于多数，** 基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。
* 如果K=5，绿色圆点的最邻近的5个邻居是2个红色三角形和3个蓝色的正方形，**还是少数从属于多数，** 基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。
* 通过上面的例子也能够看出，KNN并不需要事先训练一个模型，而是直到需要分类测试样本时才进行。这种学习方法叫做 懒惰学习（lazy learning），这类技术在训练阶段仅仅把样本保存起来，训练时间开销为0，待收到测试样本时再处理。而且我们讲过的神经网络，决策树，logistic 回归，SVM等在训练阶段就学习模型的方法，称为急切学习（eager learning）。下面稍微形式化一点用伪代码来描述下KNN分类算法的流程：
* 
* 
* 这里加一句题外话，KNN虽然思想简单，但是性能是很不错的，**能够理论证明KNN的泛化错误率不超过贝叶斯最优分类器的错误率的两倍。** 从以上的基本原理中，我们大概能够得到KNN算法的三个关键点：
* 1. **K值的大小对预测结果的影响**
* 2. **距离度量方式**
* 3. **如何找到与测试样本距离最近的K个样本**
* 下面会分别介绍这三方面的内容。
## **2. KNN中K值大小对预测结果的影响**
* 从上面原理中，能够知道KNN中K值是需要自己指定的，关于K值大小对预测结果的影响如下：
* 若K值太小，相当于用较小的邻域中的训练样本去预测，则KNN分类器容易受到由于训练数据中噪声的影响而产生过拟合。
* 若K值太大，因为邻域比较大，则与测试样本距离较远的训练样本也会起作用，这样会导致误分类测试样本。
* 若K=N，那么无论输入的测试样本是什么，输出都会是训练样本中样本数量最多的类，这种模型基本没什么用。
* **在实际应用中，k值一般选取一个比较小的值，可以通过交叉验证法来选取最优的K值。**
## **3. KNN中距离度量方式**
* 在上文中说到，k近邻算法是在训练数据集中找到与该实例**最邻近**的K个实例，这K个实例的多数属于某个类，我们就说预测点属于哪个类。
* 定义中所说的最邻近是如何度量呢？我们怎么知道谁跟测试点最邻近。这里就会引出我们几种度量俩个点之间距离的标准。
* 我们可以有以下几种度量方式：
* 
* 其中当p=2的时候，就是我们最常见的欧式距离，我们也一般都用欧式距离来衡量我们高维空间中俩点的距离。在实际应用中，距离函数的选择应该根据数据的特性和分析的需要而定，一般选取p=2欧式距离表示。
## **4. 特征归一化的必要性**
* 首先举例如下，我用一个人身高(cm)与脚码（尺码）大小来作为特征值，类别为男性或者女性。我们现在如果有5个训练样本，分布如下：
* A \[(179,42),男\] B \[(178,43),男\] C \[(165,36)女\] D \[(177,42),男\] E \[(160,35),女\]
* 通过上述训练样本，很容易看到第一维身高特征是第二维脚码特征的4倍左右，那么在进行距离度量的时候，**我们就会偏向于第一维特征。**这样造成俩个特征并不是等价重要的，最终可能会导致距离计算错误，从而导致预测错误。举例如下：
* 现在来了一个测试样本 F(167,43)，让我们来预测他是男性还是女性，我们采取k=3来预测。
* 下面我们用欧式距离分别算出F离训练样本的欧式距离，然后选取最近的3个，多数类别就是我们最终的结果，计算如下：
* 
* 由计算可以得到，最近的前三个分别是C,D,E三个样本，那么由C,E为女性，D为男性，女性多于男性得到我们要预测的结果为**女性**。
* **这样问题就来了，一个女性的脚43码的可能性，远远小于男性脚43码的可能性，那么为什么算法还是会预测F为女性呢？那是因为由于各个特征量纲的不同，在这里导致了身高的重要性已经远远大于脚码了，这是不客观的。** 所以我们应该让每个特征都是同等重要的！这也是我们要归一化的原因！归一化公式如下：
* 
## **5. k近邻算法中的分类决策规则**
* k近邻算法的分类决策规则通俗来说就是**k 近邻法中的分类决策规则往往是多数表决决定，背后的数学思维是什么？**
* k 近邻法中的分类决策规则往往是多数表决，即由输入实例的 k 个近邻的训练实例中的多数类决定输入实例的类。
* 多数表决规则（majority voting rule）有如下解释：如果分类的损失函数为 0-1 损失函数，分类函数为：
* :-: 
* 那么误分类的概率是：
* :-: 
* 
* 换句话说，目前候选种类为c1,c2....cj，我选择哪一个，使得我们的经验风险最小（**经验风险通俗讲就是训练数据的错误值**）。
* 那么由上式经验风险最小，**也就是说，要我们预测出的种类属于cj类的最多（那么预测出来的种类结果和真实结果一致的越多，我们认为正确可能性就越大，也就是经验风险越小），也就是我们所说的多数表决规则。而它也等价于我们的经验风险最小。这也是我们在k近邻算法中采用多数表决规则的正确性说明！**
## **6. k近邻法的实现：kd树原理的讲解以及kd树详细例子**
### **kd树原理**
**kd 树的结构**
* kd树是一个二叉树结构，它的每一个节点记载了【**特征坐标，切分轴，指向左枝的指针，指向右枝的指针**】。
* 其中，特征坐标是线性空间 Rn 中的一个点 (x1,x2,…,xn)切分轴由一个整数 r 表示，这里 1≤r≤n，是我们在 n 维空间中沿第 rr维进行一次分割。节点的左枝和右枝分别都是 kd 树，并且满足：如果 y 是左枝的一个特征坐标，那么 yr≤xr（**左分支结点**）；并且如果 z 是右枝的一个特征坐标，那么 zr≥xr（**右分支结点**）。
* 给定一个数据样本集 S⊆Rn 和切分轴 r，以下**递归算法**将构建一个基于该数据集的 kd 树，每一次循环制作一个节点：
> −− 如果 |S|=1，记录 S 中唯一的一个点为当前节点的特征数据，并且不设左枝和右枝。（|S| 指集合 S 中元素的数量）
> −− 如果 |S|>1
> * 将 S 内所有点按照第 r 个坐标的大小进行**排序**；
> * 选出该排列后的中位元素（**如果一共有偶数个元素，则选择中位左边或右边的元素，左随便哪一个都无所谓**），作为当前节点的特征坐标，并且记录切分轴 r；
>
> * 将 SL设为在 S 中所有排列在中位元素之前的元素； SR 设为在 S 中所有排列在中位元素后的元素；
>
> * 当前节点的左枝设为以 SL 为数据集并且 r 为切分轴制作出的 kd 树；当前节点的右枝设为以 SR 为数据集并且 r为切分轴制作出的 kd 树。再设 r←(r+1)modn。（**这里，我们想轮流沿着每一个维度进行分割；modn 是因为一共有 n 个维度，**在**沿着最后一个维度进行分割之后再重新回到第一个维度。**）
>
### **kd树的构建**
* **给定一个二维空间的数据集：**
* **T = {（2,3），（5,4），（9,6）,（4,7），（8,1），（7,2）}， 构造一个平衡kd树。**
* **为了方便，我这里进行编号A(2，3)、B（5,4）、C（9,6）、D（4,7）、E（8,1）、F（7,2）**
* **初始值r=0，对应x轴。**
* 可视化数据点如下：
* :-: 
* 首先先沿 x 坐标进行切分，我们选出 x 坐标的中位点，获取最根部节点的坐标，对数据点x坐标进行排序得：
* A(2，3)、D（4,7）、B（5,4）、F（7,2）、E（8,1）、C（9,6）
* **则我们得到中位点为B或者F，我这里选择F作为我们的根结点，并作出切分（并得到左右子树），如图：**
* :-: 
* **对应的树结构如下：**
* :-: 
* **根据算法，此时r=r+1=1，对应y轴，此时对应算法|S|>1，则我们分别递归的在F对应的左子树与右子树按y轴进行分类，得到中位节点分别为B，C点，如图所示：**
* :-: 
* **对应树结构为：**
* :-: 
* **而到此时，B的左孩子为A，右孩子为D，C的左孩子为E,均满足|S|==1，此时r = (r+1)mod2 = 0,又满足x轴排序，对x轴划分！则如图所示：**
* :-: 
* 对应树结构如下：
* :-: 
* 到这里为止，给定的kd树构造完成啦，**所有的数据点都能在树上的每个结点找到！**而我们根据上面构造树的过程，也能很容易的知道，来了一个新的数据点的时候，对应该层的指定维数，通过比较大小，我就能知道往左（**预测点对应维度数据小于该结点对对应维度数据**）走还是往右（**预测点对应维度数据大于该结点对应维度数据**）走，**那么好的情况下**，就能省掉一半的数据点啦~（**不好的情况，没有节省，后面会说到，这也是kd树的致命缺点~**）
* 这也是李航博士书籍上例子中kd树构造的详细过程！他的图片如下：
* :-: 
* 对应kd树为:
* :-: 
### **kd树搜索**
* 我这里和统计学习方法例子一样，以最近邻为例加以叙述，同样的方法可以应用到k近邻。
* **为了让大家更好的理解，我这里直接用上面例子给大家一步一步给出过程！**
* **首先我们来看用kd树的最近邻搜索算法流程：**
* **输入：已构造的kd树；目标点x；**
* **输出：x的最近邻.**
* （1）在kd树中找出包含目标点x的叶结点：从根结点出发，递归地向下访问kd树，**若目标点x当前维的坐标小于切分点的坐标,则移动到左子节点，否则移动到右子结点.直到子结点为叶结点位置.**
* （2）以此叶结点为“当前最近点”
* （3）递归地向上回退，在每个结点进行以下操作：
* * （a）如果该结点保存的实例点比当前最近点距离目标点更近，则以该实例点为“当前最近点”.
* * （b）当前最近点一定存在于该结点一个子结点对应的区域.检查该子结点的父结点的另一个子结点对应的区域是否有更近的点.具体地，**检查另一子结点对应的区域是否以目标点为球心、以目标点与“当前最近点”间为半径的超球体相交。**
* **如果不相交，向上回退.**
* （4）**当回退到根结点时，搜索结束。最后的“当前最近点”即为最近邻点.**
* 下面通过例子，一步一步走一遍上面所描述的算法过程，化抽象为具体！
* **kd树最近邻搜索例题：**
* **给定一个二维空间的数据集：**
* **T = {（2,3），（5,4），（9,6）,（4,7），（8,1），（7,2）}，输入目标实例为K(8.5,1),求K的最近邻。**
* **首先我们由上面可以给出，T的kd树对应如下：**
* :-: 
* 我们此时的K（8.5,1），根据算法第一步得：第一层的x轴K点为8大于F点的7，所以进入F（7,2）的右子树，进入下面红色线条区域：
* :-: 
* 到了第二层，分割平面坐标为y轴，K点y轴坐标为1，小于C点y轴坐标6，则继续向右走，在下图红色线条区域内：
* :-: 
* 则此时算法对应第（1）部分完成，我们找到了叶子节点E（8,1）。
* 我们进行算法第（2）步，把E（8,1）作为最近邻点。此时我们算一下KE之间的距离为0.5（便于后面步骤用到）.
* 然后进行算法第（3）步，递归的往上回退，每个结点进行相同步骤，好，我现在从E点回退到C点，对应图片如下；
*
* :-: 
*
* 此时对C点进行第（3）步的（a）操作，判断一下KC距离与保存的最近邻距离（这时是KE）比较，KC距离为点K（8.5,1）与点C（9,6）之间的距离![[公式]](https://www.zhihu.com/equation?tex=%5Csqrt%7B25.25%7D+)\>最近邻0.5，于是不更新最近邻点。
*
* 然后对C点进行第（3）步的（b）操作，判断一下当前最近邻的距离画一个圆是否与C点切割面相交，如图所示：
*
* :-: 
*
* 我们很容易看到与C点切割面并没有相交，于是执行由C点回退到它的父结点F点。如图：
*
* :-: 
*
* 对F点进行（a），（b）操作！
* 进行（a）步骤，判断FK的距离是否小于当前保存的最小值，FK=![[公式]](https://www.zhihu.com/equation?tex=%5Csqrt%7B%287-8.5%29%5E%7B2%7D%2B%282-1%29%5E%7B2%7D+%7D%3D%5Csqrt%7B1.25%7D++)\>0.5，所以不改变最小距离
* 下面我们进行（b）步骤，为了判断F点的另一半区域是否有更小的点，判断一下当前最近邻的距离画一个圆是否与F点切割面相交，如图所示：
* :-: 
* **发现与任何分割线都没有交点，那么执行算法最后一步，此时F点已经是根结点，无法进行回退，那么我们可以得到我们保留的当前最短距离点E点就是我们要找的最近邻点！任务完成，**
* **并且根据算法流程，我们并没有遍历所有数据点，而是F点的左孩子根本没有遍历，节省了时间，但是并不是所有的kd树都能到达这样的效果。**
## **7. kd树的不足以及最差情况举例**
* 讲解这个知识点，还是通过一个例子来直观说明!
* **给定一个二维空间的数据集：**
* **T = {（2,3），（5,4），（9,6）,（4,7），（8,1），（7,2）}，输入目标实例为K(8,3),求K的最近邻。**
* **首先我们由上面可以给出，T的kd树对应如下：**
*
* :-: 
* **我们此时的K（8,3），根据算法第一步得：第一层的x轴K点为8大于F点的7，所以进入F（7,2）的右子树，进入下面红色线条区域：**
*
* :-: 
*
* **（注意：这里叶子节点画不画分割线都没有关系！）**
*
* **到了第二层，分割平面坐标为y轴，K点y轴坐标为3，小于C点y轴坐标6，则继续向右走，在下图红色线条区域内：**
*
* :-: 
*
* **则此时算法对应第（1）部分完成，我们找到了叶子节点E（8,1）。**
*
* **我们进行算法第（2）步，把E（8,1）作为最近邻点。此时我们算一下KE之间的距离为2（便于后面步骤用到）.**
*
* **然后进行算法第（3）步，递归的往上回退，每个结点进行相同步骤，好，我现在从E点回退到C点，对应图片如下；**
*
* :-: 
*
* **此时对C点进行第（3）步的（a）操作**，判断一下KC距离与保存的最近邻距离（这时是KE）比较，KC距离为点K（8,3）与点C（9,6）之间的距离![[公式]](https://www.zhihu.com/equation?tex=%5Csqrt%7B10%7D+)\>最近邻2，于是不更新最近邻点。
*
* **然后对C点进行第（3）步的（b）操作，判断一下当前最近邻的距离画一个圆是否与C点切割面相交，如图所示：**
*
* :-: 
*
* **我们很容易看到与C点切割面并没有相交，于是执行由C点回退到它的父结点F点。如图：**
*
* :-: 
*
* **对F点进行（a），（b）操作！**
*
* **进行（a）步骤，判断FK的距离是否小于当前保存的最小值，FK=![[公式]](https://www.zhihu.com/equation?tex=%5Csqrt%7B%287-8%29%5E%7B2%7D%2B%282-3%29%5E%7B2%7D+%7D%3D%5Csqrt%7B2%7D++)**
*
* **<2,所以将最小距离替换为FK的距离！**
* **下面我们进行（b）步骤，为了判断F点的另一半区域是否有更小的点，** 判断一下当前最近邻的距离画一个圆是否与F点切割面相交，如图所示：
*
* :-: 
*
* 我们可以看出，此时圆与F点有交点，那么说明F点左侧是有可能存在与K点距离更小的点（注:这里我们人为看起来好像没有，但是计算机不知道，必须搜索下去，只要以当前最小值画圆发现与节点切割面有交点，**那么一定要进行搜索，不然数据如果是下图：）**
*
* :-: 
*
* 如果不进行搜索，我们就可能会漏掉Z数据点，因为KZ比当前最小值KF小！
*
* 此时相交，我们就需要再F点的左孩子进行搜索，一直搜索到叶子节点A，然后进行（a），（b）步骤，继续回溯到它的父亲结点B，以及最后到达F点，完成最后的最近邻是F点，这里几乎遍历了所有数据点，**几乎退化了为线性时间0（n）了。这也是kd树的最差的情况。**
*
*
* 当给定的数据分布很差的时候，我们每一次计算画圆过程中，**都会与每一个分割面相交的时候，都会递归搜索到该结点的另一个子空间中遍历，那么这样最坏的情况是进行线性时间搜索！**比如构建的kd树和数据分布如下：
*
* :-: 
*
* **如图所示，我们可以看到几乎所有的数据离给定预测的点距离很远，每次进行算法第三步判断是否与分割面有交点的时候，几乎每个面都有交点，只要有交点，就必须将该点的另一半结点遍历到叶子结点，重复的进行算法步骤，导致了搜索的低效！**
## **8. k近邻方法的一些优缺点总结**
* **优点：**
*
* 1. KNN分类方法是一种非参数的分类技术，简单直观，易于实现！**只要让预测点分别和训练数据求距离，挑选前k个即可，非常简单直观。**
*
* 2. KNN是一种在线技术，新数据可以直接加入数据集而**不必进行重新训练**
*
* **缺点及改进**：
* 1. 当样本不平衡时，**比如一个类的样本容量很大，其他类的样本容量很小**，输入一个样本的时候，K个邻近值大多数都是大样本容量的那个类，这时可能会导致分类错误。
* **改进方法：对K邻近点进行加权，也就是距离近的权值大，距离远的点权值小。**
*
2. 计算量较大，每个待分类的样本都要计算它到全部点的距离**，根据距离排序才能求得K个临近点。
* **改进方法：先对已知样本带你进行裁剪，事先去除分类作用不大的样本，采取kd树以及其它高级搜索方法BBF等算法减少搜索时间。**
