当前位置:首页 >> >> 云计算 分布式 反垃圾邮件 系统

云计算 分布式 反垃圾邮件 系统


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

应用实践

   总第 149 期

改进 KNN 算法在垃圾邮件过滤中的应用
张俊丽   张  帆
(华中师范大学信息管理系   武汉 430079 )

3

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

Applica tion of I m proved KNN A lgor ithm in Spam E 2 ma il F ilter in g
Zhang Jun li Zhang Fan
( D epa rtm en t of Infor m a tion M anagem en t, Huazhong N or m a l U n iversity, W uhan 430079, Ch ina )
   【Abstract】   In this paper, an imp roved K - Nearest Neighbor ( KNN ) is p roposed and is app lied to filter spam
email . It’ s p roved that the imp roved algorithm is less sensitive to the parameter K and the distribution of the training set, help s reducing the m isclassification, and performances well in experim ents .

   【 Keywords】  KNN  Anti - spam email Text classification

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

提出

[6 ]

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

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

; 基于规则的过

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

; 因此更多学者倾向

于基于统计算法的研究 。 KNN ( K - Nearest Neighbor) 是 一种简单的基于统计的过滤算法 , Joachim s T 和 L i Baoli 指出 KNN 算法是一种很好的分类算法 , 在不同的数据集 上进行实验 , 都取得了很好的分类效果
[ 3, 4 ]

2  系统设计
   邮件过滤系统的框架如图 1 所示 。

。 Androutso2

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

基于关键词的过滤算法进行比较 , 发现前两者过滤效果 相当 , 而基于关键词的过滤算法效果较差 价值的 。    经典 KNN 是一种简单的分类算法 , 由 Cover和 Hart
   收稿日期 : 2007 - 03 - 05    收修改稿日期 : 2007 - 03 - 22 (项目   3 本文系 2006 年国家社科基金项目“ 网络信息过滤研究 ” 编号 : 06BTQ024) 的研究成果之一 。
[5]

, 因此 , 对

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

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

?75?

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

应用实践

   总第 149 期

行分类 。若待测文本被判为合法邮件 , 则系统输出该邮 件 , 否则 ,系统予以过滤 。

   ( 2 ) 依次计算新文本属于每类的权重 ,根据文献 [ 6 ] ,计 算公式如下 :
P ( x, c j ) =
x i∈K NN

3  文本预处理 3. 1   文本表示
   用向量空间模型表示文本 , 即文本表示为 ( x1 , x2 , K
xn ) ,特征词表示为 ( t1 , t2 , K tn ) , 特征词的权重表示为 ( w1 , w2 , K wn ) 。然后排除停用词 , 合并数字和人名等词

∑ Sim ( x, xi ) y ( xi , c j )

( 4)

   其中 , x为新文本的特征向量 , y ( xi , c j ) 为类别属性函数 , 如果文 本 xi 属于类 c j ,那么函数值为 1,否则为 0。

   ( 3 ) 比较权重值 ,将新文本划分到权重最大的那个类别 中。

5  改进的 KNN 算法 5. 1   算法描述
   在经典 KNN 算法中 , 一般先设定一个初始 K 值 , 然 后根据实验测试的结果调整 K的大小 , 然而 , 在电子邮件 过滤系统中 , K值不能自动调整 ,而且 K取值不当或训练 文本分布不均会降低过滤性能 , 影响过滤效果 。因此 , 笔 者对 KNN 的权重算法进行改进 , 使其能适应动态变化的 电子邮件过滤系统 。改进的 KNN 算法如下 :
   (1)利用特征项集合描述训练文本向量 。    ( 2 )用向量表示待测文本 , 删除停用词汇 、 数字和其它字 符 (如 * &等 ) ,利用公式 (1)计算词频 。    ( 3 )利用公式 ( 2 )提取能表现文本特征的关键词 。    (4)利用公式 (3) ,在训练文本集中选出与待测文本最相 似的 K个文本 。    (5)依次计算新文本属于每类的权重平均值 , 计算公式 如下 :
∑ Sim ( x, xi ) y ( xi , c1 )
k1
x i∈K NN

汇 ,并统计词频 ,本文采用常见的 TF - I D F 公式统计词 频。
W ( t, x) = tf ( t, x) ×log(N / n t + 0. 01)

[7 ]



t∈x

[ tf ( t, x) ×log (N / n t + 0. 01) ] 2

( 1)

   其中 ,W ( t, x) 为词 t在文本 x中的权重 , tf ( t, x) 为词 t在文本 x中 的词频 , N 为训练文本的总数 , n t 为文本集中出现 t的文本数 。

3. 2   特征提取
   对词进行特征项选择 ,可以降低向量空间的维数 , 提 高程序运行效率 。考虑到垃圾邮件所出现的词特征突出
(如“ 赚钱 ” 、 “ 成人 ” 等 ) , 过滤时只需考虑这些特征词即

可 , 故在电子邮件过滤系统中 , 采用互信息进行特征提取 效果比较好
[8 ]

。互信息描述的是特征词 t与类别 c 之间

的关联程度 。互信息量越大 , 名词和类别同时出现的概 率就越大 , 因此应该选择互信息大的词作为特征词 。其 计算公式
[9]

如下 :
2

P ( tk , c j ) M I( tk ) = ∑ P ( c j ) log   ( j = 1, 2) j=1 P ( tk ) P ( c j )

( 2) P ( x, c1 ) =

x i∈K NN

( 5)

   其中 P ( tk ) 为训练集中特征词 tk 出现的概率 , P ( c j ) 表示训练集 中 c j 类文本出现的概率 , P ( tk , c j ) 表示特征词 kk 出现在 c j 类中的概 率 ,设 c1 为合法邮件 , c2 为垃圾邮件 。

∑ Sim ( x, xi ) y ( xi , c2 )
k2 ( 6)

P ( x, c2 ) =

3. 3   相似度计算
   在 KNN 算法中 , 相似度的选择也很重要 , 算法的关 键就在于找出与其最相似的 K 个文本 , 本文利用夹角余 弦
[ 10 ]

   其中 k1 为 K个文档中属于 c1 类的文本数 , k2 为 K个文档中属 于 c2 类的文本数 , K = k1 + k2 , P ( x, c1 ) 为文本 x属于 c1 类的权重平 均值 , P ( x, c2 ) 为文本 x属于 c2 类的权重平均值 , 此算法与向量空间 距离分类法有所相似但不相同 ,后者是利用算术平均为每类文本生成 一个代表该类的中心向量 , 然后计算待测文本与类中心向量间的距
k =1 m

计算相似度 。
Sim ( xi , xj ) =

∑w ik × w jk
m k =1

m

离 ,最后判定新文本属于与其距离最小 (最相似 ) 的类 。笔者提出的
) ( 3)

2 ( ∑ w2 ik ) ( ∑ w jk ) k =1

算法是与待测文本最相似的 K篇文本在每个类中的平均相似度 ,即删 去了一些相似度很低的文本对分类的影响 ,这样可避免训练集中属于 类 c1 或 c2 文本过多 , 而造成前 K个文本更靠近某一类的倾向 , 使结 果更客观 。

   其中 , m 为特征向量的维数 k, w ik表示第 i个文本的第 k 个特征项 的权重值 。

4  经典 KNN 算法
   该算法的基本思路是 : 在训练文本集中找出与待测 文本距离最近 (最相似 ) 的 K 个文本 , 然后计算新文本属 于每类的权重 ,最后将其分到权重最大的一类中 , 算法如 下:
   (1) 在训练文本集中选出与待测文本最相似的 K 个文 本。

   (6)比较权重均值 ,将文本划分到值最大的那个类别中 。

5. 2   改进 KNN 算法的主要流程
   ( 1 )找出待测文本的 k个近邻文本 ,并存入集合 E中
     初始化 : 输入训练文本集 X = { x1 , x2 , K, xn } , 选择常数 k, 输 入待测文本 x,初始化集合 E,令 i = 1。   Do until ( i≤n)     计算待测文本与训练文本的相似度 Sim ( x, xi )    If  i≤k

?76?

《 现代图书情报技术 》  2007 年   第 4期
   Then将 xi 放入集合 E

应用实践
7  实  验

   总第 149 期

  Else if ( Sim ( x, xi ) 小于集合 E 中某训练文本与待测文本的距 离)    Then删去集合 E 中训练文本与待测文本距离最大的文 本 ,将 xi 放入集合 E   End If    i = i + 1   End Do Until    ( 2 )对待测文本进行分类

   本实验的测试语料来源于 L ing - Spam

[ 14 ]

, 它是由希

腊学者 Androutsopoulos 等人提供 , 由提供者收到的垃圾 邮件和来自于语言学家邮件列表 ( L inguist L ist) 的合法邮 件构成 ,其公用的合法邮件没有加密 。语料中含合法邮 件 2 412 篇 ,垃圾邮件 481 篇 , 为了验证训练文本集集的 分布对过滤性能的影响 , 本文选取合法邮件 50 篇 , 垃圾 邮件 480 篇 ,取其中 4 /5 作为训练集 , 1 /5 为测试集 , 改变
K值进行实验 ,并计算其平均值 , 实验中 μ = 9, 实验结果

    For i = 1 to K     计算 P ( x, c1 )和 P ( x, c2 )    End For     If P ( x, c1 ) > P ( x, c2 )      则 x属于 c1 类    Else x属于 c2 类    End If

如表 2 所示 。    表 2  实验结果
经典 KNN
K值 正确率召回率 (%) 5 8 (% ) 88. 13 82. 45 88. 25 83. 27

改进 KNN 正确率召回率 代价因子时间 ( s)
(%) (% ) 3. 92 3. 54 4. 07 3. 83 3. 71 3. 82 148. 2 149. 1 147. 6 147. 3 148. 4 148. 1

代价因子时间 ( s)
2. 25 2. 12 2. 02 1. 85 1. 88 2. 02

138. 5 89. 18 82. 13 142. 7 92. 46 81. 96 145. 1 93. 83 82. 72 139. 2 92. 95 82. 48 138. 8 93. 72 81. 56 140. 8 92. 43 82. 17

6  算法评价
   垃圾邮件过滤的性能评价通常借用文本分类的相关 指标 。评估映射准确程度的参照物是人工分类结果 (假 设人工分类完全正确且排除个人思维差异的因素 ) , 测试 结果与人工分类结果越相近 ,分类的准确程度就越高 。    假设待测集邮件集合中共有 N 封邮件 , 垃圾邮件的 判定结果如表 1 所示 。    表 1  垃圾邮件系统判定情况分布
实际为垃圾邮件 系统判为垃圾邮件 系统判为合法邮件
A C

10 85. 46 83. 78 20 81. 81 85. 16 25 77. 02 86. 54

平均 83. 13 84. 24

   通过以上的实验 , 可以看出 : 随着 K 值的增大 , 经典
KNN 正确率减小 ,而召回率增大 ,这是因为本文实验样本

中 , 合法邮件数量小于非法邮件 , 系统将待测文本分到垃
实际为合法邮件
B D

圾邮件类的概率增大 , 所以此算法将合法邮件误判为垃 圾邮件的可能性大 , 而垃圾邮件漏网的少 , 改进 KNN 受
K值变化影响不大 。通过比较改进 KNN 和经典 KNN 的

   其中 N =A +B + C +D ,则有 :

值可以发现 : 改进 KNN 的正确率 、 代价因子值均高于经 典 KNN ,改进 KNN 能够提高电子邮件的过滤性能 , 但是 改进的 KNN 同时也增加了时间开销 。

A    ( 1 ) 正确率 [ 11 ] ( Precision ) : P = , 即垃圾邮件检对 A +B

率 。它反应了过滤系统“ 找对 ” 垃圾邮件的能力 , 正确率越 大 ,将合法邮件误判为垃圾邮件的可能性越小 。
A    (2) 召回率 [ 12 ] ( Recall) : R = , 即垃圾邮件检出率 。 A +C

8  结  语
   本文通过改进 KNN 算法 , 从而降低 K值和训练文本 的分布对结果的影响 ,实验证明 , 改进后的算法能够提高 垃圾邮件的过滤效果 。如何提高算法运行速度 , 并使其 适应适时性要求较高的电子邮件过滤系统 , 还需要进一 步研究和探讨 。
参考文献 :
1  张帆 . 信息组织学 . 北京 : 科学出版社 , 2005: 411 - 412 2  王斌 ,潘文锋 . 基于内容的垃圾邮件过滤技术综述 . 中文信息学

这个指标反映了过滤系统发现垃圾邮件的能力 ,召回率越高 , “ 漏网 ” 的垃圾邮件就越少 。
A +C    ( 3 ) 代价因子 [ 13 ] ( Total Cost Ratio ) : TCR = , 其中 μB + C

μ为参数 ,表示将合法邮件误判为垃圾邮件的损失为垃圾邮 件判为合法邮件的 μ倍 。 TCR 越高 , 则垃圾邮件过滤系统的 损失越低 。

报 , 2005, 19 ( 5) : 4 - 5
3  Joachim s T . Text Categorization w ith Support VectorMachines: Learn2 ing with Many Relevant Features . European Conference on Machine

   以上是垃圾邮件过滤系统性能评价中的三个最重要 的指标 , 在实际中 ,正确率比召回率更重要 。

?77?

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

应用实践

   总第 149 期

9  M itchell T M. Machine Learning . New York: McGraw - H ill, 1997 10  Salton G,McGill M J. Introduction to Modern Information Retrieval . McGraw H ill, Computer Series, 1983 11   徐洪伟 ,方勇 ,音春 . 垃圾邮件过滤技术分析 . 通信技术 , 2003, 142 ( 10) : 127 12  Georgios Sakkis, Ion Androutsopoulos . Stacking Classifiers for Anti Spam Filtering of Email . In: Proceedings of the Conference on Emp iri2 cal Methods in Natural Language Processing ( EMNLP) . 2001: 44 50 13  Androutsopoulos I, Koutsias J, Chandrinos K V , Paliouras P, Spyropou2 los C D. An Evaluation of Na? ve Bayesian Anti - Spam Filtering . In: Proceedings of the Workshop on Machine Learning in the New In2 formation Age, 11 th European Conference on Machine Learning . 2000: 9 - 17 14   The L inguist L ist . http: / / listserv . linguistlist . org / archives/ linguist . htm l . (Accessed Dec. 20, 2006) (作者 E - mail: elili62@126. com )

4  L i Baoli, Chen Yuzhong, Yu Shiwen. A Comparative Study on Auto2 matic Categorization Methods for Chinese Search Engine. In: Proceed2 ings of the Eighth Joint International Computer Conference, 2002: 117 - 120 5  Androutsopoulos I, Koutsias J, Chandrinos K V , Spyropoulos C D. An Experim ental Comparison of Naive Bayesian and Keyword - Based An2 ti - Spam Filtering with Encryp ted Personal E - mail Messages . In: Proceedings of the 23 rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 2000: 160 167 6  Cover T M , Hart P E. Nearest Neighbor Pattern Classification. IEEE Trans . Inform. Theory, 1967 ( 13) : 23 7  Salton G, Wong A , Yang C S . A Vector Model for Automatic Inde2 xing . Communication of ACM , 1975, 18 ( 11) : 613 - 620 8  Saham i M , Dumais S, Heckerman D , Horvitz E. A Bayesian App roach to Filtering Junk E - Mail . AAA I Technical Report, 1998 ( 5) : 55 62

动    态
e - Learning项目 — — —B lendEd 成果预发布
  B lendEd项目是苏格兰基金管理委员会资助的一个合作 式 e - Learning改革项目 ,将于 2007 年春完成 。该项目由英国 瑞德克学院发起 ,项目组成员包括 6 所进修大学 ,大学开放学 习交换组 ( Colleges Open Learning Exchange Group , COLEG ) 和 J ISC苏格兰西南区域支持中心 ( J ISC Regional Support Cen2
tre Scotland S& W , J ISC RSC Scotland S& W)。 B lendEd的目标是在大学专科社会公益和商业管理两个 ( 2 )有高质量的资源去支持复合学习传输模块 ; ( 3 )强有力的员工开发程序以支持部门采纳该模块 ; ( 4 )有实施复合学习的指南 ; (5) 教 育 者 角 色 新 转 变 — — — 成为复合学习技术专家 (B lended Learning Technologist, BLT) 。

该项目初期试验效果不错 , 得到了学习者及教学人员的 一致好评 。很多合作伙伴都任命了新的复合学习技术专家支 持该模块的运行 ,目前 ,该项目正在对 500 多个学习对象进行 最后编辑 。
(编译自 : The B lendEd Project Nears Comp letion. http: / /www. dlib. org / dlib / december06 /12 inbrief . htm l#DYET . [ 2007 - 1 - 3 ] )

专业中引进一个复合学习传输模块 。这种方法的本质是为现 在的高等教育机构提供基于主题的电子资源 , 支持教育者以 一种新的 、 灵活的方式将这些资源传递给学习者 。该项目的 主要成果包括 :
( 1 )一个完全测试好的复合学习模块和实施计划 ;

(本刊讯 )

?78?


更多相关文档:

云计算平台下基于改进型DMTP的反垃圾邮件系统设计.pdf

云计算平台下基于改进型DMTP的反垃圾邮件系统设计 - 针对DMTP(diffe

云计算在反垃圾邮件系统中的运用.doc

云计算反垃圾邮件系统中的运用 - 龙源期刊网 http://www.qikan.com.cn 云计算反垃圾邮件系统中的运用 作者:吕建强 来源:《电脑知识与技术》2017 年第 09...

云计算实际案例_图文.ppt

(GAE) Web运行平台 Gmail、Google Docs等云端应用 分布式文件系统GFS 分布式计算...反垃圾邮件系统、广告 的优化选择、大数据处理、用户兴趣预测、搜 索排名、广告...

基于云计算的反垃圾邮件系统研究_图文.pdf

基于云计算反垃圾邮件系统研究_IT/计算机_专业资料。基于云计算反垃圾邮件...云计算 分布式 反垃圾邮... 4页 免费 邮件与反垃圾邮件系统 28页 免费 ...

云计算技术云计算研究热点(2)(精)_图文.ppt

分布式计算平台 --组成:设计接口、任务调度器和运行时间支持系统 --系统的...应用研究 ? 云安全研究 Anti-Spam Grid:反垃圾邮件网格反垃圾邮件网格的主要...

云计算实际案例_图文.ppt

(GAE) Web运行平台 Gmail、Google Docs等云端应用 分布式文件系统GFS 分布式计算...反垃圾邮件系统、广告 的优化选择、大数据处理、用户兴趣预测、搜 索排名、广告...

《云计算》教材.doc

云计算是并行计算(Parallel Computing) 、分布式计算(...微软的云计算操作系统 Microsoft Windows Azure 也可...与早在 2003 年就提出的反垃圾邮件网格非常接近[5...

云计算研究热点_图文.ppt

分布式计算平台 --组成:设计接口、任务调度器和运行时间支持系统 --系统的...应用研究 ? 云安全研究 Anti-Spam Grid:反垃圾邮件网格反垃圾邮件网格的主要...

云计算商家对比_图文.ppt

云计算商家对比_计算机软件及应用_IT/计算机_专业...反垃圾邮件系统、广告的优化 选择、大数据处理、用户...GFS 针对数据密集型应用的分布式文件系统 ...

虚拟化与云计算_云计算实际案例_图文.ppt

虚拟化与云计算_云计算实际案例_互联网_IT/计算机_...反垃圾邮件系统、广告 的优化选择、大数据处理、用户...GFS 针对数据密集型应用的分布式文件系统 ...

云计算的发展前景.doc

自我管理和自我修复的虚 拟化云计算软件, 使来自全球的应用可以访问分布式的大型...反垃圾邮件网格体现了真正的网格思想,每个加入系统的用户既 是服务的对象, 也是...

云计算稿件.ppt

云安全的核心思想与刘鹏在2003年提出的反垃圾 邮件网格非常接近。建立一个分布式统计和学习 平台,以大规模用户的协同计算来过滤垃圾邮件: ? 首先,为客户收到的每...

云计算技术.txt

云计算是并行计算( Parallel Computing)、分布式计算(...微软的云计算操作系统“ Microsoft Windows Azure”也...云安全的核心思想与早在 2003年提出的反垃圾邮件...

巍山代理发表职称论文发表-集群计算机处理系统设计论文....doc

交通信息分布式处理中的 Hadoop 调度算法优化 52……基于和声算法异构 Hadoop ...云计算平台下基于改进型 DMTP 的反垃圾邮件系统设计 95……一种改进的 Linux ...

云安全.doc

云安全思想的来源云安全技术是 P2P 技术、网格技术、云计算技术等分布式计算技术...反垃圾邮件网格体 现了真正的网格思想,每个加入系统的用户既是服务的对象,也是...

云计算及其应用论文.doc

技术上,分布式计算的日益成熟和应用,特别是网格 计算...云计算试验中心;解放 军理工大学研制了云存储系统 ...与早在2003年就提出 的反垃圾邮件网格非常接近[5]...

《云计算研究热点》ppt_图文.ppt

分布式计算平台 --组成:设计接口、任务调度器和运行时间支持系统 --系统的...应用研究 ? 云安全研究 Anti-Spam Grid:反垃圾邮件网格反垃圾邮件网格的主要...

云计算技术及其安全性研究.pdf

云计算是随着处理器技术、虚拟化技术、分布式存储技术...(7) 系统和网络隔离 ( S y s t e m a n ...CelloCloud 将反垃圾邮件技 术包括黑名单、分类数据...

一种基于云的+Web应用安全服务_图文.pdf

建 立一个分布式统计和学习平台,以大规模用户协同 计算的方式来过滤垃圾邮件。...安全云服务通过实时监控 系统状态、资源占用情况,精确调度、按需部署,使 得安全...

云计算发展现状及未来展望_图文.ppt

分布式计算框架、集群管理、云存储 系统、弹性计算系统、并行数据挖掘工具等功 能...反垃圾邮件网格 ASG Server ASG Server To Other Grid Nodes ASG Server ASG ...

更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com