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

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

李東1，王虎強(qiáng)2

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

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

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

收稿日期：2014-06-27

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

doi:10.11809/scbgxb2015.01.039

中圖分類號(hào)：TP391.3

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

本文引用格式：李東，王虎強(qiáng).基于Timed-PageRank的聚焦爬蟲優(yōu)化研究[J].四川兵工學(xué)報(bào)，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ā)展，信息增長速度迎來了歷史高峰，大量信息涌入人們的日常生活，而對(duì)于人們所需的信息的檢索就有了相當(dāng)了困難，搜索的結(jié)果要么是雜亂無章，要么不能達(dá)到令人滿意的效果。因此建立特定領(lǐng)域?qū)I(yè)化網(wǎng)絡(luò)檢索系統(tǒng)[1]是一個(gè)行之有效的措施。而聚焦爬蟲就是為了滿足這一要求誕生的，它以其爬蟲范圍緊貼主題，檢索效果既全又準(zhǔn)的優(yōu)勢贏得了開發(fā)人員的青睞。

1聚焦爬蟲

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

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

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

二是查準(zhǔn)率低下。正是因?yàn)榕老x冗余大，也就勢必造成檢索數(shù)據(jù)庫信息量劇增， 會(huì)檢索結(jié)果不能很好地達(dá)到預(yù)期目的。

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

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

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

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

圖2　聚焦爬蟲流程

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

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

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

三是檢索效果佳。因?yàn)槠渑老x范圍不僅小了許多，而且緊貼主題，所以對(duì)于檢索的效果會(huì)更好。

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

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í)間維數(shù)和頁面相關(guān)度。

2.1相關(guān)概念

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

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

2.2算法原理分析

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

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

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

(1)

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

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

(2)

假如一個(gè)Web超鏈接有向圖如圖3所示。

圖3　 Web 鏈接有向圖

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

(3)

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

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

(4)

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

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

圖4PageRank迭代求解算法

3Timed-PageRank改進(jìn)算法

3.1融入時(shí)間維度的PageRank改進(jìn)算法

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

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

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

(5)

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

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

(6)

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

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

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

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

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

(7)

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

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

(8)

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

4實(shí)例分析

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

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

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

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

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

5結(jié)論

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

參考文獻(xiàn)：

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

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

[3]周立柱,林玲.聚焦爬蟲技術(shù)研究綜述[J].計(jì)算機(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].計(jì)算機(jī)工程與設(shè)計(jì),2010,14:3309-3312.

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

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

(責(zé)任編輯蒲東)