QBC主动采样学习在垃圾邮件在线过滤中的应用

陈念，唐振民

1.池州学院数学与计算机科学系，安徽池州 247000

2.南京理工大学计算机科学与工程学院，南京 210094

QBC主动采样学习在垃圾邮件在线过滤中的应用

陈念1，2，唐振民2

1.池州学院数学与计算机科学系，安徽池州 247000

2.南京理工大学计算机科学与工程学院，南京 210094

垃圾邮件指的是通过群发方式，未经许可强行向用户发送的电子邮件，其承载的信息多为商业广告，但也充斥着相当数量的诈骗、色情信息，严重干扰了人们的日常生活，甚至会造成一定的经济损失。提供邮件服务的网站都有一些垃圾邮件在线过滤的方法，其实质都是解决二值文本的在线分类问题[1]，但由于垃圾邮件本身的格式、内容等都在不断地发生变化，因此分类器也需要获取相应的样本进行更新。网络上存在着一些已被标注的邮件样本，但更多的是未经用户标注的样本。当前研究方向是：以较小的标注成本获取高价值的样本，快速地建立训练集，使得垃圾邮件在线过滤既能满足低计算量的要求，又能兼顾高识别率的期望。

主动学习是近年来机器学习研究的热点，它改变了原先分类器被动接受训练样本的学习方式[2]，在已有带标签样本数量不足，分类器充分训练得不到保证的条件下，在无标签样本池中通过一定的采样策略主动选择样本，经专家或用户标注类别后，加入训练集。现有的采样策略主要分三种[3]：一是基于不确定性的采样策略，文献[4]中提出的边界采样（Margin Sampling）是目前广泛被使用的一种方法，它在SVM超平面附近采集类别归属不确定性大的样本进行机器训练，并在各种实际应用中取得很好分类效果。Huang等人提出的最小—最大视图方法[5]（QUIRE）由于充分考虑了样本的分布信息，因此能很好地克服噪音带来的干扰，是该策略下采样效果较好的方法。二是基于版本空间缩减的采样策略，它将所有可能成为目标参数的模型假设集中在一起，构成版本空间（Version Space），在某种算法思想下，逐步淘汰错误的假设，使版本空间最终收敛于目标假设。委员会投票算法QBC就是这种策略下最具代表性的采样方法，由此衍生出的Boosting_QBC[6]和Bagging_QBC[7]，都能很好地适应多种分类器模型。三是基于误差缩减的采样策略，它采集的训练样本可以最大程度地缩减泛化误差，如Fisher Information方法。

本文根据垃圾邮件在线过滤应用的特点，在分析缩减版本空间采样策略的思想基础上，采用投票熵度量样本类别归属的不确定性，将熵值超过阈值θ的样本进行标注学习。文中提出一种基于QBC的快速采样方法，即在算法执行过程中，随着分类器预测能力的增强，以Δθ的幅度逐步调高阈值，这样可以减少采样次数，降低样本采集带来的标注成本和学习时间成本，同时对分类精度不会产生大的影响。

1 缩减版本空间采样策略

设样本空间χ={xi|i=1,2,…,n},类标识空间C= {ck|k=1,2,…,m},对xi∈χ,存在ωj={ωj1,ωj2,…,ωjs}使得表达式f(ωjp,xi)=ck成立，其中f为分类器模型，ωj为模型参数集合，p=1,2,…,s。χ中任一样本都对应有ωj,可以将它映射到空间C中，那么由所有ωj构成的集合称为f参数的版本空间（Version Space），表示为：

VS={ωj|j=1,2,…,t}（1）

图1（a）中显示了样本x1可被4个超平面划归到Class1中（可能的分类面远不止4个），每个分类面对应的模型参数ωj构成了x1的版本空间。缩减版本空间的做法在于：对新采集的样本，版本空间中现有的参数预测其类别，在与专家标注的真实类别比对后，预测错误的参数将被淘汰出去。该过程迭代若干次，版本空间最终将收敛于目标参数ω0。

如图1（b）中所示，新样本x2被plane1、plane2错误地划分到Class1中，那么这两个分类面对应的参数被淘汰之后，版本空间的规模将缩减一半，而新样本x3对版本空间的缩减则没有产生贡献。

从上例可以看，版本空间收敛的速度取决于采集样本的质量。平分版本空间是缩减策略的理想化实践，它假设VS中的t个元素服从平均概率分布，即每个元素成为目标参数的概率都是相同的，有P(ω0|ωj)=,则第i次采样后，样本空间规模的数学期望是：

图1 版本空间概念与缩减过程图解

当然，这种获取分类器参数的方法，和其他很多方法一样，不能避免噪音样本的干扰。设想如果采集到的新样本是野值点，那么依此训练得出的目标参数可能就是错误的。

2 委员会投票算法

2.1 算法思想与实现步骤

Seung和Freund提出的委员会投票算法QBC[9-10]，是基于版本空间缩减策略中最具代表性的采样学习方法。它依据采集样本的归类不确定性的高低，来决定该样本是否用于机器训练，图2简单表达了QBC的算法思想。

图2 委员会投票算法的一般步骤

设有带标签样本集L={＜xi,ck＞},无标签样本集UL={xj},分类器模型f。从L中分离出若干个子集SL分别训练f获取分类器当前版本空间VS,从VS中选择r个元素组成委员会com。对采集的样本xi∈UL,com中的每个成员对其类别归属有一票的表决权，计算xi的归类不确定性值，如果超出了设定门槛θ,则需经专家标注获取其真实类别ci。调整L,UL集合的组成：L+xi→L,UL-xi→UL,用L训练模型f,并在测试集上检验其泛化精度。

投票熵是度量样本归类不确定性的一种方式[11]，由于它没有考虑样本的概率分布情况，因此在采样时不会遗漏有价值的训练样本，公式为：

样本存在属于或不属于某类两种情况，式中V(c,xi)是委员会判断样本xi属于c类的票数，|C|是类别数，ε是为防止某类得票数为0，而出现lb 0这种情况的微调常量，可取非常小的值。

QBC算法可描述如下：

输入条件：有标签样本集L,无标签样本集UL,标注阈值θ

输出：训练样本集L及对应目标参数ω0

算法将UL中的无标签样本逐一取出判断其归类不确定性，然后将其熵值超过门槛θ与否，作为是否进行标注且作为训练数据的依据。θ∈[0,1]对算法的执行效果影响很大。θ偏大时，由于门槛过高，很多高价值样本得不到作为训练数据的机会，分类器的精度会降低；而其值偏小时，大量信息量近似的样本会被冗余标注和训练，增加了学习过程的时间成本。

实际问题处理中，Boosting和Bagging方法有效结合了投票查询的过程，使分类模型适应复杂数据环境的能力更强。Boosting_QBC中每个委员会成员被赋予不同的动态权重wj,其投票结果wj×f(ωj,xi)对熵值的影响也相应存在差异。一次采样投票后，预测误差e被作为权值调整的依据，wj=ln((1-e)/e),低预测误差的成员将被赋予更高的权重参与下一次投票。Bagging_QBC算法则每次在有标签池L中随机选择由n个样本构成的子集Li,迭代i次训练分类模型f,由此获得委员会成员。Bagging方法对诸如判定树、神经网络等受训练规模影响较大的不稳定模型，具有较强的预测能力。

2.2 快速训练样本采样方法

对于一些在线应用，如垃圾邮件的在线过滤，由于时效性要求较高，因此应选择高信息量样本进行针对性训练，使分类器在较短的时间内获得强的泛化能力。分类器学习效率η与识别准确率facc及所需训练样本数量nosam之间的关系显然满足：

训练样本规模nosam由两部分组成：初始训练样本数量|L|和标注后加入训练集的样本数量labelsam。初始样本是机器学习开始之前就已具备的，可以给分类器提供前期经验，后续的学习样本则是训练过程中主动选择的。labelsam与熵值votentropy及标注门槛θ的关系是：

随着机器学习过程的推进，版本空间中错误的模型参数被逐步淘汰，保留下的参数成为目标参数的概率也在增加。分类器应倾向于选择具有更高熵值，即信息量更丰富的样本来加快版本空间的收敛，而样本标注依据的阈值θ却是静态的。本文在主动采样学习的过程中，以相同的幅度Δθ逐步增加θ的值，以达到分类器训练效果不变的前提下，削减训练样本数量，提高学习速度的目的。

机器的学习目的是用最小的训练代价获得最高的识别准确率，即maxη，假定分类器训练后可达到的准确率facc=δ,δ为常量，由式（5）得：

因此，阈值增加幅度Δθ应满足条件：

与θ的取值一样，过大的Δθ值虽然能使采样的过程快速地结束，但也会遗漏样本集中有价值的数据，分类器由于得不到充分训练而泛化精度不高；Δθ偏小的取值，同样会造成冗余采样，出现获取样本对版本空间的缩减贡献较低的现象。

一般的做法是，在分类器学习的初始阶段，设置的门槛θ值较低，让更多的样本能获得训练分类器的机会。随着学习过程的推进，分类器预测能力的提升，逐步提高采样标注门槛，以求获取更高价值的样本，更快地结束分类器的学习过程。

3 实验与分析

UCI的Spambase是从实际e-mail应用中收集出的邮件集合，可用于邮件过滤器的训练。它包含有4 601个样本，分成Non-Spam（正常邮件2 788个）和Spam（垃圾邮件1 813个）两个类别，每个样本由58个属性描述，其中包含1个类别属性。认定垃圾邮件的依据有：特定的单词或字符在e-mail中出现的频率，及不间断的大写字母长度信息等。表1给出了Spambase集中各样本的属性描述。

实验在Spambase数据集上进行，采用SVM二分类模型，分别用随机采样（Random Sampling），委员会投票采样（QBC Sampling），衍生的投票采样（Boosting_ QBC Sampling和Bagging_QBC Sampling）及本文提出的快速QBC采样（Fast QBC Sampling）五种方法在无标签样本池中采集训练样本。通过实验，比较这些方法的工作效率，并分析θ,Δθ不同取值下，快速QBC采样算法表现出的性能。

3.1 不同采样方法分析与比较

将Spambase按4∶1的比例随机划分成训练集和测试集，做交叉验证。设算法中各相关量初始化为|L|=90,θ=0.2,Δθ=0.002,计算在测试集上进行不同规模的采样，分类器训练所能达到的精度，表2给出了5次实验的平均值。

表2的对比主要是展现同等采样规模下泛化精度的变化，可以看出，随着由采样获得的训练样本不断加入，用不同方法获得样本训练分类器，获得的精度都是逐步上升的。随机采样方法在选择样本时，由于带有一定盲目性，因此在不同采样次数下，其所能达到的精度在85%～86%之间，低于表中其他方法。QBC采样选择类别不确定性大的样本加入训练集，相比较于随机采样，同等规模下能提升泛化精度2%左右。Boosting_QBC和Bagging_QBC采样优势在这个数据集上并没有体现出来，相同数量的采样获得的泛化精度与QBC采样相近，最大差值只有0.6%。这是因为前者的加权投票策略更适用于难区分样本数量较多的情形，而后者则在受训练规模影响偏大的不稳定分类模型上更能体现其针对性，可以推断，邮件分类数据集Spambase和当前模型并不满足充分发挥它们预测优势的条件。Fast QBC方法则在采样过程，不断寻找更高价值训练样本，因而能获得优于其他方法的效率，实验结果证实了这点，例如在采样规模为130时，精度较常规QBC方法有1.4%的提升，比Boosting_QBC也增加了1%。

图3给出了相同θ前提下，几种QBC方法在无标签样本池中采样次数的对比，其中Fast QBC采用Δθ=0.005。

由图3可见，四种投票采样方法随着采样阈值θ的递增，在无标签池中采样的次数呈现明显的下降趋势。QBC、Boosting_QBC及Bagging_QBC由于使用固定值的采样标注门槛，相同阈值下的采样次数差别并不明显。而Fast QBC以Δθ的步长动态提升门槛设置，因此能更为快速地结束采样过程，建立训练样本集。

3.2 参数设置对Fast QBC的影响

在2.2节中提到，参数θ和Δθ的取值是影响Fast QBC采样数量与质量的重要因素，而引入调整幅度Δθ是该方法区别与其他投票算法的最主要特点。表3记录了不同参数设置时，Fast QBC的采样次数情况，其中|L|=90,表中数据为5次实验均值。

表1 Spambase数据集样本属性情况

表2 不同算法在不同采样规模时获得的泛化精度对比

图3 几种QBC算法采样次数对比

表3结果与理论分析一致，随着采样门槛θ和调整幅度Δθ的增加，算法在数据集上的采样次数呈现递减趋势，且调高Δθ可以更快地降低采样数量。由于初始训练样本L是从训练集中随机产生的，它的组成也会影响到后续的采样，因此从表中看出，递减的过程并不是单调的。

表3 不同参数对应的Fast QBC采样数量情况

θ和Δθ值增加时，能够快速地从样本池中收集训练样本，使机器学习的过程尽快结束，但过大的值设置同样会带来识别率的下降。

图4显示，θ在0.25附近取值时，Δθ用不同值采样训练后得到的分类器识别精度能够保持在90%附近。随着参数值设置得增大，训练获得的分类器泛化精度会呈现下降的趋势。在两个参数都有较大取值时（如图θ=0.5,Δθ=0.008），识别率仅有86%，这是由于相邻的两次采样间门槛跨度过大，一些信息量大，但熵值未超过门槛设置的样本没有获得训练分类模型的机会，而导致识别率不高。因此θ和Δθ值的选择要综合考虑采样数量和泛化精度两个方面的因素，以达到用较小的训练代价获得相对较高识别准确率的目标。

4 结束语

图4 Fast QBC识别精度随参数变化情况

本文针对垃圾邮件在线过滤的实际应用，在委员会投票QBC算法的基础上，通过逐步提高采样门槛的做法，在无标签样本池中选择高信息量的样本用于分类器的训练。根据应用的时效性要求，需要在尽可能短的时间内建立最有学习价值的训练集，QBC采样算法是一种高效的主动学习方法，它通过计算样本的熵值高低，来评价其训练价值。本文充分考虑了机器学习过程中，分类器识别能力逐步增强这一特点，用动态提升采样阈值的方法，梯度增加采集样本的质量，进一步压缩样本标注和学习所需的时间成本，提高学习的效率。

[1]刘伍颖，王挺.结构化集成学习垃圾邮件过滤[J].计算机研究与发展，2012，49（3）：628-635.

[2]陈荣.基于主动学习和半监督学习的多类图像分类[J].自动化学报，2011，37（8）：954-962.

[3]吴伟宁.基于采样策略的主动学习算法研究进展[J].计算机研究与发展，2012，49（6）：1162-1173.

[4]Tong S，Koller D.Support vector machine active learning with applications to text classification[J].The Journal of Machine Learning Research，2002（2）：45-66.

[5]Huang Shengjun，Jin Rong，Zhou Zhihua.Active learning by querying informative and representative examples[C]// Proc of NIPS 2010.Cambridge，MA：MIT Press，2010：892-900.

[6]Freund Y，Schapire R E.A decision-theoretic generalization of on-line learning and an application to boosting[J]. Journal of Computer and System Sciences，1997，55（1）：119-139.

[7]Breiman L.Bagging predictors[J].Machine Learning，1996，24（2）：123-140.

[8]龙军.选取最大可能预测错误样例的主动学习算法[J].计算机研究与发展，2008，45（3）：472-478.

[9]Seung H S，Opper M，Sompolinsky H.Query by committee[C]//Proceedings of the 15th Annual ACM Workshop on Computational Learning Theory，California，1992：287-294.

[10]Freund Y，Seung H S，Samir E，et al.Selective sampling usingthequerybycommitteealgorithm[J].Machine Learning，1997，28（23）：133-168.

[11]Argamon E S，Dagan I.Committee-based sample selection for probabilistic classifiers[J].Journal of Artificial Intelligence Research，1999，11：335-360.

CHEN Nian1，2,TANG Zhenmin2

1.Department of Mathematics and Computer Science,Chizhou College,Chizhou,Anhui 247000,China
2.College of Computer Science and Engineering,Nanjing University of Science and Technology,Nanjing 210094,China

A method is put forward in the paper which can get informative samples from unlabeled-sample pool with stepped way.The method which is based on query-by-committee algorithm increases the sampling threshold dynamically and it is in order to solve the problem of spam filtering online.Through the new method,the number of samples which is used for labeling and training is further reduced and the accuracy of classifier can remain stable.By experiments on Spambase datasets,the effectiveness which can improve efficiency of machine learning is certificated.

spam filtering;version space;active learning;vote entropy;query-by-committee algorithm

针对垃圾邮件在线过滤的实际应用，在委员会投票算法采样学习的基础上，提出动态提升采样门槛，在无标签样本池中阶梯式获取高信息量训练样本的方法。该方法能够在稳定识别精度的前提下，进一步降低用于标注和学习的样本数量，压缩由此带来的时间成本。通过在UCI的Spambase数据集上仿真，证明了该方法在改善学习效率方面的有效性。

垃圾邮件过滤；版本空间；主动学习；投票熵；委员会投票算法

A

TP393

10.3778/j.issn.1002-8331.1211-0016

CHEN Nian,TANG Zhenmin.Method of spam filtering online based on QBC active sampling learning algorithm. Computer Engineering and Applications,2014,50（22）：170-174.

安徽省教育厅自然重点项目（No.KJ2012A211）。

陈念（1978—），男，副教授，主研方向：机器学习与人工智能；唐振民，教授，博导。E-mail：njustchennian@gmail.com

2012-11-01

2013-01-23

1002-8331（2014）22-0170-05

CNKI网络优先出版：2013-02-28,http://www.cnki.net/kcms/detail/11.2127.TP.20130228.1148.012.html

◎图形图像处理◎