王建平，王夢澤

合肥工業(yè)大學(xué)電氣工程及自動化學(xué)院，合肥 230009

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

王建平，王夢澤

合肥工業(yè)大學(xué)電氣工程及自動化學(xué)院，合肥 230009

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

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

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

引入粒度原理，從屬性重要度的角度出發(fā)，結(jié)合信息粒度的邏輯運算，形成凝聚式的自下而上的信息粒網(wǎng)的構(gòu)建，形成決策信息系統(tǒng)特征約簡集的粒度網(wǎng)結(jié)構(gòu)，最終構(gòu)成由特征屬性和決策屬性組成的決策系統(tǒng)。

1 脫機手寫體漢字識別決策信息系統(tǒng)

1.1 手寫體漢字識別信息系統(tǒng)

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

1.2 三枝粗糙集的漢字識別決策信息系統(tǒng)

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

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

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

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

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

1.3 決策信息系統(tǒng)約簡

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

（S）性質(zhì)保留性：

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

2.1 幾個性能指標熵的定義

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

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

3 利用屬性及重要度構(gòu)建多粒度結(jié)構(gòu)

3.1 粒的內(nèi)部結(jié)構(gòu)、粒集的組織結(jié)構(gòu)

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

3.2 粒的計算

3.3 粒度網(wǎng)的構(gòu)建

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

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

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

步驟2對所有漢字特征屬性與其有父子聯(lián)系的倒數(shù)第2層粒進行差運算，把特殊應(yīng)用的剩余屬性根據(jù)屬性及其權(quán)重分組，把屬性及其權(quán)重完全相似的特殊應(yīng)用合并，基本相似的特殊應(yīng)用分為一組，構(gòu)成不同分組，分組內(nèi)進行交運算，父粒形成倒數(shù)第4層。重復(fù)上述驟。

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

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

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

輸出：屬性約簡集B和識別規(guī)則。

（1）屬性分層

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

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

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

（2）第一層決策系統(tǒng)

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

（3）次層決策系統(tǒng)

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

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

4 識別規(guī)則的融合算法

脫機手寫體漢字識別決策信息系統(tǒng)經(jīng)過手寫體漢字特征屬性約簡以及適當(dāng)?shù)膶傩灾导s簡之后，從而得到“if…then…”形式的脫機手寫體漢字識別決策規(guī)則集。只要找到匹配的條件就可以得到與之相對應(yīng)的結(jié)論，即漢字真實屬性，從而完成粗糙集理論下的脫機手寫體漢字識別過程。

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

5 實驗結(jié)果與仿真

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

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

（2）“程”計算決策風(fēng)險最小時的閾值β2，實驗過程中得到9維屬性約簡集Bβ2的向量為{1，0，0，1，1，1，1，0，2}，以及特征屬性重要度的順序{C1,C2,…,Cn}，根據(jù)本文定義的粒之間邏輯關(guān)系的決策系統(tǒng)為：AG={(AG1,d),(AG2,d),…,(AGn,d)}，約簡得到對應(yīng)決策規(guī)則為：{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手寫體漢字圖像樣本數(shù)據(jù)庫中“大、目、自、跟、根、鶩、騖”這樣的簡單字、中等復(fù)雜字、復(fù)雜字、一對簡單相似字和一對復(fù)雜相似字進行了實驗。實驗軟件采用Rosetta和Matlab平臺下開發(fā)的相關(guān)算法。其中每個漢字50個樣本，分為訓(xùn)練集（90%）和測試集（10%），獲得128維特征向量，利用Rosetta和Matlab環(huán)境開發(fā)相關(guān)算法，實現(xiàn)對訓(xùn)練集315個漢字樣本的訓(xùn)練以及對測試集35個漢字樣本的識別。實驗結(jié)果如表1、表2所示。

表1 所選樣本漢字實驗結(jié)果

表2 實驗結(jié)果統(tǒng)計

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

6 結(jié)束語

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

（1）從貝葉斯理論出發(fā)，基于三枝決策粗集理論，構(gòu)建期望風(fēng)險最小決策的語義下決策粗集理論。

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

[1]封筠，王先梅.脫機手寫體漢字識別技術(shù)研究的回顧與展望[J].微型電腦應(yīng)用，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].北京：清華大學(xué)出版社，2005.

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

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

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

[10]賈修一，李偉湋，商琳，等.一種自適應(yīng)求三枝決策中決策閾值的算法[J].電子學(xué)報，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]費雅潔.基于粗集理論的本體屬性動態(tài)加權(quán)法研究[J].微計算機信息，2009，27：209-210.

[13]費雅潔，趙琦，許泓寧.一種領(lǐng)域多粒度網(wǎng)的動態(tài)構(gòu)建策略[J].微計算機信息，2011（12）.

[14]吳佑壽，丁曉青.漢字識別－原理方法與實現(xiàn)[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

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

粗糙集；三枝決策；風(fēng)險損失；決策約簡；粒度分層

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—），男，博士，教授，主研領(lǐng)域：數(shù)字化監(jiān)控、圖像識別、檢測技術(shù)；王夢澤（1987—），女，碩士研究生，主研領(lǐng)域：自動檢測技術(shù)。E-mail：wangww@mail.hf.ah.cn

2013-01-16

2013-03-14

1002-8331（2014）22-0223-05

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-03-26,http://www.cnki.net/kcms/detail/11.2127.TP.20130326.1040.009.html

◎工程與應(yīng)用◎