基于Timed-PageRank的聚焦爬蟲優化研究

【基礎理論與應用研究】

基于Timed-PageRank的聚焦爬蟲優化研究

李東1，王虎強2

(裝甲兵工程學院 信息工程系，北京100072)

摘要：傳統的基于PageRank算法的網絡爬蟲在抓取網頁時由于只考慮了網頁的超鏈接，勢必會使爬蟲結果覆蓋面廣、冗余度高，聚焦爬蟲由于其可以有效地過濾與主題無關的鏈接，只保留有用的鏈接并將其加入到待抓取的URL隊列，因此能夠有效地降低爬蟲冗余；在分析PageRank算法的基礎上，將網頁的時間維數和頁面的內容相關度融于其中，提出了基于Timed-PageRank的改進算法，并將該算法應用于聚焦爬蟲過程中，實踐證明該算法能夠有效地提高爬蟲頁面相關度及檢索結果的查全率和查準率。

關鍵詞：傳統網絡爬蟲；PageRank算法；聚焦爬蟲； Timed-PageRank改進算法

收稿日期：2014-06-27

作者簡介：李東(1962—)，男，副教授，主要從事軍事管理信息系統研究。

doi:10.11809/scbgxb2015.01.039

中圖分類號：TP391.3

文章編號：1006-0707(2015)01-0141-04

本文引用格式：李東，王虎強.基于Timed-PageRank的聚焦爬蟲優化研究[J].四川兵工學報，2015(1):141-144.

Citationformat:LIDong,WANGHu-qiang.OptimizationResearchonFocusedCrawlerBasedonImprovedTimed-PageRankAlgorithm[J].JournalofSichuanOrdnance,2015(1):141-144.

OptimizationResearchonFocusedCrawlerBasedonImproved

Timed-PageRankAlgorithm

LIDong1, WANG Hu-qiang2

(DepartmentofInformationEngineering,AcademyofArmoredForcesEngineering,Beijing100072,China)

Abstract:Traditional web crawler which based on PageRank algorithm only takes the hyperlinks into consideration when scraping the web pages and it is bound to make the results in a wide coverage and high redundancy. Focus crawlers can effectively filter off-topic links, and only save useful links and add them to the URL queue, so it can reduce redundancy effectively. By analyzing the PageRank algorithm, the improved algorithm was proposed based on the Timed-PageRank, and after that we added the time dimension and page content relevance into it. Then we applied the algorithm into focus crawler. Practice proves that the algorithm can effectively improve the relevance, the recall rate and precision of the search results.

Keywords:traditionalwebcrawler;PageRankAlgorithm;focuscrawlers;improvedTimed-PageRankAlgorithm

隨著互聯網的普及與發展，信息增長速度迎來了歷史高峰，大量信息涌入人們的日常生活，而對于人們所需的信息的檢索就有了相當了困難，搜索的結果要么是雜亂無章，要么不能達到令人滿意的效果。因此建立特定領域專業化網絡檢索系統[1]是一個行之有效的措施。而聚焦爬蟲就是為了滿足這一要求誕生的，它以其爬蟲范圍緊貼主題，檢索效果既全又準的優勢贏得了開發人員的青睞。

1聚焦爬蟲

作為搜索引擎的核心組成部分，傳統的網絡爬蟲[2]的主要功能是從網上下載與主題相關的網頁，以供后續開發搜索引擎時建立索引并檢索的需要。其主要思想是從預先設定好的起始網頁開始爬取，將起始網頁中的超鏈接添加到URL隊列中，反復迭代，根據一定的搜索策略，不斷地從當前頁面上提取新的URL超鏈接放入隊列，直到爬蟲結束或是滿足一定的爬蟲條件而終止，其爬蟲流程圖如圖1所示。

因此傳統網絡爬蟲具有一定的局限性：

一是冗余大。傳統網絡爬蟲沒有對待爬取的網頁進行頁面相關度匹配，只是將存在于起始頁面的鏈接加載到URL隊列里，反復迭代，因此將許多相關度很低甚至是不相關的網頁爬取下來，造成了大量的冗余信息。

二是查準率低下。正是因為爬蟲冗余大，也就勢必造成檢索數據庫信息量劇增， 會檢索結果不能很好地達到預期目的。

三是爬蟲時間長。傳統網絡爬蟲會爬取許多不相干的網頁，勢必會增加爬蟲時間。

圖1　傳統網絡爬蟲流程

聚焦爬蟲[3]則不同，它需要根據一定的網頁分析算法計算其頁面相關度，以此來過濾與主題無關的鏈接，只保留有用的鏈接并將其放入等待抓取的URL隊列。然后，它將根據一定的搜索策略從隊列中選擇下一步要抓取的網頁URL，并重復上述過程，直到達到系統的某一條件時停止。

此外，聚焦爬蟲的另一個特色就是所有被爬蟲抓取的網頁將會被系統存貯，進行一定的分析、過濾，并建立索引，以便之后的查詢和檢索；對于聚焦爬蟲來說，這一過程所得到的分析結果還可能對以后的抓取過程給出反饋和指導。其爬蟲流程圖如圖2所示。

圖2　聚焦爬蟲流程

因此聚焦爬蟲相對于傳統網絡爬蟲具有一定的優越性：

一是冗余小。根據一定的算法有效控制爬蟲范圍，去糟取精。

二是爬蟲結果與主題相關度更加貼近。聚焦爬蟲能很好地控制爬取網頁與主題的相關度，舍棄相關度地的網頁。

三是檢索效果佳。因為其爬蟲范圍不僅小了許多，而且緊貼主題，所以對于檢索的效果會更好。

對比上面兩幅圖可以看出，兩種爬蟲策略的最大區別在于是否通過算法對頁面進行分析，確定其與主題的相關度大小，倘若計算結果大于事先設定的相關度閾值，則將該網頁加入到URL隊列中待爬取，反之則棄之。

2PageRank算法

PageRank算法[4]廣泛應用于傳統搜索引擎的網絡爬蟲中，它是基于網頁的超鏈接之間的關系而得出頁面排序值的，因此它只考慮與網頁有直接或間接關聯關系的網頁，而并不考慮任何用戶的任何查詢以及網頁的時間維數和頁面相關度。

2.1相關概念

網頁i的入鏈：指向網頁i的來自于其他網頁的超鏈接的個數，即可以通過超鏈接從其他網頁進入到網頁i中；

網頁i的出鏈：從網頁i出發，指向其他網頁的超鏈接的個數，即可以從網頁i鏈接到其他網頁中。

2.2算法原理分析

1) 從一個網頁指向另一個網頁的超鏈接是一種權威性的隱式傳輸，即指向它的父鏈接數越多，表示它的PageRank值就越高。

2) 網頁i的PageRank值是由所有指向它的父網頁的PageRank值的總和決定的，而每個父鏈接的PageRank值將分配給所有的子鏈接，一般取平均分配，即分配系數取0.5。

為了形象而又直觀的理解，文章引入了圖論思想：將Web抽象為一個有向圖G=(V，E)，其中V表示有向圖的節點，這里的節點指網頁，E表示有向邊，這里指超鏈接。則Web上的網頁總數n=|V|，網頁i的PageRank值用PR(i)表示

(1)

其中Oj表示網頁j的出鏈個數。

再用矩陣A表示有向圖的鄰接矩陣，按如下規則為每條邊賦值

(2)

假如一個Web超鏈接有向圖如圖3所示。

圖3　 Web 鏈接有向圖

根據式(1)便可求出第1個節點的PageRank值

(3)

因為節點1有2個出鏈(分別為節點2和節點4)，所以根據式(1)可以得出A12=A13=1/2，同理可求得狀態轉移矩陣為

任何時刻，隨機瀏覽者從任意頁面出發，是否選擇繼續瀏覽超鏈接網頁，都會給這一鏈接分配一個由參數d控制的微小轉換概率，也稱為阻尼因子，其取值范圍為0～1。 一般取值d=0.85。這樣一來，對于含有n個Web網頁節點的任意網頁的PageRank值公式為

(4)

該算法可以賦予任意的PageRank值初始值，經過反復迭代，當PageRank值不再發生顯著變化或是趨于收斂時，算法結束，其迭代[5]求解算法如圖4所示，當差值向量的1階范數小于網頁相關度閾值ε的時候就結束迭代。

PageRank-Iterate(G)Pε=任意值k←1Repeatpk←(1-d)+dATPk-1k←k+1until‖Pk-Pk-1‖<εreturnPk

圖4PageRank迭代求解算法

3Timed-PageRank改進算法

3.1融入時間維度的PageRank改進算法

Web網頁的一個顯著特征就是網頁的動態性，它將不斷隨著時間的推移而不斷的變化，因此它具有良好的時效性，而傳統網絡爬蟲的不足之處就是沒有考慮和處理網頁檢索結果的時效性，因此不能很好地滿足用戶的檢索需求。

Time-PageRank算法是在PageRank算法的基礎上，新增了關于網頁的一個時間維度[6]，其主要思想為：仍延續PageRank的隨機沖浪和馬爾科夫鏈模型，不同之處就是不再使用阻尼因子d，而是引入了一個時間函數f(t)〈f(t)∈[0,1]〉來懲罰“陳舊的鏈接和網頁”，這里的自變量t指的是當前時間和上次網頁更新時間的差值，函數f(t) 指的是通過超鏈接訪問網頁的概率，而1-f(t)就指不通過超鏈接訪問網頁的概率。則Web瀏覽者就有2種選擇：以f(t)概率通過超鏈接訪問網頁；以1-f(t)概率不通過超鏈接跳到其他網頁。

通常，f(t)的函數值會隨著當前時間和上次網頁更新時間的差值的增大而減小，對f(t)定義如下：

(5)

式(5)中：t表示當前時間和上次網頁更新時間的月份差值。網頁越新，t值越小，其時間權值就越大，這樣就能有效地區調整新舊網頁的PageRank值，調整新的PageRank值[7]計算公式如下：

PR′(i)=PR(i)×f(it)

(6)

式(6)中：PR′(i)為融入時間維度后的PageRank值，PR(i)為傳統算法所得的PageRank值， f(it)為頁面i的時間權值。

3.2融入頁面內容相關度的 PageRank改進算法

聚焦爬蟲相比傳統網絡爬蟲的優勢就在于爬取的網頁盡可能地保證與主題的相關度大，最大限度地降低冗余網頁，提高網頁檢索的查準率。

由于在計算網頁相關度[8]的時候，共同詞語出現位置的不同，其占的權重也不同[9]。比如標題的權重必然大于內容權值，內容權重必然大于標簽權重等。因此計算網頁相關度一般從如下幾個方面考慮：標題關鍵字相關；內容共同詞語頻度。

一般而言，標題關鍵字的權重要大于內容共同詞語頻度的權重，這里取a為標題權重，b為內容權重，且滿足歸一化原理，即a+b=1。設主題關鍵字在標題中出現的次數為m，在內容中出現的次數為n，則頁面i與待檢索主題相關度Sim(i) 計算公式為

(7)

綜合以上兩種PageRank改進算法，則新的改進算法將由兩部分組成：一是融入時間維度的PageRank改進算法，二是融入頁面內容相關度的PageRank改進算法，假設前者的權重系數為α，后者的系數為β，同樣滿足α+β=1，便可得到改進后的Timed-PageRank新算法公式如下：

PR(i)=αPR′(i)+βSim(i)=α[(1-d)+

(8)

因此，在進行聚焦爬蟲的過程中，要對待爬取的網頁進行相關度計算，便可運用式(8)計算其與主題的相關度，看其是否滿足爬蟲前預先設置好的爬取閾值，若滿足，則爬取，否則丟棄。

4實例分析

為了測試改進后的Timed-PageRank算法是否相對于傳統的利用PageRank算法具有優越性，進行了爬蟲測試。實驗平臺為PC機(Pentium(R) 4CPU+2.93GHz,2.00GB內存)，操作系統為Win7旗艦版，開發工具為Myeclipse10.0.0，使用開源的Heritrix程序進行爬蟲。選擇的爬取起始網頁分別為搜狐，新浪和163的新聞主頁。

爬蟲前，可以預先設置相關度閾值，這里取0.3，在爬蟲的過程中，如果待爬取的網頁與爬蟲主題相關度高于0.3時才能添加到URL隊列中等待爬取，否則將直接丟棄。

如圖5所示在1 000s的爬蟲時間內，基于PageRank算法的傳統網絡爬蟲和基于改進后的Timed-PageRank算法的聚焦爬蟲所爬取的網頁與主題的相關度隨爬蟲時間的函數關系。

從圖5中可以看出，爬蟲開始時，兩種算法網頁的相關度都是最高，隨著時間的推移，網頁的相關度逐漸下降，但都始終高于閾值0.3。且基于Timed-PageRank改進算法的聚焦爬蟲的網頁相關度總是大于基于Timed-PageRank算法的傳統網絡爬蟲。這說明Timed-PageRank改進算法明顯優于傳統的PageRank算法，因此基于Timed-PageRank改進算法的聚焦爬蟲也同樣優于傳統的網絡爬蟲，因為其爬取的網頁與檢索主題的相關度高，這能很好地保障檢索結果的查準率，這也將對今后開發專業搜索引擎提供了一個很好的思路。

圖5　基于2種不同算法的爬蟲效果示意圖

5結論

本文在分析了傳統網絡爬蟲沒有考慮網頁時間維度以及網頁相關度的基礎上，對傳統的PageRank算法進行了改進，提出了一種基于Timed-PageRank改進算法的聚焦爬蟲，不僅增加了時間維度，而且將頁面內容相關度融入其中。此算法比較全面地考慮了影響網頁相關性的各種因素，能夠有效地分析網頁相關度，并根據預先設定好的閾值優化爬蟲范圍，縮小URL隊列，能夠有效地提高檢索的查全率和查準率，相對于傳統爬蟲具有一定的優越性。最后根據實例驗證了該算法的可行性和相對于傳統算法的優越性，同時也說明了聚焦爬蟲優于傳統網絡爬蟲，其在不久的將來定會得到廣泛應用。

參考文獻：

[1]李國成.網絡搜索引擎的現狀及發展探析[J].企業科技與發展,2009(8):25-26.

[2]劉世濤.簡析搜索引擎中網絡爬蟲的搜索策略[J].阜陽師范學院學報：自然科學版,2006,03:59-62.

[3]周立柱,林玲.聚焦爬蟲技術研究綜述[J].計算機應用,2005(9):1965-1969.

[4]吳信東，庫瑪爾.數據挖掘十大算法[M].李文波，吳素研，譯.北京：清華大學出版社,2013.

[5]GolubGH,VanLoanCF.MatrixComputations[M].TheJohnsHopkinsUniversityPress,1983.

[6]LiX,LiuB,YuPS.TimeSensitiveRankingwithApplicationtoPublicationSearch[M].ConferenceonDataMining,2008.

[7]張翔,周明全,李智杰,等.基于PageRank與Bagging的主題爬蟲研究[J].計算機工程與設計,2010,14:3309-3312.

[8]鄧丹君,周彩蘭.基于內容相關性和時間分析的改進PageRank算法[J].計算機與數字工程,2011(1):25-27.

[9]陳小飛,王軼彤,馮小軍.一種基于網頁質量的PageRank算法改進[C]//中國計算機學會數據庫專業委員會.第26屆中國數據庫學術會議論文集(B輯).中國計算機學會數據庫專業委員會,2009:

(責任編輯蒲東)