KNN算法

• KNN算法的简介：KNN算法也称K近邻算法，就是K个最近的邻居的意思。即每个样本都可以用与它相距最近的K个邻居来代表。

• KNN算法的核心是：如果一个样本在特征空间中的K个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特征。对于当前待分类的样本,需要大量已知分类的样本的支持，其中K通常是不大于20的数。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最近邻的一个或者几个样本的类别来决定待分类样本所属的类别。因此KNN是一种有监督学习算法。

• KNN算法的适用情况是：KNN算法在分类时只与极少数相邻的样本有关。由于KNN算法主要靠待判别样本的周围有限个临近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分类样本集来说，KNN算法较合适。

• KNN算法的用途：分类和回归。KNN做回归和分类的主要区别在于最后做预测的时候决策方式不同。KNN做分类预测时，一般是选择多数表决法，即训练集里和预测的样本特征最近的K个样本里有最多类别数的类别。而KNN做回归时，一般选择平均法，即最近的K个样本的样本输出的平均值作为回归预测值。两者区别不大。

• KNN算法描述：（Description of KNN algorithm）
  (1) : 计算测试数据与各个训练数据之间的距离
  (2) : 按照距离的递增关系进行排序
  (3) : 选取距离最小的K个点
  (4) : 确定前K个点所在类别的出现频率
  (5) : 返回前K个点中出现频率最高的类别作为测试数据的预测分类
  所以KNN算法我们主要考虑三个重要的要素，对于固定的训练集，只要这三点确定了，算法的预测方式也就决定了。这三个最终的要素是K值的选取，距离度量的方式和分类决策的规则。
  对于分类决策的规则，一般都是使用前面提到的多数表决法，所以我们重点关注K值的选择和距离的度量方式。

• K值的选择:
  (1)对于K值的选择,没有一个固定的经验,一般根据样本的分布,选择一个较小的值, 可以通过交叉验证选择一个合适的K值。
  (2)选择较小的K值,就相当于用较小的邻域中的训练实例进行预测,训练误差会减小,只有与输入实例较近或相似的训练实例才会对预测结果起作用,与此同时带来的问题是泛化误差会增大,换句话说,K值的减小就意味着整体模型变复杂,容易发生过拟合。
  (3)选择较大的K值,就相当于用较大邻域中的训练实例进行预测,其优点是可以减少泛化误差,但缺点是训练误差会增大。这时候,与输入实例较远(不相似的)训练实例也会对预测器作用，使预测发生错误,且K值的增大就意味着整体的模型变简单。
  (4)一个极端的K是等于样本数m,即完全没有分类，此时无论输入实例是什么，都只是简单的预测它属于训练实例中最多的类，模型过于简单。

• KNN算法的距离度量方式
  

• KNN算法的优缺点