k近邻法篇

上回的感知机(perception)篇讨论的问题是二类分类问题，现在要介绍的k近邻法也是分类问题，不过不局限于二类问题，可以应用于多类分类问题中。

k近邻法(k-nearest neighbor, K-NN)是由Cover和Hart在1968年提出的，是一个基本的分类和回归方法，现在讨论的是在分类问题中的应用。核心思想就是在对于一个未知类别的输入，根据已知输入类别中k个最相似的输入类别，将该类别作为这个未知类别的类别。也就是俗话说的物以类聚，人以群分。想了解一个人怎么样，可以先了解下这个人最好的几个朋友，也就可以推出这个人怎么样。从这儿看出，k近邻法本质上没有学习的过程，只是对输入的特征空间进行了一个划分。自然而然地可以猜出在分类中，knn的三要素就是k值的选择+距离度量+分类决策规则。那下面的介绍就自然而然是围绕按照这三要素来了。

k值的选择

k值的选择是有依据的，k值太小，比如等于1，来一个输入，就把该输入归为和该输入距离最近的训练点的类别，这样会让模型太复杂，而且如果最近的点恰好又是噪声，预测就不正确了，也就是输入会对每个训练点敏感，这就是所谓的过拟合。

k值太大，比如等于训练集大小N，这样模型就太简单了，找出训练集中成员最多的类别，新来的输入，不管三七二十一，就分为该类别。这样会让经验风险太大，毕竟都不用学习什么参数了，那个类别成员多，以后所有输入都是这个类的。我理解这样就成了欠拟合了。

顺路说下过拟合与欠拟合，这个在机器学习模型中还是很基础的。

过拟合：也就是为了拟合每个训练数据，模型设计的特别复杂，效果就是可以将训练误差搞得非常小。可是对于未知的输入效果可能就很差了，因为如果训练数据中有噪声，那么系统将噪声也作为合理输入了，这样必然没法保证未知的输入。可以想想如果某一个地方的房价和面积是一阶线性关系，可是你却用10阶函数去拟合，能保证准确预测房价么？一句话，过拟合，就是你把模型设计的太复杂了。

欠拟合：就是你把模型设计的太简单了。不仅训练误差没法保证，期望误差也没法保证。比如还是房价，你用0阶函数来拟合，看到大家房价从0.5k到5w间变化，你不管三七二十一，房价都是2w。这样必然也是不行的。

那怎么防止过拟合或者欠拟合？

一般的套路都是来一个损失函数L=E+aJ E是经验误差，用来防止欠拟合的，J是系统复杂度，用来防止过拟合的。a是权重，可以来回调，这不就可以处理这样的极端问题了么。

那继续KNN，那怎么选取k比较合理呢？毕竟对于KNN，还不太好弄损失函数。那就选一个偏小的值，然后交叉验证看效果。据我所知没有特别科学的方法，直接告诉我们k选多少。

距离度量

要选择K个最近的点，那至少需要知道最近是用啥衡量的吧。因为距离反映到输入上，就是输入间的相似程度。在KNN中由于特征空间一般是n维的向量空间，那么用度量向量距离的方法来度量就可以了。比如有x1，x2两个输入，距离L=

（PS：用latex生成的公式只能用图片拷贝过来了，效果不太好，直接用编辑器拷贝公式可能效果更好，下来研究下）。

p>=1, 我们用的比较多的是p=2，就是欧式距离，p=1也用吧，曼哈顿距离。需要知道的是对于一个点，用不同的p，也就是距离度量方法获取到的最近邻点是不一样的。

分类决策规则

KNN的分类决策规则一般都是多数表决，K个邻近点中，那个类别点最多，那么就是那个类别。

那为什么选类别成员多的，就能保证经验误差小呢？

从数学上解释就是：

P(Y!=f(x)) = 1 - P(Y=f(x))

也就是猜中的概率越大，经验误差越小。那怎样能做能让猜中的概率最大呢？

k个邻近点，有j个类，类成员越多的，f(x)是这个类的概率也就越大。

kd树

到现在就介绍完KNN的三要素了，还有一个问题？怎样快速搜索k个最近的邻点？如果是挨个训练数据遍历的话，当训练数据很大的时候，计算会很耗时。为了提升k搜索的效率，有很多种方法，这儿介绍下其中的一种，kd树。

kd树本质上就是二叉树，普通的二叉树是针对单个数值，对于k维的数据，在各个坐标轴上循环切分，就是kd树。举一个栗子：

现在有一个训练数据集合 T=,一共是n个输入。每个输入又是k维的数据。比如x_1=（x1,x2,...xk），这儿的每个数据是对应坐标轴上的表示，这儿的k就意味着我们有k个坐标轴，也可以说成是x_1是k维空间上的点。

构造kd树的过程就是：

根节点，选择x1所在坐标轴上的所有点，选取中位数，按照中位数将训练集划分为两个区域，小于中位数的作为左子节点，大于中位数的作为右子节点，等于中位数的就放到当前节点

重复，对左右节点，选择第j个数据的中位数，j的选取就是依次循环取坐标轴上数据即可，比如父节点是第i个坐标轴，那么子节点就选取第i%k+1个坐标轴。按根节点方法划分即可。

结束，啥时候结束？划分到没数据划分就可以结束了

那怎么搜索呢？ 例如来了一个输入，想找和这个输入最接近的点。

步骤是：

在kd树中找包含该输入的叶节点。

找该区域内最邻近该输入的训练点，找到后，把这个点作为最近距离点，然后以输入点为圆心，最近距离点为半径，做一个圆，如果有更近的点，那么必然在这个圆里面

看父节点的另外一个子节点区域是否和该圆相交，如果没有，那么继续往上看当前节点的父节点，重复过程3.如果有，那么看该节点对应的区域内是否有比当前最近点更近的点，如果有，那么把这个点作为当前最近的点。重复3.如果到达根节点，遍历就结束了。这时候的最近距离点就是最近的点了。

算法时间复杂度O（LOG（N）），N是训练节点个数。

那怎么找k个最邻近的点呢？ 这个参考堆排序的思想即可。

总结

本篇介绍了下KNN算法，包括KNN算法的三要素，还介绍了一种快速查到最邻近点的方法，kd树。总的来说，这块不太复杂。下一篇是朴素贝叶斯篇。