实验环境

Python:3.7.0
Anconda:3-5.3.1 64位
操作系统:win10
开发工具:sublime text(非必要)

简介

本次实验中的重点为采用kNN算法进行手写数字识别，其中kNN算法是机器学习中入门的分类算法。其核心思想是将需要进行分类的目标放入已有充足样本的向量集中，求得与其距离最近的前k(自定超参数)个点，并返回这k个点中出现频率最高的类别，并将此类别作为模型的预测结果。

如上图所示，即是KNN算法的概念，当我们需要判断未知值（绿色正方形）是什么类别时，当K的取值为3时，会将其判断为蓝色。反之，当K值来到5时，则会出现下图所示情况。

简而言之，knn算法是一种简单的机器学习中的有监督分类算法，其优点在于模型简单，且训练过程快；但与之相对的，它对内存的要求高且预测阶段可能很慢。下面的公式展示的是它的距离计算公式，其实很容易看出这个就是简单的欧氏距离计算公式,在大家的中学阶段乃至小学阶段可能都接触过，在此不做赘述。

kNN算法

为了实现手写数字的分类，最重要的是取得分类算法(如果有不理解的可以看代码的注释，我每一句都有写对应的作用)

#kNN算法
def kNNclassify()

#下示kNN算法来自人民邮电出版社的《机器学习实战》，注释为笔者所作

#输入参数依次为分类向量，样本集，标签向量和最近邻居数量
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]]	#依次取得前k个点对应的分类
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1	#使用get函数取得上一步中得到分类的已有得分数，若无则取0，并将结果+1保存至classCount字典内
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)	#对结果进行排序
    return sortedClassCount[0][0]	#返回结果

简要来说，上述算法实现了将待分类的inx向量与样本集中每一个样本进行距离求值，并对所求的距离进行排序，选取前K小的点并依次读取其所属类别，将出现次数最多的类别作为分类结果进行输出。
其中每一步的具体含义都在上示代码中写有注释，所有出现的函数操作在下面都有大致介绍。

应用函数

以下所列的算法中采用函数为简介，实际应用可以自行查询
shape函数
numpy中的shape函数用于返回指定变量的某一维度的数量值（在例子中为返回dataset的第一维度值，即样本个数）

tile函数
numpy中的tile函数为平铺函数，在上述kNN算法中的用法是将inX在第一维度上复制datasesize倍，在第二维度上复制一倍（即不复制）

sum函数
numpy中的sum函数为指定维度求和函数，可以通过axis参数指定进行求和的维度，在本算法中将按照第二维度的值进行相加，即求距离的平方的和

argsort函数
numpy中的argsort函数为将上例中distances的元素从小到大排列，提取其对应的index(索引)，然后输出

get函数
字典自带函数get的操作为取得key对应的value，若无则取第二个参数（可不设置第二个参数）

sorted函数
python中自带的sorted函数有着复杂的用法，在本算法中的作用是从大到小输出不同分类的排序

items函数
字典自带函数items用于返回一个指定字典的迭代器

itemgetter函数
operator模块中的itemgetter()函数，是获取对象指定域中的值

样本集说明

本实验采用的样本集和测试集均为人民邮电出版社的《机器学习实战》所提供的源代码中的数据，其已将图片文件转换为文本文件；包含约2000个样本集和约900和测试集。其中具体图片如下（都取自样本集，左为数字3，右为数字7）

样本处理

此时可知，我们的样本是类似32✖32的文本数据，但为了分类器的处理，我们需要对其进行矩阵转换为1✖1024的向量以期可以使用前面完成的kNN算法进行分类。

#下示函数来自人民邮电出版社的《机器学习实战》，注释为笔者所作
def img2vector(filename):
    returnVect = zeros((1,1024))	#新建并初始化一个初值赋0的矩阵
    fr = open(filename)		#打开传入文件
    for i in range(32):
        lineStr = fr.readline()		#读取文本文件
        for j in range(32):
            returnVect[0,32*i+j] = int(lineStr[j])		#将32*32的矩阵依次赋值给1*1024的矩阵
    return returnVect 	#返回结果

上示函数中调用的值得说明的numpy函数只有zeros：新建并初始化一个初值赋0的矩阵。该函数可以完成32✖32的原文件转换并存储为1✖1024的numpy数组。下面进行一个小小的测试，将上图中左边的3进行转换。可以看到前两行的结果完全正确。

手写数字识别

接下来准备工作都已经做完，只要将数据喂入准备好的识别系统代码即可，详细代码如下

#下示函数来自人民邮电出版社的《机器学习实战》，注释为笔者所作
def handwritingClassTest():
    hwLabels = []	#设定用于存储的列表
    trainingFileList = listdir('trainingDigits')	#读取样本集 
    m = len(trainingFileList)	#读取样本集长度
    trainingMat = zeros((m,1024))	#新建并初始化一个初值赋0的矩阵
    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)	#将32*32转换为1*1024
    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)	#将32*32转换为1*1024
        classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)		#将转化后的结果丢入kNN分类器
        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)))	#输入错误率

上述的函数用于完成手写数字识别系统，简单来说，上述的函数所作的操作是先将样本集依次读入，并依其所属的数字分类，并将他们进行格式的转换。完成后对测试数据进行依次读入的操作，丢入kNN分类算法后得出预测值，并与真实值进行比较，并将不符合的错误结果进行记录，从而得出最终整个系统的错误率。下面附上完整代码截图和测试截图。

备注

如果同样是采用本书的源代码，需要注意由python版本带来的两点注意事项

• 源代码中的print采用的是python2的格式，本次实验采用python3，需要依照本博客提供的格式进行修改.
• 源代码中采用了iteritems函数，在python3.5中需要如本博客中一样修改为items

附加：约会网站配对效果改进实验

这里补充上本书同章节的另外一个实验；简单来说，这个实验实现了一个同样是以knn算法为驱动的分类问题，其中样本为每一个待约会对象，而每个对象的某一项特征被抽象为某一维度的数值，在这个基础上输入一个新的约会对象及其每个特征值，来得到本对象是否被喜欢。下面附上代码和过程。

先来看一下样本集，和上面的数字分类实验一样，任然采用文本的方式进行存储；可能作者是考虑到文本的格式对新手友好且方便可视化，所以采用这种形式；如图所示，第一行代表的是每年获得的飞行常客里程数，第二行是玩视频游戏消耗时间，第三行是每周消费的冰激凌公升数，第四行是代表这个对象的心动程度（dindntlike 不喜欢 smalldoses 小小心动 largedoses 大心动）。

#下示函数来自人民邮电出版社的《机器学习实战》
def file2matrix(filename):
    love_dictionary = {'largeDoses':3, 'smallDoses':2, 'didntLike':1}
    fr = open(filename)
    arrayOLines = fr.readlines()
    numberOfLines = len(arrayOLines)            #get the number of lines in the file
    returnMat = np.zeros((numberOfLines, 3))        #prepare matrix to return
    classLabelVector = []                       #prepare labels return
    index = 0
    for line in arrayOLines:
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index, :] = listFromLine[0:3]
        if(listFromLine[-1].isdigit()):
            classLabelVector.append(int(listFromLine[-1]))
        else:
            classLabelVector.append(love_dictionary.get(listFromLine[-1]))
        index += 1
    return returnMat, classLabelVector

上述代码完成了对样本集的读入，并且每一个样本的各项特征值以向量的方式存储到第一个返回值returnMat中，将每一个样本量对应的心动程度（即是对应分类）存储到第二个返回值classLabelVector中；其中用到的步骤和方式与前面的数字分类实验读入数字的原理是相同的，在此不做赘述。

#下示函数来自人民邮电出版社的《机器学习实战》
def autoNorm(dataSet):
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    ranges = maxVals - minVals
    normDataSet = np.zeros(np.shape(dataSet))
    m = dataSet.shape[0]
    normDataSet = dataSet - np.tile(minVals, (m, 1))
    normDataSet = normDataSet/np.tile(ranges, (m, 1))   #element wise divide
    return normDataSet, ranges, minVals

上述代码进行的是一种叫做归一化的操作，归一化处理是数据挖掘的一项基础工作，不同评价指标往往具有不同的量纲和量纲单位，这样的情况会影响到数据分析的结果，就如同上面展示的样本库中，若不做处理，由于使用KNN算法是直接的计算距离，那每年获取的飞行常客里程数由于量级过大，会对结果产生过大的影响以至于其他两者无足轻重，这是与目的相悖的,为了消除指标之间的量纲影响，需要进行数据标准化处理，以解决数据指标之间的可比性。原始数据经过数据标准化处理后，各指标处于同一数量级，适合进行综合对比评价,通常是将数据映射到（0，1）或（-1，1）之间。上图函数执行的就是这个过程，它的过程可以用以下的公式解释：映射变换后的值=（映射变换前的值-最小值）/（最大值-最小值），需要注意的是，这种归一化的操作的方式被称作min-max标准化（Min-Max Normalization），也即离差标准化，这种方法有个缺陷就是当有新数据加入时，可能导致max和min的变化，需要重新定义。

#下示函数来自人民邮电出版社的《机器学习实战》
def classifyPerson():
    resultList = ['not at all', 'in small doses', 'in large doses']
    percentTats = float(input(\
                                  "percentage of time spent playing video games?"))
    ffMiles = float(input("frequent flier miles earned per year?"))
    iceCream = float(input("liters of ice cream consumed per year?"))
    datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')
    normMat, ranges, minVals = autoNorm(datingDataMat)
    inArr = np.array([ffMiles, percentTats, iceCream, ])
    classifierResult = classify0((inArr - \
                                  minVals)/ranges, normMat, datingLabels, 3)
    print("You will probably like this person: %s" % resultList[classifierResult - 1])

上图所示的代码即为最终实验所需代码，在下图将展示实验所得成果，其中我们输入了一个在数值上与第二个样本非常接近的样本，可以看到得出的结果与样本结果相同。（注：上图的代码中调用的file2matrix函数和autoNorm函数前面都有给出；而classify0在前面的实验已经给出）