基于k-鄰近算法的手寫識別系統的研究與實現

辛英

（山東工商學院數學與信息科學學院，山東煙臺264005）

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

1 系統簡介

1.1 K-鄰近算法

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

圖1 k-鄰近算法原理

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

1）數據搜集與準備：在Python中通常采用寫網絡爬蟲的方式，從各大互聯網站上搜集數據。大數據時代，也有各種現成的數據庫提供所需的數據。在機器學習中，數據的搜集是開始系統構建的重要步驟。數據搜集完成后，需要對數據進行整理，最好化成結構化的形式，為后續的使用提供便利。

2）訓練算法：對于大多數的機器學習算法，利于決策樹、神經網絡等，算法的訓練是模型構建的必須步驟，通過訓練算法，獲得模型的參數，然后對需要預測的數據進行分析。但在k鄰近算法中，卻不需要進行預先的訓練。

3）實施kNN算法：根據k鄰近算法的原理，先計算樣本數據與當前數據的特征之間的距離，隨后對所有計算出的距離遞增排序，選取前k個距離最小的樣本點，統計前k個樣本點中所在類別的頻率，并將出現頻率最高的樣本點對應的分類作為當前數據的分類。

4）算法測試：由于所有的算法都不是百分之百完美的，預測的結果可能與真實值存在一定的偏差。在使用k鄰近算法構建分類器之后需要對該分類器的性能進行評估。在測試的過程中，為了客觀的評估k鄰近算法的正確率，文中選取已有數據的90%來訓練模型生成分類器，用剩下的10%數據作為測試樣本來測試分類器的正確率。在選取過程中，注意數據的隨機性即可。

1.2 系統框架設計

通過參考相關文獻，并結合本系統的實際需求，建立如圖2所示的手寫識別系統。具體包括通過手寫板或者觸摸屏進行數據的采集，然后通過數據的預處理將數據進行歸一化抽取相關的特征，根據由k-鄰近算法生成的識別字典進行特征匹配，最后輸出識別結果。

圖2 手寫識別系統原理框圖

1）預處理：在進行手寫字符的識別之前，系統需要先對輸入到手寫版或者觸摸屏的文字進行預處理。在預處理的第一階段，需要做的是對手寫版或者觸摸屏上筆的位置檢測錯來，并化作x，y坐標輸入計算機，通過A/D轉換技術，化成數字信號進行處理。得到的坐標由于含有干擾和噪聲需要進行平滑、去噪與插入處理。噪聲、干擾往往是由人在輸入時手部的抖動、感應噪聲等造成，不可避免。因此預處理階段十分重要，是手寫字符識別的基礎。

2）特征提取：在機器學習的系統中特征工程中，特征的提取是核心步驟之一。對于樣本的特征提取可以分為兩個類別，分別是結構特征與統計特征。關于結構特征：手寫字符的結構性很強，表達信息豐富。在進行結構特征提取時，本文采用自底向上的方法，由預處理后的像素開始，得到筆段，再用筆段合成筆畫，用筆畫生成字根，用字根識別手寫字符。結構特征的提取對于用戶按筆畫輸入的字符優勢十分明顯。關于統計特征：統計特征是指字符輸入的輪廓、邊緣信息以及水平、豎直、對角、反對角等特征信息。按照統計特征進行特征提取是將字符識別視作模式識別問題，用機器學習的思想通過對象特征學習、經驗積累多次訓練計算機，再應用于字符的識別。統計特征又分為全局特征與局部特征，良好的特征工程可以大大提高算法的精確度，提高識別準確率。

3）特征匹配：特征匹配是特征提取的目的所在。通過測試樣本與學習樣本之間的特征匹配，可以得到測試樣本的分類。針對結構特征的匹配取采用結構特征匹配的方法，結構特征的匹配需要將提取出的輸入信息與標準模板中的信息進行比對，找到最相似的字體完成識別。在當前的手寫識別系統中，常常采用按照筆劃順序輸入一筆識別一筆的方法，完成結構特征的識別。統計特征匹配對應于統計特征提取。在本文中采取k-鄰近算法計算提取出的特征與樣本特征的距離，進行分類判決。距離度量采用歐式距離，以簡化特征工程與模板建立，同時可以提高模型的抗干擾能力。其他常用的算法還有支持向量機與人工神經網絡。

2 系統實現與仿真

文中描述的手寫識別系統采用Python語言實現，Python版本為2.7，開發環境選擇Windows7下的Spyder。Python語言具有結構清晰、易于操作文本文件等優點，在開發中有非常豐富的開發文檔，針對機器學習，Python中集成了現在最流行的SciPy、NumPy等科學計算庫，在數據可視化上，有Matplotlib用于2D、3D圖形的繪制。同時，Python還提供了shell交互環境，為用戶在開發過程中的查看與檢測程序提供便利。

2.1 算法實現

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

第一步是導入系統所需的相關模塊，第一個是科學計算包numpy，第二個是運算符operator。

在數據預處理中包括兩個函數，一個是將文本記錄轉化為Numpy庫可以處理的矩陣的file2matrix函數，一個是將圖像格式化處理的img2vector函數，其中img2vector函數可以將從手寫板獲取的32*32的二進制圖像轉化為1*1024的向量，系統選取的學習樣本如圖3所示。

圖3 學習樣本

數據的預處理還包括歸一化函數autoNorm，采取的歸一化公式如下：

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

Classfy0中輸入4個參數，其中inX是用于分類的向量，dataSet是訓練所需的樣本數據，labels是每個訓練樣本對應的標簽，k表適用于選擇最近鄰居的數目。在特征距離的計算上，采用歐式距離：

文中用提供的數據集進行模型的訓練，并選取剩下的10%進行測試，算法的錯誤率為1.2%，在算法中更改模型的參數k，更改隨機選取的樣本與測試樣本的數目都會對錯誤率造成影響，本文經多次調整參數進行優化，獲得較優值。

2.2 算法測試

文中在測試時，從網上截取了一段200字的新聞稿，在文稿的選取上，文中特意關注了字符的多樣性，在本段文字中，包括文字、標點、數字等多種符號。然后選擇了10名用戶對該段文字進行手寫輸入，新聞稿與用戶的輸入數據分別如圖4、圖5所示。

圖4 新聞稿數據

圖6為系統對用戶書寫樣本的識別情況，在編輯區域可以清晰地看到用戶的筆跡與系統的識別結果。其中黑色的為系統的首先字符，淺灰色的為二選字符，在k鄰近算法判別二選字符與首選字符類別判別模糊時，本系統為用戶提供第二接近的字符，供用戶判別。通過計算機智能自動識別與人工識別相結合的方式，提高手寫字符的準確率。經過十個用戶的輸入數據的測試，本系統的首選加二選識別準確率達到95%以上。

圖5 測試輸入手寫字符

圖6 手寫樣本識別

3 結束語

文中介紹了一種基于k鄰近算法實現的手寫字符的識別系統。通過采用k鄰近算法，將用戶手寫的輸入字符數據與樣本集合中的每一個數據特征一一比較，然后提取前k個與該數據最相似的特征對應的樣本標簽返回識別結果。經測試，本識別系統有較高的識別正確率，可以廣泛應用在未來的手寫輸入系統中。

參考文獻：

[1]曾紀川.基于安卓的篇章級手寫識別輸入法[D].哈爾濱：哈爾濱工業大學，2013.

[2]王曉龍，關毅.計算機自然語言處理[M].北京:清華大學出版社，2005.

[3]孫家廣.計算機圖形學[M].北京:清華大學出版社，1998.

[4]王秋生，孫圣和，鄭為民.數字音頻信號的脆弱水印嵌入算法[J].計算機學報，2002，25（5）:1-6.

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

[6]房秉毅，張云勇，程瑩，等.云計算國內外發展現狀分析[J].電信科學，2010，26（8）:1-6.

[7]羅軍舟，金嘉暉，宋愛波，等.云計算:體系架構與關鍵技術[J].通信學報，2011，32（7）:3-21.

[8]陳康，鄭緯民.云計算:系統實例與研究現狀[J].軟件學報，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].電信科學，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]孫志軍，薛磊，許陽明，等.深度學習研究綜述[J].計算機應用研究，2012，29（8）:2806-2810.

[13]黃凱奇，任偉強，譚鐵牛.圖像物體分類與檢測算法綜述[J].計算機學報，2014，37（6）:1225-1240.

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

[15]王森，楊克儉.基于雙線性插值的圖像縮放算法的研究與實現[J].自動化技術與應用，2008，27（7）:44-45.

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

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

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