统计学习方法——KNN

以上是《统计学习方法》这本书里给出的KNN的算法形式

KNN，中文全称K近邻法，三个基本要素：距离度量，K值的选择和分类决策规则。 是一种基本的分类回归算法

我们先来看个例子来进一步说明KNN到底是干什么的：

KNN算法解释

上图中共有三种颜色的样本：红色三角形、蓝色正方形和绿的的圆形。现在我们假设，蓝色和红色是我们已知的两种类型，绿色样本是未知的，我们想要知道绿色样本（x）是属于蓝红哪一种，因此，我们可以通过以下两个步骤进行判断：

1.根据给定的距离度量，在训练集中找到与绿色样本x最近的k个点，涵盖着k个点的邻域记作

2.在中根据分类决策规则（如多数表决）决定x的类别y

那么我们现在来给绿色样本x找到类别y。首先我们假设距离度量的标准给好了，就用欧氏距离，k=3，也就是距离x最近的3个样本，即图中实线范围A内，范围A内，红色样本有2个，蓝色样本有1个，因此我们认为x类别为红色。然而，如果我们将k=5，也就是距离x最近的5个样本，即图中虚线范围B内，B中的样本中，红色2个，蓝色3个，因此我们认为x类别为蓝色。

从上面我们可以看出，k值的选择不同，可以影响到分类的结果，那么k值我们应如何选择呢？我们通常使用交叉验证的方法来选择k。也就是说，我们将样本集分为两种，训练集和验证集，验证集中的样本是已知分类的，我们把验证集中的实例的特征提取出来，根据这些特征在训练集上取不同的k值进行KNN分类，然后每次取值后的结果和验证集中的正确分类进行比较，通过比较选出最合适的k值。

我们目前为止讲了K值的选择，分类决策规则的话一般就是多数表决。那么，接下来我们重点讲解距离度量这个基本要素。

距离度量是衡量特征空间中每个实例点间的距离的，k近邻模型的特征空间一般是n维实数向量空间，使用的距离一般是欧氏距离，或者是距离，形式如下：

距离公式 常用p值的公式形式

那么，时的区别和联系又是什么呢？让我们来看下图：

Lp距离间的关系 统计学习方法的例子

从例3.1中我们可以看出，根据范数的选择不同，距离同一个实例的最近的实例是不一样的。因此，我们可以根据训练集中的实例的特征来进行p值的选择。也就是说，我们想要考虑输入实例的每个分量的时候，可以选择p=1或p=2；当我们只考虑输入实例的较大的分量时，可以选择。

最后我们来总结一下，KNN模型没有显示的形式，不像多层感知机（MLP）那样有明显的公式来表示，但是也有三个基本要素：距离度量，K值的选择和分类决策规则。KNN模型的复杂度主要体现在K值的选择，K值比较小的情况下容易过拟合，K值比较大的情况下容易欠拟合。KNN的特点是模型完全取决于数据集，没有数学模型可言，适合做一些解释性的工作。

此学习笔记参考了《统计学习方法》和深度之眼的课程，写在这里也是给自己做个学习笔记，有错误还望大佬们指点~