美文网首页
《统计学习方法》-k近邻法

《统计学习方法》-k近邻法

作者: Joe_WQ | 来源:发表于2018-12-09 14:20 被阅读0次

date: 2018-1-19
k近邻算法不需要显示学习判别模型,属于懒惰学习的一种,这样要素变成了:k值的选取、距离度量和分类决策规则。

K值选择

k值决定了有多少个点参与决策,拿最简单的欧式距离(距离度量)来说,就是先选择一个固定的K值,然后比较带测试点与所有点的距离,然后将对应最小的k个距离的点选出来,选用投票法(分类决策)来决定带测试点的类别。

k值的选取与模型有很大的关系,小了容易发生过拟合,大了可以减小学习的估计误差,但会增大近似误差。一般是取一个比较小的数值,然后采用交叉验证的方法来选取最优的k值(书上原话)。

距离度量

这里需要数学上的概念:范数,P范数定义是这样的:
P范数:L_p(x_i,x_j)=(\sum_{l=1}^n \vert x_i^{(l)}-x_j^{(l)}\vert^p)^{\frac{1}{p}},p\geqslant 1

当然,是存在0范数的,零范数:\left\| \boldsymbol{a}\right\|_0表示向量\boldsymbol{a}有多少个非零点,在作为约束条件时比L_2范数稀疏性更好,但求解麻烦,所以之前一般是用的L_1范数求解,但根据我导师说L_0范数求解貌似有了很大的进展,所以如果大家有兴趣的化可以看下相关的文章。

这样子的话,当p=1时,称为曼哈顿距离,p=2称为欧式距离,p=\infty称为无穷范数,是各个坐标距离的最大值。
L_\infty (x_i,x_j)=\max_l \vert x_i^{(l)}-x_j^{(l)} \vert
这个用高等代数的知识可以推出来,不同的p值对应的解空间是不同的,这里就不多说了。

分类决策规则

书上只讲了多数表决规则,也就是看分类数目的多少,哪种多就选哪个,普遍选择这个的原因是该规则等价于经验风险最小化,书上写了证明。

搜索方法

当样本容量比较大时,一个个的去判断距离无疑是一件很耗时的事情,所以大量的科研工作者做了很多的改进工作,书上介绍了kd树,也就是将包含整个样本的空间划分出一个个超矩形区域,一般以中心点划分,直到再进一步划分的超矩形区域内部没有样本点。详细的算法再书上有。

相关文章

网友评论

      本文标题:《统计学习方法》-k近邻法

      本文链接:https://www.haomeiwen.com/subject/okaefqtx.html