资源描述：
《云计算 分布式 反垃圾邮件 系统》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、《现代图书情报技术》2007年第4期应用实践总第149期3改进KNN算法在垃圾邮件过滤中的应用张俊丽张帆(华中师范大学信息管理系武汉430079)【摘要】提出一种改进的KNN算法,并将其用于垃圾邮件的过滤问题。经实验证明,改进的算法能够降低K值和训练文本的分布对过滤效果的影响,减少垃圾邮件的误判和漏判,具有较好的过滤性能。【关键词】KNN垃圾邮件过滤文本分类【分类号】TP391ApplicationofImprovedKNNAlgorithminSpamE2mailFilteringZhangJunliZhangFan(Department
2、ofInformationManagement,HuazhongNormalUniversity,Wuhan430079,China)【Abstract】Inthispaper,animprovedK-NearestNeighbor(KNN)isproposedandisappliedtofilterspamemail.It’sprovedthattheimprovedalgorithmislesssensitivetotheparameterKandthedistributionofthetrainingset,helpsreducing
3、themisclassification,andperformanceswellinexperiments.【Keywords】KNNAnti-spamemailTextclassification[6]提出。应用于邮件过滤中就是将训练文本分为两类,1引言一类为合法邮件,一类为非法邮件,在训练文本集合中,目前,常用的垃圾邮件过滤算法主要有三类:黑白名待测文本找出与其最相似的K个文本,然后将其中的多单过滤法、基于规则的方法和基于统计的方法。其中,黑数文本所属的类别赋给待测文本,从而判断出待测邮件白名单法是将黑名单地址发出的邮件进行拦阻和过滤,
4、是否合法。在经典KNN算法中,K值的选择对分类的结白名单地址发出的邮件判为合法,但在实际应用中,动态果影响很大,如果K值过大,则将会使结果偏向于文本数[1]变化的邮件地址会导致这种方法失效;基于规则的过较多的一类,如果K值过小(如K=1),则会降低过滤效滤方法是通过训练得到显式规则,再利用规则来进行过果。本文提出对KNN算法进行改进,降低K值和训练文滤,如Ripper、Decisiontree、Boosting等方法,此类算法的本的分布对结果的影响,实验证明,改进后的算法能够提过滤正确率和召回率都在80%以上,其缺点是在规律性高邮件过滤系统
5、的稳定性。[2]不明显的邮件中过滤效果比较差;因此更多学者倾向2系统设计于基于统计算法的研究。KNN(K-NearestNeighbor)是一种简单的基于统计的过滤算法,JoachimsT和LiBaoli邮件过滤系统的框架如图1所示。指出KNN算法是一种很好的分类算法,在不同的数据集[3,4]上进行实验,都取得了很好的分类效果。Androutso2poulosI等人将KNN应用于邮件过滤中,并与Bayesian及基于关键词的过滤算法进行比较,发现前两者过滤效果[5]相当,而基于关键词的过滤算法效果较差,因此,对KNN算法进行改进并运用到邮件
6、过滤系统中是很有研究价值的。图1邮件过滤系统框架图经典KNN是一种简单的分类算法,由Cover和Hart首先,将训练文本分为合法邮件和垃圾邮件,进行预收稿日期:2007-03-05处理,并提取特征词,将处理结果存入训练集数据库;待收修改稿日期:2007-03-22测文本经过特征提取后,与训练集数据库中的全部训练3本文系2006年国家社科基金项目“网络信息过滤研究”(项目编号:06BTQ024)的研究成果之一。文本进行相似度计算,利用KNN分类器,将待测文本进·75·《现代图书情报技术》2007年第4期应用实践总第149期行分类。若待测文本被
7、判为合法邮件,则系统输出该邮(2)依次计算新文本属于每类的权重,根据文献[6],计件,否则,系统予以过滤。算公式如下:P(x,cj)=∑Sim(x,xi)y(xi,cj)(4)xi∈KNN3文本预处理其中,x为新文本的特征向量,y(xi,cj)为类别属性函数,如果文3.1文本表示本xi属于类cj,那么函数值为1,否则为0。(3)比较权重值,将新文本划分到权重最大的那个类别用向量空间模型表示文本,即文本表示为(x1,x2,K中。xn),特征词表示为(t1,t2,Ktn),特征词的权重表示为(w1,w2,Kwn)。然后排除停用词,合并数字和人名
8、等词5改进的KNN算法[7]汇,并统计词频,本文采用常见的TF-IDF公式统计词5.1算法描述频。在经典KNN算法中,一般先设定一个初始K值,然tf(t,x)×log(N/nt+
