算法原理

K最近邻(KNN，k-NearestNeighbor)分类算法是数据挖掘分类技术中最简单的方法之一。
给定测试样本，基于某种距离度量找出训练集中与其最靠近的K个训练样本，然后基于这 K个”邻居”的信息来进行预测。

KNN 算法的核心思想是如果一个样本在特征空间中的 K 个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。

具体步骤

给定训练样本集/(/begin{gather*}S=/{t_1,t_2,t_3…t_s/}/end{gather*}/)和一组类属性/(/begin{gather*}C=/{c_1,c_2,c_3…c_m/}(m/leq s)/end{gather*}/) ，对样本进行分类，KNN 算法的基本步骤为：

（1）先求出 t 与 S 中所有训练样本/(/begin{gather*}t_i(1/leq i /leq s)/end{gather*}/)的距离/(/begin{gather*}dist_{ed}(t,t_i)/end{gather*}/) ，并对所有求出的/(/begin{gather*}dist_{ed}(t,t_i)/end{gather*}/)值递增排序；
（2）选取与待测样本距离最小的 K 个样本，组成集合 N；
（3）统计 N 中 K 个样本所属类别现的频率；
（4）频率最高的类别作为待测样本的类别。

举例说明

如果没看懂上面在说什么，没关系，举个例子这样能更好的理解一下，这里采用的是欧氏距离

假设 测试集有2和11，其中K=4；对测试集分别计算其与训练集的欧氏距离，得到如下结果

对测试集与训练集的距离进行排序，选取距离最小的前四（k=4）个

在测试集2，距离最小的四个（k=4）训练集数据中，属于类别1的有3个，属于类别2的有1个，所以测试集2的类别为1

在测试集11，距离最小的四个（k=4）训练集数据中，属于类别1的有1个，属于类别2的有3个，所以测试集11的类别为2

相信通过这个例子，大家能够很好的理解KNN算法的具体步骤了。
好了，话不多说，下面还是上代码。

KNN算法代码