机器学习-识别手写字母的kNN算法

　　本文主要使用kNN算法对字母图片进行特征提取和分类. 内容如下:

　　kNN算法和相关的Python模块介绍，字母图像特征提取，kNN算法和kNN算法分析

　　I. kNN算法简介

　　K最近邻（kNN，k-NearestNei*敏*感*词*or）分类算法是机器学习算法中最简单的方法之一. 所谓的K个最近邻居是指k个最近邻居，这意味着每个样本都可以由其最近的k个邻居表示. 我们将样本分为训练样本和测试样本. 为了对测试样本t进行分类，kNN的方法是首先计算从样本t到所有训练样本的欧几里得距离，然后找到距离它们最短的k个训练样本，并使用出现次数最多的类别. k个训练样本. 样本t的类别.

　　欧氏距离的计算公式:

　　假设每个样本都有两个特征值，例如A: （a1，b1）B: （a2，b2），则AB的欧几里得距离为

　　

　　例如: 根据下图中前四名学生的成绩和成绩来预测第五名小白的成绩.

　　

　　我们可以看到: 汉语和数学成绩是学生的特征，而成绩是学生的类别.

　　前四个学生是训练样本，第五个学生是测试样本. 现在，我们使用kNN算法来预测第五名学生的成绩，而k为3.

　　我们可以根据上面的欧几里德距离公式进行计算

　　d（5-1）=

　　

　　= 7 d（5-2）=

　　

　　= 30

　　d（5-3）=

　　

　　= 6 d（5-4）=

　　

　　= 19.2

　　由于k为3，我们寻找3个最接近的样本，即编号分别为3、1，和4的学生，其成绩分别为B，B和A. 在这三个样本的分类中，B出现两次，A和B出现次数最多，因此5号学生的等级可能是B

　　通用Python模块

　　NumPy: NumPy是Python的开源数值计算扩展. 该工具可用于存储和处理大型矩阵，并且比Python自己的嵌套列表结构更有效.

　　PIL: Python Imaging Library，是Python平台事实上的图像处理标准库，具有非常强大的功能和易于使用的API. 但是PIL软件包主要用于Python2，并且与Python3不兼容，因此Pillow用于Python3，Daniel根据PIL移植了Pillow. 两者的用法是相同的.

　　以上两个Python库均可通过pip安装.

　　pip3 install [name]

　　Python附带了一个标准库: shutil模块提供了大量的高级文件操作，尤其是用于文件的复制和删除. 主要功能是目录和文件操作以及压缩操作. 操作员模块是Python操作员库，而os模块是Python系统和与操作系统相关的功能库.

　　第二，对图片进行特征提取

　　1. 采集手写字母的图片资料

　　有许多网站提供机器学习数据集. 例如，知乎整理了我采集的手写字母图片资源. 以下链接是: 密码: i725 by_class.zip压缩包是已分类图片的样本，您可以直接下载使用.

　　2. 提取图片素材的特征

　　最简单的方法是将图片转换为由0和1组成的txt文件，例如

　　

　　

　　

　　转换代码如下:

　　 1 import os

2 import shutil

3 from PIL import Image

4

5

6 # image_file_prefix png图片所在的文件夹

7 # file_name png png图片的名字

8 # txt_path_prefix 转换后txt 文件所在的文件夹

9 def generate_txt_image(image_file_prefix, file_name, txt_path_prefix):

10 """将图片处理成只有0 和 1 的txt 文件"""

11 # 将png图片转换成二值图并截取四周多余空白部分

12 image_path = os.path.join(image_file_prefix, file_name)

13 # convert('L') 将图片转为灰度图 convert('1') 将图片转为二值图

14 img = Image.open(image_path, 'r').convert('1').crop((32, 32, 96, 96))

15 # 指定转换后的宽 高

16 width, height = 32, 32

17 　　 img.thumbnail((width, height), Image.ANTIALIAS)

18 # 将二值图片转换为0 1，存储到二位数组arr中

19 arr = []

20 for i in range(width):

21 pixels = []

22 for j in range(height):

23 pixel = int(img.getpixel((j, i)))

24 pixel = 0 if pixel == 0 else 1

25 pixels.append(pixel)

26 arr.append(pixels)

27

28 # 创建txt文件(mac下使用os.mknod()创建文件需要root权限，这里改用复制的方式)

29 text_image_file = os.path.join(txt_path_prefix, file_name.split('.')[0] + '.txt')

30 empty_txt_path = "/Users/beiyan/Downloads/empty.txt"

31 shutil.copyfile(empty_txt_path, text_image_file)

32

33 # 写入文件

34 with open(text_image_file, 'w') as text_file_object:

35 for line in arr:

36 for e in line:

37 text_file_object.write(str(e))

38 text_file_object.write("\n")

　　将所有材料转换为txt后，它们分为两个部分: 训练样本和测试样本.

　　三，kNN算法的实现

　　1. 将txt文件转换为一维数组的方法:

　　1 def img2vector(filename, width, height):

2 """将txt文件转为一维数组"""

3 return_vector = np.zeros((1, width * height))

4 fr = open(filename)

5 for i in range(height):

6 line = fr.readline()

7 for j in range(width):

8 return_vector[0, height * i + j] = int(line[j])

9 return return_vector

　　2. 对测试样本执行kNN分类，并返回测试样本的类别:

　　 1 import numpy as np

2 import os

3 import operator

4

5

6 # test_set 单个测试样本

7 # train_set 训练样本二维数组

8 # labels 训练样本对应的分类

9 # k k值

10 def classify(test_set, train_set, labels, k):

11 """对测试样本进行kNN分类,返回测试样本的类别"""

12 # 获取训练样本条数

13 train_size = train_set.shape[0]

14

15 # 计算特征值的差值并求平方

16 # tile(A,(m,n))，功能是将数组A行重复m次 列重复n次

17 diff_mat = np.tile(test_set, (train_size, 1)) - train_set

18 sq_diff_mat = diff_mat ** 2

19

20 # 计算欧式距离 存储到数组 distances

21 sq_distances = sq_diff_mat.sum(axis=1)

22 distances = sq_distances ** 0.5

23

24 # 按距离由小到大排序对索引进行排序

25 sorted_index = distances.argsort()

26

27 # 求距离最短k个样本中 出现最多的分类

28 class_count = {}

29 for i in range(k):

30 near_label = labels[sorted_index[i]]

31 class_count[near_label] = class_count.get(near_label, 0) + 1

32 sorted_class_count = sorted(class_count.items(), key=operator.itemgetter(1), reverse=True)

33 return sorted_class_count[0][0]

　　3. 统计分类错误率

　　 1 # train_data_path 训练样本文件夹

2 # test_data_path 测试样本文件夹

3 # k k个最近邻居

4 def get_error_rate(train_data_path, test_data_path, k):

5 """统计识别错误率"""

6 width, height = 32, 32

7 train_labels = []

8

9 training_file_list = os.listdir(train_data_path)

10 train_size = len(training_file_list)

11

12 # 生成全为0的训练集数组

13 train_set = np.zeros((train_size, width * height))

14

15 # 读取训练样本

16 for i in range(train_size):

17 file = training_file_list[i]

18 file_name = file.split('.')[0]

19 label = str(file_name.split('_')[0])

20 train_labels.append(label)

21 train_set[i, :] = img2vector(os.path.join(train_data_path, training_file_list[i]), width, height)

22

23 test_file_list = os.listdir(test_data_path)

24 # 识别错误的个数

25 error_count = 0.0

26 # 测试样本的个数

27 test_count = len(test_file_list)

28

29 # 统计识别错误的个数

30 for i in range(test_count):

31 file = test_file_list[i]

32 true_label = file.split('.')[0].split('_')[0]

33

34 test_set = img2vector(os.path.join(test_data_path, test_file_list[i]), width, height)

35 test_label = classify(test_set, train_set, train_labels, k)

36 print(true_label, test_label)

37 if test_label != true_label:

38 error_count += 1.0

39 percent = error_count / float(test_count)

40 print("识别错误率是:{}".format(str(percent)))

　　以上完整的代码地址:

　　4. 测试结果

　　训练样本: 0-9，a-z，A-Z，共有62个字符，每个字符选择120个训练样本，总共7440个训练样本. 每个角色选择20个测试样本，总共1200个测试样本.

　　尝试更改条件，测得的识别率如下:

　　

　　四个kNN算法分析

　　从以上部分的结果可以看出，knn算法对手写字母的识别率并不理想.

　　原因可能如下:

　　1. 图像特征提取太简单，图像的边缘更加空白，图像中字母的中心位置可能并非全部对应

　　2. 由于某些英文字母的大小写相似，因此很容易识别错误.

　　3. 样本量很小，每个角色最多只有300个训练样本. 真正的训练需要海量数据

　　在随后的文章中，尝试使用其他学习算法来提高分类识别率. 欢迎同道人有更好的意见！