三枝粗糙集和變粒度原理的手寫(xiě)體漢字識(shí)別

王建平，王夢(mèng)澤

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

三枝粗糙集和變粒度原理的手寫(xiě)體漢字識(shí)別

王建平，王夢(mèng)澤

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

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

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

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

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

1 脫機(jī)手寫(xiě)體漢字識(shí)別決策信息系統(tǒng)

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

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

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

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

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

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

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

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

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

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

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

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

2.1 幾個(gè)性能指標(biāo)熵的定義

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

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

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為一個(gè)粒，A為粒的屬性集，W為屬性重要度集，Gp為該粒的父粒集，Gc為該粒的子粒集，A按照屬性重要度遞減的順序排列。粒的相似性分為兩種[12-13]。

3.2 粒的計(jì)算

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

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

圖1 N層特征遞階約簡(jiǎn)示意圖

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

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

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

算法1基于特征屬性相對(duì)重要度的分層遞階約簡(jiǎn)算法。

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

輸出：屬性約簡(jiǎn)集B和識(shí)別規(guī)則。

（1）屬性分層

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

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

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

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

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

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

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

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

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

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

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

5 實(shí)驗(yàn)結(jié)果與仿真

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

（1）“中”計(jì)算決策風(fēng)險(xiǎn)最小時(shí)的閾值β1，實(shí)驗(yàn)過(guò)程中計(jì)算得到9維屬性約簡(jiǎn)集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)}，約簡(jiǎn)得到對(duì)應(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)，識(shí)別正確。

（2）“程”計(jì)算決策風(fēng)險(xiǎn)最小時(shí)的閾值β2，實(shí)驗(yàn)過(guò)程中得到9維屬性約簡(jiǎn)集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)}，約簡(jiǎn)得到對(duì)應(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)，識(shí)別正確。

再次選取SCUT-IRAC手寫(xiě)體漢字圖像樣本數(shù)據(jù)庫(kù)中“大、目、自、跟、根、鶩、騖”這樣的簡(jiǎn)單字、中等復(fù)雜字、復(fù)雜字、一對(duì)簡(jiǎn)單相似字和一對(duì)復(fù)雜相似字進(jìn)行了實(shí)驗(yàn)。實(shí)驗(yàn)軟件采用Rosetta和Matlab平臺(tái)下開(kāi)發(fā)的相關(guān)算法。其中每個(gè)漢字50個(gè)樣本，分為訓(xùn)練集（90%）和測(cè)試集（10%），獲得128維特征向量，利用Rosetta和Matlab環(huán)境開(kāi)發(fā)相關(guān)算法，實(shí)現(xiàn)對(duì)訓(xùn)練集315個(gè)漢字樣本的訓(xùn)練以及對(duì)測(cè)試集35個(gè)漢字樣本的識(shí)別。實(shí)驗(yàn)結(jié)果如表1、表2所示。

表1 所選樣本漢字實(shí)驗(yàn)結(jié)果

表2 實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)

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

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

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

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

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

[1]封筠，王先梅.脫機(jī)手寫(xiě)體漢字識(shí)別技術(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]張文修，仇國(guó)芳.基于粗糙集的不確定決策[M].北京：清華大學(xué)出版社，2005.

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

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

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

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

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

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

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

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

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í)別、檢測(cè)技術(shù)；王夢(mèng)澤（1987—），女，碩士研究生，主研領(lǐng)域：自動(dòng)檢測(cè)技術(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)用◎