• 1. 基于生物序列模式提取技术的 邮件过滤算法陈蔚然 董守斌 华南理工大学信息网络工程研究中心 广东省计算机网络重点实验室 2005-9 全国搜索引擎与网上信息学术研讨会 SEWM 2005
  • 2. 目录算法原理 实现机制 实验及结果分析 总结
  • 3. 垃圾邮件给全球的生产力造成严重损失。垃圾邮件的智能分析、自动过滤成为了研究的热点。过滤垃圾邮件可以采用文本分类技术,常用的算法有贝叶斯分类算法、SVM分类算法和k-NN算法等[1]。 背景
  • 4. 网络信息与生物信息的一个共同特征就是具有海量数据,其中垃圾邮件还具有内容重复的特点。用于搜索生物序列相似性的模式提取算法可以从输入序列中找出重复出现的模式,所以可将这类算法应用于提取垃圾邮件的特征模式,从而对邮件进行分类并过滤。 2004年,IBM T. J. Watson研究中心提出Chung-Kwei邮件过滤系统[2],但目前还没有针对中文垃圾邮件应用情况的报道。 背景
  • 5. 生物序列模式提取算法,主要用于解决基因发现和蛋白质注释等计算生物学领域的问题[3]。其中,TEIRESIAS算法的计算速度快,能够处理大量的输入序列,因此被广泛应用于生命科学和计算机安全等领域。 TEIRESIAS算法:对于一组输入序列 S= {s1,s2 , …, sn },设定参数L、W、K,找出所有最大的模式(L≤W),并保证在输入序列中至少出现过K次(至少在S中K个不同的序列中出现)。模式是指该模式的任何子模式如果长度大于等于W,那么至少应该含有L个字符[4]。TEIRESIAS算法
  • 6. 过滤算法BioMatrix的主要原理1) 基于TEIRESIAS算法提取垃圾邮件的模式,形成垃圾邮件模式库。 2) 通过学习正常邮件,系统将同时出现在正常邮件中的模式从垃圾邮件模式库中剔除,提高模式库的精确度,降低误过滤率。但在实际应用中,获得正常邮件的数量毕竟有限,可结合邮件边缘信息(如邮件头信息,白名单)减少误过滤。 3) 将邮件和模式库中模式进行匹配,把模式出现次数作为该模式的权值,并结合考虑模式对邮件内容的覆盖程度,对邮件进行分类。
  • 7. ωi:模式Pi在垃圾邮件训练集中出现的次数 LN: 该邮件文本的长度 |Pi|:模式Pi 的长度 TN :包含模式的数量阈值 TL :对邮件长度覆盖率阈值分类决策
  • 8. 把待分类邮件m与模式库 中的所有模式比对,找出包含于m中的所有模式Pi,计算: (1) (2) 如果( 同时满足(1)(2)式 ) ,则判为垃圾邮件,否则判为正常邮件 分类决策N
  • 9. (1)式采用模式在训练集中出现的次数作为该模式的权值,ωi越大,对判断结果的贡献越多; (2)式可以检测垃圾邮件模式对邮件内容覆盖的程度,覆盖程度越大,是垃圾邮件的可能就越大。 TN和TL的取值可以通过实验调整,综合考虑过滤率和误过滤率情况。分类决策
  • 10. 模式提取实现机制 基于邻接矩阵的拼接方法 TEIRESIAS算法把序列中的单个字符拼接成出现过K次以上的短模式。设字符的取值集合为,试探性的把中每个字符连接在字符β的末尾,以获得新的模式β’。 (3) 避免采用上述穷举式拼接法。引入了邻接矩阵M,记录每两个连续字符的邻接关系。M[i][j] 表示中文序列中取值为i的字符连接取值为j的字符的次数。算法的拼接方法可由(3)式改为(4)式: (4) 有效地减少了字符β后面接续的的数目,减少运算时间,显著提高系统效率。
  • 11. 最短模式长度限制 中英文序列,分别采用不同的参数L作为最短模式长度的限制(即所有模式的长度大于等于L个字符)。 汉字和英文字符特点不同,两个以上的连续汉字所表达的意思一般已经可以体现垃圾邮件的特点。英文序列L过小时提取出的很多英文模式会没有意义,如单词后缀、前缀。 对于中文序列,参数L可以取值较小。英文序列适合采用较大的参数L。 英文模式中文模式tion群发软件ment破解软件less增值税电脑发票
  • 12. 正常邮件被过滤的垃圾邮件学习新垃圾邮件 动态更新模式库垃圾邮件训练集正常邮件训练集文本预处理模式匹配 数量控制过滤 垃圾邮件 邮件 提 取 模 式 垃圾邮件 模式库图1. 过滤系统结构过滤系统结构
  • 13. 实验及结果分析 采用华南理工大学邮件服务器2004/9/20日,由数量控制过滤出的6859封垃圾邮件作为训练集,提取垃圾邮件模式;用另外收集到的2132封正常邮件,去除垃圾邮件和正常邮件中共有的模式。 对该邮件服务器2004/9/22日过滤出的6752封垃圾邮件和另外收集到的2512封正常邮件进行过滤 邮件平均大小4.17KB。 过滤率=被正确判别的垃圾邮件数目 / 垃圾邮件总数 误过滤率=被判为垃圾邮件的正常邮件数目 / 正常邮件总数
  • 14. 模式出现最少次数K对过滤效果的影响K为2时,过滤率99%,误过滤率较高,不适合实际应用。 K取值为3时,模式数量17211,过滤率为94.2%,误过滤率0.04%。 随着K取值继续增大,提取的模式数量减少,过滤率和误过滤率也都随着下降。 综合考虑过滤效果和误过滤情况,可以把K=3作为最佳取值。86%88%90%92%94%96%98%100%0246810 模式出现的最少次数K 过滤率图2. L=4,K对过滤效果的影响
  • 15. 最短模式长度L对过滤效果的影响 当L增大,提取出的模式较长,包含的信息相对较多,误过滤的可能就越小。 L减小,提取出更多的短模式,模式总数增加。但短模式中包含的信息不足,误过滤可能会增大。 经实验测试,对于中文序列,L=4,K=3时,可以获得较好的过滤效果,过滤率94.2%,误过滤率为0.04%,
  • 16. 与Naïve Bayes算法过滤器的比较 采用相同数据集,对BioMatrix算法和Naïve Bayes算法的过滤效果和效率进行了测试比较。测试服务器安装Fedora操作系统,配备P4 2.4G CPU和512M内存。
  • 17. 与Naïve Bayes算法过滤器的比较 过滤率误过滤率过滤速度/ message·sec-1Bayes92.0%0.12%147BioMatrix94.2%0.04%182BioMatrix算法过滤系统具有更好的过滤效果,误过滤率降低,能识别出更多的垃圾邮件。 采用Bayes等算法过滤邮件时,通常需要对中文序列做分词处理,会降低过滤速度。我们针对中文环境,对BioMatrix算法进行了优化,避开中文分词问题,提升了系统效率,因此具有更高的过滤速度。
  • 18. 总结本文基于生物信息模式提取技术,设计了BioMatrix过滤算法,将其应用于垃圾邮件过滤系统,并在中文环境下对实现过程进行优化。 系统通过获取垃圾邮件中重复出现的模式,对邮件进行分类。与Naïve Bayes过滤器相比,此系统过滤准确性更高。实验结果表明将生物信息技术应用于邮件过滤具有一定的研究和实用价值。
  • 19. 参考文献 Fabrizio Sebastiani. Machine Learning in Automated Text Categorization [J]. ACM Computing Surveys, 2002, 34: 1–47. Isidore Rigoutsos, Tien Huynh. Chung-Kwei: a Pattern-discovery-based System for the Automatic Identification of Unsolicited E-mail Messages [OL]. http:// www.research.ibm.com/spam/papers/. 2004 Isidore Rigoutsos, Aris Floratos. Combinatorial pattern discovery in biological sequences: the TEIRESIAS algorithm [J]. Bioinformatics, 1998, 14: 55-67. Aris Floratos, Isidore Rigoutsos. The Time Complexity of the TEIRESIAS Algorithm [OL]. http://domino.watson.ibm.com/library. 1998 Sandra Romero Hidalgo, Gina Holguin, Cheryl Patten, et al. Finding Patterns in Biological Sequences [OL]. http://genetics.uwaterloo.ca/tvinar/cs798g/motif. 2000 林珊,宁国宁,赵之霖. 中文分词在邮件过滤系统中的应用[J], 华南理工大学学报(自然科学版),2004, 32:112-116
  • 20. 欢迎提出宝贵意见!