K-邻近分类算法——分类MNIST手写体数据算法(机器学习实战)

时间:2024-03-10 13:53:41

  k 近邻法(K-nearest neighbor, KNN)是一种基本分类于回归方法,其在1968年由Cover和Hart提出的。k 近邻算法采用测量不同特征值之间的距离方法进行分类。其输入为示例的特征向量,对应于特征空间的点;输出为实例的类别,可以取多类。

  k 近邻法假设给定一个训练数据集,其中的上实例类别已定,分类时,对新的实例,根据其K 个最近邻的训练实力的类别,通过多数表决等方式进行预测。k 近邻法实际上利用训练数据集对特征向量哦那关键进行划分,并作为其分类的“模型”。

  k 邻近法的基本三要素为: k 值的选择、距离度量以及分类决策规则。

实例:k-近邻算法的手写识别系统

1.收集数据:提供文本文件。

2.准备数据:编写函数classify0() ,将图像格式转换为分类器使用的list格式。

3.分析数据:在Python命令提示符中检查数据,确保它符合要求。

4.测试算法:编写函数使用提供的部分数据集作为测试样本,测试样本与非测试样本的区别在于测试样本是已经完成分类的数据,如果预测分类与实际类别不同,则标记为一个错误。

步骤:

1、该手写体数据集合修改自"手写数字数据集的光学识别"一文中的数据集合,该文登载于2010年10月3日的UCI机器学习资料库中 http://archive.ics.uci.edu/ml。

2、准备数据

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

def img2vector(filename):
    returnVect = zeros((1,1024)) #创建1*1024的数组
    fr = open(filename) #打开文件
    #循环读出文件的前32行,并将每行的头32个字符值存储在NumPy数组中
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
            returnVect[0, 32*i+j] = int(lineStr[j])
    return returnVect #返回数组

2.2 准备分类:k 邻近算法,此处距离度量采用欧式距离度量;classify0() 函数有4个输入参数:用于分类的输入向量是inX,输入的训练样本集为dataSet,标签向量为labels ,最后的参数k 表示用于选择最近邻居的数目,其中标签向量的元素数目和矩阵dataSet 的行数相同。

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.iteritems(), 

      #❸ 排序

      key=operator.itemgetter(1), reverse=True)

    return sortedClassCount[0][0]

距离度量:欧式距离、曼哈顿距离、切比雪夫距离;这三种分别为闵可夫斯基度量的2范、1范、∞。将上述classify0()中内容关于距离距离内容修改

3、使用k 邻近识别手写体数据

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

def handwritingClassTest():

    hwLabels = []

    trainingFileList = listdir(\'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(\'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)

        print "the classifier came back with: %d, the real answer is: %d"\% (classifierResult, classNumStr)

        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))

4、实验比较不同K值影响,距离度量等影响

1 不同K值以及距离度量的错误率

距离度量

K=3(error rate)

K=5(error rate)

8(error rate)

欧式距离

0.010571

0.017970

0.019027

曼哈顿距离

0.010571

0.017970

0.019027

切比雪夫

0.908034

0.908034

0.908034

整体算法以及部分实验结果如下所示:

from numpy import *
import operator
from os import listdir

def createDataSet():
    groups = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
    labels = [\'A\',\'A\',\'B\',\'B\']
    return groups,labels

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 = {}
    #选择距离最近的
    for i in range(k):
        votelabel = labels[sortedDistIndicies[i]]
        classCount[votelabel] = classCount.get(votelabel,0) + 1
    sortedClassCount = sorted(classCount.items(),key = operator.itemgetter(1),reverse=True)
    #排序
    return sortedClassCount[0][0]

#图像转向量
def img2vector(filename):
    returnVect = zeros((1,1024)) #创建1*1024的数组
    fr = open(filename) #打开文件
    #循环读出文件的前32行,并将每行的头32个字符值存储在NumPy数组中
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
            returnVect[0, 32*i+j] = int(lineStr[j])
    return returnVect #返回数组

def handwritingClassTest():
    hwLabels = []
    trainingFileList = listdir(\'digits/trainingDigits\')#获取目录内容;trainingDigits目录中的文件内容存储在列表中
    m = len(trainingFileList)#得到目录中有多少文件,并将其存储在变量m 中。
    trainingMat = zeros((m, 1024))
    for i in range(m):
        #从文件名解析分类数:接着,代码创建一个m 行1024列的训练矩阵,该矩阵的每行数据存储一个图像。
        # 我们可以从文件名中解析出分类数字
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split(\'.\')[0]
        classNumStr = int(fileStr.split(\'_\')[0])
        hwLabels.append(classNumStr)#类代码存储在hwLabels 向量中
        trainingMat[i,:] = img2vector(\'digits/trainingDigits/%s\' % fileNameStr)
    testFileList = listdir(\'digits/testDigits\')#获取目录内容;testDigits目录中的文件内容存储在列表中
    errorCount = 0.0
    mTest = len(testFileList)#得到目录中有多少文件,并将其存储在变量mTest 中。
    #testDigits目录中的文件执行相似的操作,
    # 不同之处是我们并不将这个目录下的文件载入矩阵中,
    # 而是使用classify0() 函数测试该目录下的每个文件
    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)
        print(\'the classifier came back with: %d, the real answer is: %d\' % (classifierResult, classNumStr))
        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)))

test = handwritingClassTest()

算法结果如下:

 参考文献:

[1]peter harrington,机器学习实战[M].

[2]李航,统计学习方法(第二版)[M].