机器学习_KNN实验（手写数字的识别）

kNN实验

手写数字识别

实验内容

1. 使用K-NN算法识别数字0-9，实现最基本的KNN算法，使用trainingDigits文件夹下的数据，对testDigits中的数据进行预测。（K赋值为1，使用欧氏距离，多数投票决定分类结果）
2. 改变K的值，并观察对正确率的影响。
3. 更改距离度量方式，更改投票方式（距离加权），分析错误率。

实验要求

1.要求给出代码，以及运行窗口截图。

2.K对正确率的影响，最好用表格或作图说明，并做简要分析。

算法描述：

基本思想

以所有已知类别的样本作为参照，计算未知样本与所有已知样本的距离，从中选取与未知样本距离最近的K个已知样本，根据少数服从多数的投票法则（majority-voting），将未知样本与K个最邻近样本中所属类别占比较多的归为一类。

算法关键

(1) 样本的所有特征都要做可比较的量化 ： 若是样本特征中存在非数值的类型，必须采取手段将其量化为数值。例如样本特征中包含颜色，可通过将颜色转换为灰度值来实现距离计算。

(2) 样本特征要做归一化处理 ： 样本有多个参数，每一个参数都有自己的定义域和取值范围，他们对距离计算的影响不一样，如取值较大的影响力会盖过取值较小的参数。所以样本参数必须做一些 scale 处理，最简单的方式就是所有特征的数值都采取归一化处置。

(3) 需要一个距离函数以计算两个样本之间的距离 ：通常使用的距离函数有：欧氏距离、余弦距离、汉明距离、曼哈顿距离等，一般选欧氏距离作为距离度量，但是这是只适用于连续变量。

(4) 确定K的值： K值选的太大易引起欠拟合，太小容易过拟合，需交叉验证确定K值。

实验步骤：

数据集介绍

digits 目录下有两个文件夹，分别是:1、trainingDigits：训练数据，1934个文件，每个数字大约200个文件；2、testDigits：测试数据，946个文件，每个数字大约100个文件。每个文件中存储一个手写的数字，文件的命名类似0_7.txt，第一个数字0表示文件中的手写数字k是0，后面的7是个序号。

实现基本knn算法

首先将32x32的二进制图像矩阵转换为1x1024的向量

def img2vector(fname):
    reVect = np.zeros((1,1024))#将32x32的二进制图像矩阵转换为1x1024的向量
    fr = open(fname)
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
            reVect[0,32*i+j] = int(lineStr[j])
    return reVect

然后实现knn分类器

#实现knn分类器
def classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]
     #下面的四行代码计算距离,使用欧氏距离
    diffMat = np.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]

最后就可以检测一下knn的效果了

def handwritingTest(n):#n为设定的k值
    hwLabels = []
    tFL = listdir('trainingDigits')#加载训练集trainingFileList
    m = len(tFL)
    tM = np.zeros((m,1024))
    for i in range(m):
        #从文件名解析分类数字
        fileNameStr = tFL[i]
        fileStr = fileNameStr.split('.')[0] 
        classNumStr = int(fileStr.split('_')[0])
        hwLabels.append(classNumStr)
        tM[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, tM, hwLabels, n)
        print ("分类器得到结果为: %d, 实际情况为: %d\n" % (classifierResult, classNumStr))
        if (classifierResult != classNumStr): errorCount += 1.0
    print ("总错误个数为: %d" % errorCount)
    print ("\n总错误率为: %f" % (errorCount/float(mTest)))
    
if __name__ =="__main__":   
    start=time.process_time() 
    handwritingTest(3)
    end=time.process_time()
    print('Running time:',end-start)#显示运行时间

实验一结果

k=5时结果为：

观察k对正确率的影响

下图为k值对错误率的影响：（可以看到k=3时错误率最小，同理可得对正确率的影响图）

更改距离度量方式更改投票方式（距离加权）分析错误率

使用余弦距离测试 排序时降序

def classify0(inX, dataSet, labels, k):
    distances = np.array([0 for _ in range(1934)] , dtype=float)
    #计算距离,使用余弦距离（Cosine Distance）
    sqDiffMat = inX**2
    sqDistances = sqDiffMat.sum()
    sqDistances = sqDistances**0.5
    #放在循环外，因为每次都要算测试样本的长度
    reVect = dataSet
    for i in range(1934):
        diffMat = float(np.dot(inX,reVect[i].T))
        sqDiffMat1 = reVect[i]**2
        sqDistances1 = sqDiffMat1.sum()
        sqDistances1 = sqDistances1**0.5
        distances[i] = float(diffMat/sqDistances*sqDistances1)
    #对距离进行排序，由性质得cos越大相似度越大
    sortedDistIndicies = np.argsort(-distances)     
    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]

但是得出结果错误率较高，发现是没有归一化的问题，后面改进

归一化处理后代码 结果k=5时效果比欧式距离好

def classify0(inX, dataSet, labels, k):
    distances = np.array([0 for _ in range(1934)] , dtype=float)
    reVect = dataSet
    for i in range(1934):
        num = float(np.dot(inX,reVect[i].T)) 
        denom = linalg.norm(inX) * linalg.norm(reVect[i])
        cos = num / denom #余弦值
        distances[i] = 0.5 + 0.5 * cos #归一化
    #对距离进行排序
    sortedDistIndicies = np.argsort(-distances)     
    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]

更改投票方式（距离加权）

classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1/(1+math.log(i+1,2))
#只需要改这一行即可，将投票机制加权

得到结果如下：

将所有的数据进行对比：




可以看到，加权投票机制使得错误率得到一定的下降，余弦距离的相似度对k值较大时效果还不如欧氏距离。