基于粗糙集的增量式垃圾邮件过滤方法研究.doc

基于粗糙集的增量式垃圾邮件过滤方法研究 徐丹，韩艳杰，寇曼曼 （河南省地震局，河南郑州450016） 摘要：在粗糙集理论基础上，提出一种增量式的垃圾邮件过滤方法。该方法将邮件样本的局部最小确定性作为阈值来控制规则产生，并在邮件识别过滤过程中增加了反馈环节，将错判和未识别样本作为增量样本进行再学习，动态调整邮件规则的置信度。根据阈值选择可信度较高的规则进行更新，从而减少了规则的个数，提高了样本的正确识别率，最后用实验证明了该方法的有效性。 关键词：垃圾邮件过滤；粗糙集理论；增量学习；ilrs算法 ：TN911?34：A：1004?373X（xx）14?0024?04 ：xx?02?25 基金项目：国家自然科学基金（61379114） 0引言 随着Inter技术的快速发展，电子邮件在人们的生活中扮演着越来越重要的角色。人们之间大量的交流都通过电子邮件来进行，但是垃圾邮件的日益增多也成为困扰人们日常工作生活的一个难题，电子邮件过滤技术由此产生并成为阻止垃圾邮件的重要手段之一。 有很多学者对电子邮件过滤方法进行了研究，常见的有以下三种： （1）基于黑名单?白名单的识别方法，即利用邮件地址、IP地址或域名的属性进行的邮件识别，这种方法的正确识别率低，容易造成误判，典型的应用有结合DNS（DomainNameServer）的RBL（Real?timeBlockList）识别1等。 （2）基于数据挖掘技术，利用文本分类和统计算法的识别，比如Bayes2、SVM3、人工神经网络4等，识别准确率较高，但速度慢，不适用于邮件规模较大的情况；同时，它们大都没有考虑交互的问题，对错判邮件的处理不够完善。 （3）基于规则匹配的识别方法。文献5结合粗糙集理论的数据分析技术研究了邮件过滤系统的建模和特征发现等问题，并用经验数据进行实验，得到了较好的结果。刘洋等基于粗糙集理论将邮件向量同规则向量统一定义，有选择的进行二次过滤，得到了80%左右的正确率6。 以上所介绍的方法都只能静态的对电子邮件进行分类过滤，如何对邮件信息进行动态的增量式学习将是未来研究的热点。文献7在扩展决策矩阵的定义的基础上提出一种能够增量的从样本数据中提取确定性和可能性规则的方法，该方法对缺乏领域知识时的规则获取有重要意义；文献8首先根据粗糙集方法提取规则，然后在自定义的归纳分配表上利用概率论的思想提取可以覆盖新样本的规则强度高的规则，并用实验证明了它的有效性，如何将连续属性进一步离散化是该方法的下一步需要考虑的问题之一。文献9提出了一种基于概率粗糙集模型的增量式规则学习算法，该算法能够有效地从不一致和含有噪声的决策表中提取带有确定性因子和支持数的决策规则，提取的规则具有很好的抗噪声能力，但是在数据量较大的情况下，该方法未能得到有效验证。 本文提出的增量式电子邮件过滤方法是在基于粗糙集的电子邮件过滤模型的基础上增加反馈环节，将识别过程中错误识别和未识别的邮件信息作为新增的矛盾样本进行再学习，通过邮件决策信息表的局部最小确定性与矛盾规则和样本可信度的比较，对规则集进行更新，有效地提高了邮件的正确识别率。本文介绍了基于粗糙集理论的邮件分类模型的相关基本概念，在此基础上提出了一种基于粗糙集的增量式电子邮件过滤方法，并利用UCI中的SpamDatabase数据集对该方法进行了实验，并分别与增量前的学习效果和ID4算法进行比较，从而验证了该方法的有效性。 1相关基本概念 定义1（电子邮件决策表信息系统）：电子邮件决策表信息系统是一个四元组S=U,R=C?D,V,f。其中：U是邮件的集合；R为属性的集合；C为邮件条件属性的集合；D表示决策属性集合；V是属性值的集合；f是信息函数，它指定U中每个对象x的属性值10。 2基于粗糙集的增量式邮件过滤方法 为了更有效地获得邮件规则，需要将学习识别后反馈的错判和未识别信息作为新样本进行再训练，原始的非增量式学习方法是将错判和未识别样本放入原始信息决策表，进行重新训练。这种方法比较简单，但在样本集非常大的时候，重新训练的周期较长，且规则更新速度非常慢，影响学习的效率，不能满足实时邮件过滤要求。本文提出的增量式邮件过滤方法针对错判和未识别样本的情况，能从矛盾的邮件决策信息表中提取带有置信度的决策规则，从而实现邮件规则集的动态更新。 基于粗糙集的自主式增量邮件过滤方法需要经过以下两个步骤： （1）根据粗糙集的方法：邮件决策信息表数据预处理属性约简值约简规则集，抽取数据集进行匹配，记录匹配过程中出现的错判和未识别样本。 （2）将上述反馈的错判、未识别样本加入新增样本训练集中，将计算样本的置信度加入到原始规则集中。 输入：邮件规则集M，新增样本x。 输出：更新后的规则集M。 Step1：根据原邮件规则集中的规则对新增对象x进行匹配，匹配结果分为2种情况。 （1）若x:xx的条件属性特征和已有规则yy匹配，而决策属性特征不匹配，即?yU,xy,xy出现矛盾样本，转向Step2。 3实验仿真 本文抽取UCI机器学习数据库中的垃圾邮件数据集Spambase12进行实验，该数据集包含4601个实例，其中包括1813封垃圾邮件，2788封非垃圾邮件，每个实例分别用58个特征属性来描述（包括57个条件属性特征和1个决策属性特征），用0，1对垃圾邮件和非垃圾邮件分别进行标识。以下实验分为两个部分：测试1为增量前后的对比实验，测试2为ILRS算法与决策树ID4算法的增量式电子邮件学习效果的比较。 3.1增量前后的实验对比 从Spambase的4601条实例中随机抽取含有500，1000，1500，2000，2500，3000，3500，4000，4500个样本的9个数据集，进行对比实验。 具体实验步骤如下： Step1：将原始数据集中随机抽取50%邮件样本用粗糙集方法进行属性约简、值约简得到规则集； Step2：用Step1中得到的规则集对剩下的50%邮件样本进行识别，记录反馈的错误识别和未识别的样本； Step3：对Step2中错判和未识别的邮件样本进行增量式学习，得到更新后的规则集； Step4：在Spambase数据集中重新提取与训练集数量相同的样本作为测试集，将第3步得到的更新后的规则集用测试集进行测试，得到正确识别率、未识别率和规则个数。表1中，各个符号的含义如下：N#为邮件样本数量；RR（%）为邮件样本正确识别率；NR（%）为未识别率；GR为规则个数。 3.2ILRS算法与ID4方法的实验对比 为了进一步验证算法的有效性，将ILRS算法和决策树ID4算法作对比测试。实验步骤同实验3.1，原始数据样本为测试集，记录运算时间T（s）、正确识别率RR（%）、错误识别率WR（%）及规则个数GR。实验结果如表2所示。 从图3、图4可见，在进行增量式学习时粗糙集方法ILRS在规则个数较少的情况下，对邮件样本的正确识别率高于ID4算法。 4结论 本文在粗糙集理论的基础上，提出了一种增量式的邮件过滤方法，即将学习后反馈的错判和未识别邮件信息作为新增样本进行再学习，把邮件决策信息表局部最小确定性作为阈值与矛盾规则的置信度进行比较，从而更新规则。实验表明，增量学习后对邮件样本的正确识别率明显提高，错误识别率有所降低，并且经过实验对比可以看出，本文提出的ILRS算法比ID4算法提取的规则数量少近3倍，对邮件的正确识别率却高出10%20%，从而证明了该方法的有效性。 参考文献 1杨峰，曹麒麟，段海新.基于DNSBlocklist的反垃圾邮件系统的设计与实现J.计算机工程与应用，xx（7）：11?12. 2PROVOSTJ.Naive?Bayesvsrule?learninginclassificationofemailD.Austin，USA：DepartmentofComputerSciences，UniversityofTexas，1999. 3DRUCKERH，WUD，VAPNIKVN.Supportvectorma?chinesforspamcategorizationJ.IEEETransactionsonNeu?ralNetworks，1999，10：1048?1054. 4TRETYAKOVKonstantin.Machinelearningtechniquesinspamfilteringdataminingproblem?orientedseminarJ.MTAT，xx，177：60?79. 5于洪，李志君，唐宏，等.电子邮件过滤系统的粗糙集分析模型J.计算机工程与应用，xx（15）：47?48. 6刘洋，杜孝平，罗平，等.垃圾邮件的智能分析、过滤及Rough集讨论C/xx年第十二届中国计算机学会网络与数据通信学术会议.武汉：中国计算机学会，xx：515?521. 7於东军，王士同，杨静宇.一种增量式规则提取算法J.小型微型计算机系统，xx，25（1）：79?81. 8邱兆雷，王爱云，陈传臻.基于变精度粗集和搜索树的增量式规则获取算法J.计算机工程与应用，xx，44（14）：163?165. 9付长龙，杜旭辉，姚全珠.一种基于概率粗糙集模型的增量式规则学习算法J.计算机科学，xx，35（5）：143?146. 10王国胤.Rough集理论与知识获取M.西安：西安交通大学出版社，xx. 11王国胤，何晓.一种不确定性条件下的自主式知识学习模型J.软件学报，xx，14（6）：1096?1102. 12ZHENGZ，