k近邻法是基本的分类和回归方法，基本做法是：对给定的训练实例点和输入实例点，首先确认输入实例点的k个最近邻训练实例点，然后根据k个近邻点多数表决，确定输入实例点的类别。
k近邻法不具有显式的学习过程。（利用训练数据对特征空间进行划分）
k近邻对应于基于训练数据集对特征空间的一个划分。在k近邻算法中，当训练集、距离度量、k值及分类决策规则确定后，结果唯一确定。
k近邻法的三要素¶
距离度量：常用欧氏距离或定长的Lp范数（也即闵可夫斯基距离）
k值的选择：k太小，模型越复杂（如果近似误差与估计误差的和衡，通常使用交叉验证选择k）
分类决策规则：常用多数表决，对应经验风险最小化。
kd树（kd-tree）¶
kd树是用于在该k维空间数据的一种数据结构，这里的k与k近邻法的k意义不同。
kd树是一种便于对k维空间中的数据进行快速检索的数据结构。
解决的问题：快速搜索k个最近邻点，利用kd树可以省去对大部分数据点的检索，从而减少计算量。
kd树是一叉树，表示对k维空间的一个划分，其每个结点，对应于k维空间划分中的一个超矩形区域。
kd树的构造算法¶
输入：k维空间数据集 $ T = \{x_1, x_2, ..., x_N\} $，其中 $ x_i = (x_i^{(1)}, x_i^{(2)}, ..., x_i^{(k)})^T $，$ i=1,2,...,N $
输出：kd树
(1) 开始：构造根结点，根结点对应包含所有k维空间的点的矩形区域
- 选择 $ x^{(j)} $ 为坐标轴，以T中所有实例的 $ x^{(j)} $ 的中位数为切分点，将根结点区域划分为两个子区域。
- 由通过切分点并与 $ x^{(j)} $ 轴垂直的超平面实现。
- 由根结点生成左右子结点，左结点对应 $ x^{(j)} $ 小于切分点的子区域；右——大于——；
- 将落在超平面上的实例归入左子树或右子树。
(2) 重复：对深度为j的结点，选择 $ x^{(l)} $ 作为切分坐标轴，$ l = j \mod k + 1 $，以该结点的区域中所有实例的 $ x^{(l)} $ 值的中位数。
停止条件：两个子区域中均没有实例存在时。
搜索kd树¶
给定目标点，如何依据kd树搜索最近邻？
首先找到包含目标点的叶结点，从该叶结点出发，依次回退到父结点，不断查找与目标点最近的结点，直到没有可能在更近的结点时终止。