基于SVM的渣滓短信过滤系统（用android实现，并在真机测试）

基于SVM的垃圾短信过滤系统^*

摘要：传统的垃圾短信过滤方案，以垃圾短信中出现的敏感词作为判断的依据，却忽略了正常短信中出现的词对分类的贡献，并且由于短信用语的灵活性，特征提取难度较大。本文提出了一种基于svm算法对垃圾短信进行监控和过滤的方案，该方案根据短信内容、短信长度等特征，对短信文本进行向量空间的表示。通过机器学习的方式，对垃圾短信进行判断，过滤。相比传统方法而言，本系统在过滤准确度和效率两方面均获得大幅度提升。

关键词:垃圾短信，短信过滤，机器学习，支持向量机，文本分类,特征提取

中图分类号: TP309   文献标志码: A

Spam Messages Filtering System Based On SVM

LIHui ,YE Hong ,PAN Xue-rui , DUAN Zhen ,ZHANG Yan-ping

（Department ofComputer Science & Technology ,Anhui University,Hefei 230601,China)

Abstract：The traditional scheme to filter spam messages isgenerally based on the occurrence of sensitive words in them, but ignores thecontribution made to the classification by words appearing in normal messages.Andthe flexibility of message phrases renders feature extraction rather difficult.This text presents a scheme to superintend and filter spam messages on thebasis of SVM algorithm. This scheme expresses the text in way of vector spacewith reference to features like the content and length of messages. And it usesthe method of machine learning to judge and filter spam messages. Compared withtraditional schemes，this system performs better in terms of filtering efficiency andaccuracy.

Keywords: spam messages, message filtering, machine learning, support vector machines,text classification, feature extraction

0.引言

   短消息服务是移动通信网络上一项基本的服务，但随着短信使用的越来越普及，垃圾短信成为日益突出的问题，来自不同渠道的各种垃圾短信充斥手机短信，给用户带来了很多的烦恼。手机垃圾短信是指未经请求或允许而收到的，对接收者来说无用的短信，例如未经短信接收人请求或允许而发送的商业广告。垃圾短信的常见内容包括广告信息、色情信息、假中奖信息、欺诈信息、恶作剧等。根据中国互联网协会发布的调查结果显示，我国平均每周收22.92条的垃圾短信。目前我国手机上用户已经超过五亿，全国用户每天收到的垃圾短信高达十五亿条以上。虽然，各种网关，短信中心均建有垃圾短信监控和控制模块，但由于不同用户需求不同，以及受到转发速度的影响，这些模块往往做的很简单，不能有效的过滤掉垃圾短信。

现有垃圾短信过滤软件一般采用黑白名单机制和关键字过滤方法。

其中黑白名单机制是根据发送过来的手机号进行过滤，一般黑名单是需要人工添加的方法实现，白名单一般是通过直接扫描用户的通讯录生成，也可通过用户手动添加，对白名单中的号码实现直接放行，而对于黑名单中的号码，则不管其内容如何，系统都进行拦截，但黑白名单机制对陌生号码的短信基本无能为力。

而市面上流行的垃圾软件中，对待这些陌生号码，往往单纯的采用一些关键字进行短信的屏蔽，实现起来虽较为简单，但效果很差。这是因为关键字选取难度大，表示相同意思的词很多，用法也很灵活，比如“拨打”，“电话”，“热线”，“拨”，“电”，“打”，等词，均可表示为拨打电话的意思。此外不法份子还采用各种方法，绕过关键字表，使得关键字机制形同虚设，不法分子往往采用以下手段：

（1）在一些较敏感的字段中，添加“”，“\”,“#”，等符号绕开关键字，比如“您好：我》集》团》现》有》多》项》税》票》对》外》开》出（请电13417－567995林总）”中，不法分子就采用“》”来绕开关键字表。

（2）繁体字替换，大部分关键字表中，采用的均为简体字，不法分子利用这个弱点，将短信内容全部替换为繁体字，比如“金振錢莊長期在上海為中小企業及個人發放貸款，金額1-500萬。期限1-12個月，戶籍不限，無需擔保。諮詢13017317585陽經理。”

（3）错别字替换，对一些敏感的关键字，不法分子往往使用一些别字来代替，比如“诚信集团长期在本市提供无担保借贷《月息3%》有意者拔打：13826063677广东，移动动感地带卡王经理”其中，不法分子将“拨打”替换为“拔打”。

另外，单单凭借某个关键字是否出现，来作为衡量是否为垃圾短信的唯一标准，是极为不妥当的，比如，很多商业类的广告都有“咨询”这个关键词，如果我们简单认为只要出现带“咨询”字眼的词，就是垃圾短信的话，会在很大程度上造成误判，比如，这样一条正常短信，“这件事我咨询下学校，再给你答复”。所以仅仅采用上述简单方法进行过滤的话，很大程度上用户的正常短信也会被屏蔽掉，这可能会给用户造成很大程度的损失。

垃圾信息过滤可以看作是文本分类技术的应用，黑白名单^[1]、神经网络算法^[2]、贝叶斯^[3]和SVM^[4] 等，都常用于文本分类。本实验所采用的模拟程序对发送到手机上的垃圾短信内容进行预处理，加入了规则,并结合对短信长度的信息，利用信息增益减小单词属性的个数判断，并采用SVM算法，对预处理后的短信进行分类。结果表明，该方法具有较好的准确率。同时合法短信，能极少的被判别为垃圾短信。

1. 短信特征提取

一般的文本分类只采用分词后的词作为特征项，考虑到短信用语的灵活多变，我们在一般的方案中，加入规则，以及短信长度，作为特征项，结果显示，这种方法能够大大提高准确度。

1.1 样本预处理及分词

过滤系统将以文本形式接受到的短信，进行预处理，首先将短信中对判别是否为垃圾短信无意义的词，如“了，的，啊”以及各种标点剔除掉。

再次按照分词字典对短信进行分词，分词是将短信分割成一个个有意义的单词，中文分词有着其本身的复杂性^[5]，比如词性变化，一词多意等。

其次，对分词后得到的信息进行提取，例如；

出现网址信息，如http://www.baidu.com等。

出现关于钱的信息，如“钱汇到这个账户来”，“20元”等。

出现关于电话号码的信息，如“拨打125908061”，其中连续出现的九位数“125908061”，被抽象为电话号码。

然后将文本进行向量空间模型的表示(VSM)^[6]．向量空间模型的基本思想是把文档简化为特征项的权重为分量的向量表示：(w_1,w₂,……w_n)，其中为w_i为第i个特征向量的权重，一般选取词作为特征项，权重用词频表示。

1.2 特征降维

预处理之后的短信会被分成很多的词语，当训练集使用的字典包含词语数量很大时，其向量空间维数必定相当巨大，必须对其进行特征降维。特征降维有两种方法：(1)特征选择，不改变原始特征空间的性质，只是从原始特征空间中选择了一部分重要的特征，组成一个新的低维空间。(2)特征抽取，存储和计算量大，不适合对手机短信的处理。因此，本文采用特征选择的方法进行降维。常用的特征选择方法有：文档频率(DF)，互信息(MI)，信息增益(IG)，统计量(CHI)等^[7]。本系统在特征选择算法上采用信息增益(IG)，实验中我们对在语料中出现的每个词条计算其信息增益值，从原始特征空间中移除低于特定阈值的词条，保留高于特定阈值的词条。

1.3 长度特征提取

短消息规范中规定一条短消息中文为70个汉字，一般垃圾短信发送者为了有效降低短信的发送成本，尽量达到宣传或欺诈效果往往尽量使用完70个汉字的信息量，使得单位成本的效益最大化，见图（1），其中正常短信长度大部分长度在30汉字长度以下，所占比重为72.60%，而垃圾短信在这个范围内仅占0.33%，而垃圾短信长度主要分布在60汉字以上，高达69.91%，而正常短信中所占比例仅为6.16%，所以我们将短信长度，也作为短信特征值之一。

图 1 垃圾短信和正常短信长度特征分布

1.4 其他特征提取

垃圾短信中往往会频繁的出现网址，电话以及和金钱有关的信息，我们将这些信息提取出。判断是否出现网址信息，主要根据短信中是否出现http，www，com等关键词。判断电话信息主要根据预处理后短信中连续出现数字位数是否在7到12位之间，金钱信息的出现判断，则是将常用的与金钱相关的词提取出来，如“打到”，“农行”，“账户”，“钱”等，并引入加权机制，计算加权和，权值高的短信，则认为其出现了与金钱相关的信息。其信息特征分布如表1所示，其中（Currbish|Ri）表示出现规则i，是垃圾短信的概率，(Cnormal|Ri)表示出现规则i，是正常短信的概率。

表1 垃圾短信和正常短信其他特征分布

2.构造分类器

SVM是近年机器学习、识别方面公认比较好的算法。在解决小样本、非线性及高维模式识别中表现出许多特有的优势, 是基于统计学习理论的VC 维理论和结构风险最小原理。 

  当问题并不是线性可分时,可以通过一个适当的非线性函数φ（即核函数）,将数据由原始特征空间映射到一个新的特征空间，见图（2）然后在新空间中寻求最优判定超平面,其数学原理见参考文献[8-10]。

       图 2线性可分和不可分时的最优超平面

常用的核函数有

　　(1)线性核函数K(x,y)=x·y；

　　(2)多项式核函数K(x,y)=[(x·y)+1]d；

(3)径向基函数K(x,y)=exp(-|x-y|^2/d^2)

(4)二层神经网络核函数K(x,y)=tanh(a(x·y)+b)．

本文选择的是RBF径向基内积函数, 支持向量机的三个基本思想可以概括为：求最优的分类面以取得较好的推广能力；提出软间隔的概念以解决线性不可分的问题；引入核函数解决平面从非线性扩展到线性。

SVM的学习过程如下：

Step1:给定训练集

Step2:假设空间H，从H中选择“最好”的h，这个h的期望风险有下列形式的界:

这个界至少以1-η概率成立。

Step3:通过同时最小化式右边两项来最小化E(h)，来使得结构风险最小化。

3.实验结果及分析

实验中所使用的短信集全部都是中文短信，从实际手机用户和网上收集的正常短信和垃圾短信各600条，其中随机选择360条垃圾短信和360条正常短信作为训练集，其余短信作为测试集，选取不同的阈值，得到不同的维数，其中阈值选取越大，得到维数越少，结果如表2所示。其中Sn表示正常短信误判率，Sr表示垃圾短信误判率，Sa表示总识别率。表3是在表2的基础上加入各种规则后，得到的结果，表4则是在表3基础上加入长度信息后得到的结果。

表2   单一特征值过滤结果

表3   加入规则后的过滤结果

表4  加入长度判断后的结果

从表2可以看出，随着选取的特征属性集维数的升高，SVM的分类正确率随之提高。但提高到一定维数时，分类效果稳中有降。分析其原因是在低维数时，分类器不能获得足够的特征以进行短信的判断。随着维数的上升，分类器逐渐获得更多有用信息，从而可以提高分类的正确率。但继续上升到一定维数时，新加入的特征已经不能对区分垃圾短信和非垃圾短信提供新的有用信息，甚至可能跟前面提供的信息相互冲突，反而影响了分类器分类的效果。

在添加规则和增加长度信息判断后，Sn（正常短信误判率）和Sr（垃圾短信误判率）均有显著降低，证明这些规则和长度是区别垃圾短信和正常短息必不可少得因素，再选取特征值时不可忽略。

同时我们采用传统方法，提出垃圾短信中300个关键词，与我们系统采用的方案进行比较，结果如表5所示。

   表5  维数为300维时各种过滤方案比较

    表中可以看出传统的关键字过滤中Sr（垃圾短信误判率）要远远低于单一特征值过滤结果，但Sn（正常短信误判率）普遍高于后者，这是因为，前者特征选取是针对垃圾短信的，而后者特征选取则是综合考虑正常短信与垃圾短信的，所以前者的Sn（正常短信误判率）高于后者的Sn（正常短信误判率）。正如先提到的那样，由于短信用语的灵活性，往往会造成垃圾短信特征表现不明显，所以会造成单一特征值过滤中Sr（垃圾短信误判率）较高。

在实际选择维数时，我们还对系统的性能进行了分析，对各个维数所占内存的大小进行了比较，结果如表6所示。

表6   性能分析

我们发现随着维数增加，SVM算法的训练时间和学习时间都随之增加，并且训练生成的模型所占空间也会随之增加，所以需要对时间，空间和效果进行综合考虑。

综上，从总体准确度来说维数选在665维比较好，Sn（正常短信误判率）为1.67%，Sr（垃圾短信误判率）为3.75%,总体准确度能达到97.2%,但所占内存较大为1.61MB，当维数选在300维时，Sn（正常短信误判率）为1.67%，Sr（垃圾短信误判率）为5.00%，总识别率达到96.76%，但所占内存仅为前者的1/3,所以综合考虑到处理速度，以及所占内存大小，在实际应用中，维数选在300维比较合适。

4.结束语

基于SVM的垃圾短信过滤系统可以取得很好的过滤效果。实验表明，该方法可以以很高的准确率判断垃圾短信，同时，对合法短信判断的错误率很低，减少了因为误判对移动用户造成的损失。随着短信业务的不断发展，短信的形式不再以纯文本形式为主。以声音和图片为载体的多媒体短信(彩信)得到广泛的普及，垃圾彩信也开始出现，如何有效、快捷地过滤彩信将是下一步工作的重点。

参考文献：

[1] 张燕，傅建明．垃圾短信的识别与追踪研究[J]．计算机应用研究，2006，23(3): 245-247.

[2]Miguel E Ruiz. Padmini SrinivasanHierarchical Text Categorization Using Neural Networks[J]．InformationRetrieval，2002，5(1)：87-118．

[3] 章舜仲，王树梅，黄河燕 ，陈肇雄.词间相关性在贝叶斯文本分类中的应用研究[J]. 计算机工程与应用，2009，45(16):159-161.

[4] 刘晓亮,丁世飞, 朱红, 张力文. SVM用于文本分类的适用性[J].计算机工程与科学，2010,32(6):106-108.

[5]Shasha Liao, Minghu Jiang. A New Feature Selection Method Based On ConceptExtraction In Automatic Chinese Text Classification [J].New Mathematics and Natural Computation(NMNC), 2007, 03(03):331-347.

[6] Salton G，Wong A. On the specification of term value in automatic indexing[J]．Journal of Documentation，1973，29(4)：351—372.

[7] Yang Y，Pedersen J Q.A comparative study on feature selection in text categorization[A]／／Proceedings of the 14th International Conference on MachineLearning(ICML’97)[c]．SanFrancisco：Morgan Kaufmann Publishers．1997：412—420.

[8]LanckrietG,Cristianini N,Bartlett P,et al. Learning the kernel matrix with semidefiniteprogramming[J].Journal of Machine Learning Research,2004,5(12): 27-72.

[9]AMARIS, WU S. Improving Support Vector Machine Classifiers by Modifying KernelFunctions[J].Neural Networks,1999, 12(6):783-789.

[10] Edda Leopold，Jorg Kindermann．Text Categorization with Support Vector Machines，How to represent text in input space[J]．MachineLearning，2002，46(1)：423-444．