K近邻算法（KNN）

简介

KNN既可以做分类,也可以做回归,主要区别在于最后做预测时候的决策方式不同.KNN做分类预测时,一般选择多数表决法,即训练集里和预测的样本特征最近的k个样本,预测为里面有最多类别数的类别.而KNN做回归时,一般是选择平均法,即最近的K个样本输出的平均值作为回归预测值.

三要素

K的选择

对于k值的选择，没有一个固定的经验，一般根据样本的分布，选择一个较小的值，可以通过交叉验证选择一个合适的k值。

距离的度量方式

曼哈顿距离
欧式距离（常用）
闵可夫斯基距离(Minkowski Distance)

分类决策规则

1. 蛮力实现(brute-force):KNN算法的蛮力实现:需要计算出预测样本和所有训练集中的样本的距离,然后计算出最小的k个距离,接着多数表决,做出预测.此方法简单直接,适用于样本较少的情况.

2. KD树实现:
   2.1 原理
   KD树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形结构。可以进行多分类，KD树是一种二叉树，它相当于不断用垂直于坐标轴的超平面对k维空间进行切分，构成一系列的k维超矩形区域。KD树的每个节点对应于一个k维超矩形区域。利用KD树可以省去对大部分数据的搜索，相比于暴力搜索，可以大大减少搜索时间。
   
   2.2构造方法

    首先从m个样本的n维特征中，分别计算n个特征的方差，选取最大方差的特征n_k来进行划分，选取该特征的中位数作为根节点，以垂直与该维度的超平面将空间划为两部分，并生成左子树和右子树。对于左子树和右子树，我们采用和刚才同样的方法来找方差最大的特征的中位数来更新节点，递归生成KD树。
    具体流程图如下：
   
   2.3 KD树搜索最近邻
    当我们生成KD树以后，就可以去预测测试集里面的样本目标点了。对于一个目标点，我们首先在KD树里面找到包含目标点的叶子节点。以目标点为圆心，以目标点到叶子节点样本实例的距离为半径，得到一个超球体，最近邻的点一定在这个超球体内部。然后返回叶子节点的父节点，检查另一个子节点包含的超矩形体是否和超球体相交，如果相交就到这个子节点寻找是否有更加近的近邻,有的话就更新最近邻。如果不相交那就简单了，我们直接返回父节点的父节点，在另一个子树继续搜索最近邻。当回溯到根节点时，算法结束，此时保存的最近邻节点就是最终的最近邻。
    从上面的描述可以看出，KD树划分后可以大大减少无效的最近邻搜索，很多样本点由于所在的超矩形体和超球体不相交，根本不需要计算距离。大大节省了计算时间。

   2.4 KD树预测
    有了KD树搜索最近邻的办法，KD树的预测就很简单了，在KD树搜索最近邻的基础上，我们选择到了第一个最近邻样本，就把它置为已选。在第二轮中，我们忽略置为已选的样本，重新选择最近邻，这样跑k次，就得到了目标的K个最近邻，然后根据多数表决法，如果是KNN分类，预测为K个最近邻里面有最多类别数的类别。如果是KNN回归，用K个最近邻样本输出的平均值作为回归预测值。

小结

KNN算法是很基本的机器学习算法了，它非常容易学习，在维度很高的时候也有很好的分类效率，因此运用也很广泛，这里总结下KNN的优缺点。

KNN的主要优点有：
1） 理论成熟，思想简单，既可以用来做分类也可以用来做回归
2） 可用于非线性分类
3） 训练时间复杂度比支持向量机之类的算法低，仅为O(n)
4） 和朴素贝叶斯之类的算法比，对数据没有假设，准确度高，对异常点不敏感
5） 由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合
6）该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分
　　　　
KNN的主要缺点有：
1）计算量大，尤其是特征数非常多的时候
2）样本不平衡的时候，对稀有类别的预测准确率低
3）KD树，球树之类的模型建立需要大量的内存
4）使用懒散学习方法，基本上不学习，导致预测时速度比起逻辑回归之类的算法慢
5）相比决策树模型，KNN模型可解释性不强