基于結構信息和時域信息的垃圾網頁檢測技術

摘要：提出一種將結構信息和時域信息綜合運用來檢測Spam技術的方法，并針對目前流行的Spam技術，從四個月的網絡鏈接圖中提取大量的結構和時域信息特征，訓練一組檢測Spam技術的網頁分類器，取得了很好的實驗結果。

關鍵詞：Spam技術； 搜索引擎優化； PageRank

中圖分類號：TP393文獻標志碼：A

文章編號：1001－3695(2008)04－1243－04

0引言

隨著國際互聯網的普及，人類社會進入了一個信息爆炸的時代，大量的信息得以在互聯網上高速傳播。一方面，這使得不同地區的人們能夠更加自由、方便地獲取和傳播知識，這在一定程度上打破了過去存在于發達地區與不發達地區之間的信息鴻溝，使對信息有相當依賴性的科學研究、工農業生產等方面的競爭環境趨于平等；另一方面，如何在海量的信息中查找用戶需要的信息，已成為這個時代的一個重要課題。在這種情況下，互聯網搜索引擎因應而生，并且不斷發展壯大，形成了一個新興產業。搜索引擎檢索結果的排序會對相關的網站產生直接的影響，在同一查詢下排名靠前的網頁所在的站點會被更多的用戶點擊，從而獲得更多的經濟效益。因此，為了使自己的網站在搜索引擎的檢索結果中排名靠前，一些網站的所有者會采用各種各樣的手段來提高自己的排名，于是產生了專門為其他網站提供提高網站排名服務的盈利組織——SEO（search engine optimizer，搜索引擎優化組織）。SEO采用的技術手段有些是合法有益的，能夠使對用戶有用的信息排名靠前；而有些技術則是利用一些非法手段來提高網頁的排名，這會造成大量垃圾信息，并使得一些對用戶沒有價值的網頁在檢索結果的排名靠前。后者被稱做Spam，即使用非法手段提高網站或網頁在搜索引擎檢索結果中的排名的技術。

目前，搜索引擎對網頁的排名主要依靠內容相關度和網頁重要程度兩方面來確定。內容相關度可以由tf－idf[1]等信息檢索的方法計算，而重要程度往往由PageRank[2]和HITS[3]等基于鏈接分析的算法得出。相應地，Spam技術也主要分為針對內容相關度的Spam和針對網頁重要程度的Spam（或者稱為基于超級鏈接的Spam）兩大類。這些Spam技術往往會干擾搜索引擎的正常排名結果。

本文所研究的重點是檢測和識別使用了針對網頁重要程度的Spam技術的網站。學術界已經在相關領域作出了很多卓有成效的探索。目前，已經發現的比較經典的基于超級鏈接的Spam技術包括鏈接農場（link farm）、在論壇或者博客中粘貼大量超級鏈接、購買過期域名和其他網站的超級鏈接等。為了有效識別這些技術，人們提出了基于信任的傳播模型，相關的算法包括TrustRank[4]和BadRank[5]。還有一類方法利用鏈接關系的統計信息[6]來檢測基于超級鏈接的Spam技術，Benczur等人[7]提出了SpamRank算法來懲罰有Spam嫌疑的網頁。除了上面提到的利用某一時刻網頁之間的鏈接關系來檢測Spam技術外，Shen等人[8] 還利用采樣于不同時刻的兩張網絡鏈接圖的對比信息提出了基于網站鏈接關系變化的時域特征的Spam檢測技術。

前面介紹的反Spam技術實際上分為兩類：a)基于某一時刻的網絡鏈接關系，稱之為結構信息，是靜態的；b)基于網絡鏈接關系的變化，稱之為時域信息，是動態的。為了更準確地檢測使用Spam技術的網頁，同時也為了檢測到更多的Spam網頁，本文從多個網絡鏈接圖中提取結構信息與時域信息，并且提出了一種將結構信息與時域信息結合起來的方法。實驗表明，本文提出的算法能以相當高的準確度檢測出使用了基于超級鏈接的Spam技術的網頁。

1實驗設置

本文的目的是將結構信息特征與時域信息特征綜合運用，所以本文的實驗不會僅建立在某一時刻的網絡鏈接圖上。為此，筆者使用了由某商業搜索引擎提供的從2006年3月至2006年6月四個月的網絡鏈接圖的抽樣子圖，每張子圖均包含網站的URL以及網站之間的鏈接數等信息。

筆者利用網站級別的網絡鏈接子圖來開展本實驗是基于以下幾個原因：

a)不同的頂級域名中的垃圾網站的比例不同。例如，以.gov或.edu為域名的網站大都由合法正規的機構來維護，其中的垃圾網站會少一些；而以.com或.biz為域名的網站，其所有者良莠不齊，既有名譽全球的大企業，又有大量不知名的小公司，甚至還有很多個人網站，所以里面垃圾網站會多一些。給本文提供數據的搜索引擎在生成實驗子圖時，對.gov和.edu等域名采取了低密度抽樣，而對.com和.biz等域名采取了高密度抽樣。這就保證了能在有限的數據資源中包含更多的垃圾網站。

b)頁面級別的網絡鏈接圖雖然信息更加詳盡，但是由于信息量過于龐大，難以處理。實際上，在網站級別的網絡鏈接子圖中，每個子圖已經有3 000多萬個網站存在。

c)很多以前的研究表明，基于網站級別的研究確實可以檢測出很多鏈接欺詐行為。

本文對四張網絡鏈接圖的數據統計如表1、2所示。

從表1中可以發現，四張網絡鏈接圖中網站總數差別不大。但是從表2中發現實際包含在兩個圖中的網站改變了許多。大約有超過10%的網站出現在前一個月的圖中，而在后一個月的圖中消失了；同時后一個月的圖中又增加了大約10%的新網站。這一方面是由于網站抓取的策略原因；另一方面，這也說明網站更新速度很快。總之，有很多網站存在于不同的圖中，同時有很多網站只存在于個別的圖中。單純利用結構信息或時域信息都會漏掉很多網站，這也證明了采取兩種信息特征結合的方法是很有必要的。

為了檢驗筆者提出的每個特征的有效性，本文對網絡鏈接圖中的一部分網站進行了標注，將這些網站分為正常網站和垃圾網站（使用了Spam技術的網站）兩部分。本文一共標注了將近兩萬個網站，具體數據如表3所示。



2兩種特征的結合

從表1和2中可以發現，出現在多個圖中的網站和只出現在一個圖中的網站均占有一定的比例。為了充分利用本文數據，同時為了對盡可能多的網站作出判斷，本文提出了一種將結構信息特征與時域信息特征綜合運用的方法。

2．1數據分類

對四個月網絡鏈接圖中的網站統計如表4所示。

從表4的數據可以看出，對于出現在連續月網絡鏈接圖中的網站，可以利用它們的時域信息特征去判斷它們是不是垃圾網站，而對于只出現在某個單獨月份網絡鏈接圖中的網站，可以利用的只有它們的結構信息特征。

對于僅利用結構信息預測的網站，可以抽取網站所在的網絡鏈接圖上的結構特征信息（見3.1節）去訓練分類器，然后用分類器去預測當前的網站性質。

對于利用時域信息預測的網站，情況要復雜一些。Shen等人的工作[8]，只利用到了兩個月網絡鏈接圖中的時域信息。顯然，本文擁有的四個月的網絡鏈接圖信息更加豐富。由于時域信息是相鄰兩個月內網站的變化信息，出現在連續多個月份網絡鏈接圖中網站的時域信息肯定要比只出現在兩個連續月份網絡鏈接圖中網站的時域信息多。一般來說，出現在m(m>1)個連續月份網絡鏈接圖中網站的時域信息量與出現在n(n>1)個連續月份網絡鏈接圖中網站的時域信息量的比例關系是(m-1)/(n-1)。為了更充分地利用時域信息，筆者對3~6月份的圖作了統計（表5）。

將表5中的網站分為三類，第一類是在3~6四個月均出現的網站；第二類是在4~6三個月中出現但是不出現在3月份中的網站；第三類是出現在5、6月份但是不出現在3、4月份的網站。顯然，對于這些不同類型的數據使用同一種模型來判斷是不夠準確的。本文解決辦法是針對數據信息量的不同抽取不同數量的信息特征(見3.2節)，并訓練不同的分類器加以判斷。

 對于第一類的數據，本文抽取三部分的時域特征信息，分別是3~4月、4~5月以及5~6月的信息；對于第二類數據抽取兩部分的特征信息，分別是4~5月以及5~6月的信息；同理，對于第三類數據本文抽取一部分的特征信息，即5~6月的信息。

2．2訓練數據準備

在訓練數據的準備中，筆者發現如果將利用時域特征信息的訓練數據分成前面描述的互不相交的三類數據（圖1），每一類的數據量將會大量減少，進而有可能影響最終的分類器性能。為此，筆者設計了一種方案，以最大限度地利用訓練數據。



從圖1中可以看出，屬于第一類數據的時域特征信息包括了第二類和第三類數據的時域特征信息，所以當第一類數據僅抽取第二類數據的特征信息時，同樣可以作為第二類訓練數據使用，這樣就增加了第二類訓練數據的樣本量。同理，第一類訓練數據和第二類訓練數據同樣可作為第三類訓練數據使用。

2．3實驗流程

前面將利用時域信息特征的網站分為三類，再加上只出現在單個網絡鏈接圖中的網站需要利用結構信息特征，所以將全部網站分為四類。訓練數據準備好后，筆者用Boosting算法[9]分別預測出針對于各種類型數據的分類器。整個網站預測過程如圖2所示。



由圖2可以看出，對于一個待預測的網站，先判斷其是否出現在連續月份的網絡圖中。如果不是，則選擇用結構信息去判斷該網站；如果是，則判斷該網站是屬于三類時域信息中的哪一類，并用相應的分類器去預測它。

3結構信息特征及時域信息特征介紹

3．1結構信息特征

本文在結構信息中提取了38個特征，由于篇幅所限，本文只介紹其中有代表性的幾個特征。為了方便對后面的特征加以描述，首先定義一些符號：

Sin（a)：存在鏈接指向a網站的網站集合;

Sout(a)：a網站的鏈接指向的網站集合。

4．1．1入鏈接數目（ILN）

某個網站的入鏈接是其他網站指向自己網站的鏈接，入鏈接數目定義為有鏈接指向該網站的網站數目。

ILN(a)=|Sin(a)|

一個知名的網站，指向它的鏈接會有很多，一般會有數十萬甚至數百萬個；而一個正常的小網站，也許只有幾個指向它的鏈接，如個人的博客。可以看出正常的網站入鏈接數分布是相當廣泛的。而對于一個垃圾網站而言，一方面它會想辦法通過增加入鏈接提高自己的PageRank；另一方面它又沒有能力獲取到像一個知名網站那么多的鏈接。所以，入鏈接數是一個有用的信息。為了驗證這一點，本文對所有標注的網站（18 257個）進行了統計，結果如圖3所示。

將18 257個網站的入鏈接數按照由小到大的順序后放入19個桶中，前18個桶的容量都是1 000，最后一個桶存放剩下的數據。圖3中的橫坐標軸表示19個桶的編號，每個桶中有兩個柱，分別表示垃圾網站和正常網站；縱坐標軸標注的是桶中網站個數。

可以看出，在入鏈接數目最大的前兩個桶和入鏈接數目最小的后三個桶中，正常網站的數目明顯大于垃圾網站的數目；而在入鏈接數目排在中游的幾個桶中，垃圾網站的數目要大于正常網站的數目。考慮到在實際情況中，垃圾網站數目與正常網站數目的比例大約為1∶10[8]，而在本文的標注數據集中，兩者的比例大約是1∶1，所以這并不能說明在實際情況下，真的會出現在某個桶中垃圾網站的數目一定會多于正常網站數目。但是，通過入鏈接數目這個特征，至少可以比較有效地觀察出垃圾網站的分布范圍。

3．1．2鄰節點入鏈接數方差（ILNVariance）



有很多自動生成的鏈接圖中的垃圾網站，或受控于SEO公司的一些小網站（其存在目的是為了提升目標垃圾網站在搜索引擎返回結果中的排名），它們的鄰節點網站往往具有相似的性質。而正常網站的鄰節點網站的性質則會比較分散，它們之間的差異會比較大。以這個假設為前提，筆者求出了鄰節點入鏈接數的方差，看看是否能幫助人們區分垃圾網站和正常網站。鄰節點入鏈接數方差定義為

ILNVariance(a)=∑b∈Sin(a)∪Sout(a)(ILN(b)-ILNMean(a))2/|Sin(a)∪Sout(a)|。

圖4是ILNVariance的分布，將所有標注的網站鄰節點入鏈接數方差按照由大到小的順序后放入19個桶中，橫坐標軸分別表示19個桶，縱坐標軸標注的是桶中垃圾網站和正常網站個數。可以很明顯地看出，總體來說垃圾網站鄰節點入鏈接數的方差要小于正常網站鄰節點入鏈接數的方差，這也驗證了先前的直觀想法。

3．1．3其他結構信息特征

由于篇幅所限，這里不再詳細介紹每一個結構信息特征，而只在表6中給出部分特征列表。

3．2時域信息特征

除了結構信息特征，本文還抽取了一些時域特征，包括IGR（入鏈接增長率）、IDR（入鏈接減少率）、OGR（出鏈接增長率）、ODR（出鏈接減少率）、IGRMean（入鏈接增長率均值）、IDRMean（入鏈接減少率均值）、OGRMean（出鏈接增長率均值）、ODRMean（出鏈接減少率均值）、IGRVar（入鏈接增長率方差）、IDRVar（入鏈接減少率方差）、OGRVar（出鏈接增長率方差）、ODRVar（出鏈接減少率方差）等。由于篇幅所限，這里就不詳細介紹了，具體請參見文獻[8]。

4實驗結果

本文采用訓練數據和第3章節中介紹的信息特征訓練出不同的分類器，并用2.3節中介紹的判斷流程對全局數據進行判斷，在大約3 000萬個網站中，有約30萬網站被判斷為垃圾網站。由于數據量太大，本文采用隨機選出網站進行人工標定的方法來檢驗該實驗結果的準確性。

首先，對30萬個筆者判斷的垃圾網站中得分最高的1 000個進行標注，結果如表7所示。

其次，對30萬個網站進行隨機抽取，選擇了其中的1 000個網站進行標注，結果如表8所示。

筆者認為，垃圾網站和無法打開的網站均是用戶不希望看到的網站，而且很多無法打開的網站也很有可能曾經使用過Spam技術來提高自己的重要程度。所以，將垃圾網站和無法打開的網站數目定義為本文的方法判斷正確的網站數目，正常網站數目是本文方法判斷錯誤的網站數目，不能確定的網站忽略不計。按照這個定義，在前1 000個網站中，判斷準確率達到（497+339）/（497+6+339）=99.29%；在從30萬個網站隨機抽取的1 000個網站中，準確率降為（636+87）/（636+101+87）=87.74%。可見，排名越靠前的網站是垃圾網站的可能性越大。考慮到在整個互聯網中，垃圾網站只占到1/10[8]，本文的分類器還是取得了非常理想的效果。

5結束語

本文提出了一種將網絡鏈接圖中的結構信息特征和時域信息特征綜合運用來檢測Spam技術的方法。針對目前比較流行的Spam技術，從四個月的網絡鏈接圖中提取了大量的結構信息特征和時域信息特征來進行實驗。實驗結果表明，使用本方法預測垃圾網站，在隨機抽取檢驗樣本的情況下準確率達到87.74%，在抽取排名最靠前的1 000個網站為檢驗樣本的情況下，準確率達到99.29%。

參考文獻：

［1］BAEZA－YATES P， RIBEIRO－NETO B. Modern information retrieval[M].[S.l.]: Addison Wesley Longman Publishing Co Inc，1999.

[2］PAGE L， BRIN S， AMRITKAR R E， et al. The PageRank citation ranking: bringing order to the Web[EB/OL].(1999－11－11). http://newdbpubs.stanford.edu/8090/pub/1999－66/1999.

[3］KLEINBERG J M. Authoritative sources in a hyperlinked environment[J]. Journal of the ACM，1999，46(5): 604－632.

[4］GYONGYI Z， GARCIA－MOLINA H， PEDERSEN J. Combating Web Spam with TrustRank[C]//Proc of International Conference on Very Large Data Bases (VLDB). 2004.

[5］WU B， DAVISON B D. Identifying link farm Spam pages[C]//Proc of the 14th Int’l Conf on World Wide Web. New York:ACM Press，2005:820－829.

[6］DAVISON B D. Recognizing nepotistic links on the Web[EB/OL].(2000). http://citeseer.ist.psu.edu/davison00recognizing.html.

[7］BENCZUR A A， CSALOGANY K， SARLOS T， et al. SpamRank－fully automatic link spam detection[C]//Proc ofthe 1st AIRWeb. 2005.

[8］SHEN Guo－yang， GAO Bin， LIU Tie－yan， et al. Detecting link Spam using temporal information[C]//Proc of ICDM－2006. 2006.

[9］FREUND Y， SCHAPIRE E. A decision theoretic generalization of on line learning and an application to boosting[J]. Journal of Compu－ter and System Sciences， 1997， 55(1):119－139.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”