【统计学习方法】 k近邻法

k近邻算法

算法(k近邻法):

输入:训练数据集:

                         【统计学习方法】 k近邻法

 

输出:实例x所属的类y

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

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

                        【统计学习方法】 k近邻法

 

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

 

k近邻模型

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

 

距离度量

设特征空间X是n维实数向量空间R^n,【统计学习方法】 k近邻法的Lp距离定义为:

 

                             【统计学习方法】 k近邻法

 

p=2时,称为欧氏距离(Euclidean Distance):

                              【统计学习方法】 k近邻法

 

 p=1时,称为曼哈顿距离(Manhattan Distance):

                           【统计学习方法】 k近邻法

 

p=∞时,为各坐标距离的最大值:

                            【统计学习方法】 k近邻法

 

 

k值选择

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

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

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

 

分类决策规则

 往往采用多数表决

 

k近邻算法的实现:kd树

构造kd树

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

算法(构造平衡kd树)

输入:k维空间数据集【统计学习方法】 k近邻法 

输出:kd树

(1)开始:构造根节点,根节点对应于包含T的k维空间超矩形区域。

选择【统计学习方法】 k近邻法为坐标轴,以T中所有实例的【统计学习方法】 k近邻法坐标的中位数为切分点,将根节点对应的超矩形区域切分为两个子区域。切分通过切分点并与坐标轴【统计学习方法】 k近邻法垂直的超平面实现。

 

由根节点生成深度为为1的左右节点:左子节点对应坐标【统计学习方法】 k近邻法小于切分点的子区域,右子节点对应坐标【统计学习方法】 k近邻法大于切分点的子区域

 

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

(2)重复:对深度为 j 的节点,选择【统计学习方法】 k近邻法为切分的坐标轴,l = j(mod k)+ 1,以该节点的区域中所有实例的【统计学习方法】 k近邻法坐标的中位数为切分点,将该节点对应的超矩形区域切分为两个子区域。切分通过切分点并与【统计学习方法】 k近邻法坐标轴垂直的超平面实现。

 

 由根节点生成深度为为 j 的左右节点:左子节点对应坐标【统计学习方法】 k近邻法小于切分点的子区域,右子节点对应坐标【统计学习方法】 k近邻法大于切分点的子区域

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

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

 

 搜索kd树

算法(用kd树的最邻近搜索)

输入:已构造的kd树, 目标点x

输出:x的最近邻

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

(2)以此叶节点为“当前最近点”

(3)递归的向上回退,每个节点进行如下操作:

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

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

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

  如果不相交,向上回退。

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

 

上一篇:MySQL基础知识—约束(重点)


下一篇:KD 树总结