一種改進(jìn)的FCM算法在手寫數(shù)字識(shí)別中的應(yīng)用

姜　琴（鄖陽(yáng)師范高等專科學(xué)?！∮?jì)算機(jī)科學(xué)系，湖北十堰442000）

?

一種改進(jìn)的FCM算法在手寫數(shù)字識(shí)別中的應(yīng)用

姜琴
（鄖陽(yáng)師范高等?？茖W(xué)校計(jì)算機(jī)科學(xué)系，湖北十堰442000）

摘要：模糊c均值（FCM，F(xiàn)uzzy c-Means）算法是一種非常實(shí)用的模糊聚類算法，在非監(jiān)督模式分類中占據(jù)著重要的地位。而手寫數(shù)字識(shí)別在現(xiàn)實(shí)中也有著非常廣泛的應(yīng)用，如郵政編碼、統(tǒng)計(jì)報(bào)表、銀行票據(jù)等等。在FCM算法基礎(chǔ)上，加入部分監(jiān)督信息，并對(duì)手寫數(shù)字圖像用Zernike矩來(lái)篩選特征，最后通過(guò)MATLAB編程，驗(yàn)證了該改進(jìn)的FCM算法對(duì)手寫數(shù)字識(shí)別具有一定的可靠性。

關(guān)鍵詞：FCM算法；手寫數(shù)字識(shí)別；部分監(jiān)督

0　引言

根據(jù)是否有教師指導(dǎo)，聚類方法分為無(wú)監(jiān)督聚類和有監(jiān)督聚類。對(duì)于沒(méi)有任何先驗(yàn)知識(shí)來(lái)指導(dǎo)的分類，稱之為無(wú)監(jiān)督聚類；而有監(jiān)督聚類，是指事先已知部分樣本的隸屬類別，需用一定的方法再對(duì)未知的樣本劃分類別的聚類。

在無(wú)監(jiān)督聚類中，理論上比較完善并且應(yīng)用非常廣泛的是模糊c均值（FCM，F(xiàn)uzzy c-Means）［1，2］類型的聚類算法。在實(shí)際中，若有一定的先驗(yàn)知識(shí)，即已知某些樣本屬于某個(gè)類別時(shí)，可以將該先驗(yàn)知識(shí)加入到FCM算法中，從而，人們研究出了多種具有部分監(jiān)督信息的FCM算法。

1　 FCM算法

設(shè)X=｛X1，X2，…，Xn｝?Rn×q為樣本集合，n為樣本數(shù)，q為特征空間的維數(shù)。記c為類別數(shù)，U=［uij］c×n為模糊劃分矩陣：其中uij（1≤i≤c，1≤j≤n）表示第j個(gè)樣本Xj屬于第i個(gè)類別的隸屬度，uij應(yīng)滿足以下二個(gè)約束條件：

Bezdek定義了模糊c均值聚類算法的一般描述：

（3）式中V=（v1，v2，…，vc）為s×c矩陣，vj（j=1，2，…，c）∈Rs為第j類中心為點(diǎn)xj與第i類中心vi之間的距離公式。m為模糊指數(shù)，控制分類矩陣U的模糊程度。目標(biāo)函數(shù)Jm（X，μ，v）是類內(nèi)加權(quán)誤差平方和目標(biāo)函數(shù)，F(xiàn)CM算法就是一個(gè)使目標(biāo)函數(shù)Jm（X，μ，v）最小化的迭代求解過(guò)程［3，4］。

2　改進(jìn)的具有部分監(jiān)督的FCM算法

假設(shè)ns為具有先驗(yàn)知識(shí)的樣本個(gè)數(shù)，未知類別的樣本數(shù)為n個(gè)，則總共樣本數(shù)有ns+n個(gè)；其中n1個(gè)屬于第一類，n2-n1個(gè)屬于第二類，ns-ns-1個(gè)屬于第s類。設(shè)具有先驗(yàn)知識(shí)的樣本劃分矩陣為U*，分類數(shù)依舊為c （s≤c），則劃分矩陣U′=（U*，U），即為

則基于目標(biāo)函數(shù)的改進(jìn)的具有部分監(jiān)督的模糊聚類一般描述為：

且滿足下列條件：

其中，W為文獻(xiàn)［5］所描述的特征加權(quán)矩陣。

根據(jù)拉格朗日乘數(shù)法，有如下計(jì)算步驟：

首先設(shè)定2≤c≤n，迭代停止閥值為ε，初始化聚類原型模式P（0），迭代計(jì)數(shù)器b=0；

步驟一：用下式計(jì)算或更新劃分矩陣U′=（U*（b），U（b））：

（1）對(duì)于U*（b）的第k列，其最大隸屬度為：

（2）無(wú)監(jiān)督樣本的隸屬度矩陣U（b）為：

步驟二：用下式更新聚類中心P（b+1）：

3　手寫數(shù)字識(shí)別

手寫體數(shù)字識(shí)別屬于字符識(shí)別領(lǐng)域，其主要研究如何利用電子計(jì)算機(jī)來(lái)自動(dòng)辨認(rèn)人手寫在紙張上的阿拉伯?dāng)?shù)字。相較于英文識(shí)別，漢字識(shí)別，脫機(jī)手寫數(shù)字則是最難識(shí)別的。

在進(jìn)行手寫數(shù)字識(shí)別時(shí)，需要先對(duì)帶有隨機(jī)噪聲的字符灰度值數(shù)字信號(hào)進(jìn)行預(yù)處理。

通過(guò)預(yù)處理（參見(jiàn)文獻(xiàn)［6］，［7］），可將原始圖像轉(zhuǎn)二值化，并對(duì)尺寸和位置進(jìn)行歸一化處理。一般地，還需在預(yù)處理后的圖像上提取特征，可用Zernike矩來(lái)篩選特征。

若圖像的密度函數(shù)為f（x，y），其n階Zernike矩的定義為

式（15）中，*表示取共軛，Zernike多項(xiàng)式Vnm（x，y）由下式給出：Vnm（x，y）=Vnm（r，θ）=Rnm（r）ejmθ，式中，n為非負(fù)整數(shù)并滿足為偶數(shù)，實(shí)半徑多項(xiàng)式Rnm（r）的定義為

Zernike多項(xiàng)式滿足下述正交關(guān)系：

Znm在極坐標(biāo)形式下可表示為：

Znm是一個(gè)復(fù)數(shù)，將實(shí)部記為Cnm，虛部記為和Snm，則：

根據(jù)正交性，Znm的反變換為

式中，M表示所需使用的矩的最高階數(shù)。

考慮一幅圖像，設(shè)其以α角度旋轉(zhuǎn)，旋轉(zhuǎn)后的圖像用fr表示，則fr（r，θ）=f（r，θ-α）。設(shè)θ1=θ-α，旋轉(zhuǎn)后的圖像的Zernike矩的計(jì)算表示為：

令θ1=θ-α，則

可用項(xiàng)Rn-2，m（r）和Rn-4，m（r）來(lái)計(jì)算Zernike多項(xiàng)式Rnm（r）。迭代關(guān)系式的起始項(xiàng)可選Rnm（r）=rm。

這里：k1=（n-1）（n+1）（n-2）/2；k2=2n（n-1）（n-2）；k3=-（n-1）3；k4=-n（n-1）（n-3）/2。對(duì)于不同的初始值m，都要重復(fù)整個(gè)過(guò)程。

4　改進(jìn)的FCM算法在手寫數(shù)字識(shí)別中的實(shí)驗(yàn)分析

現(xiàn)從UK測(cè)試表中截取了5000樣本進(jìn)行數(shù)據(jù)處理。先根據(jù)上面所說(shuō)的特征提取方法提取出部分手寫體數(shù)字的特征矢量，然后再將同一數(shù)字的不同矢量特征表達(dá)作為研究對(duì)象進(jìn)行模糊聚類分析。如手寫體的“2”的手寫形式為，其特征矢量為C=［-1 -1 -1 0 -1 -1 -3 1 1 0 3 3 3 0 0］；而的特征矢量為C=［-1 -1 0 -1 -2 0 -1 -1 -1 6 3 0 0 0 1］。以此類推。

表1　實(shí)驗(yàn)結(jié)果（ε=0.0015）

從上表可以看出，數(shù)字“2，3，4，5，8，9”的識(shí)別率都比較高，而“0”和“6”，“1”和“7”這兩組數(shù)字，因?yàn)樵谧中紊嫌行┫嘟?，人們?cè)跁鴮懙臅r(shí)候，由于字跡潦草、習(xí)慣等原因，使得識(shí)別率相對(duì)于其他數(shù)字稍低。但總體來(lái)講，此算法對(duì)手寫數(shù)字識(shí)別具有一定的可靠性。

［參考文獻(xiàn)］

［1］閔珊華，賀仲雄.懂一點(diǎn)模糊數(shù)學(xué)［M］.北京：中國(guó)青年出版社，1985.

［2］Zadeh L A. Fuzzy sets［J］.Information and Control，1965，8（5）：338～353.

［3］王士同，夏祖勛，陳劍夫.模糊數(shù)學(xué)在人工智能中的應(yīng)用［M］.北京：機(jī)械工業(yè)出版社，1991.

［4］Bezdek J C. A review of probabilistic，fuzzy，and neutral model for pattern recognition［J］.Journal of intelligent and fuzzy systems，1996，4（1）：1～25.

［5］Xiaojun Tong，Qin Jiang，Haitao Gan，Shan Zeng，Kai Zhao. Research on the Calculation Mothod for Weight of the Feature Weight Fuzzy Clustering Algorithm［A］∥DCABES2008：677～682.

［6］夏德深，傅德勝.現(xiàn)代圖像處理技術(shù)與應(yīng)用［M］.南京：東南大學(xué)出版社，1997.

［7］姜琴.模糊聚類分析及其在數(shù)字圖像處理中的應(yīng)用［D］.武漢工業(yè)學(xué)院，2009.

Application of Improved FCM Algorithm in Handwritten Numeral Recognition

JIANG Qin
（Department of Computer Science，Yunyang Teachers College，Shiyan 442000，China）

Abstract:Fuzzy Means（FCM）algorithm，a practical fuzzy clustering algorithm，plays an important role in the unsupervised pattern classification. The hand -written numeral recognition is widely applied in different fields，such as postcodes，statistics statements，bank bills，etc. Partial supervision information is added in FCM algorithm，and characteristics are selected by Zernike moment with hand-written numeral images，and the improved FCM algorithm is proved to be reliable to the hand-written numeral recognition by means of MATLAB programming.

Key words:FCM algorithm；handwritten numeral recognition；partial supervision

中圖分類號(hào)：TP391

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：2095-8153（2016）02-0105-04

收稿日期：2016-03-27

基金項(xiàng)目：湖北省教育廳2015年度科研計(jì)劃項(xiàng)目（Q20156002）；鄖陽(yáng)師范高等?？茖W(xué)校科研基金項(xiàng)目（編號(hào)2012B03）階段性成果。

作者簡(jiǎn)介：姜琴（1978-），女，鄖陽(yáng)師范高等?？茖W(xué)校計(jì)算機(jī)科學(xué)系講師，碩士，研究方向：計(jì)算機(jī)圖形圖像及計(jì)算數(shù)學(xué)方面教學(xué)。