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

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

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

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

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

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

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

收稿日期：2014-06-27

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

1聚焦爬蟲(chóng)

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

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

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

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

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

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

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

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

圖2　聚焦爬蟲(chóng)流程

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

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

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

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

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

2PageRank算法

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

2.1相關(guān)概念

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

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

2.2算法原理分析

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

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

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

(1)

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

(4)

該算法可以賦予任意的PageRank值初始值，經(jīng)過(guò)反復(fù)迭代，當(dāng)PageRank值不再發(fā)生顯著變化或是趨于收斂時(shí)，算法結(jié)束，其迭代[5]求解算法如圖4所示，當(dāng)差值向量的1階范數(shù)小于網(wǎng)頁(yè)相關(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)頁(yè)的一個(gè)顯著特征就是網(wǎng)頁(yè)的動(dòng)態(tài)性，它將不斷隨著時(shí)間的推移而不斷的變化，因此它具有良好的時(shí)效性，而傳統(tǒng)網(wǎng)絡(luò)爬蟲(chóng)的不足之處就是沒(méi)有考慮和處理網(wǎng)頁(yè)檢索結(jié)果的時(shí)效性，因此不能很好地滿足用戶的檢索需求。

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

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

(5)

式(5)中：t表示當(dāng)前時(shí)間和上次網(wǎng)頁(yè)更新時(shí)間的月份差值。網(wǎng)頁(yè)越新，t值越小，其時(shí)間權(quán)值就越大，這樣就能有效地區(qū)調(diào)整新舊網(wǎng)頁(yè)的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)為頁(yè)面i的時(shí)間權(quán)值。

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

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

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

一般而言，標(biāo)題關(guān)鍵字的權(quán)重要大于內(nèi)容共同詞語(yǔ)頻度的權(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，則頁(yè)面i與待檢索主題相關(guān)度Sim(i) 計(jì)算公式為

(7)

綜合以上兩種PageRank改進(jìn)算法，則新的改進(jìn)算法將由兩部分組成：一是融入時(shí)間維度的PageRank改進(jìn)算法，二是融入頁(yè)面內(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)行聚焦爬蟲(chóng)的過(guò)程中，要對(duì)待爬取的網(wǎng)頁(yè)進(jìn)行相關(guān)度計(jì)算，便可運(yùn)用式(8)計(jì)算其與主題的相關(guān)度，看其是否滿足爬蟲(chóng)前預(yù)先設(shè)置好的爬取閾值，若滿足，則爬取，否則丟棄。

4實(shí)例分析

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

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

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

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

圖5　基于2種不同算法的爬蟲(chóng)效果示意圖

5結(jié)論

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

參考文獻(xiàn)：

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

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

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

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

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

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

[7]張翔,周明全,李智杰,等.基于PageRank與Bagging的主題爬蟲(chóng)研究[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)頁(yè)質(zhì)量的PageRank算法改進(jìn)[C]//中國(guó)計(jì)算機(jī)學(xué)會(huì)數(shù)據(jù)庫(kù)專業(yè)委員會(huì).第26屆中國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集(B輯).中國(guó)計(jì)算機(jī)學(xué)會(huì)數(shù)據(jù)庫(kù)專業(yè)委員會(huì),2009:

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