Question

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

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

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

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

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

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

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

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

   • 它的缺点有：

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

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

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

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

4. $ MathJax-Element-157 $ 近邻法的三要素：

   • $ MathJax-Element-157 $ 值选择。
   • 距离度量。
   • 决策规则。

1.1 k 值选择

1. 当 $ MathJax-Element-16 $ 时的 $ MathJax-Element-157 $ 近邻算法称为最近邻算法，此时将训练集中与 $ MathJax-Element-150 $ 最近的点的类别作为 $ MathJax-Element-150 $ 的分类。

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

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

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

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

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

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

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

     即： $ MathJax-Element-157 $ 值增大意味着模型整体变简单。

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

3. 应用中， $ MathJax-Element-157 $ 值一般取一个较小的数值。通常采用交叉验证法来选取最优的 $ MathJax-Element-157 $ 值。

1.2 距离度量

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

   $ MathJax-Element-157 $ 近邻模型的特征空间一般是 $ MathJax-Element-29 $ 维实数向量空间 $ MathJax-Element-30 $ ， $ MathJax-Element-157 $ 其距离一般为欧氏距离，也可以是一般的 $ MathJax-Element-32 $ 距离：

   $ L_p(\mathbf {\vec x}_i,\mathbf {\vec x}_j)=(\sum_{l=1}^{n}|x_{i,l}- x_{j,l}|^{p})^{1/p},\quad p \ge 1\\ \mathbf {\vec x}_i,\mathbf {\vec x}_j \in \mathcal X=\mathbb R^{n};\quad \mathbf {\vec x}_i=(x_{i,1},x_{i,2},\cdots,x_{i,n})^{T} $
   • 当 $ MathJax-Element-33 $ 时，为欧氏距离： $ MathJax-Element-34 $
   • 当 $ MathJax-Element-35 $ 时，为曼哈顿距离： $ MathJax-Element-36 $
   • 当 $ MathJax-Element-37 $ 时，为各维度距离中的最大值： $ MathJax-Element-38 $

2. 不同的距离度量所确定的最近邻点是不同的。

1.3 决策规则

1.3.1 分类决策规则

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

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

   设分类的损失函数为 $ MathJax-Element-39 $ 损失函数，分类函数为 $ MathJax-Element-40 $ 。

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

   $ L = \frac {1}{k}\sum_{\mathbf {\vec x}_i \in \mathcal N_k(\mathbf {\vec x})}I(\tilde y_i \ne c_m)=1-\frac{1}{k}\sum_{\mathbf {\vec x}_i \in \mathcal N_k(\mathbf {\vec x})}I(\tilde y_i = c_m) $

   $ MathJax-Element-55 $ 就是训练数据的经验风险。要使经验风险最小，则使得 $ MathJax-Element-48 $ 最大。即多数表决： $ MathJax-Element-49 $ 。

1.3.2 回归决策规则

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

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

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

   $ L = \frac 1k\sum_{\mathbf {\vec x}_i \in \mathcal N_k(\mathbf {\vec x})} (\tilde y_i - \hat y)^2 $

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

1.4 k 近邻算法

1. $ MathJax-Element-157 $ 近邻法的分类算法：

   • 输入：

     • 训练数据集 $ MathJax-Element-58 $
       
     • 给定样本 $ MathJax-Element-150 $

   • 输出： 样本 $ MathJax-Element-150 $ 所属的类别 $ MathJax-Element-85 $

   • 步骤：

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

2. $ MathJax-Element-157 $ 近邻法的回归算法：

   • 输入：

     • 训练数据集 $ MathJax-Element-73 $
       
     • 给定样本 $ MathJax-Element-150 $

   • 输出：样本 $ MathJax-Element-150 $ 的输出 $ MathJax-Element-85 $

   • 步骤：

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