机器学习值KNN：K近邻算法（一：算法原理）
目录
一、KNN概述
KNN是一种常见的有监督学习算法，可以用于分类，也可以用于回归，比较常用于分类。
K近邻算法的直观解释就是给定一个已知样本分类的训练数据集，当有新样本输入时，在训练集中找到K个和新样本距离最近的的训练样本，这K个训练样本多数属于哪个类别，就把这个新样本判定为哪个类别。
二、KNN三要素
2.1、距离度量
多维特征空间中，两个样本的距离，代表这两个样本的相似程度，距离越近，相似程度就越高，属于同一类别的概率就越大，KNN通常使用的距离度量方法是欧几里得距离，简称欧氏距离。在n维特征空间中，欧氏距离的测量公式为：
也有其他的距离度量方式，如更一般化的Lp距离或Minkowski距离。其中Lp距离的度量公式为：
对于上式，当P=1时，Lp距离称为曼哈顿距离，当P=2时，Lp距离称为欧氏距离。对于两者的区别，如下图，图中绿线代表x1与x2的欧氏距离，而红色线代表两点的曼哈顿距离。
2.2 、K值的选择
对于KNN算法而言，K值的选择至关重要。
当K的值选择较小时， 就是用较小邻域中的训练集来近似预测。此时，近似误差会很小，也就是在训练集上的误差会很小。但估计误差会比较大，模型失去泛化能力，在测试集上的误差较大，测试结果对近邻的样本点异常敏感。当K=1时，KNN退化为最近邻算法，如果近邻的样本点为噪声，或者受噪声影响较大，那么预测结果就不准确。换句话说，K值较小时，模型容易过拟合。
当K值选择过大时，就是用较大邻域中的训练集来近似测试。此时可以减少估计误差，但近似误差会较大。这时是用不那么相似的样本来预测，所以预测结果可能会发生错误。换句话说，K值太大，容易发生欠拟合。当K=N（N为样本总数），无论输入为什么，都会分类为样本数最多的那一类，此时，模型过于简单，完全没有学习到数据中的信息。
一般来说，K选择一个较小的值，依次增大，通过交叉验证的判断最优的K值，而且K值一般为奇数。
2.3、分类决策规则
KNN算法中常采用的时多数表决法，即少数服从多数。如：测试点的7个最近邻样本点中，有4个属于A类，2个属于B类，1个属于C类，那么该测试点属于A类。
多数表决法是根据邻域内多数决定归属的方法，是一种基于经验的判决方法，训练集中该邻域内的哪类样本多，测试集中该邻域内的点便属于哪一类。所以多数表决法等同于经验风险最小化方法。
三、KNN的优缺点
优点：精度高、对异常值不敏感、无输入数据假定
精度高是指KNN算法对于样本估计的精度高，分类错误率小。
对异常值不敏感是由于对K邻域内的点按多数表决法判断，所以个别的异常值并不会影响多数的判断。
无输入数据假定是指，相较于朴素贝叶斯等对于输入数据要提前假定数据服从高斯分布或者其他分布，KNN不需要进行这种假定。
缺点：计算复杂度高、受样本均衡度影响
计算复杂度高是指对于每个输入的测试样本，都要计算并存储其到其他各个点的距离，然后将距离排序并选择其中K个最小的，当样本点较多时，计算复杂度难以接受。
受样本均衡度影响是指，当某一类样本数量较多时，会影响判断，如下图所示：明显三角形属于红色的类别，而红色类别只有三个样本，所以当K大于6时，就会出现多余三个的黑色样本出现在领域内，并且三角形会被分类为黑色，这明显是错误的。
四、KNN的实现：kd树
KNN实现最简单的算法是线性扫描，即依次求测试样本点到其他所有点的距离，存储并选出最小的K个来判断。而当数据样本量较大时（一般指超过10000个样本或者样本个数远大于特征维数），计算开销就变的不太能接受，所以需要一种其他的方式来选出K个最近的点，kd树便是一种，其他的方法还有Ball Tree，MVP Tree等等。
值得一提的是，kd tree与KNN中的K并不是一个概念。KNN中的K是指选K个最近邻样本，而kd tree中的k是指样本特征空间的维度为k。
4.1、kd树的构造
首先选择根节点，先计算特征空间每个维度的方差，选择方差最大的维度A，这样的目的是使树的跨度尽可能的大。然后对维度A的数值进行排列，选择中位数，若有奇数个样本，则中位数恰好出现在样本点上，若为偶数个，则中位数是维度A上两个样本点的平均数，因为节点上的样本要为真实出现的样本，所以一般选择较大的值为中位数。选择好根节点后，按照A维度，将样本划分为左右两个区域，就A维度上的值而言，左边区域内的都小于等于根节点，右边区域内的都大于等于根节点。然后在左右两个节点上分别进行上述操作，知道每个节点的区域内没有其他子区域。
以李航老师《统计学习方法》上给出的样本点为例：{(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}
这组数据共两维，第一维上，均值为:(2+5+9+4+8+7)/6=5.83
方差为:(2-5.83)*(2-5.83)+(5-5.83)*(5-5.83)+(9-5.83)*(9-5.83)+(4-5.83)*(4-5.83)+(8-5.83)*(8-5.83)+(7-5.83)*(7-5.83)=34.8134
第二维上，均值为(3+4+6+7+1+2)/6=3.83
方差为:(3-3.83)*(3-3.83)+(4-3.83)*(4-3.83)+(6-3.83)*(6-3.83)+(7-3.83)*(7-3.83)+(1-3.83)*(1-3.83)+(2-3.83)*(2-3.83)=26.8134
因此选择split域为第一维，2，4，5，7，8，9的中位数为6，按照上面说的，选择7，所以根节点为(7,2),左区域内包括：(2,3)(5,4)(4,7),右区域包括(8,1)(9,6)。
再对根节点的左区域划分，根节点选择(5,4),左区域只剩(2,3),右区域只剩(4,7) ,划分完毕。
对根节点的右区域进行划分，根节点选择(9,6),左区域选择(8,1)，至此，划分完毕，结果如下：
特征空间划分如下：
4.2、kd树的搜索
搜索过程如下：
（1）找出kd树中包含目标节点x的叶节点：从根节点出发，递归的遍历kd树，若目标节点x的当前维坐标小于切分点坐标，则移动到左子节点，否则移动到右子节点。知道子节点为叶节点为止。
（2）以当前叶节点为当前最近的临近点。
（3）递归的向上回溯：而找到的叶子节点并不一定就是最邻近的，最邻近肯定距离查询点更近，应该位于以查询点为圆心且通过叶子节点的圆域内。若园与其他邻域相交，则可能存在更近的点，否则继续回溯。
（4）退回到根节点，回溯结束，当前保留的即为最近点。
以刚才构建的kd树为例，寻找点A(2.1，3.1)：
（1）根节点split域为第一维，所以A在其左子域内，当前节点由根节点（7，2）更新到（5，4），此时split域为第二维，所以A在其左子域，更新到叶子节点，所以此时最近点为（2，3）。
（2）点（2，3）到（2.1，3.1）的距离为0.1414。从（2，3）回溯到（5，4），由于该圆与（5，4）的分类边界没有交点，所以距离（5，4）的另一个子域内的点肯定不是最近点，因此不必遍历（5，4）的右孩子，继续回溯到（7，2），由于该圆与（7，2）的边界也没有交点，所以之前记录的最近点（2，3）即为全局最近点。
以刚才构建的kd树为例，寻找更麻烦的点B（2，4.5)：
（1）根节点split域为第一维，所以A在其左子域内，当前节点由根节点（7，2）更新到（5，4），此时split域为第二维，所以A在其右子域，更新到叶子节点，所以此时最近点为（4，7）。
（2） 以B为圆心，B到（4，7）的距离为半径画圆。从（4，7）开始回溯，回溯到（5，4），发现圆与分类边界相交，所以要去验证（5，4）的左子域内是否有点离B更近。此时会更新到（2，3），因为（2，3）是叶子节点，所以开始计算距离，发现（2，3）离B更近，所以将最近点由（4，7）更新到（2，3），重新画圆，并开始回溯到（5，4）的父节点（7，2），此时圆与（7，2）的分类边界不相交，所以另一子邻域内没有更近的点，再加上（7，2）为根节点，所以更新结束。最近点为（2，3）.
kd树的平均计算复杂度是 O(logN)，当特征空间维数较大或者与样本数相差不大时，kd树退化为线性扫描。