基于客觀聚類的手寫數(shù)字識別方法

王 娜，胡超芳

(1 a.天津工業(yè)大學(xué)電氣工程與自動化學(xué)院自動化系；b.天津市電工電能新技術(shù)重點(diǎn)實(shí)驗(yàn)室，天津 300387；2 a.天津大學(xué)微光機(jī)電系統(tǒng)技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室；b.電氣自動化與信息工程學(xué)院自動化系，天津 300072)

0 引言

作為數(shù)據(jù)驅(qū)動工具之一，聚類是一種處理高維特征數(shù)據(jù)的有效手段，且基于劃分的聚類算法已廣泛應(yīng)用于手寫數(shù)字的識別[7]。但傳統(tǒng)的劃分聚類的初始聚類個數(shù)和聚類中心先驗(yàn)未知，需要經(jīng)驗(yàn)或試湊確定，具有較多主觀性；且聚類過程易受噪聲或者數(shù)據(jù)分布影響，降低結(jié)果的準(zhǔn)確性[8]。為此，引入一種新的基于客觀聚類的手寫數(shù)字識別方法——客觀聚類分析方法[9]，它具有對數(shù)據(jù)中噪聲和不規(guī)則形狀的魯棒性，可以確保上述聚類結(jié)果的準(zhǔn)確性，且通過對模板數(shù)據(jù)集的一次聚類，獲得代表性聚類個數(shù)和聚類中心，用來代替模板集識別分類，不僅避免了傳統(tǒng)模板匹配法需要將待識別數(shù)據(jù)與模板數(shù)據(jù)集逐個比較的繁瑣過程，而且約簡了模板集、降低了計(jì)算量。通過對隨機(jī)手寫的數(shù)字在變形和添加噪聲等情況下的識別，并與其他手寫數(shù)字識別方法如Hopfield神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)和粗糙集等，以及傳統(tǒng)模板匹配法相比較，驗(yàn)證了本方法的有效性[5]。

1 手寫數(shù)字識別問題描述

手寫體數(shù)字識別一般包括圖像預(yù)處理、特征提取、分類這3個步驟，其基本原理如圖1所示。

如圖1所示，其中預(yù)處理去除數(shù)字圖像的噪聲，并灰度化處理讀入圖像；采用降維方法提取數(shù)字圖像的結(jié)構(gòu)和統(tǒng)計(jì)特征，相比結(jié)構(gòu)特征，統(tǒng)計(jì)特征對噪聲不敏感，具有較好的穩(wěn)定性，故可用于噪聲較多的任意手寫數(shù)字識別中。為此，本文采用一種統(tǒng)計(jì)特征法—5×5模板提取特征法[5]來對任意輸入的手寫體數(shù)字進(jìn)行模板集的構(gòu)造和輸入數(shù)字特征向量的提取。其步驟如下：

1)找到每個手寫樣本的起始位置，在此附近搜索該樣本的寬度和高度，將每個樣本的長度和寬度5等分，構(gòu)成5×5的均勻小區(qū)域，如圖2所示。

2)對每一小區(qū)域內(nèi)的黑像素個數(shù)進(jìn)行統(tǒng)計(jì)，除以該小區(qū)域的面積總數(shù)，即得特征值，如圖3所示。

圖1 手寫數(shù)字識別的基本步驟Fig.1 Basic steps of handwriting digital recognition

圖2 對樣本分成5×5區(qū)域Fig.2 Dividing the handwriting digital into a five times five area

圖3 5×5模板特征值示意圖Fig.3 Diagram of eigenvalue for the template of five times five

2 基于客觀聚類的手寫數(shù)字識別

采用模板匹配法進(jìn)行數(shù)字識別時(shí)，首先，模板樣本集中可能包含冗余的噪聲數(shù)據(jù)，導(dǎo)致樣本集整體數(shù)據(jù)的準(zhǔn)確度下降，從而影響分類結(jié)果；其次，模板數(shù)據(jù)的維數(shù)較高且個數(shù)較多時(shí)，每個模板數(shù)據(jù)都要與待識別的樣本進(jìn)行一次距離測度的計(jì)算，計(jì)算量極其龐大，也帶來識別效率的降低。為此，引入客觀聚類分析方法來克服原始數(shù)據(jù)集中噪聲數(shù)據(jù)的影響，提高分類精度，并選出代表性數(shù)據(jù)來約簡模板數(shù)據(jù)集，降低計(jì)算量。

2.1 客觀聚類分析

客觀聚類分析方法分為兩個階段：偶極子劃分和凝聚層次聚類。偶極子劃分為后續(xù)的凝聚層次聚類提供初始聚類對象；此外原始數(shù)據(jù)集被偶極子劃分為相似分布的子集，在子集上進(jìn)行凝聚層次聚類，并將距離聚類中心遠(yuǎn)的數(shù)據(jù)，一般為噪聲和邊界點(diǎn)放置到最后聚類，從而能夠有效降低其對最終聚類結(jié)果準(zhǔn)確度的影響。凝聚層次聚類的聚類對象為偶極子劃分的4個子集，并利用改進(jìn)一致性準(zhǔn)則來評判不同子集之間聚類結(jié)果的一致性，并選擇一致性程度最高的聚類結(jié)果作為最終結(jié)果。

2.1.1 偶極子劃分

偶極子劃分過程分為初始子集生成、相似度排序、訓(xùn)練和測試子集生成[9]。

1)初始子集生成

2)相似度排序

對O中的元素，按照偶極子值由小到大依次排列，形成新的偶極子集On。

3)訓(xùn)練子集和測試子集生成

從On中取出前N/2個包含不重復(fù)樣本的偶極子，將每個偶極子中距離數(shù)據(jù)集中點(diǎn)zr近的元素構(gòu)成訓(xùn)練子集ZA={zA1,…,zAN/2}，其中每個元素按照距離遠(yuǎn)近排列。同理對每個偶極子中距離zr遠(yuǎn)的元素，得到訓(xùn)練子集ZB={zB1,…,zBN/2}。最后，從On中剩余的偶極子中再取出前N/2個包含不重復(fù)樣本的偶極子，形成測試子集Zc和ZD。

由上述偶極子劃分機(jī)制可知，其根據(jù)選定的參考聚類中心將原始數(shù)據(jù)集劃分為不同的數(shù)據(jù)子集，在劃分過程中按照偶極子對之間的相似性進(jìn)行排序，使得在后續(xù)的凝聚層次聚類中，距離參考中心最遠(yuǎn)的偶極子對，大多為噪聲數(shù)據(jù)點(diǎn)最后進(jìn)行聚類中心的合并，而距離聚類中心最近的偶極子對最先進(jìn)行聚類，從而有效降低了這些噪聲點(diǎn)對聚類過程的影響，確保了聚類結(jié)果的準(zhǔn)確性。

2.1.2 凝聚層次聚類

偶極子劃分后，分別在子集A、B及C、D上進(jìn)行凝聚層次聚類，選擇相對不相似性測度作為每次聚類時(shí)聚類合并相似性程度的評判。相對不相似性測度定義為[10]

(1)

(2)

本文采用改進(jìn)一致性準(zhǔn)則克服噪聲和分布的影響，提高聚類結(jié)果的魯棒性，改進(jìn)一致性準(zhǔn)則定義為

(3)

最后，將指標(biāo)BLnewAB和BLnewCD比較，由最低值確定最終聚類數(shù)和聚類中心，其中BLnewAB和BLnewCD分別由子集A、B和C、D按照式(3)得到。

由上述偶極子劃分和凝聚層次聚類的步驟描述可知，偶極子分類初始劃分了數(shù)據(jù)子集，并利用相似性排序法將噪聲點(diǎn)和邊界點(diǎn)對后續(xù)凝聚層次聚類的影響降低，從而為凝聚層次聚類提供了準(zhǔn)確的初始聚類結(jié)果；而凝聚層次聚類利用改進(jìn)一致性準(zhǔn)則評判不同子集之間聚類結(jié)果的一致性，避免了單一聚類過程易受數(shù)據(jù)分布影響而導(dǎo)致聚類結(jié)果準(zhǔn)確度下降的問題，提高了聚類結(jié)果選擇的客觀性，進(jìn)而增強(qiáng)了聚類結(jié)果的精確性。

2.2 手寫數(shù)字識別算法步驟描述

3 仿真研究

首先，獲得數(shù)字0的模板庫Z0，其表達(dá)式為130×25維矩陣：

(4)

圖4 偶極子劃分后的訓(xùn)練子集和測試子集the dipole partitioning

給定聚類數(shù)c∈{2,…,64}，利用相對不相似性測度進(jìn)行聚類的合并，在聚類數(shù)為3時(shí)得到最小一致性準(zhǔn)則值0.048，其對應(yīng)聚類中心為

(5)

并取該聚類中心CenterAB0作為數(shù)字0模板樣本集的代表，其由3個1×25維行向量組成，有效實(shí)現(xiàn)對訓(xùn)練子集A、B的約簡。同理獲得數(shù)字1,2,…,9的模板樣本集聚類中心，分別為CenterAB1,…,CenterAB9：

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

在手寫數(shù)字輸入軟件的模板中在線輸入數(shù)字0如下：

圖5 數(shù)字0的手寫在線輸入示意圖Fig.5 Online input diagram for the handwriting digital zero

圖6 數(shù)字0變形后的手寫在線輸入示意圖Fig.6 Online-input diagram for the distortion of handwriting digital zero

(15)

由式(15)可見，在線輸入數(shù)字0與已知模板集中數(shù)字0的距離最近，為0.303，故應(yīng)把其歸為0類。

(16)

圖7 數(shù)字0變形后的手寫輸入示意圖Fig.7 Online-input diagram for the distortion of handwriting digital zero

(17)

(18)

表1 隨機(jī)手寫數(shù)字0輸入下本方法與其他數(shù)據(jù)驅(qū)動方法比較

在手寫數(shù)字分類軟件模板[5]中隨機(jī)輸入29個數(shù)字0，本方法與其他數(shù)據(jù)驅(qū)動及模板匹配法比較如表1和表2所示。由表1和表2可見，對于任意輸入的手寫數(shù)字0，模板匹配法比其他數(shù)據(jù)驅(qū)動方法具有更高的識別精度。在其他數(shù)據(jù)驅(qū)動方法中，精度最低的是勢函數(shù)法，為24.14%，最高的是Bayes匹配法，為69%。其他模板匹配法中精度最低的是基于類中心的歐幾里德距離法，為72.41%；最高的是使用PCA的最近鄰模板匹配法，為96.55%，而上述本方法識別精度為100%，說明本方法具有對變形及含噪聲數(shù)據(jù)更強(qiáng)的魯棒性，并且避免了支持向量機(jī)、Hopfiled神經(jīng)網(wǎng)絡(luò)等需要參數(shù)的初始設(shè)置和調(diào)節(jié)的過程，也避免了PCA最近鄰模板匹配和夾角余弦距離法的PCA降維步驟，計(jì)算簡單，易于實(shí)現(xiàn)，識別精度更高；另外本方法采用客觀聚類分析對模板集聚類，利用聚類中心代表原始模板集，大大降低了計(jì)算量，提高了在線識別的效率。

同理依次隨機(jī)輸入9個手寫數(shù)字1，圖像如圖8所示。

表2 隨機(jī)手寫數(shù)字0輸入下本方法與其他模板匹配法比較

圖8 按順序1-9依次輸入隨機(jī)手寫數(shù)字1示意圖Fig.8 Diagram of inputting the random handwriting digital one in turn in the order of one to nine

本方法與其他方法比較如表3和表4所示[5]。由表3和表4可見，本方法與其他數(shù)據(jù)驅(qū)動和模板匹配法相比，仍具有更高的識別精度，簡單易行。

表3 隨機(jī)手寫數(shù)字1輸入下本方法與其他數(shù)據(jù)驅(qū)動方法比較

表4 隨機(jī)手寫數(shù)字1輸入下本方法與其他模板匹配法比較

此外，通過每個數(shù)字均隨機(jī)輸入30個樣本，對于其他手寫輸入數(shù)字2,3,…,9，本方法與其他方法的識別精度比較如表5所示。

表5 隨機(jī)手寫數(shù)字2-9輸入下本方法與其他模板匹配法比較

由表5可見，本方法與其他模板匹配法相比，除對數(shù)字9的識別精度略低，為30%外，對其他數(shù)字2～8的識別精度均為最高，最高為100%，說明本方法具有較高的識別精度。并且，本方法采用模板集的聚類中心代表整個模板集，避免了傳統(tǒng)的最近鄰模板匹配法需要將待識別樣本與模板集反復(fù)比較導(dǎo)致的繁瑣計(jì)算量，提高了算法的計(jì)算效率。

4 結(jié)論

本文將客觀聚類分析與模板匹配法相結(jié)合，提出了一種新的手寫數(shù)字識別方法。該方法在無數(shù)據(jù)先驗(yàn)知識下，通過啟發(fā)式自組織產(chǎn)生聚類，并利用聚類中心代替原始模板集，一方面具有對數(shù)據(jù)分布和噪聲的較強(qiáng)魯棒性，從而提高了識別精度；另一方面也約簡了原始模板集，降低了計(jì)算的復(fù)雜性，提高了識別效率，對隨機(jī)手寫輸入數(shù)字0-9在變形和加入噪聲等情況下的識別結(jié)果驗(yàn)證了所提方法的有效性。