基于文本内容的敏感词决策树信息过滤算法

邓一贵,伍玉英

(重庆大学a.信息与网络管理中心;b.计算机学院,重庆400030)

;

基于文本内容的敏感词决策树信息过滤算法

邓一贵a,伍玉英b

(重庆大学a.信息与网络管理中心;b.计算机学院,重庆400030)

随着互联网的高速发展,各种各样的信息资源呈指数级增长,随之出现许多负面影响,需要构建一个安全健康的网络环境。为此,提出针对网页文本内容的敏感信息过滤算法(SWDT-IFA)。该算法不依赖词典与分词,通过构建敏感词决策树,将网页文本内容以数据流形式检索决策树,记录敏感词词频、区域信息以及敏感词级别,计算文本整体敏感度,过滤敏感文本。实验结果表明,SWDT-IFA算法具有较高的查准率和查全率,且执行时间能够满足当前网络环境的实时性要求。

文本过滤;敏感级别;决策树;分流;词频

1 概述

随着互联网时代的到来,海量网络信息资源使得人们获取信息、生活交流、购物理财等变得越来越方便快捷。但是在人们获得便利的同时,各种色情、暴力、反动、迷信等非法信息也接踵而至,给人们尤其是青少年带来了巨大的危害,也给社会带来了诸多不良影响。对此,从事信息安全的研究人员做了多方面研究,提出多种内容过滤技术。

针对Web上大量的网页文本内容,本文利用决策树分流特性提出了敏感词决策树信息过滤算法SWDT-IFA。该算法基于敏感词库,通过构建敏感词决策树,以数据流形式处理网页文本内容,综合考虑区域、词频、敏感词级别三大要素,最终给出候选敏感词权重,计算文本整体敏感度,实现敏感文本检测。

2 问题描述及相关工作

定义1(敏感词) 是指带有敏感政治倾向(或反执政党倾向)、暴力倾向、不健康色彩的词或不文明语。但是也有的网站根据自身实际情况,设定一些只适用于本网站的特殊敏感词。敏感词设定功能在贴吧或论坛中都被广泛应用。

经相关研究,目前敏感信息过滤技术主要有以下4个需要解决的关键问题:

(1)人工干扰[1-2]。为了逃避关键词匹配过滤,敏感信息发布者通常会采取多种方式来逃避。包括在敏感词中间夹杂无意义的符号,如法&轮&功;将敏感词进行拆分,如三去车仑工力;用拼音代替敏感词,如fa lun gong;或者将前述几种方式结合,如法lun功等。对于这些复杂的组合但又不影响人阅读的方式,传统的文本过滤算法是无法解决的。

(2)准确性。部分在敏感网页上出现的敏感词,很多时候也会出现在健康教育类的网页中。实际上不应当将这些正常的教育网页归类到敏感信息中。

(3)分词障碍[3]。网络环境中新词、音译词大量出现,而中文文本又没有显示词边界,利用人工词典分词难以识别词典未包含的词,而且人工词典的更新和维护费时费力。

(4)时空效率。现在网络上的资源呈指数级增长,并且很多网页还在不定时的动态更新,这就要求敏感信息过滤算法必须满足时效性,以及海量的处理需求。这对时空效率的要求是必然的。

对于人工干扰问题,参考文献中的多数算法仅能处理夹杂特殊符号的敏感词,而对于拼音或者拆分词却无能为力。在SWDT-IFA中,采取了多种方式解决干扰问题:首先通过对文本停用词预处理文本,解决恶意夹杂无意义符号的敏感词问题;敏感词决策树同时兼具判断拼音的部分,对于夹杂拼音的敏感词也无从逃避;而对于拆分字,目前本算法是采用增加敏感词库词汇的方式。

针对准确性,文献[4]提出了针对准确检测敏感信息的解决方案,通过构建由显示,隐藏以及逻辑3种关键词构成的CNN-like词网对文本进行分析处理。该算法识别敏感信息文本的准确率较高,但是CNN-like需要人工去构建词与词之间的关联,而且构建原理和检测算法也比较复杂,对于敏感词递增的网络环境很难维护。文献[5]提出了基于自学习的两级过滤算法,在不依赖词典的情况下能够进行自学习,快速地处理文本,但是该算法在第一级主题字过滤时,有限的计数器就会被出现频率较多的敏感信息无关的字占用,以至于影响第二级过滤的准确性。SWDT-IFA在计算敏感词权重时,增加了敏感词级别因子:将类似于既出现在健康科普网站,又出现在敏感网站的敏感词级别降低,提高只会出现在非法网站敏感词级别,提升网页检测准确率。

目前许多敏感信息过滤算法都效仿文本主题提取技术[5-6],先对文本进行分词,提取关键词,再进行敏感词匹配,但是实际上敏感信息过滤与主题提取的侧重点差别较大。文本主题需要提取可以描述文本主旨的词语或者语句,是未知的,所以需要统计全文重点出现的词语;而敏感信息过滤需要找出的敏感信息是用户自定义的,已知的,数量在可控范围内,比WORD NET[7-8]要小得多。并且敏感信息发布者很有可能比较隐晦,不会大篇幅高频率地在文本中出现敏感词,利用词典提取主题词来过滤敏感信息的算法准确率并不高。所以,SWDT-IFA算法不依靠词典,直接将预处理过的文本与敏感词库中的词相匹配。

为了提高时空效率,SWDT-IFA算法将敏感词库中的词按照一定分类规则构建成了一棵敏感词决策树,提高文本检索时的匹配时效;并且决策树中敏感词的存储方式非常节约空间。

3 SWDT-IFA算法设计

算法整体思想如下:(1)将文本进行去停用词等预处理;(2)将敏感词库通过敏感词决策树构建算法建立成一棵分流树,以达到文本匹配过程的分流的作用,提高时空效率;在前2步的基础上,将预处理过的文本,以文本数据流方式通过检索敏感词决策树,记录文本中对应敏感词的频率和区域信息; (3)通过特殊计算公式,得出文本整体敏感度,将对应网页划分为敏感、非敏感网页。

3.1 文本预处理

首先需要对网页文本进行预处理[9],去除HTML标记,停用词过滤,以及记录文本区域信息,得到待处理文本。这里停用词定义为不能反映主题的功能词以及标点符号。例如:“的”、“地”、“得”之类的助词,以及像“然而”、“因此”等只能反映句子语法结构的词语,在敏感词过滤中,它们的出现频率较高,不属于敏感信息,还会影响敏感词检索效率,有必要将其滤除。而对所有无意义标点符号的滤除,解决了发布敏感信息者对敏感词过滤的干扰问题之一:在敏感词之间夹杂无意义符号。

3.2 敏感词决策树构建算法

算法通过对敏感词库中的词,按第一个字的拼音首字母进行分类,首字母都为A的“安眠药”、“安乐死”、“爱情”等为同一类。首字母同类的词再进行同字聚类,如“安眠药”、“安乐死”,这里对于这2个词,“安”字只存储一次,这种结构在敏感词较多时,能够节约空间。在存储汉字的同时,将该汉字的拼音也存储起来,当遇到纯拼音或者拼音与汉字搭配的敏感词时,算法也同样能够将其检测出来,如:“安le死”,“zuo e”。

建树算法的输入是敏感词库,每个敏感词都带有用户自定义的敏感因子,如:敏感词库Aford={{安眠药,3},{安乐死,3},{爱情,1},…,{糟蹋,2},{作恶,2}},输出一棵决策树,如图1所示。

图1 敏感词决策树

定义 2 敏感词库Aford={a0,a1,…,ai,…,an-1},(0≤i＜n),n为敏感词个数,ai表示敏感词;ai={ai,0,…,ai,j,…,ai,m-1},(0≤j＜m),aij表示第i个敏感词的第j个敏感字,m表示敏感词长度。

算法如下:

(1)初始化i=0,j=0,k=0,k记录孩子节点序号;

(2)输入敏感词ai,获取其中文长度为m,并提取首字母LetterS;

(3)进入S子树查询,将aij与S的第k个孩子节点childk比较;

(5)否则,若aij≠childk节点值,查询childk的兄弟节点是否为空;

(6)若childk兄弟节点为空,创建新节点childk+1,值为aij,记录aij的拼音,j++;

(8)否则,若childk兄弟节点不为空,k++,返回步骤(2),处理下一个敏感词;

(9)算法结束。

本文算法构建的敏感词决策树深度为敏感词库中最长敏感词的长度,一般≤6。树中每个节点都存储了敏感字以及其对应的拼音,叶节点还记录了敏感词的频率、区域信息、敏感级别,并且将各个词的频率和区域因子都进行了初始化。

3.3 查找树处理文本

定义3 文本流Btext={b0,b1,…,bi,…,bn–1}, (0≤i＜n),其中,bi表示文本中的字符;n为文本长度,在这里的字符定义为一个汉字或者一串没有空格间断的英文字符,以便区分检索决策树中的中文字和拼音。

算法如下:

(1)初始化i=0,k=0,k用于记录第一个进入分支的字符序列号;

(2)输入bi,k=i,j=0,判断bi为英文字符还是中文字符,如果是中文字符需要提取首字母s,英文直接获取;

(3)将bi与S的孩子childj相匹配;

(4)若bi==childj节点值,i++(若i≥n,则算法结束)

(5)若bi≠childj值,查询childj兄弟节点是否为空;

(6)若兄弟节点不为空,则j++,转步骤(3)处理;

;

(8)算法结束。

在3.1节、3.2节处理基础上,本文算法输入预处理过的文本,以数据流形式检测文本中所含有的敏感词,并记录其频率和区域信息以提供文本最后的敏感度计算。

3.4 文本敏感度计算

算法借鉴文献[8,10]中提取关键词采用的对每个词的词频因子、位置因子的加权计算方式,词频因子frei的计算方式为:

其中,fi为i的词频,再加上敏感词级别因子,最终对敏感词的权值采用下式:

其中,weighti表示敏感词汇i的权值;loci表示词汇i的区域因子,参考文献[6,11],当词汇出现在标题中时loci=5,否则loci=1;levi表示敏感词级别因子,一般地,敏感词分3个级别,绝对禁止levi=3,一般levi=2,需要审核levi=1,这3个级别由人工划分。α,β,γ都是调节因子,需要设置合理的调节因子,检测结果才能更加准确,参考文献[8,10]中的实验结果,定义α=2,β=1,γ=1。

查树处理文本之后,文本中相关的敏感词的词频因子、区域因子以及敏感级别都已经统计完成。提取top-k[12]个敏感词,计算文本的整体敏感度。考虑到文本长度较长的敏感词频率个数比较多,所以为了平衡文本长度的影响,这里k的取值为k=len×ε,其中,len为文本长度;ε为误差系数。

(1)初始化i=0,获取文本长度len,初始化k=len×ε;

(2)建立一个有k个节点的堆,每个节点值初始化为0,堆顶节点为root;

(7)重新调整堆为最小顶点堆,即root仍然为堆中最小值;

(8)IF++i＜n

(9)转步骤(4)处理;

(10)最后通过式(3),取堆的所有k个节点值计算出文本的权重W:

文本的最终敏感度值W由式(3)计算得来,定义θ为文本敏感度阈值,如果W≥θ则表示此文本为敏感文本,若W＜θ,则表明此文本非敏感文本。对上面算法的时间复杂度进行分析:建堆的时间复杂度为O(k);遍历所有n个敏感词,调整堆的时间为O(nlogk)。总的复杂度为O(nlogk)。

4 实验和性能分析

采用C语言程序实现,实验环境为内存1.0 GB、硬盘250 GB、操作系统为Windows7的主机。由于算法中有多个待定参数,因此采用交叉验证的方式。从网络上下载200篇网页文档,其中60篇新浪网的普通新闻报道,60篇健康教育网页,另外80篇包括计算机病毒相关等贴吧网页。选择的这3类中新闻报道类相对较正规,偏向非敏感;健康教育类属于带有敏感词而非敏感的文本,属于非敏感与待审查之间;第3类写作比较自由,内容偏敏感文本,并且存在干扰因子。从3类文档中各抽取一半即100篇作为训练集,剩余100篇为验证集。针对参数ε,θ,通过训练集实验,实验中的敏感词库,是由网络上下载并整理的2 000个敏感词,包含了现在网站管理使用的绝大多数的敏感词汇,并手工给所有敏感词汇标记了敏感级别。当ε=0.01,θ=4.85时,SWDT-IFA算法能取得最好的结果。

利用训练集实验得出的经验值,用SWDT-IFA算法和SAFE算法分别对100篇验证集文本进行过滤,从查准率和查全率以及过滤效率对2个算法作了分析。选择文献[5]中的SAFE算法进行比较,因为SAFE算法是当前执行效率和准确率都较高的,并且同样是通过数据流形式处理文本,不依赖字典。

4.1 算法的查准率和查全率

首先考察算法的查全率和查准率:

SWDT-IFA算法在提高查准和查全率方面除了考虑敏感词频、区域信息外,增加了对敏感词级别的综合计算,这对于处理带有敏感词的正常健康教育类信息的准确过滤非常关键;并且对于停用词的预处理,以及敏感词决策树中带拼音的数据结构匹配模式,使得SWDT-IFA算法具有较强的抗干扰能力,能够处理有较多干扰因子的文本。

经过实验,SWDT-IFA和SAFE算法的查全率与查准率结果分别如表1和表2所示。由表1可以看出,SWDT-IFA算法的查全率和查准率比SAFE高,其中查准率在新闻报道和计算机病毒类都是100%,只有健康教育类有一篇错误过滤。经分析,是由于错误过滤的文本包含的敏感词级别属于二级的较多,而且出现频率高,并且标题中也有敏感词出现,以至于最后计算敏感度值偏高。由表2可以看出,SAFE对于形式比较正规的新闻报道类,查全率与查准率与SWDT-IFA一致都是93.75%,100%,而对于容易引起误判的健康教育类,以及具有干扰因子较多的计算机病毒类,SAFE的查全率和查准率就比较低,这是由于SAFE算法只考虑了敏感词的频率和区域信息,并且对人为的有意干扰没有进行处理。

表1 SWDT-IFA算法处理结果

表2 SAFE算法处理结果

4.2 算法效率

SWDT-IFA算法采用不依赖词典分词而是直接与敏感词库匹配的方式;并且采用决策树模式对数据匹配进行分流;对预处理过的文本流只需遍历一次即可得出文本敏感度,总体算法时间复杂度低,执行效率高。需要说明的是,SWDT-IFA构建敏感词决策树的时间并没有算在内,因为敏感词决策树只需要构建一次,就可以处理所有文本。SAFE算法虽然也不依赖词典分词,但是SAFE算法需要一次对所有敏感词进行匹配,并且需要多次遍历文本过滤,算法时间复杂度较高,执行效率较低。

针对效率问题对SWDT-IFA和SAFE算法做了实验,结果如图2所示,可以看出SWDT-IFA具有较高的执行效率。对于平均长度为4.5千字的内容, SAFE算法平均处理时间为42 ms,SWDT-IFA算法只需要30 ms,效率提升了28.6%。并且由图2的走势可以看出,当文本长度越长,SWDT-IFA执行时间增长比SAFE增长慢。这说明SWDT-IFA在处理长度越长的文本上比SAFE优势更加明显。

图2 SWDT-IFA和SAFE算法过滤时间对比

4.3 SWDT-IFA算法复杂度分析

针对时空复杂性进行分析,SWDT-IFA算法主要分为两部分,即建树和查树。对于建树算法,复杂度为属性个数和结点数之积的线性函数。由于叶节点中存储较多属性,因此会占用较多空间,不过构建决策树是在前期进行,对敏感文本过滤的实时效率影响不大。搜索算法的时间复杂度为O(n×m),n为文本长度,m实际上是树的深度,最坏情况下为O(n×mMAX)。综合考虑查准率、查全率以及快速的处理速率,SWDT-IFA算法执行效率更高,适合实时过滤敏感文本。

5 结束语

针对当前敏感文本过滤算法的要求,本文提出一种SWDT-IFA算法,首先将带有敏感级别的敏感词构建成分流的决策树;然后把经过预处理的文本通过检索敏感词决策树,记录规则信息;最后通过加权公式计算文本敏感度,以达到文本敏感检测目的。实验结果表明,SWDT-IFA算法的查准率和查全率都达到了90%以上,并且执行时间也符合实时性要求。下一步的工作包括:改善拆分词干扰算法的解决方案以及敏感词决策树的结构,以提高检索效率。

[1] 张 坤,徐安凤.网络环境下有害信息的识别与过滤技术[J].电脑知识与技术,2009,5(9):2099-2100.

[2] 李宝林,张翼英,兰 芸.用关联分析技术识别不良信息特征项的新方法[J].计算机工程与应用,2003,39 (28):39-41.

[3] 冯 颖.网络舆情敏感话题发现平台的研究[D].北京:北京交通大学,2009.

[4] Wu Ou,Hu Wweiming.Web Sensitive Text Filtering by Combining Semantics and Statistics[C]//Proc.of IEEE NLP-KE'05.[S.1.]:IEEE Press,2005:215-259.

[5] 段 磊,唐常杰,左 劫,等.Web实时环境两级过滤中文文本内容自学习算法[J].计算机科学与探索, 2011,5(8):695-706.

[6] 彭浩林.基于内容的敏感信息过滤系统研究[D].武汉:武汉科技大学,2011.

[7] 华秀丽,朱巧明,李培峰.语义分析与词频统计相结合的中文文本相似度量方法研究[J].计算机应用研究, 2012,29(3):833-836.

[8] 郑家恒,卢娇丽.关键词抽取方法的研究[J].计算机工程,2005,31(18):194-196.

[9] 张雪英,Krause J.中文文本关键词自动抽取方法研究[J].情报学报,2008,27(4):512-520.

[10] 索红光,刘玉树,曹淑英.一种基于词汇链的关键词抽取方法[J].中文信息学报,2006,20(6):25-30.

[11] 韩客松,王永成.一种用于主题提取的非线性加权方法[J].情报学报,2000,19(6):650-653.

[12] Metwally A,AgrawalD,AbbadiA E.Efficient Computation of Frequent and Top-k Elements in Data Streams[C]//Proc.of the 10th International Conference on Database Theory.Berlin,Germany:Springer Verlag, 2005:398-441.

编辑 索书志

Information Filtering Algorithm of Text Content-based Sensitive Words Decision Tree

DENG Yi-guia,WU Yu-yingb
(a.Information and Campus Network Management Center;
b.School of Computer Science,Chongqing University,Chongqing 400030,China)

With the development of Internet,many negative effects come out as the exponential growth of various information resources,which means that a more secure and healthy network environment should be constructed right now. In order to solve this problem,this paper proposes a Sensitive Word Decision Tree for Information Filtering Algorithm (SWDT-IFA)for content-based Web pages.The algorithm takes no consideration of dictionary and word segmentation, builds the foundation on the sensitive words decision tree,lets the web text retrieval decision tree in form of data stream, records word frequency,regional information and sensitive level,and calculates the sensitive degree of the text to filter the sensitivity.Experimental results show that the SWDT-IFA algorithm has precision ratio and recall ratio,and low time complexity which can require the real-time demand of network environment.

text filtering;sensitive level;decision tree;distributary;word frequency

1000-3428(2014)09-0300-05

A

TP393

10.3969/j.issn.1000-3428.2014.09.060

邓一贵(1971-),男,高级工程师、博士,主研方向:信息安全;伍玉英,硕士研究生。

2013-08-21

2013-10-16E-mail:dengyg@cqu.edu.cn