机器学习-mnist kNN算法识别（python） - 好文

方以类聚，物以群分

---《周易·系辞上》

测试环境：python3.6、win7 32bit、x86。

在上一篇文章中介绍了mnist数据的格式，以及用python如何读取mnist数据并转化成numpy格式的数据（
https://blog.csdn.net/eleclike/article/details/79968574
<https://blog.csdn.net/eleclike/article/details/79968574>
），本文将从机器学习众多算法中比较直观易于理解的kNN（k近邻）算法介绍如何识别mnist图片。

1 什么是kNN

将待测试的数据每个特征和训练样本数据的每个特征进行比较
，然后提取k个最邻近的训练样本数据，统计这k个训练样本数据的分类标签，其中出现次数最多的标签所表示的类别就是待测试数据的类别。kNN的含义就是k个最相近的
“邻居”。这里面怎么进行每个特征的比较就会有很多种方法，其中比较常用的就是距离值。

1.1 一维数据的kNN

通常一个样本数据有很多个特征值，比如一张图片少则几百个像素，多则几万个像素，而人脑在处理3维以上空间（3个多的特征）时，需要脑补的画面比较多，直观理解起来比较困难，一般需要借助数学工具来抽象表达，而在处理一维和二维空间时就会得心应手的多。下面先以最直观的一维数据来看看kNN算法是个什么样子的，这时的样本就只有1个特征，最后我们再扩展到高维空间。

下图中在一条直线上有A类标签的3个训练样本，它们的特征值分别为x0=2,x1=3,x2=4，B类标签的训练样本有4个，它们的特征值分别为x3=10,x4=11,x5=12,x6=14，在这个训练集中共有7个样本，现在有一个待测试对象，它的值为x=6。它应该被分类为A还是B呢？

计算x=6与其他7个点的直线距离，分别为x-x0=4,x-x1=3,x-x2=2 和
x-x3=4,x-x4=5,x-x5=6,x-x6=8，得到了7个距离值，将这7个距离值从小到大排序得到训练样本顺序为A,A,A(或者B),B（或者A）,B,B,B。

如果取k=1，最近的1个邻居为A，所以x属于类别A。

如果取k=2，最近的2个邻居都是A，所以x属于类别A。

如果取k=3，最近的3个邻居中3个A，或者2个A和1个B，A的类别超过50%，所以x的类别还是A。

如果取k=4，最近的4个邻居中3个A，1个B，A的类别超过50%，x的类别还是A。

如果取k=5，最近的5个邻居中3个A，2个B，x类别为A。

如果取k=6，最近的6个邻居中3个A，3个B，x的类别可以为A，也可以为B。

如果取k=7，最近的7个邻居在4个B，3个A，x的类别变成了B。

从上面的k取值可以得到一些经验：

1）k值越接近样本数，类别就和直观上看到的结果相反了，所以在选择k值时应与样本数相比要足够小；

2）如果k的值为偶数，有可能出现了类别各占一半的情况，需要加入判别机制。

1.2 二维数据的kNN

前面我们分析了一维数据的kNN算法，现在扩展到二维空间，也就是每一个样本数据有2个特征。看下图，其中有A类3个点，B类4个点。

################### 样本数据初始化 #A类数据 xcord_a=[2.2,2.4,1.1]#x轴坐标
ycord_a=[1.4,2.3,3.4]#y轴坐标 #B类数据 xcord_b=[8.3,9.2,10.2,11.2]
ycord_b=[7.3,8.3,11.1,9.3] #待测试样本 xcord_x=[4.6] ycord_x=[3.4]

现在开始计算待测试数据(x=4.6,y=3.4)和样本数据的距离，在二维空间中距离=x差值平方+y差值平方再开二次方。比如与
A样本的第1个点的距离为：((2.2-4.6)^2 + (1.4-3.4)^2)^0.5 = 3.124，样本数量太多不一一计算，直接show me the
code：
''' author: eleclike date: 2018-4-15 environment: python3.6,win7-32bit
description: 二维特征样本的knn算法演示 comment: https://blog.csdn.net/eleclike ''' import
numpy from matplotlib import pyplot as plt print('\n\n\n') ###################
样本数据初始化 #A类数据 xcord_a=[2.2,2.4,1.1]#x轴坐标 ycord_a=[1.4,2.3,3.4]#y轴坐标 #B类数据
xcord_b=[8.3,9.2,10.2,11.2] ycord_b=[7.3,8.3,11.1,9.3] #待测试样本 xcord_x=[4.6]
ycord_x=[3.4] #################### 显示数据 fig = plt.figure() ax =
fig.add_subplot(111) #ax.scatter(xcord,ycord, c=colors, s=markers) type1 =
ax.scatter(xcord_a, ycord_a, s=20, c='red')#s=后面的数值是这个点的大小，c=表示颜色 type2 =
ax.scatter(xcord_b, ycord_b, s=20, c='green') type3 = ax.scatter(xcord_x,
ycord_x, s=20, c='blue') ax.legend([type1, type2, type3], ["A", "B", "x"],
loc=2) #loc是从右上角开始数值为1的逆时针4个角的位置，范围1~4
ax.axis([1,12,1,12])#坐标范围，前2个数值是x坐标的范围，后2个是y轴坐标范围 plt.xlabel('x cord')
plt.ylabel('y cord') plt.show() print('\n\n\n') ####################
计算待测试对象和样本数据间的差值 #取待测试数据的坐标值 x = xcord_x[0] y = ycord_x[0]
print('待测试对象坐标x=%f，y=%f'%(x,y)) #计算和A类样本的距离值 dista = []#保存和A类样本的距离值 ind = 0 for
xa in xcord_a: ya = ycord_a[ind]#取对应y点坐标 dist = ((x-xa)**2 +
(y-ya)**2)**0.5#计算待测试数据与当前样本坐标的距离
print('A:ind=%d,cord:(%f,%f),dist=%f'%(ind,xa,ya,dist)) dista.append(dist) ind
+= 1 #计算和B类样本的距离值 distb = []#保存和B类样本的距离值 ind = 0 for xb in xcord_b: yb =
ycord_b[ind]#取对应y点坐标 dist = ((x-xb)**2 + (y-yb)**2)**0.5#计算待测试数据与当前样本坐标的距离
print('B:ind=%d,cord:(%f,%f),dist=%f'%(ind,xb,yb,dist)) distb.append(dist) ind
+= 1 print('\n\n\n')

计算的结果显示如下：

取k=1，最小的差值为A：ind=1，所以待测试对象归类为A。

取k=2，最近的2个邻居都是A：ind=1,0，所以归类为A。

取k=3，最近的2个邻居也都是A：ind=1,0,2，所以也归类为A。

2 kNN算法的实现

前面的章节介绍了如何在一维和二维空间里进行knn分类，即在样本只有1个或2个特征时如何分类，但是实际应用中，样本的特征值数量要大的多，比如一张mnist图片是28*28大小的图片，每个像素对应成一个特征，总共包含有784个特征，如果再使用前面章节介绍的方法则会出现表达上的困难，如果引入矩阵来进行描述则相对要容易的多。还是先回到前面的2维空间的例子，我们的训练样本有7个，其他3个属于A类，4个属于B类，每个样本有2个特征（x和y坐标），整个样本集就可以表示为一个7x2的矩阵,第0列为x坐标，第1列为y坐标：

待分类数据为：

test_data = [4.6，3.4]

训练标签为：

train_label: ['A', 'A', 'A', 'B', 'B', 'B', 'B']

训练数据为(红色为特征x0)：

train_dataset:

[[ 2.2  1.4]

[ 2.4  2.3]

[ 1.1  3.4]

[ 8.3  7.3]

[ 9.2  8.3]

[10.2 11.1]

[11.2 9.3]]

kNN算法步骤：

第1步，用待分类数据的第0列去减训练样本的每一行的第0列，第1列减第1列：

diff_mat = [

[4.6-2.2 3.4-1.4]

[4.6-2.4 3.4-2.3]

[4.6-1.1 3.4-3.4]

[4.6-8.3 3.4-7.3]

[4.6-9.2 3.4-8.3]

[4.6-10.2 3.4-11.1]

[4.6-11.2 3.4-9.3]

]=

[[ 2.4 2. ]

[ 2.2 1.1]

[ 3.5 0. ]

[-3.7 -3.9]

[-4.6 -4.9]

[-5.6 -7.7]

[-6.6 -5.9]]

第2步，这2个差值分别求平方

sq_diff_mat:

[[ 5.76 4. ]

[ 4.84 1.21]

[12.25 0. ]

[13.69 15.21]

[21.16 24.01]

[31.36 59.29]

[43.56 34.81]]

第3步，分别求每一行的第1列和第2列的和

sq_dist: [ 9.76 6.05 12.25 28.9 45.17 90.65 78.37]

第4步，将第3步计算的每个数值开平方

distance: [3.12409987 2.45967478 3.5        5.37587202 6.72086304 9.52102936
8.85268321]

第5步，计算distance中每个数字在整个distance排序中的索引值：

dist_index: [1 0 2 3 4 6 5]

第6步，根据k的值选择前面k个数据，看对应的类别A还是B占多数，则表示x属于哪个类别。

排序后的分类结果： [('A', 3)]

到了SHOW ME THE CODE的时间:
''' author： eleclike date： 2018-4-10 description： knn分类算法的实现 comment：
python3.6,win7 32bit https://blog.csdn.net/eleclike ''' from numpy import *
import operator def knn_classify(test_data, train_dataset, train_label, k):
train_dataset_amount = train_dataset.shape[0]#行数，也即训练样本的的个数，shape[1]为列数
print('train_label:',train_label) print('train_dataset:',train_dataset)
#将输入test_data变成了和train_dataset行列数一样的矩阵 test_rep_mat = tile(test_data,
(train_dataset_amount,1))#tile(mat,(x,y)) Array类 mat 沿着行重复x次，列重复y次 diff_mat =
test_rep_mat - train_dataset print('diff_mat:',diff_mat) #求平方，为后面求距离准备
sq_diff_mat = diff_mat**2 print('sq_diff_mat:',sq_diff_mat)
#将平方后的数据相加，sum(axis=1)是将一个矩阵的每一行向量内的数据相加，得到一个list，list的元素个数和行数一样;sum(axis=0)表示按照列向量相加
sq_dist = sq_diff_mat.sum(axis=1) print('sq_dist:',sq_dist) #开平方，得到欧式距离
distance = sq_dist**0.5 print('distance:',distance) #argsort
将元素从小到大排列，得到这个数组元素在distance中的index(索引)，dist_index元素内容是distance的索引 dist_index =
distance.argsort() print('dist_index:',dist_index) class_count={} for i in
range(k): label = train_label[dist_index[i]]
#如果属于某个类，在该类的基础上加1，相当于增加其权重，如果不是某个类则新建字典的一个key并且等于1 class_count[label] =
class_count.get(label,0) + 1 #降序排列 class_count_list =
sorted(class_count.items(), key=operator.itemgetter(1), reverse=True)
print('排序后的分类结果：',class_count_list) return class_count_list[0][0]
############################################################ if __name__ ==
'__main__': print('\n\n') train_data_set=array([[2.2,1.4],\ [2.4,2.3],\
[1.1,3.4],\ [8.3,7.3],\ [9.2,8.3],\ [10.2,11.1],\ [11.2,9.3]]) train_label =
['A','A','A','B','B','B','B'] test_data = [4.6,3.4]
print('分类结果为：',knn_classify(test_data,train_data_set,train_label,3))

3 kNN算法识别mnist图片

利用上一篇文章中（https://blog.csdn.net/eleclike/article/details/79968574
<https://blog.csdn.net/eleclike/article/details/79968574>
）介绍的获取数据的方法生成训练样本的numpy array，然后通过输入选择测试样本中偏移位置和图片数量，生成测试样本的numpy array
数据，然后每张图片进行分类，再将分类的结果和测试样本的标签比较，最后计算总的错误率。
''' author: eleclike date: 2018-4-15 environment: python3.6,win7-32bit
description: 二维特征样本的knn算法演示 comment: https://blog.csdn.net/eleclike ''' from
createmat import * from knn import * '''
解析输入的字符，如果符合2个数字的输入，则开始测试。如果是其他格式，则返回类型为string，主程序中判断是否继续 ''' def
get_cmd_pars(cmd_str): cmd_medum=[] pars_ret=[] type_ret = 'digit' cmd_list =
cmd_str.split(sep=' ')#切割输入的字符串 for cl in cmd_list:#这里将空串清除 if cl != '':
cmd_medum.append(cl) for cr in cmd_medum:#这里判断所有输入的参数是否是纯数字 if not
cr.isdigit(): type_ret = 'string' else: pars_ret.append(int(cr)) if
len(pars_ret)<2:#判断输入的参数是否大于2个数字 type_ret = 'string' return type_ret,pars_ret
################################################# if __name__ == '__main__':
train_image_file = '..\\data\\mnist\\train-images.idx3-ubyte' train_label_file
= '..\\data\\mnist\\train-labels.idx1-ubyte' test_image_file =
'..\\data\\mnist\\t10k-images.idx3-ubyte' test_label_file =
'..\\data\\mnist\\t10k-labels.idx1-ubyte' #选择所有图片作为训练样本。 train_image_mat,
train_label_list =
read_image_label_all_vector(train_image_file,train_label_file) #
test_image_mat, test_label_list =
read_image_label_all_vector(test_image_file,test_label_file)
#选择部分数据作为训练集，第3个参数为偏移起始位置，第4个参数是训练样本数 # train_image_mat, train_label_list =
read_image_label_vector(train_image_file,train_label_file,0,5000) while True:
#-----------交互式输入控制开始----------------- #如果输入的样本数量为0，判断是否退出，如果不为0，继续开始分类。 cmd =
input('输入测试样本偏移和数量(比如 100 50):') type_ret,par_ret = get_cmd_pars(cmd)#解析输入的字符串
if type_ret == 'digit':#如果全部为数字 offset = par_ret[0] amount = par_ret[1] if
amount == 0: continue else: #如果不是数字，提示是否退出程序 cmd = input('格式不正确，输入Y(y)确定要退出:')
if cmd == 'y' or cmd == 'Y':#输入了y则表示要退出程序 break continue#没有输入y表示继续循环
#-----------交互式输入控制结束----------------- #根据前面的输入偏移和数量，开始读出测试样本 test_image_mat,
test_label_list =
read_image_label_vector(test_image_file,test_label_file,offset,amount) #开始分类
err_count = 0.0#记录错误数量 for i in range(len(test_image_mat)):
print('当前进度：%2.2f%%'%(100.0*i/len(test_image_mat))) #利用knn算法进行分类 class_result =
knn_classify(test_image_mat[i], train_image_mat, train_label_list, 5)#计算分类结果
print( "第 %d 张图片, 分类器结果: %d, 实际值: %d" % (i,class_result,
test_label_list[i]),end=' ') #判断分类结果是发和标签一致 if (class_result !=
test_label_list[i]): print(' 分类错误！',end = ' ') err_count += 1.0 #打印错误率
print('当前错误率：%2.2f%%' % (100.0*err_count/(i+0.01))) print( "\n总错误数: %d" %
err_count) print( "总错误率: %2.2f%%" % (100.0*err_count/len(test_image_mat)))

比如读取偏移5000开始的200张图片，错误率为1.5%。

读取所有图片测试错误率为3.4%：

4 结语

本文先从1维数据、2维数据描述knn算法，可以直观地理解其算法实现的各个步骤的含义，在此基础上再扩展到高维空间。
本文中完整代码和工程文件：https://download.csdn.net/download/eleclike/10369494
<https://download.csdn.net/download/eleclike/10369494>

热门工具换一换