KNN算法三要素

• 选择较小的值，就相当于用较小的领域中的训练实例进行预测，训练误差会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是泛化误差会增大，换句话说， 值的减小就意味着整体模型变得复杂，容易发生过拟合；

• 选择较大的值，就相当于用较大领域中的训练实例进行预测，其优点是可以减少泛化误差，但缺点是训练误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，且值的增大就意味着整体的模型变得简单。一个极端是等于样本数，则完全没有分类，此时无论输入实例是什么，都只是简单的预测它属于在训练实例中最多的类，模型过于简单。

KNN算法蛮力实现

KNN算法之KD树实现原理

KD树算法没有一开始就尝试对测试样本分类，而是先对训练集建模，建立的模型就是KD树，建好了模型再对测试集做预测。所谓的KD树就是个特征维度的树，这里的和KNN中的的意思不同。KNN中的K代表最近的个样本，KD树中的代表样本特征的维数。为了防止混淆，后面称特征维数为。

KD树算法包括三步，第一步是建树，第二部是搜索最近邻，最后一步是预测

KD树的建立

KD树建树采用的是从 个样本的 维特征中，分别计算 个特征的取值的方差，用方差最大的第 维特征 来作为根节点。对于这个特征，选择特征 的取值的中位数对应的样本作为划分点，对于所有第维特征的取值小于的样本，划入左子树，对于第维特征的取值大于等于的样本，划入右子树，对于左子树和右子树，采用和刚才同样的办法来找方差最大的特征来做更节点，递归的生成KD树。

具体流程如下图：

 

比如有二维样本6个， ，构建kd树的具体步骤为：

1. 找到划分的特征
6个数据点在维度上的数据方差分别为6.97，5.37，所以在轴上方差更大，用第1维特征建树

2. 确定划分点
根据维上的值将数据排序，6个数据的中值为7，所以划分点的数据是(7,2)，这样，该节点的分割超平面就是通过(7,2)并垂直于：划分点维度的直线

3. 确定左子空间和右子空间
分割超平面将整个空间分为两部分： 的部分为左子空间，包含3个节点={(2,3),(5,4),(4,7)}；另一部分为右子空间，包含2个节点={(9,6)，(8,1)}

4. 用同样的办法划分左子树的节点{(2,3),(5,4),(4,7)}和右子树的节点{(9,6)，(8,1)}。最终得到KD树

 

 

KD树搜索最近邻

生成KD树以后，就可以去预测测试集里面的样本目标点了。对于一个目标点，首先在KD树里面找到包含目标点的叶子节点。以目标点为圆心，以目标点到叶子节点样本实例的距离为半径，得到一个超球体，最近邻的点一定在这个超球体内部。然后返回叶子节点的父节点，检查另一个子节点包含的超矩形体是否和超球体相交，如果相交就到这个子节点寻找是否有更加近的近邻,有的话就更新最近邻。如果不相交那就简单了，直接返回父节点的父节点，在另一个子树继续搜索最近邻。当回溯到根节点时，算法结束，此时保存的最近邻节点就是最终的最近邻。

从上面的描述可以看出，KD树划分后可以大大减少无效的最近邻搜索，很多样本点由于所在的超矩形体和超球体不相交，根本不需要计算距离。大大节省了计算时间。

 

用前面建立的KD树，来看对点找最近邻的过程：

先进行二叉查找，先从 查找到节点，在进行查找时是由为分割超平面的，由于查找点为值为4.5，因此进入右子空间查找到 ，形成搜索路径 ，但 与目标查找点的距离为3.202，而 与查找点之间的距离为3.041，所以为查询点的最近点； 以 为圆心，以3.041为半径作圆，如下图所示。可见该圆和 超平面交割，所以需要进入 左子空间进行查找，也就是将节点加入搜索路径中得 ；于是接着搜索至叶子节点，距离 比 要近，所以最近邻点更新为，最近距离更新为1.5；回溯查找至，直到最后回溯到根结点 的时候，以 为圆心1.5为半径作圆，并不和分割超平面交割，如下图所示。至此，搜索路径回溯完，返回最近邻点，最近距离1.5。

对应的图如下：

KD树预测

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

 

 

KNN算法之球树实现原理

KD树算法虽然提高了KNN搜索的效率，但是在某些时候效率并不高，比如当处理不均匀分布的数据集时,不管是近似方形，还是矩形，甚至正方形，都不是最好的使用形状，因为他们都有角，如下图：

如果黑色的实例点离目标点星点再远一点，那么虚线圆会如红线所示那样扩大，导致与左上方矩形的右下角相交，既然相 交了，那么就要检查这个左上方矩形，而实际上，最近的点离星点的距离很近，检查左上方矩形区域已是多余。于此我们看见，KD树把二维平面划分成一个一个矩形，但矩形区域的角却是个难以处理的问题。

为了优化超矩形体导致的搜索效率的问题，牛人们引入了球树，这种结构可以优化上面的这种问题。

球树的建立

球树，顾名思义，就是每个分割块都是超球体，而不是KD树里面的超矩形体。

具体的建树流程：

1. 先构建一个超球体，这个超球体是可以包含所有样本的最小球体

2. 从球中选择一个离球的中心最远的点，然后选择第二个点离第一个点最远，将球中所有的点分配到离这两个聚类中心最近的一个上，然后计算每个聚类的中心，以及聚类能够包含它所有数据点所需的最小半径。这样我们得到了两个子超球体，和KD树里面的左右子树对应

3. 对于这两个子超球体，递归执行步骤2). 最终得到了一个球树

KD树和球树类似，主要区别在于球树得到的是节点样本组成的最小超球体，而KD得到的是节点样本组成的超矩形体，这个超球体要与对应的KD树的超矩形体小，这样做最近邻搜索的时候，可以避免一些无谓的搜索。

球树搜索最近邻

使用球树找出给定目标点的最近邻方法是首先自上而下贯穿整棵树找出包含目标点所在的叶子，并在这个球里找出与目标点最邻近的点，这将确定出目标点距离它的最近邻点的一个上限值，然后跟KD树查找一样，检查兄弟结点，如果目标点到兄弟结点中心的距离超过兄弟结点的半径与当前的上限值之和，那么兄弟结点里不可能存在一个更近的点；否则的话，必须进一步检查位于兄弟结点以下的子树。

检查完兄弟节点后，向父节点回溯，继续搜索最小邻近值。当回溯到根节点时，此时的最小邻近值就是最终的搜索结果。

从上面的描述可以看出，KD树在搜索路径优化时使用的是两点之间的距离来判断，而球树使用的是两边之和大于第三边来判断，相对来说球树的判断更加复杂，但是却避免了更多的搜索，这是一个权衡。

 

KNN算法的扩展

KNN算法小结

• 理论成熟，思想简单，既可以用来做分类也可以用来做回归

• 可用于非线性分类

• 训练时间复杂度比支持向量机之类的算法低，仅为

• 和朴素贝叶斯之类的算法比，对数据没有假设，准确度高，对异常点不敏感

• 由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合

• 该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分

• 计算量大，尤其是特征数非常多的时候

• 样本不平衡的时候，对稀有类别的预测准确率低

• KD树，球树之类的模型建立需要大量的内存

• 使用懒散学习方法，基本上不学习，导致预测时速度比起逻辑回归之类的算法慢

• 相比决策树模型，KNN模型可解释性不强