基于改进平衡Winnow算法的短信过滤系统
摘 要：将黑白名单技术与chinaaet.com/search/?q=Balanced Winnow" title="Balanced Winnow">Balanced Winnow算法相结合，实现对垃圾短信的过滤。采用CHI特征提取算法并对权重计算方法进行改进，同时提出了去除训练样本中野点的想法，通过判定去除野点，减缓在训练过程中出现的抖动现象。实验表明这种改进对于提高训练速度及提高短信过滤的性能均有很好的作用。
关键词：balanced Winnow；短信过滤；CHI；野点
手机短信以其短小、迅速、简便、价格低廉等优点成为一种重要的通信和交流方式，受到众多人士的青睐。然而，手机短信与邮件一样存在着垃圾信息问题。
目前，垃圾短信过滤主要有黑名单过滤、关键词过滤和基于文本分类的内容过滤等方式。黑名单过滤和关键词过滤方式能快速过滤垃圾短信，但这两种过滤方式实质是基于规则的过滤，虽然在一定程度上阻挡了一些垃圾短信，但规则的方法需要更多的用户自定义设置，很容易被反过滤。基于文本分类的短信过滤采用常见的分类算法，如朴素贝叶斯、SVM、神经网络等。黎路[1]等人将贝叶斯分类应用到J2ME模拟环境中成功地过滤了中奖短信和祝福短信。浙江大学的金展、范晶等[2]将朴素贝叶斯和支持向量机结合，解决了传统垃圾短信过滤系统短信特征和内容未能得到及时更新而导致过滤性能降低的问题。王忠军[3]将基于朴素贝叶斯短信过滤算法与基于最小风险贝叶斯算法进行了实验分析和比较，结论是基于最小风险的短信过滤算法具有较好的性能。然而，短信过滤的准确率依赖于其训练样本的数量及质量，这些分类算法需要经过训练学习建立分类器模型，因此在速度上不能很好地满足短信过滤实时性的要求。从现有技术上来说，垃圾短信的过滤在准确率和效率方面仍然不能满足现实需要。
本文针对现有短信过滤技术的不足，设计了在手机终端的短信过滤系统，根据垃圾短信的特点将黑白名单和基于内容过滤相结合。这种过滤方式要求能够快速地对短信进行分类，并且能够实现用户对短信过滤的个性化要求，使垃圾短信过滤系统具有更好的过滤性能。
Winnow算法是在1987年由Nick Littlestone提出并对可行性做了严格证明的线性分类算法[4]。当时的目标是想找到一种时空复杂度仅仅与分类对象相关属性相关的数量呈线性相关的算法。平衡Winnow算法是对基本Winnow算法的一种改进，该算法具有过滤速度快、性能好、支持反馈更新的优点，在信息过滤领域有很好的应用前景，尤其适合于对实时性要求较高的短信过滤系统。
本文设计并实现了一个基于平衡Winnow算法的短信内容过滤系统，对该算法在短信过滤系统上的应用进行了详细分析。分类器的训练过程分成预处理、训练、分类和反馈四个部分。
1 预处理模块
预处理模块包括中文分词、特征提取以及短信的向量表示子模块。
1.1 中文分词
中文分词是汉语所特有的研究课题。英语、法语等印欧语种词与词之间存在着自然的分割，一般不存在分词的问题。本系统采用了目前国内较多使用的中科院计算所开发的汉语词法分析系统ICTCLAS[5](Institute of Computing Technology，Chinese Lexical Analysis System)。ICTCLAS 3.0分词速度单机996 Kb/s，分词精度98.45%，API不超过200 KB，各种词典数据压缩后不到3 MB，是当前相对较好的汉语词法分析器。
2 构造分类器
训练分类器是研究的重点，采用Balanced Winnow算法并对其进行改进。
2.1 Winnow分类算法
Winnow算法是二值属性数据集上的线性分类算
在平衡Winnow算法中，一旦参数α、β和阈值θ确定下来后，将在训练过程中不断更新权重向量w+和w-至最适合这组参数。因此对参数的依赖较小，需要手工调整的参数不多。
2.3 去除野点
