基于K近鄰算法識別手寫數(shù)字

馬玉賢，郭秀娟

吉林建筑大學 電氣與計算機學院,長春 130118

隨著經(jīng)濟的發(fā)展,金融市場也日益加快,然而仍有大量的手寫數(shù)字報告、匯款單等需要計算機進行識別管理,如果用計算機可以進行手寫數(shù)字識別,將能節(jié)省大量的人力財力物力.所以,手寫數(shù)字識別系統(tǒng)的開發(fā)對生產生活有重要的作用[1].K近鄰算法是目前理論上比較成熟的算法,與其他算法相比直觀簡單,實用性較強,已經(jīng)被廣泛應用于各種分類問題[2],所以采用K近鄰算法進行手寫數(shù)字的識別有較好的效果.

1 K近鄰算法的原理

K近鄰算法屬于分類與邏輯回歸的算法,是機器學習中簡單而且有效的算法.K近鄰學習算法屬于機器學習中的分類算法[3],工作機制相對來說比較簡單:給定一個樣本集合,也稱作樣本訓練集,并且知道樣本數(shù)據(jù)集中數(shù)據(jù)與其所屬分類的對應關系.輸入一個新的沒有分類的數(shù)據(jù)之后,計算機提取數(shù)據(jù)的特征并且與數(shù)據(jù)集中的特征對比,找出與其特征相近的K個數(shù)據(jù),在K個數(shù)據(jù)當中出現(xiàn)的分類頻次最高的分類作為這個新數(shù)據(jù)的分類.

1.1 歐拉距離

通常情況下,使用歐拉距離公式來計算向量點的距離.關于歐拉距離的計算:

二維平面上兩點A(x1,y1)與B(x2,y2)之間的歐拉距離:

(1)

三維平面上兩點A(x1,y1,z1)與B(x2,y2,z2)之間的歐拉距離:

(2)

N維向量A(x11,x12,…,x1n)與N維向量B(x21,x22,…,x2n)之間的歐拉距離:

(3)

1.2 K值的選擇

如果選擇較小的K值,訓練實例集合就會變小,訓練的近似誤差會變的很小,訓練數(shù)據(jù)與輸入的新數(shù)據(jù)相近才能有效果.K值變小的情況下,容易受到異常值的影響,更容易出現(xiàn)過擬合問題.選擇較大的K值,訓練實例會變大,訓練的近似誤差亦會變的很大,如果訓練數(shù)據(jù)與新輸入的新數(shù)據(jù)不相關也會產生不同效果,容易出現(xiàn)樣本均衡的問題,使模型變得簡單,出現(xiàn)欠擬合問題.所以,一般情況下將數(shù)據(jù)分為訓練集和測試集來選取最優(yōu)K值.

1.3 K近鄰算法的一般步驟

(1) 獲取訓練數(shù)據(jù)集,抽取其特征.

(2) 數(shù)據(jù)集中一部分作為訓練數(shù)據(jù),一部分作為測試數(shù)據(jù),用于驗證.

(3) 選取一個K值,使用交叉驗證法,即使用訓練集和驗證集選取最優(yōu)K值.

(4) 計算與K值最相近的K個樣本實例.

(5) 通過測試樣本集判斷準確性.

(6) 修改K值,跳到步驟(3),選取更準確的K值.

2 K近鄰算法在手寫識別系統(tǒng)中的實現(xiàn)

2.1 數(shù)據(jù)收集與圖像預處理

由于Python使用簡單,易于讀寫,支持面向對象的編程,所以算法的實現(xiàn)使用Python語言進行編程,采用Python3.7版本,以Pycharm Community作為集成開發(fā)環(huán)境.首先將需要識別的手寫數(shù)字進行預處理,以滿足算法的要求,把圖片處理成黑白圖片；其次將其轉換為32×32的數(shù)組放入文本文檔中；最后將圖像轉換成文本格式的文件(如圖1所示).從sklearn手寫數(shù)據(jù)集中收集2 000個從0到9的手寫數(shù)字樣本,用來訓練分類器,另外收集900個測試數(shù)據(jù)樣本,用來測試分類器的效果.

圖1 手寫數(shù)字數(shù)據(jù)集(部分) 圖2 錯誤率隨K值變化 圖3 運行結果(部分)Fig.1 Handwritten digit data set(partial) Fig.2 The error rate varies with the value of K Fig.3 Running results(partial)

2.2 準備數(shù)據(jù)與算法實現(xiàn)

將圖片轉換成向量,為了方便算法處理數(shù)據(jù),把32×32的圖像預處理為一個1×1 024的向量.然后對數(shù)據(jù)集中的每個點依次執(zhí)行以下操作:

(1) 使用歐拉距離計算已知類別數(shù)據(jù)集中的點與當前點之間的距離.

(2) 計算出距離大小按照遞增的次序對數(shù)據(jù)進行排序.

(3) 選取與當前點距離最小的K個點.

(4) 確定前K個點所在類別的出現(xiàn)頻率.

(5) 確定前K個點出現(xiàn)頻率最高的類別,作為此點的預測分類標簽.

使用K近鄰算法對預處理過的手寫數(shù)字文件進行識別,取不同的K值,并且對錯誤個數(shù)與錯誤率進行統(tǒng)計,選取最優(yōu)K值,識別錯誤率統(tǒng)計如圖2所示.由實驗統(tǒng)計可知,當K=3時,K值的錯誤率最低,因此選取K=3為最優(yōu)K值.當K=3時,部分程序運行結果如圖3所示.

2.3 結果分析

實驗表明,當K=3時,運行結果中錯誤個數(shù)為10,準確率高達98.94 %,在算法中取不同的K值,實驗準確率會有不同結果.所以,當采用交叉驗證法選取合適的值時,K近鄰算法對手寫數(shù)字的識別會有較高的準確率,證明了該算法用于手寫數(shù)字識別系統(tǒng)的可行性,且具有研究價值.各類別分類識別準確率見表1.

表1 各類別分類識別準確率Table 1 Classification and recognition accuracy of each category

3 K近鄰算法優(yōu)缺點分析

K近鄰算法作為簡單有效的分類算法,優(yōu)點比較明顯,新的數(shù)據(jù)集直接可以計算不必再重新訓練,算法也比較簡單,相對于其他算法來說比較容易實現(xiàn),準確度較高,對異常值不敏感,容忍度較高.在手寫數(shù)字識別方面,識別準確,誤差小.但是在某些方面也存在缺陷,一是由于圖像具有高維度特征,運算復雜,K近鄰算法無法準確提取特征,通常情況下會受到干擾；二是,如果驗證數(shù)字足夠多則會出現(xiàn)一定量的誤差.在執(zhí)行此算法時,其訓練時間復雜度為O(n),相比支持向量機等算法來說較低.但是在本次實驗中,每次的距離運算均有210維度的運算,算法對測試向量需做高達兩千多次的距離運算,這會導致計算復雜度過高,運行效率降低.樣本數(shù)據(jù)過多時,要計算新數(shù)據(jù)到所有點的距離,會導致計算量過大.另外,也可以對K鄰近點進行加權計算,距離遠的權重小,距離近的權重大,會提高分類的準確性.K近鄰算法屬于一種惰性學習方法,在預測時會效率低下.在空間復雜度上,該算法必須將所有的訓練數(shù)據(jù)進行保存,還要為測試樣本預留出另外的存儲空間,如果樣本數(shù)據(jù)過多,就會占用大量內存,使空間復雜度變高.

4 結語

本實驗采用Python語言進行編程,相比Java更加簡單且易于理解.K近鄰算法在手寫數(shù)字識別方面有較高的準確率,且有重要研究價值,與其他算法相比雖然算法簡單,易于理解,但是還有些許差距,如果是計算量特別大,而且復雜度高,則占用內存較多且效率低,今后還有待進一步改進.