K近邻法(k-nearst neighbors,KNN)是一种很基本的机器学习方法了，在我们平常的生活中也会不自主的应用。比如，我们判断一个人的人品，只需要观察他来往最密切的几个人的人品好坏就可以得出了。这里就运用了KNN的思想。KNN方法既可以做分类，也可以做回归，这点和决策树算法相同。

KNN做回归和分类的主要区别在于最后做预测时候的决策方式不同。KNN做分类预测时，一般是选择多数表决法，即训练集里和预测的样本特征最近的K个样本，预测为里面有最多类别数的类别。而KNN做回归时，一般是选择平均法，即最近的K个样本的样本输出的平均值作为回归预测值。由于两者区别不大，虽然本文主要是讲解KNN的分类方法，但思想对KNN的回归方法也适用。由于scikit-learn里只使用了蛮力实现(brute-force)，KD树实现(KDTree)和球树(BallTree)实现，本文只讨论这几种算法的实现原理。其余的实现方法比如BBF树，MVP树等，在这里不做讨论。

1. KNN算法三要素

KNN算法我们主要要考虑三个重要的要素，对于固定的训练集，只要这三点确定了，算法的预测方式也就决定了。这三个最终的要素是k值的选取，距离度量的方式和分类决策规则。

对于分类决策规则，一般都是使用前面提到的多数表决法。所以我们重点是关注与k值的选择和距离的度量方式。

 

对于k值的选择，没有一个固定的经验，一般根据样本的分布，选择一个较小的值，可以通过交叉验证选择一个合适的k值。

选择较小的k值，就相当于用较小的领域中的训练实例进行预测，训练误差会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是泛化误差会增大，换句话说，K值的减小就意味着整体模型变得复杂，容易发生过拟合；
选择较大的k值，就相当于用较大领域中的训练实例进行预测，其优点是可以减少泛化误差，但缺点是训练误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，且K值的增大就意味着整体的模型变得简单。
一个极端是k等于样本数m，则完全没有分类，此时无论输入实例是什么，都只是简单的预测它属于在训练实例中最多的类，模型过于简单。

 

对于距离的度量，我们有很多的距离度量方式，但是最常用的是欧式距离，即对于两个n维向量x和y，两者的欧式距离定义为：

D(x,y)=(x1?y1)2+(x2?y2)2+...+(xn?yn)2???????????????????????????????√=∑i=1n(xi?yi)2??????????√D(x,y)=(x1?y1)2+(x2?y2)2+...+(xn?yn)2=∑i=1n(xi?yi)2

大多数情况下，欧式距离可以满足我们的需求，我们

延伸阅读

学习是年轻人改变自己的最好方式-Java培训,做最负责任的教育,学习改变命运,软件学习,再就业,大学生如何就业,帮大学生找到好工作,lphotoshop培训,电脑培训,电脑维修培训,移动软件开发培训,网站设计培训,网站建设培训学习是年轻人改变自己的最好方式