k近邻算法理论（一）

谁借莪１个温暖的怀抱￠ 2022-08-24 11:21 163阅读 0赞

时间 ：2014.07.05

地点：基地

\-----------------------------------------------------------------------------------

# 一、简述 #

K近邻法（k-nearest neighbor，kNN）是一种基本分类与回归方法。k近邻的输入为实例的特征向量，对应特征空间中的点，输出为实例的类别。k近邻算法的基本思想是：给定训练数据集，实例类别已定，在对目标实例进行分类时，我们根据与目标实例k个最近邻居的训练实例的类别，通过多数表决的方式进行决定。也就是说，k近邻算法实际上是利用了训练数据集对特征向量空间进行了划分，并作为其分类的模型。这样k近邻算法涉及三个最基本的元素：

1.k值的选择，即取多大的k最适合于分类

2.距离的度量，即怎么样一个距离计算判断是否为目标实例的邻居

3.分类决策

\-----------------------------------------------------------------------------------

# 二、k近邻算法 #

输入：给定训练数据集

![SouthEast][]

其中![SouthEast 1][] 为输入实例的特征向量，![SouthEast 2][]为实例的类别，通过建模后，我们在输入一个实例特定向量x

输出：实例x所属的类别。

算法描述：

1.根据给定的距离度量，在训练集T中找出与x最近邻的k个点，涵盖这k个点的x的邻域我们记为：![SouthEast 3][]

2.在x的k个点邻域![SouthEast 4][]中，根据分类决策规则（一般为多数表决）决定x的类别y，即：

![SouthEast 5][]

argmax是取使得表达式取值最大的参数值，在这里即得到对应的哪个类别值，这类别使得右边表达式取值最大。即表示：在x的领域里，邻域元素大部分属于某个类别时右式取值最大，然后我们把对应的类别（即参数取值）赋给结果。

k近邻算法在k=1时是最近邻算法，k近邻算法也没有显示的学习过程。

\-----------------------------------------------------------------------------------

# 三、k近邻模型 #

## 3.1 k近邻的模型 ##

k近邻法的建模，实际上就是对特征空间的划分，当训练集、距离度量、k值和分类决策规则都确定后，对于任何一个新的输入实例它所属的类型也就会被确定。于是整个过程就相当于将特征空间划分为一些子空间，我们的任务就是要确定子空间里的每个点所属的类。

在特征空间中（特征空间的维数为输入向量x的维数），对于每个训练实例点x，我们把距离该点比其他点更近的所有点组成一个单元。这样，每个实例点都拥有一个单元，所有训练实例点的单元构成了对特征空间的一个划分。

## 3.2 距离的度量 ##

特征空间中两个实例点的距离是两个实例点相似程度的反映，k近邻模型的特征空间由n维实数向量空间![SouthEast 6][]张成，距离的度量也有很多方式，比如欧式距离Lp距离等等。

我们设特征空间X是n维实数向量空间张成，其中两个实例 为 ![SouthEast 7][]，这样，这两个实例的Lp距离定义如下：

![SouthEast 8][]

p为大于或等于1的正整数，特别的

当p等于1时就是曼哈顿距离（街道距离）

当p等于2时就是欧式距离（直线距离）

当p为无穷大时就是向量各个维度坐标中距离最大的值，即

![SouthEast 9][]

## 3.3k值的选择 ##

k值的选择能对k近邻法的结果产生很大的影响，合理地选择k值的大小，对于预测结果的准确性能起到莫大的作用。

首先，如果k值较小，就相当于用较小的邻域中的训练实例进行预测，当然，这样学习的近似误差会减小，只有与输入实例相对更近的k个训练实例才会对预测结果起作用，缺点是学习的估计误差会增大，预测结果会对近邻的实例点非常敏感，即如果近邻点实例是个噪声点，然而这个噪声点对于分类所占的分量也就随着k值的减小而增大，于是容易在预测时出现误判。换而言之，随着k值的减小，整体模型更为复杂，容易发生过拟合。

其次，如果k值较大，就相当于用较大的邻域训练实例进行预测，这样就可以减少学习的估计误差，但缺点是学习的近似误差会增大，此时输入实例较远的训练实例也会对预测起到作用，使预测发生错误。k值的增大意味着整体的模型变得简单。一种极端案例就是k=N,此时无论输入的实例是什么，都只是简单的预测训练实例中最多的类，忽略了训练实例中大量的有用信息，模型过于简单。

实际应用中，k值取一个比较小的数值，常采用交叉验证的方法来选取一个最优的k值。

## 3.4分类决策规则 ##

k近邻法中分类规则一般采用多数表决的方式，即由k个近邻总训练实例中多数类决定输入实例的类。多数表决规则等价于经验风险最小化。

[SouthEast]: /images/20220823/48befa610e984f998783506409aea0a9.png
[SouthEast 1]: https://img-blog.csdn.net/20140705104201765?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxMjMzMzAwMw==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 2]: /images/20220823/ada8679e8bbe4fb9af84949c82bdcac2.png
[SouthEast 3]: /images/20220823/a340d4f5cc804aa79a3d61ce4c7e8286.png
[SouthEast 4]: /images/20220823/af94cfbf63c44674959c12d388a1c0bb.png
[SouthEast 5]: /images/20220823/f95ac22bc4b7427b8cf832022e321298.png
[SouthEast 6]: /images/20220823/87d474a00227454f8503504c3815fc66.png
[SouthEast 7]: /images/20220823/99e1b676d50e4716a6d4f51ccea25762.png
[SouthEast 8]: /images/20220823/78e1fd166b894b21a26a990026d3ac96.png
[SouthEast 9]: /images/20220823/16a42e02a8294fc5ad73b48dee71bc67.png