机器学习导论-第3章k-最近邻和k-d树算法.ppt

1、第第3章章 k-最近邻和最近邻和k-d树算法树算法n掌握掌握k-最近邻法的基本原理。最近邻法的基本原理。n熟悉熟悉k-最近邻法的三个关键要素和优缺点。最近邻法的三个关键要素和优缺点。n熟悉熟悉k的取值对的取值对k-最近邻法的影响因素。最近邻法的影响因素。n熟悉熟悉k-d树的构建过程。树的构建过程。本章学习目标本章学习目标n3.1 k-最最近邻法近邻法n3.2 k-d树树第第3章章 k-最近邻和最近邻和k-d树算法树算法3.1 k-最近邻法最近邻法3.1.1 k-最近邻法最近邻法的基本思想的基本思想n距离距离度量度量，特征空间中样本点的距离是样本点间相似程度的反映。n算法超算法超参数参数 k 的

2、的取值取值。n决策规则决策规则，例如，对于分类任务，采取少数服从多数的“投票法”；对于回归任务，采用取平均值的规则。给定一个训练样本集，对于待预测类别标签的新输入测试实例，可以在特征空间中计算它与所有训练样本的距离，然后在训练样本集中找到与该测试实例最邻近的 k 个训练样本，统计这 k 个样本所属的类别，其中样本数最多的那个类就是该测试实例所属的类别。k-最近邻最近邻（kNN）法涉及到以下三个关键要素：3.1 k-最近邻法最近邻法3.1.2 距离度量距离度量n闵可夫闵可夫斯基距离斯基距离（Minkowski distance）n曼哈顿距离曼哈顿距离（Manhattan distance）3.1

3、 k-最近邻法最近邻法3.1.2 距离度量距离度量n欧欧氏氏距离距离（Euclidean distance）n切比雪夫距离切比雪夫距离（Chebyshev distance）n汉明距离汉明距离（Hamming distance）3.1 k-最近邻法最近邻法3.1.3 k值的选择值的选择3.1 k-最近邻法最近邻法3.1.3 k值的选择值的选择n如果选择较小如果选择较小的的k值值n优点优点:训练误差会训练误差会减小，只有减小，只有与输入的测试实例较近或相似的与输入的测试实例较近或相似的训练样本才会对训练样本才会对预测结果起作用。预测结果起作用。n缺点缺点:泛化误差会泛化误差会增大，预测增大，预测

4、结果会对近邻的训练样本非常结果会对近邻的训练样本非常敏敏感。如果感。如果近邻的近邻的训练样本训练样本恰巧是恰巧是噪声，则噪声，则预测就会预测就会出错。出错。n如果选择较大如果选择较大的的k 值值n优点优点:可以减小泛化误差。可以减小泛化误差。n缺点缺点:训练误差会增大。训练误差会增大。值太大会使模型整体变得值太大会使模型整体变得简单，容简单，容易易发生欠拟合。发生欠拟合。3.1 k-最近邻法最近邻法3.1.4 k-最近邻法最近邻法的的优缺点优缺点n优点优点n算法简单，易于理解，既可以用于分类任务也可以用于回归任务，且算法简单，易于理解，既可以用于分类任务也可以用于回归任务，且适用于多分类和非线

5、性分类问题。适用于多分类和非线性分类问题。n没有显式的训练过程，没有显式的训练过程，k值是唯一的超参数，在确定值是唯一的超参数，在确定k值后，直接进值后，直接进行预测。行预测。n由于由于kNN法并不关注样本的类别数量，因此在处理类别交叉或重叠较法并不关注样本的类别数量，因此在处理类别交叉或重叠较多的待分类样本时，选用多的待分类样本时，选用kNN法比较合适。法比较合适。n缺点缺点n当训练样本集较大、样本的特征向量维数较高时计算量大，耗时长，当训练样本集较大、样本的特征向量维数较高时计算量大，耗时长，时间复杂度高；需要大量的内存，空间复杂度高。时间复杂度高；需要大量的内存，空间复杂度高。n当存在样

6、本不平衡问题时，对稀有类别的预测准确度低。当存在样本不平衡问题时，对稀有类别的预测准确度低。nk 值的选取没有一个良好的准则值的选取没有一个良好的准则。n适用数据范围适用数据范围n数值型和标称型数值型和标称型n3.1 k-最近邻法最近邻法n3.2 k-d树树第第3章章 k-最近邻和最近邻和k-d树算法树算法nk-d 树是一种对树是一种对k维空间中的实例点进行存储以便对其进行维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。快速检索的树形数据结构。nk-d树是二叉树，表示对树是二叉树，表示对k维空间的一个划分（维空间的一个划分（partition)。n构造构造k-d树相当于不断地用垂直

7、于坐标轴的超平面将树相当于不断地用垂直于坐标轴的超平面将k维空维空间切分，构成一系列的间切分，构成一系列的k维超矩形区域。维超矩形区域。nk-d 树的每个结点对应于一个树的每个结点对应于一个k维超矩形区域。维超矩形区域。3.2 k-d树树3.2 k-d树树3.2.1 如何构建如何构建k-d 树树图3-3 二叉搜索树的一个例子 3.2.1 如何构建如何构建k-d 树树构建构建k-d 树树的的过程过程如下如下：3.2.1 如何构建如何构建k-d 树树3.2.1 如何构建如何构建k-d 树树3.2.1 如何构建如何构建k-d 树树3.2.1 如何构建如何构建k-d 树树 （1）首先首先要找到该目标点

8、的叶子节点，然后以目要找到该目标点的叶子节点，然后以目标点为圆心，目标点到叶子节点的距离为半径，标点为圆心，目标点到叶子节点的距离为半径，建立一个超球体，我们要找寻的最近邻点一定是建立一个超球体，我们要找寻的最近邻点一定是在该球体内部。在该球体内部。搜索（搜索（4,4）的最近邻时。首先从根节点（）的最近邻时。首先从根节点（6,4）出）出发，将当前最近邻设为（发，将当前最近邻设为（6,4），对该），对该KD树作深树作深度优先遍历。以（度优先遍历。以（4,4）为圆心，其到（）为圆心，其到（6,4）的距）的距离为半径画圆（多维空间为超球面），可以看出离为半径画圆（多维空间为超球面），可以看出（7,2

9、）右侧的区域与该圆不相交，所以（）右侧的区域与该圆不相交，所以（7,2）的）的右子树全部忽略。右子树全部忽略。3.2.2 如何在如何在k-d 树中搜索树中搜索 （2）返回返回叶子结点的父节点，检查另一个子结叶子结点的父节点，检查另一个子结点包含的超矩形体是否和超球体相交，如果相点包含的超矩形体是否和超球体相交，如果相交就到这个子节点寻找是否有更加近的近邻交就到这个子节点寻找是否有更加近的近邻,有有的话就更新最近邻。的话就更新最近邻。接着走到（接着走到（6,4）左子树根节点（）左子树根节点（4,5），与原最），与原最近邻对比距离后，更新当前最近邻为（近邻对比距离后，更新当前最近邻为（4,5）。）

10、。以（以（4,4）为圆心，其到（）为圆心，其到（4,5）的距离为半径画）的距离为半径画圆，发现（圆，发现（6,4）右侧的区域与该圆不相交，忽）右侧的区域与该圆不相交，忽略该侧所有节点，这样（略该侧所有节点，这样（6,4）的整个右子树被）的整个右子树被标记为已忽略标记为已忽略。3.2.2 如何在如何在k-d 树中搜索树中搜索 （3）如果如果不相交直接返回父节点，在另一个子不相交直接返回父节点，在另一个子树继续搜索最近邻树继续搜索最近邻。（4）当当回溯到根节点时，算法结束，此时保存回溯到根节点时，算法结束，此时保存的最近邻节点就是最终的最近邻。的最近邻节点就是最终的最近邻。遍历完（遍历完（4,5）的左右叶子节点，发现与当前最）的左右叶子节点，发现与当前最优距离相等，不更新最近邻。优距离相等，不更新最近邻。所以（所以（4,4）的最近邻为（）的最近邻为（4,5）。）。3.2.2 如何在如何在k-d 树中搜索树中搜索Question?