k近邻算法-手写识别系统

云计算 waitig 626℃ 百度已收录 0评论

本节我们一步步地构造使用k-近邻分类器的手写识别系统。为了简单起见,这里构造的系统 只能识别数字09,参见下图。需要识别的数字已经使用图形处理软件,处理成具有相同的色 彩和大小:宽髙是32像素x 32像素的黑白图像。尽管采用文本格式存储图像不能有效地利用内存空间,但是为了方便理解,我们还是将图像转换为文本格式。

该数据集合修改自“手写数字数据集的光学识别”一文中的数据集合,该文登载于2010年10月3日UCI机器学习 资料库中http://archive.ics.ud.edu/ml。作者是土耳其伊斯坦布尔海峡大学计算机工程系的E.AlpaydinC.

使用k-近邻算法的手写识别系统

  • 收集数据:提供文本文件。
  • 准备数据:编写函数classify0(),将图像格式转换为分类器使用的list格式。
  • 分析数据:在Python命令提示符中检查数据,确保它符合要求。
  • 训练算法:此步驟不适用于各近邻算法。
  • 测试算法:编写函数使用提供的部分数据集作为测试样本,测试样本与非测试样本的区别在于测试样本是已经完成分类的数据,如果预测分类与实际类别不同,则标记为一个错误。
  • 使用算法:本例没有完成此步驟,若你感兴趣可以构建完整的应用程序,从图像中提 取数字,并完成数字识别,美国的邮件分拣系统就是一个实际运行的类似系统。

准备数据:将图像转换为测试向量

目录trainingDigits中包含了大约2000个例子, 每个数字大约有200样本;目录testDigits中包含了大约900个测试 数据。我们使用目录trainingDigits中的数据训练分类器,使用目录testDigits中的数据测试分类器的效果。两组数据没有覆盖,你可以检査一下这些文件夹的文件是否符合要求。

为了使用前面两个例子的分类器,我们必须将图像格式化处理为一个向量。我们将把一个32 x 32的二进制图像矩阵转换为1 x 1024的向量’这样前两节使用的分类器就可以处理数字图像信息了。

我们首先编写一段函数img2vector,将图像转换为向量:该函数创建1x1024Numpy数 组,然后打开给定的文件,循环读出文件的前32行,并将每行的头32个字符值存储在NumPy数组 中,最后返回数组。

img2vector代码如下:

# -*- coding:utf-8 -*-


def img2vector(filename):
    import numpy as np

    with open(filename) as f:
        imgList0 = f.readlines()

    imgList1 = []
    for i in imgList0:
        imgList1 = imgList1 + list([int(j) for j in i.strip()])

    returnVect0 = np.array(imgList1)
    return returnVect0.reshape((1, 1024))

测试如下:

In [5]: from knn.img2vector import img2vector

In [6]: testVector = img2vector('data/digits/testDigits/0_13.txt')

In [7]: testVector[0, 0:31]
Out[7]:
array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
       0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 
       0, 0, 0, 0, 0])

In [8]: testVector[0, 32:63]
Out[8]:
array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 
       1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 
       0, 0, 0, 0, 0])

测试算法:使用k-近邻算法识别手写数字

在写人这些代码之前,我们必须确保将from os import listdir写人文件的起始部分,这段代码的主要功能是从os模块中导人函数listdir,它可以列出给定目录的文件名。

手写数字识别系统的测试代码:

# -*- coding:utf-8 -*-


from os import listdir
from knn.classify0 import classify0
from knn.img2vector import img2vector
import numpy as np


def handwritingClassTest():
    # 样本数据的类标签列表
    hwLabels = []

    # 样本数据文件列表
    trainingFileList = listdir('data/digits/trainingDigits')
    m = len(trainingFileList)

    # 初始化样本数据矩阵(M*1024)
    trainingMat = np.zeros((m, 1024))

    # 依次读取所有样本数据到数据矩阵
    for i in range(m):
        # 提取文件名中的数字
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split('.')[0]
        classNumStr = int(fileStr.split('_')[0])
        hwLabels.append(classNumStr)

        # 将样本数据存入矩阵
        trainingMat[i, :] = img2vector('data/digits/trainingDigits/%s' % fileNameStr)

    # 循环读取测试数据
    testFileList = listdir('data/digits/testDigits')

    # 初始化错误率
    errorCount = 0.0
    mTest = len(testFileList)

    # 循环测试每个测试数据文件
    for i in range(mTest):
        # 提取文件名中的数字
        fileNameStr = testFileList[i]
        fileStr = fileNameStr.split('.')[0]
        classNumStr = int(fileStr.split('_')[0])

        # 提取数据向量
        vectorUnderTest = img2vector('data/digits/testDigits/%s' % fileNameStr)

        # 对数据文件进行分类
        classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)

        # 打印KNN算法分类结果和真实的分类
        print("the classifier came back with: %d, the real answer is: %d" % (classifierResult, classNumStr))

        # 判断KNN算法结果是否准确
        if (classifierResult != classNumStr):
            errorCount += 1.0

    # 打印错误率
    print("\nthe total number of errors is: %d" % errorCount)
    print("\nthe total error rate is: %f" % (errorCount / float(mTest)))


if __name__ == '__main__':
    handwritingClassTest()

测试效果:

k-近邻算法识别手写数字数据集,错误率为0.01168改变变量k的值、修改函数handwritingClassTest随机选取训练样本、 改变训练样本的数目 ,都会对k-近邻算法的错误率产生影响 ,感兴趣的话可以改变这些变量值,观察错误率的变化。

实际使用这个算法时,算法的执行效率并不高。因为算法需要为每个测试向量做2000次距离 计算,每个距离计算包括了 1024个维度浮点运算,总计要执行900次,此外,我们还需要为测试 向量准备2MB的存储空间。是否存在一种算法减少存储空间和计算时间的开销呢?k决策树就是 是-近邻算法的优化版,可以节省大量的计算开销。


本文由【waitig】发表在等英博客
本文固定链接:k近邻算法-手写识别系统
欢迎关注本站官方公众号,每日都有干货分享!
等英博客官方公众号
点赞 (0)分享 (0)