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

李詩(shī)語(yǔ)+王峰+曹彬+梅琪+肖飛

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

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

中圖分類號(hào)：TP391.43 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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é)字符識(shí)別是圖像處理與模式識(shí)別領(lǐng)域的一個(gè)重要分支。其目的就是通過掃描，攝像等光學(xué)輸入方式將漢字報(bào)刊，書籍，文稿及其他印刷品的文字轉(zhuǎn)化為圖像信息，將圖形，表格的圖像進(jìn)行保存，再利用文字識(shí)別技術(shù)講圖像內(nèi)的文字或表格中的資料一律變成計(jì)算機(jī)能識(shí)別的文字，以便于計(jì)算機(jī)的管理維護(hù)。它能夠減少存儲(chǔ)容量，通信交流的信息，循環(huán)利用已識(shí)別出的文字以及節(jié)省因鍵盤輸入而浪費(fèi)的人力，物力，財(cái)力和時(shí)間。

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

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

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

2 KNN算法

2.1 KNN算法的基本介紹

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

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

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

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

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

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ù)測(cè)分類。

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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