邮件分类

2025-01-08

邮件分类（精选4篇）

邮件分类篇1

摘要：以朴素贝叶斯理论作为基石并结合信息增益、代价因子等方法, 尝试设计一种基于用户需求的垃圾邮件过滤分类模型, 在垃圾邮件一次分类基础上提出邮件先过滤后分类方法, 进而改进传统邮件分类一次阈值比较, 变为两次阈值比较, 且应用反馈技术以应对垃圾邮件的日益变化。该模型可能会对垃圾邮件多分类研究具有一定的参考价值。

关键词：朴素贝叶斯,信息增益,代价因子,用户需求,过滤分类

0 引言

科学技术的日益发展, 尤其是电信互联网产业的迅速成长, 促使电子邮件成为现代通信系统的一部分。然而, 在如今信息革命浪潮的强烈冲击下, 各种广告、宣传信息也通过邮件方式传播, 许多邮件中夹杂着病毒程序, 钓鱼网页信息, 攻击某些企业, 欺骗广大网民。这些邮件有着一个共同点———未经用户许可而强行发送到用户的邮件信箱, 称之为垃圾邮件[1]。

垃圾邮件泛滥对整个互联网系统造成了严重负面效应:从网络层次来讲, 它阻碍了互联网健康发展, 如今的垃圾邮件包含其他各种文件格式, 信息量更加丰富, 在网络上大量传输必然会占用大量带宽以及存储资源, 导致网络阻塞现象;从ISP角度来讲, 大量的垃圾邮件会损害ISP的市场形象, 因此可能会被加入到RBL中, 阻断ISP邮件服务器正常通信;从用户的角度看, 垃圾邮件会占据用户信箱的大部分存储空间, 可能会导致信箱空间已满而无法顺利接收正常邮件, 同时大量的垃圾邮件必然会浪费用户花费大量的时间和精力来阅读和清理;从社会层次来看, 部分不法分子会利用垃圾邮件来宣传虚假信息或者是反动信息, 严重扰乱社会秩序和威胁社会安全。鉴于此, 必须采取有效措施来抵制垃圾邮件, 使其危害程度尽可能降低。

1 反垃圾邮件方法

为解决垃圾邮件带来的相关问题, 可以从政府立法和技术手段两方面入手。许多国家就曾经制定出相应的法律来规范垃圾邮件发送行为, 力图减少垃圾邮件的数量。美国在2003年制定出反垃圾邮件法案———非请求色情及广告信息攻击控制法案 (controlling the assault of non-solicited pornography and marketing act, CAN-SPAM Act) [2];澳大利亚的电信法案第107条, 针对个人公司分别制定了不同的规定, 只有得到了收件人的允许, 才能向个人发送垃圾邮件[3];欧洲议会在2002年6月通过了隐私和电子通讯法律规章, 禁止在未征得收件人同意的情况下, 向其发送垃圾邮件[4]。这些法律法规能够在一定程度上降低垃圾邮件发送的几率, 但是并不能够彻底杜绝垃圾邮件的产生。另一方面就是靠各种技术手段对垃圾邮件进行识别并加以过滤, 比如黑白名单技术、SPF源头认证技术、简单模式匹配方法[5]、以及智能垃圾邮件检测技术[6]———包括朴素贝叶斯方法[7]、Ripper方法、人工神经网络、人工免疫系统等。而基于贝叶斯理论的垃圾邮件过滤方法相对而言有比较高的准确率同时该方法简便、有效, 实用范围较广, 以下主要以该方法为基础加以讨论。

1.1 贝叶斯理论

①条件概率:A、B为两个事件, 并且P (A) >0, 称:

为在事件B发生的条件下事件A发生的条件概率。

②乘法公式:两事件的概率P (A) >0, P (B) >0, 由条件概率定义式可得:

此式称为概率的乘法公式。

③全概率公式:事件A为实验E的样本空间S的一个事件, B1, B2, …, Bn为S的一个划分, 并且P (Bi) >0 (i=1, 2, …, n) , 则:

④贝叶斯公式:事件A为实验E的样本空间S的一个事件, B1, B2, …, Bn为S的一个划分, 并且P (A) >0, P (Bi) >0 (i=1, 2, …, n) , 则贝叶斯公式为:

在公式 (4) 中, 通常将P (Bi) 称为先验概率, 将P (Bi|A) 称为后验概率。若把A看做观察的“结果”, 把B1, B2, …, Bn理解为原因, 则贝叶斯公式传递出“因果”的概率规律, 并由此做出根据结果追溯原因的推断, 称之为贝叶斯决策[8]。该决策在信号处理、模式识别、投资决策、环境检测[9]等方面都有广泛应用, 该文以此理论来进行垃圾邮件的类别判断进而达到过滤分类的目的。

1.2 基于用户需求模型设计

传统邮件过滤系统将邮件主要分为两个类别, 一个是垃圾邮件类Spam和正常邮件类Ham, 对待分类邮件D进行特征提取后根据贝叶斯算法求得该邮件的后验概率P (Cj|D) (Cj表示的是邮件所属类别, 这里只能取两种, j=Spam or Ham) , 通过后验概率的大小来确定待分类邮件的最终类别。本模型将Ham类分为两个类别, Ham1和Ham2, Ham1类表示基于特定个人用户或者企业需求邮件类别, Ham2类表示一般性质的邮件类别, 其具体的模型设计内容包括以下步骤:

①收集大量的邮件, 建立训练集数据库, 针对不同的用户需求或者企业要求, 通过人工分析将其归分为Spam、Ham1和Ham2三个类别, 对训练集合中的每封邮件进行特征分析并且提取邮件特征, 建立特征向量, 计算各个类别的先验概率, 形成知识库。

②对新邮件来源进行检测, 同黑白名单匹配, 达到简单过滤效果。

③通过上步骤的邮件, 对其内容进行扫描, 得到该邮件对应特征项的特征值并结合贝叶斯理论和知识库将其送入后验概率计算模块, 求解出对应类别的后验概率。

④求得后验概率, 再引入代价因子, 由后验概率与代价因子的一次比较来确定该未知邮件为垃圾邮件还是正常邮件。

⑤经上一步骤验证的正常邮件再进行代价因子的第二次比较, 确定其最终接收类别, 存储于用户信箱的不同区域。

⑥整个系统运行一段时间后, 再将已经鉴别过的邮件导入到训练集合中, 从而更新垃圾邮件集合中的特征项, 应对垃圾邮件的日益变化, 提高整个系统的分辨能力。

模型的基本流程如图1所示。

1.3 模型计算实现

1.3.1 特征选择

对训练集中的邮件集中分析, 主要是利用分词技术对其进行分词, 将其作为特征项, 并引入特征向量概念, 每一个特征项对应向量中的一个元素, 对于邮件D的特征向量X可以表示为X= (X1, X2, X3, …, Xn) , 由于训练集合中邮件内容的复杂性和多样性必然造成了特征向量X中元素的数目庞大而不利于后期计算, 可采用停用词表和信息增益[10]方法来减少X的元素个数。所谓停用词表指的是那些对文本分类不起作用反而会因为该词数目过多影响正确分类的单词的集合, 当对一封新来的邮件进行特征向量化的时候, 若出现了停用词表中的单词可以直接将其删除。信息增益是描述特征能够为分类系统带来多少信息, 带来的信息越多, 该特征越重要, 它的公式表示:

公式 (5) 中P (Cj) 表示不同类别出现的概率, P (Xi) 指的是特征项Xi在训练集中出现的概率, P (i) 指的特征项Xi在训练集中不出现的概率, P (Cj|Xi) 为在出现特征项Xi情况下属于Cj类的概率, P (Cj|i) 表示特征项Xi不出现的情况下归为Cj类的概率。IG (Xi) 描述了Xi为整个分类提供的信息量, 本模型为三类问题, 若令C0表示垃圾类, C1为基于用户需求邮件类, C2表示一般性邮件类, 则以上公式 (5) 可以转化为公式 (6) :

通过公式 (6) 可以求出训练集中去掉停用词后每个特征项的IG值, 然后将所求的值按照从大到小的顺序排列出来, 取前面N个较大值对应的特征项作为特征向量的元素, 构建特征向量X= (X1, X2, X3, …, Xn) 。

1.3.2 邮件过滤———分类

贝叶斯原理本质是计算出后验概率, 将后验概率作为类别划分的主要参考因素。对新来邮件Dx进行特征分析得到对应的特征向量的特征值x={x1, x2, x3, …, xn}, 采用贝努里事件模型 (每个特征值取值有两种情况, 当Dx中存在特征项Xi, 则对应的特征值xi=1, 若不存在特征项Xi, 则对应特征值xi=0) , 按照贝叶斯原理对其求解:

公式 (7) 中x={x1, x2, x3, …, xn}, 则有朴素贝叶斯公式转化为:

由公式 (9) 可看出对于不同类别Cj其P (X) 都相同, 故此影响分类的主要取决于公式 (8) 中的分子部分, 由贝努里模型特性可将P (X=x|Cj) 转化为:

将式 (9) - (10) 代入到式 (8) 中可得:

将其应用在邮件分类上, 上面的种类Cj可以取三种, 即为CSpam、CHam1、CHam2

若已经求出P (CSpam|Dx) 、P (CHam1|Dx) , 可采用以下简单方法计算P (CHam2|Dx) :

在训练集合中, 邮件总和为N, 垃圾邮件为NSpam, Ham1类邮件总数为NHam1, Ham2类邮件总数为NHam2, 即N=NSpam+NHam1+NHam2, 以上公式中的各类先验概率:

待分类邮件的后验概率是作为其最终分类的重要判别因素, 传统的两类邮件分类系统只需要计算出P (CSpam|Dx) , 再和预先设置的阈值T相比较确定是否为垃圾邮件, 本模型以传统方法为基础采用过滤———分类两步骤进行。

①过滤

该步骤以垃圾邮件特征为主要研究对象, 确定未知邮件是否为垃圾邮件, 从而决定其最终是否过滤。因为在实际生活中, 考虑到垃圾邮件和正常邮件价值的不对等性 (接受一封垃圾邮件一般是不会给人们带来多大影响, 但是倘若系统将一封正常邮件误判为垃圾邮件而将其过滤掉, 就有可能造成经济损失, 尤其是对于一些大型企业) , 这里引入了代价因子λ[11], 它是垃圾邮件和正常邮件价值对比的一种数字化表示方法, 在过滤步骤中可以设定一个代价因子λ1 (λ1>1) , 对于数学表达式:

表达式 (16) 的值大于λ1, 即, 此时的T就相当于传统二分类中的阈值) 时, 可认为该未知邮件为垃圾邮件, 采取过滤措施。

②分类

经过滤环节到达分类步骤的为正常邮件, 分类步骤是以特定用户或者企业需求邮件特征为主要研究对象, 确定该正常邮件是否符合用户需求邮件特性, 从而决定将其存储在用户信箱服务器的哪个区域, 便于用户准确、方便读取邮件信息。在实际生活中, 考虑到用户对这两种正常邮件的重视程度有所不同, 可以再次引入了代价因子λ2, 它表示该正常邮件分别属于Ham1和Ham2的后验概率之比, 对于数学表达式:

表达式 (17) 的值大于λ2 (λ2>1, 即Ham1类邮件重视程度高于Ham2类) , 可认为该邮件为Ham1类, 将其存储在用户邮箱服务器的区域一, 否则认为该邮件为一般性邮件Ham2类, 将其存储在用户邮箱服务器的区域二。

1.4 模型分析

传统的垃圾邮件过滤研究一般采用贝叶斯算法进行特征识别确定邮件类别, 只是单纯将所有的邮件区分为正常和不正常两种情况, 在实际计算过程中也只需要计算出未知邮件属于垃圾邮件类的后验概率进行阈值比较后即可进行接收或者过滤操作, 这种方法比较极端, 而且被识别为正常类别的邮件也比较杂乱, 没有针对性, 不利于用户快速而方便地读取, 倘若系统设置的阈值不合理, 将会整体影响系统对未知邮件的判断结果。本模型在正常类别基础上建立基于用户需求分支类别, 将正常邮件按照用户重视程度再次分类, 针对性较强便于用户准确而快速读取所需邮件, 同时采用了二级阈值 (代价因子) 设置方法, 可以有效缓解传统阈值设置不合理导致整体性能降低的问题:

①传统过滤系统中, 阈值设置偏低, 将会导致部分原本为正常邮件而系统将其判定为垃圾邮件的概率增大, 用户可能因此而不能够正常收发信息, 甚至直接造成经济损失。

②传统过滤系统中, 阈值设置偏高, 将会导致部分原本为垃圾邮件而系统将其判定为正常邮件的概率增大, 垃圾邮件过滤效率不高, 花费用户时间和精力重新查找和清理。

二级阈值设置方法将两个阈值配合起来使用, 可以实现邮件更准确的分类, 比如在实验中可以将一级阈值λ1设置偏低, 二级阈值λ2设置偏高, 可以到达比较好的分类效果, 需要实验数据进一步验证。

2 结束语

本设计采用了目前技术比较成熟的贝叶斯分类算法, 利用信息增益方法进行特征选取, 结合代价因子决定邮件最终类别的设计思想来构建模型, 在理论上存在可行性, 对邮件的多分类或者更为精细分类可能会有一定的指导意义。在后期研究中, 需继续细化该理论模型, 并以此模型为基础, 通过实验数据加以支撑, 借此来确定合理的代价因子λ1和λ2, 使整个系统具有更高的准确率, 进而应用或推广到实际生活中。

参考文献

[1]中国互联网协会.中国互联网协会反垃圾邮件规范[EB/OL]. (2011-08-13) .[2013-04-10].http://www.isc.org.cn/hyzl/hyzl/listinfo-15601.html.

[2]SPAM LAWS.The CAN-SPAM Act of 2003[EB/OL].[2013-04-11].http://www.spamlaws.com/federal/index.shtml.

[3]RUNDFUNK&TELEKOM REGULIERUNGS-GmbH.Telecommunikationsgesetz 2003 (TKG 2003) [EB/OL].[2013-04-11].http://www.rtr.at/de/tk/TKG2003JHJp107.

[4]BLANZIERI E, BRYL A.A Survey of Learning-Based Techniques of Email Spam Filtering[EB/OL].[2013-4-11].http://eprints.biblio.unitn.it/1070/.

[5]陈志贤.垃圾邮件过滤技术研究综述[J].计算机应用研究, 2009, 26 (5) :1612-1615.

[6]谭营, 朱元春.反垃圾电子邮件方法研究进展[J].智能系统学报, 2010, 5 (3) :189-201.

[7]张铭锋, 李云春, 李巍.垃圾邮件过滤的贝叶斯方法综述[J].计算机应用研究, 2005 (8) :14-19.

[8]陈荣江, 张万琴.概率论与数理统计[M].北京:北京大学出版社, 2006.

[9]王明芳, 谭骏珊, 朱明娥.贝叶斯理论在室内空气质量等级识别中的应用[J].中国环境监测, 2010, 26 (2) :63-67.

[10]刘庆和, 梁正友.一种基于信息增益的特征优化选择方法[J].计算机工程与应用, 2011, 47 (12) :130-132.

[11]翟军昌, 秦玉平, 王春立.改进的朴素贝叶斯垃圾邮件过滤算法[J].计算机工程与应用, 2009, 45 (14) :145-148.

邮件分类篇2

Internet的问世带来了电子邮件业务的出现,网络技术的飞速发展促进了邮件服务的广泛普及和繁荣,电子邮件不仅是人们信息交流的重要渠道,也是信息获取的重要途径,而垃圾邮件作为商业广告、恶意程序和敏感内容的载体,对系统安全和用户生活造成了严重的困扰[1]。据中国反垃圾邮件联盟[2]最新消息显示:2009年9月份全球86%的邮件为垃圾邮件,如何有效地防范垃圾邮件,已经成为网络信息安全领域的一个经典难题[3]。

1邮件分类中的概念漂移问题

基于内容的过滤技术是反垃圾邮件的主要技术,特别是基于概率统计的朴素贝叶斯算法因其简单、快速[4]、准确率高[5]、占用存储空间少等优点被广泛应用于垃圾邮件过滤系统中[6,7]。然而,由于邮件的特殊性,人们对垃圾邮件的认定各不相同:(1) 不同用户对同一邮件的判定不相同,例如一份商品宣传类邮件,对有兴趣购买的用户是一个重要的信息,而大多数用户则认为是一份垃圾邮件;(2) 用户的喜好随时间变化,同一份邮件在一个阶段被用户认为是垃圾邮件,在另一个阶段可能就被判定为正常邮件;(3) 垃圾邮件的主题不断变化,即垃圾邮件的概念随时间而变化,这就是概念漂移[8]。

贝叶斯邮件分类是根据训练样本中垃圾邮件和非垃圾邮件的特征预测新邮件属于某一类别的概率,然后根据概率大小做出判别。然而随着时间的推移,贝叶斯分类的准确率逐渐下降,主要原因有:(1) 垃圾邮件的概念随时间变化,固定的训练集不可能具有完备的数据,需要分类器不断学习新的邮件样本;(2) 概念漂移预先未知,增加了学习的复杂性;(3) 用户对垃圾邮件的认定各不相同,现有的服务器端通用过滤器不适应邮件分类的个性化需要;(4) 传统的学习算法都采用静态学习样本[6,7],难以适应邮件概念的动态变化。针对这些问题,本文提出了一种基于用户反馈的贝叶斯动态学习算法,将其应用于客户端,使每个用户拥有各自独立的分类器,而且可以根据需要不断学习。

2基于用户反馈的客户端动态学习算法

2.1贝叶斯邮件分类算法

将邮件ei表示为向量 $\bar{x_{e i}} = (x_{1}, x_{2}, \dots, x_{n})$ ,其中x1,x2,…,xm是ei的特征词,基于朴素贝叶斯假设,邮件ei属于类别Ck的概率可表示为[9]:

$Ρ (C_{k} | \bar{x_{e i}}) = \frac{Ρ (C_{k}) \prod_{i = 1}^{m} Ρ (x_{i} | C_{k})}{\sum_{k \in {l e g i t, s p a m}} Ρ (C_{k}) \prod_{i = 1}^{m} Ρ (x_{i} | C_{k})}$ (1)

采用多项式事件模型,P(xi|Ck)表示如下:

$Ρ (x_{i} | C_{k}) = \frac{1 + \sum_{j = 1}^{| c_{k} |} Ν (x_{i}, e_{j})}{p + \sum_{i = 1}^{m} \sum_{j = 1}^{| c_{k} |} Ν (x_{i}, e_{j})}$ (2)

其中m为邮件向量的维数,N(xi,ej)为特征词xi在邮件ej中出现的次数,|Ck|为Ck类邮件的数量,p为训练集中不重复的特征词的数目。

建立数据表token(emailID,wordID,word,tcount,ntime)和train_emai(emailID,flag,spam)保存统计数据(tcount记录word出现的次数;ntime记录该word最近一次被访问的时间),利用式(1)、式(2)计算 $\bar{x_{e i}}$ 属于垃圾邮件的概率,如果此概率大于某一阈值,就将其归为垃圾邮件,否则为非垃圾邮件。用数据库保存计算过程的中间数据,例如特征项的类条件概率等,以避免重复计算,提高分类效率。

2.2基于用户反馈的客户端贝叶斯动态学习算法

动态学习的任务是通过学习新样本,不断更新分类器参数,适应概念漂移,难点是选择学习样本、确定学习序列和降低动态学习的复杂度。本文采用的学习样本由不断收集的新邮件组成,另外当收到用户分类错误的反馈时(即出现了概念漂移),将这些错误分类的邮件也加入学习样本并进行重点学习。学习样本构成测试集T,T不断更新,当分类错误的邮件达到一定数目时,自动触发学习机制。

2.2.1 确定学习序列

有些样本带有较强的类别信息,应该尽早学习;有些样本不利于正确分类,过早学习会干扰正常的学习过程,使分类器性能持续下降,即合理、有效的学习序列能够优化分类器性能。本文采用一种动态学习序列,依次从T中选择有助于提高分类精度的样本实例(衡量标准是对T中实例的分类效果),学习并更新分类器;引入用户反馈机制,使分类错误的邮件加入到分类器的几率相对降低,减少了噪音数据的影响。

假设训练集为L,采用用最小风险贝叶斯决策思想[10],选定e′i∈T,在L′= L + {<e′i,C′i>} 下估计T-{ e′i}的分类损失:

$L o s s (L^{'}) = λ \times \sum_{x \in Τ - {e^{'}_{i}}} (e_{l e g i t \to s p a m}) + \sum_{x \in Τ - {e^{'}_{i}}} (e_{s p a m \to l e g i t})$ (3)

其中 $\sum_{x \in Τ - {e^{'}_{i}}} (e_{l e g i t \to s p a m})$ 表示误判为垃圾邮件的非垃圾邮件数目, $\sum_{x \in Τ - {e^{'}_{i}}} (e_{s p a m \to l e g i t})$ 表示误判为非垃圾邮件的垃圾邮件数目,λ通常大于1,即认为非垃圾邮件的误判造成的损失更大。

算法步骤:

(1) 在训练集L上,使用贝叶斯算法学习得到分类器C;

(2) 对于T中的每一个样本e′i,采用下列步骤计算其加入分类器后的分类损失:

① 利用现有分类器C,分类e′i,得到类别C′i,根据用户反馈修正C′i;

② 在L′= L+{<e′i,C′i>} 上,对T-{ e′i} 中的每一个样本e′j分类,根据式(3)计算分类损失和 $S L^{'}_{i} = \sum_{j \neq i} L o s s_{j}$ ;

(3) 按分类损失和SL′i由小到大的顺序依此学习T中的样本e′i,更新贝叶斯分类器。

2.2.2 更新分类器

算法步骤(3)当样本<e′i,C′i>加入到L后,为提高学习效率,避免分类器更新时的大量重复计算,在单个样本加入时应较少涉及到整体的性质,本文采用式(4)～式(7)更新分类器,在不降低分类效果的同时,减少了新样本学习所需要的计算量。

(1) 类先验概率

$Ρ (C_{k}) = \frac{S}{S + 1} \cdot Ρ (C_{k}) + \frac{1}{S + 1} C = C_{k}$ (4)

$Ρ (C_{k}) = \frac{S}{S + 1} \cdot Ρ (C_{k}) C \neq C_{k}$ (5)

其中S=|L|。

(2) 特征项的类条件概率

$\begin{array}{l} Ρ (x_{i} | C_{k}) = \frac{| S_{C_{k}} |}{| S_{C_{k}} | + \sum_{j = 1}^{m} Ν (x_{j}, e)} \cdot Ρ (x_{i}, C_{k}) + \\ \frac{Ν (x_{i}, e)}{| S_{C_{k}} | + \sum_{j = 1}^{m} Ν (x_{j}, e)} C = C_{k} \land x_{i} \in e (6) \end{array}$

其中|SCk|为Ck类所有邮件的所有词频之和,m为邮件e的维数, $\sum_{j = 1}^{m} Ν (x_{j}, e)$ 表示邮件e中所有特征项的词频总和。e′i加入后,只需对原特征词库中不存在的特征词计算类条件概率,已有特征词的类条件概率采用公式(6)、式(7)在原值基础上更新。

2.2.3 特征库维护

不断增加的学习样本使特征库增长很快,表1是个人邮箱用户的统计数据,10个月中平均样本数和特征数从114和20087增加到了170和24708。为控制增长速度、提高运行效率、降低客户端存储负担,本文根据ntime字段值定期将长时间未使用的特征词及未查询的邮件样本从数据库中删除。

2.3算法评价

2.3.1 空间复杂度

假设L的样本数为n,T的样本数为n′,则训练阶段和动态学习阶段的空间复杂度分别为O(nm)和O(n′m)。

2.3.2 时间复杂度

训练阶段只需扫描一遍训练样本,时间复杂度为O(nm);动态学习阶段,对T中的每一个样本x′i,都要计算对T-{e′i} 的分类损失和,时间复杂度为O(n′2m),为适应概念漂移,分类器必须及时更新,n′2的值应在可接受范围之内。与不进行动态学习的贝叶斯算法相比,动态学习算法在空间和时间上的额外开销都是可以接受的,所以该算法可行。

3实验及结果分析

为模拟概念漂移,实验选用的训练集和测试集来自两个语料库,训练集来自Ling-spam语料;测试集来自spamAssassin语料,邮件样本按时间顺序排列。采用互信息方法选取特征,特征数取150,λ取值9[9],邮件判定结果如表2所示。

定义如下评价指标[11,12]:

$S Ρ = \frac{A}{A + B}$ ,SP越高,非垃圾邮件的“误报率”越低;

$S R = \frac{A}{A + C}$ ,SR越高,垃圾邮件的“漏报率”越低;

$L Ρ = \frac{D}{D + C}$ ,LP越高,垃圾邮件的“误报率”越低;

$L R = \frac{D}{D + B}$ ,LR越高,非垃圾邮件的“漏报率”越低;

$F = \frac{2 S Ρ \times S R}{S R + S Ρ}$ ,F值是召回率和正确率的调和平均。

实验目的是测试一段时间内过滤系统适应概念漂移的能力,采用两种算法进行对比分析,方法1采用传统贝叶斯算法,但不进行动态学习,方法2采用本文提出的动态学习算法。通常提高SP会降低SR,即需要在“误报率”和“漏报率”之间作出权衡,本实验采用F值作为度量标准,测试结果如图1所示。

从实验结果可以看出,随着测试样本的增加,方法1分类性能不稳定,而且垃圾邮件和非垃圾邮件的F值呈现较明显的下降趋势,结果表明贝叶斯在静态数据集上显示出了良好的性能,但不能适应测试集的动态变化,导致分类器性能下降,而且随着时间的推移,下降趋势越明显。随着学习样本的增加,方法2的类别区分信息更加完备,分类器的知识储备更加充足,受到噪音数据的干扰也随之减少,动态学习算法性能相对比较稳定,而且有缓慢的上升趋势,能较好地适应概念漂移。

4结语

文献[13]提出的增量学习算法每次都找出使分类损失最小的实例进行学习,优点是能得到最优的学习序列;缺点是每选择一个实例,都需要计算当前所有实例加入后的分类损失,时间复杂度高(复杂度为O(n′3m))。本文提出的算法时间复杂度降低,适合于客户端动态学习,有很好的实用性。

动态学习算法的另一个优点是不需要重新构建分类器,实际中概念漂移往往是局部性的,特定类型的垃圾邮件会随时间改变,而其他类型则保持不变,动态学习算法能很好地适应这种情况。

邮件分类篇3

当前, 知识和智力资产正在成为企业的竞争优势。知识型企业中, 在已知知识上创造新的、复杂的知识的员工正成为主要角色[1], 商业决策越来越依靠日常工作中相互交流产生的知识[2,3]。知识管理的概念和方法被企业用来寻求应对这种知识社会的变化[4,5,6]。尽管管理知识的重要性已被深入认识, 但系统的知识管理研究是最近10来年才开始的[7]。许多技术和方法被用于结构化知识, 以便有效地管理知识。例如贝叶斯网络 (Bayesian Networks) , 决策树 (Decision Trees) , 神经网络 (Neural Networks) , 支持向量机 (Support Vector Machines) , K最近邻方法 (K-Nearest Neighbor Approach) 等。一些技术方法聚焦在知识搜索领域, 另一些方法用于知识的分类[8]。

分类体系 (Taxonomy) 是一种传统有效的信息分类和管理方法。它包含实体 (对象或者标题) 、关系、链接、分组、标签和导航等部件, 提供信息的搜索、浏览、提示等功能, 实现有效的内容管理[9]。分类体系相比较知识库而言, 提供了一种结构化的知识管理模式[10,11], 其组成要素包括控制词表、元数据和分类目录。由于知识的特性, 传统的人工分类及管理知识的方式是一项高智能和耗费时间的工作。动态分类体系 (Dynamic Taxonomy) 作为一种较好地描述和分类复杂的信息和知识的工具被提出来[12], 能够有效地实现对非结构化知识的分类管理。

在企业的商业运作中, 电子邮件已成为重要的、不可或缺的交流方式, 大量的企业信息和知识蕴含在电子邮件中。本文提出采用动态分类体系的方法, 建立一个基于多智能代理架构的电子邮件信息管理自动分类系统, 以提升邮件自动分类的效率, 促进企业知识的管理和分享, 支持企业商业服务工作的开展。

1 体系架构

电子邮件是当前最重要和最广泛应用的通信媒介之一, 许多公司已把电子邮件作为企业商业运作的重要智力资产。基于WEB的邮件服务系统提供一种集中式的邮件信息管理模式。基于多智能代理架构的电子邮件信息管理自动分类系统 (multi-agent email dynamic taxonomy system, MEDTS) , 包括4层结构, 如图1所示。

1) 邮件代理子系统 (email agent system, EAS) 是MEDTS的基础子系统, 负责电子邮件信息的发送和接收。同时, EAS负责将接收到的电子邮件信息分解为结构化信息, 并存入到邮件数据库 (mail database, EDB) , 以便电子邮件信息能够更方便地被管理和使用。需要说明的是, EAS自身并不是一个电子邮件服务器, 它通过两个电子邮件代理程序与第三方的电子邮件服务器连接。电子邮件发送代理程序 (Sending Agent) 负责通过连接SMTP服务器发送电子邮件, 接收代理程序 (Receiving Agent) 则通过POP3服务器从互联网接收电子邮件。MEDTS建立了一个可伸缩的、较灵活的体系结构, 支持在互联网和内联网中发送和接收电子邮件。

小圆圈表示知识工作的实体, 例如员工等;实线表示信息和知识流;虚线表示实体之间的关系。

2) 动态分类子系统 (dynamic taxonomy system, DTS) 负责将电子邮件中的信息和知识结构化, 并构建分类体系, 形成知识库。邮件中的实体对象、关系、链接、分组、标签和导航由DTS识别和抽取, 并被保存在知识分类数据库 (knowledge taxonomies &inventory, KTI) 。DTS提供搜索、浏览、提醒和内容管理等功能, 以便员工能快速、可视化地发现有用信息和知识。MEDTS系统提供3种动态分类模式增强对知识的分类、整理和检索等管理能力。

3) 知识审计子系统 (knowledge audit system, KAS) 提供对企业智力资产的审计服务功能, 通过挖掘分析KTI中实体间的关系, 可以定位关键人物和社交网络, 搜索和分享知识工作的解决方案。智力资产的评估和评价作为企业管理决策的主要任务之一, 有助于企业高层对其智力资产的全面掌握, 支持企业的商业运作。

4) 知识工作流规划子系统 (knowledge workflowplanning system, KWPS) 构造一个处理知识工作的多代理服务架构, 帮助员工在知识工作中可以动态搜索相关的信息和知识, 高效地找到所需的专业知识。KWPS能够规划一个知识工作流, 并根据具体需要和目标, 配置相应的知识资源。

上述4个子系统构成了MEDTS的4个层次。基于WEB的EAS是基础层;DTS是负责将采集的电子邮件构建为一个动态分类体系, 并保存在知识库中;KAS分析和审计基于电子邮件的智力资产, 评价知识的价值;审计的结果作为KWPS的运作依据。

2 动态分类模式

一般认为, 动态分类体系是使用户可以浏览所有可能的信息分类目录的一种工具, 包括观察、交叉联系、混合和匹配目录, 例如, 邮件信息可被标签和分配到多个目录项中。借助分类体系, 用户可以运用其独特的逻辑, 自由地创造和组织其知识空间[11]。在MEDTS系统中, 设计3种动态分类模式:基于用户定义的分类模式、基于搜索关键字的分类模式和基于多代理机制的动态分类体系模式。前2种模式主要聚焦在如何逻辑地分类大量的信息;第3种模式则通过运用人工智能的文本挖掘和分析技术, 动态辨识和生成新的分类体系。

2.1 基于用户定义的动态分类模式

在信息系统中, 用户访问管理是一项重要功能。根据用户的角色、职位、部门和其他身份认证, 允许合法的访问或禁止非法的访问是主要的应用形式。用户对信息访问的分类视角应根据其角色的不同而不同。

图2给出了企业中3种不同角色的分类视角, 包括员工视角、经理视角和CEO视角。经理负责管理员工, 在其分类体系中包含员工的目录项;同样, CEO的分类体系中也包括了部门的目录项。

动态分类体系根据用户登录身份构建个性化目录, 电子邮件信息被自动分类到相应的目录项中。这种分类模式针对每个用户提供了一个与之关联的有效的分类体系, 无用的信息被屏蔽。

2.2 基于搜索关键字的动态分类模式

基于搜索关键字的动态分类模式是通过对输入关键字的理解自动地生成分类体系。系统建立关键字的语义关联模型, 根据对关键字的语义分析, 调用相关分类体系, 形成语义关联的分类架构, 以满足用户信息分类检索的一般性习惯。例如, 搜索关键字“询价”意味着用户想得到与市场相关的信息, “市场”目录被用来分类搜索结果。类似的, 产品的“白皮书”可能意味着用户想得到产品的技术信息。图3提供了市场和技术2种简单的分类体系。

这种分类模式是一个由用户行为驱动的动态和不断演绎的分类体系, 是一种根据搜索关键字可以逻辑地组织信息和提供合适的分类目录的模式。它不同于通常的搜索引擎的搜索功能, 主要包含着大量的搜索结果的列表, 没有信息组织的逻辑结构。当搜索关键字被输入, 系统会从控制单词的列表中返回其含义, 推断用户的意图, 确定相关领域, 构建检索结果目录。

2.3 基于多代理机制的动态分类体系模式

考虑到信息和知识的不断增长, 新概念、术语和知识在不断产生, 动态分类体系应具备持续改进和演绎的能力。本文采用人工智能技术, 设计了一种基于多代理机制的动态分类体系模式。

代理 (Agent) 提供了需要处理大型和复杂问题的抽象, 具有自治能力。多代理即建立了多个代理的协同工作机制, 智能系统通常采用多代理机制协助用户处理复杂的协同工作。在MEDTS系统中, 几个代理被设计成动态分类体系, 如图4所示。它们链接在一起构成一个增强系统自学习能力的学习环。系统采用了文本挖掘和基于案例推理的技术。

1) 抽取代理 (Extracting Agent) 负责从电子邮件中抽取关键字, 采用词法分析技术, 建立控制词表和词组数据库;

2) 合并代理 (Merging Agent) 负责将从电子邮件中抽取的关键字合并成关键字队列;

3) 统计代理 (Statistics Agent) 根据从Merging Agent获得的关键字列表, 建立一个关键字的使用频率表;

4) 文字挖掘代理 (Word Mining Agent) 根据关键字使用频率在一个语义空间中挖掘单词或术语之间的关系, 推断一个新的分类体系;

5) CBR代理 (CBR Agent) 基于案例库中旧的分类体系, 进行归纳推理, 构成新的分类体系, 并提交给用户;

6) 人机交互代理 ( Human-Machine Interface Agent) 建立人机交互, 由用户确定产生一个新的分类体系;

7) CBR存储代理 (CBR Storing Agent) 负责存储新的分类体系模式, 并保存到案例库中。

3 文本分类算法

在MEDTS系统中, 文本分类算法是关键技术。本系统建立训练学习机制, 构建分类体系的每个目录项的特征向量, 通过词法分析与特征提取, 构建电子邮件的特征向量, 再采用文本相似度计算, 以此判定电子邮件的分类目录项。

定义1:电子邮件的特征向量为w

其中, wn为词表中第n个词的权重;n为词表中词组的总数量。

定义2:wi权重为p

其中, P为第i个词在邮件中出现的次数;W为邮件中所包含的词表中所有词的出现次数的总和。

分类体系中每个目录项的特征向量由训练集中所属电子邮件的特征值整合而成, 即对包含的所有电子邮件的特征向量做简单的平均计算而成。

定义3:分类目录项的特征向量为s

其中, wij为词表中第i个词在分类目录项所包含的所有邮件中第j篇邮件的特征向量的权重;m为该分类目录项中所包含邮件的总数量。

本文采用欧式距离为相似度计算算法。

定义4:分类相似度为μ

其中, wi为电子邮件的特征向量的第i个分量值;si为分类目录项的特征向量的第i个分量值。

通过限定一定的阀值, 依据相似度计算结果, 可判定电子邮件是否属于某个特定的分类目录项。本系统选择的阀值为0.7。

4 案例分析

本文研发的MEDTS系统已在一家总部设于香港的电子有限公司运行。该公司主要经营电子元器件, 为客户提供电子元器件的整体解决方案。公司大量的信息和知识来源于员工与供应商之间电子邮件的交流和沟通。传统方式是:每个员工的电子邮件都封闭在其专有的账户内, 员工内部的信息交流也依靠简单的邮件转发实现, 造成了信息冗余;成功的解决方案未能得到及时分享和应用, 已有的邮件转发模式不能有效地管理不断增长的大量电子邮件信息, 不利于企业知识的检索和应用。

MEDTS系统是一个基于WEB模式的应用系统, 可以嵌入传统的电子邮件系统, MEDTS系统的网络拓扑结构如图5所示。它从电子邮件服务器接收邮件并存储到一个单一中心的动态分类体系中。员工通过个人电脑上的浏览器可浏览完整的动态分类体系。通过集中式的信息管理模式, 可以方便地对全公司的电子邮件信息进行检索, 也能有效地支持信息的分享应用。同时, 提供发送电子邮件的功能, 使员工可仅仅使用MEDTS系统执行基于电子邮件的知识工作。

图6给出根据用户角色提供的个人分类目录的界面;图7为输入搜索关键字界面;图8为根据输入的搜索关键字关联的领域形成的搜索结果界面;图9为基于多代理机制的动态分类体系系统界面。

目前, 该公司所有员工可以在MEDTS系统中发送和接收电子邮件, 所有邮件信息被保存在一个中央数据库中, 通过安全授权机制, 可以便捷地浏览所有邮件信息和解决方案知识, 方便实现信息的共享与学习, 有效地支持企业的商业运营工作。

5 结论

动态分类体系正在成为知识管理的有效方法。基于动态分类体系的3种模式为知识工作者提供了良好的信息和知识组织管理工具。MEDTS系统提供了基于电子邮件的知识工作支持, 使知识工作者可以方便地从电子邮件的分类体系逻辑中浏览和学习有用的信息, 构成知识协同工作的基础。今后, 3种动态分类体系模式需要更深入的研究和开发智能功能, 知识审计和知识工作流支持系统也将被深入研发。

摘要：电子邮件已成为许多企业开展商务与办公的重要媒介, 许多信息都保存在电子邮件系统。对大量邮件的管理, 信息分类是一种有效的管理方法, 但传统的人工文本分类方式相对静态且耗时较多。针对非结构化的邮件信息管理, 提出采用动态分类体系, 通过文本挖掘方法, 开发一套基于多智能代理架构的电子邮件自动分类系统, 提升邮件自动分类的效率。

关键词：电子邮件管理,动态分类,智能代理

参考文献

[1]Drucker P F.The age of social transformation[J].The Atlantic Monthly, 1994, 274 (5) :53-80.

[2]Drucker P F.Managing in turbulent times[M].London:Heinemann, 1980.

[3]Fred Nickols.Shift to knowledge work yearbook of knowledge management[M].Butterworth-Heinemann, 2000.

[4]Sheila Corrall.Are we in the knowledge management business[J].Adriad, 18.URL:http://www.ariadne.ac.uk/issue18/knowledge-mgt/ (available:Dec., 1998) .

[5]Yogesh Malhora.Knowledge management for the new world of business[J].Journal for Quality&Participation special issue on Learning and Information Management, 1998, 21 (4) :58-60.

[6]Prusak L.Where did knowledge management[J].IBM Systems Journal, 2001, 40 (4) :1002-1007.

[7]Karl M Wiig.Knowledge Management:Where did it come from and where will It go[J].Expert Systems With Applications, 1997, 13 (1) :1-14.

[8]Sebastiani F.Machine learning in automated text categorization.Technical[R].ACM Computing Surveys, March 2002, 34 (1) :1-47.

[9]Steve Blake.Lecture note on taxonomies masterclass[M].Arkgroup, 2002.

[10]Susan Conway, Char Sligar.Unlocking Knowledge Assets[R].Microsoft Press, 2002.

[11]Scott Spangler, Jeffrey Kreulen.Interactive methods for taxonomy editing and validation[C].The Proceedings of CIKM’02, URL:http://www.almaden.ibm.com/software/km/eClassifier/cikm2002.pdf, 2002.

邮件分类篇4

垃圾邮件存在于互联网中占用大量的传输、存储和运算资源, 造成巨大的资源浪费;对信息安全系统也构成了一定程度的威胁;浪费用户的时间、精力和金钱, 损害了用户的利益。因此正确识别垃圾邮件显得尤其重要。常见的垃圾邮件过滤技术:邮件发送认证技术仅仅保证了合法用户发送邮件;黑白名单技术, 邮件特征过滤技术, 关键字过滤技术仍然具有一定的实用价值, 但是误判率都较高。

贝叶斯算法具有学习功能, 其准确程度能够随着学习次数的增加而不断提高。但传统的贝叶斯分类算法实现过于复杂, 把基于贝叶斯分类算法的垃圾邮件识别过程移植到云计算平台上, 通过Map Reduce编程模型实现, 充分利用云计算平台的高效的数据存储能力和处理能力, 实现对垃圾邮件的智能、高效过滤。

2. Hadoop框架

2.1 HDFS简介

Hadoop分布式文件系统 (HDFS) 适合部署在廉价的机器上应用于大规模数据集上, 具有高容错性, 高吞吐量的特点。HDFS放宽了可移植操作系统接口的要求, 实现以流的形式访问文件系统中的数据, HDFS框架如图1所示。

Name Node维护名字空间, Data Node存储数据块。一个数据块在多个Data Node中有备份;而一个Data Node对于一个块最多只包含一个备份。Data Node定时和Name Node通信, 接受Name Node的指令。Data Node和Name Node建立连接以后, 就会不断地和Name Node保持心跳。Data Node可作为服务器接受来自客户端的访问, 处理数据块读/写请求。Data Node之间还会相互通信, 执行数据块复制任务, 同时, 在客户端做写操作的时候, Data Node需要相互配合, 保证写操作的一致性。

2.2 Map Reduce简介

Map Reduce是一种编程模型, 适用于大规模数据集的并行运算。Map Reduce任务过程被分成两个处理阶段:map阶段和reduce阶段, 每个阶段都以键/值对作为输入和输出, 可选择他们的类型。但reduce阶段的输入类型必须与map阶段的输出类型相匹配。控制作业执行过程的是两类节点:Job Tracker和Task Tracker。Task Tracker运行自己的任务, 并且将运行的进度报告给Job Tracker。Job Tracker负责调度, 记录各个任务的进度情况, 若发现有任务失败的, 在其他的Task Tracker节点上重新调度该任务。一个Map Reduce job (作业) 通常把输入的数据集切分为若干个独立的数据块, 由map任务 (task) 以完全并行的方式处理。框架会对map的输出先进行排序, 然后把结果输入给reduce任务。作业的输入和输出都会被存储在文件系统中, 原理如图2所示。在Hadoop平台上, Map Reduce框架和HDFS是运行在相同节点上的, 即存储节点和计算节点在一起, 降低了网络传输量、网络延迟, 提高了整体的网络带宽利用率。

3. 贝叶斯分类算法在垃圾邮件过滤中的应用

3.1 数据准备

本文使用向量空间模型表示法将文本转换为计算机可识别的特征。可将文本Mail分词后表示为如下向量形式:M= (w1, w2, …wk…wn) M= (w1, w2, …wk…wn) (wkwk为第k个特征项的权值, 本文使用权值函数为TFIDF函数) 。为了提高过滤的准确率和效率, 在将文本表示成向量前, 可采用停用词表、稀有词处理、单词归并、同根词处理等方法去除噪声。

3.2 朴素贝叶斯分类模型

3.3 朴素贝叶斯算法的Map Reduce实现

邮件分类器的设计分为两部分:训练过滤部分和实时过滤部分, 如图3所示。

本文采用两轮Map Reduce的方法, 如图4所示。第一轮Mapper对邮件进行分词和去除噪声。每个map接收一个邮件数据块, 以作为输入键值对, 对每个数据块进行分词, 映射到键值对, 并作为中间结果输出。每个Reduce函数接收具有相同Key值的中间结果, 合并value值, 得到各词条的数量统计, 分别计算各词条的概率, 输出结果为键值对。产生相应分词的计数结果文件。

第二轮Map阶段主要转换格式为:。拆分输入信息Key得到邮件的标识, 并以此做输出的Key, 在系统对Key操作过程结束后, 一条邮件的各个分词便会集中一块, 然后使用第二轮Reduce过程中进行规约操作。Reduce阶段运算相应的结果, 输出格式为, 如果Value值为T则表示是正常邮件, 否则为垃圾邮件。

4. 结果分析

本文所用样本部分来自CCERT (中国教育和科研计算机网紧急响应组) Data Sets of Chinese Emails, 该样本集邮件均只保留了邮件的纯文本部分, 并将邮件头也以文本形式保留。另外包含个人收集的邮件, 包括私人邮件, 各种公司、产品、广告、服务、营销邮件, 及一些论坛上的垃圾邮件等。

实验评价标准:垃圾邮件查准率, 垃圾邮件召回率, 全部邮件判对率。由表1可以看出贝叶斯邮件过滤算法在传统分布式并行计算模型和基于Hadoop的Map Reduce模型上的实现在邮件过滤准确性上的效果相当。

另外, 单机环境的加速比:1.075, 云计算环境的加速比为:1.306。其加速比方面云计算环境有一定的优势。但云计算在编程实现和系统扩展上优势更为明显, 不用考虑线程之间的同步、互斥、并发等问题;且系统扩展仅需增加新的机器, 而传统并行系统扩展则相对麻烦。

5. 总结

经实验验证, 垃圾邮件过滤系统中应用贝叶斯分类算法具有较高的性能与准确率;另外实验还证明了贝叶斯分类算法在云计算环境中的实现相比传统式的实现方式有编程实现简单和系统扩展容易的优势。

摘要：为了抵制垃圾邮件对互联网及其用户造成的严重不良影响, 本文采用高效的贝叶斯分类算法, 基于hadoop平台实现垃圾邮件的过滤系统, 克服了传统并行系统在编程实现和系统扩展上的不足, 充分利用云计算环境优势, 使系统实现简单, 扩展容易, 性能提高;并做了相关的试验, 验证了设计理论。

关键词：垃圾邮件,云计算,贝叶斯分类,MapReduce,HDFS

参考文献

[1]Jiawei Han.Micheline Kamber.数据挖掘概念与技术[M].北京:机械工业出版社, 2006.

[2]Tom Wbite.Hadoop权威指南[M].北京:清华大学出版社, 2011.

[3]朱杰.基于云计算及贝叶斯算法的垃圾短信过滤技术研究与实现[D].电子科技大学, 2010.

[4]曾青华.面向海量邮件过滤的云计算技术研究[D].南京航空航天大学, 2012.

[5]杨际祥.并行与分布计算负载均衡问题研究[D].大连理工大学, 2012.