k近邻法：假设输入空间中每个点对应一个分类，可以依据训练数据，将输入空间进行区域划分，对于一个新的测试数据，K近邻法使用距离该测试实例点最近的k个训练数据，取训练数据中类别数最多的为该实例的类别，即在该区域内使用多数表决原则。

算法

给定训练数据集X 以{数据：类别}的形式展示，其中数据为N维实数空间的向量，对于目标数据M，有输入数据X，KNN模型将输入M所对应的类别。
换句话说，目标数据M的类别等同于在M附近的K个训练数据的类别中数量最大的。
极端的情况下，k=1， 即取M最近的1个数据的类别，作为该输入的类别；
另一种极端是 k=N，即取所有训练数据中类别最大的类，等同于没有做区域划分。
因此，考虑k值的选择，过小会导致模型过于复杂，易出现过度拟合，过大则造成模型精度不够，合适的k值可使用交叉验证的方法来确定。

kd树

1. 首先构造根节点，根节点包含空间中所有的点；
2. 选择一个超平面（X1的中位数）对1进行切割；
3. 生成的两个区域lt为X1小于切分点的区域，rt为X1大于切分点的区域；
4. 重复上述动作，直到子区域不能再划分。

搜索

使用kd树进行搜索的算法比较精妙，这里写不下就不写了。