0. 导论

本文简单介绍梳理一下KNN理论知识.本文的重点其实是kd tree的构建和查找算法,但是算法最好的学习方法是coding出来,因此本文最后给出参考资料.KNN是一种思想很简单的分类算法.它不算一个标准的统计模型,更像是一个纯粹基于数据的算法,它没有类似于感知机那种优化迭代的学习超参数过程.

1. “模型”

其实没有严格的模型说法,按照它的过程来说: 就是你有一堆(xi,y)的训练数据,一个新的x需要分类,对于KNN来说就是寻找x在这一堆数据中最近的k个点,然后统计这k个点中y的类别个数,谁多,x自然而然就是那个类别

2. 距离度量

$x_i=(x_i^{(1)},x_i^{(2)},....,x_i^{(n)})$ , $x_j=(x_j^{(1)},x_j^{(2)},....,x_j^{(n)})$ $$L_p(x_i,x_j)=(\sum _{l=1}^n|x_i^l-x_j^l{|}^p{)}^{\frac{1}{p}}$$

p = 2时为欧式距离,为我们常用的公式,其他公式不再展开

3. k的选择

k值优点缺点模型较大预测误差减少训练误差大模型更简单较小预测误差偏大训练误偏小模型更复杂(过拟和) 通常用交叉验证来选取k值

4. 分类决策

其实就是找到的最近的k个里面,类别最多的就是当前需要预测点的类别—多数表决多数表决等价与经验风险最小化

5. kd树

kNN算法核心就是,快速从tarin_set里面找到距离target最近的点普通线性遍历,在数据量大时速度很慢,速度O(N),很慢因此这里提出了一种基于二叉树的数据结构,达到快速查找的目的具体实现参考代码,因为只是文字叙述没什么用

细节注意:

kd的k指的是数据的维度,不是KNN的k直观上看,kdd加速的原因是因为其数据结构(二叉树),如果确定object到某一个节点距离已经很大了,那么这个节点往下的枝叶就不需要遍历.构造kd树时,注意树层数和数据维度无关,他会递归一直划分下去,直到数据集为空,不能再划分(有点像减枝).其kd树的遍历代码实现类似与树的中序遍历(不过遍历同时有减枝),可以自行对比,方便理解里面的递归写法.看到另一种角度的解释(寻找速度更快原因):参考        ~~~~~~       类比“二分查找”： 给出一组数据： [9 1 4 7 2 5 0 3 8]， 要查找8。如果挨个查找（线性扫描），那么将会把数据集都遍历一遍。而如果排一下序那数据集就变成了： [0 1 2 3 4 5 6 7 8 9]， 按前一种方式我们进行了很多没有必要的查找， 现在如果我们以5为分界点， 那么数据集就被划分为了左右两个“簇” [0 1 2 3 4]和[6 7 8 9]。        ~~~~~~       因此， 根本久没有必要进入第一个簇，可以直接进入第二个簇进行查找。把二分查找中的数据点换成k维数据点， 这样的划分就变成了用超平面对k维空间的划分。空间划分就是对数据点进行分类， “挨得近”的数据点就在一个空间里面。

5.1 代码

请自行参考

复现经典：《统计学习方法》第 3 章 k 近邻法