基于支持向量機與余弦夾角法的中文網頁過濾的研究與設計

胡 迪, 陳 運, 楊義先, 陳 悅

(1.成都信息工程學院信息安全研究所,四川成都610225;2.北京郵電大學信息安全中心,北京100083)

1 引言

網頁過濾可以嵌套在基于安全網關網絡(Secure Internet Gateway,SIG)上,提供給移動、聯通等運營商。重點過濾色情、賭博、毒品、低俗等對青少年危害較大的一些網頁。營造一個安全、綠色的上網環境。

中文網頁過濾首先要經過分詞。目前常用的分詞技術有Httpcws、Paoding、ICTCLAS[1](Institute of Computing Technology,Chinese Lexical Analysis System)等。

表1 分詞方法對比

根據表1對各種分詞方法的比較,采用由中國科學院張華平教授等開發的開放源碼分詞系統ICTCLAS,在其基礎上添加去禁用詞模塊,通過實驗在windowsXP系統上使用C++語言實現。

特征選擇是通過頻數(Document Frequency,DF)信息增益(Information Gain,IG)、互信息(Mutual Information,MI)、χ2(亦為CHI)統計等特征評估函數實現。

表2 特征評估函數對比

如表2所示各種特征評估函數都有其優缺點,根據分類對色情、毒品等類別關注度高的特點,通過DF保留到達一定次數的特征,再通過MI將DF過濾的特征將類別相關性高的特征保留的方法實現特征提取。

2 基于SVM與余弦夾角法的網頁文本過濾流程

SVM(Support Vector Machine)[2]方法適合大樣本集的分類,特別是文本分類。基于結構風險最小化原理,將原始數據集合壓縮到支持向量集合,然后用子集學習得到新知識,同時也給出由這些支持向量決定的規則。近年來不少學者對SVM在分類應用中進行不斷完善和改進。SVM主動學習策略[3]和直推式算法[4]來解決大規模語料庫消耗大量人力和時間;在SVM學習過程中加入文本的先驗知識[5]改善學習模型的泛化能力。文章采用自適應C-支持分類向量機。

哈爾濱工業大學鄭德權[6]利用基于模板匹配的相似度計算Blog網頁相似度,很好的區分blog網頁和其它網頁。文章以色情網頁為例,運用余弦夾角法過濾掉色情、毒品等對青少年危害較大的網頁。

基于SVM與余弦夾角法的網頁文本過濾是先對總庫中的URL進行判斷,如果是以文字為主采用的分類算法是支持向量機SVM。如若不是就通過基于網頁結構的余弦夾角法就是分類。具體實現如圖1所示。

3 基于SVM的網頁文本分類

3.1 去禁用詞的ICTCLAS分詞法

ICTCLAS是基于5層隱馬模型的系統。原始的中文字串根據分隔符、回車換行符進行斷句形成短句。把短句切割成不可再分割的最小語素單位即為原子分詞。原子的所有可能的組合再進行 N-最短路徑粗切分,粗切分結果通過簡單未登錄詞識別之后又進入嵌套未登錄詞中識別階段。再通過基于類的隱馬分詞和詞類的隱馬標準得到詞法分析結果。文章除原有詞庫外,添加一個禁用詞詞庫。在此系統基礎上將第4層HMM中添加去禁用詞(副詞、介詞、連詞等虛詞)功能。在程序運行初,先把原有詞庫和禁用詞詞典均加載到內存中,以提高訪問的速度。去除禁用詞算法如下：

(1)輸入中文字串L;

(2)輸出中文字串 L′;

(3)Begin;

(4)While L≠Φ;

(5)flag=isInStopWordList();

(6)If(flag==ture)

(7)delete();

(8)End.

原始中文字串“一朵朵的牡丹很漂亮”用原始ICTCLAS分詞之后變為：

一朵朵/m的/u牡丹/n很/d漂亮/a

通過去禁用詞之后分詞結果為：

一朵朵/m牡丹/n漂亮/a

這樣去除了對文本分類沒有作用的詞,降低了維度,提高分類速度。

3.2 特征處理

經過預處理分詞后得到的關鍵詞集合就是特征集。頻率統計、降維技術和特征權重等特征處理技術是對特征集中的特征進行頻率統計,然后去除弱關聯詞,保留強關聯詞構成用于學習的特征集,給這些特征賦予不同的權重,表示特征對文本的重要程度。

3.2.1 改進的TF-IDF統計方法

TF-IDF(Tenn Frequency-Inverse Document Frequency)通過突出重要特征、抑制次要特征的方法評估某特定特征對一個文件集或者語料庫中的其中一份文件的重要程度。對于Web文檔,特征詞在不同位置對文檔內容的反映程度不同,因此權重的計算方法應該體現HTML的結構特征。由于TF-IDF沒有體現出特征的位置信息。所以提出一種改進的TF-IDF方法對處于網頁不同位置的特征詞賦予不同的系數,再乘以特征詞的詞頻來提高文本表示的效果。TF-IDF權重計算公式表示為：

圖1 基于SVM和余弦夾角法的網頁過濾流程圖

式中 TFij碼是特征詞tj在文本di中的詞頻;DFj為訓練集中出現特征詞tj的文檔頻率;N為訓練集的文本總數;θ為權重系統且 0＜θ＜1,k 為特征出現位置(url、title、keywords、description、subtitle、content)。

3.2.2 基于DF和MI的特征提取

基于DF和MI的特征提取首先根據文檔頻率計算特征詞在類別中出現頻率,計算公式如(2)式所示：

其中DFt是特征詞t在類別c中出現的文檔數量;Nc是c中的文檔總數。然后設置閾值Dmin,將(2)式中計算的DF(t,c)與之比較。大于Dmin直接保留。小于Dmin再通過MI計算特征與類別之間的相關性。如(3)式所示：

其中t,c分別表示特征和類別

為了計算簡便,(3)式可轉化為：

其中N為訓練集中包含的文本總數;A是t,c同時出現的次數;B只指出現t的次數;C是只出現c的次數。最后設置閾值D′min,將(4)式中計算的 MI(t,c)值大于D′min值保留。

3.3 向量空間模型表示文本

將通過DF和MI綜合考慮提取的特征作為特征項,并賦予一定的權重。那么一個文本可以表示成 d=(w1,w2,…,wi),wi為第i個特征詞ti對應的權重。用向量空間模型VSM(Vector Space Model)表示文本。文本表示為賦予權重的特征詞的集合。即為構成特征空間的一個向量。具體表示方法為：

3.4 SVM分類實現

步驟1：確定訓練集

分類類別數已經確定,并設其值為 M(M ∈N+)。對于給定訓練集 T={(dj,Mi)}其中dj={(t1j,w1j),(t2j,w2j),…}表示第 j個文本;表示第i(i=1,2,3,…,M)個分類。需找到一個決策函數 f(dj)：dj→Mi,用以推斷任意輸入文本dj對應的分類Mi。

鄧乃揚、田英杰等認為成對分類方法以及一類對多類分類方法不適合文本分類[7]。前者需求解(M-1)?M/2個兩類問題,計算量大。后者的缺點為考慮的兩類問題往往不對稱會引起誤差。使用自適應懲罰因子C。即為懲罰因子隨訓練點的不同而不斷調節。原問題變為：

圖2 基于DF和M I的特征提取流程圖

步驟2：選擇核函數以及懲罰因子

由于文本數據具有特點不明確、數據量大等特點。而高斯函數處理數據速度快,適應新數據能力強,學習能力較強。所以本文采用高斯函數作為核函數。懲罰因子是為了平衡訓練誤差和間隔。對于較少的正類選取較大的懲罰因子C。

步驟3：構造、求解凸二次規劃

步驟4：確定 b

步驟5：構造決策函數

4 基于余弦夾角法的網頁過濾

針對色情等重點關注類采用網頁結構相似度計算方法進行再次驗證。以色情類為例,具體實現如下：

步驟1：提取色情網頁的結構特征

色情網頁有很大的相似性。這些相似性主要體現在：(1)設置風格相同或者相似;(2)采用同一類邏輯(列表或者表格)對象進行表示;(3)在頁面內容的組織上,通過相同的靜態關鍵字標識同一數據項取值。

步驟2：頁面相似度計算

運用余弦夾角法計算頁面相似度。

其中sim(di,dj)為余弦值,反映文本i與文本j的相似度,sim(di,dj)越小相似度越高;wik表示第k個特征詞在文本i中對應的權值;

wjk表示第k個特征詞在文本j中對應的權值。

步驟3：設定閾值Dsim(di,dj)

具體方法為將已經分類準確的網頁作為訓練集,得到Dsim(di,dj)T,然后再從待分類樣本中隨機抽出3/10的作為測試集不斷修正確定出

5 實驗結果及分析

在URL總庫存在情況下對已經校對正確過的10個類別(每個類別各100條URL)進行實驗。實驗過程中分別采用一般SVM方法和基于SVM與網頁結構結合的網頁過濾方法。得到結果如表3和表4所示。

表3 一般SVM分類

從表3可以看出此分類器對計算機、時尚、生活等類識別準確率較差。對色情類識別能力雖然比較高,但由于色情類是重點關注類,所以沒有達到理想效果。

表4 基于SVM和余弦夾角法分類

表4是利用基于SVM與網頁結構結合的余弦夾角方法對網頁進行識別。從表中可以看出此方法對各個類別的識別率都有提高。特別是色情網頁的識別率高達99%。

表5 準確率對比

從表5可以看出表4的方法在時尚、色情、生活這3個類比表3識別率明顯提高。而這3個類有一個共同點就是網頁結構有一部分是由很少的文字以及大量的圖片構成。所以基于SVM與網頁結構相結合的余弦夾角方法對大量圖片組成的網在頁識別率方面占有一定的優勢。

6 結束語

對Web文本分類作了較為深入的闡述和分析,實現了一種能夠很好區分色情等對青少年危害較大的網頁分類方法。在ICTCLAS系統基礎上添加去禁用詞功能,并采用DF和MI綜合考慮實現特征提取。根據色情網頁結構上相似的特點,采用SVM與網頁結構結合的余弦夾角方法進行網頁過濾,初步實驗獲得較好效果。在今后工作中,將添加語言識別功能模塊,并將其應用到毒品、犯罪等網頁分類,并不斷改進,以獲得更好的分類識別效果。

[1]屈培,葛秦.Nutch-0.8.1中二分法中文分詞的實現[J].計算機時代,2007,22(7)：9-11.

[2]Vapnik V.The Nature of Statistical Learning Theory[M].New York：Springer-Verlag,1995.

[3]Tong S,Koller D.Support vector machine active learning with application to text classification[J].Journal of Machine Learning Research,2002,2(1)：45-66.

[4]盧增祥,李衍達.交互學習算法及其在文本信息過濾中的應用[J].清華大學學報,1999,39(7)：93-97.

[5]李輝,史忠植,許卓群.運用文本領域的常識改善基于支持向量機的文本分類器性能[J].中文信息學報,2002,16(2)：7-13.

[6]鄭德權,張迪.Blog網頁分類與識別技術研究[J].通信學報,2007,28(12)：28-32.

[7]鄧乃揚,田英杰.支持向量機-理論、算法與擴展[M].北京：科學出版社,2009：189-191.