提出一种改进的KNN算法 ,并将其用于垃圾邮件的过滤问题。经实验证明 ,改进的算法能够降低K值和训练文本的分布对过滤效果的影响 ,减少垃圾邮件的误判和漏判 ,具有较好的过滤性能

《现代图书情报技术》　2007年　第4期

应用实践

　　总第149

期

改进KNN算法在垃圾邮件过滤中的应用

张俊丽　张　帆

(华中师范大学信息管理系　武汉430079)

3

　　【摘要】　提出一种改进的KNN算法,并将其用于垃圾邮件的过滤问题。经实验证明,改进的算法能够降低K值和训练文本的分布对过滤效果的影响,减少垃圾邮件的误判和漏判,具有较好的过滤性能。　　【关键词】　KNN　垃圾邮件过滤　文本分类　　　　【分类号】　TP391

ApplicationofImprovedKNNAlgorithminSpamE2mailFiltering

ZhangJunli　ZhangFan

(DepartmentofInformationManagement,HuazhongNChina)

　　【Abstract】　Inthispaper,animprovedK-)andisappliedtofilterspam

email.It’sprovedthattheimprissensitiveKandthedistributionofthetrainingset,helpswellinexperiments.

　　【K-spa　Textclassification

1　引　言

　　目前,常用的垃圾邮件过滤算法主要有三类:黑白名单过滤法、基于规则的方法和基于统计的方法。其中,黑白名单法是将黑名单地址发出的邮件进行拦阻和过滤,白名单地址发出的邮件判为合法,但在实际应用中,动态变化的邮件地址会导致这种方法失效

[1]

提出

[6]

。应用于邮件过滤中就是将训练文本分为两类,

一类为合法邮件,一类为非法邮件,在训练文本集合中,待测文本找出与其最相似的K个文本,然后将其中的多数文本所属的类别赋给待测文本,从而判断出待测邮件是否合法。在经典KNN算法中,K值的选择对分类的结果影响很大,如果K值过大,则将会使结果偏向于文本数较多的一类,如果K值过小(如K=1),则会降低过滤效果。本文提出对KNN算法进行改进,降低K值和训练文本的分布对结果的影响,实验证明,改进后的算法能够提高邮件过滤系统的稳定性。

;基于规则的过

滤方法是通过训练得到显式规则,再利用规则来进行过滤,如Ripper、Decisiontree、Boosting等方法,此类算法的过滤正确率和召回率都在80%以上,其缺点是在规律性不明显的邮件中过滤效果比较差

[2]

;因此更多学者倾向

于基于统计算法的研究。KNN(K-NearestNeighbor)是一种简单的基于统计的过滤算法,JoachimsT和LiBaoli指出KNN算法是一种很好的分类算法,在不同的数据集上进行实验,都取得了很好的分类效果

[3,4]

2　系统设计

　　邮件过滤系统的框架如图1

所示。

。Androutso2

poulosI等人将KNN应用于邮件过滤中,并与Bayesian及

基于关键词的过滤算法进行比较,发现前两者过滤效果相当,而基于关键词的过滤算法效果较差价值的。

　　经典KNN是一种简单的分类算法,由Cover和Hart

　　收稿日期:2007-03-05　　收修改稿日期:2007-03-22

(项目　　3本文系2006年国家社科基金项目“网络信息过滤研究”

编号:06BTQ024)的研究成果之一。

[5]

,因此,对

KNN算法进行改进并运用到邮件过滤系统中是很有研究

图1　邮件过滤系统框架图

　　首先,将训练文本分为合法邮件和垃圾邮件,进行预处理,并提取特征词,将处理结果存入训练集数据库;待测文本经过特征提取后,与训练集数据库中的全部训练文本进行相似度计算,利用KNN分类器,将待测文本进

75