基于k-鄰近算法的手寫(xiě)識(shí)別系統(tǒng)的研究與實(shí)現(xiàn)

辛英

（山東工商學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院，山東煙臺(tái)264005）

近年來(lái)人工智能與模式識(shí)別技術(shù)飛速發(fā)展，成為當(dāng)前的熱門(mén)技術(shù)。手寫(xiě)字符的識(shí)別是模式識(shí)別領(lǐng)域的重要分支。國(guó)內(nèi)外對(duì)手寫(xiě)輸入文字的識(shí)別技術(shù)歷經(jīng)了多年的研究并取得了很好的應(yīng)用性成果。手寫(xiě)輸入字符由于輸入時(shí)的隨意與筆畫(huà)的不規(guī)則，使得同一字符的輸入有著多樣性，給識(shí)別增添了難度。經(jīng)過(guò)多年的研究，針對(duì)手寫(xiě)字符的識(shí)別提出了多種解決方案，每種方法采用不同的數(shù)學(xué)模型進(jìn)行手寫(xiě)字符的特征提取，常用的模式識(shí)別方法大致有兩類(lèi)：第一類(lèi)通過(guò)現(xiàn)成的模板、矩陣、集成特征直接比照識(shí)別，第二類(lèi)通過(guò)字符的關(guān)鍵節(jié)點(diǎn)、端點(diǎn)或者粗糙處等結(jié)構(gòu)特征直接識(shí)別。大致的方法包括模板匹配、統(tǒng)計(jì)決策與句法構(gòu)造等方法。簡(jiǎn)單容易的事情。本文基于機(jī)器學(xué)習(xí)的思想進(jìn)行手寫(xiě)字符的識(shí)別，力求把人工智能的新技術(shù)應(yīng)用到手寫(xiě)字符識(shí)別領(lǐng)域進(jìn)行字符的預(yù)處理和特征提取，最終達(dá)到提高識(shí)別精度與準(zhǔn)確率的目的。本文選取的機(jī)器學(xué)習(xí)算法是k-鄰近算法，基于該算法設(shè)計(jì)了手寫(xiě)識(shí)別系統(tǒng)。系統(tǒng)包括學(xué)習(xí)與識(shí)別兩大模塊，采用Python語(yǔ)言編寫(xiě)完成。

1 系統(tǒng)簡(jiǎn)介

1.1 K-鄰近算法

k-鄰近算法（kNN）是機(jī)器學(xué)習(xí)領(lǐng)域中的一個(gè)簡(jiǎn)單易用的算法，常用語(yǔ)分類(lèi)之中。它的原理非常簡(jiǎn)單，卻是數(shù)據(jù)挖掘領(lǐng)域的十大算法之一。它的基本思想是丈量樣本點(diǎn)與不同特征值之間的距離來(lái)確定樣本點(diǎn)的類(lèi)別。它的工作原理如圖1所示：假設(shè)存在一個(gè)樣本數(shù)據(jù)，在機(jī)器學(xué)習(xí)中常把這樣的樣本數(shù)據(jù)稱作訓(xùn)練數(shù)據(jù)，該數(shù)據(jù)集合中的每一個(gè)數(shù)據(jù)都有各自對(duì)應(yīng)的標(biāo)簽屬性，即該集合存在著數(shù)據(jù)到樣本集合的映射。當(dāng)輸入一個(gè)沒(méi)有標(biāo)簽的數(shù)據(jù)時(shí)，k鄰近算法要求我們將該數(shù)據(jù)與樣本集合中的每一個(gè)數(shù)據(jù)特征一一比較，然后提取前k個(gè)與該數(shù)據(jù)最相似的特征對(duì)應(yīng)的樣本標(biāo)簽。最后統(tǒng)計(jì)這k個(gè)數(shù)據(jù)中出現(xiàn)頻率最多的標(biāo)簽對(duì)應(yīng)的分類(lèi)，把該類(lèi)別作為新數(shù)據(jù)的標(biāo)簽分類(lèi)。通常k是一個(gè)不大于20的整數(shù)，其選取需要根據(jù)訓(xùn)練數(shù)據(jù)集的大小確定。

圖1 k-鄰近算法原理

由上述闡述，總結(jié)k鄰近算法的步驟如下

1）數(shù)據(jù)搜集與準(zhǔn)備：在Python中通常采用寫(xiě)網(wǎng)絡(luò)爬蟲(chóng)的方式，從各大互聯(lián)網(wǎng)站上搜集數(shù)據(jù)。大數(shù)據(jù)時(shí)代，也有各種現(xiàn)成的數(shù)據(jù)庫(kù)提供所需的數(shù)據(jù)。在機(jī)器學(xué)習(xí)中，數(shù)據(jù)的搜集是開(kāi)始系統(tǒng)構(gòu)建的重要步驟。數(shù)據(jù)搜集完成后，需要對(duì)數(shù)據(jù)進(jìn)行整理，最好化成結(jié)構(gòu)化的形式，為后續(xù)的使用提供便利。

2）訓(xùn)練算法：對(duì)于大多數(shù)的機(jī)器學(xué)習(xí)算法，利于決策樹(shù)、神經(jīng)網(wǎng)絡(luò)等，算法的訓(xùn)練是模型構(gòu)建的必須步驟，通過(guò)訓(xùn)練算法，獲得模型的參數(shù)，然后對(duì)需要預(yù)測(cè)的數(shù)據(jù)進(jìn)行分析。但在k鄰近算法中，卻不需要進(jìn)行預(yù)先的訓(xùn)練。

3）實(shí)施kNN算法：根據(jù)k鄰近算法的原理，先計(jì)算樣本數(shù)據(jù)與當(dāng)前數(shù)據(jù)的特征之間的距離，隨后對(duì)所有計(jì)算出的距離遞增排序，選取前k個(gè)距離最小的樣本點(diǎn)，統(tǒng)計(jì)前k個(gè)樣本點(diǎn)中所在類(lèi)別的頻率，并將出現(xiàn)頻率最高的樣本點(diǎn)對(duì)應(yīng)的分類(lèi)作為當(dāng)前數(shù)據(jù)的分類(lèi)。

4）算法測(cè)試：由于所有的算法都不是百分之百完美的，預(yù)測(cè)的結(jié)果可能與真實(shí)值存在一定的偏差。在使用k鄰近算法構(gòu)建分類(lèi)器之后需要對(duì)該分類(lèi)器的性能進(jìn)行評(píng)估。在測(cè)試的過(guò)程中，為了客觀的評(píng)估k鄰近算法的正確率，文中選取已有數(shù)據(jù)的90%來(lái)訓(xùn)練模型生成分類(lèi)器，用剩下的10%數(shù)據(jù)作為測(cè)試樣本來(lái)測(cè)試分類(lèi)器的正確率。在選取過(guò)程中，注意數(shù)據(jù)的隨機(jī)性即可。

1.2 系統(tǒng)框架設(shè)計(jì)

通過(guò)參考相關(guān)文獻(xiàn)，并結(jié)合本系統(tǒng)的實(shí)際需求，建立如圖2所示的手寫(xiě)識(shí)別系統(tǒng)。具體包括通過(guò)手寫(xiě)板或者觸摸屏進(jìn)行數(shù)據(jù)的采集，然后通過(guò)數(shù)據(jù)的預(yù)處理將數(shù)據(jù)進(jìn)行歸一化抽取相關(guān)的特征，根據(jù)由k-鄰近算法生成的識(shí)別字典進(jìn)行特征匹配，最后輸出識(shí)別結(jié)果。

圖2 手寫(xiě)識(shí)別系統(tǒng)原理框圖

1）預(yù)處理：在進(jìn)行手寫(xiě)字符的識(shí)別之前，系統(tǒng)需要先對(duì)輸入到手寫(xiě)版或者觸摸屏的文字進(jìn)行預(yù)處理。在預(yù)處理的第一階段，需要做的是對(duì)手寫(xiě)版或者觸摸屏上筆的位置檢測(cè)錯(cuò)來(lái)，并化作x，y坐標(biāo)輸入計(jì)算機(jī)，通過(guò)A/D轉(zhuǎn)換技術(shù)，化成數(shù)字信號(hào)進(jìn)行處理。得到的坐標(biāo)由于含有干擾和噪聲需要進(jìn)行平滑、去噪與插入處理。噪聲、干擾往往是由人在輸入時(shí)手部的抖動(dòng)、感應(yīng)噪聲等造成，不可避免。因此預(yù)處理階段十分重要，是手寫(xiě)字符識(shí)別的基礎(chǔ)。

2）特征提?。涸跈C(jī)器學(xué)習(xí)的系統(tǒng)中特征工程中，特征的提取是核心步驟之一。對(duì)于樣本的特征提取可以分為兩個(gè)類(lèi)別，分別是結(jié)構(gòu)特征與統(tǒng)計(jì)特征。關(guān)于結(jié)構(gòu)特征：手寫(xiě)字符的結(jié)構(gòu)性很強(qiáng)，表達(dá)信息豐富。在進(jìn)行結(jié)構(gòu)特征提取時(shí)，本文采用自底向上的方法，由預(yù)處理后的像素開(kāi)始，得到筆段，再用筆段合成筆畫(huà)，用筆畫(huà)生成字根，用字根識(shí)別手寫(xiě)字符。結(jié)構(gòu)特征的提取對(duì)于用戶按筆畫(huà)輸入的字符優(yōu)勢(shì)十分明顯。關(guān)于統(tǒng)計(jì)特征：統(tǒng)計(jì)特征是指字符輸入的輪廓、邊緣信息以及水平、豎直、對(duì)角、反對(duì)角等特征信息。按照統(tǒng)計(jì)特征進(jìn)行特征提取是將字符識(shí)別視作模式識(shí)別問(wèn)題，用機(jī)器學(xué)習(xí)的思想通過(guò)對(duì)象特征學(xué)習(xí)、經(jīng)驗(yàn)積累多次訓(xùn)練計(jì)算機(jī)，再應(yīng)用于字符的識(shí)別。統(tǒng)計(jì)特征又分為全局特征與局部特征，良好的特征工程可以大大提高算法的精確度，提高識(shí)別準(zhǔn)確率。

3）特征匹配：特征匹配是特征提取的目的所在。通過(guò)測(cè)試樣本與學(xué)習(xí)樣本之間的特征匹配，可以得到測(cè)試樣本的分類(lèi)。針對(duì)結(jié)構(gòu)特征的匹配取采用結(jié)構(gòu)特征匹配的方法，結(jié)構(gòu)特征的匹配需要將提取出的輸入信息與標(biāo)準(zhǔn)模板中的信息進(jìn)行比對(duì)，找到最相似的字體完成識(shí)別。在當(dāng)前的手寫(xiě)識(shí)別系統(tǒng)中，常常采用按照筆劃順序輸入一筆識(shí)別一筆的方法，完成結(jié)構(gòu)特征的識(shí)別。統(tǒng)計(jì)特征匹配對(duì)應(yīng)于統(tǒng)計(jì)特征提取。在本文中采取k-鄰近算法計(jì)算提取出的特征與樣本特征的距離，進(jìn)行分類(lèi)判決。距離度量采用歐式距離，以簡(jiǎn)化特征工程與模板建立，同時(shí)可以提高模型的抗干擾能力。其他常用的算法還有支持向量機(jī)與人工神經(jīng)網(wǎng)絡(luò)。

2 系統(tǒng)實(shí)現(xiàn)與仿真

文中描述的手寫(xiě)識(shí)別系統(tǒng)采用Python語(yǔ)言實(shí)現(xiàn)，Python版本為2.7，開(kāi)發(fā)環(huán)境選擇Windows7下的Spyder。Python語(yǔ)言具有結(jié)構(gòu)清晰、易于操作文本文件等優(yōu)點(diǎn)，在開(kāi)發(fā)中有非常豐富的開(kāi)發(fā)文檔，針對(duì)機(jī)器學(xué)習(xí)，Python中集成了現(xiàn)在最流行的SciPy、NumPy等科學(xué)計(jì)算庫(kù)，在數(shù)據(jù)可視化上，有Matplotlib用于2D、3D圖形的繪制。同時(shí)，Python還提供了shell交互環(huán)境，為用戶在開(kāi)發(fā)過(guò)程中的查看與檢測(cè)程序提供便利。

2.1 算法實(shí)現(xiàn)

文中先建立kNN.py模塊保存系統(tǒng)的所有代碼。

第一步是導(dǎo)入系統(tǒng)所需的相關(guān)模塊，第一個(gè)是科學(xué)計(jì)算包numpy，第二個(gè)是運(yùn)算符operator。

在數(shù)據(jù)預(yù)處理中包括兩個(gè)函數(shù)，一個(gè)是將文本記錄轉(zhuǎn)化為Numpy庫(kù)可以處理的矩陣的file2matrix函數(shù)，一個(gè)是將圖像格式化處理的img2vector函數(shù)，其中img2vector函數(shù)可以將從手寫(xiě)板獲取的32*32的二進(jìn)制圖像轉(zhuǎn)化為1*1024的向量，系統(tǒng)選取的學(xué)習(xí)樣本如圖3所示。

圖3 學(xué)習(xí)樣本

數(shù)據(jù)的預(yù)處理還包括歸一化函數(shù)autoNorm，采取的歸一化公式如下：

然后根據(jù)1.1中的步驟實(shí)施k-鄰近算法，在kNN.py中添加classify0函數(shù)

Classfy0中輸入4個(gè)參數(shù)，其中inX是用于分類(lèi)的向量，dataSet是訓(xùn)練所需的樣本數(shù)據(jù)，labels是每個(gè)訓(xùn)練樣本對(duì)應(yīng)的標(biāo)簽，k表適用于選擇最近鄰居的數(shù)目。在特征距離的計(jì)算上，采用歐式距離：

文中用提供的數(shù)據(jù)集進(jìn)行模型的訓(xùn)練，并選取剩下的10%進(jìn)行測(cè)試，算法的錯(cuò)誤率為1.2%，在算法中更改模型的參數(shù)k，更改隨機(jī)選取的樣本與測(cè)試樣本的數(shù)目都會(huì)對(duì)錯(cuò)誤率造成影響，本文經(jīng)多次調(diào)整參數(shù)進(jìn)行優(yōu)化，獲得較優(yōu)值。

2.2 算法測(cè)試

文中在測(cè)試時(shí)，從網(wǎng)上截取了一段200字的新聞稿，在文稿的選取上，文中特意關(guān)注了字符的多樣性，在本段文字中，包括文字、標(biāo)點(diǎn)、數(shù)字等多種符號(hào)。然后選擇了10名用戶對(duì)該段文字進(jìn)行手寫(xiě)輸入，新聞稿與用戶的輸入數(shù)據(jù)分別如圖4、圖5所示。

圖4 新聞稿數(shù)據(jù)

圖6為系統(tǒng)對(duì)用戶書(shū)寫(xiě)樣本的識(shí)別情況，在編輯區(qū)域可以清晰地看到用戶的筆跡與系統(tǒng)的識(shí)別結(jié)果。其中黑色的為系統(tǒng)的首先字符，淺灰色的為二選字符，在k鄰近算法判別二選字符與首選字符類(lèi)別判別模糊時(shí)，本系統(tǒng)為用戶提供第二接近的字符，供用戶判別。通過(guò)計(jì)算機(jī)智能自動(dòng)識(shí)別與人工識(shí)別相結(jié)合的方式，提高手寫(xiě)字符的準(zhǔn)確率。經(jīng)過(guò)十個(gè)用戶的輸入數(shù)據(jù)的測(cè)試，本系統(tǒng)的首選加二選識(shí)別準(zhǔn)確率達(dá)到95%以上。

圖5 測(cè)試輸入手寫(xiě)字符

圖6 手寫(xiě)樣本識(shí)別

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

文中介紹了一種基于k鄰近算法實(shí)現(xiàn)的手寫(xiě)字符的識(shí)別系統(tǒng)。通過(guò)采用k鄰近算法，將用戶手寫(xiě)的輸入字符數(shù)據(jù)與樣本集合中的每一個(gè)數(shù)據(jù)特征一一比較，然后提取前k個(gè)與該數(shù)據(jù)最相似的特征對(duì)應(yīng)的樣本標(biāo)簽返回識(shí)別結(jié)果。經(jīng)測(cè)試，本識(shí)別系統(tǒng)有較高的識(shí)別正確率，可以廣泛應(yīng)用在未來(lái)的手寫(xiě)輸入系統(tǒng)中。

參考文獻(xiàn)：

[1]曾紀(jì)川.基于安卓的篇章級(jí)手寫(xiě)識(shí)別輸入法[D].哈爾濱：哈爾濱工業(yè)大學(xué)，2013.

[2]王曉龍，關(guān)毅.計(jì)算機(jī)自然語(yǔ)言處理[M].北京:清華大學(xué)出版社，2005.

[3]孫家廣.計(jì)算機(jī)圖形學(xué)[M].北京:清華大學(xué)出版社，1998.

[4]王秋生，孫圣和，鄭為民.數(shù)字音頻信號(hào)的脆弱水印嵌入算法[J].計(jì)算機(jī)學(xué)報(bào)，2002，25（5）:1-6.

[5]徐舒暢.基于色素分離的皮膚圖像處理與分析[D].杭州:浙江大學(xué)2007.

[6]房秉毅，張?jiān)朴?，程瑩，?云計(jì)算國(guó)內(nèi)外發(fā)展現(xiàn)狀分析[J].電信科學(xué)，2010，26（8）:1-6.

[7]羅軍舟，金嘉暉，宋愛(ài)波，等.云計(jì)算:體系架構(gòu)與關(guān)鍵技術(shù)[J].通信學(xué)報(bào)，2011，32（7）:3-21.

[8]陳康，鄭緯民.云計(jì)算:系統(tǒng)實(shí)例與研究現(xiàn)狀[J].軟件學(xué)報(bào)，2009，20（5）:1337-1348.

[9]Cusumano M.Cloud computing and SaaS as new computing platforms[J].Communications ofthe ACM，2010，53（4）:27-29.

[10]何聰，金連文，周貴斌.基于云計(jì)算平臺(tái)的手寫(xiě)識(shí)別系統(tǒng)[J].電信科學(xué)，2010，26（9）:84-89.

[11]Hinton G E，Salakhutdinov R R.Reducing the dimensionality ofdata withneuralnetworks[J].Science，2006，313（5786）:504-507.

[12]孫志軍，薛磊，許陽(yáng)明，等.深度學(xué)習(xí)研究綜述[J].計(jì)算機(jī)應(yīng)用研究，2012，29（8）:2806-2810.

[13]黃凱奇，任偉強(qiáng)，譚鐵牛.圖像物體分類(lèi)與檢測(cè)算法綜述[J].計(jì)算機(jī)學(xué)報(bào)，2014，37（6）:1225-1240.

[14]馮帆，王建華，張政保，等.基于CSR-ICA模型的隱寫(xiě)信息盲提取算法[J].計(jì)算機(jī)工程與應(yīng)用，2013（24）:70-73.

[15]王森，楊克儉.基于雙線性插值的圖像縮放算法的研究與實(shí)現(xiàn)[J].自動(dòng)化技術(shù)與應(yīng)用，2008，27（7）:44-45.

[16]趙甲.利用條件概率與乘法公式解釋搜索引擎拼寫(xiě)糾錯(cuò)功能的原理[J].湖北科技學(xué)院學(xué)報(bào)，2013，33（3）:183-184.

[17]趙曦.基于仿生算法的顯著性特征數(shù)據(jù)挖掘方法[J].西安工程大學(xué)學(xué)報(bào)，2017（2）:244-250.

[18]章佳佳，楊振超，周律.基于Matlab圖像處理的果核分揀系統(tǒng)[J].電子科技，2017（9）:50-52.