基于KNN算法的手寫數(shù)字識別研究

張 勇，馬亞州，侯益明

(山西農(nóng)業(yè)大學(xué) 信息科學(xué)與工程學(xué)院，山西 太谷 030801)

0 引言

近年來，隨著科學(xué)技術(shù)的不斷發(fā)展和創(chuàng)新，人工智能迅速崛起，手寫數(shù)字識別在各行各業(yè)也有了應(yīng)用，尤其在金融行業(yè)應(yīng)用更加廣泛，但數(shù)字識別的錯誤在金融領(lǐng)域所帶來的后果是不可低估的[1]，因此，對手寫數(shù)字識別的準(zhǔn)確率要求相當(dāng)高。

為了提高手寫數(shù)字識別的準(zhǔn)確率，本研究使用K最近鄰(K-Nearest Neighbor，KNN)算法構(gòu)建分類器，識別手寫數(shù)字的準(zhǔn)確率得到了很大的提高，而且實現(xiàn)方便簡單，運行速度快，值得進(jìn)一步去研究。

1 KNN算法

KNN算法中存在一個樣本數(shù)據(jù)集合，在該集合中，每個數(shù)據(jù)對應(yīng)一個標(biāo)簽，即數(shù)據(jù)與其類別之間一一對應(yīng)[2]，當(dāng)輸入一個未知類別的數(shù)據(jù)之后，算法會計算該數(shù)據(jù)的每個特征與樣本數(shù)據(jù)集中所有數(shù)據(jù)對應(yīng)特征之間的關(guān)系，具體計算方法：

(1)

將計算結(jié)果從小到大排序，選擇前K個距離最近的數(shù)據(jù)[3]，判斷其中出現(xiàn)次數(shù)最多的類別，將其作為輸入數(shù)據(jù)的類別。

2 數(shù)據(jù)準(zhǔn)備

(1)收集0—9的手寫數(shù)字圖像共2 721張，包括1 856張圖像作為樣本數(shù)據(jù)集，865張圖像作為測試數(shù)據(jù)集合。在分類之前，需要將圖像進(jìn)行預(yù)處理，可以使用圖形處理軟件，使之成為寬高是32×32 px的黑白圖像，并將圖像轉(zhuǎn)換為文本格式，使之成為32×32的二進(jìn)制矩陣[4]。

表1 樣本數(shù)量表

(2)要想使用KNN算法構(gòu)造的分類器來識別手寫數(shù)字，就需要將數(shù)據(jù)處理之后得到的二進(jìn)制矩陣轉(zhuǎn)換為1×1 024的向量，使之滿足數(shù)據(jù)集中一行代表一個數(shù)據(jù)的基本要求。

3 實驗過程

3.1 構(gòu)造分類器

根據(jù)KNN算法的原理，構(gòu)造一個有4個參數(shù)的分類器：待分類數(shù)據(jù)、樣本數(shù)據(jù)集、樣本標(biāo)簽集、K值，依次進(jìn)行新數(shù)據(jù)與樣本數(shù)據(jù)之間距離的計算、對距離由小到大排序、取得前K個距離最近的數(shù)據(jù)、確定前K個點中各類別出現(xiàn)的次數(shù)、出現(xiàn)次數(shù)最多的類別為新數(shù)據(jù)類別之后，即可預(yù)測出新數(shù)據(jù)的類別[5]。分類器流程如圖1所示。

3.2 參數(shù)K的選擇

K值的選取非常重要。(1)當(dāng)K的取值過小時，如果有噪聲成分存在，將會對預(yù)測產(chǎn)生比較大的影響。例如，取K值為1時，一旦最近的一個點是噪聲，那么就會出現(xiàn)偏差。(2)如果K的值取的過大時，就相當(dāng)于用較大鄰域中的訓(xùn)練實例進(jìn)行預(yù)測，學(xué)習(xí)的誤差會增大，與目標(biāo)點距離較遠(yuǎn)的實例也會對預(yù)測起作用，使預(yù)測可能發(fā)生錯誤。(3)如果K取N時，就是取全部的實例中出現(xiàn)次數(shù)最多的類別，則失去了預(yù)測的意義。

圖1 分類器流程圖

在選取K值時，應(yīng)該盡量選取奇數(shù)，保證最終總會得到一個分類結(jié)果，如果為偶數(shù)，可能出現(xiàn)相等的情況，不利于分類。K通常是不大于20的整數(shù)，所以，從K取1開始進(jìn)行測試，記錄分類結(jié)果的錯誤率，每次使得K值增加1，選擇錯誤率最低的K值作為分類器的K。分類錯誤率隨K值變化如圖2所示，據(jù)此進(jìn)行分析，最終選擇K值為3。

圖2 分類錯誤率隨K值的變化

3.3 數(shù)字識別

用收集到的1 856張圖像作為初始的樣本數(shù)據(jù)集合，將每張圖進(jìn)行預(yù)處理[6]，轉(zhuǎn)換為32×32的二進(jìn)制矩陣，并存儲在文本文檔中，以X_i.txt格式命名，其中，X代表數(shù)據(jù)的真實分類，i代表該類別下的第幾個數(shù)據(jù)。將樣本數(shù)據(jù)集輸入到算法中，使用split()函數(shù)對文件名進(jìn)行分割，取下標(biāo)為0的元素，即為數(shù)據(jù)的真實類別。

使用構(gòu)造好的分類器進(jìn)行測試，對于數(shù)字0—9分別進(jìn)行測試。測試前，要使用split()函數(shù)對文件名進(jìn)行分割，以得到數(shù)據(jù)的真實類別。將測試結(jié)果與其真實類別進(jìn)行比較，若不相等，則分類錯誤，錯誤次數(shù)加1，錯誤率如式(2)：

(2)

其中，x為錯誤分類的數(shù)據(jù)個數(shù)，N為進(jìn)行測試的數(shù)據(jù)個數(shù)，可以得到手寫數(shù)字識別的錯誤率，以評價分類的效果。

4 結(jié)果分析

將每個類別的數(shù)據(jù)分別輸入到分類器中，各類別的分類準(zhǔn)確率如表2所示。實驗表明，基于KNN算法構(gòu)建的分類器用于識別手寫數(shù)字準(zhǔn)確率最高可達(dá)98.89%，進(jìn)一步證明了該方法用于識別手寫數(shù)字的可行性，具有實現(xiàn)簡單、運行速度快的優(yōu)點，解決了人工處理大量數(shù)字的問題，具有很好的研究價值。

表2 各類別的分類識別準(zhǔn)確率