k近邻算法总结

k-nn在轨迹数据采样率合适的情况下，用于路网映射的子流程中；下面将介绍k邻近算法的基本概念和算法实现方式；
1.对于给定的训练集合{(x1,y1),(x2,y2）.......(xn,yn)}其中，y为不同的类别，而k邻近算法所起的作用为，对于给定的训练集合，当给定新的输入x时，通过k邻近算法为其分配一个对应的类；

2.一个k邻近模型有三个要素；

1）距离的度量

对于给定的x要求出他到达最近k个训练点的距离，然后根据这k个点，依据某种决策规则，来预测x的类别；多数情况下取得是x-xi的二范数，值得注意的是，不同度量的选取会影响k个近邻点的选取

2）k值得选取
如上，k的选择会对k近邻发的结果产生较大的影响，具体表现在：
k较小时，近似误差小，估计误差较大
k较大时，近似误差大，估计误差较小

3）分类决策规则
k近邻算法的分类决策往往是多数表决，也就是把输入实例的k个近邻的训练实例中的多数类决定实例的类。

3.k近邻算法的实现：kd树
kd树是一种类似于R树的属性结构，但是我觉得他比R树要简单，他的具体构造过程就是先选取一个和训练集x的维数k相同的超平面矩阵，首先，根结点是包含所有训练集的超平面矩阵，然后，选取x某个维的中值，来进行划分，分为左右子结点，再对左右子结点进行递归操作，指导无法再分为止。

下面我将介绍两种kd树常用的算法：

1）构造平衡kd树：
输入：k维训练集
输出：kd树

Step1：构造根节点，其对应包含所有训练集的k为超矩阵区域
step2：对于给定的结点，选取x的维的中值，在该纬度上，进行垂直划分，得到左右结点
step3：对于左右子结点进行递归操作，终止条件为不可再分时

2）用kd树实现最近邻搜索
输入：kd树，目标点x
输出：x的最近邻

step1：在kd树中找到包含x的叶子结点，从根结点出发，向下访问kd树，到达叶子结点为止
step2：把得到的叶子结点作为当前最近点。
step3：递归向上回退，执行以下操作：
1.如果结点所保存的实例点比当前最近点更近，那么把改点作为当前最近点
2.当前最近的点一定存在于该节点的一个子结点对应的区域，检查该区域的另外一个子节点是否有更近的点，并检查以目标点和当前最近的点的距离为半径的超球体相交，如果相交，那么可能纯在另外一个子节点对应区域内存在距离目标点更近的点，移动到另外一个子节点，然后进行递归的最近邻搜索
如过不相交，则向上回退
step4：当回退到根节点时，搜索结束，最后的‘当前最近点’即为x的最近邻点