第3章 k近邻法（k-nearest neighbor，k-NN）

分类问题中的k近邻方法。

• 输入：实例的特征向量，对应于特征空间的点
• 输出：实例的类别，可以取多类。

k近邻法假设给定一个训练数据集，其中的实例类别已定。分类时，对新的实例，根据其k个最近邻的训练实例的类别，通过多数表决等方式进行预测

基本要素：k值的选择、距离度量及分类决策规则

1968年由Cover和Hart提出

3.1 算法

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

3.2 模型

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

3.2.1 模型

• 单元（cell）：特征空间中，对每个训练实例点xi，距离该点比其他点更近的所有点组成一个区域。
• 划分：所有训练实例点的单元。
• 最近邻法将实例xi的类yi作为其单元中所有点的类标记（class label）。

3.2.2 距离度量(待补充)

特征空间中两个实例点的距离是两个实例点相似程度的反映。

• 欧氏距离
• 曼哈顿距离
• 切比雪夫距离
• 闵可夫斯基距离（Minkowski distance）

当p=1时，称为曼哈顿距离（Manhattan distance）

这里p≥1。当p=2时，称为欧氏距离（Euclidean distance），即

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

 图3.2给出了二维空间中p取不同值时，与原点的Lp距离为1（Lp=1）的点的图形。

• 标准划欧氏距离
• 余弦距离
• 汉明距离
• 杰卡德距离
• 马氏距离

3.2.3 k值的选择

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

交叉验证：交叉验证的基本想法是重复地使用数据；把给定的数据进行切分，将切分的数据集组合为训练集与测试集，在此基础上反复地进行训练、测试以及模型选择。

3.2.4 分类决策规则

多数表决规则（majority voting rule）

等价于经验风险最小化。

3.3 k近邻法的实现：kd树

3.3.1 构造kd树

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

• 构造根结点，使根结点对应于k维空间中包含所有实例点的超矩形区域；
• 通过下面的递归方法，不断地对k维空间进行切分，生成子结点。
• 在超矩形区域（结点）上选择一个坐标轴和在此坐标轴上的一个切分点，确定一个超平面，这个超平面通过选定的切分点并垂直于选定的坐标轴，将当前超矩形区域切分为左右两个子区域（子结点）；
• 这时，实例被分到两个子区域。这个过程直到子区域内没有实例时终止（终止时的结点为叶结点）。在此过程中，将实例保存在相应的结点上。

通常，依次选择坐标轴对空间切分，选择训练实例点在选定坐标轴上的中位数（median）[插图]为切分点，这样得到的kd树是平衡的。注意，平衡的kd树搜索时的效率未必是最优的。

 例3.2 给定一个二维空间的数据集：

解 根结点对应包含数据集T的矩形，选择x(1)轴，6个数据点的x(1)坐标的中位数是7注2，以平面x(1)=7将空间分为左、右两个子矩形（子结点）；接着，左矩形以x(2)=4分为两个子矩形，右矩形以x(2)=6分为两个子矩形，如此递归，最后得到如图3.3所示的特征空间划分和如图3.4所示的kd树。

3.3.2 搜索kd树

给定一个目标点，搜索其最近邻。首先找到包含目标点的叶结点；然后从该叶结点出发，依次回退到父结点；不断查找与目标点最邻近的结点，当确定不可能存在更近的结点时终止。这样搜索就被限制在空间的局部区域上，效率大为提高。

例3.3 给定一个如图3.5所示的kd树，根结点为A，其子结点为B，C等。树上共存储7个实例点；另有一个输入目标实例点S，求S的最近邻。

解 首先在kd树中找到包含点S的叶结点D（图中的右下区域），以点D作为近似最近邻。真正最近邻一定在以点S为中心通过点D的圆的内部。然后返回结点D的父结点B，在结点B的另一子结点F的区域内搜索最近邻。结点F的区域与圆不相交，不可能有最近邻点。继续返回上一级父结点A，在结点A的另一子结点C的区域内搜索最近邻。结点C的区域与圆相交；该区域在圆内的实例点有点E，点E比点D更近，成为新的最近邻近似。最后得到点E是点S的最近邻。

最后

以上就是傲娇冬天为你收集整理的[DataWhale]统计学习方法-打卡-Day3第3章 k近邻法（k-nearest neighbor，k-NN）3.1 算法3.2 模型3.3 k近邻法的实现：kd树的全部内容，希望文章能够帮你解决[DataWhale]统计学习方法-打卡-Day3第3章 k近邻法（k-nearest neighbor，k-NN）3.1 算法3.2 模型3.3 k近邻法的实现：kd树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。