1.K-NN算法

1.1K-NN近邻算法简介

k近邻法(k-nearest neighbor, k-NN)是1967年由Cover T和Hart P提出的一种基本分类与回归方法。它的工作原理是：存在一个样本数据集合，也称作为训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一个数据与所属分类的对应关系。输入没有标签的新数据后，将新的数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本最相似数据(最近邻)的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

1.2K-NN算法定义

KNN通过测量不同样本的特征值之间的距离进行分类。它的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。K通常是不大于20的整数。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

1.3K-NN算法的简单实例

举个简单的例子，我们可以使用k-近邻算法分类一个电影是爱情片还是动作片。

表1 电影数据集

表1 就是我们已有的数据集合，也就是训练样本集。这个数据集有两个特征，即打斗镜头数和接吻镜头数。除此之外，我们也知道每个电影的所属类型，即分类标签。用肉眼粗略地观察，接吻镜头多的，是爱情片。打斗镜头多的，是动作片。

2.问题描述

用原生python实现knn分类算法。采用鸢尾花作为数据集。利用已知鸢尾花训练集数据预测鸢尾花测试集中鸢尾花分类情况。

 

表2 鸢尾花测试集

 

表3 鸢尾花训练集

3.问题分析

3.1明确项目目标

利用KNN算法通过鸢尾花训练集中的分类数据对鸢尾花测试集中的数据进行分类。

利用MATLAB对鸢尾花数据集绘制散点图(如图1、图2所示)：

 

表1 鸢尾花训练数据集

 

图2 鸢尾花测试数据集

3.2分析过程，拆解项目

A.第一步：要对训练集以及测试集中数据统一进行归一化处理

B.第二步：对训练集数据进行处理，得到每一个样本的数据集合以及所属类别标签集合

C.第三步：对测试集数据进行处理，得到每一个样本的数据集合

D.第四步：计算训练样本和测试样本之间的欧几里德距离:

                       ρ=x2-x12+y2-y12                 (1)

                             X=x22+y22                       (2)

其中，ρ为点x1,y1与点x2,y2之间的欧氏距离；|X|为点x2,y2到原点的欧氏距离。(如图3所示，ab长度即为欧氏距离)

 

图3 欧氏距离

E.第五步：得到与测试样本距离最近的k个训练样本及其公共类别

F.第六步：计算预测准确率

G.第七步：得到测试结果

3.3逐步执行，代码实现

为了减小代码量以及方便阅读和后期使用时的更改，将采用函数封装的方式逐步实现各个部分的功能，最后结合所有函数功能，实现KNN算法的计算过程。

A.第一步代码实现：

 

B.第二步代码实现：

 

C．第三步代码实现：

 

D．第四步代码实现：

 

 

E.第五步代码实现：

将第五步分为两部分分别进行处理：

1.取得与测试样本距离最近的k个训练样本:

 

2.取得与测试样本距离最近的k个训练样本中的最公共类别

 

F.第六步代码实现：

 

G.第七步代码实现：

 

 

 

4.算法分析

4.1对3.3中所有函数及功能进行总结(如表4所示):

函数	功能
trainingFile2Matrix(filename)	处理训练数据集
testFile2Matrix(filename)	处理测试数据集
calculateDistance(train_example, test_example, example_length)	计算训练样本和测试样本之间的欧几里德距离
get_K_Neighbors(trainingSet, trainingLabel, test_example, k)	取得与测试样本距离最近的k个训练样本
getReasult(kNeighbors)	取得与测试样本距离最近的k个训练样本中的最公共类别
getAccuracy(testLabel, predictions)	计算预测的准确率
getNormolization(dataSet)	对数据进行归一化
write2File(filename, resultSet)	将测试结果写入文件

表4 函数及函数功能

4.2综合调用前面所有的功能函数，实现KNN算法的所有步骤

5.运行调试及运行

5.1调试过程

进行单步调试（见图4-5）

 

图4 单步调试

 

图5 单步调试

5.2运行结果

 

6.总结

KNN算法是机器学习中最简单的一种算法，该算法具有以下特点：

优点：精度高、对异常值不敏感、无数据输入假定

缺点：计算复杂度高、空间复杂度高

使用数据范围：数值型和标称型