基于并行組合分類器的脫機手寫體數字識別

楚浩宇，高 萌，劉永生

(東北農業大學 電氣與信息學院，黑龍江 哈爾濱 150030)

0 引 言

手寫體數字識別是光學字符識別的一個重要分支，分為聯機手寫體數字識別和脫機手寫體數字識別。在聯機手寫體數字識別中，計算機可以通過與之相連的輸入設備得到關于筆尖運動軌跡和速度的有效信息，所以識別相對較易[1]。由于數字圖像的數據量龐大且書寫風格的迥異等干擾因素對識別會產生很大的影響，因此脫機手寫體數字識別難度較大，但其應用領域更加寬泛。因此這是一項意義重大的研究課題。

鑒于傳統的單一分類器對數字之間差異的敏感性不同，許多學者開始研究組合分類器所產生的效果[2]。文獻[3]使用四種特征和三種傳統分類器構造了九種不同的分類器進行組合。文獻[4]構造了兩級的組合分類器，第一級是最小距離分類器，第二級由三個反向傳播網絡并聯而成。文獻[5]提出了一種基于量子神經網絡的二級識別系統。這些方法雖然在一定程度上提高了識別率與可靠性，但分類器的組合結構卻十分復雜，因此識別速度隨之下降。

文中提出使用一種特征、三種分類器、并行結構組織的組合分類器，與傳統方法相比，在提高識別率與可靠性的同時,極大地減少了算法的時間復雜度。

1 手寫體數字識別的基本原理

手寫體數字識別一般包括圖像預處理、特征提取、分類識別等模塊[6]，其結構如圖1所示。

圖1 數字識別的步驟

1.1 圖像的預處理

預處理的主要目的是去除字符圖像中的噪聲，并采用灰度化方法處理讀入的圖像，圖像中的每個像素就對應唯一一個灰度值,得到規范化的點陣，為識別做好準備[7]。

1.2 特征提取

數字圖像用元素為灰度值的矩陣表示，直接用維數很高的矩陣進行計算無論是時間復雜度還是空間復雜度都很大，因此需要進行特征提取。一般對預處理后的圖像進行統計特征提取，常用的有主成分分析、獨立成分分析和Fisher線性鑒別分析[8]。

1.3 識別方法

分類器主要分為基于概率分布的分類器，例如邏輯回歸分類器[9]；基于距離的分類器，例如最近鄰分類器[10]; 人工神經網絡分類器，例如BP神經網絡分類器；支持向量機分類器[11]。 近年來，也有學者提出應用分類識別的伯努利隱馬爾可夫模型與基于活動圖的半監督學習模型[12-13]。

2 并行結構組合分類器的設計

為了能夠從不同的角度觀察不同數字之間變化的規律，綜合考慮各種單一分類器的優缺點，同時不能由于結構太過復雜化而導致訓練分類器的時間和綜合決策時間過長。對此，文中采用K-近鄰算法、廣義回歸神經網絡及支持向量機，提出一種基于改進的投票機制的并行組合分類器，實現脫機手寫體數字的快速、高效識別。

2.1 單一分類器的分類原理

2.1.1 K-近鄰(KNN)分類器

2.1.2 廣義回歸神經網絡(GRNN)分類器

廣義回歸神經網絡是徑向基神經網絡的一種[14]。假設隨機變量x和隨機變量y的聯合概率密函數為f(x,y)。設X是隨機變量x的測量值，則y在給定X下的條件均值為：

(1)

(2)

其中，n為樣本觀測值的個數；p為隨機變量x的維數；σ為高斯函數的寬度系數。

(3)

2.1.3 支持向量機(SVM)分類器

支持向量機是一種建立在統計學習理論的VC維理論和結構風險最小原理基礎上的模式識別方法。支持向量機的主要思想是通過某種事先選擇的非線性映射將輸入向量x映射到高維特征空間，在這個空間中構造最優分類超平面[11]。

對于給定的訓練集(x(i),y(i)),為了尋找最優分類超平面，支持向量機需要求解以下二次規劃問題:

0≤αi≤C,i=1,2,…,m

(4)

其中,m為訓練樣本數;αi為拉格朗日乘子；C為懲罰系數；(x(i),x(j))為核函數。

給定測試數據x,通過式(5)的值來確定標簽y。

(5)

2.2 組合分類器的工作原理及流程

2.2.1 改進的投票機制

分類器識別狀況的權值矩陣為：

(6)

其中，wij為第i+1個分類器在識別數字j時設定的權值。

權值矩陣中每個元素的取值為：

(7)

其中，ω為該分類器的預設定權值；c為該分類器的識別結果。

在識別數字時的判定依據為：

(8)

給定拒識閾值t,若滿足Rj

2.2.2 工作流程

三個分類器，即KNN分類器、GRNN分類器、SVM分類器分別簡稱為C1、C2、C3。

(1)C1、C2、C3分別在訓練集中進行學習并進行參數尋優，得出各分類器的參數；

(2)將各分類器的識別結果與測試集中的結果進行比對，根據正確率排出各分類器的可信度的排名；

(3)收集C1、C2、C3識別數字的結果，設定矩陣中各元素的取值范圍；

(9)

(10)

(11)

(4)列出三行十列的混淆矩陣;

(12)

(5)根據式(13)計算Rj的值；

(13)

(6)根據各分類器的可靠性預設拒識閾值t=2.5，若滿足Rj<2.5拒絕識別，否則輸出識別的數字。

3 實 驗

3.1 數據來源

文中應用的實驗數據來源于MNIST數據庫，這是一個廣泛使用于各種圖像處理系統和機器學習領域的大型手寫體數字數據庫。該數據庫包含了6萬組訓練圖片和1萬組測試圖片，其中每張圖片已經經過預處理壓縮至784(28*28)像素[15]。特征矩陣即是由灰度值作為元素的28*28維矩陣。圖2是MNIST數據庫中的部分訓練數據。

圖2 MNIST訓練集的部分數據

3.2 性能指標

分類器的水平由性能指標來評價，主要的性能指標如下：

(1)識別率(recognition rate)。

Recognition Rate=

100%

(14)

(2)誤識率(false accept rate)。

False Accept Rate=

(15)

(3)可靠性(reliability)。

Reliability=

(16)

(4)拒識率(rejection rate)。

多數情況下，在輸入待測樣本之后，分類器會給出對應數字的分類結果。但是對于某些特定領域，分類結果發生錯誤可能會帶來極其嚴重的后果,因此需要對沒有把握的樣本拒絕識別,由此降低誤識率，提高可靠性。

RejectionRate=

100%

(17)

3.3 實驗結果及分析

評價一個分類器性能的優劣主要看其是否具有低誤識率、低拒識率和高識別率、高可靠性。實驗結果如表1所示。

表1 分類器性能對比實驗結果 %

比較表1中單一分類器和組合分類器的結果，單一分類器的拒識率這一指標全部為0。組合分類器由于有些數字樣本因手寫不謹慎而與別的數字產生混淆的原因，才拒絕識別了這一小部分樣本，所以組合分類器存在單一分類器所沒有的“噪音”過濾功能。從表1中可以看出，并行組合分類器的誤識率要比單一分類器低0.45%～2.38%，而且可靠性要高于單一分類器0.5%～2.43%，所以其魯棒性優于單一分類器。

文中提出的并行組合分類器在識別率、拒識率、識別算法的時間復雜度上均優于文獻[3-5]中所采用的組合分類器。由于文中選取了識別率較高的單一分類器、改進了傳統的投票機制，這使得只有極少測試樣本會因同時在各種分類器中識別不佳導致權值之和達不到預設的閾值而被拒識，因此組合分類器具有高識別率、低拒識率。

文獻[3]需要事先訓練九種分類器再進行組合判斷；文獻[4]中組合分類器第二級采用了三個并聯BP神經網絡，雖然BP神經網絡在數學上已經被證明具有實現任何復雜非線性映射的功能，但收斂速度十分緩慢；文獻[5]使用的QNNs多級分類器包含十四個子網絡；而文中采用的三個單一分類器均具有較快的訓練速度且并行組合分類器的結構簡單，因此在識別算法的時間復雜度上小于以上文獻的同時，又取得了高識別率、低拒識率。

并行組合分類器在誤識率和可靠性方面高于文獻[4-5]，較之文獻[3]略低。考慮到文獻[3]中九個組合分類器極大地增加了訓練時間和綜合決策時間，而且其較高的拒識率也在一定程度上減少了誤識率、增加了可靠性，而文中提出的并行組合分類器在犧牲較少時間，拒識較少樣本的情況下與其只有不到0.1%的差距，所以并行組合分類器在總體性能上要優于其他組合分類器。

4 結束語

提出了一種并行結構的組合分類器，通過改進的投票機制得出最終的結果，實驗結果表明，對單一分類器進行組合，在保證了低誤識率、低拒識率、高識別率、高可靠性的前提下，利用簡易結構即可實現脫機手寫體數字的快速、高效識別。組合分類器的魯棒性比單一分類器的要強，而且組合分類器有著較強的靈活性和可拓展性，找到更好的組織結構以及判斷機制將是今后研究的重點。手寫體數字識別是字符識別中的一個研究方向，提出的組合分類器起到了拋磚引玉的作用，絕不只是應用于數字識別，稍加改變，便可應用于其他字符識別。

[1] KHERALLAH M,HADDAD L,ALIMI A M,et al.On-line handwritten digit recognition based on trajectory and velocity modeling[J].Pattern Recognition Letters,2008,29(5):580-594.

[2] 柳回春,馬樹元,吳平東,等.手寫體數字識別技術的研究[J].計算機工程,2003,29(4):24-25.

[3] 胡鐘山,婁 震,楊靜宇,等.基于多分類器組合的手寫體數字識別[J].計算機學報,1999,22(4):369-374.

[4] 傅德勝,謝忠紅,蘇 堅.基于組合分類器的自由手寫體數字識別方法[J].計算機工程與設計,2004,25(10):1713-1715.

[5] 吳茹石,彭 力.基于量子神經網絡的手寫體數字識別方法研究[J].計算機工程與設計,2007,28(18):4462-4465.

[6] 朱小燕,史一凡,馬少平.手寫體字符識別研究[J].模式識別與人工智能,2000,13(2):174-180.

[7] 張 猛,余仲秋,姚紹文.手寫體數字識別中圖像預處理的研究[J].微計算機信息,2006,22(6-1):256-258.

[8] 楊 健,楊靜宇,葉 暉.Fisher線性鑒別分析的理論研究及其應用[J].自動化學報,2003,29(4):481-493.

[9] BISHOP C M.Pattern recognition and machine learning[M].New York:Springer-Verlag,2006:205-206.

[10] 劉家峰,趙 巍,朱海龍,等.模式識別[M].哈爾濱:哈爾濱工業大學出版社,2014:15-17.

[11] VAPNIK V N.The nature of statistical learning theory[M].New York:Springer-Verlag,2000:133-141.

[12] GIMERNEZ A,ANDRES-FERRER J,JUAN A.Discriminative Bernoulli HMMs for isolated handwritten word[J].Pattern Recognition Letters,2014,35:157-168.

[13] CECOTTI H.Active graph based semi-supervised learning using image matching:application to handwritten digit recognition[J].Pattern Recognition Letters,2016,73:76-82.

[14] SPECHT D F.A general regression neural network[J].IEEE Transactions on Neural Networks,1991,2(6):568-576.

[15] LECUN Y,BOTTOU L,BENGIO Y,et al.Gradient-based learning applied to document recognition[J].Proceedings of the IEEE,1998,86(11):2278-2324.