基于逻辑回归模型的垃圾邮件过滤系统的研究.doc

基于逻辑回归模型的垃圾邮件过滤系统的研究 哈尔滨工程大学硕士学位论文基于逻辑回归模型的垃圾邮件过滤系统的研究姓名:安波申请学位级别:硕士专业:计算机应用技术指导教师:顾国昌20090301哈尔滨工程大学硕士学位论文摘 要垃圾邮件的传播蔓延,严重侵害了电子邮件用户利益,影响了电子邮件服务运营秩序,危害了互联网安全和社会稳定,已经成为互联网一大公害。本文研究了使用文本分类进行邮件过滤的方法。基于机器学习理论的垃圾邮件过滤算法是解决垃圾邮件问题的研究热点,本文重点对中文过滤特征项和垃圾邮件过滤模型两方面进行研究。本文采用在线逻辑回归模型解决垃圾邮件过滤,提出了字节级元文法获取邮件特征,有效解决了垃圾邮件特征获取的问题,应用该文法不仅简化了特征提取,还使得过滤器具有能够处理图像、病毒邮件的能力,为大幅提高垃圾邮件过滤器的性能奠定了基础;本文采用训练方法进行垃圾邮件过滤器的训练,减轻了系统对训练数据的需求,提高了系统的效率,同时还提高了系统的鲁棒性。实验结果表明,该方法的性能极佳,可以满足实际应用的需求。本文描述的系统参加了中国计算机学会主办的垃圾邮件过滤评测,获立即反馈、主动学习、延迟反馈全部在线评测项目的第一,性能优于第二名倍左右;在另外两个中文测试集 和通上也显著优于当年评测的最好结果。关键词:垃圾邮件过滤;机器学习;在线判别学习;文本分类;逻辑回归;字节级元文法;哈尔滨工程大学硕士学位论文, .? . . ,.,.? ,., ,. . . ,.,. .: ; ; ; ?;?哈尔滨工程大学学位论文原创性声明本人郑重声明:本论文的所有工作,是在导师的指导下,由作者本人独立完成的。有关观点、方法、数据和文献的引用已在文中指出,并与参考文献相对应。除文中已注明引用的内容外,本论文不包含任何其他个人或集体已经公开发表的作品成果。对本文的研究做出重要贡献的个人和集体,均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。作者签字:民政日期: 争罗年,月;日哈尔滨工程大学学位论文授权使用声明本人完全了解学校保护知识产权的有关规定,即研究生在校攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨工程大学有权保留并向国家有关部门或机构送交论文的复印件。本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据库进行检索,可采用影印、缩印或扫描等复制手段保存和汇编本学位论文,可以公布论文的全部内容。同时本人保证毕业后结合学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈尔滨工程大学。涉密学位论文待解密后适用本声明。口本论文囱在授予学位后.口在授予学位个月后解密后由哈尔滨工程大学送交有关部门进行保存、汇编等。导师签字:祆团昂作者签字:交为日期:。彩年月口日穹年亨月日哈尔滨程大学硕士学位论文第章绪言本章介绍课题的来源、背景和意义,分析国内外研究现状,并给出本文的主要内容和组织结构。.课题的来源本课题来源于黑龙江省科技厅年攻关项目项目编号:“基于在线判别学习的垃圾邮件过滤器的研究与开发,该课题负责人为黑龙江工程学院计算机系雷国华教授。目前上垃圾电子邮件泛滥是一个亟待解决的问题。有关垃圾邮件过滤的评测会议在国际上有文本检索会议,是由美国国家标准和技术局, 和美国国防部高等研究计划局,联合举办。的总目标是支持在信息检索领域的基础研究,提供对大规模文本检索方法的评估办法。从年开始,中加入了 测试。的目的是为垃圾邮件过滤器提供一个标准的测试平台,以支持垃圾邮件过测试为垃圾邮件过滤器提供了一系列按时间顺滤方面的研究。序排列的邮件报文,数据量大,语料规范、真实,具可比性、公开性。提供了一个垃圾邮件过滤器评估工具包,过滤器只要实现评估工具包规定的接口,就可以使用测试平台进行测试。中文信息处理研究起步较晚,国内比较有影响的评测会议有全国搜索 引擎和网上信息挖掘会议 哈尔滨工程大学硕学位论文,自年开始加入垃圾邮件过滤部分,目的在于为垃圾邮件处理的国内外研究组织提供一个交流的平台;建立并完善一个以中文为主的大规模邮件数据集。该邮件数据集包含正常邮件和垃圾邮件,可作为评测垃圾邮件过滤系统的数据集,能反映最新垃圾邮件特征。本文研究的垃圾邮件过滤系统是基于 测试要求的接口进行的,通过实现该接口,可以与处于研究前沿的过滤器进行比较并分析各过滤方法的优劣。.课题的背景及意义迄今为止,垃圾邮件在国际上没有统一的定义。在中国互联网协会反垃圾邮件规范中垃圾邮件被界定为:.收件人事先没有提出要求或者不同意接收的广告、电子刊物以及各种形式的宣传邮件。.收件人无法拒收的电子邮件。.隐藏发件人身份、地址、标题等信息的电子邮件。.含有虚假的信息源、发件人、路由等信息的电子邮件。按照上述界定,上面四类邮件都属于垃圾邮件范畴。相反,可以称收到的其他邮件为“合法邮件。对大多数用户,收到的垃圾邮件大部分都是没有主动订阅的广告、电子期刊等宣传品,其基本特征是“不请自来、带有商业目的或者政治目的。实际上,垃圾邮件的判定会因人而异,不同的用户对同一邮件的判定结果可能存在差异。目前,很多用户都使用免费邮箱,这类邮箱对垃圾邮件的防范能力较差,垃圾邮件发送者可以很容易的通过穷举、猜测等途径获得用户的邮件地址。人们在学习和工作中也不可避免的要经常对外公开自己的邮箱地址,如完成各种网站的会员注册、公开自己的联系方式等,这正好也给了垃圾邮件可乘之机。一些人专门收集邮件地址,然后有偿转让给有这种需求的垃圾邮件发送者。哈尔滨程大学硕士学位论文现在越来越多的垃圾邮件是通过中继发送的,即远程机器利用某台服务器向外发垃圾邮件。标准的电子邮件传输协议在传输邮件时,不进行用户的身份认证,邮件可以被匿名或冒名发送。因此,任何人都可以利用邮件服务器对任意地址发送邮件,使得服务器无限转发 。目前己经有很多邮件服务器的升级版本支持了关闭 的方法,但由于系统管理员的疏忽,这一漏洞经常没有得到即时修补。作为垃圾邮件的发送方,其成本是极低的,通常是通过各种方式群发。而对电子邮件服务提供商和用户而言,垃圾邮件却给他们带来很大的危害和损失。具体的说,其危害主要表现在以下几个方面:.占用网络带宽,浪费网络资源,干扰邮件系统的正常运行。当有限的网络资源和网络带宽上充斥大量的垃圾邮件时,就降低了网络的使用效率。对邮件服务器而言,收到的垃圾邮件占用了它的磁盘空间,而且,如果垃圾邮件得不到有效控制,用户会放弃邮箱,服务商将被迫终止服务,给企业带来很大的损失。另外,当一些用户利用邮件服务器对外发送垃圾邮件时,该服务器会被列入黑名单而遭外部封杀。因此,邮件服务器既要拒收来自外部的垃圾邮件,还要阻止自己的邮件用户对外发送垃圾邮件。.浪费用户的宝贵时间和上网费用。如果网民每天都要花费一段时间来处理垃圾邮件,工作效率就要降低,对整个社会来说,被浪费的时间更是一大笔宝贵的财富。有关调查显示,年,网民平均每天需花费.分钟来处理无用的邮件,单是下载垃圾邮件所花费的上网费与电话费,全年就要浪费全球网民亿美元。.对网络安全形成威胁。一些垃圾邮件传播色情、反动等各式各样的有害信息,给社会带来危害。黑客们利用电子邮件系统发送数以万计的垃圾邮件攻击目标,使之瘫痪、拒绝服务。垃圾邮件还可以被病毒利用,成.为它们的传播途径。面临着垃圾邮件问题日益严重的现状,人们开始从多方面寻找解决方案。例如,一些“邮箱运营商成立了专门的部门处理垃圾邮件,并设立哈尔滨程大学硕七学位论文“首席垃圾邮件官”,有些邮件客户端工具也提供了一定的垃圾邮件过滤功能。从世纪年代以来,国内外的许多学者进行了大量研究,为治理垃圾邮件做出了不懈的努力。年月中国互联网协会成立了民间的反垃圾邮件协调小组,推出了中国互联网协会反垃圾邮件工作规范和拒收垃圾邮件指南,从定期公布黑名单到时时公布黑名单。自年月国家四部委联合发文要求整治垃圾邮件和不良信息到年月信息产业部出台的电子邮件服务管理办法。应该说,从民间的行业自律到政府的行政法规的规范,还有网络企业采取的大量的技术手段,对垃圾邮件的治理是全方位的。但是中国互联网协会反垃圾邮件中心发布的年第四季度反垃圾邮件调查报告显示,垃圾邮件在规模上不断增长,年全球%的邮件是垃圾邮件,年第四季度中国网民平均每周收到的垃圾邮件比例为.%;垃圾邮件越来越具有攻击性,技术手法也更复杂】。目前各种技术各有优缺点,技术的更新始终没有跟上垃圾邮件的“进步,经济损失在加剧。垃圾邮件的治理是一项长期的工作,任重道远。特别是反垃圾邮件技术和产品,是反垃圾邮件的基础。在反垃圾邮件所做出的各种努力中,基于内容的垃圾邮件过滤器成为了解决垃圾邮件问题的主流。当前的内容式过滤器仍存在局限性,尽管已经有 、 、决策树等多种文本分类模型用于垃圾邮件过滤,过滤器的误判率也降低到了%以下,但现有系统的准确度还不够理想,并且相对于英文,中文没有明显的词与词之间的间隔,因此中文垃圾邮件过滤在技术方面有较大差距。本文将在现有研究成果的基础上探索进一步提高以中文为主的垃圾邮件过滤器准确度的途径。.国内外研究现状典型的邮件过滤技术有黑白名单、规则过滤、基于统计分类等嘲。哈尔滨程大学硕士学位论文.黑白名单过滤黑白名单是一个简单有效而最为常用的过滤方法,其工作原理是邮件服务器在收到一封新邮件时,首先查看邮件头部的发送方地址,如果地址在白名单中,则接收或转发邮件;如果地址在黑名单中,则拒收邮件或直接将邮件丢弃。目前,国内外已成立权威性的反垃圾邮件联盟,提供实时的黑白名单服务,如中国反垃圾邮件联盟的实时黑名单,简称,包括近期中国国内的主要垃圾邮件发送源、中国国内动态分配地址。其优点是对垃圾邮件处理能力的要求较低,它能够节省大量的带宽、存储容量和处理时间。缺点是不够灵活,对垃圾邮件的判别准确度不高。.基于规则过滤基于规则过滤是设置一些过滤规则,这些规则通常有信头分析、群发过滤、关键词精确匹配以及邮件内容中的其它特征,包括:特别的词语,如“免费、“订阅”、“发财、“情色”等;特别的格式,如大号的红色粗体字等:伪造的信头,如不合理的日期等。这种技术是指通过将新接受邮件与既定的规则相比较来判定是否为垃圾邮件的技术,基于规则过滤方法的优点是规则较易理解和修改、易推广。如工具,经过合适的参数调整,可以过滤%的垃圾邮件。但是由于这种规则特有的静态属性,使得垃圾邮件发送者很容易就绕开了检查,如在“免费”中间加上两个“簟号,尽量避免使用特别的字体等等。其缺点是需要开发商不断更新邮件规则,而且在规律性不明显的应用领域效果较差。.基于统计分类过滤通常并不仅仅是某几个固定的发件人在发送垃圾邮件,发送者在不断地变化,黑白名单方法有局限性。规则方法的不足之处在于规则都是人工哈尔滨程大学硕学位论文指定的,需要人们不断去发现、总结和更新,人为因素比较多,一些没有经验的用户可能很难提供有效的规则。而且手工制定规则比较耗时,准确率也受到了限制。随着时间的变化,垃圾邮件的特征也在变化,让用户维护这些规则也不是一件易事。人们在长期的观察和实践中发现,垃圾邮件在其行文风格和传输行为上都与正常邮件迥然不同,而且垃圾邮件所包含的话题往往也不存在于正常邮件中。如果能从垃圾邮件和正常邮件中提取有代表性的特征,那么就能够设计有效的算法来区分这两类邮件。一个很自然的想法是,对电子邮件的内容如正文文本进行分析,识别出垃圾邮件。这就将垃圾邮件过滤与文本分类联系起来了,将文本分类中常用的方法引入到垃圾邮件过滤中来。现在很多文本分类的方法可以直接用于垃圾邮件的过滤问题中,比如贝叶斯方法、启发式规则、支持向量机方法、基于实例的学.方法包括最近邻方法和基于案例的推理以及最大熵方法等等。对邮件内容统计分类过滤方法,过滤正确率高,而且速度很快,是垃圾邮件处理技术中很受欢迎的一种方法,具有广泛的应用前景。.其它垃圾邮件过滤方法垃圾邮件格式特征具有多样性,所要应对的反垃圾邮件技术方法同样也要求具有也多样性。对邮件文本内容进行语义分析来判断其发件者的言语行为从而进行邮件分类、过滤【】。为减少邮件过滤的负载和检测效率,通过分布代理的方式进行垃圾邮件过滤,邮件过滤作并行性处理,每一邮件子过滤器同时检测多封邮件,以提高检测效率【。垃圾邮件多变,反垃圾邮件技术也需要不断发展。垃圾邮件指纹检测、邮件实名签名【】、像分析 【】等过滤技术都已得到一定的发展并应用到现有的邮件安全产品中。哈尔滨工程大学硕十学位论文近些年来,使用基于机器学习的文本分类技术对垃圾邮件进行过滤成为了一个新的研究热点,日益受到研究者的重视。应用该技术过滤正确率高,而且速度很快,是垃圾邮件处理技术中很受欢迎的一种方法,具有广泛的应用前景。大学的将方法引入到垃圾邮件过滤的研究中,并进行了实验,他使用单词、人工构造的短语以及非文本规则比如是否还有附件为特征,在一个较小的邮件测试集上取得了优异的性能.%由于机器学习方法的高效率,目前%、多数的研究都是在基于机器学习的空间向量模型上,针对邮件表示、分类方法和训练方法有许多研究机构提出了改进思路。年,和在.垃圾邮件集上做实验,证明了在邮件过滤上,采用判别学习的分类效果比采用生成学习的分类效果要好】。在邮件表示问题上,无损数据压缩算法 和局部匹配预测 等压缩算法被引入到了文本分类及垃圾邮件过滤川,在字符级别上引入了特征依赖。和是数据压缩中使用的动态压缩算法,其原理是根据已经出现的数据流预测后面要出现的数据流,预测的越准,所需的编码也就越少。当把动态压缩算法引入文本分类后,需要使用训练数据为每一类建立一个压缩模型,在进行分类时,用每个模型对目标文本进行压缩,哪个模型压缩的结果小,就说明这篇文本与此分类接近,从而可以判断文本的分类。在词一级的特征上,和 则研究了保存词组的方法。该算法由美国三菱电子研究实验室的锄.博士首先在文本过滤软件 中实现。和算法将词组字符串转换为值,并通过贝叶斯链式法则计算分值,公司的反垃圾邮件系统就使用了/算法进行内容识别过滤。年, 和. 发表了基于在线判别学习的垃圾邮件过滤器训练 ,从理论上提出了新的垃圾邮件过滤器训练方法;该方法提高了垃圾邮件过滤器的哈尔滨程大学硕士学位论文.适应性,与相比,该方法简单,训练速度快。年,将基于在线判别学习的垃圾邮件过滤器训练方法,采用字符级别的特征项定义,进行了 评测,发现选择字符级别的作为特征项,过滤器的性能要比选择词作为特征项好嗍。.研究的主要内容与论文组织结构本文首先从文本分类技术入手,研究了文本分类技术,分析了文本分类与邮件过滤之间的区别,从而将文本分类技术应用于邮件过滤,得到了邮件过滤问题的数学描述,并结合实际的反垃圾邮件应用,抽象出了邮件的在线过滤体系结构。在邮件的在线过滤体系结构下本文重点研究了基于逻辑回归的垃圾邮件过滤系统。本论文分为四章,按如下方式组织结构:第章为绪论部分,介绍了垃圾邮件过滤的研究现状和本课题的背景、目的及意义,提出了论文的主要工作内容和组织结构。第章介绍垃圾邮件过滤的相关技术,本文采用文本分类技术进行垃圾邮件过滤,并阐述文本分类与垃圾邮件过滤的一致性和主要区别。基于机器学习的文本分类算法中,判别学习优于生成学习,垃圾邮件过滤中常用的判别学习算法有、和逻辑回归。第章阐述了一个垃圾邮件过滤系统,该系统的过滤器是基于逻辑回归算法进行建模,提出了邮件特征提取基于字节级元文法作为特征项,训练器采用方法,并给出了系统的部分算法实现。第章对第章的系统实现进行测试,测试采用国际、国内顶级评测会议提供的测试集和评测工具,并对测试结果进行分析。哈尔滨工程大学硕士学位论文第章垃圾邮件过滤的相关技术垃圾邮件过滤的目标是将邮件区分为垃圾邮件和正常邮件,垃圾邮件过滤问题本质是二值文本分类问题,本文应用文本分类的技术进行垃圾邮件过滤,本章重点介绍文本分类等与垃圾邮件过滤相关的技术,为垃圾邮件过滤系统的抽象描述、算法实现等做准备。.文本分类技术文本分类 的任务是:在给定的类别体系下,根据文本的内容以及事先制定的类别体系,将具体文本划归适当类别。类别体系一般由人工按照应用需求构造。基于内容的文本分类需要指导,即一定数量的已分类好的训练文本或者实例,分类系统从训练文本中获取必要的信息,构造分类器。因此文本分类一般都由训练过程和分类过程两阶段构成。文本分类技术的应用很广泛,如新闻网页的分类、电子图书的分类等等。.文本表示计算机并不具有人类的智慧,不能读懂文字,所以必须把文本转化成计算机能够理解的形式,即进行文本表示。,简称表示在目前,通常采用向量空间模型 文本,向量空间模型是 和于年提出的。向量空间模型:给定一个自然语言文档,在选定了特征项以后,用向量,;,;?;,来表示文档,其中,.?.,为特征项,为的权重,并且规定。,.?.,互不相同,称向量哈尔滨丁程大学硕士学位论文瓴,;,;?;,为文档的向量表示或向量空间模型。除了向量空间模型外,还有概率模型。概率模型考虑词与词的相关性,把文本集中的文档分为相关文档和无关文档。以数学理论中的概率论为原理,通过赋予特征词某个概率值来表示这些词在相关文档和无关文档之间出现的概率,然后计算文档间相关的概率,系统据此概率做出决策。本文系统采用向量空间模型描述电子邮件文档。.特征项定义文档表示前,首先要识别并抽取出文档的特征项。目前,广泛用于文档表示的特征项包括字、词、短语、概念、.元组或语句等。近年来,一些基于词法和语法的特征也逐渐出现,但一般需要和传统特征联合使用。.词特征词是文档中的基本单位之一。不同的词对文档表示的区分度不同,频率太高或太低的词的区分度都比较低,而中等频率的词与文档类别的相关性最大, 因此区分度更大,表示能力最强。.短语特征相对于词特征,短语特征的频率要明显低于每个组成成分的频率,因此区分性更好。另外,与单一的词特征相比,短语的表现能力更强,更能反映文档的主题。如,根据文档中的词“数据”和“挖掘,并不能肯定文档就与数据挖掘相关,但是,如果文档中出现“数据挖掘这样的短语,则其被认定与人工智能相关的可能性就很大。.概念特征自然语言中不仅词汇量大,而且不同词间还有多种语义联系,如同义关系、近义关系、泛化关系等,另外一词多义现象也很普遍,如“一般被解释为“老鼠”,而在计算机领域中则通常被解释为“鼠标,因此哈尔滨工程大学硕十学位论文严格区分相同词形的词义对文档的理解非常重要。解决上述问题的常用方法是进行概念标注,并把同义的或相仿的项合并为相应的概念。.字特征字是中文中最基本的语言单位,虽然它不能完整地表示一个语义范畴,但很多实验表明,用字作为文档特征并不会明显降低系统的分类性能,而且, 由于字的数量远远少于中文中词的数量,只占约十分之一,因此所需的计算时间远远少于后者。.特征选择方法训练集中包含了大量的特征,这将带来一系列问题。首先是向量的维数太大,给计算带来了非常大的压力,存储空间大、处理速度慢。其次是特征中实际上有很大一部分是与类别无关的,对分类作用不大。因此,要降低向量的维数,需进行特征选择。先对文本进行预处理,去掉那些常用、标记符,词根还原的对分类用处不大的词称为停用词,等,然后采用某种特征选择方法按照特征项的定义抽取特征。常用的特征选择方法有:、文档频次文档频次,简称是出现特征项的文档数量。通常认为太小的词没有代表性,而太大的词又没有区分度,所以基于的特征选择方法只留下那些介于中间的词作为特征。、互信息互信息 ,简称,定义如下一般的互信息概念是:变量和的,/幸 /尸。在文本分类中,求的是对所有类的平均互信息:沪兰 掣哈尔滨程大学硕十学位论文,表示第类文本在训练文本集合中出现的概率,表示特征在训练文本集合中出现的概率, 表示在第类的文本中的出现概率。越大,特征和类的共现程度越大。、信息增益,信息增益 简称反映了该特征为整个分类所提供的信息量,其定义如下:, ;佑:芝,兰, 艺,;。?表示特征出现的情公式.中,表示特征出现的概率,况下文本属于类的概率, 表示特征,不出现的情况下文本属于类,的概率。下面的公式中相应变量的含义与此相同。、统计量托,面面面 面面而.么胁,均表示文本数量,如表.所示,:彳。表.特征与类关系表类文本集合 非类文本集合出现不出现统计量度量词和类别独立性的缺乏程度,越大,独立性越小,相关性越大。巍表示对所有类别求平均的的统计量。、相对熵哈尔滨工程大学硕士学位论文锄,锗亿,公式也称为距离 ,反映了文本类别的概率分布和在出现了某个词的条件下文本类别的概率分布之间的距离,该值越大,词对文本类别分布的影响也大。、优势率优势率 ,用于二类分类问题:一 ,一、唧川。器 将端仁,解决了文本表示问题之后,可以将文本分类抽象为一般的描述:设类别总数为,/表示第/?.,怫类,提供给文本分类器的训练集训练集中的文本都经过人工预先分好类别的包括文本,特征空间。,.?., 为特征数量, 每篇文本表示为,嵋,.?.,加,?.,一篇待分类的文本泛化表示为以。,:,.?.,%,任务就是将以分到相应的类别中。.文本分类技术解决垃圾邮件过滤无论垃圾邮件如何改变它的表现形式,垃圾邮件要传递的内容是不变的,所以利用基于内容的文本分类方法是一个智能的方法。文本分类算法在垃圾邮件过滤方面已经表现出了强大的功能,精确率达。%以上。用文本分类器过滤垃圾邮件是一个机器学 的过程。机器学习是研究计算机怎样模拟或实现人类的学习行为,以获取新的知识或技能,重新组织己有的知识结构使之不断改善自身的性能,它是人工智能的核心,是使计算机具有智能的根本途径。在垃圾邮件过滤中,过滤器能够根据垃圾邮件的变化发展自我完善过滤规则。在邮哈尔滨丁程大学硕士学位论文件分类时,机器学习就是一个概念学习的过程。就像有个小孩,给他各种类型车的图片,并告诉他种类之间的差别,当拿出新的图片时,向小孩提问这是哪种类型的车。在邮件过滤中,提供给过滤器两种类别的邮件:垃圾邮件和非垃圾邮件,过滤器经过学习,形成了过滤的规则;然后对输入新邮件,能给出分类的结果。邮件的过滤分为训练过程和分类过程,训练过程是一个机器学习的过程,而分类过程是利用训练过程形成的规则来自动把邮件归类。垃圾邮件过滤器的模型描述如下:有一个决策函数厂,通过这个函数能判定一个给定的邮件是垃圾邮件还是非垃圾邮件。用表示垃圾邮件,表示非垃圾邮件,表示要分类的邮件集,则需要找到函数:一,日其中瓴,;,;?;一,%,.,为特征项,为的权重。但是邮件过滤与通常的文本分类是不完全相同的,垃圾邮件过滤不是简单的文本分类问题,垃圾邮件的发送者常常想尽办法来绕过过滤器,所以垃圾邮件过滤器的要求必须是很严格的。和通常的分类问题相比,邮件过滤有很多自身的特性,主要如下:、在线性邮件过滤是在线应用,过滤器必须具备较高的过滤速度。电子邮件的各种特征随时间不断发生变化,为了使过滤器随时间具有很好的泛化性,自学习功能是在线邮件过滤的关键。把历史邮件当作训练语料,采用机器学习方法能够在线精化过滤器,但是训练集随时间逐步增大,导致训练时间增加,反过来又影响过滤速度。因此针对邮件过滤的在线性,应该考虑如何选择训练语料。此外分类时的计算量也是需要考虑的问题。、结构性邮件过滤的对象是一种半结构化的数据,通常包含标题、正文、发送地址、接收地址等多个域。邮件的结构性方便了特征的分析抽取,另一方面半结构化的邮件比纯文本有更多的分类特征可供选择。不同特征项,不同形式的过滤策略,具有各自的优势和不足,是中文信息过滤的特有问题,因此需要探索适合于中文垃哈尔滨程大学硕士学位论文圾邮件过滤的过滤单元。、客户性邮件过滤是客户性很强的应用,同一个邮件对于客户来说是,对于客户来说却是,所以邮件过滤中应该考虑这种客户化的特性,必须把客户的反馈引入过滤之中。、非均匀性待过滤的邮件分布极不均匀,占绝对多数。因此不能简单的用分类问题的准确率来评判邮件过滤的好坏。邮件正文长度也是很不均匀的,有的邮件正文很长,有的邮件正文可能会很短,判定那些正文很短、信息量很少的邮件更加困难。总之,邮件过滤具有以上的四个特性,因此邮件过滤与通常的文本分类问题不同,而是一个在线二值文本分类问题,在研究垃圾邮件过滤时应加以重点考虑。针对邮件过滤的四点特性,本文考虑如下:第一, 利用在线性以及客户性,可以使用用户的反馈对过滤器进行训练;第二, 当垃圾邮件伪装为退信或回信形式时,邮件的半结构性是没有作用的,因此不考虑邮件的半结构性;第三, 本文的过滤方法是基于概率统计的,同一个邮件,当只有很少的一部分用户认为是垃圾邮件,而其他用户认为不是时,则该邮件为正常邮件;第四, 邮件过滤的非均匀性是下一步工作中需要考虑的,本文没有考虑。.垃圾邮件过滤中的常用算法机器学习技术可以粗略分为生成学习如贝叶斯模型和判别学习如、最大熵模型。在文本分类领域中,判别学习的分类效果比生成学习的分类效果要好,特别在没有足够多的训练数据的时候,这种现象更明显。在生成学习方面,著名的系统就是基于贝叶斯模型的,在评测中作为基准系统。年,和在.垃圾邮哈尔滨工程大学硕学位论文件集上做实验,证明了在邮件过滤上,判别学习的分类效果比生成学习的分类效果要好。不严格的在线支持向量机 克服了支持向量机计算量大的问题被用于垃圾邮件过滤,并在 评测中取得了很好效果。和提出使用在线逻辑回归模型,避免了、最大熵模型的大量计算,并取得了与上一年度年最好结果可比的结果。接下来,本文仅对垃圾邮件过滤中普遍采用的在线判别学习算法进行介绍。.自学习邻近算法四是模式识别中一种被广为学习和研究的统计学方法。很早就被用在文档分类中,并且是几种经验学习方法中性能突出的一种。基于类比学习,训练样本用维数值属性描述,每个样本代表一个点。在给定新样本后,考虑在训练样本集中与该新样本距离最近最相似的个样本,根据这个样本所属的类别判定新样本所属的类别,具体的算法步骤如下:根据特征项集合重新描述训练样本向量。在新样本到达后,根据特征词分词新样本,确定新样本的向量表示。在训练样本集中选出与新样本最相似的个样本。在新样本的个邻居中,依次计算每类的权重,计算公式如下:冤,五乏,其中,为新样本的特征向量,乏为相似度的计算公式,与上一步骤的计算公式相同,而乏,为类别属性函数,即,如果乏属于类,那么函数值为,否则为。哈尔滨程大学硕士学位论文比较类的权重,将样本分到权重最大的那个类别中。是基于要求的或懒散的学习方法,它所存放的样本,直到新样本需要分类时才建立分类,这使得训练集合随着多变的垃圾邮件而随时变化,有利于邮件精确识别【副。算法可以说是从算法上衍生出来的,算法是找一个最近的邻居,而算法则是找个最近的邻居。因此它的分类响应时间要长于算法,计算复杂度和训练集中的文档数目成正比。不过,算法简单有效,所以在大型应用中获得广泛应用。从分类的过程来看,方法最直接地利用了样本和样本之间的关系,减少了特征选择不当对分类造成的不利影响,从而最大程度地减少了分类过程中的误差项。另外,对于一些特征不是很明显的类别,方法更能体现出其分类规则独立性的优势。虽然应用很广,但是它一个最大的缺点就是计算的时间复杂度高。为了从训练样本中找的个近邻,不得不计算与所有样本的相似度;同时,计算出的相似度又要经过很多次比较,才能从中找到的个近邻。当训练样本数很大时,这两部分都是很耗时的工作。因为算法是一种懒散学习算法,在训练期间没有对数据进行进一步的抽象和概括,所以才使得计算的负担全部落在了分类部分。从上面的分析可以看出,要想减少的计算负担,可以从两方面对算法进行改进:在保持或近似保持分类性能不变的条件下,减少训练样本集的大小。在保持或近似保持分类性能不变的条件下,采用快速算法,减少比较次数。对第一个方面进行改进的算法称为“编辑”方法,主要是利用聚类的方法对样本进行压缩,去掉其中对分类作用不大的样本,并且把对分类有相同贡献的冗余样本进行合并。年,提出的方法是首先对训练集合中的所有样本进行分类,然后除去那些被错误分类的训练样本,企图通过除去不明确的训练样本来分开分类区域。年,提出了相反的方法,除去训练集合中所有被正确分类的训练样本,企图通过除去决策区域内部的训练样本来定义类别之间的边界。随着近几年来数据挖掘技术的发展,已经哈尔滨程大学硕士学位论文有许多更好的聚类算法【】可用于解决这方面的问题。对于第二个方面也有很多文献提出了改进算法,如文献【】提出了一种基于小波域部分距离搜索的近邻搜索算法,对一个待分类的未知样本,此算法在小波域中利用部分距离搜索方法快速地找到个近邻,从而适当地减少了计算复杂性。文献】提出了一种快速算法,在搜索个近邻前,先将特征向量变换到小波域,再利用两个向量逼近系数和距离的关系这一重要特征排除大部分不可能是个近邻的向量,进而大大提高分类速度。文献【】基于也提出了一种改进的快速算法。上述算法都在一定程度上减少了比较次数,但并没有完全消除相似度之间的比较。.支持向量机,简称,也叫做支撑向量机支持向量机方法是年扫在解决模式识别 问题时引入的一种经验学习方法【】。这种方法定义在向量空间中,问题的核心在于寻找一个最佳解决方案,将线性可分割空间中的点用一个决策面划分为两部分。,方法的决策面是一个使用结构风险最小化准则原理构造的超平面。方法是建立在统计学习理论的维理论和结构风险最小化原理基础上的,提供了一个与问题维数无关的刻画函数复杂性的方法,它引入高维特征空间,将输入空间的非线性决策边界转化为高维特征空间的线性决策边界,利用线性函数的对偶核,解决了数值优化的二次规划求解问题,根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折衷,以获得最好的推广能力,在解决小样本学习、非线性及高维模式识别问题中表现较好,在两类分类问题上效果最佳【】。的主要思想可以概括为两点: 第一,它是针对线性可分情况进行分析,对于线性不可分的情况:通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分,从而使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可能;第二,哈尔滨工程大学硕士学位论文它基于结构风险最小化理论之上在特征空间中建构最优分割超平面,使得学习器得到全局最优化,并且在整个样本空间的期望风险以某个概率满足一定上界。支持向量机的目标就是要根据结构风险最小化原理,构造一个目标函数将两类模式尽可能地区分开来,通常分为两类情况来讨论:、线性可分情况在线性可分的情况下,就会存在一个超平面使得训练样本完全分开,该超平面可描述为:?其中,“.,是点积,是维向量,为偏移量。最优超平面是使得每一类数据与超平面距离最近的向量与超平面之间的距离最大的这样的平面。最优超平面可以通过解下面的二次优化问题来获得:忉:知圳满足约束条件:乃?,?,聆在特征数目特别大的情况,可以将此二次规划问题转化为其对偶问题:弧形口:窆%一羔/五.一,。口。 一? 一【。满足约束条件:,.?.,刀?%,%哈尔滨程大学硕学位论文这里口口.?口。是乘子,是最优超平面的法向量,是最优超平面的偏移量,在这类优化问题的求解与分析中,条件将起到很重要的作用,在公式.中,其解必须满足:口少?石一,?,阼 ?从公式知,那些口。的样本对分类没有任何作用,只有那些口,的样本才对分类起作用,这些样本称为支持向量,故最终的分类函数为:厂,%?石,根据厂的符号来确定的归属。、线性不可分的情况对于线性不可分的情况,可以把样本映射到一个高维特征空间,并在此空间中运用原空间的函数来实现内积运算,这样将非线性问题转换成另一空间的线性问题来获得一个样本的归属。根据泛函的有关理论,只要一种核函数满足条件,它就对应某一空间中的内积,因此只要在最优分类面上采用适当的内积函数就可以实现这种线性不可分的分类问题。此时的目标函数为:?%一去%口,?,其相应的分类函数为:厂乃口,?常见的核函数包括多项式核函数、径向基函数,函数等。将算法引用到文本分类中,并且将其与其它方法进行性能对比。他的实验结果表明算法在各方面的表现均超过了其它方法哈尔滨程大学硕士学位论文【。将线性用于垃圾邮件过滤,得到的结果印证了这一点。采用二值表示的的性能稍高于采用多值表示的。实验证明,与贝叶斯、神经网络算法进行比较,得到结果效果最佳。但计算量大、速度慢、参数选择经验性强、不能得到很优的解决,一般需借助其它方法进行结合弥补【。.逻辑回逻辑回归 是以某种结果发生的概率为应变量,影响该结果发生的因素为自变量建立回归。逻辑回归中应变量应具有二分特点,应变量的可能取值仅有两种,即二分类变量,如发病与未发病、死亡与生存。逻辑回归和本质上是一致的,都是在寻找具有最大间隔的超平面,不同的是损失函数经验风险的定义不同。但从计算复杂度上看,逻辑回归的计算复杂要明显低于,其分类速度要也比快得多。本文系统采用逻辑回归算法设计过滤器模型,逻辑回归将在下一章作详细介绍。.本章小结垃圾邮件过滤问题本质是二值文本分类问题,因此,文本分类的技术理论上可以应用在垃圾邮件过滤领域,本章首先介绍对文本分类和文本分类中的特征选择等进行简要阐述。但是邮件过滤与通常的文本分类是不完全相同的,垃圾邮件过滤不是简单的文本分类问题。和通常的分类问题相比,邮件过滤具有在线性、结构性、客户性、非均匀性等特性,进而提出垃圾邮件过滤问题是一个在线二值文本分类问题。目前,基于机器学习的文本分类是研究热点,机器学习技术可以粗略哈尔滨程大学硕士学位论文分为生成学习如贝叶斯模型和判别学习如、最大熵模型,判别学习的分类效果比生成学习的分类效果要好,判别学习的常用算法中,逻辑回归算法复杂度低,分类速度快,本系统采用此算法。哈尔滨工程大学硕士学位论文第章基于逻辑回归的垃圾邮件过滤系统本文应用文本分类技术进行垃圾邮件过滤,给出了基于逻辑回归模型的过滤系统,该过滤系统以过滤器和训练器为核心,本章重点阐述过滤器的模型选择、特征项定义和训练方法的选择。.垃圾邮件过滤系统的体系结构过滤器分类器的学习方式可以分为在线学习和离线学习批量学习。在离线学习方式下,通过训练样本调整分类器的参数。在实际应用时,不再调整分类器的参数。在在线学习方式下,分类器根据用户的反馈不断调整系统参数,使系统能够适应不断变化的应用环境。在线学习适用于需要快速更新的环境,受制于在线更新学习器,参数更新算法的复杂度要低,以适应实际应用的需求。离线学习方式反之。为了避免垃圾邮件被过滤器过滤,垃圾邮件发送者不断改进垃圾邮件。这就要求垃圾邮件过滤器具有良好的适应能力。在线学习方式能够满足过滤不断变化的垃圾邮件的要求,这也是和 .评测采用在线学习方式的原因。通过对实际的反垃圾邮件应用需求进行抽象,得到的电子邮件在线过滤的体系结构如图.所示,以过滤器和训练器为中心分为过滤和训练即学习两部分。过滤器根据在线更新的特征库,过滤按实际顺序输入的邮件流,对每个邮件做出或的判断。训练器根据客户反馈对每个邮件的过滤结果进行在线学习,学习的结果进一步精化过滤器的知识库,使得一个邮件到来时能提高过滤器的性能。随着过滤器的不断使用和客户不断反馈,学习器逐渐收集了很多带有客户反馈的邮件,每次学习时都可以使用当前收集到的带反馈邮件集进行训练。哈尔滨工程大学硕士学位论文图.在线垃圾邮件过滤系统的体系结构本文给出的过滤器采用逻辑回归算法进行建模,训练器采用训练方法,提出了字符级的特征项定义。.逻辑回了模型逻辑回归模型是一种判别学习模型,是指采用逻辑回归算法进行建模。逻辑回归 ,算法,和一样,是一种判别学习算法。判别学习算法与以贝叶斯为代表的生成学习有本质差异。传统生成学习认为数据都是某种分布生成的,并试图根据这种分布建模。采用最大似然估计 ,简称来求解模型参数,并用平滑算法来解决数据稀疏问题。这种方法仅当以下两个条件都满足时才是最优的:第一,数据的概率分布形式是已知的;第二,存在足够大的训练数据时才能采用最大似然估计来求解模型参数。但在实际应用中,这两个条件很多时候无法满足。判别学习模型是与生成学习相对应的一类建模方法。其假设条件比弱得多,只要求训练数据和测试数据来自同一个分布即可。而且,判别学习模型的目标往往与实际应用的评价标准密切相关如使得模型在训练数据上的错误率最小化。因此判别学习模型要优于生成学习模型。逻辑回归和本质上是一致的,都是在寻找具有最大间隔的超平哈尔滨工程大学硕学位论文面,不同的是损失函数经验风险的定义不同。但从计算复杂度上看,逻辑回归的计算复杂度要明显低于,其分类速度要也比快得多。逻辑回归是以某种结果发生的概率为应变量,影响该结果发生的因素为自变量建立回归。逻辑回归中应变量应具有二分特点,应变量的可能取值仅有两种,即二分类变量,如发病与未发病、死亡与生存。第章给出的垃圾邮件过滤器的模型描述如下:有一个决策函数厂,通过这个函数能判定一个给定的邮件是垃圾邮件还是非垃圾邮件。用表示垃圾邮件,表示非垃圾邮件,表示要分类的邮件集,则需要找到函数:一,日其中,;,;?;。,%,.,为特征项,为的权重。由邮件过滤问题的模型描述可知,邮件过滤的应变量也仅有两种取值?垃圾邮件和非垃圾邮件。在基于内容的邮件过滤系统中,影响一封邮件是垃圾邮件还是非垃圾邮件的因素是该邮件中的特征。应用逻辑回归算法,可以根据邮件的特征判断该邮件是垃圾邮件的概率:器其中:是该封邮件的所有特征组成的向量,是该封邮件的所有特征相对应的特征权重向量。某封邮件为非垃圾邮件的概率:鼢砌乃罴潞定义一个分界值阈值,通常设为.,就可以判断该封邮件是垃圾邮件还是非垃圾邮件。因此,邮件过滤的函数为:哈尔滨工程大学硕士学位论文,朋四博篇曩施因此最主要的是求各个