k近邻算法

算法（k近邻法）：

输入：训练数据集：

输出：实例x所属的类y

（1）根据给定的距离度量，在训练集中找到距离x最近的k个点，涵盖这k个点的x的邻域记为Nk(x)

（2）在Nk(x)中根据分类决策规则（如多数表决）决定x的类别y

 k = 1时称为最近邻法。 k近邻法没有显示的学习过程。

k近邻模型

k邻近法使用的模型对应于特征空间的划分。 当模型的三要素（距离度量、k值选择、和分类决策规则）确定后， 对于任何一个实例，它所属的类也确定下来。

距离度量

设特征空间X是n维实数向量空间R^n，的Lp距离定义为：

p=2时，称为欧氏距离（Euclidean Distance）：

 p=1时，称为曼哈顿距离（Manhattan Distance）：

p=∞时，为各坐标距离的最大值：

k值选择

k值越小， 估计误差越大， 对近邻的实例越敏感， 整体模型变得复杂， 容易发生过拟合；

k值越大， 近似误差越大， 模型变得简单， 容易发生欠拟合。

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

分类决策规则

 往往采用多数表决

k近邻算法的实现：kd树

构造kd树

kd树是一种对k维空间中实例点进行储存以便对其进行快速检索的树形数据结构。kd树是二叉树，表示对k维空间的一个划分。构造kd树相当于不断用垂直坐标轴的超平面将k维空间切分， 构成一系列k维超矩形区域。kd树的每个节点对应一个超矩形区域。

算法（构造平衡kd树）

输入：k维空间数据集 

输出：kd树

（1）开始：构造根节点，根节点对应于包含T的k维空间超矩形区域。

选择为坐标轴，以T中所有实例的坐标的中位数为切分点，将根节点对应的超矩形区域切分为两个子区域。切分通过切分点并与坐标轴垂直的超平面实现。

由根节点生成深度为为1的左右节点：左子节点对应坐标小于切分点的子区域，右子节点对应坐标大于切分点的子区域

 将落在切分超平面上的实例点保存为根节点。

（2）重复：对深度为 j 的节点，选择为切分的坐标轴，l = j（mod k）+ 1，以该节点的区域中所有实例的坐标的中位数为切分点，将该节点对应的超矩形区域切分为两个子区域。切分通过切分点并与坐标轴垂直的超平面实现。

 由根节点生成深度为为 j 的左右节点：左子节点对应坐标小于切分点的子区域，右子节点对应坐标大于切分点的子区域

将落在切分超平面上的实例点保存为该节点。

（3）直到两个子区域没有实例存在时停止。从而形成kd树的划分。

 搜索kd树

算法（用kd树的最邻近搜索）

输入：已构造的kd树， 目标点x

输出：x的最近邻

（1）在kd树中找出包含目标点x 的叶节点：从根节点出发，递归向下访问kd树。若目标点x当前维的坐标小于切分点坐标，则移动当左子节点，否则移动到右子节点。直到子节点为叶节点为止。

（2）以此叶节点为“当前最近点”

（3）递归的向上回退，每个节点进行如下操作：

　　（a）如果该节点保存的实例点比当前距离目标更近，则以该实例点为“当前最近点”

　　（b）当前最近点一定存在于该节点的一个子节点对应区域。检查该子节点的父节点的另一个子节点对应的区域是否有更近的点。具体地， 检查另一子节点对应的区域是否以目标点为球心、目标点与“当前最近点”间的距离为半径的超球体相交。

　　如果相交， 可能在另一个节点对应区域存在更近点， 移动到另一个子节点。接着，递归地进行最近邻搜索：

　　如果不相交，向上回退。

（4）回退到根节点时，搜索结束。最后的 “当前最近点”即为x的最近邻点。