李詩語+王峰+曹彬+梅琪+肖飛

摘要：一直以來，讓機器具有模式識別能力一直是計算機科學(xué)家們的努力方向。研究模式識別，是理解人類智能的本質(zhì)的重要途徑。字符識別是一個典型的模式識別問題，手寫數(shù)字識別具有不同字符體型相差不大，相同字符有多種不同寫法，數(shù)字沒有上下文關(guān)聯(lián)等特點，這些特點使手寫數(shù)字識別比較困難。該論文設(shè)計了一套基于KNN算法，用Python語言實現(xiàn)手寫數(shù)字識別系統(tǒng)。先對圖片進行預(yù)處理，預(yù)處理包括灰度化、去噪、二值化等等，再用KNN算法對圖片進行分類，手寫數(shù)字識別也是一個十分類的問題。實驗結(jié)果表明該文所設(shè)計的手寫數(shù)字識別具有較好的識別率，同時也說明KNN算法在手寫數(shù)字識別上具有良好的應(yīng)用。

關(guān)鍵詞：KNN算法；Python語言；模式識別；預(yù)處理；手寫數(shù)字識別

中圖分類號：TP391.43 文獻標(biāo)識碼：A 文章編號：1009-3044（2017）25-0175-03

Abstract： All along， There always been a direction of computer scientists' efforts of Making the machine a pattern recognition capability. Research pattern recognition is an important way to understand the essence of human intelligence. Character recognition is a typical pattern recognition problem. Handwritten digital recognition has different characters. The same characters have many different Wordings， and the numbers are not context-sensitive. These features make handwritten digital recognition difficult. This paper designs a set of KNN algorithm Based on Python language to achieve handwritten digital recognition system. First of all， the image preprocessing， including gray， denoising， binarization， etc.， and then use KNN algorithm to classification image， the handwritten digital recognition is a ten classification problem. The experimental results show that the handwritten digital recognition in this paper has a good recognition rate， and also shows that KNN algorithm has a good application in handwritten numeral recognition.

Key words： KNN algorithm； Python language； pattern recognition； preprocessing； handwritten numeral recognition

1 緒論

1.1 研究的背景

光學(xué)字符識別是圖像處理與模式識別領(lǐng)域的一個重要分支。其目的就是通過掃描，攝像等光學(xué)輸入方式將漢字報刊，書籍，文稿及其他印刷品的文字轉(zhuǎn)化為圖像信息，將圖形，表格的圖像進行保存，再利用文字識別技術(shù)講圖像內(nèi)的文字或表格中的資料一律變成計算機能識別的文字，以便于計算機的管理維護。它能夠減少存儲容量，通信交流的信息，循環(huán)利用已識別出的文字以及節(jié)省因鍵盤輸入而浪費的人力，物力，財力和時間。

手寫數(shù)字識別是光學(xué)字符識別的一個分支，它的研究對象是，如何利用電子計算機自動辨認人手寫在紙張上的阿拉伯?dāng)?shù)字[1]。手寫數(shù)字識別屬于模式識別，是人工智能的一個重要分支，涉及模式識別和圖像處理，人工智能，統(tǒng)計對策理論，模糊數(shù)學(xué)，組合數(shù)學(xué)，信息論，計算機等學(xué)科。

1.2 手寫數(shù)字識別的意義和前景

手寫數(shù)字識別不僅有重大的現(xiàn)實意義，而且有廣闊的應(yīng)用前景，由于當(dāng)今的經(jīng)濟發(fā)展，金融市場發(fā)展日益加快，票據(jù)業(yè)務(wù)發(fā)展很快，例如個人憑證，支票，發(fā)票，進賬單等票據(jù)都需要處理大量信息，如果這些信息全依賴人工輸入，無疑會浪費大量人力物力，會造成成本高，效率低等問題。所以，手寫數(shù)字識別顯得很有必要。由于阿拉伯?dāng)?shù)字是唯一的被世界各國通用的符號，所以對手寫數(shù)字識別的研究基本上與文化背景無關(guān)，研究者研究出這一技術(shù)，世界可以通用，也為各國研究者提供了一個共同探討的平臺。并且，手寫數(shù)字識別的方法很容易被推廣到其他相關(guān)問題上，比如英文字母識別等。

2 KNN算法

2.1 KNN算法的基本介紹

K最近鄰（k-Nearest Neighbor，KNN）是一種基于統(tǒng)計學(xué)的分類方法，該算法最早于1968年由Cover和Hart提出，作為最簡單的機器學(xué)習(xí)方法，理論上研究已比較成熟[2]。

KNN算法主要是在文本分類上有著極好的分類效果，包括信息檢索、機器翻譯、自動文摘、信息過濾、郵件分類等任務(wù)。文本分類在搜索引擎中也有這大量的使用，KNN算法不僅可以用于分類，還可以用于回歸。通過找出一個樣本的K個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對該樣本產(chǎn)生的影響給予不同的權(quán)值，如權(quán)值與距離成正比。還可以用KNN算法做現(xiàn)有用戶產(chǎn)品推薦，基于用戶的最近鄰買了什么產(chǎn)品來推薦。endprint

2.2 KNN算法的實現(xiàn)

KNN分類算法是最簡單的機器學(xué)習(xí)算法之一，理論上比較成熟[3]。KNN算法的核心思想是如果一個樣本在特征空間中的K個最近鄰的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別，并具有這個類別上樣本的特性。KNN方法在類別決策時，只與極少量的相鄰樣本有關(guān)。KNN算法的原理如圖1，圓要被決定賦予哪個類，是三角形還是四方形，如果K = 3，由于三角形所占比例為2/3，圓將被賦予三角形那個類，如果K = 5，由于四方形比例為3/5，因此圓被賦予四方形類。

該算法對未知類別屬性的數(shù)據(jù)集中的每個點依次執(zhí)行以下操作：

1） 計算已知類別數(shù)據(jù)集中的點與當(dāng)前點之間的距離；

2） 按照距離遞增次序排序；

3） 選取與當(dāng)前點距離最小的k個點；

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

5） 返回前k個點出現(xiàn)頻率最高的類別作為當(dāng)前點的預(yù)測分類。

KNN算法的優(yōu)點是計算簡單，在基于統(tǒng)計的模式識別中有效性及其突出，已成為在模式識別、回歸、文本分類和數(shù)據(jù)挖掘領(lǐng)域比較常見的一種分類方法，該算法準確率高容易實現(xiàn)，使用簡單易于操作，一些文獻表明KNN算法分類效果好，并且在訓(xùn)練過程中投入的時間最少[2]。但KNN算法仍然存在不足，主要表現(xiàn)為對于高維文本向量樣本規(guī)模較大時，算法的時間和空間復(fù)雜度較高，當(dāng)新待分類樣本到來時，每次都要計算其與所有訓(xùn)練樣本的距離（或相似度），這就大大降低了算法的效率[4]。

3 手寫數(shù)字識別的實現(xiàn)

手寫數(shù)字識別中圖像的預(yù)處理非常重要，在處理圖像照片的時候，由于光照，背景，拍攝角度等外界因素的影響，會造成圖像失真并帶有噪聲，因為這些噪聲的緣故，識別圖片中的數(shù)字時會發(fā)生誤差，造成數(shù)字識別錯誤，所以要對圖像進行預(yù)處理。預(yù)處理的目的是去除圖像中的噪聲，壓縮圖像中的冗余信息，得到規(guī)范化的點陣，為識別做好準備，預(yù)處理是把圖像轉(zhuǎn)化成識別器能接受的二進制形式。

預(yù)處理的過程如圖2，先把圖像灰度化，所謂的灰度圖像是指圖像的每一個像素的R，G，B分量的值都是相等的，彩色圖像的每個像素的R，G，B都是不同的，所以顯示出不同顏色，由于圖像拍出來是彩色的，而彩色的圖片比較復(fù)雜，使得很多算法沒辦法展開，所以要對圖像進行灰度化。

對圖像進行了灰度化之后，每個像素只有一個灰度值，它的大小決定了圖像的亮暗程度，為了更加便利地對圖形進行處理，要對圖像進行二值化處理，二值化處理就是根據(jù)像素中的灰度值把圖片處理成黑白兩種顏色，對圖像二值化處理后要能在現(xiàn)原數(shù)字，即筆畫要能保持原特征，筆畫中不能出現(xiàn)空白點。

圖像在掃描過程中會產(chǎn)生噪聲，所以要對圖像進行去噪處理，平滑去噪的目的在于去除孤立的噪聲點，填充字符邊緣的凹陷或者去除凸點。

歸一化是預(yù)處理中非常重要的一環(huán)，由于原始圖像在大小上存在差異，所以要進行歸一化把圖像變得大小一樣，有利于提高識別的準確度，預(yù)處理結(jié)果如圖3。

因為Python適用于處理純文本文檔，所以先把經(jīng)過上述預(yù)處理后的圖片轉(zhuǎn)化成純文本文檔，本實驗是把圖片轉(zhuǎn)化成32*32的純文本文檔，如圖4 ，圖片上寫數(shù)字的地方的數(shù)字為非零的常數(shù)，空白地方的數(shù)字為零。然后把轉(zhuǎn)化好的圖片和已經(jīng)存在的圖片集用KNN算法進行比較，找出圖片屬于哪一類，從而識別出圖片中的數(shù)字。

如圖5為本實驗的結(jié)果，由于本實驗一次性只驗證了十個數(shù)字，所以正確率為百分之百。如驗證數(shù)字足夠多，則會出現(xiàn)一定量的誤差，一般來講，訓(xùn)練集越大，則驗證時的誤差就會越小，用KNN算法做手寫數(shù)字識別，識別準確，誤差小。

4 結(jié)束語

本實驗選用Python語言來進行編程，用KNN算法實現(xiàn)功能，Python具有清晰的語法結(jié)構(gòu)，使用廣泛，代碼范例也很多，相比于JAVA和C，Python的代碼量要少很多， KNN算法理解簡單，易于實現(xiàn)，精度高，對異常值不敏感，缺點是計算量大，所以仍需改進。目前主要通過兩種途徑來減小KNN方法的計算量：一種是通過對高維文本向量進行降維處理。另一種是通過使用小樣本庫代替原來的大樣本庫進行分類。這類分類方法一般是在原來的訓(xùn)練樣本庫中選取一些代表樣本作為新的訓(xùn)練樣本，或刪除原來的訓(xùn)練樣本庫中的某些樣本，將剩下的樣本作為新的訓(xùn)練樣本庫，從而達到減小訓(xùn)練樣本庫的目的[4]。

參考文獻：

[1] 任丹， 陳學(xué)峰. 手寫數(shù)字識別的原理及應(yīng)用[J]. 計算機時代， 2007（3）：17-18.

[2] 潘登. KNN算法的相似度研究[D]. 東北師范大學(xué)， 2014.

[3] 肖輝輝， 段艷明. 基于屬性值相關(guān)距離的KNN算法的改進研究[J]. 計算機科學(xué)， 2013， 40（11a）：157-159.

[4] 卜凡軍. KNN算法的改進及其在文本分類中的應(yīng)用[D]. 江南大學(xué)， 2009.endprint