三枝粗糙集和變粒度原理的手寫體漢字識別

王建平，王夢澤

合肥工業大學電氣工程及自動化學院，合肥 230009

三枝粗糙集和變粒度原理的手寫體漢字識別

王建平，王夢澤

合肥工業大學電氣工程及自動化學院，合肥 230009

手寫體漢字識別是超多類模式識別問題，被公認為是模式識別領域中難題之一。粗糙集理論已經成功地運用到手寫體漢字識別的研究中，但是仍然存在諸多的不完善，本文利用三枝粗糙集原理解決如何建立較完備穩定的特征表示和提取方法，以及處理不確定、不精確和不完全性特征信息的識別決策機制[1]。

粗糙集理論于1982年由波蘭科學家Pawlak提出，它是一種研究不確定、不完整知識和數據的表達、學習、歸納的理論方法[2]。將粗糙集理論用于手寫體漢字識別，建立特定空間上的等價關系分類機制，構成了對手寫體漢字識別是超多類模式識別該空間的劃分，并將真實屬性知識理解為對手寫體漢字識別超多類模式數據的劃分，每一被劃分的集合稱為概念。

在變精度粗糙集模型中，閾值參數由專家給定，沒有語義解釋，而基于三枝粗糙集理論的決策粗糙集模型不僅給予了概率粗糙集模型一種基于貝葉斯最小風險下的語義解釋[3-5]，而且閾值參數可以直接計算得出，針對這一情況，本文研究基于三枝粗糙集原理，構建期望風險最小決策的語義下決策粗集理論基本模型的過程。

引入粒度原理，從屬性重要度的角度出發，結合信息粒度的邏輯運算，形成凝聚式的自下而上的信息粒網的構建，形成決策信息系統特征約簡集的粒度網結構，最終構成由特征屬性和決策屬性組成的決策系統。

1 脫機手寫體漢字識別決策信息系統

1.1 手寫體漢字識別信息系統

根據粗糙集理論對廣義論域信息系統的定義[6-7]，對脫機手寫體漢字識別信息系統可作如下定義。

1.2 三枝粗糙集的漢字識別決策信息系統

模仿人類有導師的學習識字過程，將手寫體漢字的真實值D=d作為先驗知識加入到脫機手寫體漢字識別系統S=(U,A,V,f)中來指導訓練過程中的決策。

定義2設手寫體漢字識別信息系統S=(U,A,V,f)，若A中的屬性可分為兩個不相交的子集，即A=C∪D，C∩D=?，其中C={C1,C2,…,Cn}為條件屬性集，即所提取的手寫體漢字樣本特征集；D=g0gggggg為決策屬性集，即樣本漢字的真是屬性。記其中RC表示特征屬性集C中所有特征值相同的漢字樣本組成的等價類，Rd表示真實值相同的漢字樣本組成的等價類，這兩種等價類分別對手寫體漢字樣本集U進行了劃分。若RC?Rd，即特征屬性對樣本漢字的劃分細于真實屬性對樣本漢字的劃分，即所選特征足以將樣本漢字正確分類，則S=(U,A,V,f)稱為脫機手寫體漢字識別決策信息系統。

定義3P(Rd|Rc)為手寫體漢字特征屬性集Rc關于漢字真實屬性集Rd的相對正確分類率；設λ=(ai|Rd)為當手寫體漢字樣本的真實值為Rd時采取動作a的損失函數，則該動作所帶來的預期可表示為：

該決策過程的實際意義是，當采取某種動作所帶來的風險不超過其他兩種動作所帶來的風險時，就采取該動作，對于決策代價函數值的大小，根據上述條件，決策規則可重新定義為：

當β=0和α=1時，上述模型將轉化為pawlak粗集模型。當β=α=0.5時，上述模型轉換為0.5概率粗集模型。一般不要超過兩行。

1.3 決策信息系統約簡

定義概率粗糙集模型的屬性約簡[9-10]，假設決定一個信息表，S=(U,A,V,f)，一個屬性集B?C是C關于D的一個約簡；定義概率粗糙集模型的屬性約簡它滿足如下兩個條件：

（S）性質保留性：

2 粒度原理的手寫漢字特征屬性定義

2.1 幾個性能指標熵的定義

其中，I(D|B(α,β))表示手寫體漢字樣本特征屬性子集B(α,β)確定后脫機手寫體漢字識別決策信息系統所殘留的平均信息量，殘留的不確定性，I(D|B(α,β))越小，說明D與B(α,β)相關性越大，識別錯誤率越小。

2.2 手寫體漢字特征屬性重要度的定義

3 利用屬性及重要度構建多粒度結構

3.1 粒的內部結構、粒集的組織結構

粒的內部結構表示為：G(A,W,Gp,Gc)；其中G為一個粒，A為粒的屬性集，W為屬性重要度集，Gp為該粒的父粒集，Gc為該粒的子粒集，A按照屬性重要度遞減的順序排列。粒的相似性分為兩種[12-13]。

3.2 粒的計算

3.3 粒度網的構建

從特征屬性重要度的角度出發，研究設計了一種基于特征屬性重要度的自下而上的粒度網的構建策略[13]，該算法按照特征屬性重要度遞減的順序構建，并結合粒度之間的并、交、差運算，使系統可以更好獲取信息，使得每層的粒度適用度逐層變大。分裂式粒度網構建流程圖。

圖1 N層特征遞階約簡示意圖

步驟1根據已有漢字特征屬性及其權重進行分組，把屬性及其權重完全相似的特殊應用合并，基本相似的特殊應用分為一組，構成不同分組，分組內進行交運算，父粒形成倒數第2層，剩余屬性形成最底層粒。并將此層與決策屬性的并集進行約簡。如果約簡后決策屬性唯一則直接輸出匹配規則，如果不唯一，則繼續建立下一層決策系統。

步驟2對所有漢字特征屬性與其有父子聯系的倒數第2層粒進行差運算，把特殊應用的剩余屬性根據屬性及其權重分組，把屬性及其權重完全相似的特殊應用合并，基本相似的特殊應用分為一組，構成不同分組，分組內進行交運算，父粒形成倒數第4層。重復上述驟。

步驟3…N：以此類推逐漸形成領域適用粒度逐漸變大的層次多粒度樹。具體算法如下：

算法1基于特征屬性相對重要度的分層遞階約簡算法。

輸入：手寫體漢字識別決策信息系統S=(U,C∪D,V,f)，其中U={x1,x2,…,xn}為待訓練手寫體漢字樣本集；C={c1,c2,…,cn}為所提取的手寫體漢字樣本特征集，即條件屬性；D=g0gggggg為漢字的真實值，即決策屬性集。

輸出：屬性約簡集B和識別規則。

（1）屬性分層

①由公式分別計算手寫體漢字決策信息系統的相對粒度熵I(D/{ci}),i=1,2,…,n。

②令Bβ為使I(D/{ci})最大的特征屬性，對ci∈{C-Bβ}分別按照定義8計算SGF(ci,Bβ,D)并按遞減順序排列。

③按照屬性重要度排序的順序，依次將每2個相鄰權重的屬性記作一個粒G1，如{G1,G2,…,Gn}，再根據相似性定義計算每2個粒的特征屬性重要度及屬性的相似程度，分別進行并，交，差運算，記作：AGi，i={1,2,…,n}形成一個自下而上的，粒度逐漸變細的粒度網結構。

（2）第一層決策系統

圖1由邏輯運算得到的第n層與決策屬性d構成的第一層決策系統，記作：(AG1,d)；對首層決策系統進行約簡，得到其簡約，如果輸出結果唯一就停止運算。如果輸出不唯一，繼續進行下一步。

（3）次層決策系統

圖1所示，邏輯運算得到的第n-1層與決策屬性d的構成次層決策系統，記作：(AG2,d)；步驟如上所示。

（4）當屬性重要度已分配到最底層，無法向下進時，算法停止。

4 識別規則的融合算法

脫機手寫體漢字識別決策信息系統經過手寫體漢字特征屬性約簡以及適當的屬性值約簡之后，從而得到“if…then…”形式的脫機手寫體漢字識別決策規則集。只要找到匹配的條件就可以得到與之相對應的結論，即漢字真實屬性，從而完成粗糙集理論下的脫機手寫體漢字識別過程。

然而，約簡后的手寫體漢字特征屬性集中的元素取值會出現沒有或者有多條識別規則的條件匹配的情況，這時就要解決規則匹配的問題。選用適當的規則融合理論，以解決決策規則不能唯一匹配的問題。

5 實驗結果與仿真

為了驗證文中方法的有效性，選取SCUT-IRAC手寫體漢字圖像樣本數據庫，采用文獻[14]特征提取方法，其中選取“中”和“燮”這兩個字仿真實驗如下。

（1）“中”計算決策風險最小時的閾值β1，實驗過程中計算得到9維屬性約簡集Bβ1的向量為{1，0，0，0，1，0，1，1，1}，以及特征屬性重要度的順序{C1,C2,…,Cn}，根據本文定義的粒之間邏輯關系得出決策系統為：AG={(AG1,d),(AG2,d),…,(AGn,d)}，約簡得到對應決策規則為：{a0(1)，a1(0)，a2(0)，a3(0)，a4(1)，a5(0)，a6(1)，a7(1)，a8(1)}=＞D(1)，輸出D(1,β1)，識別正確。

（2）“程”計算決策風險最小時的閾值β2，實驗過程中得到9維屬性約簡集Bβ2的向量為{1，0，0，1，1，1，1，0，2}，以及特征屬性重要度的順序{C1,C2,…,Cn}，根據本文定義的粒之間邏輯關系的決策系統為：AG={(AG1,d),(AG2,d),…,(AGn,d)}，約簡得到對應決策規則為：{a0(1)，a1(0)，a2(0)，a3(1)，a4(1)，a5(1)，a6(1)，a7(0)，a8(2)}=＞D(2)，輸出D(2,β2)，識別正確。

再次選取SCUT-IRAC手寫體漢字圖像樣本數據庫中“大、目、自、跟、根、鶩、騖”這樣的簡單字、中等復雜字、復雜字、一對簡單相似字和一對復雜相似字進行了實驗。實驗軟件采用Rosetta和Matlab平臺下開發的相關算法。其中每個漢字50個樣本，分為訓練集（90%）和測試集（10%），獲得128維特征向量，利用Rosetta和Matlab環境開發相關算法，實現對訓練集315個漢字樣本的訓練以及對測試集35個漢字樣本的識別。實驗結果如表1、表2所示。

表1 所選樣本漢字實驗結果

表2 實驗結果統計

由上表可以看出，本文所研究的識別方法對35個手寫體漢字測試樣本的總體識別率為91.43%，誤識率為8.57%，拒識率0。通過分析可發現，本系統對復雜相似字的識別準確率低于對簡單相似字的識別準確率，這是由于采集的樣本間的書寫差異較大和所提取的漢字樣本特征屬性不夠精細等多方面原因造成的，此外，采用分層變粒度的識別決策方法，有助于降低漢字識別的拒識率，提高正確識別率。

6 結束語

三枝決策是基于粗糙集的正域、邊界域和負域以及假設驗證提出的，它可以用來解釋生活中的很多決策現象。領域多粒度網的構建策略，使問題的某些關鍵的性質必須在不同粒度上體現出來，通過粒運算證實滿足粒化準則。為提高脫機手寫體漢字識別的識別率和識別速度，本文利用三枝粗糙集理論和變粒度原理對脫機手寫體漢字識別系統進行了研究。主要工作如下：

（1）從貝葉斯理論出發，基于三枝決策粗集理論，構建期望風險最小決策的語義下決策粗集理論。

（2）定義了脫機手寫體漢字識別決策信息系統特征屬性約簡的幾個性能指標熵，以及特征屬性相對重要度指標，從屬性重要度角度出發，對粒與粒之間進行邏輯運算，形成凝聚式的自上而下的信息粒網的構建策略，形成此領域適用粒度逐漸變小的層次多粒度網結構，建立相應的特征屬性集達到最優的決策表。提高了信息利用率，更好地獲取信息，提高了約簡精度。

[1]封筠，王先梅.脫機手寫體漢字識別技術研究的回顧與展望[J].微型電腦應用，2003（4）.

[2]Pawlak Z.Rough sets[J].International Journal of information and Computer Science，1982，11（5）：341-356.

[3]Yao Y Y.Three-way decisions with probabilistic rough sets[J].Information Sciences，2010，180：341-353.

[4]Yao Y Y.Two semantic issues in a probabilistic rough set model[J].Fundament a Informaticae，Manuscript，2009.

[5]Yao Y Y.Three-way decision：an interpretation of rules in rough set theory[J].LNAI，2009（5589）：642-649.

[6]張文修，仇國芳.基于粗糙集的不確定決策[M].北京：清華大學出版社，2005.

[7]菅利榮.面向不確定性決策的雜合粗糙集方法及其應用[M].北京：科學出版社，2008.

[8]胡卉穎，羅錦坤，劉阿寧.三枝決策粗糙集模型屬性約簡研究[J].軟件導刊，2012（2）.

[9]耿志強，朱群雄，李芳.知識粗糙性的粒度原理及其約簡[J].系統工程與電子技術，2004，26（8）：1112-1116.

[10]賈修一，李偉湋，商琳，等.一種自適應求三枝決策中決策閾值的算法[J].電子學報，2011（11）.

[11]Wang J P，Chen K Q.A study of off-line handwritten Chinese character recognition with optimized decision and iteration based on rough set and the granular theorem[J].Advanced Materials Research，2012：1715-1722.

[12]費雅潔.基于粗集理論的本體屬性動態加權法研究[J].微計算機信息，2009，27：209-210.

[13]費雅潔，趙琦，許泓寧.一種領域多粒度網的動態構建策略[J].微計算機信息，2011（12）.

[14]吳佑壽，丁曉青.漢字識別－原理方法與實現[M].北京：高等教育出版社，1992：154-171.

WANG Jianping,WANG Mengze

School of Electric Engineering and Automation,Hefei University of Technology,Hefei 230009,China

The model of the theory of three-way decision-theoretic rough sets is used for the recognition of handwritten Chinese characters.A model of the theory of three-way decision-theoretic rough sets is set up which the regional classification is based on positive,negative and boundary.It can better reflect the recognition of handwritten Chinese characters classification on approximation.And define characteristic attribute of reduction of relative granularity entropy and the significance of attribute in offline handwritten Chinese characters recognition decision information system.If consider the recognition of handwritten Chinese characters from the point of view of the importance of attribute,it can design a kind of bottom up particle network structure based on logical operation between grain and grain,you can obtain more effective information.Simulation results show that,the method is feasible and effective.

rough set;three-way decision making;risk of loss;attribute reduction;vary granularity

將三枝決策粗糙集模型用于手寫體漢字識別，建立三枝決策粗糙集模型，其區域分類以正、負和邊界為基礎，更好地體現手寫體漢字識別分類近似性。定義了脫機手寫體漢字識別決策信息系統特征屬性約簡相對粒度熵和屬性重要度，將手寫體漢字識別從屬性重要度的角度出發，設計一種基于粒與粒之間邏輯運算的自下而上的粒度網結構，使手寫體漢字識別屬性集的適用粒度逐漸變大，可以獲取更多的有效信息。仿真實驗表明，該方法是可行有效的。

粗糙集；三枝決策；風險損失；決策約簡；粒度分層

A

TP391.12

10.3778/j.issn.1002-8331.1301-0176

WANG Jianping,WANG Mengze.Study of handwritten Chinese characters recognition based on three branches rough sets and variable granularity principle.Computer Engineering and Applications,2014,50（22）：223-227.

王建平（1955—），男，博士，教授，主研領域：數字化監控、圖像識別、檢測技術；王夢澤（1987—），女，碩士研究生，主研領域：自動檢測技術。E-mail：wangww@mail.hf.ah.cn

2013-01-16

2013-03-14

1002-8331（2014）22-0223-05

CNKI網絡優先出版：2013-03-26,http://www.cnki.net/kcms/detail/11.2127.TP.20130326.1040.009.html

◎工程與應用◎