写在前面

KNN近邻算法是最简单的机器学习算法，也正是因为其算法简单的特点，其具有非常好的实时性，在一些嵌入式设备中可以被轻易的部署。
KNN具有非常好实时性的同时，其对于一些分类问题也有很好的性能，在本文的鸢尾花识别中，如果选取合适的K，算法精度甚至可以达到97.5%以上。
KNN本身也具有非常多的变种，本文只是展示了其简单的一种变种。

本文的KNN紧邻算法原理

何为KNN？其英文，“K-Nearest Neighbors”非常好的概括了KNN算法的本质。以本文的分类问题为例来剖析：

• 样本的类别与其邻居(Neighbors)有关
• 与哪些邻居有关？与距离样本最近(Nearest)的K个邻居(Neighbors)有关
• 距离最近怎么定义？人工定义！本文算法使用的是欧氏距离

所以我们来总结一下，KNN算法是怎么来进行样本分类的：

• 首先根据人工定义的距离函数来计算待分类样本与已分类样本的距离
• 接着选取距离待分类样本最近的K个已分类样本
• 最后，对于本算法而言，最近的K个已分类样本中哪个类别的样本数量最多，那么待分类样本就属于此类别

算法实现

为了使用Python实现KNN紧邻算法，本实验将实现过程细分为如下⼏个部分：

• 首先是将整体样本可视化⽤以直观感受各个类型鸢尾花之间的特性差异
• 其次是划分待分类样本，就叫他test吧与已分类样本，就叫他train吧(但需要注意，KNN不需要任何的训练，我们叫他train只是为了区分样本名字)，用于在算法最后测试算法的准确性
• 接着是对已划分的test, train集合中的4种特性数据(sepal_length, sepal_width, petal_length, petal_width)进行最大最小归一化处理，用以消除不同量纲特征对结果的影响
• 接下来通过欧式距离公式，获得test和train之间的带有顺序的欧式距离的距离矩阵，并且同时获得距离矩阵每⼀个距离元素，即train集合，相之对应的在原数据集中的索引以及target类别标签
• 最后根据KNN近邻算法的定义，获得不同K下的预测结果以及算法准确率，并在此过程中规避可能出现的非正常情况，下面对各部分进行分析

数据集可视化

为了直观体现各个鸢尾花之间的特性差异，首先利用append()将不同类型的鸢尾花压入空list[]，利用plt.scatter()函数进行对不同类别鸢尾花进行散点图绘画，于此同时利用title(),xlabel(),grid(),legend(),show()等绘图函数实现绘制标题，坐标轴标签，显示网格，绘制散点标签，展示曲线等功能，其最终效果如下：

使用KNN算法对鸢尾花进行聚类分析
from sklearn.datasets import load_iris    #datasets模块
import numpy as np
import operator

iris = load_iris()    #加载鸢尾花数据
x = iris.data         #x有4个属性（sepal_length,sepal_width,petal_length,petal_width）
y = iris.target       #y代表有三类鸢尾花（Setosa，Versicolour，Virginica）

#可视化x中的各类别target
x_sepal_length_0 = []
x_sepal_length_1 = []
x_sepal_length_2 = []
x_petal_length_0 = []
x_petal_length_1 = [] 
x_petal_length_2 = [] 

for i in range(len(x)):
    if y[i] == 0:
        x_sepal_length_0.append(x[i , 0])
        x_petal_length_0.append(x[i , 1])
    elif y[i] == 1:
        x_sepal_length_1.append(x[i , 0])
        x_petal_length_1.append(x[i , 1])
    elif y[i] == 2:
        x_sepal_length_2.append(x[i , 0])
        x_petal_length_2.append(x[i , 1])

plt.title("target of each element in x")
plt.xlabel('x_sepal_length')
plt.ylabel('x_petal_length')
plt.grid(True)
plt.scatter(x_sepal_length_0, x_petal_length_0, color ='red', label = 'Setosa')
plt.scatter(x_sepal_length_1, x_petal_length_1, color ='blue', label = 'Versicolour')
plt.scatter(x_sepal_length_2, x_petal_length_2, color ='green', label = 'Virginica')
#显示图中的标签
plt.legend()
plt.show()

划分待分类样本(test)和已分类样本(train)

由于KNN的简单特性，因此此部分的train，其本身并无训练的意义，其作用仅是为测试集test提供欧式距离的计算数据。同时为了实验的准确性，规定test与train的比例为3:7。其提取方式为通过np.random.choice()函数获取原样本中规定数量的数据作为测试集test，并将在原样本中通过np.delete()函数剔除test，将剩余的样本作为训练集train。划分集合后同时需要记录各个元素在原样本的索引。可视化效果如下：

#随机划分测试集为总集合的30%，用于最后测试算法准确率
test_num = round(len(x) * 0.3)
acc = []
for i in range(1):
    test_index = np.random.choice(len(x), test_num, replace = False)

    x_test = x[test_index , :]        #data的测试集数据
    y_test = y[test_index]            #target的测试集数据

    train_index = np.arange(len(x))
    train_index = np.delete(train_index, test_index)

    x_train = x[train_index , :]      #data的训练集数据
    y_train = y[train_index]          #target的训练集数据

对各个特性进行最大最小归一化

由于各个特性之间的数值差异过大，为了消除这样的差异，需要进行对数据的归一化处理，在此对test, train分别进行通过np.amin(),np.amax()函数进行最大最小归一化处理：

#归一化(采用最大最小归一化)不同集合中鸢尾花4个属性

for i in range(4):
    x_train[: , i] = (x_train[: , i] - np.amin(x_train[: , i]))/(np.amax(x_train[: , i]) - np.amin(x_train[: , i]))
    x_test[: , i]  = (x_test[: , i] - np.amin(x_test[: , i]))/(np.amax(x_test[: , i]) - np.amin(x_test[: , i]))

建立带距离排序的各个信息矩阵

根据欧式距离定义有：

根据此公式建立具有如下特性的欧式距离矩阵：

其中每一个元素都储存了了该元素对所代表的的test与train之间的欧式距离，接下来需要对距离进行排序，在不使用numpy的情况下笔者是这样处理：

• 首先将距离矩阵的每一行与train各个元素相对应的索引利用zip()函数绑定为元组，并利用dict()函数创建字典，这样之后，字典中的key()意义为train在原样本中的索引，字典中的value()意义为行test与该train之间的欧式距离
• 接着利用sorted()函数对字典中的value()进行排序，同时更关键的可以提取与value()相对应的keys()值，即获得train排序后的在原样本中的索引

与此同时也可以通过该索引矩阵获得train所属的种类(Setosa，Versicolour，Virginica)，其最终效果如下：

• 首先是未排序的欧式距离矩阵：
  
• 同时获得排序后的欧式距离矩阵：
  
• 其次是与已经排序的欧式距离矩阵相之对应的train索引矩阵：
  
• 并且通过索引矩阵获得train在原样本中所属的种类矩阵：
  

#编写KNN算法，首先计算测试集和训练集之间的欧式距离 d = sqrt( (x - x0)^2 + (x1 - x10)^2 + (x2 - x20)^2 + (x3 - x30)^2 )
    #每行意义一个test数据，每列意义此test数据与列train数据对应的距离
    test_d = np.zeros((len(x_test),len(x_train)))
    for i in range(len(x_test)):
        for j in range(len(x_train)):
            each_test_d = np.sqrt(sum((x_test[i , :] - x_train[j , :])**2)) #计算每一个测试集中的元素距离训练集之间的距离
            test_d[i,j] = each_test_d

    #根据距离进行排序，创建字典
    test_2_train_array = np.zeros((len(x_test),len(y_train)))
    test_2_train_dist = np.zeros((len(x_test),len(y_train)))
    each_d = []
    for i in range(len(test_d)):
        train_2_test_d = test_d[i , :].tolist()            #每一个test数据与所有train之间的距离数组
        oj_distance = zip(train_index , train_2_test_d)    #打包元组(key = train的索引 , values = 该test与该train的欧式距离)
        test_d_dict = dict(oj_distance)                    #创建字典
        test_d_dict = sorted(test_d_dict.items(), key=lambda item:item[1])#对字典中的values进行排序
        for j in range(len(x_train)):
            test_2_train_array[i,j] = test_d_dict[j][0]#获取value对应的target标号
            test_2_train_dist[i,j] = test_d_dict[j][1]#获取排序后的欧式距离矩阵

    #获取target的所属的种类数组

    target_class = np.zeros((len(x_test),len(x_train)))

    for i in range(len(x_test)):
        for j in range(len(x_train)):
            target_class[i , j] = y[int(test_2_train_array[i , j])]

统计与test相邻最近的train样本,即实现KNN算法

当获得train在原样本中所属的种类矩阵之后，由于其本身就带有排序的距离信息，即第一列为相距test最近的元素，第二列次近，以此类推，这时，仅需输入K的取值即可，笔者在程序中默认K=5，根据KNN算法定义，统计种类矩阵中前5列的出现最多的种类作为该test元素的种类，并且同时为了防止有两种及以上类型都是出现次数最多的类型情况出现，需要利用count()对数组中最大数出现的次数进行判断，当最大数出现次数为大于等于1时，可以使用对最大数对应的欧式距离之和进行进行判断等方式，笔者在本算法中选取欧式距离和更小的种类作为该test样本最终的预测类型，其最终效果如下：

分析不同k下的准确率变化情况

最后利用for循环得到不同K下的不同的准确率，并利用plt.plot()函数进行图像绘制得到如下曲线，多次运行可以发现，当k <= 5时，KNN算法的准确率较高，效果较好。

写在最后

至此，实现了KNN最近邻识别鸢尾花的任务，并且从最后的结果可以看出，算法有着不俗的准确度，在深度学习大火的今天，对于一些简单的任务，我们或许也可以返璞归真。在下一篇博客中，笔者将利用KNN实现MNIST手写数字体识别。