劉 陽，張化祥

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

0 引 言

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

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

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

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

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

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

2.1 文本單詞數(shù)量

網(wǎng)頁內(nèi)容與查詢關(guān)鍵詞的匹配程度通常作為網(wǎng)頁排名的一個重要因素。垃圾網(wǎng)頁堆砌大量的流行關(guān)鍵詞，因此在查詢時可以匹配上很多關(guān)鍵詞，排名就會靠前。本文統(tǒng)計了數(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)過實驗測試，λ＝3.6，θ＝4.5時能夠很好的擬合正常網(wǎng)頁文本單詞數(shù)量分布。，由于正常網(wǎng)頁文本單詞數(shù)量分布近似指數(shù)分布，所以網(wǎng)頁比例與指數(shù)分布的差值較小，而垃圾網(wǎng)頁的文本單詞數(shù)量分布散亂，差值較大，因此我們把文本單詞數(shù)量網(wǎng)頁比例與指數(shù)分布概率密度函數(shù)的差值ω作為決策樹的一個閾值。差值計算公式為

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

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

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

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

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

2.3 網(wǎng)頁壓縮率

如果一個網(wǎng)頁多次包含同一查詢關(guān)鍵詞，搜索引擎將對此網(wǎng)頁給予較高的排名。例如，對于給定的一個查詢關(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的對比可以發(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%，遠遠高于正常網(wǎng)頁，正常網(wǎng)頁壓縮率的網(wǎng)頁比例在最高峰之前遞增而在最高峰之后遞減近似泊松分布，泊松分布的概率分布列為

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

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

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

3.1 PageRank值

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

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

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

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

3.2 TrustRank值

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

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

通過計算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ù)集中主機的入度、出度、與鄰居的距離等21個網(wǎng)頁鏈接特征分布，用分布函數(shù)擬合并計算差值。

4 實驗結(jié)果

4.1 度量標準

為了檢測實驗結(jié)果，我們使用web spam的準確率、召回率和F值作為實驗結(jié)果的衡量標準。

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

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

表1 度量單位定義

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

F值實際上是準確率和召回率的調(diào)和平均，它將準確率和召回率綜合為一個指標

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

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

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

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

圖7 閾值的選擇與實驗結(jié)果

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

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

5 結(jié)束語

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