K 近邻法及其在手写数字识别的实践近邻法及其在手写数字识别的实践
文章首发于文章首发于 个人博客个人博客
引言引言
k 近邻法(k-nearest-neighbor, KNN)是一种基本的分类和回归方法。现在只讨论其分类方面的应用,它不具备明显的学习过程,实际
上是利用已知的训练数据集对输入特征向量空间进行划分,并作为其分类的“模型”。
其中 k 值的选择、距离的度量及分类决策规则是 k 近邻模型的三个基本要素。
本文将按照以下提纲进行:
k 近邻法阐述
k 近邻的模型
k 近邻在手写数字识别上的实战
k 近邻法阐述近邻法阐述
k 近邻算法非常容易理解,因为其本质上就是求距离,这是非常简单而直观的度量方法:对于给定的一个训练数据集,对新的输入实例
M,在训练数据集中找到与该新实例 M 最邻近的 k 个实例,由这 k 个实例按照一定的表决规则进行投票决策最合适的类别,那么实例
M 就属于这个类。下面是算法的描述:
k 近邻模型近邻模型
k 近邻算法本质上是在超空间内划分区域空间分类的问题,在输入数据集的特征空间内,对于每个训练实例点 xix_ixi ,距离改点比其
他点更近的所有点组成一个区域,叫做单元(cell)。上文说了 k 近邻模型的三个要素,k 值选择、距离度量、决策函数,下面一一说明。
k 值选择值选择
k 值指的是选择近邻点的数目,如果 k = 1 则是最近邻,即是每次由距离新实例最近的训练点所属的类别决定待分类实例的类别。
k 值的选择对于 k 近邻法的结果可以产生重大影响。
当 k 值较小的时候,那么预测学习的近似误差会减少,因为此时只有距离待分类点较近的训练实例才会对于分类预测结果有影响作
用,但是缺点是估计误差会增大,因为预测结果会对近邻的实例点非常敏感,如果近邻的实例多数都是噪声点,那么就很容易导致预
测出错。即是说,k 值的减少意味着模型变得复杂,容易发生过拟合。
当 k 值较大的时候,就相当于用较大邻域中的训练实例进行预测。其优点是可以减少学习的估计误差。但缺点是学习的近似误差会增
大,这时与输入实例较远的(不相似的)训练实例也会对预测起作用,使预测发生错误。k 值的增大就意味着整体的模型变得简单。
如果 k = N,那么无论输入实例是什么,都将简单地预测它属于在训练实例中最多的类。这时,模型过于简单,完全忽略训练实例中的
大量有用信息,是不可取的。
在应用中,k 值一般取一个比较小的数值。通常采用交叉验证法来选取最优的 k 值。