k 近邻法

　　k 近邻法(k-nearest neighbor, k-NN)是一种基本分类与回归方法．k 近邻法的输入为实例的特征向量，对应于特征空间的点；输出为实例的类别，可以取多类．k 近邻法假设给定一个训练数据集，其中的实例类别已定，分类时，对新的实例，根据其 k 个最近邻的训练实例的类别，通过多数表决等方式进行预测．
　　k 近邻法实际上利用训练数据集对特征向量空间进行划分，并作为其分类的模型．k 值的选择，距离度量以及分类决策规则是 k 近邻法的三个基本要素.

算法(k 近邻法)

　　输入: 训练数据集

　　其中，为实例的特征向量, 为示例的类别，;
　　实例特征向量

　　输出: 实例 所属的类 y;
　　(1) 根据给定的距离度量，在训练集 T 中找出与 x 最邻近的 k 个点，涵盖这 k 个点的 x 的邻域记作 ;
　　(2) 在 中根据分类决策规则(如多数表决)决定 x 的类别 y:

　　上式中， 为指示函数，即当 时 为 1, 否则 I 为 0.
　　k 近邻法的特殊情况是 的情形，称为最近邻法．对于输入的实例点(特征向量) x, 最近邻法将训练数据集中与 x 最邻近点的类作为 x 的类．

k 近邻模型

　　k 近邻法使用的模型实际上对应于对特征空间的划分．
　　模型由三个基本要素: 距离度量, k 值的选择和分类决策规则 决定.

模型

　　在 k 近邻法中，当训练集，距离向量(如欧式距离), k 值及分类决策规则(如多数表决)确定后，对于任何一个新的输入实例，它所属的类唯一地确定．
　　特征空间中，对于每个训练实例 , 距离该点比其他点更近的所有点组成一个区域，叫做单元(cell).每个训练实例点拥有一个单元，所有训练实例点的单元构成对特征空间的一个划分，最近邻法将实例 的类 作为其单元中所有点的类标记(class label). 这样，每个单元的实例点的类别是确定的．

距离度量

　　特征空间中两个实例点的距离是两个实例点相似程度的反映，k 近邻模型的特征空间一般是 n 维实数空间 . 使用的距离是欧式距离,其他的距离度量方式有 更为一般的 距离( distance) 或者 闵可夫斯基距离(Minkowski distance), 余弦相似度(Cosine similarity).

　　设特征空间 是 n 维实数向量空间 ,
　　, , 的 距离(闵可夫斯基距离)定义为

　　这里 . 当 时，　称为欧式距离(Euclidean distance), 即

　　当 时，称为曼哈顿距离(Manhattan distance), 即

　　当 时，它是各个坐标距离的最大值，即

　　余弦相似度衡量的是连个向量之间的夹角大小，通过夹角的余弦值表示结果，因此两个向量A, B(推广到 n 维空间中)的余弦相似度为

　　上值越接近 1, 表示两个向量越相似.

　　 距离度量的是两点之间的距离，两点距离越接近也就越相似，但是从几何意义上讲，底边固定的情况下，其顶角可以取 中任意值．即当两个向量方向相反，但是模长很小时，仍会归为一类．
　　余弦相似度度量的是向量之间的方向差异，所以具体使用哪种度量方法要结合实际应用，侧重于方向上的度量应使用余弦相似度，即不侧重其数值的大小；如果侧重于数值的大小而不侧重于方向，应使用 距离度量.

k 值的选择

　　k 的选择对 k 近邻法的分类结果影响很大．
　　当 k 的值较小时，则只用输入实例的较小邻域中的训练实例进行预测，学习的近似误差(approximation error)会减小，但是学习的估计误差(estimation error)会增大，即分类结果对邻域中的实例点非常敏感，如果邻近的分类点中有噪声，那么预测结果就会出错．即 k 值的减小意味着整体模型变得复杂，容易发生过拟合．
　　当 k = 1 时，则训练数据中与输入实例最近似的向量为预测结果．

　　当 k 的值较大时，则相当于使用输入实例的较大邻域中的训练实例进行预测．学习的估计误差(estimation error)会减小，但是近似误差(approximation error)会增大．与输入实例较远的实例也会影响预测结果. k 值的增大意味这整体模型变得简单，容易欠拟合．
　　当 k = N 时，那么无论输入实例是什么，都会简单的预测为训练实例中最多的类，这时的模型过于简单．

　　在应用中，k 值一般取一个比较小的数值．通常采用交叉验证法来选取最优的 k 值．

分类决策规则

　　k 近邻法中的分类决策规则多采用多数表决，即由输入实例的 k 个邻近的训练实例中的多数类决定输入实例的类．
　　多数表决规则(majority voting rule)有如下解释: 如果分类的损失函数为 0-1损失函数，分类函数为

　　那么误分类的概率为

　　对于给定的实例 , 其最近邻的 k 个训练实例点构成集合 . 如果涵盖 的区域的类别是 , 那么误分类率是

　　要使误分类最小即经验风险最小，就要使 最大，所以多数表决规则等价于经验风险最小化.

k 近邻法的实现: kd Tree

　　kd 树是二叉树，表示对 k 维空间的一个划分．构造 kd 树相当于不断地用垂直于坐标轴的超平面将 k 维空间切分，构成一系列的 k 维空间超矩形区域， kd 树的每个结点对应于 k 维超矩形区域.

构造 kd 平衡树

　　输入: k 维空间数据集
　　输出：kd 树

• 开始: 构造根结点，根结点对应于包含 T 的 k 维空间的超矩形区域
  选择为坐标轴，以 T 中所有实例的 坐标的中位数为切分点，将根结点对应的超矩形区域切分为两个子区域．切分由通过切分点并与坐标轴 垂直的超平面实现.
  由根结点生成深度为 1 的左右子结点: 左子结点对应坐标 小于切分点的子区域，右子结点对应于坐标 大于切分点的子区域
  将落在切分超平面上的实例点保存在根结点
• 重复: 对深度为 j 的子结点．选择 为切分的坐标轴，, 以该结点的区域中所有实例的 坐标的中位数为切分点，将该结点对应的超矩形区域切分为两个子区域．切分由通过切分点并与坐标轴 垂直的超平面实现．
  由该结点生成深度为 j + 1 的左右子结点．
• 直到连个子区域没有实例存在时停止．从而形成 kd 树的区域划分

搜索 kd 树

　　输入: 已构造的 kd 树；目标点 x
　　输出: x 的最近邻．

• 在 kd 树中找出包含目标点 x 的子结点: 从根结点出发，递归地向下访问 kd 树．直到子结点为叶结点为止.
• 以此叶结点为 当前最近点
• 递归地向上回退在每个结点做如下操作
  a. 如果该结点保存的实例点比当前最近点距离目标点更近，则以该实例点为 当前最近点
  b. 当点最近点一定存在于该结点一个子结点对应的区域．检查该子结点的父结点的另一子结点对应的区域是否有更近的点，检查另一子结点对应的区域是否与当前最近点间的距离为半径的超球体相交．
  如果相交，可能在另一个子结点对应的区域内存在距离目标点更近的点，移动到另一个子结点，接着，递归地进行最近邻搜索．
  如果不相交，向上回退．
• 当回退到根结点时，搜索结束．最后的当前 当前最近点　即为 x 的最近点