基于边缘Fisher分析的主动学习方法

李慧思，洪振杰

(温州大学数学与信息科学学院，浙江温州 325035)

基于边缘Fisher分析的主动学习方法

李慧思，洪振杰†

(温州大学数学与信息科学学院，浙江温州 325035)

将边缘Fisher分析引入到MAED算法中，通过构建类内紧凑图和类间分离图，来描述样本点间的几何特征，形成一种新的主动学习方法．该算法利用两个图同时对流形数据局部结构和类鉴别信息进行建模，从而更好地保持了数据的内在几何特征．基于图像数据集的实验结果，证实了该方法的有效性．

边缘Fisher分析；类内紧凑图；类间分离图；主动学习；图像分类

在信息处理任务中，图像分类是一项很重要的工作．很多有监督图像分类系统都是建立在统计模型的基础上，首先用户需要手动标注大量的图像样本点，然后根据这些带标签的样本点训练出一个分类模型．在实际运用中，标注这些图像样本点往往需要花费大量的人力物力，因此分类系统很难获得足够的带标签的样本进行训练．在训练样本很少的情况下，分类器的性能可能会产生极大的恶化．如何获得整个数据集里最具代表性的一个子集，使得在注释图像样本上花费最少精力，并训练出一个好的分类器，成为图像分类任务中的一个关键问题．为了解决这个问题，主动学习已经成为机器学习和模式识别里的一个研究热点．

目前，研究人员已经做了很多主动学习的研究，比如支持向量机主动学习（Support Vector Machine active learning, SVMactive）[1]和直推式实验设计（Transductive Experimental Design, TED）算法①Yu K, Bi J B, Tresp V. Active learning via transductive experimental design [C] // Proc. 23rd international conference on Machine learning (ICML’ 06). New York, 2006: 1081-1088.，然而这些方法都没有把数据样本点的几何结构考虑进去．蔡登等人[2]基于TED算法提出了一种新的主动学习算法用于文本分类，称为流形适应性实验设计算法（Manifold Adaptive Experimental Design，MAED）．这种算法在流形适应性核空间中进行主动学习，充分考虑了数据间的内在流形结构．

图形是用于数据挖掘和模式识别的一项强大的工具，而基于图方法的性能在很大程度上依赖于构造图的质量．MAED算法需要一个固定邻居的大小来构造一个邻接图，因此邻居的大小很大程度上影响了MAED算法的效果．

在本文中，我们将边缘Fisher分析（Marginal Fisher Analysis, MFA）[3-4]引入到MAED算法中，通过构建类内紧凑图和类间分离图，来更好地描述样本点之间的几何特征，从而形成一种新颖的主动学习方法．这种新的算法利用两个图来同时对流形数据的局部结构和类鉴别信息进行建模，从而更好地保持数据的内在几何特征．

1 相关研究

1.1 边缘Fisher分析（MFA）

最近，Yan等人在图嵌入框架的基础上提出了一种新的流形学习算法——边缘Fisher分析（MFA）[5]．该算法利用样本的类别信息以及样本之间的欧氏距离来构建类内紧凑图和类间分离图，进而分别描述同类样本之间的连接性和异类样本之间的分离性．将样本数据投影到低维空间后，使得同类的1k近邻样本之间的距离尽可能小，不同类别的2k近邻样本之间的距离尽可能大．MFA的关键算法步骤如下[6]：

在类内紧凑图中，cS用来描述两点之间的连接性，定义为：

1.2 最优化实验设计（OED）和直推式实验设计（TED）

在统计学里，主动学习又被称为实验设计．最优化实验设计（OED）[7]是为了减少方差参数化的模型．基于OED研究，Yu等提出了TED算法①Yu K, Zhu S H , Xu W, et al. Non-greedy active learning for text categorization using convex transductive experimental design [C] // Proc. 31st Ann. Int’ l ACM SIGIR conf. research and development in information retrieval (SIGIR’ 08). New York, 2008: 635-642.，这种算法旨在最小化学习函数f的预期平方误差．

对任意的样本x，假设ˆˆwTy x=是它的预测值．则整个数据集X的平均预测误差就是：

1.3 MAED算法：

在这里I是一个单位矩阵，K是核矩阵，M是一个半正定矩阵，0λ≥是调节函数光滑度的一个常数．

2 基于MFA与MAED算法的主动学习

在MFA算法与MAED算法基础上，我们提出一种新颖的主动学习方法，称之为边缘实验设计（Fisher Experimental Design, FED）．这种算法通过构建类内紧凑图和类间分离图，来更好地描述样本点之间的几何特征，从而形成一种新颖的主动学习方法．

2.1 基于MFA的权重矩阵

MAED算法的性能依赖于权重矩阵M的定义，由此，基于数据的范数诱导核的变形，反映了数据点的本质几何特性．图中权重矩阵的选择有很多，而且不同的图产生不同的权重矩阵．

基于减式MFA的新的权重矩阵算法步骤如下：

首先，构造类内紧凑图和类间分离图[4]．设给定n个数据集其中，是高维数据．设G和PG分别表示2个具有n个顶点的无向图：类内紧凑图和类间分离图，其中，顶点i对应于样本数据点ix．

在类内紧凑图G中，对于任意数据点ix，如果ix和jx具有相同的类别，且满足jx是ix的1k-最近邻居，则在数据点ix和jx之间创建一条边．

此权重矩阵利用两个图（即类内紧凑图和类间分离图）来同时对流形数据的局部结构和类别信息进行建模，对数据的几何流形有着更为精确地描述．同时，基于目标函数为减式的权重矩阵又可以避免奇异性带来的困扰，减少计算难度．

2.2 基于MFA的主动学习算法

输出：依据样本点重要性排列的样本点的新顺序．

相比于MAED算法，我们提出的主动学习算法有着突出的优势：基于目标函数为减式的MFA，通过构建的类内紧凑图和类间分离图来确定新的权重矩阵，此权重矩阵不仅能更精确地描述数据之间的几何流形特征，还能避免奇异性带来的困扰，减少计算难度．

3 实验部分

将在四个基准图像数据集上进行试验，这些数据集分别是美银证券数据集（BANC）[10]，智能交通系统（ITS）数据集[11]，ORL数据集[12]和美国邮政总局的手写数字数据集USPS[13]．

3.1 数据集描述和实验设置

BANCA人脸数据集包含了52个人脸的520幅图像（每个人有10幅图像）．数据集里的所有图像都被人为地规范化为46×56像素．

ORL数据集包括40个人的400幅图像，其中每个人有10个不同的图像．这个数据集里的每幅图像都被裁剪成32×18像素的．

USPS数据集里的图像均是8位灰度图像，这些图像的类别从0 – 9，每个类别有1 100个数据点．这个数据集里的每个数据点都是一个16×16的形象手写数字，然后被转换成一个256维的向量．我们随机地从每类里面挑选250个数据点．因此，USPS数据集包含了10个类别的2 500个数据点．

ITS数据集包含了分属两个类别的2 000幅图像．其中1 000幅图像是关于人类行走或者跑步的，另外1 000幅图像则是关于一个常见场景图像道路而没有人类活动．每个数据点都是一张被裁剪成32×16的灰度图像，然后又被转换成一个512维的向量．

在实验中，利用10-折交叉验证法进行评估比较计算．给定一个数据集，把它随机分割成10个大小相等的子集．对于第k个子集，其它9个子集是作为训练集trainX，且第k个子集是用作测试数据testX．

将FED算法与1-最近邻算法（1-NN）、随机样本法和MAED算法进行比较．对于MAED和FED算法，根据训练集trainX中每个样本点的重要性进行排序．然后选择训练数据集里一个给定的部分（0.α），并且假设它们的类别标签都是已知的，其中α从1到9进行变化．最后，这些挑选的带标签的训练数据被用作训练1-NN分类器，训练出的分类器用于对测试集testX进行分类．随机样本法，就是随机地在所选择的训练数据集里挑选一个给定的部分（0.α），并且假设它们的类别标签都是已知的，我们就用这种方法作为主动学习的基准．1-NN算法知道所有训练集trainX的类别标签，然后利用训练集trainX对测试集testX进行训练．

3.2 实验结果分析

图1 – 4中给出了四个数据集中四种主动学习算法的平均准确率．

根据图1中所示，可以看出在BANC数据集中，当2α≤时，FED、MAED和1-最近邻算法有着很相近的分类结果；当3α≥时，FED算法比MAED算法分类效果好，同时，MAED算法又比随机样本法优秀．

图2中给出了数据集ORL中四种算法的分类准确率．可以看出，当2α＜和8α＞时，FED的分类准确率非常贴近于MAED算法．特别地，当5α=时， FED算法明显优越于MAED．在所有的算法中，随机样本法的分类准确率是最低的．

图3中所示的USPS数据集中，在8α＜时，FED算法显然优于MAED算法，并且MAED算法在6α＜时比随机样本法优秀，之后却表现得比随机样本法差．

图4所示的ITS数据集中，FED算法优秀于其他两种算法．尤其当6α=时，FED算法的分类准确率比MAED高出约3个百分点．

总的来说，1-最近邻算法在所有的数据集中分类效果是最优的，这正是由于在1-最近邻算法中所有数据点都是带标签的．

4 小 结

通过构建类内紧凑图和类间分离图来确定新的权重矩阵，此权重矩阵不仅可以避免奇异性带来的困扰，更能精确地对数据的几何流形结构进行描述，从而提升主动学习的效率．我们提出的FED算法优点在于：（1）建立了更加适应数据集几何结构的图；（2）新建的类内紧凑图和类间分离图有很强的区分性，利于选择重要的样本点．实验证明FED算法在图像数据集ORL、ITS、USPS和BANC上显示出了很好的分类效果．

图1 BANC数据集上的分类准确率

图3 USPS数据集上的分类准确率

图2 ORL数据集上的分类准确率

图4 ITS数据集上的分类准确率

[1] Tong S, Koller D. Support vector machine active learning w ith application to text classification [J]. J. Machine Learning Research, 2001, 2: 45-66.

[2] Cai D, He X F. Manifold adaptive experimental design for text categorization [J]. IEEE Transactions on Know ledge and Data Engineering, 2012, 24(4): 707-719.

[3] 朱振凤, 范丽亚. 基于间隔Fisher分析的几种改进算法[J]. 聊城大学学报: 自然科学版, 2012, 25(4): 5-10.

[4] 李森, 刘希玉. MFASSC: 基于间隔Fisher分析的半监督聚类方法[J]. 计算机应用研究, 2012, 29(11): 4093-4096.

[5] Yan S C, Xu D, Zhang B Y, et al. Graph embedding and extension: a general framework for dimensionality reduction [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(1): 40-51.

[6] 黄可坤. 基于正则化边界Fisher分析和稀疏表示分类的人脸识别方法[J]. 计算机应用, 2013, 33(6): 1723-1726.

[7] Atkinson A C, Donev A N. Optimum experimental designs, with SAS [M]. Oxford: Oxford Univ. Press, 2007: 23-30.

[8] Chung F R K. Spectral graph theory [M]. Providence, Rhode Island: American Mathematical Society, 1997: 2-14.

[9] Hastie T, Tibshirani R, Friedman J. The elements of statistical learning: data m ining, inference, and prediction [J]. The mathematical Inteligencer, 2005, 27(2): 83-85.

[10] Kim T K, Stenger B, Kittler J, et al. Incremental linear discriminant analysis using sufficient spanning sets and its applications [J]. International Journal of Computer Vision, 2011, 91(2): 216-232.

[11] Cao X B, Qiao H, Keane J. A low-cost pedestrian-detection system with a single optical camera [J]. IEEE Trans. on Intelligent Transportation Systems, 2008, 9(1): 58-67.

[12] Olivetti & Oracle Research Laboratory. The olivetti & oracle research laboratory face database of faces [EB/OL]. [2013-05-01]. http://www.camorl.co.uk/facedatabase.htm l.

[13] Hull J. A database for handw ritten text recognition research [J]. IEEE Trans. Pattern Analysis and Machine Intelligence, 1998, 16(5): 550-554.

On Active Learning Method Based on the Margin Fisher Analysis

LI Huisi, HONG Zhenjie
(School of Mathematics and Information Science, Wenzhou University, Wenzhou, China 325035)

In this paper, a new active learning method is put forward by leading margin Fisher Analysis into MAED algorithm, and describing the geometric structure of samples with constructing within-class compact and inter-class separate graphs. This algorithm uses two graphs modeling the local structure of the manifold data and discrim ination information of the dataset simultaneously, which can keep the intrinsic geometric structure of the data better. This method is proved effectively based on the experimental results of the image data set.

Margin Fisher Analysis; Within-class Compact Graph; Inter-class Separate Graph; Active Learning; Image Classification

TP391.41

：A

：1674-3563(2014)03-0055-08

10.3875/j.issn.1674-3563.2014.03.009 本文的PDF文件可以从xuebao.wzu.edu.cn获得

(编辑：封毅)

2014-01-06

温州大学研究生创新基金(31606036010184)

李慧思(1989- )，女，河南濮阳人，硕士研究生，研究方向：应用分析与最优化理论．† 通讯作者：hong@wzu.edu.cn