基于Winnow算法和CAPTCHA的垃圾短信过滤研究

摘要
随着移动通信技术的发展，手机短信已成为人们生活中必不可少的通信方式之一。然而日益增多的垃圾短信给人们的生活带来很多不便。垃圾短信过滤问题已成为全球性的具有重大现实意义的课题。本文深入研究了基于内容的垃圾短信过滤技术，改进了Winnow算法，并提出一种新的基于CAPTCHA的垃圾短信过滤方法，主要工作包括：
1）Winnow算法是一种可以在线更新的分类算法，它通过改变权重向量进行更新。为了降低算法的复杂度，本文提出在每次更新权值后加入剪枝过程，剪掉那些对分类结果几乎没有影响的特征。
2）利用用户交互式学习思想，根据用户的反馈信息随时更新Winnow分类器。本文提出的方法根据用户判定的误分类短信的信息找出未被判定的误分类短信，然后纠正分类器以前产生的错误，同时更新分类器的分类规则，避免以后的分类过程中产生同样的错误。更新分类器时采用Adaboosting算法提升分类器性能，并对Adaboosting算法进行了两方面的改进：针对退化问题，采用在各样本集内部调整短信样本的权重的方法；针对垃圾短信和正常短信的不对称问题，采用修改分类器加权因子的方法。
3）提出多Winnow分类器模型，根据多个分类器的分类结果对短信分类。利用同样的训练集选择出不同的特征集，根据各个特征集训练出不同的分类器。本文只实现了双Winnow分类器。
4）针对计算机程序经常发送恶意的组垃圾短信的现状，本文提出了基于CAPTCHA（全自动人机识别系统）的过滤方法，并提出一种新的基于图片识别的CAPTCHA方法。
关键词：垃圾短信  Winnow算法剪枝交互式学习多分类器模型全自动人机识别系统图片识别
目录
摘要.............................................................................................................................I
ABSTRACT...............................................................................................................II
目录..........................................................................................................................IV
1 绪论.......................................................................................................................1
1.1 研究背景............................................................................................................1
1.2 国内外垃圾短信处理现状................................................................................2
1.3 本文研究内容....................................................................................................4
1.4 本文结构............................................................................................................5
2 基于内容的垃圾短信过滤...............................................................................6
2.1 中文分词方法介绍............................................................................................6
2.2 特征选择方法介绍............................................................................................9
2.2.1 文本特征表示...............................................................................................................9
2.2.2 特征选择方法.............................................................................................................10
2.3 文本分类算法..................................................................................................12
2.3.1 贝叶斯分类.................................................................................................................13
2.3.2 支持向量机分类算法.................................................................................................14
2.3.3 决策树分类算法.........................................................................................................14
2.3.4 基于神经网络的分类方法.........................................................................................15
2.3.5 K近邻文本分类算法..................................................................................................16
3 基于改进的Winnow算法的垃圾短信过滤方法....................................18
3.1 线性分类器......................................................................................................18
3.2 Winnow算法.....................................................................................................19
3.3 Winnow算法中的剪枝.....................................................................................20
3.4 反馈学习提升分类器性能..............................................................................22
3.4.1 反馈学习.....................................................................................................................22
3.4.2 用户交互式学习.........................................................................................................22
3.4.3 利用Boosting算法更新分类器.................................................................................24
3.5 多Winnow分类器模型...................................................................................26
3.6 基于Winnow算法的垃圾短信过滤...............................................................27
3.7 实验结果与分析..............................................................................................30
3.7.1 实验环境与实验数据.................................................................................................30
3.7.2评价指标......................................................................................................................31
3.7.3实验结果与分析..........................................................................................................31
4 基于CAPTCHA的组垃圾短信过滤方法................................................36
4.1 CAPTCHA定义................................................................................................36
4.2 CAPTCHA分类................................................................................................36
4.3 CAPTCHA方法的应用....................................................................................38
4.4 本文提出的CAPTCHA方法..........................................................................39
4.5 实验结果与分析..............................................................................................40
5 总结与展望.........................................................................................................42
5.1 总结................................................................................................................42
5.2 进一步工作......................................................................................................42
参考文献...................................................................................................................44
致谢..........................................................................................................................47