基于改進(jìn)KNN算法的手寫數(shù)字識(shí)別研究

胡君萍，傅科學(xué)

(武漢理工大學(xué) 信息工程學(xué)院，湖北 武漢 430070)

目前，仍有大量的手寫數(shù)字單據(jù)需要錄入計(jì)算機(jī)進(jìn)行管理，比如物流行業(yè)中手寫快遞單據(jù)、銀行業(yè)的手寫支票和匯款單、公司賬本等，如果能進(jìn)行智能化的手寫數(shù)字識(shí)別，則可以節(jié)省大量的人力。手寫數(shù)字識(shí)別方法從原理上大致可以分為基于統(tǒng)計(jì)特征分類、基于結(jié)構(gòu)特征分類、基于神經(jīng)網(wǎng)絡(luò)三大類算法[1-4]。K最近鄰(k-nearest neighbors，KNN)算法是基于統(tǒng)計(jì)特征進(jìn)行分類的人工智能算法，簡(jiǎn)單易懂，對(duì)系統(tǒng)要求低，因此筆者選取該算法對(duì)手寫數(shù)字進(jìn)行識(shí)別研究。Python是一種解釋型、面向?qū)ο?、?dòng)態(tài)的高級(jí)腳本語言[5]，其通過編譯器運(yùn)行，可以實(shí)現(xiàn)快速的機(jī)器學(xué)習(xí)和人工智能算法的實(shí)現(xiàn)，筆者用Python作為編程語言。

1 KNN算法原理

KNN算法是通過選擇分類集合中與待分類樣本最相似的K個(gè)樣本值，通過決策得出待分類樣本的類別。KNN算法屬于分類與邏輯回歸算法[6]，KNN只存在前向傳播過程，不存在學(xué)習(xí)的過程，是機(jī)器學(xué)習(xí)中簡(jiǎn)單有效的分類算法。將分類集合替換為手寫數(shù)字集合，即可用于手寫數(shù)字識(shí)別。

KNN算法實(shí)現(xiàn)的整個(gè)過程中有四大核心點(diǎn)：①分類集合的選擇；②K值的選擇；③向量距離度量規(guī)則；④決策方案。其中，訓(xùn)練數(shù)據(jù)集的選擇和K值的選擇需要綜合考量，過大會(huì)降低整個(gè)算法實(shí)現(xiàn)的效率，過小會(huì)影響識(shí)別的精度；向量距離度量規(guī)則用來確定待分類樣本與分類集合中樣本的相似度；而決策方案用來確定待分類樣本屬于哪個(gè)類別，優(yōu)秀的決策方案可以極大地提高分類的準(zhǔn)確率。根據(jù)KNN算法原理，用KNN實(shí)現(xiàn)樣本分類與識(shí)別的程序流程圖如圖1所示。

圖1 KNN算法流程圖

2 傳統(tǒng)KNN算法在手寫數(shù)字識(shí)別中的實(shí)現(xiàn)

2.1 手寫數(shù)據(jù)集的選擇

手寫數(shù)字識(shí)別算法的研究需要有好的手寫數(shù)字集(即分類集合)進(jìn)行訓(xùn)練和測(cè)試，目前主要有3種數(shù)據(jù)集：USPS、UCI和MNIST。

USPS即美國(guó)郵政服務(wù)手寫數(shù)字識(shí)別庫，該手寫數(shù)字樣本庫中共有9 298個(gè)樣本，其中7 291個(gè)樣本組成訓(xùn)練集，2 007個(gè)樣本組成測(cè)試集，所有樣本采集于郵政記錄員的筆跡。

UCI是用于筆交互的手寫數(shù)字識(shí)別庫，該數(shù)據(jù)集采集于44位不同行業(yè)人員的手寫筆跡，共計(jì)250個(gè)，訓(xùn)練集和測(cè)試集自行分配。

MNIST手寫數(shù)據(jù)集是由Google實(shí)驗(yàn)室、紐約大學(xué)柯朗研究所及微軟研究院整理了不同年齡段人的手寫數(shù)字構(gòu)成的集合[7]，包含60 000個(gè)訓(xùn)練集和10 000個(gè)測(cè)試集。MNIST數(shù)據(jù)集中部分手寫數(shù)字圖片如圖2所示。

圖2 訓(xùn)練集前28張手寫數(shù)字圖

手寫數(shù)字識(shí)別研究需要具有泛化性能和更高的準(zhǔn)確率，因此選擇數(shù)據(jù)人員類型多樣化和數(shù)據(jù)量大的MNIST數(shù)據(jù)集作為本研究進(jìn)行測(cè)試和訓(xùn)練的數(shù)據(jù)集。

2.2 圖像預(yù)處理

采用KNN實(shí)現(xiàn)手寫數(shù)字識(shí)別，首先需要將MNIST數(shù)據(jù)集標(biāo)準(zhǔn)化為KNN需要的格式，因此需要對(duì)MNIST數(shù)據(jù)集進(jìn)行預(yù)處理，即讀取MNIST數(shù)據(jù)集，并將其轉(zhuǎn)化為1×784的向量，MNIST數(shù)據(jù)集中圖像訓(xùn)練數(shù)據(jù)為60 000條，圖像測(cè)試數(shù)據(jù)為10 000條，因此訓(xùn)練數(shù)據(jù)可形成60 000×784的矩陣，測(cè)試數(shù)據(jù)可形成10 000×784的矩陣。

為了更好地提取數(shù)字的結(jié)構(gòu)特征和統(tǒng)計(jì)特征，一般還需要對(duì)圖片數(shù)據(jù)進(jìn)行歸一化和二值化處理。假設(shè)r(x,y)是位于圖像中坐標(biāo)(x,y)處的原始灰度值，c(x,y)是位于圖像中坐標(biāo)(x,y)處的歸一化灰度值，b(x,y)是位于圖像中坐標(biāo)(x,y)處的二值化值，maxg代表圖像中的最大灰度值，ming代表最小灰度值，其表達(dá)式分別如式(1)和式(2)所示。歸一化公式和二值化公式分別如式(3)和式(4)所示。

(1)

(2)

(3)

(4)

MNIST數(shù)據(jù)集的標(biāo)簽采用長(zhǎng)度為10的向量表示0～9,共10個(gè)種類。該向量由9個(gè)0.1和1個(gè)0.9組成，其中0.9在向量中的編號(hào)代表此標(biāo)簽的值，用一個(gè)長(zhǎng)度為10的向量作為一個(gè)輸出標(biāo)簽。

2.3 傳統(tǒng)KNN算法的實(shí)現(xiàn)

(1)選擇向量距離度量規(guī)則。在上述圖像預(yù)處理中，手寫數(shù)字已經(jīng)轉(zhuǎn)化為向量，筆者使用歐氏距離作為距離度量規(guī)則[8]，歐氏距離越小，則說明相似度越大。

在二維空間中，假設(shè)A點(diǎn)的坐標(biāo)為(x1,y1)，B點(diǎn)的坐標(biāo)為(x2,y2)，則AB兩點(diǎn)歐式距離dAB的計(jì)算公式為：

(5)

在N維空間中，假設(shè)向量A為(x11,x12,…,x1n)，向量B為(x21,x22,…,x2n)，則向量AB的歐式距離dAB的計(jì)算公式為：

(6)

(2)訓(xùn)練數(shù)據(jù)集的選擇。MNIST數(shù)據(jù)集有60 000條訓(xùn)練數(shù)據(jù)，如果全部進(jìn)行歐式距離的計(jì)算，會(huì)占用極大的計(jì)算機(jī)資源，同時(shí)時(shí)間和復(fù)雜度劇增，效率較低，因此選擇其中的10 000條作為訓(xùn)練的樣本實(shí)例進(jìn)行歐式距離的計(jì)算。

(3)K值的選擇。當(dāng)K值過小時(shí)，則整體的決策流程迅速，但出錯(cuò)的概率較大；當(dāng)K值過大時(shí)，則整體的決策復(fù)雜，時(shí)間和空間復(fù)雜度使識(shí)別效率降低。阿拉伯?dāng)?shù)字共計(jì)10個(gè)種類，選擇K=10，可以將10種數(shù)字容納到鄰近的K類中，有利于提高準(zhǔn)確率，同時(shí)復(fù)雜度也可以接受。

(4)決策方案的選擇。筆者將K個(gè)數(shù)據(jù)中出現(xiàn)次數(shù)最多的分類值作為最終的預(yù)測(cè)值。待識(shí)別的手寫數(shù)字通過歐式距離計(jì)算，找到10個(gè)最相似的MINIST數(shù)據(jù)集中的樣本，如果值為2的樣本最多，則待識(shí)別的手寫數(shù)字識(shí)別為2。

2.4 傳統(tǒng)KNN算法弊端分析

傳統(tǒng)KNN算法作為一種無參的簡(jiǎn)單有效的分類方法，在基于統(tǒng)計(jì)特征的機(jī)器學(xué)習(xí)中具有較好的表現(xiàn)。雖然存在上述優(yōu)點(diǎn)，但是也存在以下缺陷。

(1)手寫數(shù)字圖像具有高維度特征，使得運(yùn)算較復(fù)雜，KNN又無法很好地實(shí)現(xiàn)特征提取，對(duì)分類結(jié)果起決定性作用的維度往往遠(yuǎn)小于原輸入維度，對(duì)那些無法起決定性作用的特征，一般會(huì)成為噪聲，影響分類結(jié)果。

(2)不同人的手寫數(shù)字差異性較大，即MNIST數(shù)據(jù)集中同一類別的數(shù)字差別大，可能出現(xiàn)訓(xùn)練集中較多其他類別的圖像進(jìn)入K-最近鄰范圍，較少同一類別的圖像進(jìn)入K-最近鄰范圍，導(dǎo)致分類結(jié)果錯(cuò)誤，其模型示意如圖3所示。由圖3可知，待分類樣本的值應(yīng)為1，且分類集合中部分為1的樣本值也很靠近待分類樣本，但是由于在K-最近鄰范圍內(nèi)存在大量的樣本值為7的數(shù)據(jù)，導(dǎo)致最終的分類結(jié)果錯(cuò)誤地識(shí)別為7。

圖3 傳統(tǒng)KNN識(shí)別錯(cuò)誤模型圖

3 基于PCA降維和距離權(quán)重統(tǒng)計(jì)的改進(jìn)KNN方法

針對(duì)傳統(tǒng)KNN在手寫數(shù)字識(shí)別中存在的問題，經(jīng)過研究采取如下兩種措施進(jìn)行改進(jìn)：①針對(duì)第一個(gè)缺陷，利用主成分分析法(principal component analysis，PCA)[9]提取高維向量中的主要特征，實(shí)現(xiàn)降維。②針對(duì)第二個(gè)缺陷，將基于距離的權(quán)重統(tǒng)計(jì)方法應(yīng)用于KNN算法中，在K-最近鄰范圍，距離越近則賦于其的權(quán)重越高，這樣可以彌補(bǔ)手寫數(shù)字不規(guī)范及訓(xùn)練樣本中不同類數(shù)據(jù)相似度較高帶來的識(shí)別錯(cuò)誤問題。

3.1 PCA降維提高識(shí)別速度

3.1.1 PCA降維方法

PCA的目的就是在保證信息熵最大的情況下，使數(shù)據(jù)的維度盡可能地降低，使得計(jì)算過程中的運(yùn)算量減小。PCA就是在高維特征空間中，選擇合適的投影空間，計(jì)算高維向量在投影空間中的投影向量，即得到降維數(shù)據(jù)。具體的PCA降維過程如下：

(1)對(duì)輸入的數(shù)據(jù)進(jìn)行預(yù)處理，即按照式(7)進(jìn)行均值歸一化處理。

(7)

(2)計(jì)算協(xié)方差矩陣Σ。

(8)

(3)采用奇異值分解函數(shù)計(jì)算Σ的特征值和特征向量。

Σ=USVT

(9)

式中：U為左奇異向量，用于壓縮行特征；S為奇異值；V為右奇異向量，用于壓縮列特征。

(4)對(duì)輸入的數(shù)據(jù)按照式(10)進(jìn)行降維。

Zi=[u1，u2，…，uK]TXi

(10)

式中：ui為特征向量中前K列列向量；Zi為降維后的數(shù)據(jù)。

經(jīng)過上述的處理過程，可以有效消除手寫數(shù)字圖像中的噪聲，更加凸顯圖像數(shù)據(jù)與標(biāo)簽值之間的對(duì)應(yīng)關(guān)系，同時(shí)壓縮了特征空間，提高了執(zhí)行效率。

3.1.2 PCA的特征維度選擇

PCA的特征維度選擇對(duì)整個(gè)算法執(zhí)行有重大影響，只有采用合適的維度，才能夠既降低計(jì)算時(shí)間，又不影響算法的準(zhǔn)確度。為此，筆者首先檢測(cè)PCA特征維度選擇對(duì)整個(gè)算法的影響，通過不斷地調(diào)用執(zhí)行PCA算法的程序，并在每次迭代中對(duì)特征維度增加1，得到PCA維度與算法識(shí)別準(zhǔn)確率的關(guān)系，如圖4所示。

圖4 PCA維度選擇對(duì)算法結(jié)果的影響

由圖4可知，當(dāng)PCA特征維度選擇在20以下時(shí)，識(shí)別的準(zhǔn)確率受到明顯影響，在PCA維度為30時(shí)，其準(zhǔn)確率已經(jīng)接近最高，說明已經(jīng)有效地提取了手寫數(shù)字圖片的主要特征，再繼續(xù)增加PCA特征維度已經(jīng)對(duì)準(zhǔn)確率的提升沒有太大的影響，反而增加了很多時(shí)間和空間上的消耗。因此，改進(jìn)KNN算法的PCA特征維度選擇為30。

3.2 距離權(quán)重統(tǒng)計(jì)方法提高識(shí)別精度

距離權(quán)重統(tǒng)計(jì)的目的是為了提高分類結(jié)果的準(zhǔn)確率，在傳統(tǒng)KNN算法中，已經(jīng)計(jì)算了待分類數(shù)據(jù)與訓(xùn)練數(shù)據(jù)之間的歐氏距離，再按式(11)計(jì)算距離權(quán)重Wi。

(11)

其中，di為待測(cè)樣本與第i個(gè)近鄰的距離；d1為K近鄰中最近數(shù)據(jù)的距離；dK為K近鄰中最遠(yuǎn)數(shù)據(jù)的距離。

對(duì)上述計(jì)算得到的距離權(quán)重按照標(biāo)簽值進(jìn)行歸類疊加，疊加距離權(quán)重越大，說明待識(shí)別數(shù)字屬于此類別的可能性越大。

3.3 改進(jìn)KNN算法流程的設(shè)計(jì)

改進(jìn)KNN算法流程：①首先讀入數(shù)據(jù)，形成特征矩陣。②運(yùn)用PCA方法對(duì)手寫數(shù)字圖像特征進(jìn)行降維處理。③采用傳統(tǒng)的KNN算法，選擇距離最近的前K條訓(xùn)練數(shù)據(jù)。④對(duì)選出的前K條訓(xùn)練數(shù)據(jù)進(jìn)行距離權(quán)重統(tǒng)計(jì)，選擇疊加權(quán)重最大的類別，為待分類數(shù)據(jù)的類別。

在傳統(tǒng)KNN算法的基礎(chǔ)上，加入PCA降維和距離權(quán)重統(tǒng)計(jì)兩種方法組合成改進(jìn)的KNN算法，并應(yīng)用于手寫數(shù)字識(shí)別中，其算法流程如圖5所示。

圖5 改進(jìn)KNN算法流程圖

4 實(shí)驗(yàn)結(jié)果及分析

選定手寫數(shù)字集MNIST中樣本數(shù)據(jù)集數(shù)量為3 000，K值為10，PCA維度為30，選擇MNIST中測(cè)試集的10 000條測(cè)試數(shù)據(jù)，用Python編程對(duì)傳統(tǒng)KNN算法和改進(jìn)KNN算法進(jìn)行測(cè)試，得到傳統(tǒng)KNN算法和改進(jìn)KNN算法的準(zhǔn)確率和全部預(yù)測(cè)完10 000條測(cè)試數(shù)據(jù)所用時(shí)間，如表1所示。

表1 基于KNN算法的測(cè)試結(jié)果對(duì)比表

由表1可知，改進(jìn)的KNN算法在預(yù)測(cè)的準(zhǔn)確率上提高了3.12%，準(zhǔn)確率達(dá)到了93.86%，但識(shí)別時(shí)間不到傳統(tǒng)KNN算法的2%，說明改進(jìn)的KNN算法的執(zhí)行效率得到極大提高，節(jié)約了時(shí)間和空間。雖然特征不夠明顯的數(shù)據(jù)因書寫不規(guī)范的原因仍然存在識(shí)別錯(cuò)誤的情況，但是相對(duì)于傳統(tǒng)KNN算法而言，從準(zhǔn)確率對(duì)比上可以看出，部分?jǐn)?shù)據(jù)因手寫不規(guī)范引發(fā)的分類誤差已經(jīng)得到了明顯的改善。

基于上述測(cè)試結(jié)果，統(tǒng)計(jì)得到改進(jìn)KNN算法的識(shí)別錯(cuò)誤數(shù)據(jù)的分布，如圖6所示。由圖6可知，錯(cuò)誤主要發(fā)生在3和8之間，因?yàn)橛刹煌娜藭鴮懙臄?shù)字3在外貌描述上與8更接近，導(dǎo)致改進(jìn)KNN算法識(shí)別錯(cuò)誤。

圖6 改進(jìn)KNN算法的識(shí)別錯(cuò)誤統(tǒng)計(jì)圖

在人工智能領(lǐng)域，基于神經(jīng)網(wǎng)絡(luò)算法比基于統(tǒng)計(jì)特征分類的KNN算法有更好的識(shí)別準(zhǔn)確度。為此，筆者也對(duì)基于卷積神經(jīng)網(wǎng)絡(luò)算法和基于BP神經(jīng)網(wǎng)絡(luò)的算法[10]在手寫數(shù)字集MNIST上進(jìn)行實(shí)驗(yàn)，同樣，選定樣本數(shù)據(jù)集數(shù)量為3 000，選擇測(cè)試集中的10 000條測(cè)試數(shù)據(jù)，實(shí)驗(yàn)得到兩種算法的訓(xùn)練耗時(shí)、預(yù)測(cè)耗時(shí)及準(zhǔn)確率，結(jié)果如表2所示。由表2可知，改進(jìn)的KNN算法雖然相對(duì)于傳統(tǒng)KNN算法的準(zhǔn)確率提高了3.12%，但相對(duì)于神經(jīng)網(wǎng)絡(luò)算法，尤其是卷積神經(jīng)網(wǎng)絡(luò)算法，仍然有差距。所以，類別差異小的分類與識(shí)別宜選擇卷積神經(jīng)網(wǎng)絡(luò)算法，改進(jìn)KNN算法復(fù)雜度低，可用于類別之間差異大的分類與識(shí)別，如電影分類、網(wǎng)頁內(nèi)容分類、話題分類[11]等。

表2 BP神經(jīng)網(wǎng)絡(luò)和卷積神經(jīng)網(wǎng)絡(luò)算法測(cè)試結(jié)果

5 結(jié)論

在傳統(tǒng)KNN算法的基礎(chǔ)上，采用PCA降維方法和距離權(quán)重統(tǒng)計(jì)進(jìn)行算法改進(jìn)，得到的改進(jìn)KNN算法可以極大地提高手寫數(shù)字識(shí)別的效率，并且提高了識(shí)別準(zhǔn)確率。改進(jìn)KNN算法相對(duì)于卷積神經(jīng)網(wǎng)絡(luò)算法，雖在識(shí)別精度上有差距，但復(fù)雜度低，更適用于類別之間差異大的分類與識(shí)別。