基于内容的垃圾邮件过滤系统研究_孙雪.docx

《基于内容的垃圾邮件过滤系统研究_孙雪.docx》由会员分享，可在线阅读，更多相关《基于内容的垃圾邮件过滤系统研究_孙雪.docx（69页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 Classified Index： TN911 CODE： 10075 U.D.C： NO： gxjs07123 A Dissertation for the Degree of Master Research on Content-Based Spam Filtering Candidate: Sun Xue Supervisor: Prof. Li Kun-Lun Academic Degree Applied for: Master of Engineering Specialty: Comm. & Info. System University: Hebei University D

2、ate of Accomplishment: May, 2010 河北大学 学位论文独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写的研究成果，也不包含为获得河北大学或其他教育机构的学位或证书 所使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了致谢。 作 者 签 名 ： 办 i _ 日 期 ： 穴 /0年 上 月 円 学位论文使用授权声明 本人完全了解河北大学有关保留、使用学位论文的规定， g卩：学校有权保留并向国 家有关部门

3、或机构送交论文的复印件和电子版，允许论文被查阅和借阅。学校可以公布 论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 本学位论文属于 1、 保密 ，在 _ 年 _ 月 _ 日解密后适用本授权声明。 2、 不保密丘 （ 。 (请在以上相应方格内打 “ V ” ） 保护知识产权声明 本人为申请河北大学学位所提交的题目为（基于内容的垃圾邮件过滤系统研究）的 学位论文，是我个人在导师（李昆仑）指导并与导师合作下取得的研究成果，研究工作 及取得的研究成果是在河北大学所提供的研究经费及导师的研究经费资助下完成的。本 人完全了解并严格遵守中华人民共和国为保护知识产权所制定的各项法律、行政法规

4、以 及河北大学的相关规定。 本人声明如下：本论文的成果归河北大学所有，未经征得指导教师和河北大学的书 面同意和授权，本人保证不以任何形式公开和传播科研成果和科研工作内容。如果违反 本声明，本人愿意承担相应法律责任。 声明人 : 曰期： W。 年 r月 巧 日 作者签名： _ 日 期 ： 年 广 月 片 H 导师签名 : 日期： 年 广 月 1 曰 摘要 摘要 随着电子邮件的普及，垃圾邮件问题日益凸显，其数量急剧増长，内容千变万化， 具有破坏性强，传播速度快，危害范围广等特点，已经成为全球化公害。如何有效地过 滤和治理这些垃圾邮件成为当前的迫切要求。现有的垃圾邮件过滤技术主要包括基于规 则的过滤

5、和基于内容的过滤两大类。基于规则的过滤方法加入的主观因素较多，抗干扰 能力较弱，规则制定的好坏将直接影响邮件的过滤效果。基于内容的过滤作为当前垃圾 邮件处理所采用的一种主要技术手段可以通过文本分类的相关算法针对邮件内容自动 寻找规律，本文主要针对基于内容的过滤方法进行相关研究。 本文从邮件的预处理、特征选择、权重计算和分类器的设计等方面对如何改善 垃圾 邮件的过滤性能进行了探索，并对现有的算法在垃圾邮件过滤中存在的问题进行了分 析。针对基于内容的垃圾邮件过滤算法存在的 “ 维数灾难 ” 等问题，预处理中加入词频 和文档频度过滤，采取双重特征选择算法，有效的降低了冗余信息和噪声数据对分类性 能的

6、影响。 针对垃圾邮件与正常邮件在语义表述上存在的差异性，本文提出一种基于类别信息 的 LDA特征选择及加权算法 Categories-LDA， 在不同类型的邮件集中建立各自的生成 模型，分别搜寻构成各个主题的特征信息。该算法不但利用了 LDA模型基于隐含主题 建模的优点，而且 还有效的克服了由于忽略类别主题差异性所造成的系统过滤性能下降 的影响。 本文将反馈学习与随机森林算法相结合，继承了决策树集成与反馈学习的优势，针 对垃圾邮件种类实时变化的特点和客户群对邮件判别的差异性，实现邮件过滤系统的自 适应调节，及时捕捉到垃圾邮件的变化趋势，搭建客户与过滤系统的内在联系平台。实 验表明：基于类别信息

7、的 LDA特征选择及加权算法采用反馈学习的随机森林分类器可 以有效的提高邮件的分类精度。在 CCERT中文语料库的 2005-Jun子集上系统精确率提 高约 2%，在 Trec06中英文语料库上垃圾邮 件的准确率提高约 3%。 关键词垃圾邮件过滤，反馈学习，特征选择，特征加权， LDA模型 I Abstract Abstract With the development of the e-mail, the spam problems become more and more serious in our daily life. Fast variety development and ext

8、ensive quantity increase will influence the quality of spam filtering. Spam has a lot of disadvantages, such as high propagation speed and potential damage, which has already become the globalization social effect of pollution. Spam must be handled effectively. The available spam-filtering technolog

9、y includes regulation-based filtering and content-based filtering. The subjective factors are too much for the regulation-based fliteration, so this method has the weaker anti-interference ability, the establishment of the regulation will affect the mail filtering effect directly. The content-based

10、filtering is one kind of main technology, which is adopted by current spam treatment. This technology can seek filter rules automatically by the relevance algorithm of text categorization . This paper will study the content-based filtering method. This paper are focus on how to improve the filter pe

11、rformance of the system from e-mail pre-processing, feature selection, and weight calculation side. This paper analysis the problems of currently existing algorithms of spam filtering, and the corrective measure are proposed. For the the curse of dimensionality problem in content-based spam filterin

12、g algorithm, a double feature selection method based on word frequency combined with other algorithms was proposed. It can effectively reduce the impact of redundant information and noise data for classification performance. Owing to the differences of spam and legitimate E-mail, a method of Categor

13、ies LDA model is introduced. That is generate a respectively model in different type of mail grounds, and search for the information composing each subjects characteristic. Categories LDA model avoids performance degradation of the traditional LDA when it is ignore the difference between spam and le

14、gitimate email. There is no consensus of opinions among people as to face spam, and moreover, the types of spam change over time, the paper presents a method based on the Feedback-Random Forest algorithms which combines the advantages of Decision Tresses and Relevance II Abstract Feedback, The metho

15、d can be prompt catching the change trend to spam, establish the inner link between the customer and the filtering system, and the mail filtering system can be self-regulation. The results of experiment show that Categories-LDA by using Feedback-Random Forest algorithms can improve the performance o

16、f the e-mail filtering system more effectively. The system accuracy improve 2% on the 2005-Jun subset of CCERT corpus and the spam precision improve 3% on Trec06 corpus. Keywords Spam-filtering Feedback Feature selection Feature weight calculation LD A model ill 目录 目录 第 1 章绪论 . 1 1.1 石开究背景和意义 . 1 1.

17、2垃圾邮件过滤技术研究现状 . 2 1.2.1基于规则的过滤 . 3 1.2.2基于内容的过滤 . 5 1.3主要研究内容及章节安排 . 6 第 2章基于内容的垃圾邮件过滤系统概述 . 8 2.1特征选择 . 8 2.1.1特征频度和文档频度 . 8 2.1.2 f统计量 . 9 2.1.3信息增益 （ IG) . 9 2.1.4 互信息 （ MI) . 10 2.1.5 特征熵 （ TE) . 10 2.1.6文本证据权 （ WET) . 10 2.1.7期望交叉熵 （ ECE) . 11 2.2文本表示 . 11 2.2.1布尔模型 . 12 2.2.2向量空间模型 （ VSM) . 12

18、 2.2.3隐含语义索引模型 （ LSI) . 14 2.2.4 LDA生成模型 . 15 2.3垃圾邮件过滤中常用的分类算法 . 15 2.3.1 Z近邻算法 （ KNN) . 15 2.3.2支持向量机 （ SVM) . 16 2.3.3决策树 . 17 2.3.4基于数据集的分类器集成 . 18 IV 2.4垃圾邮件过滤的评价体系 . 19 第 3章基于内容的垃圾邮件过滤系统预处理 . 20 3.1中文邮件预处理 . 20 3.1.1中文分词 . 21 3.1.2词性选择 . 21 3.2英文邮件预处理 . 22 3.2.1去除信头 . 22 3.2.2词根还原和停用词过滤 . 24 第

19、 4章基于类别信息的 LDA特征选择及加权算法 . 26 4.1 LDA生成模型相关知识介绍 . 26 4.1.1贝叶斯网络 . 26 4.1.2 EM算法 . 27 4.1.3 LDA生成模型 . 28 4.2基于邮件类别信息的 LDA特征选择 CLDA算法 . 30 4.2.1基于邮件类别信息的 LD A特征选择算法 CLD A概述 . 30 4.2.2 LDA模型参数估计 . 31 4.2.3实验结果与分析 . 32 4.3基于 LDA模型改进的特征加权 Imp-LDA算法 . 38 4.3.1算法描述 . 38 4.3.2实验结果与分析 . 39 第 5章基于反馈学习的随机森林算法 .

20、 44 5.1基于反馈学习的邮件过滤系统 . 44 5.2随机森林算法在邮件过滤系统中的应用 . 46 5.3实验结果比较与分析 . 48 5.3.1特征数量对邮件过滤系统性能的影响 . 48 5.3.2基于反馈学习的随机森林算法的邮件过滤系统性能分析 . 49 第 6章总结与展望 . 52 . 54 目录 g i射 .58 攻读硕士学位期间取得的科研成果 .59 第 1 章绪论 第 1 章绪论 随着网络技术的发展与普及，越来越多的人开始接受、认可并融入到互联网络当中。 近年来，网络作为一项重要的工具已经深入到人们生活，工作和学习的每个角落，产生 了大量衍生品，如：网上银行、网上交友、网上购物

21、、网络游戏等。人们将大量精力， 物力和财力投入到这个虚拟的世界中，除了享受网络所带来的方便快捷，同时也在忍受 网络诈骗、电脑病毒和垃圾邮件等各种负面的影响。垃圾邮件作为阻碍网络发展的重要 因素之一，具有破坏性强，传播速度快，危害范围广等特点。据相关数字统计 ， 全球 每天流通的垃圾邮件达 1150亿封，占电子邮件总量的 75%，这些数额庞大的垃圾邮件 严重干扰了人们正常的工作生活秩序，给社会造成巨大的安全隐患，已经成为全球化公 害。 1.1研究背景和意义 1978年 5月 3 口 DEC公司的市场工作人员 Gary Thuerk发出了第一封具有真正意义 的垃圾邮件 ，从此便揭开了反垃圾邮件的序

22、幕。从第一封垃圾邮件诞生至今已经经历 了几十年的发展演变，但是垃圾邮件的制作传播者与各种反垃圾邮件联盟之间的战争就 从未停歇过，面对垃圾邮件口益横行的局面，各国都纷纷出台相应的政策，从立法、资 金和技术等各个方面坚决抵制垃圾邮件。美国作为世界上第一大垃圾邮件发送国占全球 垃圾邮件总量的 15%，在其发布的一项关于垃圾邮件受害调杳结果显示，多半网民每年 将花掉大约 8天的时间来处理垃圾邮件 。据欧盟的统计，整个欧洲因接收垃圾邮件而 支付的费用多达上百亿欧元。中国互联网协会反垃圾邮件中心在 2009年发布的第三季 度反垃圾邮件调杳数据显示 :中国网民平 均每周收到垃圾邮件的比例为 53.38%，与

23、去 年同期相比下降了 4.51%，但与第二季度相比上升了 2.12%。澳大利亚，口本，韩国， 俄罗斯等国也都在不同程度上受到垃圾邮件的侵扰。 垃圾邮件占用了大量的网络资源，造成网络通道阻塞，降低了运行效率，严重影响 中国科学院邮件系统电了期刊第五十七期 http:/ * 第 一 封垃圾邮件 http:/ 中国科学院邮件系统电了期刊第六十二期 http:/ 士 2009 年第三季度中国反垃圾邮件结果发布 http:/survey.anti- _ 河北大学工学硕士学位论文 _ 了网络的正常工作；部分垃圾邮件已经成为电脑病毒、广告诈骗、色情暴力、反政府等 各类刑事犯 罪的载体，给社会安全带来极大隐患

24、；垃圾邮件侵犯了收件人的隐私，处理 垃圾需要占用大量的时间和精力，严重干扰了人们的正常生活 。造成垃圾邮件泛滥主 要有以下几方面原因1: (1) 垃圾邮件自身具有低成本、高产出、高回报、传播性强的特点，致使一些唯 利是图的不法分子疯狂制作和发送垃圾邮件。个人网上行为的随意性，轻易泄露个人隐 私等都给垃圾邮件的制作者以可乘之机。 (2) 垃圾邮件的种类繁多，手段不断翻新，且其内容表现形式上也涉及到声音、 图片、网页和格式变形等多种变化，这都给垃圾邮件的过滤和认定工作带来一定的困难。 图 1列出了垃圾邮件内容分类示意图 。 欺诈类成人类 金融类 欺骗类 9% 图 1垃圾邮件内容分类示意图 (3)

25、对于垃圾邮件的定义没有一个全社会性的广泛认同。针对不同使用人群，判 定垃圾邮件的标准不同，大多数人宁可不去过滤垃圾邮件也不愿意让正常的邮件被过滤 掉，给垃圾邮件过滤的准确性上提出极高的要求。 总之，造成垃圾邮件泛滥的原因是多方面的，对于垃圾邮件的治理工作是一场持久 战。只有不断地革新技术才能先发制敌，不给垃圾邮件以可乘之机。同时应加快垃圾邮 件立法化进程，健全法律制度，使垃圾邮件的制作和传播者受到法律的制裁。 1.2垃圾邮件过滤技术研究现状 http:/ ? http:/ _ 第 1 章绪论 _ 面对垃圾邮件日益猖獗的局面，领域专家呼吁要依靠社会各界力量，通过技术过滤、 行政监管、立法防治、行

26、业自律等多种手段共同打击垃圾邮件，维护网民的正常权利 。 由于垃圾邮件自身具有虚拟、隐藏和欺骗性，在治理上还存在许多难度，需要强化技术 防控，从源头上扼制垃圾邮件的蔓延。现有的垃圾邮件过滤技术从过滤的方式和手段上 分，大致可以分为基于规则的过滤和基于内容的过滤，下面将针对这两种方法所采用的 技术手段和存在的问题加以分析，图 2列出了垃圾邮件的主要过滤技术。 垃圾邮件 过滤技术 基于规则 基于内容 过滤 过滤 A 黑白名单 过滤 信头分析 / 关键词 过滤 基于贝叶 斯过滤 /基于决策 树过滤 /支持向量 机过滤 基于其他 算法过滤 图 2垃圾邮件的主要过滤技术 1.2.1基于规则的过滤 基于规

27、则的过滤 1需要通过领域专家对垃圾邮件和非垃圾邮件的特性进行分析，找 出两者的本质区别，总结出相应的差异性作为过滤规则，最后利用这些规则对邮件综合 评判。主要分为黑白名单过滤、信头分析、关键词过滤等。 (1) 黑白名单过滤 黑白名单过滤 就是把垃圾邮件和正常邮件的 IP地址、服务器域名、发件人的地址 等信息分别存入黑、白名单列表中。它是一种比较简单快捷的方法，即保证了纳入白名 单的发信人实施正常行为的权利，也阻止了垃圾邮件的发送行为。此方法只对列表中所 http:/www.cwts.org/showgn.php3?source=yd&id=1571 ? http:/www.rfc-editor

28、.org/rfc/rfc2505.txt 3 河北大学工学硕士学位论文 包含的黑白名单信息生效，名单内容的真实性和完整性将直接决定垃圾邮件过滤的有效 性。该方法存在一定的局限性，需要反垃圾邮件组织不断搜集相关信息扩大黑白名单列 表，浪费了大量的人力、物力和财力。 (2) 信头分析 信头分析 指通过分析电子邮件的表头信息来发现是否存在伪造 IP地址和发件人信 息等异常行为来识别垃圾邮件的一种过滤方法。电子邮件在发送过程中需要中转多个服 务器，最终才能到达收件人的邮箱。下文是一封邮件的表头信息， Received域的内容是 在邮件经过中转服务器时由系统自动添加的，通过对比各个 Received域提

29、供的信息暨可 以鉴别出 “ From: ” 信息是否存在伪造行为，从而对邮件的性质进 行判定。该方法只能针对垃圾邮件的接收端进行过滤，无法在发送端对垃圾邮件进行有 效的拦截，造成了网络资源的浪费。 Received: from (202.112.5.66) by spam- (MIMEDefang) with ESMTP id j7CC5Jst024179 for ; Sun，14 Aug 2005 23:11:39 +0800 (CST) Received: (eyou send program); Sun, 14 Aug 2005 23:20:05 +0800 Message-ID: R

30、eceived: from 166.111.125.123 by with HTTP; Sun， 14 Aug 2005 23:20:05 +0800 From: To: Date: Sun, 14 Aug 2005 23:20:05 +0800 Reply-To: (3) 关键词过滤 关键词过滤 就是找出垃圾邮件中出现频率过高的专用词语，如 “ 郑重承诺 ” 、 “ 大 甩卖 ”和 “ 来电洽谈 ” 等，以关键词的出现来鉴定是否为垃圾邮件。该方法在执行上存 http :/www. spamhaus.org/organization/statements.lasso. ? http:/

31、SpamCorp.Junckemail.org/tonyt/program.html. _ 第 1 章绪论 _ 在明显弊端，需要根据领域专家的指导创建一个庞大的关键词列表，受主观因素影响较 大，关键词选取的好坏直接影响过滤的准确性。 基于规则的方法需要对垃圾邮件的过滤规则进行详细的分析，加入的主观因素较 多，抗干扰能力较弱。由于垃圾邮件的内容和特征处于不断变化中，这就要求规则制造 者必须实时更新规则，否则过滤的准确性将受到限制，而基于内容的过滤技术则可以有 效避免上述问题的发生，下文中将详细介绍该方法。 1.2.2基于内容的过滤 基于垃圾邮件内容的过滤技术是指针对邮件内容采取相应的分类算法，对

32、邮件的所 属类别进行判定，它属于文本分类范畴，主要包括邮件预处理、特征选择、文本表示、 构造分类器等几部分。近年来随着对人工智能研究的深入，该领域 的一些算法 2如决策 树、贝叶斯、支持向量机 SVM等被引入到垃圾邮件过滤的技术中，并取得重大进展。基 于内容的过滤技术还包括其它一些算法如 K近邻、神经网络、模糊聚类、粗糙集等，它 已成为 a前垃圾邮件过滤采用的主要技术手段。 M.Sahaim3最早将贝叶斯算法应用于垃圾邮件过滤系统中，随即引起该领域学者的 广泛关注，越来越多的人致力于此方面的研究。 T. Meyer4将贝叶斯算法与 Chi-squared 算法相结合，构建了一个垃圾邮件过滤系统

33、，有效的解决了分类器的不确定性问题，提 高了分类精度。 J.H V ld5计算每个词的互信息量，并提取该值较大的词作为特征项构 建贝叶斯分类模型，在 PU和 SpamAssassin公开数据集上进行实验，并与 C4.5， SVM， KNN算法作对比，得出系统精确度近似的结论。 H. Drucker6将 SVM和 Bootsting两种分 类器在垃圾邮件过滤中的性能进行了对比。在 AT&T公司搜集的邮件集上利用 TF、 TF-IDF以及两者结合的特征选择算法选取 1000维特征，SVM算法的错误率为 3.27%， Bootsting算法的错误率为 2.78%，但 SVM算法的执行时间要少 于 B

34、ootsting算法。 X.CarreraS7在 :PU1数据集上选取没有经过词根还原和去停用词处理的 26449维特征，经 过 10次交叉验证后得到的测试结果为 Boosting算法的性能最好，而贝叶斯算法与决策树 算法的性能相差无几，但其准确率要略高于决策树。基于垃圾邮件内容的过滤技术受邮 件集的规模、预处理、特征选择及分类器性能等诸多方面的影响，只有均衡考虑上述因 素，选取适 a参数，不断重复实验，才能从根本上提高系统的过滤性能。 5 河北大学工学硕士学位论文 本文对基于内容的垃圾邮件过滤算法研究发现，多数特征选择算法只考虑词特征对 分类的影响而忽略了邮件内容中隐含的语义信息，同时本文也

35、意识到垃圾邮件与正常邮 件所阐述的主题内容是不同的，每种类型的邮件都有各自的表达方式和组织结构。基于 上述问题，本文提出一种基于类别信息的 LDA特征选择算法 Categones-LDA， 简称为 CLDA， 并针对 LDA特征选择权重在向量空间模型中存在的特征项之间缺乏区分度的局 限性提出一种改进的加权算法 ImP-LDA LDA模型采用文本 -主题 -词的三层贝叶斯网络 结构，是一种架构于文 本语义层次的生成模型。在不同类型的邮件集中建立各自的 LDA 模型，分别搜寻构成各个主题的特征信息，有效的克服了 LDA模型中由于忽略类别主 题差异性而造成的系统过滤性能下降的影响。由于垃圾邮件种类具

36、有实时变化的特点且 不同客户群间对邮件过滤系统存在着差异性，本文将反馈学习理论与随机森林算法相结 合，继承了决策树与集成学习的优点，有效的提高了邮件过滤系统的性能。 1.3主要研究内容及章节安排 在本课题的研究中主要从邮件的预处理、特征选择、权重计算、分类器的设计等方 面对如何改善垃圾邮件的过滤性能进行了探索，并 对现有的算法在垃圾邮件过滤中存在 的问题进行了分析，提出了相应的解决措施。 各章内容安排如下： 第一章：阐述了课题研究的背景及意义，从多角度综合分析了垃圾邮件泛滥的原因， 对现有的垃圾邮件的过滤技术及存在的问题进行了总结。 第二章：介绍了基于内容的垃圾邮件过滤系统的各个环节及性能评价

37、指标，对构成 垃圾邮件过滤系统框架的特征选择、文本表示、特征加权、分类算法等部分进行简单的 介绍。 第三章：对中文邮件和英文邮件预处理的区别和特点进行了总结，针对不同语言格 式的邮件进行分别处理，并给出了完整的预处理步骤。在邮件 预处理上加入词频和文档 频度筛选提高了分类精度。 第四章：对 LDA模型进行了介绍，详细探讨了基于类别信息的 LDA特征提取算法 Categories-LDA和改进的 LDA加权算法 Imp-LDA， 并在公开的垃圾邮件数据集上进行 实验与现有的算法进行了对比，并对实验结果做出讨论。 6 第 1 章绪论 第五章：研究了随机森林算法的相关理论，对基于反馈学习的随机森林算法在垃圾 邮件过滤系统中的表现与 K近邻 (KNN)， 支持向量机 (SVM)， 决策树， Bagging， AdaBoost 等分类算法进行对比。 第六章：对所做工作进行总结，并对今后工作做出展望。 7 河北大学工学硕士学位论文 第 2章基于内容的垃圾邮件过滤系统概述 基于内容的垃圾邮件过滤系统主要包括五部分，即邮件预处理、特征选择、文