k近邻
给定一个训练集，对新的实例，在训练集中找到与该实例最邻近的k个实例，这k个实例属于哪个类的最多，那它就属于哪个类。
k近邻模型
三要素：距离度量、k、分类抉择规则
- 距离度量：如感知机篇提到的L-P范数，里面向量的各种范数可以理解为距离，如p=2就是欧氏距离，也就是空间中的距离，P=1为曼哈顿距离。
- k值得选择：一般取一个较小的值，如果接近于N，那约为线性查找。通常用交叉验证选取k。
实现：kd树
不断用垂直于坐标轴的超平面将k维空间切分，构成一系列k维超矩形区域。
构造
输入：数据点集Data-set和其所在的空间Range(初始值为)
输出：Kd，类型为k-d tree
1. If Data-set为空，则返回空的k-d tree
2. 调用节点生成程序：
(1). 确定split域：对于所有描述子数据（特征矢量），统计它们在每个维上的数据方差。
假设每条数据记录为64维，可计算64个方差。挑选出最大值，对应的维就是split域的值。
数据方差大表明沿该坐标轴方向上的数据分散得比较开，在这个方向上进行数据分割有较好的分辨率；
(2).确定Node-data域：数据点集Data-set按其第split域的值排序。位于正中间的那个数据点被选为Node-data。
此时新的Data-set = Data-set \ Node-data（除去其中Node-data这一点）。
3. dataleft = {d属于Data-set && d[split] ≤ Node-data[split]}
Left_Range = {Range && dataleft}
dataright = {d属于Data-set && d[split] > Node-data[split]}
Right_Range = {Range && dataright}
4. left = 由(dataleft，Left_Range)建立的k-d tree，即递归调用createKDTree(dataleft,Left_Range).并设置left的parent域为Kd；
right = 由(dataright，Right_Range)建立的k-d tree，即调用createKDTree(dataleft,Left_Range).并设置right的parent域为Kd。
注意这里的k不是三要素中的k值，是数据的维数即
Node-data:数据实例，k维向量。
split:以k维中的哪一维当做分割轴
Range:该节点代表的空间，二维平面中即为矩形。
搜索
输入：Kd， //k-d tree类型
target //查询数据点
输出：nearest //最邻近数据点
dist //最邻近数据点和查询点间的距离
1. If Kd为NULL，则设dist为infinite并返回
2. //进行二叉查找，生成搜索路径
Kd_point = &Kd; //Kd-point中保存k-d tree根节点地址
nearest = Kd_point -> Node-data; //初始化最近邻点
while(Kd_point)
push(Kd_point)到search_path中； //search_path是一个堆栈结构，存储着搜索路径节点指针
/*** If Dist(nearest，target) > Dist(Kd_point -> Node-data，target)
nearest = Kd_point -> Node-data; //更新最近邻点
Max_dist = Dist(Kd_point，target); //更新最近邻点与查询点间的距离 ***/
s = Kd_point -> split; //确定待分割的方向
If target[s] <= Kd_point -> Node-data[s] //进行二叉查找
Kd_point = Kd_point -> left;
else
Kd_point = Kd_point ->right;
nearest = search_path中最后一个叶子节点; //注意：二叉搜索时不比计算选择搜索路径中的最邻近点，这部分已被注释
dist = Dist(nearest，target); //直接取最后叶子节点作为回溯前的初始最近邻点
3. //按搜索路径回溯查找，中间可能会加一些可能的点
while(search_path != NULL)
back_point = 从search_path取出一个节点指针; //从search_path堆栈弹栈
s = back_point -> split; //确定分割方向
If Dist(target[s],back_point -> Node-data[s]) < dist //判断还需进入的子空间,相反空间
If target[s] <= back_point -> Node-data[s]
Kd_point = back_point -> right; //如果target位于左子空间，就应进入右子空间
else
Kd_point = back_point -> left; //如果target位于右子空间，就应进入左子空间
将Kd_point压入search_path堆栈;
If Dist(nearest,target) > Dist(Kd_Point -> Node-data,target)
nearest = Kd_point -> Node-data; //更新最近邻点
dist = Dist(Kd_point -> Node-data,target); //更新最近邻点与查询点间的距离
