武永成

(荆楚理工学院 计算机工程学院，湖北 荆门448000)

在利用监督学习(supervised learning)进行分类时，往往需要大量的有标注(label)(即分类类型)的样例(labeled instances)，才能得到准确率高的分类模型(classifier)． 现实世界中，通常存在大量的未标注样例(unlabeled instances)，而有标注样例则往往较少．例如在计算机辅助医学图像分析中，可以从医院获得大量的医学图像作为训练例，但如果要求医学专家把这些图像中的病灶都标注出来，则要付出大量的时间和精力，这往往是不现实的．为了综合利用有限的有标注样例和大量的未标注样例，各种半监督学习方法(semisupervised learning)被提出，并取得较好的效果［1－2］．但现存的这些半监督学习方法都假定样例数据(包括有标注数据和未标注数据)都是均衡的，即标注的分布是均衡的．现实世界中，很多情况下，样例数据是不均衡的．例如:在1 000 个体检数据集中，最终分类类型为健康的可能占90%，分类类型为不健康的可能为10%，标注的分布就不是均衡的了．本研究中，为便于叙述，将一个数据集中大多数的样例都属于的分类类型称为MA，而剩余的样例的分类类型称为MI．对于非平衡数据的分类(imbalanced classification)，半监督学习最大的问题是:最终得到的分类模型可能只对MA 数据敏感，而忽略MI 数据．在对测试数据进行分类预测时，容易将样例分类为MA 而忽略MI．

针对非平衡数据的分类，在监督学习中，主要采用的是重取样(re－sampling)［3］和代价敏感(cost－sensitive learning)［4］的方法．

本研究的贡献在于:①对监督学习中的重取样技术进行扩展，使其应用到半监督学习中;②通过随机动态生成样例特征子空间(random feature subspace)，提供半监督学习的协同训练［5］(co－training)所需的不同的视图(view)．在4 个相关数据集上的试验验证了本方法的有效性．

1 相关工作

1．1 基于半监督学习的分类

机器学习的分类问题中，给定一个样例集合D={＜x1，y1＞，…＜xn，yn＞}∈X×Y，其中＜xi，yi＞是一个样例．xi是一个向量［xi1，…xim］，yi是该样例的标注(或分类类型)．X、Y分别是xi，yi的取值范围． ＜x1，?＞是未标注样例，＜x1，y1＞是有标注样例．

协同训练是当前最流行的一种半监督学习风范［5］．它假设数据集有两个充分冗余(sufficient and redundant)的视图(view)．在这两个视图上利用有标记示例分别训练出一个分类器，然后，在协同训练过程中，每个分类器从未标注示例中挑选出若干分类置信度较高的示例进行标注，并把标注后的示例加入另一个分类器的有标注训练集中．协同训练的目的是，通过相互提供未知的信息，使得两个分类器的准确性都得以提高．

协同训练的关键是找到同一数据集的不同的视图． 本文通过随机动态生成样例特征子空间的方法［6］，在同一数据集上，产生多个视图．

1．2 非平衡分类

非平衡分类问题，作为一个具有挑战性的机器学习问题，近些年在多个领域被广泛研究．如:机器学习领域、数据挖掘领域和算法领域．其中使用的最重要的技术是:重取样技术和代价敏感学习技术．重取样技术又分为增重取样(over－sampling)［3］和减重取样(under－sampling)［7］两种方法．增重取样技术通过复制MI 样本来使得它和MA 的样本数达到平衡．减重取样技术则通过删除一定的MA 样本使它与MI 的样本数达到平衡．本文采用减重取样技术来处理非平衡分类问题．

2 基于半监督学习的非平衡分类算法

采用半监督学习中最流行的协同训练方法．对于协同训练所需的同一数据集上的不同视图，本文采用随机动态特征子空间的产生办法．

2．1 动态子空间的产生

动态子空间产生(Random Subspace Generation，RSG)是一种集成(ensemble)技术［6］． 如本文1．1 所述，对于样例集合D 中的每个样例＜xi，yi＞，xi是一个m维向量［xi1，xi2，…，xim］，即样例由m个特征来描述．从m个特征中，RSG 随机的选取r(m＞r)个特征，组成一个r维的特征子空间．通过这种方式，就产生了一个r维的训练样例集合Ds={＜x1s，y1＞，＜x2s，y2＞，…＜xns，yn＞}∈X×Y，其中＜xis，yi＞的xis是r维的向量．

文中，r=m/2．在得到的两个m/2 维数据集上，分别训练，生成两个子空间分类器，为协同训练做准备．

2．2 基于半监督学习的非平衡分类算法

如1．2 节所述，本文采用减重取样技术来处理非平衡分类问题．通过减重取样技术得到平衡的训练数据集后，采用动态子空间产生方法，生成两个m/2 维数据集．在这两个数据集上，训练生成协同训练所需的两个子空间分类器．这里存在一个问题:由于采用减重取样技术，使得大量MA样本被舍弃，而这些MA样本中可能蕴含很多重要的信息．为充分利用这些信息，循环地利用减重取样技术，生成多个平衡的样本集合．在每个平衡的样本集合上，再采用采用动态子空间产生方法，生成两个m/2 维数据集，训练生成两个子空间分类器．本文提出的基于半监督学习的非平衡分类算法，完整描述如算法1 所示．

算法1 基于半监督学习的非平衡分类算法(Algorithm 1 An imbalanced classification algorithm based on semi－supervised learning)

5 for j=1 to K do 6 在全部特征空间上，随机产生两个特征子空间;7 在第j 个平衡的样例集合上，在随机产生的两个特征子空间上，训练生成两个分类器Ci1 和Ci2;8 利用Ci1 和Ci2，对未标注样例集合U 进行分类，并选取分类置信度最高的一个MA 类型样本和一个MI 类型的样本，将它们加入B 中;9 end for 10 将集合B 中样例分别加入K 个平衡的样例集合中;11 A=A ∪B ;12 end for

3 试验结果与分析

试验中用到4 个数据集［8］．数据集的相关信息如表1 所示． 从表可以看出，每个数据集都是非平衡的，MA类型的样例和MI类型的样例的个数的比(K=(int)n+/ n－)最小为3，最大为8．

对于每个数据集，先随机选取100 个MI样例数据，然后选取K* 100 个MA样例数据，形成有标注样例集合L．在随机选取400个MA数据和400 个MI数据作为测试数据;最后剩余的样例数据，去掉它们的分类类型，让它们组成未标注样例集合U．

由于数据的非平衡性，最终对算法的评价不能采用常用的分类预测正确率评价方法．为此，本文采用了一种流行的G－mean 方法［9］．该方法中其中TPrate=TP/(TP+FN)，TNrate=TN(TN+FP)．TP指样例本身标注为MA且被分类预测也是MA，FN指样例本身标注为MA但被分类预测为MI，TN指本身标注为MI且被分类预测也是MI，FP指样例本身标注为MI但被分类预测为MA．

表1 试验中用到的数据集(Table 1 Experimental data sets)

为验证本算法的有效性，与另一基础算法做了比较．该基础算法的特征子空间是静态的，其余部分与本算法相同．试验结果如图1 所示．图中Ours 代表本文提出的算法．Static 代表基础算法．从图看看出，在4 个数据集上，本研究中的算法都优于Static 基础算法．

图1 比较Ours 和Static 在不同数据集上的分类正确率Fig．1 Classification accuracy on different data sets

4 结语

本文对基于半监督学习的非平衡分类问题进行了研究．首先采用减重取样技术对原始非平衡数据进行处理，得到多个平衡的数据集．然后在每个平衡的数据集上，采用动态子空间产生方法，生成同一数据集的两个不同视图，从而利于半监督学习进行学习训练．试验表明该方法优于静态的子空间的产生办法．在协同训练的过程中，循环的次数是根据实验经验事先确定的．如何设定一个循环终止的条件，让算法自动确定循环的次数，是需要继续研究的问题．

［1］ Cohen I，Cozman F G，Sebe N，et al．Semi－supervised learning of classifiers:theory，algorithm，and their application to human－computer interaction［C］//IEEE Trans．Pattern Anal．Mach． Intell，2004，26(12):553－567．

［2］ Zhu X．Semi－Supervised Learning Literature Survey［R］．Computer Sciences Technical Report，University of Wisconsin，Madison，2006．

［3］ Chawla N，Bowyer K，Hall L．SMOTE:Synthetic Minority Over－Sampling Technique［J］．Journal of Artificial Intelligence Research，2002(16):321－357．

［4］ Zhou Z，Liu X．Training Cost－Sensitive Neural Networks with Methods Addressing the Class Imbalance Problem［C］//IEEE Transaction on Knowledge and Data Engineering，2006(18):63－77．

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

［6］ Ho T．The Random Subspace Method for Constructing Decision Forests［C］//IEEE Transactions on Pattern Analysis and Machine Intelligence，1998，20(8):832－844．

［7］ Barandela R，Sánchez J，García V，et al．Strategies for Learning in Class Imbalance Problems［J］．Pattern Recognition，2003(36):849－851．

［8］ Multi－domain sentiment dataset v2．0［Z］．(2009－03－23)［2013－10－10］http://www．seas．upenn．edu/～mdredze/datasets/sentiment/．

［9］ Kubat M，Matwin S．Addressing the Curse of Imbalanced Training Sets:One－Sided Selection［C］．In Proceedings of ICML－97，1997:179－186．