Web文本分類中的反作弊研究

【摘 要】根據(jù)用戶定義的某一主題，在爬蟲算法中加入反作弊思想后，用爬蟲算法遍歷網(wǎng)絡(luò)，收集與主題相關(guān)的頁面進(jìn)行智能分析，同時(shí)將文本過濾轉(zhuǎn)化為文本分類，為了增強(qiáng)通用性，在算法中加入了松弛變量，最后在NB分類個(gè)器上驗(yàn)證算法的性能。試驗(yàn)表明，分類精度達(dá)到將近90%。

【關(guān)鍵詞】主題爬蟲；文本分類；反作弊；松弛變量

由于Web用戶的信息檢索需求是千變?nèi)f化的，這樣對(duì)于不同領(lǐng)域就需要建立相應(yīng)的主題搜索引擎，要求的主題搜索引擎數(shù)量將非常多，而且隨著人類社會(huì)知識(shí)更新速度的不斷加劇，這個(gè)問題將更嚴(yán)重；另外，用戶檢索需求所屬的領(lǐng)域有時(shí)是難以確定，造成用戶無所適從。從而導(dǎo)致主題爬蟲技術(shù)面臨以下幾個(gè)問題：（1）查準(zhǔn)率不高；（2）查全率低；（3）查詢主題不易精確表達(dá)，而且往往帶有欺騙性，也很大程度影響了查準(zhǔn)率和查全率。本文針對(duì)WebSpam算法，在其中加入反作弊方程，提高了主題爬蟲的效率，在一定程度上滿足了用戶的特定檢索要求。

1.基于反作弊技術(shù)的主題爬蟲算法

1.1 主題爬蟲簡介

主題爬蟲（Topical Crawler，F(xiàn)ocused Crawler or Topic.driven crawler）[1-3]，是一個(gè)智能化的Web下載系統(tǒng)，它按照用戶給定的主題，自動(dòng)在Web上遍歷，將與主題相關(guān)的頁面下載下來，滿足用戶對(duì)特定主題的檢索需求。

1.2 算法描述

首先訓(xùn)練一個(gè)線性分類器，分類器采用支持向量機(jī)（Support Vector Machine，SVM）來訓(xùn)練，由：

（1-1）

來定義，為參數(shù)，用來權(quán)衡算法的適應(yīng)性和復(fù)雜性。在這里，使用表示分類樣本的損耗，作為參數(shù)調(diào)整項(xiàng)，補(bǔ)充分類樣本。

由于超鏈接可以用有向圖表示，邊集為E。超鏈接并不是隨機(jī)出現(xiàn)的，通過分析可以發(fā)現(xiàn)，超鏈接所指向的源結(jié)點(diǎn)和目標(biāo)結(jié)點(diǎn)一般是主題相似的?；谝陨习l(fā)現(xiàn)，將上面的公式1-1擴(kuò)充，加入新的部分：

（1-2）

其中，為有向邊的權(quán)值，上述公式的前兩部分為線性SVM的描述，第三部分為超鏈接特性的表述，矩陣用來表述有向圖的結(jié)構(gòu)。公式1-2所描述的理論[4][5]已經(jīng)被實(shí)現(xiàn)，的值可采用，表示由超鏈接聯(lián)系的源地址和目標(biāo)地址有相似的預(yù)測(cè)值。與M.Belkin[5]等人相反，本文采用的圖結(jié)構(gòu)是專門面向Web Spam分類的，使用有向圖來進(jìn)行分類時(shí)，由于帶有Spam的頁面會(huì)制造大量鏈接指向真正的頁面，但相反的鏈接卻不存在。即可用來代替公式1-2。

1.3 添加松弛變量

通過分析，上面公式中的特征向量之間的距離可能不夠松弛，同時(shí)，像這樣的線性分類器也是不夠靈活的。根據(jù)文獻(xiàn)[5]中的論述，可以為每個(gè)結(jié)點(diǎn)引入?yún)?shù)，公式變?yōu)椋??？梢钥醋鏊沙谧兞?，用于提高分類器的適應(yīng)性。最后模型可以表述為：

（1-3）

2.反作弊算法試驗(yàn)分析

公式1-3中三個(gè)部分分別表示結(jié)點(diǎn)特征①、Spam單向性②和松弛變量③。這三個(gè)部分在區(qū)分Spam頁面的作用不同，因此選擇不同的組合，來驗(yàn)證每個(gè)部分的重要性。

只選擇結(jié)點(diǎn)特征：只選用給定的有向圖特征來訓(xùn)練分類器，而忽略Spam單向性。在公式1-3中，進(jìn)行下列賦值=0，γ=0，這樣公式1-3直接就變成了標(biāo)準(zhǔn)線性分類器。

選擇結(jié)點(diǎn)特征與Spam單向性：同時(shí)選擇結(jié)點(diǎn)特征和Spam單向性兩個(gè)部分，而忽略松弛變量這個(gè)部分，即=0。

選擇松弛變量和Spam單向性：忽略結(jié)點(diǎn)特征這一項(xiàng)，查看分類器在無結(jié)點(diǎn)特征，僅靠松弛變量的調(diào)整和結(jié)點(diǎn)之間的超鏈接有向圖特征這兩項(xiàng)訓(xùn)練SVM分類器。

僅選擇結(jié)點(diǎn)特征和松弛變量：忽略Spam單向性這一項(xiàng)，僅靠結(jié)點(diǎn)特征和松弛變量的調(diào)整，訓(xùn)練SVM分類器，查看結(jié)點(diǎn)之間的超鏈接Spam單向性對(duì)分類效果的影響。

同時(shí)選擇3個(gè)部分：應(yīng)用改進(jìn)的Anti-spam算法訓(xùn)練分類器，通過實(shí)驗(yàn)對(duì)比查看這種方式的效果。

以上五種Anti-Spam的變種算法的結(jié)果如圖3.1所示：從圖3.1可以看出，忽略超鏈接Spam單向性，僅選擇網(wǎng)站的特征項(xiàng)分類結(jié)果大致是一樣的?；竞蚖eb Spam相當(dāng)，繼續(xù)挖掘Spam的特性，對(duì)于提高分類精確度，更好的過濾Spam頁面，具有重要意義。和現(xiàn)有的作弊算法相比，時(shí)間復(fù)雜度較高，如果分類樣本比例達(dá)到90%以上，同時(shí)考慮節(jié)點(diǎn)特征、Spam的單向性和松弛變量，分類精度將會(huì)達(dá)到90%左右，當(dāng)然只是針對(duì)Web Spam的。

3.結(jié)論

主要分析了當(dāng)前主題爬蟲存在的問題，提出了基于Web反作弊的Anti-Spam及其變種算法，Anti-Spam及其變種算法使用SVM來訓(xùn)練分類器。另外，從實(shí)驗(yàn)中可以看出，決定分類的關(guān)鍵屬性是超鏈接有向圖自身的特性，與網(wǎng)站本身的特性相關(guān)比較小。在今后的算法改進(jìn)中，應(yīng)當(dāng)注重研究網(wǎng)站之間的超鏈接特性和主題漂移[6]。當(dāng)然，通過樣本聚類比例的分析，分類精度雖然有所提高，要更好的過濾Spam頁面，需要借助于文本過濾技術(shù)。

圖3.1 五種Anti-Spam的變種算法的結(jié)果

參考文獻(xiàn)：

[1]羅剛，王振東.自己動(dòng)手寫網(wǎng)絡(luò)爬蟲[M].清華大學(xué)出版社，2010，4（第二版）：331-338.

[2]王亮.搜索引擎零距離[M].清華大學(xué)出版社，2009，6（第一版）：200-216.

[3]赫楓齡，左萬歷.利用超鏈接信息改進(jìn)網(wǎng)頁爬行器的搜索策略[J].吉林大學(xué)學(xué)報(bào)：信息科學(xué)版，2005，23（1）：59-62.

[4]高琪，張永平.超鏈接導(dǎo)向搜索算法中主題漂移的研究[J].計(jì)算機(jī)應(yīng)用，2009，29（11）：3101-3102.

[5]Lili Yan，Yingbin Wei.Research on page rank and hyperlink-Introduced Topic search in Web Structure Mining[J].IEEE express Conference Publing，ITAP2011：1015-1018.

[6]ZHAO Yan-Yan，QIN Bing，LIU Ting.Sentiment Analysis[J].Journal of Software，Science Press，2010，8：13-14.

[7]WANG Huan，WU Gang，YANG Shu.Forestry Web Yellow Page Category System Based on Text Classification[J].Computer Systems Applications，Science Press，Vol.21，No.1，

pp.21-24，2012.

[8]FENG Yong，LI Hua，ZHONG Jiang，YE Chun-Xiao.Text Classification Algorithm Based on Adaptive Chinese Word Segmentation and Proximal SVM[J].Computer Science，Chongqing branch Keqing Printing Company Limited，Vol.37，No.1，pp.252-254，2010.

基金項(xiàng)目：渭南師范學(xué)院大學(xué)生創(chuàng)新基金項(xiàng)目（項(xiàng)目編號(hào)：12XK050）。