K 近邻算法实现手写数字识别系统

「爱情、让人受尽委屈。」 2022-02-01 11:27 178阅读 0赞

# 码云代码下载地址 #

https://gitee.com/minesean/ML_Number

# K 近邻算法概述 #

简单地说，K 近邻算法采用测量不同特征值之间的距离方法进行分类。

K 近邻算法适用数据范围为：数值型和标称型。

它具有的优缺点如下：

*  优点：精度高、对异常值不敏感、无数据输入假定。
 *  缺点：计算复杂度高、空间复杂度高。

**每个数据都有标签**，并且知道 每一个**数据**与所在**分类**的**对应关系**。

输入 **没有标签的新数据**，将**新数据的特征**与**样本数据的特征**进行比较，找出**最相近**数据的标签。

我们选择**最临近**数据的时候，找出**前K个**最相似(临近)数据。

k一般不大于20，**找出 出现最多的标签作为新数据的标签分类**。

**K 近邻算法的一般流程**

1.  收集数据：可以使用任何方法。
2.  准备数据：距离计算所需要的数值，最好是结构化的数据格式。
3.  分析数据：可以使用任何方法。
4.  训练算法：此步骤不适用于 K 近邻算法。
5.  测试算法：计算错误率。
6.  使用算法：首先需要输入样本数据和结构化的输出结果，然后运行K 近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理。

# 下载并解压数据。
    wget -nc "http://labfile.oss.aliyuncs.com/courses/777/digits.zip"
    # 解压缩
    unzip -o digits.zip

`digits` 目录下有两个文件夹，分别是:

*  `trainingDigits`：训练数据，1934 个文件，每个数字大约 200 个文件。
 *  `testDigits`：测试数据，946 个文件，每个数字大约 100 个文件。

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

import numpy as np
    
    def img2vector(filename):
        # 创建向量
        returnVect = np.zeros((1, 1024))
        # 打开数据文件，读取每行内容
        fr = open(filename)
        for i in range(32): # 所有数据集都是32x32的图片（32x32=1024）
            # 读取每一行
            lineStr = fr.readline()
            # 将每行前 32 字符转成 int 存入向量
            for j in range(32):
                returnVect[0, 32*i+j] = int(lineStr[j])
    
        return returnVect
    
    if __name__ == "__main__":
        a = img2vector('./testDigits/0_1.txt')
        print(a)

## 分析数据 ##

计算「距离」

import operator
    
    def classify0(inX, dataSet, labels, k):
    """ 参数: - inX: 用于分类的输入向量 - dataSet: 输入的训练样本集 - labels: 样本数据的类标签向量 - k: 用于选择最近邻居的数目 """
    
        # 获取样本数据数量
        dataSetSize = dataSet.shape[0]
    
        # 矩阵运算，计算测试数据与每个样本数据对应数据项的差值
        # 输入样本 减去 训练样本集
        diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet # @1注释
    
        # sqDistances 上一步骤结果平方和
        sqDiffMat = diffMat**2 #矩阵平方，每个元素都会**2
        sqDistances = sqDiffMat.sum(axis=1) # axis=1表示按行相加,axis=0表示按列相加
    
        # 取平方根，得到距离向量
        distances = sqDistances**0.5 #开根号
    
        # 按照距离从低到高排序
        sortedDistIndicies = distances.argsort() #排序
        
    	classCount = { }
        # 依次取出最近的样本数据
        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]

## 实现 ##

from os import listdir
    
    
    def handwritingClassTest():
        # 样本数据的类标签列表
        hwLabels = []
    
        # 样本数据文件列表
        trainingFileList = listdir('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(
                '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)
    
            # 对数据文件进行分类
            classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
    
            # 打印 K 近邻算法分类结果和真实的分类
            print("测试样本 %d, 分类器预测: %d, 真实类别: %d" %
                  (i+1, classifierResult, classNumStr))
    
            # 判断K 近邻算法结果是否准确
            if (classifierResult != classNumStr):
                errorCount += 1.0
    
        # 打印错误率
        print("\n错误分类计数: %d" % errorCount)
        print("\n错误分类比例: %f" % (errorCount/float(mTest)))

# 注释信息 #

**@1** [https://www.jianshu.com/p/9519f1984c70][https_www.jianshu.com_p_9519f1984c70]

Numpy的 tile() 函数，就是将原矩阵横向、纵向地复制。

tile 是瓷砖的意思，就是贴瓷砖一片一片排在一起

mat = array([[1,2], [3, 4]])
    [[1, 2],
     [3, 4]]
    # 横向 一行四列
    tile(mat, (1, 4)) 
    # 等同于 
    tile(mat, 4)
    # 结果
    [[1 2 1 2 1 2 1 2]
     [3 4 3 4 3 4 3 4]]
    
    #纵向，三行一列
    tile(mat, (3, 1))
    # 结果
    [[1 2]
     [3 4]
     [1 2]
     [3 4]
     [1 2]
     [3 4]]
    
    # 横向+纵向
    tile(mat, (3, 4))
    # 结果
    [[1 2 1 2 1 2 1 2]
     [3 4 3 4 3 4 3 4]
     [1 2 1 2 1 2 1 2]
     [3 4 3 4 3 4 3 4]
     [1 2 1 2 1 2 1 2]
     [3 4 3 4 3 4 3 4]]

# 完整代码 #

import numpy as np
    import operator
    from os import listdir
    
    def img2vector(filename):
        # 创建向量
        returnVect = np.zeros((1, 1024))
        # 打开数据文件，读取每行内容
        fr = open(filename)
        for i in range(32):
            # 读取每一行
            lineStr = fr.readline()
            # 将每行前 32 字符转成 int 存入向量
            for j in range(32):
                returnVect[0, 32*i+j] = int(lineStr[j])
    
        return returnVect
    
    
    
    
    
    def classify0(inX, dataSet, labels, k):
        """ 参数: - inX: 用于分类的输入向量 - dataSet: 输入的训练样本集 - labels: 样本数据的类标签向量 - k: 用于选择最近邻居的数目 """
    
        # 获取样本数据数量
        dataSetSize = dataSet.shape[0]
    
        # 矩阵运算，计算测试数据与每个样本数据对应数据项的差值
        # 输入样本 减去 训练样本集
        diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet  # @1注释
    
        # sqDistances 上一步骤结果平方和
        sqDiffMat = diffMat ** 2  # 矩阵平方，每个元素都会**2
        sqDistances = sqDiffMat.sum(axis=1)  # axis=1表示按行相加,axis=0表示按列相加
    
        # 取平方根，得到距离向量
        distances = sqDistances ** 0.5  # 开根号
    
        # 按照距离从低到高排序
        sortedDistIndicies = distances.argsort()  # 排序
    
        classCount = { }
        # 依次取出最近的样本数据
        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 handwritingClassTest():
        # 样本数据的类标签列表
        hwLabels = []
    
        # 样本数据文件列表
        trainingFileList = listdir('./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(
                './trainingDigits/%s' % fileNameStr)
    
        # 循环读取测试数据
        testFileList = listdir('./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('./testDigits/%s' % fileNameStr)
    
            # 对数据文件进行分类
            classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
    
            # 打印 K 近邻算法分类结果和真实的分类
            print("测试样本 %d, 分类器预测: %d, 真实类别: %d" %
                  (i+1, classifierResult, classNumStr))
    
            # 判断K 近邻算法结果是否准确
            if (classifierResult != classNumStr):
                errorCount += 1.0
    
        # 打印错误率
        print("\n错误分类计数: %d" % errorCount)
        print("\n错误分类比例: %f" % (errorCount/float(mTest)))
    
    if __name__ == '__main__':
        handwritingClassTest()

[https_www.jianshu.com_p_9519f1984c70]: https://www.jianshu.com/p/9519f1984c70