基于客觀聚類的手寫數字識別方法

王 娜，胡超芳

(1 a.天津工業大學電氣工程與自動化學院自動化系；b.天津市電工電能新技術重點實驗室，天津 300387；2 a.天津大學微光機電系統技術教育部重點實驗室；b.電氣自動化與信息工程學院自動化系，天津 300072)

0 引言

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

1 手寫數字識別問題描述

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

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

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

2)對每一小區域內的黑像素個數進行統計，除以該小區域的面積總數，即得特征值，如圖3所示。

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

圖2 對樣本分成5×5區域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 基于客觀聚類的手寫數字識別

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

2.1 客觀聚類分析

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

2.1.1 偶極子劃分

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

1)初始子集生成

2)相似度排序

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

3)訓練子集和測試子集生成

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

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

2.1.2 凝聚層次聚類

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

(1)

(2)

本文采用改進一致性準則克服噪聲和分布的影響，提高聚類結果的魯棒性，改進一致性準則定義為

(3)

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

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

2.2 手寫數字識別算法步驟描述

3 仿真研究

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

(4)

圖4 偶極子劃分后的訓練子集和測試子集the dipole partitioning

給定聚類數c∈{2,…,64}，利用相對不相似性測度進行聚類的合并，在聚類數為3時得到最小一致性準則值0.048，其對應聚類中心為

(5)

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

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

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

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

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

(15)

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

(16)

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

(17)

(18)

表1 隨機手寫數字0輸入下本方法與其他數據驅動方法比較

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

同理依次隨機輸入9個手寫數字1，圖像如圖8所示。

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

圖8 按順序1-9依次輸入隨機手寫數字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可見，本方法與其他數據驅動和模板匹配法相比，仍具有更高的識別精度，簡單易行。

表3 隨機手寫數字1輸入下本方法與其他數據驅動方法比較

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

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

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

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

4 結論

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