基于粗糙集正域的手寫字母識別算法

唐朝輝，陳玉明，吳克壽

廈門理工學院 計算機科學與技術系，福建 廈門 361024

基于粗糙集正域的手寫字母識別算法

唐朝輝，陳玉明，吳克壽

廈門理工學院 計算機科學與技術系，福建 廈門 361024

1 引言

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

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

苗奪謙等人[12]提出了一種基于主曲線的脫機手寫數字識別方法，該方法將主曲線及知識約簡算法運用于識別模型。本文針對手寫識別的特點，結合粗糙集正域，定義了特征重要度概念，并應用于手寫識別決策系統約簡當中；同時提出了基于粗糙集正域的手寫字母識別算法，通過實驗分析驗證了算法的可行性。

2 粗糙集相關概念

粗糙集理論研究方法基于數據分類與知識的聯系，并利用集合等價關系來描述數據分類[13-15]。為構建基于粗糙集的手寫字母樣本學習和測試集分類算法，引入以下粗糙集的相關定義。

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

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

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

定義5設決策系統T=(U，C∪D，V，f)，對b∈B?C，若POSB(D)=POSB-{b}(D)，則相對于決策特征D來說特征b是不必要的；否則b是必要的。對?B?C，如果B相對于決策特征D都是必要的，則稱特征集B獨立于決策特征D。

定義6設決策系統T=(U，C∪D，V，f)，若 ?B?C，POSB(D)=POSC(D)且特征集B獨立于決策特征D，則稱特征集B是條件特征集C相對于決策特征D的一個約簡。

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

3 手寫樣本采集及分布檢驗

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

手寫字母采樣策略如下所示：

（1）在可視化界面上用鼠標手寫字母，同時給出樣本正確的分類，便于樣本監督學習。

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

圖1 截取后的手寫學習樣本

（3）為有效充分地學習手寫字母樣本并降低時間復雜性，樣本數 N應該取樣本特征數的5～10倍，本文為每類分類收集SegNum×SegNum×6個樣本。

（4）將每個樣本特征與預期的手寫分類結果存儲起來以構建手寫字母識別決策系統，便于算法學習以提取手寫字母分類規則。

根據機器學習理論，工程上很多的統計數據都在一定程度上滿足正態分布。為保證手寫樣本具有一定的隨機性、可靠性，對樣本的分布做正態分布假設檢測：根據單個樣本模式的空間維度較大的特點，為提高分布檢測的效率，本文采用主成分分析的方法獲取特征空間的主成分，并利用 χ2檢驗法對主成分作正態分布檢驗。

首先假設手寫字母特征符合正態分布 N(μ，σ2)，μ，σ2未知。采用最大似然估計對μ，σ2進行點估計，得：

獲得分布概率密度后，采用 χ2檢驗法檢驗樣本是否滿足正態分布。χ2檢驗法可以通過分組數據的取值范圍并計算每個分組的頻數來實現分布檢驗的，其統計量如公式（2）。

其中N為樣本數，l為分組數，ri為實際頻數，ti為理論頻數。

4 基于粗糙集的手寫字母樣本學習與分類

4.1 樣本學習算法

本文使用有監督的學習算法，首先建立手寫字母識別決策系統，如表1所示。

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

表1 手寫識別決策系統結構

每一行代表一個輸入樣本的模式，D特征為決策特征，代表該樣本對應的實際分類。

在手寫識別分類算法中，首先要解決的是兩類分類的問題。本文基于粗糙集理論，提出了基于粗糙集正域的手寫字母學習算法。該算法首先利用粗糙集正域簡化手寫決策系統，然后從簡化的決策系統中抽取所有兩類分類規則，并對獲取的所有分類規則作一致性檢測，去除其中不一致的規則。

算法1基于粗糙集正域的手寫字母學習算法

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

輸出基于T的手寫分類規則表Rule

步驟1對T做一致性檢測，去除不一致的規則。

步驟2Rule:={}，計算T中 D對論域的分類數ClassNum。

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

將C賦值給約簡集R，R:=C。

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

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

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

（3）更新約簡集R:=R-{a}。

根據R簡化T，得到簡化的手寫決策系統Tsimplified。

步驟5去除Rule不一致規則，輸出Rule。

4.2 手寫字母分類算法

對手寫字母進行了合理的樣本采集和決策規則提取后，便可以對測試樣本進行分類。算法2描述了測試樣本分類的過程。

算法2手寫字母分類算法

輸入手寫分類規則表Rule、待測試樣本特征向量sample

輸出sample所屬的分類result

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

步驟2計算Rule中的分類總數ClassNum。

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

如果匹配成功，保存匹配規則的分類結果result，跳到步驟4。

步驟4返回分類結果result。

5 實驗結果與分析

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

圖2“a”分類學習樣本正態分布檢測結果圖

通過類似實驗檢驗其他所有分類的樣本正態分布情況，結果表明都符合正態分布假設。

為檢驗基于粗糙集手寫識別算法的有效性，對算法做了縱向對比：當改變手寫字母樣本的物理分割數SegNum，即改變樣本的特征數n=SegNum×SegNum，觀察算法在時間消耗、分類準確率、誤識率、拒識率上的性能變化。在相同實驗條件下實驗結果如表2所示。其中SegNum代表手寫字母樣本的橫向、縱向平均劃分塊數。

表2 樣本等分數變化時實驗結果比較

由表2可知，當SegNum取6時，手寫識別算法的分類準確率較高；SegNum過小或過大算法的分類效果會比較差。當SegNum取過大時，學習算法會出現過擬合的現象，導致算法抗干擾性下降，同時算法的分類正確率也較低。SegNum=6是一個較為合理的樣本分割數。

取 SegNum=6，對比 Roughset、BP 神經網絡、ID3、Fisher在手寫字母識別上時間消耗、分類準確率、誤識率、拒識率上的平均性能差異，其中時間包含學習時間以及識別時間，都采用本文設計的樣本數據結構。在相同實驗條件下實驗結果如表3所示。

表3 橫向對比實驗結果

從表3可以看出，本文提出的基于粗糙集手寫字母識別算法具有最優的分類準確率；雖然其時間性能相對較差，但算法的時間代價主要在離線的樣本學習過程中，對手寫字母的在線識別速度沒有影響。實驗結果驗證了粗糙集算法在性能上的總體優勢，具有一定的實用價值。

6 結語

本文基于粗糙集相關理論，提出了一種新的手寫字母識別方法。首先對學習樣本進行正態分布假設進行驗證，然后利用粗糙集原理對手寫字母決策系統進行特征選擇以適當地簡化決策系統，并對簡化后的手寫決策系統進行分類規則的提取，實驗證明算法是有效可行的。由于在樣本采樣過程中樣本離散化會導致樣本部分有效信息的丟失，同時算法也沒有考慮粗糙集邊界元素對粗糙集分類的影響，接下來的工作將應用鄰域關系改進本文的算法，并綜合考慮粗糙集正域和邊界對分類結果的影響，以提高分類算法的分類精度。

[1]劉勇，趙斌，夏紹瑋.模糊超橢球分類算法及其在無約束手寫體數字識別中的應用[J].清華大學學報：自然科學版，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]張文修，吳偉志，梁吉業，等.粗糙集理論與方法[M].北京：科學出版社，2003.

[7]劉清.Rough集及Rough推理[M].北京：科學出版社，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]苗奪謙，張紅云，李道國，等.基于主曲線的脫機手寫數字識別[J].電子學報，2005，33（9）：1639-1643.

[13]丁衛平，王建東，段衛華，等.一種求解屬性約簡優化的協同粒子群算法[J].山東大學學報：理學版，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]吳克壽，陳玉明，曾志強.基于鄰域關系的決策表約簡[J].山東大學學報：工學版，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

針對手寫字母識別的特點，結合粗糙集相關理論，提出了一種新的手寫字母識別算法。通過對采集的樣本進行正態分布假設驗證，保證樣本的可靠性；利用粗糙集上近似、下近似以及正域概念，對手寫樣本決策系統進行特征選擇以簡化決策系統，并進一步提煉手寫分類規則。實驗結果表明，新算法具有較高的識別準確率，是有效可行的。

粗糙集；正域；手寫識別；特性選擇；監督學習

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.

國家自然科學基金（No.61103246，No.60903203）；廈門理工學院人才科研啟動項目（No.YKJ10036R）；廈門理工學院教改項目（No.JGY201315）；福建省教育廳B類項目（No.JB12252S，No.JB14082）；福建省大學生創新創業訓練計劃項目（No.201411062043）。

唐朝輝（1983—），男，講師，主要研究方向：粗糙集、機器學習；陳玉明（1977—），男，博士，講師，主要研究方向：粗糙集、粒計算、數據挖掘；吳克壽（1975—），男，博士，副教授，主要研究方向為粗糙集與數據挖掘。E-mail：chhtang@xmut.edu.cn

2012-12-18

2013-01-25

1002-8331（2014）23-0118-04

CNKI網絡優先出版：2013-03-29,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1212-0221.html