摘要：項(xiàng)目介紹基于近鄰分類器的手寫識(shí)別系統(tǒng)這里構(gòu)造的系統(tǒng)只能識(shí)別數(shù)字到。將圖像格式化處理為一個(gè)向量。

基于k-近鄰分類器(KNN)的手寫識(shí)別系統(tǒng), 這里構(gòu)造的系統(tǒng)只能識(shí)別數(shù)字0到9。

數(shù)據(jù)集和項(xiàng)目源代碼

難點(diǎn)： 圖形信息如何處理?

圖像轉(zhuǎn)換為文本格式

將圖像轉(zhuǎn)換為測試向量

訓(xùn)練集：

目錄trainingDigits

大約2000個(gè)例子

每個(gè)數(shù)字大約有200個(gè)樣本;

測試集

目錄testDigits

大約900個(gè)測試數(shù)據(jù)。

將圖像格式化處理為一個(gè)向量。我們將把一個(gè)32×32的二進(jìn)制圖像矩陣轉(zhuǎn)換為1×1024的向量, 如下圖所示，

import numpy as np
def img2vector(filename):
    """
    # 將圖像數(shù)據(jù)轉(zhuǎn)換為（1，1024）向量
    :param filename: 
    :return: （1，1024）向量
    """
    # 生成一個(gè)1*1024且值全為0的向量;
    returnVect = np.zeros((1, 1024))
    # 讀取要轉(zhuǎn)換的信息;
    file = open(filename)
    # 依次填充
    # 讀取每一行數(shù)據(jù);
    for i in range(32):
        lineStr = file.readline()
        # 讀取每一列數(shù)據(jù);
        for j in range(32):
            returnVect[0, 32 * i + j] = int(lineStr[j])
    return returnVect

對(duì)未知類別屬性的數(shù)據(jù)集中的每個(gè)點(diǎn)依次執(zhí)行以下操作， 與上一個(gè)案例代碼相同:
(1) 計(jì)算已知類別數(shù)據(jù)集中的點(diǎn)與當(dāng)前點(diǎn)之間的距離;
(2) 按照距離遞增次序排序;
(3) 選取與當(dāng)前點(diǎn)距離最小的k個(gè)點(diǎn);
(4) 確定前k個(gè)點(diǎn)所在類別的出現(xiàn)頻率;
(5) 返回前k個(gè)點(diǎn)出現(xiàn)頻率最高的類別作為當(dāng)前點(diǎn)的預(yù)測分類。

def classify(inX, dataSet, labels, k):
    """
    :param inX: 要預(yù)測的數(shù)據(jù)
    :param dataSet: 我們要傳入的已知數(shù)據(jù)集
    :param labels:  我們要傳入的標(biāo)簽
    :param k: KNN里的k， 也就是說我們要選幾個(gè)近鄰
    :return: 排序的結(jié)果
    """
    dataSetSize = dataSet.shape[0]  # (6,2) 6
    # tile會(huì)重復(fù)inX, 把他重復(fù)成（datasetsize, 1）型的矩陣
    # print(inX)
    # (x1 - y1), (x2- y2)
    diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet
    # 平方
    sqDiffMat = diffMat ** 2
    # 相加, axis=1 行相加
    sqDistance = sqDiffMat.sum(axis=1)
    # 開根號(hào)
    distances = sqDistance ** 0.5
    # print(distances)
    # 排序 輸出的是序列號(hào)index，并不是值
    sortedDistIndicies = distances.argsort()
    # print(sortedDistIndicies)

    classCount = {}
    for i in range(k):
        voteLabel = labels[sortedDistIndicies[i]]
        classCount[voteLabel] = classCount.get(voteLabel, 0) + 1
        # print(classCount)
    sortedClassCount = sorted(classCount.items(), key=lambda d: float(d[1]), reverse=True)
    return sortedClassCount[0]

使用 k-近鄰算法識(shí)別手寫數(shù)字

測試集里面的信息;

def handWritingClassTest(k):
    """
    # 測試手寫數(shù)字識(shí)別錯(cuò)誤率的代碼
    :param k:
    :return:
    """
    hwLabels = []
    import os
    # 讀取所有的訓(xùn)練集文件；
    trainingFileList = os.listdir("data/knn-digits/trainingDigits")
    # 獲取訓(xùn)練集個(gè)數(shù);
    m = len(trainingFileList)
    # 生成m行1024列全為0的矩陣；
    trainingMat = np.zeros((m, 1024))
    # 填充訓(xùn)練集矩陣;
    for i in range(m):
        fileNameStr = trainingFileList[i]    # fileNameStr: 0_0.txt
        fileStr = fileNameStr.split(".")[0]  # fileStr: 0_0
        classNumStr = int(fileStr.split("_")[0])    # (數(shù)字分類的結(jié)果)classNumStr: 0
        # 填寫真實(shí)的數(shù)字結(jié)果;
        hwLabels.append(classNumStr)
        # 圖形的數(shù)據(jù)： （1，1024）向量
        trainingMat[i, :] = img2vector("data/knn-digits/trainingDigits/%s" % fileNameStr)

    # 填充測試集矩陣；
    testFileList = os.listdir("data/knn-digits/testDigits")
    # 默認(rèn)錯(cuò)誤率為0；
    errorCount = 0.0
    # 測試集的總數(shù);
    mTest = len(testFileList)
    # 填充測試集矩陣;
    for i in range(mTest):
        fileNameStr = testFileList[i]
        fileStr = fileNameStr.split(".")[0]
        classNumStr = int(fileStr.split("_")[0])
        vectorTest = img2vector("data/knn-digits/testDigits/%s" % fileNameStr)

        # 判斷預(yù)測結(jié)果與真實(shí)結(jié)果是否一致?
        result = classify(vectorTest, trainingMat, hwLabels, k)

        if result != classNumStr:
            # 如果不一致，則統(tǒng)計(jì)出來， 計(jì)算錯(cuò)誤率；
            errorCount += 1.0
            print("[預(yù)測失誤]：分類結(jié)果是：%d, 真實(shí)結(jié)果是：%d" % (result, classNumStr))
    print("錯(cuò)誤總數(shù)：%d" % errorCount)
    print("錯(cuò)誤率：%f" % (errorCount / mTest))
    print("模型準(zhǔn)確率:%f" %(1-errorCount / mTest))
    return errorCount


print(handWritingClassTest(2))

效果展示

算法的執(zhí)行效率并不高。

每個(gè)測試向量做2000次距離計(jì)算,每個(gè)距離計(jì)算包括了1024個(gè)維度浮點(diǎn)運(yùn)算,總計(jì)要執(zhí)行900次;

需要為測試向量準(zhǔn)備2MB的存儲(chǔ)空間

有沒有更好的方法？

k決策樹就是k-近鄰算法的優(yōu)化版,可以節(jié)省大量的計(jì)算開銷。