[机器学习实战札记] k-近邻算法

《机器学习实战》一书介绍的第一个算法是k-近邻算法。简单的说，k-近邻算法采用测量不同特征值之间的距离方法进行分类。其工作机制非常简单：给定测试样本，基于某种距离度量找出训练集中与其最靠近的k个训练样本，然后基于这k个“邻居”的信息来进行预测。

《机器学习实战》一书给出的示例都是分类算法，其实该算法也适用于回归任务。在分类任务中可使用“投票法”，即选择这个k个样本中出现最多的类别标记作为预测结果; 在回归任务中可使用“平均法”，即将这k个样本的实值输出标记的平均值作为预测结果。

k-近邻算法实现上也比较简单，以分类任务为例，首先是准备训练样本，训练样本都存在标签，也就是我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与训练样本对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，选择k个最相似的数据，这就是k-近邻算法中k的出处。

从前面的分析可以看出，k-近邻算法没有显式的训练过程，在训练阶段仅仅是把样本保存起来，训练时间开销为零，待收到测试样本后再进行处理。这个算法存在两个关键点：

1. k值如何选择。在《机器学习实战》和西瓜书上都没有给出，只说了k通常是不大于20的整数。从实际测试来看，k取值不同，分类结果会有所不同，这个需要根据经验来选择。
2. 距离计算方式。在《机器学习实战》中采取的是欧式距离公式：

为了避免某个属性的取值范围过大，从而对整个距离的计算影响太大，可以采用数值归一化，将取值范围处理为0到1或-1到1之间，最简单的公式就是：

newValue = (oldValue - min) / (max - min)

从上述算法上可以看出，该算法的缺点：计算复杂度高(需要计算与每个训练样本之间的距离，通常训练样本比较大）、空间复杂度高。

当然这个算法也有许多优点：精度高、对异常值不敏感、无数据输入假定。

书中给出了一个使用k-近邻算法识别手写数字的完整例子，其错误率为1.2%。这已经是很高的精度了。而且西瓜书还给出了一个简化的证明，它的泛化错误率不超过贝叶斯最优分类器的错误率的两倍！

如果使用手写数字的训练样本预测印刷体数字样本，错误率会达到多少？

56.9%

有兴趣的同学可以访问 https://gitee.com/mogoweb/Machine_Learning_in_Action 获取印刷体数字样本进行测试。

这也印证了机器学习中的NFL（没有免费的午餐）定理。我们应该清楚的认识到，脱离具体问题，空泛地谈论“什么学习算法更好”毫无意义。

参考：

1. 《机器学习实战》p15 - 31
2. 《机器学习》p225 - p226