鄧一貴,伍玉英

(重慶大學a.信息與網絡管理中心;b.計算機學院,重慶400030)

;

基于文本內容的敏感詞決策樹信息過濾算法

鄧一貴a,伍玉英b

(重慶大學a.信息與網絡管理中心;b.計算機學院,重慶400030)

隨著互聯(lián)網的高速發(fā)展,各種各樣的信息資源呈指數(shù)級增長,隨之出現(xiàn)許多負面影響,需要構建一個安全健康的網絡環(huán)境。為此,提出針對網頁文本內容的敏感信息過濾算法(SWDT-IFA)。該算法不依賴詞典與分詞,通過構建敏感詞決策樹,將網頁文本內容以數(shù)據流形式檢索決策樹,記錄敏感詞詞頻、區(qū)域信息以及敏感詞級別,計算文本整體敏感度,過濾敏感文本。實驗結果表明,SWDT-IFA算法具有較高的查準率和查全率,且執(zhí)行時間能夠滿足當前網絡環(huán)境的實時性要求。

文本過濾;敏感級別;決策樹;分流;詞頻

1 概述

隨著互聯(lián)網時代的到來,海量網絡信息資源使得人們獲取信息、生活交流、購物理財?shù)茸兊迷絹碓椒奖憧旖?。但是在人們獲得便利的同時,各種色情、暴力、反動、迷信等非法信息也接踵而至,給人們尤其是青少年帶來了巨大的危害,也給社會帶來了諸多不良影響。對此,從事信息安全的研究人員做了多方面研究,提出多種內容過濾技術。

針對Web上大量的網頁文本內容,本文利用決策樹分流特性提出了敏感詞決策樹信息過濾算法SWDT-IFA。該算法基于敏感詞庫,通過構建敏感詞決策樹,以數(shù)據流形式處理網頁文本內容,綜合考慮區(qū)域、詞頻、敏感詞級別三大要素,最終給出候選敏感詞權重,計算文本整體敏感度,實現(xiàn)敏感文本檢測。

2 問題描述及相關工作

定義1(敏感詞) 是指帶有敏感政治傾向(或反執(zhí)政黨傾向)、暴力傾向、不健康色彩的詞或不文明語。但是也有的網站根據自身實際情況,設定一些只適用于本網站的特殊敏感詞。敏感詞設定功能在貼吧或論壇中都被廣泛應用。

經相關研究,目前敏感信息過濾技術主要有以下4個需要解決的關鍵問題:

(1)人工干擾[1-2]。為了逃避關鍵詞匹配過濾,敏感信息發(fā)布者通常會采取多種方式來逃避。包括在敏感詞中間夾雜無意義的符號,如法&輪&功;將敏感詞進行拆分,如三去車侖工力;用拼音代替敏感詞,如fa lun gong;或者將前述幾種方式結合,如法lun功等。對于這些復雜的組合但又不影響人閱讀的方式,傳統(tǒng)的文本過濾算法是無法解決的。

(2)準確性。部分在敏感網頁上出現(xiàn)的敏感詞,很多時候也會出現(xiàn)在健康教育類的網頁中。實際上不應當將這些正常的教育網頁歸類到敏感信息中。

(3)分詞障礙[3]。網絡環(huán)境中新詞、音譯詞大量出現(xiàn),而中文文本又沒有顯示詞邊界,利用人工詞典分詞難以識別詞典未包含的詞,而且人工詞典的更新和維護費時費力。

(4)時空效率?，F(xiàn)在網絡上的資源呈指數(shù)級增長,并且很多網頁還在不定時的動態(tài)更新,這就要求敏感信息過濾算法必須滿足時效性,以及海量的處理需求。這對時空效率的要求是必然的。

對于人工干擾問題,參考文獻中的多數(shù)算法僅能處理夾雜特殊符號的敏感詞,而對于拼音或者拆分詞卻無能為力。在SWDT-IFA中,采取了多種方式解決干擾問題:首先通過對文本停用詞預處理文本,解決惡意夾雜無意義符號的敏感詞問題;敏感詞決策樹同時兼具判斷拼音的部分,對于夾雜拼音的敏感詞也無從逃避;而對于拆分字,目前本算法是采用增加敏感詞庫詞匯的方式。

針對準確性,文獻[4]提出了針對準確檢測敏感信息的解決方案,通過構建由顯示,隱藏以及邏輯3種關鍵詞構成的CNN-like詞網對文本進行分析處理。該算法識別敏感信息文本的準確率較高,但是CNN-like需要人工去構建詞與詞之間的關聯(lián),而且構建原理和檢測算法也比較復雜,對于敏感詞遞增的網絡環(huán)境很難維護。文獻[5]提出了基于自學習的兩級過濾算法,在不依賴詞典的情況下能夠進行自學習,快速地處理文本,但是該算法在第一級主題字過濾時,有限的計數(shù)器就會被出現(xiàn)頻率較多的敏感信息無關的字占用,以至于影響第二級過濾的準確性。SWDT-IFA在計算敏感詞權重時,增加了敏感詞級別因子:將類似于既出現(xiàn)在健康科普網站,又出現(xiàn)在敏感網站的敏感詞級別降低,提高只會出現(xiàn)在非法網站敏感詞級別,提升網頁檢測準確率。

目前許多敏感信息過濾算法都效仿文本主題提取技術[5-6],先對文本進行分詞,提取關鍵詞,再進行敏感詞匹配,但是實際上敏感信息過濾與主題提取的側重點差別較大。文本主題需要提取可以描述文本主旨的詞語或者語句,是未知的,所以需要統(tǒng)計全文重點出現(xiàn)的詞語;而敏感信息過濾需要找出的敏感信息是用戶自定義的,已知的,數(shù)量在可控范圍內,比WORD NET[7-8]要小得多。并且敏感信息發(fā)布者很有可能比較隱晦,不會大篇幅高頻率地在文本中出現(xiàn)敏感詞,利用詞典提取主題詞來過濾敏感信息的算法準確率并不高。所以,SWDT-IFA算法不依靠詞典,直接將預處理過的文本與敏感詞庫中的詞相匹配。

為了提高時空效率,SWDT-IFA算法將敏感詞庫中的詞按照一定分類規(guī)則構建成了一棵敏感詞決策樹,提高文本檢索時的匹配時效;并且決策樹中敏感詞的存儲方式非常節(jié)約空間。

3 SWDT-IFA算法設計

算法整體思想如下:(1)將文本進行去停用詞等預處理;(2)將敏感詞庫通過敏感詞決策樹構建算法建立成一棵分流樹,以達到文本匹配過程的分流的作用,提高時空效率;在前2步的基礎上,將預處理過的文本,以文本數(shù)據流方式通過檢索敏感詞決策樹,記錄文本中對應敏感詞的頻率和區(qū)域信息; (3)通過特殊計算公式,得出文本整體敏感度,將對應網頁劃分為敏感、非敏感網頁。

3.1 文本預處理

首先需要對網頁文本進行預處理[9],去除HTML標記,停用詞過濾,以及記錄文本區(qū)域信息,得到待處理文本。這里停用詞定義為不能反映主題的功能詞以及標點符號。例如:“的”、“地”、“得”之類的助詞,以及像“然而”、“因此”等只能反映句子語法結構的詞語,在敏感詞過濾中,它們的出現(xiàn)頻率較高,不屬于敏感信息,還會影響敏感詞檢索效率,有必要將其濾除。而對所有無意義標點符號的濾除,解決了發(fā)布敏感信息者對敏感詞過濾的干擾問題之一:在敏感詞之間夾雜無意義符號。

3.2 敏感詞決策樹構建算法

算法通過對敏感詞庫中的詞,按第一個字的拼音首字母進行分類,首字母都為A的“安眠藥”、“安樂死”、“愛情”等為同一類。首字母同類的詞再進行同字聚類,如“安眠藥”、“安樂死”,這里對于這2個詞,“安”字只存儲一次,這種結構在敏感詞較多時,能夠節(jié)約空間。在存儲漢字的同時,將該漢字的拼音也存儲起來,當遇到純拼音或者拼音與漢字搭配的敏感詞時,算法也同樣能夠將其檢測出來,如:“安le死”,“zuo e”。

建樹算法的輸入是敏感詞庫,每個敏感詞都帶有用戶自定義的敏感因子,如:敏感詞庫Aford={{安眠藥,3},{安樂死,3},{愛情,1},…,{糟蹋,2},{作惡,2}},輸出一棵決策樹,如圖1所示。

圖1 敏感詞決策樹

定義 2 敏感詞庫Aford={a0,a1,…,ai,…,an-1},(0≤i＜n),n為敏感詞個數(shù),ai表示敏感詞;ai={ai,0,…,ai,j,…,ai,m-1},(0≤j＜m),aij表示第i個敏感詞的第j個敏感字,m表示敏感詞長度。

算法如下:

(1)初始化i=0,j=0,k=0,k記錄孩子節(jié)點序號;

(2)輸入敏感詞ai,獲取其中文長度為m,并提取首字母LetterS;

(3)進入S子樹查詢,將aij與S的第k個孩子節(jié)點childk比較;

(5)否則,若aij≠childk節(jié)點值,查詢childk的兄弟節(jié)點是否為空;

(6)若childk兄弟節(jié)點為空,創(chuàng)建新節(jié)點childk+1,值為aij,記錄aij的拼音,j++;

(8)否則,若childk兄弟節(jié)點不為空,k++,返回步驟(2),處理下一個敏感詞;

(9)算法結束。

本文算法構建的敏感詞決策樹深度為敏感詞庫中最長敏感詞的長度,一般≤6。樹中每個節(jié)點都存儲了敏感字以及其對應的拼音,葉節(jié)點還記錄了敏感詞的頻率、區(qū)域信息、敏感級別,并且將各個詞的頻率和區(qū)域因子都進行了初始化。

3.3 查找樹處理文本

定義3 文本流Btext={b0,b1,…,bi,…,bn–1}, (0≤i＜n),其中,bi表示文本中的字符;n為文本長度,在這里的字符定義為一個漢字或者一串沒有空格間斷的英文字符,以便區(qū)分檢索決策樹中的中文字和拼音。

算法如下:

(1)初始化i=0,k=0,k用于記錄第一個進入分支的字符序列號;

(2)輸入bi,k=i,j=0,判斷bi為英文字符還是中文字符,如果是中文字符需要提取首字母s,英文直接獲取;

(3)將bi與S的孩子childj相匹配;

(4)若bi==childj節(jié)點值,i++(若i≥n,則算法結束)

(5)若bi≠childj值,查詢childj兄弟節(jié)點是否為空;

(6)若兄弟節(jié)點不為空,則j++,轉步驟(3)處理;

;

(8)算法結束。

在3.1節(jié)、3.2節(jié)處理基礎上,本文算法輸入預處理過的文本,以數(shù)據流形式檢測文本中所含有的敏感詞,并記錄其頻率和區(qū)域信息以提供文本最后的敏感度計算。

3.4 文本敏感度計算

算法借鑒文獻[8,10]中提取關鍵詞采用的對每個詞的詞頻因子、位置因子的加權計算方式,詞頻因子frei的計算方式為:

其中,fi為i的詞頻,再加上敏感詞級別因子,最終對敏感詞的權值采用下式:

其中,weighti表示敏感詞匯i的權值;loci表示詞匯i的區(qū)域因子,參考文獻[6,11],當詞匯出現(xiàn)在標題中時loci=5,否則loci=1;levi表示敏感詞級別因子,一般地,敏感詞分3個級別,絕對禁止levi=3,一般levi=2,需要審核levi=1,這3個級別由人工劃分。α,β,γ都是調節(jié)因子,需要設置合理的調節(jié)因子,檢測結果才能更加準確,參考文獻[8,10]中的實驗結果,定義α=2,β=1,γ=1。

查樹處理文本之后,文本中相關的敏感詞的詞頻因子、區(qū)域因子以及敏感級別都已經統(tǒng)計完成。提取top-k[12]個敏感詞,計算文本的整體敏感度?？紤]到文本長度較長的敏感詞頻率個數(shù)比較多,所以為了平衡文本長度的影響,這里k的取值為k=len×ε,其中,len為文本長度;ε為誤差系數(shù)。

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

(2)建立一個有k個節(jié)點的堆,每個節(jié)點值初始化為0,堆頂節(jié)點為root;

(7)重新調整堆為最小頂點堆,即root仍然為堆中最小值;

(8)IF++i＜n

(9)轉步驟(4)處理;

(10)最后通過式(3),取堆的所有k個節(jié)點值計算出文本的權重W:

文本的最終敏感度值W由式(3)計算得來,定義θ為文本敏感度閾值,如果W≥θ則表示此文本為敏感文本,若W＜θ,則表明此文本非敏感文本。對上面算法的時間復雜度進行分析:建堆的時間復雜度為O(k);遍歷所有n個敏感詞,調整堆的時間為O(nlogk)。總的復雜度為O(nlogk)。

4 實驗和性能分析

采用C語言程序實現(xiàn),實驗環(huán)境為內存1.0 GB、硬盤250 GB、操作系統(tǒng)為Windows7的主機。由于算法中有多個待定參數(shù),因此采用交叉驗證的方式。從網絡上下載200篇網頁文檔,其中60篇新浪網的普通新聞報道,60篇健康教育網頁,另外80篇包括計算機病毒相關等貼吧網頁。選擇的這3類中新聞報道類相對較正規(guī),偏向非敏感;健康教育類屬于帶有敏感詞而非敏感的文本,屬于非敏感與待審查之間;第3類寫作比較自由,內容偏敏感文本,并且存在干擾因子。從3類文檔中各抽取一半即100篇作為訓練集,剩余100篇為驗證集。針對參數(shù)ε,θ,通過訓練集實驗,實驗中的敏感詞庫,是由網絡上下載并整理的2 000個敏感詞,包含了現(xiàn)在網站管理使用的絕大多數(shù)的敏感詞匯,并手工給所有敏感詞匯標記了敏感級別。當ε=0.01,θ=4.85時,SWDT-IFA算法能取得最好的結果。

利用訓練集實驗得出的經驗值,用SWDT-IFA算法和SAFE算法分別對100篇驗證集文本進行過濾,從查準率和查全率以及過濾效率對2個算法作了分析。選擇文獻[5]中的SAFE算法進行比較,因為SAFE算法是當前執(zhí)行效率和準確率都較高的,并且同樣是通過數(shù)據流形式處理文本,不依賴字典。

4.1 算法的查準率和查全率

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

SWDT-IFA算法在提高查準和查全率方面除了考慮敏感詞頻、區(qū)域信息外,增加了對敏感詞級別的綜合計算,這對于處理帶有敏感詞的正常健康教育類信息的準確過濾非常關鍵;并且對于停用詞的預處理,以及敏感詞決策樹中帶拼音的數(shù)據結構匹配模式,使得SWDT-IFA算法具有較強的抗干擾能力,能夠處理有較多干擾因子的文本。

經過實驗,SWDT-IFA和SAFE算法的查全率與查準率結果分別如表1和表2所示。由表1可以看出,SWDT-IFA算法的查全率和查準率比SAFE高,其中查準率在新聞報道和計算機病毒類都是100%,只有健康教育類有一篇錯誤過濾。經分析,是由于錯誤過濾的文本包含的敏感詞級別屬于二級的較多,而且出現(xiàn)頻率高,并且標題中也有敏感詞出現(xiàn),以至于最后計算敏感度值偏高。由表2可以看出,SAFE對于形式比較正規(guī)的新聞報道類,查全率與查準率與SWDT-IFA一致都是93.75%,100%,而對于容易引起誤判的健康教育類,以及具有干擾因子較多的計算機病毒類,SAFE的查全率和查準率就比較低,這是由于SAFE算法只考慮了敏感詞的頻率和區(qū)域信息,并且對人為的有意干擾沒有進行處理。

表1 SWDT-IFA算法處理結果

表2 SAFE算法處理結果

4.2 算法效率

SWDT-IFA算法采用不依賴詞典分詞而是直接與敏感詞庫匹配的方式;并且采用決策樹模式對數(shù)據匹配進行分流;對預處理過的文本流只需遍歷一次即可得出文本敏感度,總體算法時間復雜度低,執(zhí)行效率高。需要說明的是,SWDT-IFA構建敏感詞決策樹的時間并沒有算在內,因為敏感詞決策樹只需要構建一次,就可以處理所有文本。SAFE算法雖然也不依賴詞典分詞,但是SAFE算法需要一次對所有敏感詞進行匹配,并且需要多次遍歷文本過濾,算法時間復雜度較高,執(zhí)行效率較低。

針對效率問題對SWDT-IFA和SAFE算法做了實驗,結果如圖2所示,可以看出SWDT-IFA具有較高的執(zhí)行效率。對于平均長度為4.5千字的內容, SAFE算法平均處理時間為42 ms,SWDT-IFA算法只需要30 ms,效率提升了28.6%。并且由圖2的走勢可以看出,當文本長度越長,SWDT-IFA執(zhí)行時間增長比SAFE增長慢。這說明SWDT-IFA在處理長度越長的文本上比SAFE優(yōu)勢更加明顯。

圖2 SWDT-IFA和SAFE算法過濾時間對比

4.3 SWDT-IFA算法復雜度分析

針對時空復雜性進行分析,SWDT-IFA算法主要分為兩部分,即建樹和查樹。對于建樹算法,復雜度為屬性個數(shù)和結點數(shù)之積的線性函數(shù)。由于葉節(jié)點中存儲較多屬性,因此會占用較多空間,不過構建決策樹是在前期進行,對敏感文本過濾的實時效率影響不大。搜索算法的時間復雜度為O(n×m),n為文本長度,m實際上是樹的深度,最壞情況下為O(n×mMAX)。綜合考慮查準率、查全率以及快速的處理速率,SWDT-IFA算法執(zhí)行效率更高,適合實時過濾敏感文本。

5 結束語

針對當前敏感文本過濾算法的要求,本文提出一種SWDT-IFA算法,首先將帶有敏感級別的敏感詞構建成分流的決策樹;然后把經過預處理的文本通過檢索敏感詞決策樹,記錄規(guī)則信息;最后通過加權公式計算文本敏感度,以達到文本敏感檢測目的。實驗結果表明,SWDT-IFA算法的查準率和查全率都達到了90%以上,并且執(zhí)行時間也符合實時性要求。下一步的工作包括:改善拆分詞干擾算法的解決方案以及敏感詞決策樹的結構,以提高檢索效率。

[1] 張 坤,徐安鳳.網絡環(huán)境下有害信息的識別與過濾技術[J].電腦知識與技術,2009,5(9):2099-2100.

[2] 李寶林,張翼英,蘭 蕓.用關聯(lián)分析技術識別不良信息特征項的新方法[J].計算機工程與應用,2003,39 (28):39-41.

[3] 馮 穎.網絡輿情敏感話題發(fā)現(xiàn)平臺的研究[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實時環(huán)境兩級過濾中文文本內容自學習算法[J].計算機科學與探索, 2011,5(8):695-706.

[6] 彭浩林.基于內容的敏感信息過濾系統(tǒng)研究[D].武漢:武漢科技大學,2011.

[7] 華秀麗,朱巧明,李培峰.語義分析與詞頻統(tǒng)計相結合的中文文本相似度量方法研究[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