基于信息增益的混合垃圾邮件特征选择方法
闫巧;冷成朝
【摘 要】Feature selection is a crucial process of spam filtering. The result
of feature selection not only affects the accuracy of classification, but also
affects the computational burden. The popular feature selection methods
such as CHI selection, information gain, mutual information and SVM
feature selection are compared and a mixed email feature selection
method is proposed based on information gain using the conditional
probability and classification discrimination between features to rudce
redundancy among features to overcome their shortcoming that only pay
attention to sorting yet ignore the redundancy among features.
Experimental results show that: the new method is promising and
improves classification accuracy of spam.%特征选择是邮件过滤重要的环节,特征的好坏不仅影响分类的准确率,还直接影响到分类器训练和分类的开销.比较了常用的CHI选择、互信息(MI)、信息增益(IG)和SVM特征选择算法在垃圾邮件过滤中的效果,针对这些方法只排序而未消除特征间冗余的缺点,提出了利用特征词间条件概率和分类区分度消除冗余的混合邮件特征选择方法.实验结果表明:方法效果良好,提高了邮件分类准确率.
第２５卷第６期 ２００８年６月 计算机应用研究 Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ Ｖｏ１．２５，Ｎｏ．６ Ｊｕｎ．２００８
基于组合算法的中文反垃圾邮件分类系统的研究米
孙铁利，张婷婷
（东北师范大学计算机科学学院，长春１３０１１７）
摘要：论述了一种采用组合算法实现的垃圾邮件分类系统，并在Ｗｉｎｄｏｗｓ平台下用Ｖｉｓｕａｌ Ｂａｓｉｃ ６．０实现。本
系统工作在邮件客户端，基于邮件内容的解析，相对于只使用基于分类器的垃圾邮件分类系统，不仅能有效快速
地分类邮件，同时提高了分类的精度、降低误判率。
关键词：垃圾邮件；向量空间算法；贝叶斯算法；组合算法
中图分类号：ＴＰ３０９．２ 文献标志码：Ａ 文章编号：１００１—３６９５（２００８）０６．１８２５—０３
Ｒｅｓｅａｒｃｈ ｏｆ Ｃｈｉｎｅｓｅ ａｎｔｉ—ｓｐａｍ ｃａｔｅｇｏｒｉｚａｔｉｏｎ ｓｙｓｔｅｍ ｂａｓｅｄ ｏｎ ｈｙｂｒｉｄ ａｌｇｏｒｉｔｈｍ
ＳＵＮ Ｔｉｅ—ｌｉ，ＺＨＡＮＧ Ｔｉｎｇ—ｔｉｎｇ （Ｓｃｈｏｏｌ ｏｆＣｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｎｏｒｔｈｅａｓｔ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｃｈｕｎ １３０１１７，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｔｈｉｓ ｐａｐｅｒ ｄｉｓｃｕｓｓｅｄ ｒｅａｌｉｚｉｎｇ ｊｕｎｋ ｍａｉｌ Ｃａｔｅｇｏｒｉｚａｔｉｏｎ Ｓｙｓｔｅｍ ｂｙ ａ Ｈｙｂｒｉｄ Ａｌｇｏｒｉｔｈｍ ａｎｄ ｉｍｐｌｅｍｅｎｔｉｎｇ ｉｎ Ｖｉｓｕａｌ Ｂａｓｉｃ ６．０ ｏｎ Ｗｉｎｄｏｗｓ ｐｌａｔｆｏｒｍ．Ｔｈｉｓ ｓｙｓｔｅｍ ｗｏｒｋｅｄ ｏｎ ｍａｉｌ ｃｌｉｅｎｔ ａｎｄ ｒｅｓｏｌｖｅｄ ｂａｓｅｄ ｍａｉｌ ｃｏｎｔｅｎｔ．Ｒｅｌａｔｉｖｉｎｇ ｔｏ ｊｕｎｋ ｍａｉｌ Ｃａｔｅｇｏｒｉｚａｔｉｏｎ Ｓｙｓｔｅｍ ｗｈｉｃｈ ｏｎｌｙ ｍａｄｅ ｕｓｅ ｏｆ ｓｉｎｇｌｅ ｃｌａｓｓｉｆｉｅｒ，ｔｈｉｓ ｓｙｓｔｅｍ ｃｏｕｌｄ ｃｌａｓｓｉｆｙ ｍａｉｌ ｅｆｆｅｃｔｉｖｌｙ ａｎｄ ｅｆｆｉｃｉｅｎｔｌｙ，ａｔ ｔｈｅ ｓａｍｅ ｔｉｍｅ ｔｈｉｓ ｓｙｓｔｅｍ ｃｏｕｌｄ ｉｍｐｒｏｖｅ ｐｒｅｃｉｓｉｏｎ ｏｆ ｃｌａｓｓｉｆｙｉｎｇ ｍａｉｌ ａｎｄ ｒｅｄｕｃｅ ｍｉｓｃａｒｒｉａｇｅ ｏｆ ｊｕｓｔｉｃｅ ｒａｔｉｏ． Ｋｅｙ ｗｏｒｄｓ：ｓｐａｍ；ｖｅｃｔｏｒ ｓｐａｃｅ ｍｏｄｅｌ；ｂａｙｅｓｉａｎ ａｌｇｏｒｉｔｈｍ；ｈｙｂｒｉｄ ａｌｇｏｒｉｔｈｍ
辽宁经济管理干部学院学报 ２００８年第３期 基于ＫＮＮ一最近邻算法的邮件过滤技术研究 胡锡衡 （１，鞍山师范学院辽宁鞍山１１４００５； 迟呈英 ２．辽宁科技大学辽宁鞍山１１４０５１） 摘要：邮件过滤器—般都是基于朴素贝叶斯概率模型，但是汉语拥有极为复杂的语义环境以即贝叶斯 算法的易欺 尚性，使得贝叶斯概率模型不能很好地过滤中文垃圾邮件。针对贝叶斯算法中存在的不足，尝试 使用改进的ＫＮＮ一最近邻算法过滤中文垃圾邮件。 关键词：邮件过滤；贝叶斯模型；ＫＮＮ－最近邻；文本；垃圾邮件 中图分类号：ＴＰ３９３．０８ 文献标示码：Ａ 文章编号：１６７２－５６４６（２００８）０３～００６２一ｏ２ 一、ＫＮＮ一最近邻算法介绍 贝叶斯分类是一种基于统计的分类方法。它可以预测类 成员之间的关系。贝叶斯算法由于方法简单，运行速度快， 分类精度高，被广泛应用于文本分类和信息检索。用ｄ表示 文本向量，他共有ｎ个特征项 ， ，．，．， ），样本空间共有ｍ 个类（ｃ， …， ）一般贝叶斯模型如下图所示： Ｂａｙｅｓ模型图 Ｂａｙｅｓ模型包含一个表示类变量的结点ｃ和表示类特征 项的结点 （ｆ＝１，２，…， 两个结点间有箭头相连，表示 这两个变量不独立；如两个结点间无箭头连接，则表示这两 个变量之间相对独立。给定一特征项为 （ １，２，…， ） 的文本ｄ，则文本ｄ属于类 的贝叶斯公式为： 粥ｌｄ）－ ）ｘ ｌｃ＾）／ ） 由贝叶斯公式可知，要判定一个邮件的类别可以通过计 算， ｆ 来实现，它表示由该文本中出现的单词与向量空间 模型中特征项的匹配情况，而决定该文本属于第 类概率， 把文本归到具有最大后验概率值Ｐ（Ｃ Ｉ啪类中去，得到最佳 的分类结果。 贝叶斯分类中的不足：在应用贝叶斯分类器进行文本分 类时，设定的文本类别是感兴趣与不感兴趣两类。在采用贝 叶斯分类法对电子邮件进行分类的过滤系统中，大多数直接 将电子邮件分为垃圾邮件和非垃圾邮件两类。这种两值的情 况会造成一些非垃圾邮件“误承认”问题。造成此种问题的 原因是贝叶斯分类器中只是简单的根据预定的阈值将电子邮 件分为垃圾邮件和非垃圾邮件。如果将电子邮件处理成多类 别的情况，例如非垃圾邮件、垃圾邮件和不确定邮件，那么 新的问题又会出现：一是阈值选为多大；二是不确定类别邮 件的存在会造成过滤效率的降低。 ＫＮＮ分类法是著名的模式识别统计学方法，对于未知 和非正态分布可以取得较好的分类准确率。训练样本用ｎ维 ．６２． 特征项描述，每个样本代表ｎ维空间的一个点。这样，所有 的训练样本都存放在ｎ维模式空间中，当给定—个未知样本 时，ＫＮＮ算法搜索模式空间，找出最接近该未知样本的Ｋ 个训练样本。这Ｋ个训练样本就是未知样本的Ｋ个“最近 邻”。Ｋ的大小根据具体应用环境选择，通常在几十到几百 之间。衡量样本之间的距离或相似性的方法，一 是用欧几 里德距离，即两个点 ＝（ 。， ：，．．， ）和 ＝ 。， ，，．．， ）之间的 欧几里德距离： 压———■ 口 ， ）＝，』 ～ ）ｚ 男一ｊ 是利用两 的余弦表示相似囱 式： ∑ × 州 ， ） 了 ｌ＿— 一 、／（∑ ×∑ ） ＇Ｍ Ｈ 由于此分类算法在训练阶段不需要首先建立模型，只是 将训练数据存储进数据库中，几乎没有计算开销，因此时间 开销相对来说比较小。本文试验采用ＫＮＮ过滤垃圾邮件的 具体步骤如下： 在训练邮件集中选出与测试邮件最相似的Ｋ个邮件样 本，计算两个样本的相似度。其中，Ｋ值的确定目前没有很 好的方法，一般采用先定一个初始值，然后根据实验测试的 结果凋整Ｋ值，实验中根据样本的比例选定Ｋ为１００。 在测试样本的Ｋ个邻居中，依次累加每类的权重，计 算公式： 一 ）＝ 砌 ） ｄＥ 其中． 为测试样本的特征向量，砌 ）为相似度计算公 式，与上一步骤的计算公式相同， ｅ（４，ｃＪ）为类别属性函数， 即如果 属于类ｃＪ，那么函数值为１，否则为０。 比较类的权重，将测试邮件分到权重最大的那个类别 中。 二、结果与评价标准 实验中把收集到的邮件样本分成两组：一组取２６６封邮 件作为训练样本，其中９４封正常邮件和１７２封垃圾邮件； 再取另外１００封邮件作为测试样本，其中３０封正常邮件， ７０封垃圾邮件。另一组取１０００封邮件作为训练样本，其中 １７６封正常邮件和８２４封垃圾邮件；再取另外２００封邮件作 为测试样本，其中５０封正常邮件，１５０封垃圾邮件。这些
信息技术 ２０１１年第０５期ｌ轻一工一设一计
基于贝叶斯算法分类的反垃圾邮件系统的实现
孙瀛
（北华大学工程训练中心，吉林吉林１３２０２１）
摘要：本文对中文垃圾邮件的特点进行分析和研究，探讨基于内容分析的邮件过滤方法，分析贝叶斯算法及其改进算法的原理
和实现方法，并研究过滤原型系统的设计、实现方法。
关键词：垃圾邮件；邮件过滤；贝叶斯理论；过滤模型
伴随着电子邮件的迅速普及，越来越多的人群使用电子邮件。然而，
电子邮件在为人们提供方便的同时也成为垃圾邮件、病毒、恶意程序或敏
感内容邮件传播的重要载体，对系统安全造成了严重的威胁。近几年来，
垃圾邮件的泛滥是由于专门发送垃圾邮件的服务器大批涌现。由于网络
的开放陛，垃圾邮件成为互联网上的—个日益严重的全球性安全问题，越
来越得到社会大众和研究人员的重视和关注。因此，针对这一问题尽快寻
找解决方案的需求也更加迫切。
１垃圾邮件的定义及其危害
２００３年，中国互联网协会在《中国互联网协会反垃圾邮件规范》中对
垃圾邮件作了以下定义：收件人事先没有提出要求或者同意接收的广
告、电子刊物、各种形式的宣传品等宣传ｌ生的电子邮件；收件人无法拒收
的电子邮件；隐藏发件人身份、地址、标题等信息的电子邮件；含有虚假
的信息源、发件人、路由等信息的电子邮件。
垃圾邮件的泛滥给人们带来的危害和损失主要体现在以下几个方
面：垃圾邮件给网络运营商（ＩＳＰ）造成了严重的损失。大量的垃圾邮件在
网络上传播，占用了网络带宽，导致网络通信质量下降，甚至是网络发生
拥塞，干扰邮件系统的正常运行；垃圾邮件侵害了用户的隐私权；垃圾邮
件给网络带来了各种安全性的问题；垃圾邮件成了计算机病毒新的、快速
的传播途径。 ２基于垃圾邮件特征向量判断垃圾邮件算法的设计
通过贝叶斯原理，构造适合本文的过滤算法，算法的一股ｌ生语言描述
为：
初始化总的概率值ｄＶａｌｕｅ为０
获得邮件信息； 从数据库中获得类别结构链表信息；
