前言

关于写作：

博主（暂且如此自称）是北京某高校的计算机系研究生在读，入行AI领域时间不久，正在努力进修。最近利用工作之余的时间正在学习李航博士的《统计学习方法》，一方面希望能够通过写作整理思路，另一方面，分享学习心得也希望可以和志同道合的小伙伴们共同探讨进步啦~

github传送门：

GitHub - wyynevergiveup/Statistical-Learning-Method: 《统计学习方法》--李航实现学习过程中的算法以加深理解

系列文章：

1.《统计学习方法》笔记（一）统计学习及监督学习概论 - 简书

2.《统计学习方法》笔记（二）感知机模型 - 简书

3.《统计学习方法》笔记（三）K近邻法 - 简书

4.《统计学习方法》笔记（四）朴素贝叶斯法 - 简书

正文

3.1 K近邻算法（K-NN）

3.1.1 概述

k近邻法是一种基本分类与回归方法。因其多用与分类问题，本文只讨论其在分类问题中的应用。

k近邻算法的输入为样本的特征向量，对应于特征空间中的点；输出为样本所属的类别。具体地，k近邻算法给定一个训练数据集，其中的样本类别已定。对新的样本进行分类时，根据与其最近邻的k个样本的类别，通过多数表决等方式进行预测。

因此，k近邻算法不需要显式的学习过程，它实际上是利用训练集对特征向量空间进行了划分，并作为其分类的“模型”。

k近邻算法的三要素：1）k值的选择；2）距离度量；3）分类决策规则。

3.1.2 算法形式化定义

KNN算法形式化定义

3.2 k近邻模型

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

3.2.1 k值的选择

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

选择较小的k值，就相当于在较小的邻域中的训练实例进行预测，近似误差会减小，估计误差会增大。（什么是近似误差和估计误差？）在这种情况下，只有与输入样本较近的训练样本对结果预测起作用，因此，预测结果会对近邻的样本点非常敏感，如果邻近的实例点恰好存在噪声，预测就很有可能会出错。换句话说，k值的减小意味着整体模型变得复杂，容易过拟合。

选择较大的k值，就相当于在较大的邻域中的训练实例进行预测，估计误差会减小，近似误差会增大。在这种情况下，与输入样本距离较远的训练样本也会对预测起作用，使得预测发生错误。换句话说，k值的增大意味着整体的模型变得简单，容易欠拟合。

现在，我们来解释一下什么是近似误差和估计误差。（此答案来自网络，个人认为这种理解方式简单易懂，值的推荐。）

近似误差，更关注于“训练”。最小化近似误差，即为使估计值尽量接近真实值，但是这个接近只是对训练样本（当前问题）而言，模型本身并不是最接近真实分布。换一组样本，可能就不近似了。这种只管眼前不顾未来预测的行为，即为过拟合。

估计误差，更关注于“测试”、“泛化”。最小化估计误差，即为使估计系数尽量接近真实系数，但是此时对训练样本（当前问题）得到的估计值不一定是最接近真实值的估计值；但是对模型本身来说，它能适应更多的问题（测试样本）。

3.2.2 距离度量

特征空间中的两个实例点的距离是两个实例点相似程度的度量。这里介绍一种比较一般（通用）的距离度量—— $L_p$ 距离（或 $Minkowski$ 距离）。

假设特征空间X是n维实数向量空间 $R^n$ , $x_i,x_j \in X,x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(n)})^T,x_j=(x_j^{(1)},x_j^{(2)},...,x_j^{(n)})^T,$ $x_i,x_j$ 之间的 $L_p$ 距离定义为：