定义：

给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最临近的k个实例，这k个实例的多数属于某个类，就把该输入实例分为这个类。

k-NN的三要素：

距离度量
k值的选择
分类决策规则

距离度量

在采用不同距离时，距离某个点最近的点是不同的，这里的距离和范数的概念是一样的，比如在采用二范数和四范数这两种范数时就会发生该种情况。

k值的选择

k值的选择会对k-NN法的结果产生不同的影响。
当k值过小时，整体模型会变得较复杂，容易产生过拟合现象。
当k值过大时，整体模型会变得过于简单，这时与输入实例较远的点也会对结果产生影响。
在实际应用中，k值一般选取一个较小的数值。通常采用交叉验证法来选取最优的k值。

分类决策规则

如果要使误分类率最小即经验风险最小，就要使准确率最高，所以多数表决规则等价于经验风险最小化。

k-NN法的实现：kd树

k近邻法最简单的实现方法是线性扫描，这时要计算输入实例与每个实例的距离。当训练集很大时，计算非常耗时。所以为了提高k-NN法的效率，可以考虑使用特殊的结构存储训练数据，以减少计算距离的次数，比如kd树方法。

构造kd树

kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。kd树是二叉树，表示对k维空间的一个划分(partition)。构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间切分，构成一系列的k维超矩形区域。kd树的每个节点对应于一个k维超矩形区域。
##构造平衡kd树
实例：
给定一个二维空间数据集：
T={(2,3)T,(5,4)T,(9,6)T,(4,7)T,(8,1)T,(7,2)T}
根节点对应包含数据集T的矩形，选择x(1)轴，6个数据点的x(1)坐标的中位数是7，以平面x(1)=7将空间分为左，右两个子矩形（子节点）；接着，左矩形以x(2)=4分为两个子矩形，右矩形以x(2)=6分为两个子矩形，如此递归，最后得到如下的特征空间和kd树。

搜索kd树

最近邻法：给定一个目标点，搜索其最近邻。首先找到包含目标点的叶节点；然后从该叶节点出发，依次回退到父节点；不断查找与目标点最临近的节点，当确定不可能存在更近的节点时终止。
（k近邻法类似）