基于支持向量機與余弦夾角法的中文網(wǎng)頁過濾的研究與設(shè)計

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

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

1 引言

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

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

表1 分詞方法對比

根據(jù)表1對各種分詞方法的比較,采用由中國科學(xué)院張華平教授等開發(fā)的開放源碼分詞系統(tǒng)ICTCLAS,在其基礎(chǔ)上添加去禁用詞模塊,通過實驗在windowsXP系統(tǒng)上使用C++語言實現(xiàn)。

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

表2 特征評估函數(shù)對比

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

2 基于SVM與余弦夾角法的網(wǎng)頁文本過濾流程

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

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

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

3 基于SVM的網(wǎng)頁文本分類

3.1 去禁用詞的ICTCLAS分詞法

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

(1)輸入中文字串L;

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

(3)Begin;

(4)While L≠Φ;

(5)flag=isInStopWordList();

(6)If(flag==ture)

(7)delete();

(8)End.

原始中文字串“一朵朵的牡丹很漂亮”用原始ICTCLAS分詞之后變?yōu)椋?/p>

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

通過去禁用詞之后分詞結(jié)果為：

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

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

3.2 特征處理

經(jīng)過預(yù)處理分詞后得到的關(guān)鍵詞集合就是特征集。頻率統(tǒng)計、降維技術(shù)和特征權(quán)重等特征處理技術(shù)是對特征集中的特征進行頻率統(tǒng)計,然后去除弱關(guān)聯(lián)詞,保留強關(guān)聯(lián)詞構(gòu)成用于學(xué)習(xí)的特征集,給這些特征賦予不同的權(quán)重,表示特征對文本的重要程度。

3.2.1 改進的TF-IDF統(tǒng)計方法

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

圖1 基于SVM和余弦夾角法的網(wǎng)頁過濾流程圖

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

3.2.2 基于DF和MI的特征提取

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

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

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

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

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

3.3 向量空間模型表示文本

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

3.4 SVM分類實現(xiàn)

步驟1：確定訓(xùn)練集

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

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

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

步驟2：選擇核函數(shù)以及懲罰因子

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

步驟3：構(gòu)造、求解凸二次規(guī)劃

步驟4：確定 b

步驟5：構(gòu)造決策函數(shù)

4 基于余弦夾角法的網(wǎng)頁過濾

針對色情等重點關(guān)注類采用網(wǎng)頁結(jié)構(gòu)相似度計算方法進行再次驗證。以色情類為例,具體實現(xiàn)如下：

步驟1：提取色情網(wǎng)頁的結(jié)構(gòu)特征

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

步驟2：頁面相似度計算

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

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

wjk表示第k個特征詞在文本j中對應(yīng)的權(quán)值。

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

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

5 實驗結(jié)果及分析

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

表3 一般SVM分類

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

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

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

表5 準確率對比

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

6 結(jié)束語

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

[1]屈培,葛秦.Nutch-0.8.1中二分法中文分詞的實現(xiàn)[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]盧增祥,李衍達.交互學(xué)習(xí)算法及其在文本信息過濾中的應(yīng)用[J].清華大學(xué)學(xué)報,1999,39(7)：93-97.

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

[6]鄭德權(quán),張迪.Blog網(wǎng)頁分類與識別技術(shù)研究[J].通信學(xué)報,2007,28(12)：28-32.

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