kNN算法实例之手写识别系统

1、实战背景

对于需要识别的数字已经使用图形处理软件，处理成具有相同的色彩和大小：宽高是32像素x32像素。尽管采用本文格式存储图像不能有效地利用内存空间，但是为了方便理解，我们将图片转换为文本格式

机器学习实战教程（一）：K-近邻算法（史诗级干货长文）

与此同时，这些文本格式存储的数字的文件命名也很有特点，格式为：数字的值_该数字的样本序号

机器学习实战教程（一）：K-近邻算法（史诗级干货长文）

通过手写knn的代码写在下面

from numpy import *
from matplotlib.font_manager import FontProperties
import matplotlib.lines as mlines
import  matplotlib.pyplot as plt
import operator
import os
''''
函数说明：knn算法，分类器，inx是输入的向量，dataset是数据集，labels是标签
'''''
def classify0(inX, dataSet, labels, k):
    #获取dataSet的行数    shape[0]是行数 shape[1]是列数
    dataSetSize = dataSet.shape[0]
    diffMat = tile(inX, (dataSetSize,1))-dataSet
    #diffMat的每一个元素都平方
    sqDiffMat = diffMat**2
    #所有列加起来
    sqDistance = sqDiffMat.sum(axis=1)
    distances = sqDistance**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]
'''
函数说明：将文本中的32*32矩阵转化为1*1024向量存储
'''
def img2vector(filename):
    returnVect =zeros((1,1024))
    fr = open(filename)
    for i in range(32):
        #readline是读取某一行的数据返回一个字符串对象
        #readlines 是读取文件的所有行，每一行作为一个元素，保存在一个list中
        lineStr = fr.readline()
        for j in range(32) :
            #把第0行第32*i+j个元素赋值
            returnVect[0,32*i+j] = lineStr[j]
    return returnVect
def handwritingClassTest(k):
    hwLabels = []
    trainingFileList = os.listdir("trainingDigits")
    m = len(trainingFileList)
    trainingMat = zeros((m,1024))
    for i in range(m):
        fileNameStr = trainingFileList[i]
        #首先把fileNameStr按照.分割，然后把列表的第一个元素赋值给fileStr
        fileStr = fileNameStr.split(".")[0]
        #首先把filestr按照——分割，然后把列表的第一个元素转化为int类型之后赋值给classNumStr，即该文件表示的数字值
        classNumStr = int(fileStr.split("_")[0])
        hwLabels.append(classNumStr)
        # trainingMat[i,:]指的是这个矩阵第i行的所有元素
        trainingMat[i,:] = img2vector("trainingDigits/%s" % fileNameStr)
    testFileList = os.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, k)
        print("预测的结果是%d,正确的结果是%d" %(classifierResult, classNumStr))
        if(classifierResult != classNumStr):
            errorCount += 1.0
    print("\n错误率是%f" % (errorCount/float(mTest)))

上述代码还是用到了我们自己写的classfi0函数，不过，knn算法已经实现好了，我们直接用就可以了，首先要导入sklearn库，下面是sklearn的实现函数的说明。

KNneighborsClassifier参数说明：

n_neighbors：默认为5，就是k-NN的k的值，选取最近的k个点。
weights：默认是uniform，参数可以是uniform、distance，也可以是用户自己定义的函数。uniform是均等的权重，就说所有的邻近点的权重都是相等的。distance是不均等的权重，距离近的点比距离远的点的影响大。用户自定义的函数，接收距离的数组，返回一组维数相同的权重。
algorithm：快速k近邻搜索算法，默认参数为auto，可以理解为算法自己决定合适的搜索算法。除此之外，用户也可以自己指定搜索算法ball_tree、kd_tree、brute方法进行搜索，brute是蛮力搜索，也就是线性扫描，当训练集很大时，计算非常耗时。kd_tree，构造kd树存储数据以便对其进行快速检索的树形数据结构，kd树也就是数据结构中的二叉树。以中值切分构造的树，每个结点是一个超矩形，在维数小于20时效率高。ball tree是为了克服kd树高纬失效而发明的，其构造过程是以质心C和半径r分割样本空间，每个节点是一个超球体。
leaf_size：默认是30，这个是构造的kd树和ball树的大小。这个值的设置会影响树构建的速度和搜索速度，同样也影响着存储树所需的内存大小。需要根据问题的性质选择最优的大小。
metric：用于距离度量，默认度量是minkowski，也就是p=2的欧氏距离(欧几里德度量)。
p：距离度量公式。在上小结，我们使用欧氏距离公式进行距离度量。除此之外，还有其他的度量方法，例如曼哈顿距离。这个参数默认为2，也就是默认使用欧式距离公式进行距离度量。也可以设置为1，使用曼哈顿距离公式进行距离度量。
metric_params：距离公式的其他关键参数，这个可以不管，使用默认的None即可。
n_jobs：并行处理设置。默认为1，临近点搜索并行工作数。如果为-1，那么CPU的所有cores都用于并行工作。

代码

from sklearn.neighbors import KNeighborsClassifier as kNN
from numpy import *
import os
def img2vector(filename):
    returnVect =zeros((1,1024))
    fr = open(filename)
    for i in range(32):
        #readline是读取某一行的数据返回一个字符串对象
        #readlines 是读取文件的所有行，每一行作为一个元素，保存在一个list中
        lineStr = fr.readline()
        for j in range(32) :
            #把第0行第32*i+j个元素赋值
            returnVect[0,32*i+j] = lineStr[j]
    return returnVect


def handwritingClassTest():
    # 测试集的Labels
    hwLabels = []
    # 返回trainingDigits目录下的文件名
    trainingFileList = os.listdir('trainingDigits')
    # 返回文件夹下文件的个数
    m = len(trainingFileList)
    # 初始化训练的Mat矩阵,测试集
    trainingMat = zeros((m, 1024))
    # 从文件名中解析出训练集的类别
    for i in range(m):
        # 获得文件的名字
        fileNameStr = trainingFileList[i]
        # 获得分类的数字
        classNumber = int(fileNameStr.split('_')[0])
        # 将获得的类别添加到hwLabels中
        hwLabels.append(classNumber)
        # 将每一个文件的1x1024数据存储到trainingMat矩阵中
        trainingMat[i, :] = img2vector('trainingDigits/%s' % (fileNameStr))
    # 构建kNN分类器
    neigh = kNN(n_neighbors=3, algorithm='auto')
    # 拟合模型, trainingMat为训练矩阵,hwLabels为对应的标签
    neigh.fit(trainingMat, hwLabels)
    # 返回testDigits目录下的文件列表
    testFileList = os.listdir('testDigits')
    # 错误检测计数
    errorCount = 0.0
    # 测试数据的数量
    mTest = len(testFileList)
    # 从文件中解析出测试集的类别并进行分类测试
    for i in range(mTest):
        # 获得文件的名字
        fileNameStr = testFileList[i]
        # 获得分类的数字
        classNumber = int(fileNameStr.split('_')[0])
        # 获得测试集的1x1024向量,用于训练
        vectorUnderTest = img2vector('testDigits/%s' % (fileNameStr))
        # 获得预测结果
        # classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
        classifierResult = neigh.predict(vectorUnderTest)
        print("分类返回结果为%d\t真实结果为%d" % (classifierResult, classNumber))
        if (classifierResult != classNumber):
            errorCount += 1.0
    print("总共错了%d个数据\n错误率为%f%%" % (errorCount, errorCount / mTest * 100))
if __name__ == '__main__':
    handwritingClassTest()

结果