唐朝輝，陳玉明，吳克壽

廈門(mén)理工學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系，福建 廈門(mén) 361024

基于粗糙集正域的手寫(xiě)字母識(shí)別算法

唐朝輝，陳玉明，吳克壽

廈門(mén)理工學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系，福建 廈門(mén) 361024

1 引言

后PC時(shí)代，大量手持設(shè)備、小型網(wǎng)絡(luò)終端相繼面世，鍵盤(pán)編碼輸入方式越來(lái)越不能滿足客戶的需求，為滿足用戶日益增長(zhǎng)的使用體驗(yàn)和易用性需求，采用手寫(xiě)輸入是未來(lái)的趨勢(shì)；同時(shí)大屏幕設(shè)備的普及，也為手寫(xiě)輸入帶來(lái)了便利。手寫(xiě)識(shí)別技術(shù)是手寫(xiě)輸入可行性的最重要的條件，已經(jīng)成為模式識(shí)別和機(jī)器學(xué)習(xí)的一大熱點(diǎn)，但由于手寫(xiě)習(xí)慣不同、形似字、連寫(xiě)、輸入噪聲等問(wèn)題，給手寫(xiě)識(shí)別帶來(lái)了很大的復(fù)雜性。近幾年機(jī)器學(xué)習(xí)領(lǐng)域?qū)κ謱?xiě)體識(shí)別做了大量研究[1-3]，部分成果取得了較好的應(yīng)用，它們主要基于統(tǒng)計(jì)分析、神經(jīng)網(wǎng)絡(luò)和聚類分析，如支持向量機(jī)（SVM）、誤差反向傳播（Back Propagation，BP）算法、Bagging算法等。

1982年由波蘭數(shù)學(xué)家Pawlak[4]首次提出的粗糙集（rough set）理論是一種處理模糊和不確定知識(shí)的數(shù)學(xué)工具[4-5]，現(xiàn)已經(jīng)被廣泛應(yīng)用于數(shù)據(jù)挖掘、人工智能、模式識(shí)別等諸多領(lǐng)域[6-11]。粗糙集可用于特征選擇，其目的是得到最小的特征子集，但找到所有可行的特征子集已經(jīng)被證明是NP-hard問(wèn)題，所以目前大多數(shù)研究采用啟發(fā)式搜索策略，獲取特征選擇的一個(gè)或多個(gè)可行解，但不一定是最優(yōu)解或所有解。

苗奪謙等人[12]提出了一種基于主曲線的脫機(jī)手寫(xiě)數(shù)字識(shí)別方法，該方法將主曲線及知識(shí)約簡(jiǎn)算法運(yùn)用于識(shí)別模型。本文針對(duì)手寫(xiě)識(shí)別的特點(diǎn)，結(jié)合粗糙集正域，定義了特征重要度概念，并應(yīng)用于手寫(xiě)識(shí)別決策系統(tǒng)約簡(jiǎn)當(dāng)中；同時(shí)提出了基于粗糙集正域的手寫(xiě)字母識(shí)別算法，通過(guò)實(shí)驗(yàn)分析驗(yàn)證了算法的可行性。

2 粗糙集相關(guān)概念

粗糙集理論研究方法基于數(shù)據(jù)分類與知識(shí)的聯(lián)系，并利用集合等價(jià)關(guān)系來(lái)描述數(shù)據(jù)分類[13-15]。為構(gòu)建基于粗糙集的手寫(xiě)字母樣本學(xué)習(xí)和測(cè)試集分類算法，引入以下粗糙集的相關(guān)定義。

定義2給定決策系統(tǒng)T=(U，C∪D，V，f)以及屬性子集B?C，B可以確定一個(gè)二元等價(jià)關(guān)系，記為IND(B)，其中 IND(B)={(x，y)∈U×U|?a∈B，f(x，a)=f(y，a)}。

定義3設(shè)T=(U，C∪D，V，f)為一個(gè)決策系統(tǒng)，?B?C，?X?U，記 U/IND(B)={B1，B2，…，Bi}，則稱 B*(X)=∪{Bi|Bi∈U/IND(B)，Bi∈X}為 X 關(guān)于 B 的下近似集，稱B*(X)=∪{Bi|Bi∈U/IND(B)，Bi∩X≠?}為 X 關(guān)于 B的上近似集。

定義4設(shè)決策系統(tǒng) T=(U，C∪D，V，f)，U/D={D1，D2，…，Di}表示在離散數(shù)據(jù)下決策特征集D對(duì)論域U的等價(jià)劃分，U/IND(C)={C1，C2，…，Ci}表示條件特征集C對(duì)論域U的等價(jià)劃分，稱為C相對(duì)于D的正區(qū)域。

定義5設(shè)決策系統(tǒng)T=(U，C∪D，V，f)，對(duì)b∈B?C，若POSB(D)=POSB-(D)，則相對(duì)于決策特征D來(lái)說(shuō)特征b是不必要的；否則b是必要的。對(duì)?B?C，如果B相對(duì)于決策特征D都是必要的，則稱特征集B獨(dú)立于決策特征D。

定義6設(shè)決策系統(tǒng)T=(U，C∪D，V，f)，若 ?B?C，POSB(D)=POSC(D)且特征集B獨(dú)立于決策特征D，則稱特征集B是條件特征集C相對(duì)于決策特征D的一個(gè)約簡(jiǎn)。

定義7設(shè)決策系統(tǒng) T=(U，C∪D，V，f)，?a∈C，R?C，定義a相對(duì)于R的特征重要度為Sign(a，R，D)= |POSR∪{a}(D)-POSR(D)|。

3 手寫(xiě)樣本采集及分布檢驗(yàn)

為提取手寫(xiě)樣本特征，首先截取手寫(xiě)字母的手寫(xiě)有效區(qū)域，然后定義一個(gè)SegNum×SegNum的等距劃分，將每個(gè)樣本的長(zhǎng)度和寬度SegNum等分，每個(gè)樣本的特征為[1，SegNum×SegNum]的向量。

手寫(xiě)字母采樣策略如下所示：

（1）在可視化界面上用鼠標(biāo)手寫(xiě)字母，同時(shí)給出樣本正確的分類，便于樣本監(jiān)督學(xué)習(xí)。

（2）獲取樣本特征：首先找出手寫(xiě)字母的上、下、左、右邊界，并截取出來(lái)，對(duì)其進(jìn)行二值化，如圖1所示；然后將截取的手寫(xiě)樣本橫向、縱向平均劃分成SegNum×SegNum個(gè)小區(qū)域，計(jì)算每個(gè)小區(qū)域中黑像素所占的比例，如果該值大于所有小區(qū)域中黑點(diǎn)所占比例的平均值，將該值作為[1，SegNum×SegNum]樣本特征向量中對(duì)應(yīng)特征的特征值。

圖1 截取后的手寫(xiě)學(xué)習(xí)樣本

（3）為有效充分地學(xué)習(xí)手寫(xiě)字母樣本并降低時(shí)間復(fù)雜性，樣本數(shù) N應(yīng)該取樣本特征數(shù)的5～10倍，本文為每類分類收集SegNum×SegNum×6個(gè)樣本。

（4）將每個(gè)樣本特征與預(yù)期的手寫(xiě)分類結(jié)果存儲(chǔ)起來(lái)以構(gòu)建手寫(xiě)字母識(shí)別決策系統(tǒng)，便于算法學(xué)習(xí)以提取手寫(xiě)字母分類規(guī)則。

根據(jù)機(jī)器學(xué)習(xí)理論，工程上很多的統(tǒng)計(jì)數(shù)據(jù)都在一定程度上滿足正態(tài)分布。為保證手寫(xiě)樣本具有一定的隨機(jī)性、可靠性，對(duì)樣本的分布做正態(tài)分布假設(shè)檢測(cè)：根據(jù)單個(gè)樣本模式的空間維度較大的特點(diǎn)，為提高分布檢測(cè)的效率，本文采用主成分分析的方法獲取特征空間的主成分，并利用 χ2檢驗(yàn)法對(duì)主成分作正態(tài)分布檢驗(yàn)。

首先假設(shè)手寫(xiě)字母特征符合正態(tài)分布 N(μ，σ2)，μ，σ2未知。采用最大似然估計(jì)對(duì)μ，σ2進(jìn)行點(diǎn)估計(jì)，得：

獲得分布概率密度后，采用 χ2檢驗(yàn)法檢驗(yàn)樣本是否滿足正態(tài)分布。χ2檢驗(yàn)法可以通過(guò)分組數(shù)據(jù)的取值范圍并計(jì)算每個(gè)分組的頻數(shù)來(lái)實(shí)現(xiàn)分布檢驗(yàn)的，其統(tǒng)計(jì)量如公式（2）。

其中N為樣本數(shù)，l為分組數(shù)，ri為實(shí)際頻數(shù)，ti為理論頻數(shù)。

4 基于粗糙集的手寫(xiě)字母樣本學(xué)習(xí)與分類

4.1 樣本學(xué)習(xí)算法

本文使用有監(jiān)督的學(xué)習(xí)算法，首先建立手寫(xiě)字母識(shí)別決策系統(tǒng)，如表1所示。

其中u表示采集的單個(gè)樣本；pi∈{0，1}，表示樣本的單塊劃分范圍內(nèi)是否具有一定數(shù)量的有效像素，ClassExpected∈{a，b，c，…，z}表示單個(gè)樣本的預(yù)期分類，SN表示樣本總數(shù)。

表1 手寫(xiě)識(shí)別決策系統(tǒng)結(jié)構(gòu)

每一行代表一個(gè)輸入樣本的模式，D特征為決策特征，代表該樣本對(duì)應(yīng)的實(shí)際分類。

在手寫(xiě)識(shí)別分類算法中，首先要解決的是兩類分類的問(wèn)題。本文基于粗糙集理論，提出了基于粗糙集正域的手寫(xiě)字母學(xué)習(xí)算法。該算法首先利用粗糙集正域簡(jiǎn)化手寫(xiě)決策系統(tǒng)，然后從簡(jiǎn)化的決策系統(tǒng)中抽取所有兩類分類規(guī)則，并對(duì)獲取的所有分類規(guī)則作一致性檢測(cè)，去除其中不一致的規(guī)則。

算法1基于粗糙集正域的手寫(xiě)字母學(xué)習(xí)算法

輸入手寫(xiě)字母決策系統(tǒng)T=(U，C∪D，V，f)

輸出基于T的手寫(xiě)分類規(guī)則表Rule

步驟1對(duì)T做一致性檢測(cè)，去除不一致的規(guī)則。

步驟2Rule:={}，計(jì)算T中 D對(duì)論域的分類數(shù)ClassNum。

步驟3計(jì)算條件特征集C相對(duì)于決策特征D的正域POSC(D)。

將C賦值給約簡(jiǎn)集R，R:=C。

如果POSR(D)=POSC(D)成立，重復(fù)以下操作：

（1）?a∈R，計(jì)算出該特征的特征重要度Sign(a，R，D)；

（2）選擇R中特征重要度最小的特征a；

（3）更新約簡(jiǎn)集R:=R-{a}。

根據(jù)R簡(jiǎn)化T，得到簡(jiǎn)化的手寫(xiě)決策系統(tǒng)Tsimplified。

步驟5去除Rule不一致規(guī)則，輸出Rule。

4.2 手寫(xiě)字母分類算法

對(duì)手寫(xiě)字母進(jìn)行了合理的樣本采集和決策規(guī)則提取后，便可以對(duì)測(cè)試樣本進(jìn)行分類。算法2描述了測(cè)試樣本分類的過(guò)程。

算法2手寫(xiě)字母分類算法

輸入手寫(xiě)分類規(guī)則表Rule、待測(cè)試樣本特征向量sample

輸出sample所屬的分類result

步驟1result:={}，temp:={}。

步驟2計(jì)算Rule中的分類總數(shù)ClassNum。

將樣本逐一匹配決策規(guī)則Rule(i，j)中的每條規(guī)則；

如果匹配成功，保存匹配規(guī)則的分類結(jié)果result，跳到步驟4。

步驟4返回分類結(jié)果result。

5 實(shí)驗(yàn)結(jié)果與分析

首先對(duì)于 ?SegNum∈{2，4，6，8，10}，根據(jù)第3章的采樣策略進(jìn)行手寫(xiě)字母的采樣，每個(gè)樣本的特征數(shù)為SegNum×SegNum，每一類學(xué)習(xí)樣本采集數(shù)N取n×6，每類待測(cè)樣本采集數(shù)為100。然后對(duì)每一類樣本作正態(tài)分布假設(shè)檢驗(yàn)，并利用Matlab主成分提取命令pcacov提取“a”分類的學(xué)習(xí)樣本第一主成分，利用jbtest命令對(duì)第一主成分進(jìn)行正態(tài)分布檢驗(yàn)，結(jié)果如圖2所示，符合正態(tài)分布假設(shè)。

圖2“a”分類學(xué)習(xí)樣本正態(tài)分布檢測(cè)結(jié)果圖

通過(guò)類似實(shí)驗(yàn)檢驗(yàn)其他所有分類的樣本正態(tài)分布情況，結(jié)果表明都符合正態(tài)分布假設(shè)。

為檢驗(yàn)基于粗糙集手寫(xiě)識(shí)別算法的有效性，對(duì)算法做了縱向?qū)Ρ龋寒?dāng)改變手寫(xiě)字母樣本的物理分割數(shù)SegNum，即改變樣本的特征數(shù)n=SegNum×SegNum，觀察算法在時(shí)間消耗、分類準(zhǔn)確率、誤識(shí)率、拒識(shí)率上的性能變化。在相同實(shí)驗(yàn)條件下實(shí)驗(yàn)結(jié)果如表2所示。其中SegNum代表手寫(xiě)字母樣本的橫向、縱向平均劃分塊數(shù)。

表2 樣本等分?jǐn)?shù)變化時(shí)實(shí)驗(yàn)結(jié)果比較

由表2可知，當(dāng)SegNum取6時(shí)，手寫(xiě)識(shí)別算法的分類準(zhǔn)確率較高；SegNum過(guò)小或過(guò)大算法的分類效果會(huì)比較差。當(dāng)SegNum取過(guò)大時(shí)，學(xué)習(xí)算法會(huì)出現(xiàn)過(guò)擬合的現(xiàn)象，導(dǎo)致算法抗干擾性下降，同時(shí)算法的分類正確率也較低。SegNum=6是一個(gè)較為合理的樣本分割數(shù)。

取 SegNum=6，對(duì)比 Roughset、BP 神經(jīng)網(wǎng)絡(luò)、ID3、Fisher在手寫(xiě)字母識(shí)別上時(shí)間消耗、分類準(zhǔn)確率、誤識(shí)率、拒識(shí)率上的平均性能差異，其中時(shí)間包含學(xué)習(xí)時(shí)間以及識(shí)別時(shí)間，都采用本文設(shè)計(jì)的樣本數(shù)據(jù)結(jié)構(gòu)。在相同實(shí)驗(yàn)條件下實(shí)驗(yàn)結(jié)果如表3所示。

表3 橫向?qū)Ρ葘?shí)驗(yàn)結(jié)果

從表3可以看出，本文提出的基于粗糙集手寫(xiě)字母識(shí)別算法具有最優(yōu)的分類準(zhǔn)確率；雖然其時(shí)間性能相對(duì)較差，但算法的時(shí)間代價(jià)主要在離線的樣本學(xué)習(xí)過(guò)程中，對(duì)手寫(xiě)字母的在線識(shí)別速度沒(méi)有影響。實(shí)驗(yàn)結(jié)果驗(yàn)證了粗糙集算法在性能上的總體優(yōu)勢(shì)，具有一定的實(shí)用價(jià)值。

6 結(jié)語(yǔ)

本文基于粗糙集相關(guān)理論，提出了一種新的手寫(xiě)字母識(shí)別方法。首先對(duì)學(xué)習(xí)樣本進(jìn)行正態(tài)分布假設(shè)進(jìn)行驗(yàn)證，然后利用粗糙集原理對(duì)手寫(xiě)字母決策系統(tǒng)進(jìn)行特征選擇以適當(dāng)?shù)睾?jiǎn)化決策系統(tǒng)，并對(duì)簡(jiǎn)化后的手寫(xiě)決策系統(tǒng)進(jìn)行分類規(guī)則的提取，實(shí)驗(yàn)證明算法是有效可行的。由于在樣本采樣過(guò)程中樣本離散化會(huì)導(dǎo)致樣本部分有效信息的丟失，同時(shí)算法也沒(méi)有考慮粗糙集邊界元素對(duì)粗糙集分類的影響，接下來(lái)的工作將應(yīng)用鄰域關(guān)系改進(jìn)本文的算法，并綜合考慮粗糙集正域和邊界對(duì)分類結(jié)果的影響，以提高分類算法的分類精度。

[1]劉勇，趙斌，夏紹瑋.模糊超橢球分類算法及其在無(wú)約束手寫(xiě)體數(shù)字識(shí)別中的應(yīng)用[J].清華大學(xué)學(xué)報(bào)：自然科學(xué)版，2000，40（9）：120-124.

[2]Demirekler M，Altincy H.Plurality voting based multiple classifier systems：statistically independent with respect to depend classifier sets[J].Pattern Recognition，2002，35：2365-2379.

[3]Altineay H，Demirelder M.Undesirable effects of output normalization in multiple classifier systems[J].Pattern Recognition Letters，2003，24：1163-1170.

[4]Pawlak Z.Rough sets[J].International Journal of Information and Computer Sciences，1982，11（1）：341-356.

[5]Kryszkiewicz M.Comparative study of alternative type of knowledge reduction in inconsistent systems[J].International Journal of Intelligent Systems，2001，16（1）：105-120.

[6]張文修，吳偉志，梁吉業(yè)，等.粗糙集理論與方法[M].北京：科學(xué)出版社，2003.

[7]劉清.Rough集及Rough推理[M].北京：科學(xué)出版社，2001.

[8]Wang G Y，Wang Y.3DM：domain-oriented data-driven data mining[J].Fundamenta Informaticae，2009，90（4）：395-426.

[9]Chen Y M，Miao D Q，Wang R Z.A rough set approach to feature selection based on ant colony optimization[J]. Pattern Recognition Letters，2010，31（3）：226-233.

[10]Hu Q H，Yu D R，Xie Z X.Neighborhood classifiers[J]. Expert Systems with Applications，2008，34（2）：866-876.

[11]Jiang F，Sui Y F，Cao C G.Some issues about outlier detection in rough set theory[J].Expert Systemswith Applications，2009，36（3）：4680-4687.

[12]苗奪謙，張紅云，李道國(guó)，等.基于主曲線的脫機(jī)手寫(xiě)數(shù)字識(shí)別[J].電子學(xué)報(bào)，2005，33（9）：1639-1643.

[13]丁衛(wèi)平，王建東，段衛(wèi)華，等.一種求解屬性約簡(jiǎn)優(yōu)化的協(xié)同粒子群算法[J].山東大學(xué)學(xué)報(bào)：理學(xué)版，2011，46（5）：97-102.

[14]Yao Y Y，Zhao Y.Discernibility matrix simplification for constructing attribute reducts[J].Information Sciences，2009，179（7）：867-882.

[15]吳克壽，陳玉明，曾志強(qiáng).基于鄰域關(guān)系的決策表約簡(jiǎn)[J].山東大學(xué)學(xué)報(bào)：工學(xué)版，2012，42（2）：7-10.

TANG Chaohui,CHEN Yuming,WU Keshou

Department of Computer Science and Technology,Xiamen University of Technology,Xiamen,Fujian 361024,China

According to the characteristics of handwritten letter recognition,a new handwritten letter recognition algorithm is proposed based on the rough set theory.The hypothesis of normal distribution has been tested to ensure the reliability of the collected samples.By using upper approximation,lower approximation,as well as positive region of rough set,feature selection is made in order to simplify the decision-making system.Classification rules are then extracted from the simplified decision-making system.Experimental results show that the new algorithm has higher recognition accuracy, and is feasible and effective.

rough set;positive region;handwriting recognition;feature selection;supervised learning

針對(duì)手寫(xiě)字母識(shí)別的特點(diǎn)，結(jié)合粗糙集相關(guān)理論，提出了一種新的手寫(xiě)字母識(shí)別算法。通過(guò)對(duì)采集的樣本進(jìn)行正態(tài)分布假設(shè)驗(yàn)證，保證樣本的可靠性；利用粗糙集上近似、下近似以及正域概念，對(duì)手寫(xiě)樣本決策系統(tǒng)進(jìn)行特征選擇以簡(jiǎn)化決策系統(tǒng)，并進(jìn)一步提煉手寫(xiě)分類規(guī)則。實(shí)驗(yàn)結(jié)果表明，新算法具有較高的識(shí)別準(zhǔn)確率，是有效可行的。

粗糙集；正域；手寫(xiě)識(shí)別；特性選擇；監(jiān)督學(xué)習(xí)

A

TP181

10.3778/j.issn.1002-8331.1212-0221

TANG Chaohui,CHEN Yuming,WU Keshou.Handwritten letter recognition algorithm based on rough set positive region.Computer Engineering and Applications,2014,50（23）：118-121.

國(guó)家自然科學(xué)基金（No.61103246，No.60903203）；廈門(mén)理工學(xué)院人才科研啟動(dòng)項(xiàng)目（No.YKJ10036R）；廈門(mén)理工學(xué)院教改項(xiàng)目（No.JGY201315）；福建省教育廳B類項(xiàng)目（No.JB12252S，No.JB14082）；福建省大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目（No.201411062043）。

唐朝輝（1983—），男，講師，主要研究方向：粗糙集、機(jī)器學(xué)習(xí)；陳玉明（1977—），男，博士，講師，主要研究方向：粗糙集、粒計(jì)算、數(shù)據(jù)挖掘；吳克壽（1975—），男，博士，副教授，主要研究方向?yàn)榇植诩c數(shù)據(jù)挖掘。E-mail：chhtang@xmut.edu.cn

2012-12-18

2013-01-25

1002-8331（2014）23-0118-04

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-03-29,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1212-0221.html