一種新的李群分類(lèi)器在手寫(xiě)體數(shù)字中的應(yīng)用＊

王曉乾，張 莉，何書(shū)萍，楊季文，李凡長(zhǎng)

（蘇州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 蘇州 215006）

1 引言

手寫(xiě)體數(shù)字識(shí)別一直是模式識(shí)別領(lǐng)域的一個(gè)重要研究課題，有著極為廣泛的應(yīng)用前景。隨著計(jì)算機(jī)技術(shù)和數(shù)字圖像處理技術(shù)的飛速發(fā)展，數(shù)字識(shí)別在大規(guī)模數(shù)據(jù)統(tǒng)計(jì)、郵件分揀、財(cái)務(wù)、稅務(wù)、金融領(lǐng)域中都有著廣泛應(yīng)用。因此，手寫(xiě)數(shù)字的識(shí)別研究有著重大的實(shí)際意義，會(huì)產(chǎn)生巨大的社會(huì)和經(jīng)濟(jì)效益。

李群是目前學(xué)術(shù)界公認(rèn)的用于研究學(xué)習(xí)問(wèn)題的一套完善的理論工具，很多物理學(xué)家和化學(xué)家開(kāi)始廣泛使用李群理論研究相關(guān)領(lǐng)域的數(shù)據(jù)[1]。李群理論在流形學(xué)習(xí)中表現(xiàn)出了強(qiáng)大的優(yōu)勢(shì)，文獻(xiàn)[2，3]研究了視覺(jué)跟蹤問(wèn)題中變換矩陣?yán)钊杭捌湎鄳?yīng)李代數(shù)的表示，文獻(xiàn)[4]使用協(xié)方差算子來(lái)構(gòu)造李群數(shù)據(jù)并用于行人檢測(cè)，文獻(xiàn)[5]成功應(yīng)用李群李代數(shù)方法表示變換過(guò)程，以此來(lái)學(xué)習(xí)動(dòng)態(tài)視覺(jué)流，效果很好。

目前，針對(duì)李群數(shù)據(jù)所設(shè)計(jì)的李群分類(lèi)器還不是很多，而能夠?qū)嵱玫木透由倭?。這里介紹兩種可以應(yīng)用到手寫(xiě)體數(shù)字識(shí)別上的李群分類(lèi)器：李群內(nèi)均值分類(lèi)器[6，7]和李群Fisher分類(lèi)器[8]。李群內(nèi)均值分類(lèi)器是先計(jì)算李群的內(nèi)均值，然后再根據(jù)和均值的遠(yuǎn)近來(lái)分類(lèi)樣本，能夠處理多類(lèi)問(wèn)題。但是，其對(duì)多類(lèi)問(wèn)題處理時(shí)，性能不是很好。李群Fisher分類(lèi)器是Fisher判別分析在李群數(shù)據(jù)上的推廣，可以在投影后獲得更好的可分性。但是，文獻(xiàn)[8]并沒(méi)有將該分類(lèi)器推廣到多分類(lèi)問(wèn)題上。

支持向量機(jī)SVM 是一種通用的學(xué)習(xí)機(jī)，在分類(lèi)和回歸問(wèn)題上都有較好的性能[9～11]。SVM 作為一種學(xué)習(xí)機(jī)，有非常多的優(yōu)點(diǎn)。比如，由于SVM采用了Mercer核方法，因此SVM 具有非常好的非線性處理能力。而又由于SVM 實(shí)現(xiàn)了Vapnik的結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則，因此SVM 具有良好的泛化能力。SVM 的訓(xùn)練過(guò)程歸結(jié)為求一個(gè)二次凸規(guī)劃問(wèn)題，因此其最優(yōu)解是全局且唯一的。

本文的目的就是將支持向量機(jī)方法應(yīng)用到李群數(shù)據(jù)，提出一種新的李群分類(lèi)器，彌補(bǔ)目前的李群分類(lèi)器在處理多分類(lèi)問(wèn)題上的不足，以及在非線性處理能力方面的不足。由于李群數(shù)據(jù)是用矩陣來(lái)表示的，而SVM 能夠接受的數(shù)據(jù)是矢量數(shù)據(jù)，我們把接受矢量數(shù)據(jù)的高斯核函數(shù)轉(zhuǎn)換為可以接受李群矩陣數(shù)據(jù)的矩陣高斯核函數(shù)。

本文其余部分結(jié)構(gòu)安排如下：第2節(jié)介紹目前已有的兩種李群分類(lèi)器；第3節(jié)介紹基于李群結(jié)構(gòu)數(shù)據(jù)的SVM 方法；第4 節(jié)是實(shí)驗(yàn)與結(jié)果；第5 節(jié)進(jìn)行總結(jié)。

2 李群分類(lèi)器

2.1 李群內(nèi)均值分類(lèi)器

其中，xi是向量或者矩陣，上式中的μ 可看成是與各數(shù)據(jù)點(diǎn)距離之和最小的點(diǎn)。因?yàn)镽d是一個(gè)歐氏空間，而歐氏距離就是兩點(diǎn)實(shí)際距離，μ 就是歐氏空間中到各數(shù)據(jù)點(diǎn)距離之和最小的點(diǎn)，如圖1a所示。因此，式（1）也可寫(xiě)為：

如果d 維流形Md并不是一個(gè)歐氏空間，那么數(shù)據(jù)點(diǎn)之間的距離就不再是歐氏距離，如圖1b所示。樣本點(diǎn)xn到平均值點(diǎn)μ 的距離是弧線d（μ，xn），而圖1a中樣本點(diǎn)xn到平均值點(diǎn)μ 的距離就是直線d（μ，xn）＝‖μ-xn‖。

Figure 1 Different distance distribution diagram圖1 不同距離分布示意圖

李群內(nèi)均值思想就是將流形空間上的某一類(lèi)的點(diǎn)集求平均，得到該類(lèi)的一個(gè)平均值點(diǎn)。新的樣本點(diǎn)到哪類(lèi)平均值點(diǎn)的距離近，該樣本點(diǎn)就歸為哪類(lèi)，而對(duì)于距離度量的求解，主要是將李群流形空間上的樣本點(diǎn)投影到測(cè)地線上，運(yùn)用李代數(shù)來(lái)求解兩點(diǎn)之間的距離，然后通過(guò)對(duì)數(shù)映射求出李群空間中兩點(diǎn)間的實(shí)際距離。此時(shí)：

其中，G 代表李群，d（·，·）表示括號(hào)內(nèi)兩個(gè)點(diǎn)之間的測(cè)地線距離，具體推導(dǎo)過(guò)程可以參考文獻(xiàn)[8]?，F(xiàn)在的問(wèn)題是需要尋找到滿足上述條件的x∈G，文獻(xiàn)[7]給出了采用梯度下降法求解μ 的過(guò)程，李群內(nèi)均值法由算法1給出。

算法1 李群內(nèi)均值算法

輸出 μi，i＝1，2.…，c，即每個(gè)分類(lèi)的內(nèi)均值。

過(guò)程

2.2 李群Fisher分類(lèi)器

標(biāo)準(zhǔn)的Fisher判別分析是將樣本點(diǎn)投影到一個(gè)比樣本維數(shù)更低的超平面上，使得各類(lèi)別之間的類(lèi)間散度盡可能大，同時(shí)各類(lèi)的類(lèi)內(nèi)散度盡可能小。Fisher判別分析的準(zhǔn)則函數(shù)為：

在實(shí)際問(wèn)題中，很多樣本都位于一個(gè)李群上，每個(gè)樣本點(diǎn)都可以看成某個(gè)李群上的點(diǎn)，對(duì)非歐空間的李群上的樣本點(diǎn)，標(biāo)準(zhǔn)的Fisher 投影就不能很好地處理。李群Fisher投影的目的就是在李群流形上尋找一條測(cè)地線，將所有的樣本向這條測(cè)地線上投影，使投影后的新樣本具有盡量大的類(lèi)間散度和盡量小的類(lèi)內(nèi)散度。而測(cè)地線的求解是將李群上的樣本點(diǎn)映射到對(duì)應(yīng)的李代數(shù)空間，在線性的李代數(shù)空間給出求解近似的李群Fisher投影測(cè)地線，李群Fisher算法由算法2給出，具體的推導(dǎo)過(guò)程參考文獻(xiàn)[8]。

算法2 李群Fisher算法

步驟1 對(duì)每個(gè)李群樣本xij去做李代數(shù)映射：Mij＝log（xij）；

步驟3 計(jì)算Sb和Sw；

步驟4 求解Sbv＝λSwv，得到的v可按exp（tv），t∈R 生成李群Fisher的測(cè)地線；

步驟5 對(duì)測(cè)試樣本T 的類(lèi)別通過(guò)下式進(jìn)行判別：

3 基于李群數(shù)據(jù)的SVM

本節(jié)提出一種基于李群數(shù)據(jù)的SVM。首先介紹一種提取李群數(shù)據(jù)的方法，然后提出一種可以處理矩陣數(shù)據(jù)的核函數(shù)，最后介紹基于李群數(shù)據(jù)的SVM 方法。

3.1 李群數(shù)據(jù)處理

對(duì)手寫(xiě)體數(shù)字樣本的分類(lèi)主要在于對(duì)樣本相似性度量的定義，由于要處理的手寫(xiě)體數(shù)字是非線性結(jié)構(gòu)，而非線性結(jié)構(gòu)樣本的分類(lèi)往往不能用一個(gè)簡(jiǎn)單的線性分離來(lái)完成。李群本身是流形，支持非線性數(shù)據(jù)，因此用李群來(lái)處理非線性結(jié)構(gòu)數(shù)據(jù)很合適。

3.2 矩陣高斯核函數(shù)

在SVM 中，通常用一個(gè)潛在的非線性核函數(shù)K（x，x′）把樣本數(shù)據(jù)映射到一個(gè)高維特征空間，其中，x和x′是兩個(gè)同維的矢量。最為常用的高斯函數(shù)定義如下：

其中，γ＞0是核參數(shù)。眾所周知，高斯核函數(shù)的作用可以等同于一個(gè)相似性度量，衡量了x 和x′兩個(gè)樣本點(diǎn)之間的相似性。

3.1 節(jié)的數(shù)據(jù)轉(zhuǎn)換過(guò)程把矢量數(shù)據(jù)轉(zhuǎn)換為矩陣數(shù)據(jù)，因此必須要設(shè)計(jì)一個(gè)核函數(shù)來(lái)衡量李群矩陣數(shù)據(jù)的相似性。在李群微分流形上的任意兩個(gè)李群矩陣z和z′之間的測(cè)地線距離可以表示為[7]：

其中，‖·‖F(xiàn)稱(chēng)為是Frobenius范數(shù)[13]。此測(cè)地線距離可以很好地表示兩個(gè)矩陣之間的相似性。如果d（z，z′）的值較小，則z 和z′比較相近且相似；反之，如果d（z，z′）的值較大，則z和z′離得比較遠(yuǎn)且不相似。由此，可以構(gòu)造如下的矩陣高斯核函數(shù)：

定理1 式（8）所示的矩陣高斯核函數(shù)是一種可容許的Mercer核函數(shù)。

定理1的結(jié)論顯然是成立的，由式（6）和式（8）之間的關(guān)系就可以得到。因此，定理1保證采用了矩陣高斯核函數(shù)的SVM 可以應(yīng)用于李群數(shù)據(jù)。

3.3 基于李群數(shù)據(jù)的支持向量機(jī)

對(duì)于輸入的兩類(lèi)手寫(xiě)體圖像數(shù)據(jù)，利用3.1節(jié)的方法構(gòu)造成李群數(shù)據(jù)。對(duì)于多類(lèi)問(wèn)題，可以簡(jiǎn)化為多個(gè)兩類(lèi)問(wèn)題，每個(gè)兩類(lèi)問(wèn)題區(qū)分兩個(gè)不同數(shù)字的樣本。可以采用一對(duì)多、一對(duì)一以及決策樹(shù)[14]的方法來(lái)實(shí)現(xiàn)多分類(lèi)。下面僅討論兩類(lèi)問(wèn)題的實(shí)現(xiàn)。

其中，αi是Lagrange乘子，C＞0是正則參數(shù)。

分類(lèi)函數(shù)可以表示為：

其中，sgn（）· 表示符號(hào)函數(shù)，對(duì)于0＜αj＜C，可以計(jì)算閾值如下：

4 實(shí)驗(yàn)與結(jié)果

實(shí)驗(yàn)采用的數(shù)據(jù)是從http：／／yann.lecun.com／exdb／mnist／下載的MNIST 手寫(xiě)體數(shù)字集。MNIST 是美國(guó)著名數(shù)據(jù)集NIST（國(guó)家標(biāo)準(zhǔn)技術(shù)局）的子集，是模式識(shí)別領(lǐng)域用來(lái)做對(duì)比實(shí)驗(yàn)的數(shù)據(jù)集之一。該數(shù)據(jù)集中共有60 000個(gè)訓(xùn)練樣本和10 000個(gè)測(cè)試樣本，每個(gè)樣本是20×20的矩陣圖像。對(duì)原始圖像進(jìn)行了二值化預(yù)處理，根據(jù)文獻(xiàn)[8]這里的二值化閾值也設(shè)置為100。為了產(chǎn)生李群矩陣數(shù)據(jù)，需要在二值化后的圖像上隨機(jī)采樣k個(gè)點(diǎn)，使這k 個(gè)點(diǎn)都位于代表手寫(xiě)體數(shù)字像素上[8]。圖2是對(duì)數(shù)字1和9在不同k 的設(shè)定下所產(chǎn)生的點(diǎn)云圖。點(diǎn)云數(shù)越多越能夠反映數(shù)字的形狀，但是所獲得的樣本維數(shù)會(huì)越高。本文算法要考慮兩個(gè)參數(shù)：核參數(shù)γ和正則因子C。在訓(xùn)練集上采用10 倍交叉驗(yàn)證得到最優(yōu)參數(shù)，其中，正則因子的取值范圍為｛2-1，20，…，24｝，矩陣高斯核參數(shù)的取值范圍為｛2-10，2-9，…，2-6｝。根據(jù)最大交叉驗(yàn)證識(shí)別率選擇最優(yōu)參數(shù)，并獲得最終的訓(xùn)練模型。此外，我們還考慮了點(diǎn)云數(shù)量對(duì)識(shí)別率的影響，點(diǎn)云數(shù)的取值集合為｛5，10，15，2.，25，30，35，40，45，50｝，由于點(diǎn)云是隨機(jī)產(chǎn)生的，重復(fù)5次實(shí)驗(yàn)。

Figure 2 Generated point cloud diagram圖2 產(chǎn)生的點(diǎn)云示意圖

這里共設(shè)計(jì)了三組實(shí)驗(yàn)。第一組是區(qū)分?jǐn)?shù)字1和9，第二組是區(qū)分?jǐn)?shù)字1、7和9，第三組是區(qū)分?jǐn)?shù)字1、2、7和9。第一組實(shí)驗(yàn)和文獻(xiàn)[8]的設(shè)置一樣，對(duì)比算法包括李群Fisher算法、李群內(nèi)均值算法和本文算法，其實(shí)驗(yàn)結(jié)果如圖3所示。第二、三組實(shí)驗(yàn)對(duì)比了李群內(nèi)均值算法和本文算法。第二組實(shí)驗(yàn)結(jié)果如圖4所示，第三組實(shí)驗(yàn)結(jié)果如圖5所示。這三幅圖均反映了算法識(shí)別率隨著點(diǎn)云數(shù)變化趨勢(shì)。從圖3可以很清楚地看到，SVM 算法的識(shí)別率遠(yuǎn)遠(yuǎn)好于李群Fisher分類(lèi)器和李群內(nèi)均值分類(lèi)器。圖4 和圖5 也反映了SVM 的優(yōu)越性。一般來(lái)說(shuō)，隨著點(diǎn)云數(shù)的增加，識(shí)別率也是增加的。但是，我們也看到識(shí)別率和點(diǎn)云數(shù)的變化并不是正比線性關(guān)系。而且，點(diǎn)云數(shù)的增加會(huì)增加計(jì)算復(fù)雜度，因此并不是點(diǎn)云數(shù)越多越好。我們列出多分類(lèi)時(shí)點(diǎn)云數(shù)k＝30的實(shí)驗(yàn)結(jié)果，如表1所示。從表1可以看出，本文的算法是明顯占優(yōu)的。

Table 1 Classification performance of different approaches表1 不同方法識(shí)別率對(duì)比表 %

5 結(jié)束語(yǔ)

本文提出了一種基于SVM 的李群分類(lèi)器，以彌補(bǔ)目前的李群分類(lèi)器在處理多分類(lèi)問(wèn)題上，以及在非線性處理能力方面的不足。由于李群數(shù)據(jù)是用矩陣來(lái)表示的，而SVM 能夠接受的數(shù)據(jù)是矢量數(shù)據(jù)，我們把接受矢量數(shù)據(jù)的高斯核函數(shù)轉(zhuǎn)換為可以接受李群矩陣數(shù)據(jù)的矩陣高斯核函數(shù)，同時(shí)給出了矩陣高斯核函數(shù)是允許Mercer核的定理。實(shí)驗(yàn)結(jié)果表明了所提方法的可行性和有效性。

但是，隨著樣本類(lèi)別的增加，算法的識(shí)別率是下降的。這一點(diǎn)是我們今后工作的重點(diǎn)。此外，點(diǎn)云的生成是隨機(jī)的，今后會(huì)考慮按幾何特征來(lái)提取點(diǎn)云，如輪廓邊緣提取等。今后還會(huì)嘗試?yán)镁仃嚪诸?lèi)方法來(lái)處理李群矩陣數(shù)據(jù)，如MatLSSVM、MatFLSSVM[15]、MatPCA 和MatFLDA[16]。

[1]Li F Z，Qian X P，Xie L，et al.Machine learning theory and its applications[M].Hefei：University of Science and Technology of China Press，2009.（in Chinese）

[2]Tuzel O，Porikliand F，Meer P.Learning on Lie groups for invariant detection and tracking[C]∥Proc of CVPR'08，2.08：1-8.

[3]Bayro-Corrochano E，Ortegon-Aguilar J.Lie algebra template tracking[C]∥Proc of ICPR'04，2.04：56-59.

[4]Tuzel O，Porikliand F，Meer P.Human detection via classification on riemannian manifolds[C]∥Proc of CVPR'07，2.07：1-8.

[5]Lin D H，Grimson E，F(xiàn)isher J.Learning visual flows：A Lie algebraic approach[C]∥Proc of CVPR'09，2.09：747-754.

[6]Hartigan J A，Wong M A.A K-means clustering algorithm[J].Journal of the Royal Statistical Society，Series C（Applied Statistics），1979，2.（1）：100-108.

[7]Fletcher P T，Lu C L，Joshi S.Statistics of shape via principal geodesic analysis on Lie groups[C]∥Proc of CVPR'03，2.03：95-101.

[8]Gao C，Li F Z.Research on Lie group means learning algorithm[C]∥Proc of CRSSC-CWI-CGrC，2011：1.（in Chinese）

[9]Zhang L.Research on support vector machines and kernel methods[D].Xi'an：Xidian University，2002.（in Chinese）

[10]Burge C J C.A tutorial on support vector machines for pattern recognition[J].Data Mining and Knowledge Discovery，1998，2.2）：121-167.

[11]Cristianini N.An introduction to support vector machines and other kernal-based methods[M].translated by Li G Z，Wang M，Zeng H J.Beijing：Publishing House of Electronic Industry，2004.

[12]Yarlagadda P，Ozcanli O，Mundy J.Lie group distance based generic 3-d vehicle classification[C]∥Proc of ICPR'08，2008：1-4.

[13]Cheng Y P，Zhang K Y，Xu Z.Matrix theory[M].Third edition.Xi'an： Northwestern Polytechnical University Press，2006.（in Chinese）

[14]Zhang L，Zhou W D，Su T T，et al.Decision tree support vector machine[J].International Journal on Artificial Intelligence Tools，2007，16（1）：1-16.

[15]Wang Z，Chen S C.New least squares support vector machines based on matrix patterns[J].Neural Processing Letters，2007（26）：41-56.

[16]Chen S C，Zhu Y L，Zhang D Q，et al.Feature extraction approaches based on matrix pattern：MatPCA and MatFLDA[J].Pattern Recognition Letters，2005（26）：1157-1167.

附中文參考文獻(xiàn)：

[1]李凡長(zhǎng)，錢(qián)旭培，謝琳，等.機(jī)器學(xué)習(xí)理論及應(yīng)用[M].合肥：中國(guó)科學(xué)技術(shù)大學(xué)出版社，2009.

[8]高聰，李凡長(zhǎng).李群均值學(xué)習(xí)算法[C]∥第十一屆中國(guó)Rough集與軟計(jì)算學(xué)術(shù)會(huì)議、第五屆中國(guó)Web智能學(xué)術(shù)研討會(huì)及第五屆中國(guó)粒計(jì)算學(xué)術(shù)研討會(huì)聯(lián)合學(xué)術(shù)會(huì)議，2011：1.

[9]張莉.支撐矢量機(jī)與核方法研究[D].西安：西安電子科技大學(xué)，2002.

[11]克里斯特安尼.支持向量機(jī)導(dǎo)論[M].李國(guó)正，王猛，曾華軍，譯.北京：電子工業(yè)出版社，2004.

[13]程云鵬，張凱院，徐仲.矩陣論[M].第三版.西安：西北工業(yè)大學(xué)出版社，2006.