【机器学习实战】k近邻算法实战——手写识别系统

【机器学习实战】k近邻算法实战——手写识别系统

文章目录

手写识别系统步骤：准备数据：将图像转换为测试向量测试算法：使用k-近邻算法识别手写数字【完整代码】

手写识别系统

为了简单起见，这里构造的系统只能识别数字0到9，参见图2-6。需要识别的数字已经使用图形处理软件，处理成具有相同的色彩和大小[插图]：宽高是32像素×32像素的黑白图像。尽管采用文本格式存储图像不能有效地利用内存空间，但是为了方便理解，我们还是将图像转换为文本格式。

步骤：

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

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

实际图像存储在第2章源代码的两个子目录内：目录trainingDigits中包含了大约2000个例子，每个例子的内容如图2-6所示，每个数字大约有200个样本；目录testDigits中包含了大约900个测试数据。我们使用目录trainingDigits中的数据训练分类器，使用目录testDigits中的数据测试分类器的效果。两组数据没有重叠，你可以检查一下这些文件夹的文件是否符合要求。（【下载地址】
为了使用前面两个例子的分类器，我们必须将图像格式化处理为一个向量。我们将把一个32× 32的二进制图像矩阵转换为1×1024的向量，这样前两节使用的分类器就可以处理数字图像信息了。
我们首先编写一段函数img2vector，将图像转换为向量：该函数创建1×1024的NumPy数组，然后打开给定的文件，循环读出文件的前32行，并将每行的头32个字符值存储在NumPy数组中，最后返回数组。

def img2vector(filename):
    returnVect = zeros((1, 1024))
    fr = open(filename)
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
            returnVect[0, 32 * i + j] = int(lineStr[j])
    return returnVect

进行测试：

testVector = img2vector('digits/testDigits/0_13.txt')
print(testVector[0, 0:31])
print(testVector[0, 32:63])
================================
[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.]
[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-近邻算法识别手写数字

函数handwritingClassTest()是测试分类器的代码，将其写入kNN.py文件中。在写入这些代码之前，我们必须确保将from os import listdir写入文件的起始部分，这段代码的主要功能是从os模块中导入函数listdir，它可以列出给定目录的文件名。

# 测试分类器
def handwritingClassTest():
    hwLabels = []
    # 获取目录内容
    trainingFileList = listdir('digits/trainingDigits')
    m = len(trainingFileList)
    trainingMat = 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('digits/trainingDigits/%s' % fileNameStr)

    testFileList = listdir('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('digits/testDigits/%s' % fileNameStr)
        classfierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
        print("the classifier came back with %d, the real answer is %d" % (classfierResult, classNumStr))
        if (classfierResult != classNumStr): errorCount += 1.0
    print("n the total number of errors is : %d" % errorCount)
    print("n the total error rate is : %f" % (errorCount / float(mTest)))

将trainingDigits目录中的文件内容存储在列表中1，然后可以得到目录中有多少文件，并将其存储在变量m中。接着，代码创建一个m行1024列的训练矩阵，该矩阵的每行数据存储一个图像。我们可以从文件名中解析出分类数字2。该目录下的文件按照规则命名，如文件9_45.txt的分类是9，它是数字9的第45个实例。然后我们可以将类代码存储在hwLabels向量中，使用前面讨论的img2vector函数载入图像。在下一步中，我们对testDigits目录中的文件执行相似的 *** 作，不同之处是我们并不将这个目录下的文件载入矩阵中，而是使用classify0()函数测试该目录下的每个文件。由于文件中的值已经在0和1之间，本节并不需要使用2.2节的autonorm()函数。

测试：

handwritingClassTest()
=====================================
the classifier came back with 0, the real answer is 0
the classifier came back with 0, the real answer is 0
the classifier came back with 0, the real answer is 0
the classifier came back with 0, the real answer is 0
the classifier came back with 0, the real answer is 0
the classifier came back with 0, the real answer is 0
the classifier came back with 0, the real answer is 0
......
the classifier came back with 9, the real answer is 9
the classifier came back with 9, the real answer is 9
the classifier came back with 9, the real answer is 9
the classifier came back with 9, the real answer is 9
the classifier came back with 9, the real answer is 9
the classifier came back with 9, the real answer is 9
the classifier came back with 9, the real answer is 9
the classifier came back with 9, the real answer is 9
the classifier came back with 9, the real answer is 9
the classifier came back with 9, the real answer is 9

 the total number of errors is : 10

 the total error rate is : 0.010571

k-近邻算法识别手写数字数据集，错误率为1.1%。改变变量k的值、修改函数handwriting-ClassTest随机选取训练样本、改变训练样本的数目，都会对k-近邻算法的错误率产生影响，感兴趣的话可以改变这些变量值，观察错误率的变化。
实际使用这个算法时，算法的执行效率并不高。因为算法需要为每个测试向量做2000次距离计算，每个距离计算包括了1024个维度浮点运算，总计要执行900次，此外，我们还需要为测试向量准备2MB的存储空间。是否存在一种算法减少存储空间和计算时间的开销呢？k决策树就是k-近邻算法的优化版，可以节省大量的计算开销。

【完整代码】

from numpy import *
import operator

def classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]
    # 距离计算
    diffMat = tile(inX, (dataSetSize, 1)) - dataSet
    sqDiffMat = diffMat ** 2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances ** 0.5

    sortedDistIndicies = distances.argsort()
    classCount = {}

    # 选择距离最小的k个点
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1

    # 排序
    sortedClassCount = sorted(classCount.items(),
                              key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]


def autoNorm(dataSet):
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    ranges = maxVals - minVals
    normDataSet = zeros(shape(dataSet))
    m = dataSet.shape[0]
    normDataSet = dataSet - tile(minVals, (m, 1))
    # 特征值相除
    normDataSet = normDataSet / tile(ranges, (m, 1))
    return normDataSet, ranges, minVals


# 手写识别######################

# 将图像转换为向量
def img2vector(filename):
    returnVect = zeros((1, 1024))
    fr = open(filename)
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
            returnVect[0, 32 * i + j] = int(lineStr[j])
    return returnVect


#
# testVector = img2vector('digits/testDigits/0_13.txt')
# print(testVector[0, 0:31])
# print(testVector[0, 32:63])

from os import listdir


# 测试分类器
def handwritingClassTest():
    hwLabels = []
    # 获取目录内容
    trainingFileList = listdir('digits/trainingDigits')
    m = len(trainingFileList)
    trainingMat = 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('digits/trainingDigits/%s' % fileNameStr)

    testFileList = listdir('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('digits/testDigits/%s' % fileNameStr)
        classfierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
        print("the classifier came back with %d, the real answer is %d" % (classfierResult, classNumStr))
        if (classfierResult != classNumStr): errorCount += 1.0
    print("n the total number of errors is : %d" % errorCount)
    print("n the total error rate is : %f" % (errorCount / float(mTest)))

handwritingClassTest()