KNN ¶

1.概念理解 ¶

K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。即是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例（也就是所说的K个邻居）， 这K个实例的多数属于某个类，就把该输入实例分类到这个类中。

最近邻算法

介绍 K-近邻算法之前，首先说一说最近邻算法。最近邻算法（Nearest Neighbor，简称：NN），其针对未知类别数据 xx，在训练集中找到与 xx 最相似的训练样本 yy，用 yy 的样本对应的类别作为未知类别数据 xx 的类别，从而达到分类的效果。

如上图所示，通过计算数据 XuXu（未知样本）和已知类别 {ω1,ω2,ω3}{ω1,ω2,ω3}（已知样本）之间的距离，判断 XuXu 与不同训练集的相似度，最终判断 XuXu 的类别。显然，这里将绿色未知样本类别判定与红色已知样本类别相同较为合适。

K-近邻算法

K-近邻（K-Nearest Neighbors，简称：KNN）算法是最近邻（NN）算法的一个推广，也是机器学习分类算法中最简单的方法之一。KNN 算法的核心思想和最近邻算法思想相似，都是通过寻找和未知样本相似的类别进行分类。但 NN 算法中只依赖 1 个样本进行决策，在分类时过于绝对，会造成分类效果差的情况，为解决 NN 算法的缺陷，KNN 算法采用 K 个相邻样本的方式共同决策未知样本的类别,这样在决策中容错率相对于 NN 算法就要高很多，分类效果也会更好。

2.实现步骤 ¶

初始化距离为最大值

计算未知样本和每个训练样本的距离dist

得到目前K个最邻近样本中的最大距离maxdist

如果dist小于maxdist，则将该训练样本作为K-最近邻样本

重复步骤2,3,4，直到未知样本和所有训练样本的距离都算完

统计K个最近邻样本中每个类别出现的次数

选择出现频率最大的类别作为未知样本的类别

如果选择较小的K值，就相当于用较小的领域中的训练实例进行预测，“学习”近似误差会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是“学习”的估计误差会增大，换句话说，K值的减小就意味着整体模型变得复杂，容易发生过拟合；

如果选择较大的K值，就相当于用较大领域中的训练实例进行预测，其优点是可以减少学习的估计误差，但缺点是学习的近似误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，且K值的增大就意味着整体的模型变得简单。

K=N，则完全不足取，因为此时无论输入实例是什么，都只是简单的预测它属于在训练实例中最多的累，模型过于简单，忽略了训练实例中大量有用信息。

在应用中，k值一般取一个比较小的数值，通常采用交叉验证法来选择最优k值

1.3.3 分类决策规则 ¶

1.多数表决法

多数表决法类似于投票的过程，也就是在 K 个邻居中选择类别最多的种类作为测试样本的类别。

2.加权表决法

根据距离的远近，对近邻的投票进行加权，距离越近则权重越大，通过权重计算结果最大值的类为测试样本的类别。