基于Timed-PageRank的聚焦爬蟲優(yōu)化研究

【基礎(chǔ)理論與應(yīng)用研究】

基于Timed-PageRank的聚焦爬蟲優(yōu)化研究

李東1，王虎強2

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

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

關(guān)鍵詞：傳統(tǒng)網(wǎng)絡(luò)爬蟲；PageRank算法；聚焦爬蟲； Timed-PageRank改進算法

收稿日期：2014-06-27

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

doi:10.11809/scbgxb2015.01.039

中圖分類號：TP391.3

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

本文引用格式：李東，王虎強.基于Timed-PageRank的聚焦爬蟲優(yōu)化研究[J].四川兵工學(xué)報，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

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

1聚焦爬蟲

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

因此傳統(tǒng)網(wǎng)絡(luò)爬蟲具有一定的局限性：

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

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

三是爬蟲時間長。傳統(tǒng)網(wǎng)絡(luò)爬蟲會爬取許多不相干的網(wǎng)頁，勢必會增加爬蟲時間。

圖1　傳統(tǒng)網(wǎng)絡(luò)爬蟲流程

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

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

圖2　聚焦爬蟲流程

因此聚焦爬蟲相對于傳統(tǒng)網(wǎng)絡(luò)爬蟲具有一定的優(yōu)越性：

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

二是爬蟲結(jié)果與主題相關(guān)度更加貼近。聚焦爬蟲能很好地控制爬取網(wǎng)頁與主題的相關(guān)度，舍棄相關(guān)度地的網(wǎng)頁。

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

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

2PageRank算法

PageRank算法[4]廣泛應(yīng)用于傳統(tǒng)搜索引擎的網(wǎng)絡(luò)爬蟲中，它是基于網(wǎng)頁的超鏈接之間的關(guān)系而得出頁面排序值的，因此它只考慮與網(wǎng)頁有直接或間接關(guān)聯(lián)關(guān)系的網(wǎng)頁，而并不考慮任何用戶的任何查詢以及網(wǎng)頁的時間維數(shù)和頁面相關(guān)度。

2.1相關(guān)概念

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

網(wǎng)頁i的出鏈：從網(wǎng)頁i出發(fā)，指向其他網(wǎng)頁的超鏈接的個數(shù)，即可以從網(wǎng)頁i鏈接到其他網(wǎng)頁中。

2.2算法原理分析

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

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

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

(1)

其中Oj表示網(wǎng)頁j的出鏈個數(shù)。

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

(2)

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

圖3　 Web 鏈接有向圖

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

(3)

因為節(jié)點1有2個出鏈(分別為節(jié)點2和節(jié)點4)，所以根據(jù)式(1)可以得出A12=A13=1/2，同理可求得狀態(tài)轉(zhuǎn)移矩陣為

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

(4)

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

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

圖4PageRank迭代求解算法

3Timed-PageRank改進算法

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

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

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

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

(5)

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

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

(6)

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

3.2融入頁面內(nèi)容相關(guān)度的 PageRank改進算法

聚焦爬蟲相比傳統(tǒng)網(wǎng)絡(luò)爬蟲的優(yōu)勢就在于爬取的網(wǎng)頁盡可能地保證與主題的相關(guān)度大，最大限度地降低冗余網(wǎng)頁，提高網(wǎng)頁檢索的查準率。

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

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

(7)

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

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

(8)

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

4實例分析

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

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

如圖5所示在1 000s的爬蟲時間內(nèi)，基于PageRank算法的傳統(tǒng)網(wǎng)絡(luò)爬蟲和基于改進后的Timed-PageRank算法的聚焦爬蟲所爬取的網(wǎng)頁與主題的相關(guān)度隨爬蟲時間的函數(shù)關(guān)系。

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

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

5結(jié)論

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

參考文獻：

[1]李國成.網(wǎng)絡(luò)搜索引擎的現(xiàn)狀及發(fā)展探析[J].企業(yè)科技與發(fā)展,2009(8):25-26.

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

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

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

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

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

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

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

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

(責任編輯蒲東)