【统计学习方法】第3章 k近邻法（一）-轻识

点击上方“公众号”可订阅哦！

$k$ 近邻法是一种基本分类与回归分析方法。

$k$ 近邻法的输入为实例的特征向量，对应于特征空间的点；输出为实例的类别，可以取多类。

$k$ 近邻法实际上利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。

$k$ 值的选择、距离度量及分类决策规则是 $k$ 近邻法的三个基本要素。

本章先叙述 $k$ 近邻算法，然后讨论 $k$ 近邻法的模型及三个基本要素，最后讲述 $k$ 近邻算法的一个实现。

先讲述 $k$ 近邻算法和三个基本要素。

●

$k$ 近邻算法

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

输入：

$T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\}$

其中，

$x$ 为实例的特征向量， $y$ 为实例的类别。

输出：

实例 $x$ 所属的类 $y$

1）根据给定的距离向量，在训练数据集中找出与 $x$ 最邻近的 $k$ 个点。

2）在这 $k$ 个点中根据分类规则决定 $x$ 的类别 $y$

●

$k$ 近邻模型

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

距离度量

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

设特征向量x是n维实数向量空间， $x_{i}, x_{j} \in \mathcal{X}$ ， $x_{i}=\left(x_{i}^{(1)}, x_{i}^{(2)}, \cdots, x_{i}^{(n)}\right)^{\mathrm{T}}$ ， $x_{j}=\left(x_{j}^{(1)}, x_{j}^{(2)}, \cdots, x_{j}^{(n)}\right)^{\mathrm{T}}$ ，

则： $x_i,x_j$ 的距离定义为，

$L_{p}\left(x_{i}, x_{j}\right)=\left(\sum_{i=1}^{n}\left|x_{i}^{(i)}-x_{j}^{(l)}\right|^{p}\right)^{\frac{1}{p}}$

$p=1$ ,曼哈顿距离

$p=2$ ,欧式距离

$p= \infty$ ，切比雪夫距离

$k$ 值的选择

$k$ 值的选择会对近邻法的结果产生重大影响。

如果选择较小的 $k$ 值，就相当于用较小的领域中的训练实例进行预测，“学习”的近似误差会减小，只有与输入实例较近的训练实例才会对预测结果起作用。或者说， $k$ 值的减小就意味着整体模型变得复杂，容易发生过拟合。

如果选择较大的 $k$ 值，就相当于用较大领域中的训练实例进行预测。其优点是可以减少学习的估计误差。 $k$ 值的增大就意味着模型变得简单。

分类决策规则

$k$ 近邻法中的分类决策规则往往是多数表决，即由输入实例的 $k$ 个近邻的训练实例中的多数类决定输入实例的类。多数表决规则等价于经验风险最小化。

END

深度学习入门笔记

微信号:sdxx_rmbj

日常更新学习笔记、论文简述

【统计学习方法】 第3章 k近邻法（一）

【统计学习方法】第3章 k近邻法（一）