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

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

K值选择

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

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

距离度量

这里需要数学上的概念：范数，P范数定义是这样的：

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

这样子的话，当时，称为曼哈顿距离，称为欧式距离，称为无穷范数，是各个坐标距离的最大值。

这个用高等代数的知识可以推出来，不同的p值对应的解空间是不同的，这里就不多说了。

分类决策规则

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

搜索方法

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