《深度学习与图像识别：原理与实践》—3.1.2　KNN的算法实现

3.1.2　KNN的算法实现

3.1.1节简单讲解了KNN的核心思想以及距离度量，为了方便读者理解，接下来我们使用Python实现KNN算法。

本书使用的开发环境（开发环境的安装已经在第2章中介绍过）是Pycharm和Anaconda。

首先，我们打开Pycharm，新建一个Python项目，创建演示数据集，输入如下代码：

import numpy as np

import matplotlib.pyplot as plt

##给出训练数据以及对应的类别

def createDataSet():

    group = np.array([[1.0,2.0],[1.2,0.1],[0.1,1.4],[0.3,3.5],[1.1,1.0],[0.5,1.5]])

    labels = np.array(['A','A','B','B','A','B'])

    return group,labels

if __name__=='__main__':

    group,labels = createDataSet()

    plt.scatter(group[labels=='A',0],group[labels=='A',1],color = 'r', marker='*')

                     #对于类别为A的数据集我们使用红色六角形表示

    plt.scatter(group[labels=='B',0],group[labels=='B',1],color = 'g', marker='+')

                     #对于类别为B的数据集我们使用绿色十字形表示

    plt.show()

下面，我们对这段代码做一个详细的介绍，createDataSet用于创建训练数据集及其对应的类别，group对应的是二维训练数据集，分别对应x轴和y轴的数据。labels对应的是训练集的标签（类别），比如，[1.0, 2.0]这个数据对应的类别是“A”。

我们使用Matplotlib绘制图形，使读者能够更加直观地查看训练集的分布，其中scatter方法是用来绘制散点图的。关于Matplotlib库的用法（如果读者还不是很熟悉的话）可以参阅Matplotlib的基本用法。训练集的图形化展示效果如图3-2所示，对于类别为A的数据集我们使用红色五角形表示，对于类别为B的数据集我们使用绿色十字形表示，观察后可以发现，绿色十字形比较靠近屏幕的左侧；红色五角形比较靠近屏幕的右侧。

图3-2　KNN例子的散点图

通过Matplotlib，读者可以很直观地分辨出左边部分的数据更倾向于绿色十字点，而右边的数据则更倾向于红色五角形点。

接下来我们看一下如何使用Python（基于欧拉距离）实现一个属于我们自己的KNN分类器。示例代码如下：

def kNN_classify(k,dis,X_train,x_train,Y_test):

    assert dis == 'E' or dis == 'M', 'dis must E or M，E代表欧式距离，M代表曼哈顿距离'

    num_test = Y_test.shape[0]                #测试样本的数量

    labellist = []

    '''

   使用欧拉公式作为距离度量

    '''

    if (dis == 'E'):

        for i in range(num_test):

            #实现欧式距离公式

            distances = np.sqrt(np.sum(((X_train - np.tile(Y_test[i], (X_train.shape[0], 1))) ** 2), axis=1))

            nearest_k = np.argsort(distances)       #距离由小到大进行排序，并返回index值

            topK = nearest_k[:k]            #选取前k个距离

            classCount = {}

            for i in topK:                #统计每个类别的个数

                classCount[x_train[i]] = classCount.get(x_train[i],0) + 1

            sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)

            labellist.append(sortedClassCount[0][0])

        return np.array(labellist)

#使用曼哈顿公式作为距离度量

#读者自行补充完成

轮到你来：

尝试模仿上述代码，通过对曼哈顿距离的理解实现曼哈顿距离度量的Python版本。

下面我们来测试下KNN算法的效果，输入如下代码：

if __name__ == '__main__':

    group, labels = createDataSet()

    y_test_pred = kNN_classify(1, 'E', group, labels, np.array([[1.0,2.1],[0.4,2.0]]))

    print(y_test_pred)         #打印输出['A' 'B']，和我们的判断是相同的

需要注意的是，我们在输入测试集的时候，需要将其转换为Numpy的矩阵，否则系统会提示传入的参数是list类型，没有shape的方法。