kNN (k-Nearest Neighbour) 算法是一种用于分类和回归的非参数的方法,可以用目标点周围所观察到的数据得平均值来预测出目标点 x 的值。本文将会介绍kNN的回归和分类算法,交叉验证和kNN算法的缺点。
1)kNN回归:
其中N{k}(x)是训练样本中离目标x最近的k个样本。
根据以上公式,我们可以看出在预测y的值时,kNN算法是求在训练样本中离x周围最近的k个样本所对应y值们的平均值。
以R语言为例,我们需要安装“kknn”包,简单的1NN例子如下:
我们可以得到以下fit的结果:
2) kNN分类:
仍以R语言为例,
如上图所示,在预测左图中小黑点的分类时,我们在k为半径的一个圆中发现蓝色点的数量大于橙色点的数量,根据kNN算法,我们把目标点归为蓝色点类。当k=1时,我们能得到上右图分区,称作“Voronoi tessellation"。图中的线段皆是两点的垂直平分线。
3.交叉验证:
不少读者看到这里会好奇,在kNN模型中到底什么样的k最符合我的预测模型呢?
从上图中发现,33NN模型由于方差较小显著优于1NN。然而,当k增加到100时,误差变得尤为显著。我们需要在误差和方差选择一个这种方案:
在寻找平衡点时,我们可以用交叉验证方法寻找最优解。
(1)将训练样本随机分成10组
(2)其中9组作为训练样本,应用k*NN模型;剩下的一组作为模型测试样本记录误差
(3)重新再10组里选择9组作为训练样本,重复10次
(4)平均10次实验的误差,最小的即为最优k。
简单的R代码实现如下,我们得到最佳的k值是33。
4.kNN的缺点:
虽然kNN模型具有容易实现,简单快捷的优点。但在平时建立模型是我们需要注意,kNN模型在每次预测时需要储存所有的训练样本数据,因为在预测时需要返回训练样本找邻近的所有k个点。其次,kNN模型对样本的异常值较为敏感,建立模型是,需要对数据进行预处理降低异常值对结果的影响。
5.参考资料:
https://sites.google.com/site/teazrq/teaching/STAT542
http://blog.csdn.net/suipingsp/article/details/41964713(含数字识别代码)