Python实现k-近邻算法

k-近邻算法简述
k-近邻算法（kNN）采用测量不同特征值之间的距离方法进行分类。工作原理：首先存在一个样本数据集合（训练样本集），并且样本集中每个数据都存在标签（监督学习）。所谓的标签就是样本集每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征相比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们只选择样本数据集中的前k个最相似的数据，这就是k近邻算法中k的出处，k通常不大于20的整数。最后选择k个最相似数据中出现次数最多的分类，作为新数据的分类。这里的距离是指d=sqrt{(X1-X2)^2+(Y1-Y2)^2}。其中(X1,Y1)表示某个样本的两个特征值。下面以一个具体的例子来说明：电影分类的例子，使用k-近邻算法分类爱情片和动作片。有人曾经统计过很多电影的打斗镜头和接吻镜头，在这里我们就选取打斗镜头和接吻镜头的次数作为特征来分类，下面显示了六部电影的打斗和接吻镜头次数。假设有一部未看过的电影，如何确定它是爱情片还是动作片？我们使用kNN来确定。

电影名称                              打斗镜头                     接吻镜头                     电影类型
California Man                          3                           104                         爱情片
He's Not Really into Dudes      2                           100                         爱情片
Beautiful Woman                      1                           81                          爱情片
Kevin Longblade                     101                         10                          动作片
Robo Slayer 3000                      99                          5                           动作片
Amped 2                                   98                          2                           动作片
?                                                18                          90                          未知                     
首先我们需要知道这个位置电影存在多少个打斗镜头和接吻镜头，数据如上表？数据，只知道打斗镜头和接吻镜头的次数。即使不知道未知电影属于哪种类型，我们也可以通过某种方法求出来。首先计算未知电影与样本集中其他电影的距离。如下表：

电影名称                               与未知电影的距离
California Man                              20.5
He's Not Really into Dudes          18.7
Beautiful Woman                          19.2
Kevin Longblade                           115.3
Robo Slayer 3000                          117.4
Amped 2                                        118.9
在这里我们可以将打斗镜头次数和接吻镜头次数作为两个特征，即（打斗镜头次数，接吻镜头次数），然后计算距离。现在我们知道了样本集中所有电影与未知电影的距离，按照距离递增排序，找到k个距离最近的电影。假定这里k=3，则三个最靠近的电影依次是He’s Not Really into Dudes 、 Beautiful Woman 以及California Man 。k-近邻算法按照距离最近的三部电影的类型，决定未知电影的类型。而这三部全是爱情片，因此我们判定未知电影是爱情片。

k-近邻算法的一般流程
1、收集数据：可以使用任何方法。

2、准备数据：距离计算所需的数值，最好是结构化的数据格式。

3、分析数据：可以使用任何方法。

4、训练算法：此步骤不适用于k-近邻算法。

5、测试算法：计算错误率。

6、使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理。

关于k-近邻算法如何使用python实现的例子不在此赘述，具体的例子会上传到github，感兴趣的可以去看看，这里只要阐述思想。