一种新的李群分类器在手写体数字中的应用＊

王晓乾，张 莉，何书萍，杨季文，李凡长

（苏州大学计算机科学与技术学院，江苏 苏州 215006）

1 引言

手写体数字识别一直是模式识别领域的一个重要研究课题，有着极为广泛的应用前景。随着计算机技术和数字图像处理技术的飞速发展，数字识别在大规模数据统计、邮件分拣、财务、税务、金融领域中都有着广泛应用。因此，手写数字的识别研究有着重大的实际意义，会产生巨大的社会和经济效益。

李群是目前学术界公认的用于研究学习问题的一套完善的理论工具，很多物理学家和化学家开始广泛使用李群理论研究相关领域的数据[1]。李群理论在流形学习中表现出了强大的优势，文献[2，3]研究了视觉跟踪问题中变换矩阵李群及其相应李代数的表示，文献[4]使用协方差算子来构造李群数据并用于行人检测，文献[5]成功应用李群李代数方法表示变换过程，以此来学习动态视觉流，效果很好。

目前，针对李群数据所设计的李群分类器还不是很多，而能够实用的就更加少了。这里介绍两种可以应用到手写体数字识别上的李群分类器：李群内均值分类器[6，7]和李群Fisher分类器[8]。李群内均值分类器是先计算李群的内均值，然后再根据和均值的远近来分类样本，能够处理多类问题。但是，其对多类问题处理时，性能不是很好。李群Fisher分类器是Fisher判别分析在李群数据上的推广，可以在投影后获得更好的可分性。但是，文献[8]并没有将该分类器推广到多分类问题上。

支持向量机SVM 是一种通用的学习机，在分类和回归问题上都有较好的性能[9～11]。SVM 作为一种学习机，有非常多的优点。比如，由于SVM采用了Mercer核方法，因此SVM 具有非常好的非线性处理能力。而又由于SVM 实现了Vapnik的结构风险最小化原则，因此SVM 具有良好的泛化能力。SVM 的训练过程归结为求一个二次凸规划问题，因此其最优解是全局且唯一的。

本文的目的就是将支持向量机方法应用到李群数据，提出一种新的李群分类器，弥补目前的李群分类器在处理多分类问题上的不足，以及在非线性处理能力方面的不足。由于李群数据是用矩阵来表示的，而SVM 能够接受的数据是矢量数据，我们把接受矢量数据的高斯核函数转换为可以接受李群矩阵数据的矩阵高斯核函数。

本文其余部分结构安排如下：第2节介绍目前已有的两种李群分类器；第3节介绍基于李群结构数据的SVM 方法；第4 节是实验与结果；第5 节进行总结。

2 李群分类器

2.1 李群内均值分类器

其中，xi是向量或者矩阵，上式中的μ 可看成是与各数据点距离之和最小的点。因为Rd是一个欧氏空间，而欧氏距离就是两点实际距离，μ 就是欧氏空间中到各数据点距离之和最小的点，如图1a所示。因此，式（1）也可写为：

如果d 维流形Md并不是一个欧氏空间，那么数据点之间的距离就不再是欧氏距离，如图1b所示。样本点xn到平均值点μ 的距离是弧线d（μ，xn），而图1a中样本点xn到平均值点μ 的距离就是直线d（μ，xn）＝‖μ-xn‖。

Figure 1 Different distance distribution diagram图1 不同距离分布示意图

李群内均值思想就是将流形空间上的某一类的点集求平均，得到该类的一个平均值点。新的样本点到哪类平均值点的距离近，该样本点就归为哪类，而对于距离度量的求解，主要是将李群流形空间上的样本点投影到测地线上，运用李代数来求解两点之间的距离，然后通过对数映射求出李群空间中两点间的实际距离。此时：

其中，G 代表李群，d（·，·）表示括号内两个点之间的测地线距离，具体推导过程可以参考文献[8]。现在的问题是需要寻找到满足上述条件的x∈G，文献[7]给出了采用梯度下降法求解μ 的过程，李群内均值法由算法1给出。

算法1 李群内均值算法

输出 μi，i＝1，2.…，c，即每个分类的内均值。

过程

2.2 李群Fisher分类器

标准的Fisher判别分析是将样本点投影到一个比样本维数更低的超平面上，使得各类别之间的类间散度尽可能大，同时各类的类内散度尽可能小。Fisher判别分析的准则函数为：

在实际问题中，很多样本都位于一个李群上，每个样本点都可以看成某个李群上的点，对非欧空间的李群上的样本点，标准的Fisher 投影就不能很好地处理。李群Fisher投影的目的就是在李群流形上寻找一条测地线，将所有的样本向这条测地线上投影，使投影后的新样本具有尽量大的类间散度和尽量小的类内散度。而测地线的求解是将李群上的样本点映射到对应的李代数空间，在线性的李代数空间给出求解近似的李群Fisher投影测地线，李群Fisher算法由算法2给出，具体的推导过程参考文献[8]。

算法2 李群Fisher算法

步骤1 对每个李群样本xij去做李代数映射：Mij＝log（xij）；

步骤3 计算Sb和Sw；

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

步骤5 对测试样本T 的类别通过下式进行判别：

3 基于李群数据的SVM

本节提出一种基于李群数据的SVM。首先介绍一种提取李群数据的方法，然后提出一种可以处理矩阵数据的核函数，最后介绍基于李群数据的SVM 方法。

3.1 李群数据处理

对手写体数字样本的分类主要在于对样本相似性度量的定义，由于要处理的手写体数字是非线性结构，而非线性结构样本的分类往往不能用一个简单的线性分离来完成。李群本身是流形，支持非线性数据，因此用李群来处理非线性结构数据很合适。

3.2 矩阵高斯核函数

在SVM 中，通常用一个潜在的非线性核函数K（x，x′）把样本数据映射到一个高维特征空间，其中，x和x′是两个同维的矢量。最为常用的高斯函数定义如下：

其中，γ＞0是核参数。众所周知，高斯核函数的作用可以等同于一个相似性度量，衡量了x 和x′两个样本点之间的相似性。

3.1 节的数据转换过程把矢量数据转换为矩阵数据，因此必须要设计一个核函数来衡量李群矩阵数据的相似性。在李群微分流形上的任意两个李群矩阵z和z′之间的测地线距离可以表示为[7]：

其中，‖·‖F称为是Frobenius范数[13]。此测地线距离可以很好地表示两个矩阵之间的相似性。如果d（z，z′）的值较小，则z 和z′比较相近且相似；反之，如果d（z，z′）的值较大，则z和z′离得比较远且不相似。由此，可以构造如下的矩阵高斯核函数：

定理1 式（8）所示的矩阵高斯核函数是一种可容许的Mercer核函数。

定理1的结论显然是成立的，由式（6）和式（8）之间的关系就可以得到。因此，定理1保证采用了矩阵高斯核函数的SVM 可以应用于李群数据。

3.3 基于李群数据的支持向量机

对于输入的两类手写体图像数据，利用3.1节的方法构造成李群数据。对于多类问题，可以简化为多个两类问题，每个两类问题区分两个不同数字的样本。可以采用一对多、一对一以及决策树[14]的方法来实现多分类。下面仅讨论两类问题的实现。

其中，αi是Lagrange乘子，C＞0是正则参数。

分类函数可以表示为：

其中，sgn（）· 表示符号函数，对于0＜αj＜C，可以计算阈值如下：

4 实验与结果

实验采用的数据是从http：／／yann.lecun.com／exdb／mnist／下载的MNIST 手写体数字集。MNIST 是美国著名数据集NIST（国家标准技术局）的子集，是模式识别领域用来做对比实验的数据集之一。该数据集中共有60 000个训练样本和10 000个测试样本，每个样本是20×20的矩阵图像。对原始图像进行了二值化预处理，根据文献[8]这里的二值化阈值也设置为100。为了产生李群矩阵数据，需要在二值化后的图像上随机采样k个点，使这k 个点都位于代表手写体数字像素上[8]。图2是对数字1和9在不同k 的设定下所产生的点云图。点云数越多越能够反映数字的形状，但是所获得的样本维数会越高。本文算法要考虑两个参数：核参数γ和正则因子C。在训练集上采用10 倍交叉验证得到最优参数，其中，正则因子的取值范围为｛2-1，20，…，24｝，矩阵高斯核参数的取值范围为｛2-10，2-9，…，2-6｝。根据最大交叉验证识别率选择最优参数，并获得最终的训练模型。此外，我们还考虑了点云数量对识别率的影响，点云数的取值集合为｛5，10，15，2.，25，30，35，40，45，50｝，由于点云是随机产生的，重复5次实验。

Figure 2 Generated point cloud diagram图2 产生的点云示意图

这里共设计了三组实验。第一组是区分数字1和9，第二组是区分数字1、7和9，第三组是区分数字1、2、7和9。第一组实验和文献[8]的设置一样，对比算法包括李群Fisher算法、李群内均值算法和本文算法，其实验结果如图3所示。第二、三组实验对比了李群内均值算法和本文算法。第二组实验结果如图4所示，第三组实验结果如图5所示。这三幅图均反映了算法识别率随着点云数变化趋势。从图3可以很清楚地看到，SVM 算法的识别率远远好于李群Fisher分类器和李群内均值分类器。图4 和图5 也反映了SVM 的优越性。一般来说，随着点云数的增加，识别率也是增加的。但是，我们也看到识别率和点云数的变化并不是正比线性关系。而且，点云数的增加会增加计算复杂度，因此并不是点云数越多越好。我们列出多分类时点云数k＝30的实验结果，如表1所示。从表1可以看出，本文的算法是明显占优的。

Table 1 Classification performance of different approaches表1 不同方法识别率对比表 %

5 结束语

本文提出了一种基于SVM 的李群分类器，以弥补目前的李群分类器在处理多分类问题上，以及在非线性处理能力方面的不足。由于李群数据是用矩阵来表示的，而SVM 能够接受的数据是矢量数据，我们把接受矢量数据的高斯核函数转换为可以接受李群矩阵数据的矩阵高斯核函数，同时给出了矩阵高斯核函数是允许Mercer核的定理。实验结果表明了所提方法的可行性和有效性。

但是，随着样本类别的增加，算法的识别率是下降的。这一点是我们今后工作的重点。此外，点云的生成是随机的，今后会考虑按几何特征来提取点云，如轮廓边缘提取等。今后还会尝试利用矩阵分类方法来处理李群矩阵数据，如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，Fisher 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].合肥：中国科学技术大学出版社，2009.

[8]高聪，李凡长.李群均值学习算法[C]∥第十一届中国Rough集与软计算学术会议、第五届中国Web智能学术研讨会及第五届中国粒计算学术研讨会联合学术会议，2011：1.

[9]张莉.支撑矢量机与核方法研究[D].西安：西安电子科技大学，2002.

[11]克里斯特安尼.支持向量机导论[M].李国正，王猛，曾华军，译.北京：电子工业出版社，2004.

[13]程云鹏，张凯院，徐仲.矩阵论[M].第三版.西安：西北工业大学出版社，2006.