基于MPWPS主动学习的半监督协同分类算法

□刘杨磊

(山西大学计算机与信息技术学院，山西太原030006)

1 引言

半监督学习(Semi－supervised Learning)是模式识别和机器学习的重要研究领域。近几年随着机器学习理论在数据分析和数据挖掘等实际问题中的广泛应用，半监督学习在众多理论和实际应用研究中也获得了长足的发展［1］。半监督学习主要关注如何综合使用有标记样本和未标记样本来获得具有良好性能和泛化能力的学习机器。

目前，常用的半监督学习算法利用有标记样本训练分类器标注未标记样本，来增加标记样本的数量，这样如果未标记样本被错误标注将会影响后续分类器的迭代训练，进而降低最终分类器的预测精度。MPWPS(The Most Possibly Wrong－predicted Sampling)作为一种主动学习算法，在训练过程中选取最大可能预测错误的样本进行标注来扩大有标记样本集，保证了训练集较小的情况下能够获得较高的分类正确率，从而降低构建高性能分类器的代价［2］。因此，本文借鉴MPWPS主动学习的思想，实现半监督分类，来提高算法的性能。

2 背景知识

2.1 半监督学习算法

按照学习目的的不同，大致将半监督学习算法分为半监督聚类［3］、半监督分类和半监督回归，其中半监督聚类和半监督分类是目前研究的热点［4］。半监督分类是从有监督学习的角度出发，当已标签训练样例不足时，如何利用大量未标签样例信息辅助分类器的训练［1］。

在A.Blum和T.Mitchell提出最早的协同训练算法后，很多研究者对其进行了研究并取得了很多进展，使得协同训练成为半监督学习中最重要的风范之一［5］。而 Tri－ training算法［6］是 Zhou 等人提出的一种新的协同训练算法，它使用3个分类器进行训练。Tri－training对属性集和3个分类器所用监督学习算法都没有约束，而且不使用交叉验证，因此适用范围更广、效率更高。

Tri－training算法执行过程如下:

该算法首先对有标记样本集进行可重复取样(Bootstrap Sampling)以获得三个有标记训练集，然后从每个训练集产生一个分类器。在协同训练过程中，各分类器所获得的新标记样本都由其余两个分类器协作提供，具体来说，如果两个分类器对同一个未标记样本的预测相同，则该样本就被认为具有较高的标记置信度，并在标记后被加入第三个分类器的有标记训练集。在对未见样本进行预测时，Tritraining算法不再像以往算法那样挑选一个分类器来使用，而是使用集成学习中经常用到的投票法来将三个分类器组成一个集成来实现对未见样本的预测［3］。

2.2 主动学习算法

主动学习算法(Active Learning)最早由Lewis等人提出，用来解决对样本进行标记代价昂贵或者非常困难的应用问题。主动学习研究是机器学习的重要研究领域之一，与半监督学习有着密切的联系。与被动接收训练数据的学习算法不同，主动学习算法自主选择对学习过程中最有用的样本来请求用户标记，以加快学习过程并提高分类性能［7］。

MPWPS算法是由龙军等人提出的主动学习算法。该算法中，如果某个可能的标签在当前分类器判断下具有非常大的概率是该样本的标签，但通过某种更准确的评估机制判断这个标签不是该样本的标签，则这样的样本优先被采样。MPWPS算法通过采样当前分类器最有可能预测错误的样本从而试图最大限度地减小版本空间。

找出最有可能预测错误的样本，必须要度量当前分类器对于一个样本预测错误的概率，也就是预测标注和真实标注不一致的概率。

为了得出度量公式，考虑分类器对样本xi预测的标注为y，则预测标注为y的概率为1，真实标注为y的概率并不知道，但可以近似的估计。

估计真实标注为y的概率可以通过下述的方式进行。在拥有无标记样本集U的情况下，Pu(y|x)表示分类器预测样本x的标注为y的概率，相应的，1－Puy|x)表示分类器预测样本x的标注不为y的概率。由于分类器不是完全正确的，分类正确率为p，所以Puy|x)中有比例p的部分才是实际应标注为y的，同理1－Puy|x)中也有比例1－p的部分是实际应标注为y的。这样，可以近似地认为Pu(y|x)·p+(1－Pu(y|x)·(1－p)即为真实标注为y的概率。

因此，有公式(1):

当ESi越大时，表明预测标注和真实标注不一致的概率越大。

3 基于MPWPS主动学习的半监督协同分类算法

算法首先利用MPWPS算法在未标记样本中找出M组最有可能预测错误标注的样本，将这M组样本交给专家进行标注，在训练集train中处理这M组样本后再执行Tri－training算法;在Tri－training算法中，首先采用协同训练的方法训练三个分类器，再采用投票法将三个分类器组成一个集成来实现对未标记样本的标注。

基于MPWPS主动学习的半监督协同分类算法的算法流程如下:

输入参数:有标记样本集L，无标记样本集U，测试集test，采样的样本数M;

输出参数:标注结果datalabel以及正确率accur;

Step 1 在L和U上调用MPWPS算法，得到M个由专家标注的有标记样本AL，U´=U－AL，L´=L+AL;

Step 1.1 根据L训练分类器H;

Step 1.2 对ESi，按照公式(1)计算ESi;

Step 1.3 根据ESi从U中选择M个ESi最大的未标记样本;

Step 1.4 将上述未标记样本交给专家进行标注，得到由专家标注的有标记样本AL;

Step 2 对有标记样本集L´进行随机采样，产生3个训练集 S1、S2、S3，分别训练 H1、H2、H3;

Step 3 对每个Hi(i=1，2，3)，从无标记样本集U'中由Hj和Hk(j，k≠i)选择满足判别条件的集合Li={x|x∈U且Hj(x)=Hk(x)}进行标记，并生成新训练集

Step 4 用训练集S´i重新训练分类器Hi;

Step 5 如果H1、H2、H3中至少有一个发生变化，则转Step 3;

Step 6 用分类器 H1、H2、H3对测试集 test进行标注得到标注结果datalabel并计算标注正确率accur;

算法流程图如图1所示。

图1 算法流程图

4 实验及结果

本文在 UCI公共数据集 haberman、heart和breast上进行实验，并将本文算法与Tri－training算法进行了对比实验，以进一步验证本文算法的有效性。实验数据集的相关信息如表1所示。

表1 实验数据集描述

本文在整个实验中只针对2值分类问题进行研究，数据的标签为1或－1。

4.1 实验结果

本文在 UCI数据集 haberman、heart、breast这三个数据集上进行了实验，并搭建可视化实验平台。在此仅以数据集heart为例展示基于MPWPS主动学习的半监督分类算法的实验结果。运行结果展示如图2所示。

图2 结果显示界面

4.2 实验比较

本文将主动学习的思想引入半监督学习中，最终完成了基于MPWPS主动学习的半监督分类算法，并在3个数据集上进行实验，得到实验数据。为了进一步验证该算法的有效性，本文将该算法与Tri－training算法进行对比实验，衡量指标是算法的标注正确率。

本文针对两种算法在数据集上的每一次划分进行了5次实验，每一次实验将训练集train按划分比例0.2随机划分，得到5组有标记样本L和无标记样本U，并对三次划分共15次实验的正确率求平均值，见表2。

表2 两种算法标注正确率对比

通过实验比较，由表2可以看出，在3个数据集上的所有实验数据中，数据结果显示基于MPWPS主动学习的半监督分类算法对测试集数据的标注正确率比Tri－training算法高。

5 结束语

本文实现了基于MPWPS主动学习的半监督协同分类算法，该算法在训练集较小的情况下也能获得较高的分类正确率，在UCI公共数据集上的实验验证了算法的有效性。不足之处在于，若选出的M组最有可能预测错误的样本是无标记样本集中的边缘数据，那么将这组标记样本加入有标记样本集中会造成训练的过拟和，这将会对分类器的预测精度产生影响，这将是今后需要研究和解决的问题。

［1］X J Zhu.Semi－ supervised learning literature survey.Technical Report TP 1530，University of Wisconsin，Madison，2008.

［2］龙 军，殷建平，祝 恩，等.选取最大可能预测错误样例的主动学习算法［J］.计算机研究与发展，2008，45(3):472－478.

［3］邓 超，郭茂祖.基于Tri－Training和数据剪辑的半监督聚类算法［J］.软件学报，2008，19(3):663 －673.

［4］梁吉业，高嘉伟，常 瑜.半监督学习研究进展［J］.山西大学学报(自然科学版)，2009，32(4):528 －534.

［5］周志华，王 珏.半监督学习中的协同训练风范机器学习及其应用［M］.北京:清华大学出版社，2007:259－275.

［6］Z H Zhou，M Li Tri－ training:Exploiting unlabeled data using three classifiers［J］.IEEE Transactions on Knowledge and Data Engineering，2005，17(11):1529 －1541.

［7］王 娜，李 霞.基于监督信息特征的主动半监督谱聚类算法［J］.电子学报，2010，38(1):172 －176.