时间 ：2014.07.05

地点：基地

-----------------------------------------------------------------------------------

一、简述

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

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

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

3.分类决策

-----------------------------------------------------------------------------------

二、k近邻算法

输入：给定训练数据集

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

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

算法描述：

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

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

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

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

-----------------------------------------------------------------------------------

三、k近邻模型

3.1 k近邻的模型

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

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

3.2 距离的度量

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

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

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

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

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

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

3.3k值的选择

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

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

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

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

3.4分类决策规则

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