王曉乾，張 莉，何書萍，楊季文，李凡長

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

1 引言

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

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

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

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

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

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

2 李群分類器

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

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

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

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

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

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

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

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

過程

2.2 李群Fisher分類器

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

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

算法2 李群Fisher算法

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

步驟3 計算Sb和Sw；

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

步驟5 對測試樣本T 的類別通過下式進行判別：

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

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

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

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

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

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

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

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

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

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

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

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

對于輸入的兩類手寫體圖像數(shù)據(jù)，利用3.1節(jié)的方法構(gòu)造成李群數(shù)據(jù)。對于多類問題，可以簡化為多個兩類問題，每個兩類問題區(qū)分兩個不同數(shù)字的樣本?？梢圆捎靡粚Χ唷⒁粚σ灰约皼Q策樹[14]的方法來實現(xiàn)多分類。下面僅討論兩類問題的實現(xiàn)。

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

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

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

4 實驗與結(jié)果

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

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

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

Table 1 Classification performance of different approaches表1 不同方法識別率對比表 %

5 結(jié)束語

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

但是，隨著樣本類別的增加，算法的識別率是下降的。這一點是我們今后工作的重點。此外，點云的生成是隨機的，今后會考慮按幾何特征來提取點云，如輪廓邊緣提取等。今后還會嘗試利用矩陣分類方法來處理李群矩陣數(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.

附中文參考文獻：

[1]李凡長，錢旭培，謝琳，等.機器學習理論及應用[M].合肥：中國科學技術(shù)大學出版社，2009.

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

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

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

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