k 近邻法（k-nearest neighbor, k-NN）是一种基本分类与回归方法。
k 近邻算法
k 近邻算法简单、直观：给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最临近的 k 个 实例，这 k 个实例的多数属于某个类，就把该输入实例分为这个类。
k 近邻法的特殊情况是 k=1 的情形，称为最近邻算法。
k 近邻模型
k 近邻法使用的模型实际上对应于对特征空间的划分。模型由三个基本要素——距离度量、k 值的选择和分类决策规则决定。
距离度量
特征空间中两个实例点的距离是两个实例点相似程度的反映。k 近邻模型的特征空间一般是 n 维实数向量空间 Rn。使用的距离是欧式距离，但也可以是其他距离。
k 值的选择
k 值的选择会对 k 近邻法的结果产生重大影响。
如果选择较小的 k 值，就相当于用较小的领域中的训练实例进行预测，“学习”的近似误差（approximation error）会减小，只有输入实例较近的（相似的）训练实例才会对预测结果起作用。但缺点是“学习”的估计误差（estimation error）会增大，预测结果会对近邻的实例点非常敏感。如果近邻的实例点恰好是噪声，预测就会出错。换句话说，k 值的减小就意味着整体模型变得复杂，容易发生过拟合。
如果选择较大的 k 值，就相当于用较大领域中的训练实例进行预测。其有点是可以减小学习的估计误差。但缺点是学习的近邻误差会增大。这时与输入实例较远的（不相似的）训练实例也会对预测起作用，使预测发生错误。k 值的增大就意味着整体的模型变得简单。
在应用中，k 值一般取一个比较小的数值。通常采用交叉验证法来选取最优的 k 值。
分类决策规则
k 近邻法的分类决策规则往往是多数表决，即由输入实例的 k 个近邻的训练实例中的多数类决定输入实例的类。
k 近邻法的实现：kd 树
k 近邻法最简单的实现方法是线性扫描（linear scan）。这时计算输入实例与每一个训练实例的距离。当训练集很大时，计算非常耗时，这种方法是不可行的。
为了提高 k 近邻搜索的效率，可以考虑使用特殊的结构存储训练数据，以减少计算距离的次数。
构造 kd 树
kd 树是一种对 k 维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。kd 树是二叉树，表示对 k 维空间的一个划分（partition）。构造 kd 树相当于不断地用垂直于坐标轴的超平面将 k 维空间切分，构成一系列的 k 维超矩形区域。kd 树的每个结点对应于一个 k 维超矩形区域。
构造 kd 树的方法如下：构造根结点，使根结点对应于 k 维空间中包含所有实例点的超矩形区域；通过下面的递归方法，不断地对 k 维空间进行切分，生成子节点。在超矩形区域（结点）上选择一个坐标轴和在此坐标轴上的一个切分点，确定一个超平面，这个超平面通过选定的切分点并垂直于选定的坐标轴，将当前超矩形区域切分为左右两个子区域（子节点）；这时，实例被分到两个子区域。这个过程直到子区域内没有实例时终止（终止时的结点为叶结点）。在此过程中，将实例保存在相应的结点上。
通常，依次选择坐标轴对空间切分，选择训练实例点在选定坐标轴上的中位数（median）为切分点，这样得到的 kd 树是平衡的。注意，平衡的 kd 树搜索时的效率未必是最优的。
搜索 kd 树
给定一个目标点，搜索其最近邻。首选找到包含目标点的叶结点；然后从该叶结点出发，依次回退到父节点；不断查找与目标点最邻近的结点，当确定不可能存在更近的结点时终止。这样搜索就被限制在空间的局部区域上，效率大为提高。
包含目标点的叶结点对应包含目标点的最小超矩形区域。依次叶结点的实例点作为当前最近点。目标点的最近邻一定在以目标点为中心并通过当前最近点的超球体的内部。然后返回当前结点的父节点，如果父节点的另一子节点的超矩形区域与超球体相交，那么在相交的区域内寻找与目标点更近的实例点。如果存在这样的点，将此点作为新的当前最近点。算法赚到更上一级的父节点，继续上述过程。如果父节点的另一子节点的超矩形区域与超球体不相交，或不存在比当前最近点更近的点，则停止搜索。
