劉 陽，張化祥

（1.山東師范大學(xué) 信息科學(xué)與工程學(xué)院，山東 濟(jì)南250014；2.山東省分布式計(jì)算機(jī)軟件新技術(shù)重點(diǎn)實(shí)驗(yàn)室，山東 濟(jì)南250014）

0 引 言

信息檢索 （IR）［1］是幫助用戶找到與需求相匹配的信息。由于網(wǎng)絡(luò)包含驚人的信息，用戶通常通過搜索引擎查詢有用的網(wǎng)頁。給定一個(gè)查詢，搜索引擎可識(shí)別在網(wǎng)絡(luò)上的相關(guān)網(wǎng)頁和鏈接，一旦用戶看到相關(guān)的鏈接，可以點(diǎn)擊一個(gè)或多個(gè)鏈接以訪問頁面。研究表明［2］，80%的搜索引擎使用者查看返回結(jié)果不超過三頁，因此在搜索引擎返回結(jié)果中，排名越高帶來的利潤(rùn)越大，很多網(wǎng)頁通過欺騙搜索引擎的手段獲得較高的排名，這類網(wǎng)頁被稱為垃圾網(wǎng)頁［3］。垃圾網(wǎng)頁損害搜索引擎的聲譽(yù)，削弱了其用戶對(duì)搜索引擎的信任，檢測(cè)垃圾網(wǎng)頁已是搜索引擎面臨的重大的挑戰(zhàn)之一。

目前垃圾網(wǎng)頁的作弊方法主要分為3種：第一種是基于網(wǎng)頁內(nèi)容的作弊方法，主要作弊手段為重復(fù)重要的關(guān)鍵詞和堆砌大量不相關(guān)的關(guān)鍵詞。通過分析正常網(wǎng)頁與垃圾網(wǎng)頁的內(nèi)容特征可以檢測(cè)出基于內(nèi)容作弊的垃圾網(wǎng)頁，例如文獻(xiàn) ［4］中分析網(wǎng)頁內(nèi)容特征文本單詞數(shù)量、網(wǎng)頁標(biāo)題字?jǐn)?shù)、錨文本比例等分布信息，利用決策樹分類器進(jìn)行分類；第二種作弊方法基于網(wǎng)頁鏈接結(jié)構(gòu)，垃圾網(wǎng)頁通過添加多余的網(wǎng)頁鏈接或誤導(dǎo)其他網(wǎng)頁鏈接指向它以此欺騙搜索引擎的排序算法。PageRank算法［5，6］是著名的網(wǎng)頁排序算法，PageRank算法根據(jù)網(wǎng)頁之間互相鏈接的貢獻(xiàn)值對(duì)網(wǎng)頁進(jìn)行排名。越重要的網(wǎng)頁得分越高，排名越靠前。Wang等［7］介紹了一種新的頁面排序算法DirichletRank，解決了PageRank算法的zero－one gap問題；Caverlee等［8］利 用頁面信任得分改進(jìn)HIST算法對(duì)基于鏈接作弊的垃圾網(wǎng)頁進(jìn)行檢測(cè)；Gyongyi［9］提出了一種基于初始信任種子集合的信任傳播模式，經(jīng)過多次傳播之后每一個(gè)網(wǎng)頁產(chǎn)生一個(gè)信任值，根據(jù)信任值的大小對(duì)網(wǎng)頁排序檢測(cè)垃圾網(wǎng)頁。Jacob等［10］則使用了基于網(wǎng)絡(luò)圖的正則化對(duì)垃圾網(wǎng)頁進(jìn)行檢測(cè)；第三種作弊方法為隱藏技術(shù)，垃圾網(wǎng)頁通過隱藏垃圾句子、關(guān)鍵詞和鏈接達(dá)到作弊目的。一個(gè)簡(jiǎn)單的方法是使垃圾關(guān)鍵詞的顏色與背景色相同，垃圾網(wǎng)頁還可以為用戶和網(wǎng)絡(luò)爬蟲提供不同的HTML文件達(dá)到隱藏的目的。

基于內(nèi)容特征的垃圾網(wǎng)頁檢測(cè)方法只考慮了網(wǎng)頁的文本內(nèi)容特征，沒有考慮網(wǎng)頁的鏈接結(jié)構(gòu)，很難適應(yīng)不斷發(fā)展的網(wǎng)頁作弊技術(shù)，而基于鏈接結(jié)構(gòu)的垃圾網(wǎng)頁檢測(cè)方法則忽略了網(wǎng)頁的內(nèi)容信息，如果只考慮網(wǎng)頁的拓?fù)浣Y(jié)構(gòu)，很難檢測(cè)出那些拓?fù)浣Y(jié)構(gòu)與正常網(wǎng)頁十分相似的垃圾網(wǎng)頁。文獻(xiàn) ［11］提出將內(nèi)容特征與鏈接信息結(jié)合起來建立分類器垃圾網(wǎng)頁檢測(cè)。在文獻(xiàn) ［11］中，通過對(duì)數(shù)據(jù)集的統(tǒng)計(jì)分析，根據(jù)正常網(wǎng)頁與垃圾網(wǎng)頁內(nèi)容特征與鏈接特征分布的差異利用決策樹對(duì)垃圾網(wǎng)頁進(jìn)行檢測(cè)。對(duì)于某一特征，如果網(wǎng)頁的特征值小于閾值，決策樹將網(wǎng)頁判定為垃圾網(wǎng)頁，因此特征值小于閾值的正常網(wǎng)頁被誤判為垃圾網(wǎng)頁。為了減少將正常網(wǎng)頁誤判為垃圾網(wǎng)頁的錯(cuò)誤率，本文在分析數(shù)據(jù)集網(wǎng)頁特征分布的基礎(chǔ)上，用各種分布函數(shù)擬合網(wǎng)頁的特征分布，根據(jù)網(wǎng)頁特征值與擬合函數(shù)的差值利用決策樹檢測(cè)垃圾網(wǎng)頁。在后面的數(shù)據(jù)集網(wǎng)頁特征分析中，我們可以看到正常網(wǎng)頁的特征分布比較有規(guī)律，而垃圾網(wǎng)頁的特征分布混亂，因此用分布函數(shù)擬合之后求差值，正常網(wǎng)頁差值較小而垃圾網(wǎng)頁差值較大。

1 數(shù)據(jù)集

本文采用的數(shù)據(jù)集是由yahoo實(shí)驗(yàn)室發(fā)布的UK－2007［12］。志愿者標(biāo)注集合標(biāo)記為主機(jī)級(jí)別，其中，主機(jī)名被人工標(biāo)注為三類： “non－spam”、 “spam”、 “undecided”。標(biāo)記為主機(jī)而非單個(gè)頁面的好處是能夠獲得一個(gè)大的覆蓋范圍，這意味著樣例包含了各種各樣的垃圾網(wǎng)頁以及它們之間有用的鏈接信息。我們只選取了 “non－spam”與 “spam”作為數(shù)據(jù)集用例。標(biāo)記數(shù)據(jù)集共有5797個(gè)數(shù)據(jù)，其中spam 321個(gè)，non－spam 5476個(gè)。spam與non－spam比例為1∶17。

2 網(wǎng)頁內(nèi)容特征

2.1 文本單詞數(shù)量

網(wǎng)頁內(nèi)容與查詢關(guān)鍵詞的匹配程度通常作為網(wǎng)頁排名的一個(gè)重要因素。垃圾網(wǎng)頁堆砌大量的流行關(guān)鍵詞，因此在查詢時(shí)可以匹配上很多關(guān)鍵詞，排名就會(huì)靠前。本文統(tǒng)計(jì)了數(shù)據(jù)集中正常網(wǎng)頁與垃圾網(wǎng)頁的文本單詞數(shù)量特征分布，結(jié)果如圖1和圖2所示。

在圖1與圖2中我們可以看出垃圾網(wǎng)頁與正常網(wǎng)頁的文本單詞數(shù)量均在0－50之間所占比例最多。在圖2中，84.7%的正常網(wǎng)頁的文本單詞數(shù)量小于500，只有3.06%的正常網(wǎng)頁的文本單詞數(shù)量大于1000，而由于堆砌大量流行關(guān)鍵詞，在圖1中超過7.5%的垃圾網(wǎng)頁文本單詞數(shù)量大于1000。正常網(wǎng)頁的文本單詞數(shù)量分布在100之后近似指數(shù)分布，垃圾網(wǎng)頁分布散亂沒有規(guī)律。我們用指數(shù)分布擬合正常網(wǎng)頁的文本單詞數(shù)量，指數(shù)分布的密度函數(shù)為

式中：λ——指數(shù)分布的參數(shù)，θ——權(quán)重，控制p（x）的值。由于文本單詞數(shù)量值過大，所以將文本單詞數(shù)量x值除以1000。經(jīng)過實(shí)驗(yàn)測(cè)試，λ＝3.6，θ＝4.5時(shí)能夠很好的擬合正常網(wǎng)頁文本單詞數(shù)量分布。，由于正常網(wǎng)頁文本單詞數(shù)量分布近似指數(shù)分布，所以網(wǎng)頁比例與指數(shù)分布的差值較小，而垃圾網(wǎng)頁的文本單詞數(shù)量分布散亂，差值較大，因此我們把文本單詞數(shù)量網(wǎng)頁比例與指數(shù)分布概率密度函數(shù)的差值ω作為決策樹的一個(gè)閾值。差值計(jì)算公式為

式中：y（x）——網(wǎng)頁文本單詞數(shù)量為x時(shí)網(wǎng)頁所占的比例。

2.2 網(wǎng)頁標(biāo)題單詞數(shù)量

搜索引擎查詢結(jié)果時(shí)根據(jù)網(wǎng)頁標(biāo)題中出現(xiàn)的關(guān)鍵詞返回結(jié)果，一些搜索引擎對(duì)標(biāo)題中出現(xiàn)的查詢關(guān)鍵詞給予額外的權(quán)重，所以出現(xiàn)了網(wǎng)頁標(biāo)題中的關(guān)鍵詞堆砌。正常網(wǎng)頁標(biāo)題單詞數(shù)量分布與垃圾網(wǎng)頁標(biāo)題單詞數(shù)量分布如圖3和圖4所示。

由圖3和圖4可知，正常網(wǎng)頁與垃圾網(wǎng)頁的標(biāo)題字?jǐn)?shù)為2時(shí)所占比例最多，網(wǎng)頁所占比例均為13.7%，正常網(wǎng)頁中標(biāo)題字?jǐn)?shù)大于15的網(wǎng)頁所占比例為4.10%，而垃圾網(wǎng)頁為了獲得較高的排名，在網(wǎng)頁標(biāo)題中惡意填充或者大量重復(fù)目標(biāo)關(guān)鍵詞，網(wǎng)頁標(biāo)題字?jǐn)?shù)大于15的網(wǎng)頁所占比例高達(dá)10.40%。正常網(wǎng)頁標(biāo)題字?jǐn)?shù)大于2時(shí)，其網(wǎng)頁比例分布近似正態(tài)分布，而垃圾網(wǎng)頁的網(wǎng)頁標(biāo)題分布沒有規(guī)律。正態(tài)分布的概率密度函數(shù)為

式中：μ——服從正態(tài)分布的隨機(jī)變量的均值，σ——隨機(jī)變量的標(biāo)準(zhǔn)差。經(jīng)過實(shí)驗(yàn)測(cè)試μ＝4，σ＝3.96時(shí)函數(shù)擬合正常網(wǎng)頁標(biāo)題字?jǐn)?shù)分布最佳。我們同樣計(jì)算網(wǎng)頁標(biāo)題字?jǐn)?shù)特征分布函數(shù)與網(wǎng)頁比例的差值作為決策樹的閾值之一。

2.3 網(wǎng)頁壓縮率

如果一個(gè)網(wǎng)頁多次包含同一查詢關(guān)鍵詞，搜索引擎將對(duì)此網(wǎng)頁給予較高的排名。例如，對(duì)于給定的一個(gè)查詢關(guān)鍵詞，出現(xiàn)十次的網(wǎng)頁要比只出現(xiàn)一次的網(wǎng)頁排名高。壓縮比指未壓縮的網(wǎng)頁與壓縮之后的網(wǎng)頁的比值。數(shù)據(jù)集中正常網(wǎng)頁與垃圾網(wǎng)頁的網(wǎng)頁壓縮率分布如圖5和圖6所示。

通過圖5與圖6的對(duì)比可以發(fā)現(xiàn)正常網(wǎng)頁與垃圾網(wǎng)頁的壓縮率均在2.1－2.2之間網(wǎng)頁比例最大，所占比例分別為12.39%和14.5%。正常網(wǎng)頁壓縮率大于2.8的網(wǎng)頁比例驟減，比例為6.0%，而垃圾網(wǎng)頁壓縮率大于2.8的網(wǎng)頁所占比例為14.5%，遠(yuǎn)遠(yuǎn)高于正常網(wǎng)頁，正常網(wǎng)頁壓縮率的網(wǎng)頁比例在最高峰之前遞增而在最高峰之后遞減近似泊松分布，泊松分布的概率分布列為

其中參數(shù)ε＞0。k的取值為網(wǎng)頁壓縮率除以0.2之后的整數(shù)部分，ε＝10，δ＝80時(shí)能夠較好的擬合正常網(wǎng)頁壓縮率的分布。

為了提供更相關(guān)的搜索結(jié)果，一些搜索引擎提供網(wǎng)頁中HTML元素的信息，例如，網(wǎng)頁內(nèi)容的注釋，分配給圖像的ALT屬性，標(biāo)題中META標(biāo)簽，這些元素被用于提示網(wǎng)頁或圖片的性質(zhì)，但卻被垃圾網(wǎng)頁當(dāng)作可視目標(biāo)作為關(guān)鍵詞堆砌。因此我們分析了可視文本比例的分布。網(wǎng)頁中一個(gè)鏈接的錨文本用來對(duì)目標(biāo)網(wǎng)頁的內(nèi)容注釋，例如一個(gè)網(wǎng)頁A有一個(gè)錨文本為 “電腦”的鏈接指向B，我們可以認(rèn)為網(wǎng)頁B的內(nèi)容與 “電腦”有關(guān)，盡管網(wǎng)頁B的關(guān)鍵詞沒有 “電腦”。有的垃圾網(wǎng)頁僅僅是為其他頁面提供錨文本，因此我們計(jì)算錨文本比例的分布。我們一共分析了包括平均單詞長(zhǎng)度、語料庫前100精確度等在內(nèi)的24個(gè)網(wǎng)頁內(nèi)容特征分布，并用近似的分布函數(shù)擬合求差值。

3 網(wǎng)頁鏈接特征

3.1 PageRank值

PageRank算法根據(jù)網(wǎng)頁之間互相鏈接的貢獻(xiàn)值對(duì)網(wǎng)頁進(jìn)行排名。越重要的網(wǎng)頁得分越高，排名越靠前，而那些垃圾網(wǎng)頁往往得分較低。PageRank值的計(jì)算公式為

式中：α——衰減系數(shù)，r（q）——網(wǎng)頁q的PageRank值，o（q）——網(wǎng)頁q的出度。網(wǎng)頁p的分?jǐn)?shù)由兩部分組成：一部分來源于那些指向網(wǎng)頁p的網(wǎng)頁，另一部分是全部網(wǎng)頁對(duì)p所做的貢獻(xiàn)。對(duì)于所有的網(wǎng)頁，其PageRank值計(jì)算方式為

其中T為整個(gè)網(wǎng)絡(luò)圖的躍遷矩陣。T的計(jì)算方法為

式中：o（p）——網(wǎng)頁p的出度，（p，q）——網(wǎng)頁p和網(wǎng)頁q之間是否存在鏈接關(guān)系。

3.2 TrustRank值

TrustRank算法在PageRank算法的基礎(chǔ)上利用信任傳播的方式對(duì)每一個(gè)網(wǎng)頁賦值一個(gè)信任值，根據(jù)信任值的大小對(duì)網(wǎng)頁進(jìn)行排名。TrustRank算法首先人工選擇好的網(wǎng)頁作為種子集合，并賦初始值，然后在web圖中以信任衰減或信任分裂的方式傳播直至圖中每一個(gè)網(wǎng)頁都有一個(gè)信任值。TrustRank算法認(rèn)為如果一個(gè)網(wǎng)頁有較高的PageR－ank值但是沒有被好的網(wǎng)頁指向，則這個(gè)網(wǎng)頁很有可能是垃圾網(wǎng)頁。TrustRank值計(jì)算公式為

式中：β——衰減因子 （通常取值為0.85），T——web圖的躍遷矩陣，d——種子集合中好網(wǎng)頁的初始信任值。由于式（8）收斂，所以經(jīng)過n（通常取值為20）次迭代后，TR值即為web圖中網(wǎng)頁的信任值。

通過計(jì)算web圖中的網(wǎng)頁鏈接結(jié)構(gòu)得到網(wǎng)頁的PageR－ank值與TrustRank值。網(wǎng)頁的PageRank值和TrustRank值越大，表示該網(wǎng)頁是正常網(wǎng)頁的概率越大，因此我們直接把PageRank值與TrustRank值作為決策樹的閾值，PageRank值與TrustRank值小于閾值的網(wǎng)頁判定為垃圾網(wǎng)頁。我們還考慮了數(shù)據(jù)集中主機(jī)的入度、出度、與鄰居的距離等21個(gè)網(wǎng)頁鏈接特征分布，用分布函數(shù)擬合并計(jì)算差值。

4 實(shí)驗(yàn)結(jié)果

4.1 度量標(biāo)準(zhǔn)

為了檢測(cè)實(shí)驗(yàn)結(jié)果，我們使用web spam的準(zhǔn)確率、召回率和F值作為實(shí)驗(yàn)結(jié)果的衡量標(biāo)準(zhǔn)。

表1中，TP表示垃圾網(wǎng)頁被正確分類的網(wǎng)頁比例，TN表示垃圾網(wǎng)頁被錯(cuò)分為正常網(wǎng)頁的比例，F(xiàn)P表示正常網(wǎng)頁被誤分為垃圾網(wǎng)頁的比例，F(xiàn)N表示正常網(wǎng)頁被正確分類的比例。

準(zhǔn)確率是指預(yù)測(cè)的垃圾網(wǎng)頁中真實(shí)垃圾網(wǎng)頁的比例，準(zhǔn)確率越大，算法將正常網(wǎng)頁誤判為垃圾網(wǎng)頁的概率就越小

表1 度量單位定義

召回率是指真實(shí)垃圾網(wǎng)頁中預(yù)測(cè)正確的比例

F值實(shí)際上是準(zhǔn)確率和召回率的調(diào)和平均，它將準(zhǔn)確率和召回率綜合為一個(gè)指標(biāo)

4.2 實(shí)驗(yàn)結(jié)果及分析

我們使用的分類方法為C4.5決策樹。C4.5決策樹分類算法的工作原理如下：給定該算法的數(shù)據(jù)集和數(shù)據(jù)集特征，C4.5決策樹創(chuàng)建一個(gè)類似流程圖的樹結(jié)構(gòu)。樹的每個(gè)內(nèi)部接點(diǎn)對(duì)應(yīng)一個(gè)特定特征的值的測(cè)試，并且該接點(diǎn)的每個(gè)后繼分支對(duì)應(yīng)該特征的一個(gè)可能值，樹葉即為對(duì)應(yīng)的分類結(jié)果。對(duì)于每一個(gè)內(nèi)部節(jié)點(diǎn)，C4.5決策樹用基于信息增益的熵挑選特征，能夠越好的分離訓(xùn)練樣例的特征 （即分離后的類熵越?。┓旁跇渲械奈恢迷礁摺?/p>

為了訓(xùn)練C4.5決策樹，本文采用十折交叉驗(yàn)證方法。十折交叉驗(yàn)證算法將數(shù)據(jù)集隨機(jī)的分為十等份，并執(zhí)行十次訓(xùn)練、測(cè)試步驟，其中每次步驟使用九份作為訓(xùn)練數(shù)據(jù)集，剩余的一份作為測(cè)試數(shù)據(jù)集。最后取十次測(cè)試結(jié)果的平均值作為實(shí)驗(yàn)結(jié)果。

通過使用C4.5決策樹和十折交叉驗(yàn)證算法對(duì)網(wǎng)頁的每一個(gè)特征測(cè)試，實(shí)驗(yàn)顯示用指數(shù)函數(shù)擬合文本單詞數(shù)量分布的效果最好，圖7為閾值的選擇與實(shí)驗(yàn)結(jié)果的關(guān)系。

圖7 閾值的選擇與實(shí)驗(yàn)結(jié)果

當(dāng)文本單詞數(shù)量分布與網(wǎng)頁比例差值選擇為1.4時(shí)準(zhǔn)確率最高，為0.662，能夠識(shí)別33.9%的垃圾網(wǎng)頁，誤分頁面為17.4%。

使用上述所有特征后，C4.5決策樹的準(zhǔn)確率為0.928，召回率為0.579，F(xiàn)值為0.713。

5 結(jié)束語

本文通過分析數(shù)據(jù)集中網(wǎng)頁內(nèi)容特征與鏈接特征的分布，用近似的分布函數(shù)對(duì)其擬合并計(jì)算差值，使用C4.5決策樹和十折交叉驗(yàn)證算法根據(jù)差值對(duì)垃圾網(wǎng)頁進(jìn)行檢測(cè)。實(shí)驗(yàn)結(jié)果表明，使用分布函數(shù)擬合網(wǎng)頁特征分布能夠減少被錯(cuò)誤分類的正常網(wǎng)頁，提高準(zhǔn)確率。下一步的工作是進(jìn)一步結(jié)合更多的網(wǎng)頁內(nèi)容特征分布和鏈接特征分布，以期獲得更好的檢測(cè)結(jié)果。

［1］Bing Liu.Web data mining：Exploring hyperlinks，contents，and usage data［M］.Berlin，Heidelberg：Springer－Verlag，2007.

［2］Janden B，Spink A.An analysis of web documents retrieved and viewed ［C］／／ The 4th International Conference on Internet Computing，2003：65－69.

［3］Metaxas P T.On the evolution of search engine rankings［C］／／Proceedings of the WEBIST Conference，2009.

［4］Ntoulasa M，Najork M Manasse.Detecting spam WebPages through content analysis ［C］／／Proceedings of the 15th International Conference on World Wide Web.New York：ACM，2006：83－92.

［5］Lin Yiqin，Shi Xinghua.On computing PageRank via lumping the google matrix ［J］.Journal of Computational and Applied Mathematics，2009，224 （2）：702－708.

［6］Oren K T，Lillian L，Cornell U.PageRank without hyperlinks：Structural reranking using links induced by language models［J］.ACM Transactions on Information Systems，2010，28（4）：18.

［7］Wang X，Tao T，Sun J T，et al.DirichletRank：Solving the zeroone gap problem of PageRank ［J］.ACM Transactions on Information System，2008，26 （2）：10.

［8］Asano Y，Tezuka Y，Nishizeki T.Improvements of HITS algorithms for spam links ［G］.LNCS 4505：APWeb／WAIM，2007：479－496.

［9］Gyongyi Z，Molina H G，Pedersen J.Combating web spam with TrustRank［C］／／Proceedings of the 30th VLDB Conference.ACM Press，2004：576－587.

［10］Jacob Abernethy，Olivier Chapelle.Graph regularization methods for Web spam decetion ［J］.Mach Learn，2010，81 （2）：207－225.

［11］Carlos Castillo，Debora Donato，Aristides Gionis，et al.Know your neighbors：Web spam detection using the web topology［C］／／Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval，2007.

［12］Yahoo.Research：Web spam collections［EB／OL］.http：／／Barcelona.research.yahoo.net／web spam／datasets／，2007.