论文部分内容阅读
摘 要：随着移动通讯的快速发展，手机短信已经成为了人们日常生活中重要的信息传递方式之一。但是，随之而来的问题是大量的垃圾短信肆意泛滥，人们因为垃圾短信而造成的经济损失的事件也屡见不鲜，这已经严重影响了社会的正常秩序。因此，如何有效识别过滤垃圾短信，遏制其传播，已经成为了迫在眉睫的实际问题。本文将根据短信拦截的需求和短信的特性，在有限的资源条件下，运用决策树预测模型，设计并实现一个基于手机联网的短信应用，其主要功能包括收发短信、黑白名单拦截和基于内容识别实现的垃圾短信识别过滤。
关键词：垃圾短信；过滤；拦截；内容识别；决策树
基金项目：西南科技大学大学生创新基金项目资助 编号：CX15-024引言
移动通讯的高速发展，使得手机短信成为人民生活不可或缺的一部分，但大量的涉黄、违法、反社会的垃圾短信严重打扰了人们的正常生活和工作，同时也浪费了运营商的通讯资源和网络资源。
垃圾短信是指未经用户同意向用户发送的用户不愿意收到的短信息，或用户不能根据自己的意愿拒绝接收的短信息。其主要包含以下属性：（一）未经用户同意向用户发送的商业类、广告类等短信息；（二）其他违反行业自律性规范的短信息。依据《中华人民共和国电信条例》第五十六条规定的九种任何组织或者个人不得利用电信网络制作、复制、发布、传播含有下列内容的信息，均可视为垃圾短信。[1]
腾讯移动安全实验室的数据统计：“2015年上半年，腾讯手机管家用户举报垃圾短信达3.08亿，同比增长12.36%。如果将用户举报的垃圾短信用五号字串起来，长度可以从北京到广州往返29次。垃圾短信类别主要分为广告类、诈骗类、违法类与其他类4大类。2015年上半年，广告类垃圾短信占垃圾短信总比例达84.04%，詐骗短信占比11.98%，违法类占比1.92%，其他类占比2.06%。在垃圾短信当中，对用户危害最大的是诈骗短信。2015年上半年用户举报诈骗短信3692万，占垃圾短信举报总比的11.98%，诈骗短信依然在持续增长”。[2]
由这份安全报告可以看出，现在垃圾短信的问题越来越严重，已经给人们的正常工作和生活造成了巨大的干扰。
针对垃圾短信，通讯运营商传统的拦截策略有控制发送频率、关键词屏蔽、手机实名制等。在手机应用端拦截垃圾短信，主要是在短信应用里内置识别拦截垃圾短信的功能，其包含的主要识别分类方法有：黑名单、白名单、关键词检测和基于短信内容的检测等。通过手机端主动屏蔽带有欺诈性质的短信，一方面可以分担运营商的压力，另一方面也让使用手机的客户群最大程度免受垃圾信息的骚扰。
本文将结合内容识别和文本分类算法，设计并实现在手机端快速有效地拦截垃圾短信的一款手机软件，该软件可以有效屏蔽和过滤垃圾短信，改善用户体验，防止用户经济受损。
现有识别过滤手段分析
运营商的拦截手段：[3]
1）控制发送频率：拦截发送短信频率很高的不正常号码。根据工业和信息化部提供的最低标准：“非节假日每个号码可以发送的短信条数每小时不得超过200条，每天总量不超过1000条；而在节假日期间，每小时不超过500条，每天总量不超过2000条”。
2）关键词屏蔽：运营商可以通过检测短信内容来实现点对点垃圾短信的拦截，尽管这种做法缺乏行业的统一标准，但是这是最常用的过滤方式。
3）手机实名制：手机号码捆绑身份证，运营商和公安部门合作，快速且精确打击垃圾短信的源头。
对于运营商这些拦截手段，垃圾短信传播的方式也有相当的变化：大量购买SIM低频发送、复制卡发送、使用特殊表达方式（同音字、异型字、近体字、多音字），敏感内容用特殊字符分隔开等，导致手段1和手段2的效果并不理想；手段3确实是可行的方案，但是在偏僻的地方，由于运营商监管不足，仍存在出售黑卡的现象，因此垃圾短信并不能被杜绝和消灭。
手机应用软件拦截手段：[4]
1）设置黑名单和白名单：在服务器端或手机端建立数据库存储手机号码和被标注的状态。若短信号码是黑名单的号码，直接拦截；若短信号码是白名单号码，直接放过。这种方式明显要比运营商的号码拦截更具有针对性。
2）关键词的检测：方法与运营商的关键词的检测大致相同，不过由于需要处理的短信数量比运营商的要少，而且和现在手机的性能有很大的提升，所以识别效率更高，漏判率更低，对垃圾短信的针对性更强。
3）基于短信内容的检测： 目前常用的文本分类算法有朴素贝叶斯（NativeBayes），贝叶斯网络（BayesNet），决策树（C45或者CART），随机森林（RandomForest），神经网络（BP），支持向量机（SVM）等等。优点：准确率高，模型易维护；缺点：成本开销相对大，需要大量计算和预处理训练集。[5]
对于手机软件端的拦截，手段1是目前手机短信应用必备的手动拦截垃圾短信功能；手段2相较于手段3，虽然成本开销低，识别速度快，但是有较高的误判漏判率；鉴于目前计算机计算性能过剩的现状，只需要一台高性能的计算机便能轻松完成十分复杂的计算，因此手段3的成本开销并不昂贵，而且其准确率比其他的手段要高，十分适合对垃圾短信进行快速并且准确地过滤和拦截。
在有限的资源条件下，我们需要一种文本分类算法，它应具有的特点是：训练周期短、系统开销小、预测分类速度快且准确率较高。决策树算法相较于其他分类算法如随机森林，支持向量机，神经网络等，它具有的以上提及到的特点。除此之外，决策树模型可读性优秀，有助于人工的数据分析；决策树模型能够一次构建多次使用，预测分类的最大计算次数小鱼或等于决策树的深度。因此决策树分类算法很适合在有限资源条件下，实现快速识别且准确率高的垃圾短信过滤拦截功能。
关键技术的研究
1.决策树模型（Decision Tree） 决策树是一种应用相当广泛的分类算法，它是一种弱学习的独立变量选择算法，经常使用于监督学习。决策树的模型是根据数据的属性采用树状结构建立的决策模型，它表示的是对象的属性与对象的类别的一种映射，树的每个子节点表示的是对象的类别的判断条件，树的叶子节点表示树的对象的类别的预测结果。[6-7]
特征的选择：选择一个确定度较高的特征作为判断的节点，可以快速的分类、减少决策树的深度。特征的确定度是指通过特征能区分出来的集合中的类别的纯度，如带翅膀的动物大部分会飞（特征确定度比较高）。
ID3算法的信息增益：信息熵表示的是不确定度，用来描述在数据集中类别的确定程度。信息增益可表示为分类前后的信息熵的差值，它用来描述某个特征对分类结果的影响大小。
假设在训练集 D 中，混有n种类别的数据， 表示类别 i 样本数量占所有样本的比例，其计算公式如下：
分类前的信息熵计算公式：
分类后的数据集D被分为k个部分，分类后的信息熵计算公式：
该特征对应的信息增益计算公式：
C45算法的信息增益率：它是对ID3算法的信息增益的改进，它克服了信息增益的两个严重的缺陷：1. 偏向拥有大量值的属性，如自变量；2. 使用离散化弥补了ID3算法对连续属性支持的不足。
对信息熵分类前计算公式进行改进：
信息增益率的计算公式：
CART算法里的基尼系数：基尼系数是另外一种描述数据集的不纯度的度量标准，相对于信息熵更为常用。当数据集中数据混合的程度越高，基尼指数也就越高。
假设数据集中类别有m个类别的数据，表示类别 i 样本数量占所有样本的比例，其计算公式：
分类前的基尼系数计算公式：
分类后的数据集被分为k个部分，分类后的基尼系数计算公式：
該特征对应的基尼系数的差值计算公式：
决策树通过不断重复求解当前特征集合中确定度最高的特征，将其作为决策树的节点，直到决策树的构建完成。从根节点到叶子结点的一条遍历路径就对应着一条合取规则，整个决策树就对应着一组析取表达式规则。决策树的预测是从根节点开始，顺着某条合取规则，得到最终的对象的类别的预测结果。
1.2.内容分类方法
内容识别分类的方法是指通过处理短信内容，达到识别来及短信的目的，步骤分析：
1）根据短信s，提取出其内容，用一定的特征提取方式将文本内的特征值提取出来，若特征存在，则特征值为正（true），相反则特征值为负（false）
2）根据步骤1所由该短信提取出来的特征集合构造出多维的特征向量：
3）训练步骤2所得到的训练集的特征向量集合，放入决策树模型中进行训练，得到训练模型model
4）对照步骤3所得的训练模型model，对每条新短信通过步骤2后得到的待预测的特征向量，从根节点开始遍历，按照模型的子节点顺序进行树的遍历，直至到达树的叶子节点，得到预测的结果
特征选取和等级划分：
1）在垃圾短信训练集中找出大量的明显的特征
2）在所选的特征中，统计在正常短信训练集和垃圾短信训练集的短信中分别进行一个匹配，比如正常短信训练集中出现a次，垃圾短信训练集中出现b次，得到比例
3）对特征集合进行降维和优化，我们可以对步骤2得到结果集合，划分取值区间，它来描述特征重要程度，然后依据步骤2所得的特征c值和其相关属性（如动词、名词、固定搭配）进行筛选和合并，形成最终的特征集合
后面的表格1为选取的特征描述以及对应的提取的方式。其中等级用来描述特征的重要性：等级1>等级2>等级3>等级4，其中等级的划分由在负集（垃圾短信集合）中出现的次数除以正集（正常短信集合）出现的次数之比c，具体如下： 1/2≤c为等级1，1/3≤c≤1/2为等级2，1/5≤c≤1/3为等级3，c≤1/5为等级4。以下为从实际项目中抽取的部分重要程度为等级1的特征：
5.实验结果分析：
由表格2和表格3我们可以看出决策树模型相较于其他模型，具有准确率高，训练模型周期短，训练开销小等优点，能够在有限条件资源下实现快速、准确且可自学习的垃圾短信拦截功能，CART的训练周期要比C45长，且准确率要比C45低，因此不推荐使用。
由表格4我们可以看出，决策树在拥有大量训练集的条件下，与实验1的随机森林相比较，准确率与随机森林相近，而且训练周期不足20分钟，远比随机森林的时间和内存开销小得多，能在较小开销获得较好的预测效果。如果拥有高性能的分布式框架提供分布式计算，决策树模型训练速度将会得到大大提高，这能让我们的模型以最小的开销得到最好的效果[8]。
结语
本文设计和实现了一个基于文本挖掘的基于在线识别判断垃圾短信的短信应用，它成本开销小，拦截垃圾短信速度快效果好，十分适合在有限资源条件下达到短信过滤的目的，同时通过不断地优化合并特征，使特征维数降低，避免了维灾难，并且规则也更便于理解，可扩展性和灵活性得到大大提高，可面对更加庞大的训练集，产生更准确的训练模型。
参考文献
[1] 中华人民共和国电信条例[S].2000年9月20日.
[2] 腾讯移动安全实验室2015年上半年手机安全报告[R].2016年.
[3] 赵英刚，龚磊 - 基于行为识别和SVM的短信过滤方法研究[J].微计算机信息.2011年28卷第1期.
[4] 杨明极，宋艳艳 - 支持向量机在垃圾短信拦截系统中的实现[J].通信技术.2012年01期[4] 钱升华，[5] 武优西，柴欣，陈冀川 – 文本分类综述及手机垃圾短信过滤方法[J].河北工业大学学报.2007年2月.第36卷第1期.
[6] 刘庆瑜 - 基于决策树分类的手机垃圾短信过滤器的设计与实现[J].2011年.
[7] 胡新海 – 一种决策树算法对微博垃圾评论的检测[J].内江师范学院学报.30卷第6期.
[8] 朱杰 - 云计算在基于贝叶斯的垃圾短信过滤中的研究与应用[D].电子科技大学硕士论文.2010.
关键词：垃圾短信；过滤；拦截；内容识别；决策树
基金项目：西南科技大学大学生创新基金项目资助 编号：CX15-024引言
移动通讯的高速发展，使得手机短信成为人民生活不可或缺的一部分，但大量的涉黄、违法、反社会的垃圾短信严重打扰了人们的正常生活和工作，同时也浪费了运营商的通讯资源和网络资源。
垃圾短信是指未经用户同意向用户发送的用户不愿意收到的短信息，或用户不能根据自己的意愿拒绝接收的短信息。其主要包含以下属性：（一）未经用户同意向用户发送的商业类、广告类等短信息；（二）其他违反行业自律性规范的短信息。依据《中华人民共和国电信条例》第五十六条规定的九种任何组织或者个人不得利用电信网络制作、复制、发布、传播含有下列内容的信息，均可视为垃圾短信。[1]
腾讯移动安全实验室的数据统计：“2015年上半年，腾讯手机管家用户举报垃圾短信达3.08亿，同比增长12.36%。如果将用户举报的垃圾短信用五号字串起来，长度可以从北京到广州往返29次。垃圾短信类别主要分为广告类、诈骗类、违法类与其他类4大类。2015年上半年，广告类垃圾短信占垃圾短信总比例达84.04%，詐骗短信占比11.98%，违法类占比1.92%，其他类占比2.06%。在垃圾短信当中，对用户危害最大的是诈骗短信。2015年上半年用户举报诈骗短信3692万，占垃圾短信举报总比的11.98%，诈骗短信依然在持续增长”。[2]
由这份安全报告可以看出，现在垃圾短信的问题越来越严重，已经给人们的正常工作和生活造成了巨大的干扰。
针对垃圾短信，通讯运营商传统的拦截策略有控制发送频率、关键词屏蔽、手机实名制等。在手机应用端拦截垃圾短信，主要是在短信应用里内置识别拦截垃圾短信的功能，其包含的主要识别分类方法有：黑名单、白名单、关键词检测和基于短信内容的检测等。通过手机端主动屏蔽带有欺诈性质的短信，一方面可以分担运营商的压力，另一方面也让使用手机的客户群最大程度免受垃圾信息的骚扰。
本文将结合内容识别和文本分类算法，设计并实现在手机端快速有效地拦截垃圾短信的一款手机软件，该软件可以有效屏蔽和过滤垃圾短信，改善用户体验，防止用户经济受损。
现有识别过滤手段分析
运营商的拦截手段：[3]
1）控制发送频率：拦截发送短信频率很高的不正常号码。根据工业和信息化部提供的最低标准：“非节假日每个号码可以发送的短信条数每小时不得超过200条，每天总量不超过1000条；而在节假日期间，每小时不超过500条，每天总量不超过2000条”。
2）关键词屏蔽：运营商可以通过检测短信内容来实现点对点垃圾短信的拦截，尽管这种做法缺乏行业的统一标准，但是这是最常用的过滤方式。
3）手机实名制：手机号码捆绑身份证，运营商和公安部门合作，快速且精确打击垃圾短信的源头。
对于运营商这些拦截手段，垃圾短信传播的方式也有相当的变化：大量购买SIM低频发送、复制卡发送、使用特殊表达方式（同音字、异型字、近体字、多音字），敏感内容用特殊字符分隔开等，导致手段1和手段2的效果并不理想；手段3确实是可行的方案，但是在偏僻的地方，由于运营商监管不足，仍存在出售黑卡的现象，因此垃圾短信并不能被杜绝和消灭。
手机应用软件拦截手段：[4]
1）设置黑名单和白名单：在服务器端或手机端建立数据库存储手机号码和被标注的状态。若短信号码是黑名单的号码，直接拦截；若短信号码是白名单号码，直接放过。这种方式明显要比运营商的号码拦截更具有针对性。
2）关键词的检测：方法与运营商的关键词的检测大致相同，不过由于需要处理的短信数量比运营商的要少，而且和现在手机的性能有很大的提升，所以识别效率更高，漏判率更低，对垃圾短信的针对性更强。
3）基于短信内容的检测： 目前常用的文本分类算法有朴素贝叶斯（NativeBayes），贝叶斯网络（BayesNet），决策树（C45或者CART），随机森林（RandomForest），神经网络（BP），支持向量机（SVM）等等。优点：准确率高，模型易维护；缺点：成本开销相对大，需要大量计算和预处理训练集。[5]
对于手机软件端的拦截，手段1是目前手机短信应用必备的手动拦截垃圾短信功能；手段2相较于手段3，虽然成本开销低，识别速度快，但是有较高的误判漏判率；鉴于目前计算机计算性能过剩的现状，只需要一台高性能的计算机便能轻松完成十分复杂的计算，因此手段3的成本开销并不昂贵，而且其准确率比其他的手段要高，十分适合对垃圾短信进行快速并且准确地过滤和拦截。
在有限的资源条件下，我们需要一种文本分类算法，它应具有的特点是：训练周期短、系统开销小、预测分类速度快且准确率较高。决策树算法相较于其他分类算法如随机森林，支持向量机，神经网络等，它具有的以上提及到的特点。除此之外，决策树模型可读性优秀，有助于人工的数据分析；决策树模型能够一次构建多次使用，预测分类的最大计算次数小鱼或等于决策树的深度。因此决策树分类算法很适合在有限资源条件下，实现快速识别且准确率高的垃圾短信过滤拦截功能。
关键技术的研究
1.决策树模型（Decision Tree） 决策树是一种应用相当广泛的分类算法，它是一种弱学习的独立变量选择算法，经常使用于监督学习。决策树的模型是根据数据的属性采用树状结构建立的决策模型，它表示的是对象的属性与对象的类别的一种映射，树的每个子节点表示的是对象的类别的判断条件，树的叶子节点表示树的对象的类别的预测结果。[6-7]
特征的选择：选择一个确定度较高的特征作为判断的节点，可以快速的分类、减少决策树的深度。特征的确定度是指通过特征能区分出来的集合中的类别的纯度，如带翅膀的动物大部分会飞（特征确定度比较高）。
ID3算法的信息增益：信息熵表示的是不确定度，用来描述在数据集中类别的确定程度。信息增益可表示为分类前后的信息熵的差值，它用来描述某个特征对分类结果的影响大小。
假设在训练集 D 中，混有n种类别的数据， 表示类别 i 样本数量占所有样本的比例，其计算公式如下：
分类前的信息熵计算公式：
分类后的数据集D被分为k个部分，分类后的信息熵计算公式：
该特征对应的信息增益计算公式：
C45算法的信息增益率：它是对ID3算法的信息增益的改进，它克服了信息增益的两个严重的缺陷：1. 偏向拥有大量值的属性，如自变量；2. 使用离散化弥补了ID3算法对连续属性支持的不足。
对信息熵分类前计算公式进行改进：
信息增益率的计算公式：
CART算法里的基尼系数：基尼系数是另外一种描述数据集的不纯度的度量标准，相对于信息熵更为常用。当数据集中数据混合的程度越高，基尼指数也就越高。
假设数据集中类别有m个类别的数据，表示类别 i 样本数量占所有样本的比例，其计算公式：
分类前的基尼系数计算公式：
分类后的数据集被分为k个部分，分类后的基尼系数计算公式：
該特征对应的基尼系数的差值计算公式：
决策树通过不断重复求解当前特征集合中确定度最高的特征，将其作为决策树的节点，直到决策树的构建完成。从根节点到叶子结点的一条遍历路径就对应着一条合取规则，整个决策树就对应着一组析取表达式规则。决策树的预测是从根节点开始，顺着某条合取规则，得到最终的对象的类别的预测结果。
1.2.内容分类方法
内容识别分类的方法是指通过处理短信内容，达到识别来及短信的目的，步骤分析：
1）根据短信s，提取出其内容，用一定的特征提取方式将文本内的特征值提取出来，若特征存在，则特征值为正（true），相反则特征值为负（false）
2）根据步骤1所由该短信提取出来的特征集合构造出多维的特征向量：
3）训练步骤2所得到的训练集的特征向量集合，放入决策树模型中进行训练，得到训练模型model
4）对照步骤3所得的训练模型model，对每条新短信通过步骤2后得到的待预测的特征向量，从根节点开始遍历，按照模型的子节点顺序进行树的遍历，直至到达树的叶子节点，得到预测的结果
特征选取和等级划分：
1）在垃圾短信训练集中找出大量的明显的特征
2）在所选的特征中，统计在正常短信训练集和垃圾短信训练集的短信中分别进行一个匹配，比如正常短信训练集中出现a次，垃圾短信训练集中出现b次，得到比例
3）对特征集合进行降维和优化，我们可以对步骤2得到结果集合，划分取值区间，它来描述特征重要程度，然后依据步骤2所得的特征c值和其相关属性（如动词、名词、固定搭配）进行筛选和合并，形成最终的特征集合
后面的表格1为选取的特征描述以及对应的提取的方式。其中等级用来描述特征的重要性：等级1>等级2>等级3>等级4，其中等级的划分由在负集（垃圾短信集合）中出现的次数除以正集（正常短信集合）出现的次数之比c，具体如下： 1/2≤c为等级1，1/3≤c≤1/2为等级2，1/5≤c≤1/3为等级3，c≤1/5为等级4。以下为从实际项目中抽取的部分重要程度为等级1的特征：
5.实验结果分析：
由表格2和表格3我们可以看出决策树模型相较于其他模型，具有准确率高，训练模型周期短，训练开销小等优点，能够在有限条件资源下实现快速、准确且可自学习的垃圾短信拦截功能，CART的训练周期要比C45长，且准确率要比C45低，因此不推荐使用。
由表格4我们可以看出，决策树在拥有大量训练集的条件下，与实验1的随机森林相比较，准确率与随机森林相近，而且训练周期不足20分钟，远比随机森林的时间和内存开销小得多，能在较小开销获得较好的预测效果。如果拥有高性能的分布式框架提供分布式计算，决策树模型训练速度将会得到大大提高，这能让我们的模型以最小的开销得到最好的效果[8]。
结语
本文设计和实现了一个基于文本挖掘的基于在线识别判断垃圾短信的短信应用，它成本开销小，拦截垃圾短信速度快效果好，十分适合在有限资源条件下达到短信过滤的目的，同时通过不断地优化合并特征，使特征维数降低，避免了维灾难，并且规则也更便于理解，可扩展性和灵活性得到大大提高，可面对更加庞大的训练集，产生更准确的训练模型。
参考文献
[1] 中华人民共和国电信条例[S].2000年9月20日.
[2] 腾讯移动安全实验室2015年上半年手机安全报告[R].2016年.
[3] 赵英刚，龚磊 - 基于行为识别和SVM的短信过滤方法研究[J].微计算机信息.2011年28卷第1期.
[4] 杨明极，宋艳艳 - 支持向量机在垃圾短信拦截系统中的实现[J].通信技术.2012年01期[4] 钱升华，[5] 武优西，柴欣，陈冀川 – 文本分类综述及手机垃圾短信过滤方法[J].河北工业大学学报.2007年2月.第36卷第1期.
[6] 刘庆瑜 - 基于决策树分类的手机垃圾短信过滤器的设计与实现[J].2011年.
[7] 胡新海 – 一种决策树算法对微博垃圾评论的检测[J].内江师范学院学报.30卷第6期.
[8] 朱杰 - 云计算在基于贝叶斯的垃圾短信过滤中的研究与应用[D].电子科技大学硕士论文.2010.