统计学习方法-李航 第三章 K近邻法

柔情只为你懂 2021-12-14 06:53 479阅读 0赞

简介

K近邻 算法（KNN）是一种基本分类与回归方法，指从一个训练数据集中，找到相近的K个点，这K个实例多数属于某个类，就把输入实例分为这个类。特殊情况，当K=1时，称为最近邻算法。
在这里插入图片描述

模型

模型有3个要素

  • 距离度量方法
  • k值的选择
  • 分类决策规则
    当3要素确定的时候，对任何实例（训练或输入），它所属的类都是确定的，相当于将特征空间分为一些子空间。
    在这里插入图片描述
距离度量方法

在这里插入图片描述

  1. 当p=1时，为曼哈顿距离：
    在这里插入图片描述
    (X1，Y1)和(X2，Y2)的曼哈顿距离为|X1-X2|+|Y1-Y2|
  2. 当p=2时，为欧式距离：
    在这里插入图片描述
    两个竖线表示欧氏距离（|| L1||），计算方式为每个维度差的平方式再相加后的开方。
  3. 当p=∞时，塔式各个坐标距离的最大值：
    在这里插入图片描述
    在这里插入图片描述
    **由不同的距离度量所确定的最近邻是不同的。**

k值的选择

  • k值比较小，近似误差会减小，估计误差会增大，容易被噪声影响，发生过拟合。
  • k值比较大，估计误差会减小，近似误差会增大，较远的训练实例也会对预测起作用，容易发生错误。

近似误差：对现有训练集的训练误差
估计误差：对测试集的测试误差

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

分类决策规则

k近邻法中的分类决策规则往往是多数表决，有输入实例的k个邻近的训练实例中的多数类决定输入的实例类

k近邻法的实现：kd树

构造kd树

方法：
在这里插入图片描述在这里插入图片描述
看例子：
在这里插入图片描述

kd树的搜索

在这里插入图片描述在这里插入图片描述
书中的例子已经可以说的足够明白：
在这里插入图片描述

发表评论

表情：
评论列表 （有 0 条评论，479人围观）

还没有评论，来说两句吧...

相关阅读