一、k 近邻算法

1. 近邻法（k-Nearest Neighbor:kNN）是一种基本的分类与回归方法。

   • 分类问题：对新的样本，根据其 个最近邻的训练样本的类别，通过多数表决等方式进行预测。
   • 回归问题：对新的样本，根据其 个最近邻的训练样本标签值的均值作为预测值。

2. 近邻法不具有显式的学习过程，它是直接预测。它是“惰性学习”(lazy learning)的著名代表。

   • 它实际上利用训练数据集对特征向量空间进行划分，并且作为其分类的”模型”。

   • 这类学习技术在训练阶段仅仅将样本保存起来，训练时间开销为零，等到收到测试样本后再进行处理。

     那些在训练阶段就对样本进行学习处理的方法称作“急切学习”(eager learning)。

3. 近邻法是个非参数学习算法，它没有任何参数（ 是超参数，而不是需要学习的参数）。

   • 近邻模型具有非常高的容量，这使得它在训练样本数量较大时能获得较高的精度。

   • 它的缺点有：

     • 计算成本很高。因为需要构建一个 的距离矩阵，其计算量为 ，其中 为训练样本的数量。

       当数据集是几十亿个样本时，计算量是不可接受的。

     • 在训练集较小时，泛化能力很差，非常容易陷入过拟合。

     • 无法判断特征的重要性。

4. 近邻法的三要素：

   • 值选择。
   • 距离度量。
   • 决策规则。

1.1 k 值选择

1. 当 时的 近邻算法称为最近邻算法，此时将训练集中与 最近的点的类别作为 的分类。

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

   • 若 值较小，则相当于用较小的邻域中的训练样本进行预测，”学习”的偏差减小。

     只有与输入样本较近的训练样本才会对预测起作用，预测结果会对近邻的样本点非常敏感。

     若近邻的训练样本点刚好是噪声，则预测会出错。即： 值的减小意味着模型整体变复杂，易发生过拟合。

     • 优点：减少”学习”的偏差。
     • 缺点：增大”学习”的方差（即波动较大）。

   • 若 值较大，则相当于用较大的邻域中的训练样本进行预测。

     这时输入样本较远的训练样本也会对预测起作用，使预测偏离预期的结果。

     即： 值增大意味着模型整体变简单。

     • 优点：减少”学习”的方差（即波动较小）。
     • 缺点：增大”学习”的偏差。
3. 应用中， 值一般取一个较小的数值。通常采用交叉验证法来选取最优的 值。

1.2 距离度量

1. 特征空间中两个样本点的距离是两个样本点的相似程度的反映。

   近邻模型的特征空间一般是 维实数向量空间 ， 其距离一般为欧氏距离，也可以是一般的 距离：

   

   • 当 时，为欧氏距离：
   • 当 时，为曼哈顿距离：
   • 当 时，为各维度距离中的最大值：
2. 不同的距离度量所确定的最近邻点是不同的。

1.3 决策规则

1.3.1 分类决策规则

1. 分类决策通常采用多数表决，也可以基于距离的远近进行加权投票：距离越近的样本权重越大。

2. 多数表决等价于经验风险最小化。

   设分类的损失函数为 损失函数，分类函数为 。

   给定样本 ，其最邻近的 个训练点构成集合 。设涵盖 区域的类别为 （这是待求的未知量，但是它肯定是 之一），则损失函数为：

   

   就是训练数据的经验风险。要使经验风险最小，则使得 最大。即多数表决： 。

1.3.2 回归决策规则

1. 回归决策通常采用均值回归，也可以基于距离的远近进行加权投票：距离越近的样本权重越大。

2. 均值回归等价于经验风险最小化。

   设回归的损失函数为均方误差。给定样本 ，其最邻近的 个训练点构成集合 。设涵盖 区域的输出为 ，则损失函数为：

   

   就是训练数据的经验风险。要使经验风险最小，则有： 。即：均值回归。

1.4 k 近邻算法

1. 近邻法的分类算法：

   • 输入：

     • 训练数据集

     • 给定样本

   • 输出： 样本 所属的类别

   • 步骤：

     • 根据给定的距离度量，在 中寻找与 最近邻的 个点。定义涵盖这 个点的 的邻域记作 。
     • 从 中，根据分类决策规则（如多数表决） 决定 的类别 ： 。

2. 近邻法的回归算法：

   • 输入：

     • 训练数据集

     • 给定样本

   • 输出：样本 的输出

   • 步骤：

     • 根据给定的距离度量，在 中寻找与 最近邻的 个点。定义涵盖这 个点的 的邻域记作 。
     • 从 中，根据回归决策规则（如均值回归） 决定 的输出 ： 。