基于用户兴趣度的在线邮件个性化分类新方法1

1、基于用户兴趣度的在线邮件个性化分类新方法1 引言随着网络技术的迅速发展，电子邮件已成为人们日常生活中重要的通信手段之一。日益增长的垃圾邮件常常附载大量虚假、不健康, 甚至危害社会稳定与安全的信息。垃圾邮件过滤是典型的二分类问题，具有区别于传统文本分类的特点Active Learning for On line Spam Filtering，集成学习和主动学习相结合的个性化垃圾邮件过滤：首先，邮件过滤需根据用户的兴趣进行，同一封邮件在不同用户甚至处于不同时期的同一用户眼中可能得到不同的分类结果；其次，邮件过滤属于在线应用，因此对处理速度要求比较高；最后，在线邮件数量众多且种类复杂，难以通过传统人

2、工标注形成通用的训练样本集。因此，如何有效解决以上问题成为在线邮件识别的首要任务。增量学习是一种应用于在线邮件识别的典型技术Incremental Leaning Algorithm Based on SVM。与传统学习技术相比，增量学习可以充分利用历史学习的结果，在不显著降低样本识别精度的前提下，节省后续训练时间。Batch SVM将初始训练集中支持向量集加入至增量样本集合中形成新的训练集，其针对训练集中冗余样本处理过于简单，算法识别精度不高；Active Learning for On line Spam Filtering提出了一种基于缓存的邮件识别方法，该方法将待分类邮件与某段时间内所

3、接受邮件进行相似度比较以实现对重复邮件的迅速分类；基于主动学习的视频对象提取方法将SVM和主动学习结合起来，增量学习过程选择正类样本构造新的最优超平面。算法能准确识别正类样本，但针对负类样本的检测精度较低；集成学习和主动学习相结合的个性化垃圾邮件过滤根据用户反馈构建个性化的用户兴趣模型，通过组合邮件模型分类器与兴趣模型分类器结果实现对邮件的准确分类。该方法通过SVM集成学习有效降低了特征向量空间维数，算法执行速度较快；Online active multi-field learning for efficient email spamfiltering将邮件分为多个域，针对每个域构建一个域分类

4、器，并在一个组合分类器中处理多个域的分类结果。算法通过接收用户反馈的标注结果实现各个域分类器的更新，分类精度较高，但是样本预测过程需要考虑该样本与所有已标注样本之间的关系，故当样本数量较多时，算法时间复杂度较高；基于主动学习和半监督学习的多类图像分类通过BvSB主动学习去挖掘那些对当前分类器模型最有价值的样本进行人工标注, 并借助CST半监督学习进一步选择样本集中大量的未标注样本, 使得当标注代价较小时仍能够获得良好的分类性能。但是，现有算法普遍存在下面问题：1难以准确判定样本分类结果的确定性，若在学习过程中加入分类错误的样本，算法识别精度将受到影响；2待标注样本选择过程往往需要训练集中所有样

5、本参与，导致计算复杂度较高；3传统主动学习只能获知用户是否对某邮件感兴趣，未具体量化用户的兴趣浓厚程度，忽略了用户关注程度不同的邮件被错分所带来的代价往往不同。本文对传统Batch SVM模型做出改进，引入用户兴趣度的概念，在主动学习过程中进一步考虑用户对邮件内容关心程度，实现了一种在线邮件个性化分类新方法。2 相关理论2.1 Batch SVM增量学习Batch SVM是最早期的SVM增量学习方法，该方法由Syed等人提出，现在已成为机器学习中一种典型的增量学习方法N. Syed, H. Liu, and K. Sung. Incremental learning with support

6、vector machines. In Proceedings of the Workshop on Support Vector Machines atthe International Joint Conference on Articial Intelligence(IJCAI-99), Stockholm, Sweden, 1999。如图 所示，该方法实现的具体步骤如下：图4.1 Batch SVM增量学习算法示意图输入：初始训练样本集合T0、增量样本集合I1，增量样本集合In；步骤1：使用SVM对样本1进行训练，获得支持向量集合SV1；步骤2：将I1加入SV1生成训练集T1，进一步得

7、到支持向量集合SV2；步骤3：重复类似步骤2的过程直到所有的增量样本集合都已参加训练。输出：增量学习后的分类器Batch SVM增量学习算法存在以下的问题：1）针对非支持向量的处理过于简单，被丢弃的非支持向量可能在下次训练后成为支持向量；2）全部增量样本被加入至先前SV集合以形成新的训练样本，使得训练集样本数目增长较快，影响分类器训练速度；3） 学习过程未融入用户兴趣，无法根据用户不同需求进行个性化分类。2.2 主动学习模型主动学习使用未标记样例辅助分类器的训练过程，目的是在增量训练过程中有选择地扩大有标记样例集合和循环训练的方法使分类器获得了更强的泛化能力。主动学习方法分为两个部分Wu Yi

8、, Kozintsev I, Bouguet J Y, et al. Sampling strategies for active learning in personal photo retrieval C / Proc of ICME 2006. Piscataway, NJ: IEEE, 2006: 529-532.：学习引擎和采样引擎，具体如图 所示。其中，学习引擎先在初始样本集合上构造初始分类器，接着使用该分类器对增量样本进行分类；采样引擎则使用不同的采样算法从增量样本集合中选择样本并移交给专家进行标注，接着将标注后的样本加入初始训练集进行循环训练。后者是区分不同主动学习算法的关键。

9、根据采样策略不同，可以将主动学习算法分 为：成员查询综合、基于流的主动学习、基于池的主动学习等。理论研究表明，相对于监督学习而言，主动学习可以有效降低样本复杂度并能带来指数级的样本复杂度改善【基于采样策略的主动学习算法研究进展】。3 本文算法3.1 算法基本流程算法可分为SVM分类、样本主动学习、样本淘汰这三个过程。图4.1给出了基于SVM增量学习的交互式邮件在线识别方法的一般过程。给定增量邮件集合Si（i=1,.,n,n为增量集数目）以及训练样本集Ai，记Si、Ai中所含样本数分别为|Si|、|Ai|，则本文分类主要步骤可描述如下：图4.1 本文算法样本训练和识别的一般过程1） 使用Ai训练

10、SVM分类器SVMi；2） 使用SVMi对Si中的样本集合sij进行分类；3） 对Si中每个样本的分类结果确定性进行评价，选择M个分类结果最不确定的样本生成集合Sri，并将Sri推荐给用户；4） 使用新的样本标注模型对Sri中样本进行类别标注；5） 使用“轮盘赌”方法将步骤4）所得的标注了样本类别的集合Sdi加入训练集Ai；6） 获取下一个增量样本Si+1，若无，算法结束；否则，令： Si=Si+1，转步骤1).3.2 主动学习过程假设当前训练集合为Ai，未标注增量样本集合为Si，则针对In所实施的主动学习过程可描述如下：3.2.1样本确定性评价文献Multi-class active lea

11、rning for image classification通过统计未标注样本属于各个类别的概率大小来寻找那些分类结果最不确定的样本. 该方法需要计算待标注样本与n个已知类别样本之间的相似度,因此时间复杂度为O(n)。为简化计算，本文从所有已分类样本中随机选取M个样本(记为Sci)进行比较，故时间复杂度为M*O(1)=O(1)。若Sci中垃圾邮件、合法邮件集合分别为Schi、Scsi，则Si中样本xi分类确定性C(xi)计算如下：将Si中所有样本对应确定性按照从小到大顺序排列，选择前Nr（0Nr|Si|）个样本(记为Sri)推荐给用户。2）用户标注传统主动学习方法强制用户对待标注样本的类别进行

12、标注，而往往用户对某种类型的样本内容并不关心，并且无法区分用户针对不同类型样本被正确分类的重视程度。本文提出了一种新的专家标注模型（如图(a)所示），具有以下特点：1用户依据邮件内容及各自兴趣选择个别样本进行类别标注；2增加关注度属性，用于表征用户针对该邮件被正确分类的重视程度。针对Sri进行的用户标注过程如下：1） 给定Sri中样本xk，用户通过查看样本内容决定其对此类型样本是否关心，若不，则丢弃该样本（如图 (b)所示），否则，转2）；2） 用户在标注xi类别R(xi)；3） 用户针对xi对应关注度A(xi)进行选择性修改（该值默认为1）,如模型图 (c)、(d)所示。4） 按照上述步骤遍

13、历Sri中的所有样本，生成标记后样本集合Sdi。3）选择样本加入传统主动学习方法将所有标注后样本直接加入原始训练集，这样存在以下问题：1）训练集样本数量增长较快；2）所有样本地位相同，而实际上不同类型样本分类正确与否给用户带来的代价却不尽相同，如相对于垃圾邮件而言，合法邮件更应当被正确地分类。本文提出了一种基于“轮盘赌”一种基于轮盘赌选择遗传算法的随机微粒群算法的样本加入方法。针对已标注的样本集合Sd做以下处理：步骤1：确定每个样本si的真实类别R(si)及加入训练集的概率P(si)，分以下三种情况：if R(si)=null,then P(si)=0; else if R(si)=ham,

14、then P(si)=A(si);else P(si)=A(si)* (0 1);endifendif步骤2：如果 ，则将si加入训练集，否则，丢弃si。其中，Rand()为轮盘赌函数，产生区间0,1内的某个随机数。4 实验结果与分析4.1 实验准备(实验软件环境:Matlab6. 5/ Windows XP;硬件环境:P2. 4GHz/ 256MB)。为便于用户对样本进行标注，使用非加密英文邮件数据Trec2007进行仿真测试。去除所有邮件中的附件、标签、邮件头、停用词等信息，使用Porter Stemming算法对所有单词进行词形还原【】。We use a large-scale, pub

15、licly available benchmark data set from the TREC spam filteringcompetition trec07p 12, which contains 75,419 total email messages (25,220 hams and50,199 spams)考虑到用户针对不同类型邮件被分类正确与否重视程度不同，本文提出了一种结合用户兴趣度(attention degree)的垃圾邮件分类召回率sra、准确率spa评价方法。具体定义如下：，其中，s(i)为用户对于垃圾邮件中某样本的关注度，h(i)为用户对于合法邮件中某样本的关注度；ns

16、(i)为垃圾邮件集合中对应s(i)关注度的样本数目；ns(i)为合法邮件集合中对应h(i)关注度的样本数目；nss(i)为垃圾邮件集合中对应s(i)关注度样本被正确分类的数目；nhs(i)为合法邮件集合中对应h(i)关注度样本被正确分类的数目。由上式知，sra越大，被误判的垃圾邮件就越少，系统发现垃圾邮件的能力就越强；spa越大，被误判的合法邮件就越少，即合法邮件“漏读”的可能性越小。4.2 多用户测试设置已标注类别的初始训练集样本数目：ns=200；每个未标注类别增量集所含样本数目：ni=50；每个已标注类别的测试样本数目：nt=200。特征选择方法使用信息增益（IG），对应特征向量维数：n

17、f=600。另外，为区分不同用户，每个测试集中样本类别由用户单独标注。图 （a）（b）显示了10个用户进行增量学习后所得测试样本对应sp及sr均值。可见，本文方法相对于反例样本驱动算法优势明显；与正类样本驱动方法在垃圾邮件的召回率方面相近，但是后者准确率却明显偏低，原因在该方法易导致数据集大小不均衡，使得许多合法邮件被误判。Batch SVM类别判定可能不准确，且样本引入及淘汰过程过于简单，因此干扰了分类精度；主动学习方法【】【】【】分类效果较其他算法好，证明了针对不确定样本进行主动学习的必要性。文献【】【】均未考虑不同用户针对不同类型样本的关注程度，因此分类效果均不如本文。4.3 单用户测试

18、单用户仿真实验时应考虑用户兴趣迁移对增量学习效果的影响。这里仿真单个用户针对不同内容邮件关注度演化过程，并测试在此情形下不同算法的分类效果。先从4.1节所给邮件样本集中挑选5个典型邮件内容主题，接着给出了某一用户在不同增量学习阶段针对接受邮件内容主题的关注度演化，具体如表 所示。仿真实验前，针对每个测试集中所有样本标注其在增量学习不同阶段所属分类。统计不同数据集上5次测试结果对应的垃圾邮件平均召回率sravg_su及平均准确率spavg_su，结果如表 所示。可见，本文所得平均召回率稍逊于文献【】，但明显高于其他算法；就平均准确率而言，本文所得结果具有显著优势，这主要是因为本文考虑了用户在不同

19、增量学习阶段对不同内容邮件重视程度不同，有效避免了用户兴趣迁移对分类结果的影响。主题1,10(10, 20)(20,30)(30,40)(40,50)car0.80.80.90.60.3football0.60.50.50.60.7stock0.50.70.80.50.6clothes0.60.80.30.10.1papers0.70.10.50.70.9算法sravg_suspavg_suBatch SVM0.9130.897半监督0.9760.936主动学习0.9640.971主动学习+自学习0.9580.963本文0.9710.9794.4训练时间测试在2.1节中实验前提下，进一步比较随

20、着训练集数目的增加，不同算法在数据集Trec2007Cormack GV (2007) TREC 2007 spam track overview. In: TREC2007 Proceedings of the 16th textretrieval conference, National Institute of Standards and Technology, Special Publication 500274下进行SVM训练所需平均时间tavg(单位ms)大小，所得结果如下图所示。可见，与本文方法相比：半监督方法每次将增量集中的正类样本加入训练集，导致训练集规模增加迅速，训练分类器

21、所需时间增长明显；主动学习方法及结合主动学习+自学习方法训练时间近似，但tavg值均高于本文，这主要是因为前两种方法每次选择Nr个样本加入训练集，而后者结合轮盘赌方法过滤掉部分用户并不关心的样本类型，有效抑制了训练集规模的快速增长； Batch SVM方法训练集大小与每个增量集大小密切相关，且存在nins，故较本文在训练速度方面具有一定优势。结束语本文提出了一种基于SVM增量学习的交互式邮件过滤新方法，主要创新点如下：1）为降低寻找待标注样本的时间复杂度，通过从已标注训练集中随机选择样本来计算待标注样本的模糊度；2）提出了新的样本标注模型，将用户针对不同内容邮件的关注度融入该模型中；3）根据不

22、同邮件用户关注度，使用“赌盘”方法决定是否将该样本加入训练集；4）根据不同邮件用户关注度，提出了新的分类器性能评价标准。实验结果证明。参考文献1. Incremental Leaning Algorithm Based on SVM2. N. Syed, H. Liu, and K. Sung. Incremental learning with support vector machines. In Proceedings of the Workshop on Support Vector Machines at the International Joint Conference on A

23、rticial Intelligence (IJCAI-99), Stockholm, Sweden, 19993. Active Learning for On line Spam Filtering4. 基于主动学习的视频对象提取方法5. 集成学习和主动学习相结合的个性化垃圾邮件过滤6. Online active multi-field learning for efficient email spamfiltering7. 基于主动学习和半监督学习的多类图像分类8. Wu Yi, Kozintsev I, Bouguet J Y, et al. Sampling strategies for active learning in personal photo retrieval C / Proc of ICME 2006. Piscataway, NJ: IEEE, 2006