基于邮件社区的垃圾邮件发现方法

张中军,张少辉,曹 彦

(周口师范学院计算机科学系,河南周口466001)

对大多数用户来说,E-mail是他们最经常使用的网络服务之一,然而,垃圾邮件泛滥已成为一个亟待解决的问题。根据Comm Touch公司的统计数据,垃圾邮件数量占电子邮件总数的60%以上。除发送药品广告外,更多的垃圾邮件被用来传播恶意件,窃取用户账户、密码等个人信息;另外一种上升的攻击活动是鱼叉式网络钓鱼,向特定人群或机构发送电子邮件,获取对方的机密信息。这都给电子邮件服务提供商以及用户造成了非常大的困扰与经济损失。因此,垃圾邮件处理方法的研究对于保护个人及机构机密信息、净化通信环境有十分重要的意义。

目前已出现很多垃圾邮件处理技术,基于聚类的有偏斜分布下基于聚类的过滤方法[1],将邮件划分成若干社区,从每个社区提取相同数量的关键词,避免了偏斜分布的影响。基于垃圾邮件行为启发式学习方法[2]中根据经验式学习方法,将垃圾邮件根据URL等特征划分成社区。文献[3]将邮件根据IP进行聚类,根据垃圾邮件的IP进行信誉评估。文献[4]中将邮件根据足球、天气等不同的主题进行划分社区,根据新邮件与每个社区的主题相似度来识别垃圾邮件。上述方法中都是根据邮件内容或一定主题将邮件分组,然后根据这些分组判断新邮件是否垃圾邮件。但是,现实中很难判断有多少主题,对每个邮件都提取关键词不但增加了服务器负担,还用到邮件内容,涉及到正常用户的隐私。本文提出一种基于邮件社区的垃圾邮件发现方法,将不考虑邮件内容主题,直接使用之前存在的社区划分方法,将邮件地址根据它们之间的联系紧密度划分为若干社区,根据现有的邮件系统收集的垃圾邮件,抽取垃圾邮件内容的关键词。然后对新邮件,根据一定的规则,给出是否垃圾邮件的判断,与邮件一起发送给目标用户。

1 基于邮件社区的垃圾邮件发现方法

1.1 邮件社区的划分

本文使用带调整策略的微聚类-宏聚类邮件社区划分算法[5]来划分邮件社区。在整体上考虑邮箱个体之间的所有联系,从分析用户关系紧密程度入手,采用带调整策略的微聚类-宏聚类技术来发现邮件通信网络中紧密联系的团体。主要通过三个过程实现:第一,使用k-medoids算法将所有邮箱个体聚类为大量相对较小的子簇,实现微聚类。第二,利用凝聚层次聚类的思想实现宏聚类,策略是反复合并子簇成为较大的簇,直到满足某个终止条件。本文将最终希望得到的簇数目作为终止条件。第三,针对个别边缘节点进行调整划分。具体算法描述如下:

输入:邮箱及邮箱个体对之间的邮件通信特征信息。

输出:社区划分结果。

方法:

1)用户输入微聚类子簇的数目k;

2 )选取k个节点作为初始子簇中心点;

3 )repeat;

4 )指派每个剩余对象给离它最近的中心点所代表的簇;

5 )随机地选择一个非中心点对象o random;

6 )计算用orandom取代原中心点的总代价S;

7 )if S<0,then orandom替换oi,形成新的k个中心点的集合;

8 )until所有的子簇中心点均不发生变化;

9 )w hile(不满足终止条件);

10)fo r每个子簇ci;

11)for每个剩余子簇cj;

12)寻找使紧密度取得最大值的ci,cj;

13)将ci与cj合并成较大的簇;

14)fo r邮件网络中每个簇 Ci;

15)for每个节点 p∈Ci;//寻找需要调整的节点;

16)计算 p与簇Ci中除p以外的剩余节点组成的簇的紧密度;

17)for邮件网络中每个剩余簇Cj;

18)计算 p与簇C的紧密度;

19)if p与其他簇C获得更大的紧密度;

20)将 p调整划分到簇Cj;

21)else p不做任何变动;

22)结合映射表输出社区划分结果。

1.2 抽取垃圾邮件特征

利用文本挖掘的从原有邮件服务器获得垃圾邮件的相关特征,即对所有垃圾邮件进行分析,从中提取关键词。这些关键词就代表了垃圾邮件主要内容,反应了垃圾邮件特征。

1 )将电子邮件数据集的所有垃圾邮件合为一个大的邮件文档,去除邮件标题,只取邮件内容部分。这些邮件文档中的每封邮件以类标号开始,用两个标记分别表示每封邮件正文的开始和结束。

2 )把垃圾邮件文档中每一封邮件正文中的重复词去掉,正文中重复词仅保留一个。

3 )对邮件正文进行特征提取:统计每个词在垃圾邮件中存在的频率,将垃圾邮件特征表示为一个多维向量。

1.3 垃圾邮件发现机制

垃圾邮件发现就是在一封新邮件出现时,邮件服务器根据某种机制判断该邮件是否垃圾邮件,并根据判断采取相应的处理措施。本文提出的方法基于以下调查研究结果:首先,邮件地址反应人类的社交行为,呈现社区特征;其次,按上述社区划分方法得到的社区,其内部成员之间联系紧密;最后,大多数的邮件通信来自社区内部。根据上面这些研究,在不考虑邮件地址被盗用的情况下,可以认为社区内部成员之间的邮件通信是正常的。那么本文提出的垃圾邮件发现过程可描述如下:

1 )邮件服务器接收到一封电子邮件后,提取邮件发送者与接收者的邮件地址。

2 )邮件服务器查询发送者与接收者的邮件地址分别所属的社区标号。

3 )如果发送者与接收者的邮件地址所属社区标号相同,将邮件直接发送给接收者;否则,继续下一步。

4 )对新邮件提取邮件关键词,建立特征向量,计算与垃圾邮件特征向量的相似度。如果不高于某个阈值,直接将邮件发送给接收者;否则,标记为垃圾邮件,并将邮件连同标记一起发送给接收者。

5 )接收者根据邮件的标记及实际内容判断是否垃圾邮件。用户阅览邮件内容后,如果认为该邮件标记错误,则向邮件服务器发送反馈报告,不发送报告则认为是正常邮件。

6 )根据接收者的反馈信息,对该邮件重新标记,是垃圾邮件则重新提取关键词;非垃圾邮件则将发送方邮件地址以及通信特征保存,等到该邮件地址与某个社区的联系紧密度超过该社区内部各成员之间的平均联系紧密度时,将该邮件地址划分到该社区。

根据上面的描述,本文提出的垃圾邮件发现模型如图1所示。

图1 垃圾邮件发现模型

从图1可以看出,当一个新的邮件到达邮件服务器时,不是直接对其进行内容分析,而是先判断该邮件的发送者邮箱地址与接收者邮箱地址是否属于同一个社区。如果来自同一个社区,那么该邮件可以看作是社区内部成员之间的正常邮件。当然,这里暂时不考虑邮箱被盗用的情况。只有发送者邮箱地址与接收者邮箱地址不属于同一个社区时,才将该邮件与垃圾邮件特征比较,以获得该邮件与垃圾邮件的近似度,并根据近似度值的大小给出是否垃圾邮件的判断。并且最后还采用了用户反馈机制,用以接收用户阅读邮件内容后对邮件客观的判断,并根据反馈信息及时更新社区或垃圾邮件特征。从某种程度上来说,这也是该垃圾邮件发现方法的一种学习机制。

2 算法分析与总结

本方法充分考虑了邮件通信网络中社区结构的客观存在性,详细分析了性质,并在此基础上提出了一种垃圾邮件发现方法。这种方法与已经存在的基于邮件内容的垃圾邮件发现方法相比,准确率远远不及后者。之所以依然提出这种思想,主要是考虑到随着社会的发展,个人隐私越来越受到社会的广泛关注,那么基于邮件正文内容的垃圾邮件过滤方法在某种意义上来说,已经触及了用户的隐私。也是出于这种考虑,诸多学者开始探索新的垃圾邮件发现方法,以绕开基于内容的文本分类。受此启发,提出了这种基于邮件社区的垃圾邮件发现方法。

在本文提出的方法中,首先是对邮件服务器下的所有邮件地址进行社区划分,此过程完全脱离邮件正文内容,而是用邮件地址之间的联系紧密度作为划分标准。这样不但在某种角度上保护了用户隐私,还能更如实的反映出邮件通信网络中的社区特征。但是,当邮件地址规模较大时该划分过程比较耗时,所以应定期对邮件地址进行重新划分,不宜频繁进行。其次,本方法不用对所有邮件进行内容抽取,只对社区外部到来的邮件进行。因为邮件通信多来自社区内部,所以大部分的邮件不必抽取内容。最后,因为该方法没有严格的标准定义垃圾邮件,所以单独使用该方法可能效果不是太好,所以目前可作为原有垃圾邮件处理引擎的补充方法。结合原有方法共同使用,在某种程度上可提高垃圾邮件处理的准确度,具体效果有待进一步实验验证。

3 下一步工作展望

下一步工作的重点是进一步完善改进该垃圾邮件发现方法,并以实际数据集实验验证该方法的有效性。在此基础上,进行该思想的实际应用研究,找到与现有垃圾邮件处理引擎的结合点,以进一步提高垃圾邮件处理的准确度。

[1]Hsiao Wen-Feng,Chang Te-M ing,Hu Guo-Hsin.A Cluster-based App roach to Filtering Spam under Skewed Class Distributions[C]//Proc of the 40th Hawaii International Conference on System Sciences, 2007:53-60.

[2]Li Fulu,Hsieh Mo-Han.An Empirical Study of Clustering Behavio r of Spammers and Group-based Anti-Spam Strategies[C]//Third Conference on Email and Anti-Spam,2006:27-28.

[3]张洪,段海新,吴建平.基于IP地址聚类的反垃圾邮件信誉系统[J].清华大学学报,2010,50(10):1723-1727.

[4]包理群,李祥林.改进的 K-均值聚类邮件过滤算法[J].兰州工业高等专科学校学报,2010,17(2):5-9.

[5]张中军,郭华平,范明.带调整策略的微聚类-宏聚类邮件社区划分算法[J].小型微型计算机系统,2010,31 (10):1970-1974.