基于Viterbi算法的網(wǎng)頁分類排序動(dòng)態(tài)爬蟲策略

張鴻飛 邵玉斌 龍華 杜慶治

摘 要：Viterbi算法是一種基于圖的動(dòng)態(tài)規(guī)劃算法，用于解決最短路徑問題。針對當(dāng)前網(wǎng)站排序算法對網(wǎng)站排名存在忽略網(wǎng)站主題、新站點(diǎn)排名無法超越舊站點(diǎn)等問題，提出了一種改進(jìn)算法。改進(jìn)算法利用網(wǎng)站入鏈數(shù)量以及網(wǎng)站內(nèi)容與主題相關(guān)度兩個(gè)參量，結(jié)合Viterbi算法思想，在逐層訪問過程中選取綜合條件最優(yōu)的網(wǎng)站，優(yōu)勝劣汰，形成Viterbi過程，提高分類網(wǎng)站排序的效率和準(zhǔn)確性。實(shí)驗(yàn)驗(yàn)證了動(dòng)態(tài)爬蟲策略的有效性。

關(guān)鍵詞：網(wǎng)頁排名；爬蟲策略；Viterbi算法

DOI：10.11907/rjdk.172674

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2018）004-0047-04

Abstract：Viterbi algorithm is a map-based dynamical programming algorithm for solving the problem of seeking the shortest route.In this paper，an improved algorithm has been proposed to solve the problems when topics are ignored in page rank and the fact that newer pages cannot defeat the elder pages in ranking.To improve the efficiency and accuracy of classified sites ranking，the new algorithm employs two parameters （link-quantity and relativity of site） by abandoning lower importance sites in drill-down process.The results of the test show that the dynamical strategy can apparently improve efficiency and accuracy of classified sites ranking.

Key Words：web page rank； crawling strategy； Viterbi algorithm

0 引言

隨著互聯(lián)網(wǎng)的飛速發(fā)展，網(wǎng)絡(luò)信息資源急劇膨脹，信息高效、準(zhǔn)確、全面采集成為熱門的研究課題[1]。其中一個(gè)關(guān)鍵問題是如何高效獲取分類主題網(wǎng)頁排序信息，網(wǎng)絡(luò)爬蟲技術(shù)應(yīng)運(yùn)而生。互聯(lián)網(wǎng)是一個(gè)以網(wǎng)頁為結(jié)點(diǎn)、超鏈接為邊的有向圖，因此爬蟲過程就可以抽象為對這個(gè)有向圖的遍歷過程[2]。爬蟲分為兩大類：普通爬蟲與主題爬蟲。PageRank算法[3]與Fish-Search算法[4]是與之對應(yīng)的兩種廣泛應(yīng)用的網(wǎng)頁排序算法。

PageRank算法的核心是計(jì)算網(wǎng)頁質(zhì)量，通過計(jì)算網(wǎng)頁被鏈接的次數(shù)，衡量一個(gè)網(wǎng)頁的質(zhì)量在整個(gè)互聯(lián)網(wǎng)中的水平，從而根據(jù)質(zhì)量大小找出互聯(lián)網(wǎng)中受歡迎的網(wǎng)站。但是該算法忽略了網(wǎng)頁的主體性，無法針對用戶鍵入的主題獲取相關(guān)主題的重要網(wǎng)站，并且還存在耗時(shí)長的缺點(diǎn)[5]。Fish-Search算法可以滿足用戶搜索相關(guān)主題信息的要求，但是只分析了子鏈接的文本相關(guān)程度，忽略網(wǎng)絡(luò)鏈接結(jié)構(gòu)信息，導(dǎo)致結(jié)果不準(zhǔn)確[6]。

綜合以上問題，本文采用基于Viterbi算法[7]的動(dòng)態(tài)分析思想，利用網(wǎng)頁入鏈數(shù)量和網(wǎng)頁內(nèi)容與主題相關(guān)度兩個(gè)參量，在逐層訪問的過程中選取綜合條件最優(yōu)的網(wǎng)站，優(yōu)勝劣汰，形成Viterbi過程，將靜態(tài)的網(wǎng)頁評價(jià)轉(zhuǎn)化為動(dòng)態(tài)學(xué)習(xí)過程，提高收集分類主題網(wǎng)站綜合重要性最高網(wǎng)頁的效率和準(zhǔn)確性、全面性。

1 網(wǎng)頁分類排序動(dòng)態(tài)爬蟲策略模型

1.1 模型框架設(shè)計(jì)

動(dòng)態(tài)網(wǎng)絡(luò)爬蟲流程如圖1所示。

1.2 網(wǎng)頁分類排序動(dòng)態(tài)爬蟲策略

在互聯(lián)網(wǎng)中，任一分類主題條件下，一個(gè)網(wǎng)頁的綜合評價(jià)主要由兩方面決定：入鏈數(shù)和主題相關(guān)度[8]。入鏈數(shù)代表網(wǎng)頁在該主題互聯(lián)網(wǎng)環(huán)境內(nèi)的受歡迎程度，入鏈數(shù)越大表示越受歡迎，越容易被訪問。主題相關(guān)度代表網(wǎng)頁在該主題領(lǐng)域內(nèi)的專業(yè)度，相關(guān)度越大表示越專業(yè)，在該領(lǐng)域越關(guān)注專業(yè)內(nèi)容。本文中網(wǎng)頁的綜合評價(jià)公式如下：

其中，f是網(wǎng)頁綜合評價(jià)值；LV為網(wǎng)頁鏈接價(jià)值；CV為網(wǎng)頁內(nèi)容價(jià)值；φ1與φ2分別為網(wǎng)頁鏈接價(jià)值和網(wǎng)頁內(nèi)容價(jià)值的權(quán)值，設(shè)φ1=0.7，φ2=0.3。

1.2.1 網(wǎng)頁鏈接價(jià)值與內(nèi)容價(jià)值

網(wǎng)頁鏈接價(jià)值計(jì)算公式如下：

其中，LN為網(wǎng)頁入鏈數(shù)。首先獲得網(wǎng)頁的入鏈數(shù)，通過反余切函數(shù)對入鏈數(shù)進(jìn)行歸一化處理[9]，得到網(wǎng)頁鏈接價(jià)值。

網(wǎng)頁內(nèi)容價(jià)值是通過TF-IDF算法[10]計(jì)算的。

詞頻統(tǒng)計(jì)公式如下：

其中，TF為詞頻，wi為某詞在網(wǎng)頁中出現(xiàn)的次數(shù)，ws為網(wǎng)頁中詞的總數(shù)。

逆文檔頻率公式如下：

其中，IDF為逆文檔頻率，D為文檔總數(shù)，DW為某詞出現(xiàn)的文檔數(shù)。

網(wǎng)頁內(nèi)容價(jià)值計(jì)算公式如下：

其中，G為某個(gè)詞的TF-IDF值，Key為網(wǎng)頁中t個(gè)關(guān)鍵詞的G集合，CV為網(wǎng)頁內(nèi)容價(jià)值，n為Key集合中主題詞的數(shù)量，N為Key集合數(shù)量。

1.2.2 維特比過程

Viterbi算法思想為：若每個(gè)狀態(tài)取概率最大路徑，則最后得到最優(yōu)路徑。公式體現(xiàn)為：

起始點(diǎn)到每個(gè)節(jié)點(diǎn)的最短距離結(jié)合后則可以得到整個(gè)過程的最優(yōu)路徑，也為最大概率路徑。將網(wǎng)絡(luò)爬蟲中每一層鏈接看作一個(gè)節(jié)點(diǎn)，若每個(gè)節(jié)點(diǎn)取最大概率網(wǎng)頁簇，則可以淘汰評價(jià)較低網(wǎng)頁，獲取評價(jià)較高網(wǎng)頁，實(shí)現(xiàn)最優(yōu)路徑。將利用Viterbi算法的網(wǎng)絡(luò)爬蟲過程稱之為維特比過程，如圖2所示。

其中，xN為N個(gè)爬蟲節(jié)點(diǎn)，圖2中用橢圓圈住的部分為選取的網(wǎng)頁簇。

本文涉及到兩個(gè)評價(jià)標(biāo)準(zhǔn)：第一個(gè)由式（1）表示，該標(biāo)準(zhǔn)處于網(wǎng)絡(luò)爬蟲結(jié)束后，是網(wǎng)頁靜態(tài)評價(jià)值；第二個(gè)評價(jià)標(biāo)準(zhǔn)處在維特比過程中。在維特比過程中，為了體現(xiàn)出網(wǎng)絡(luò)鏈接結(jié)構(gòu)信息以及網(wǎng)絡(luò)結(jié)構(gòu)中父代鏈接對子代鏈接的影響，引入了轉(zhuǎn)移轉(zhuǎn)移權(quán)值w。將轉(zhuǎn)移權(quán)值與靜態(tài)評價(jià)值相乘可以得到帶有父代鏈接信息的綜合評價(jià)值。

動(dòng)態(tài)網(wǎng)頁綜合價(jià)值評價(jià)公式如下：

其中，wi為某節(jié)點(diǎn)中第i個(gè)網(wǎng)頁的權(quán)值，fi為該網(wǎng)頁的靜態(tài)綜合評價(jià)值。Wi為第i節(jié)點(diǎn)中的網(wǎng)頁作為父代鏈接的轉(zhuǎn)移權(quán)值矩陣，M為父代鏈接與子代鏈接的關(guān)系矩陣，mij（i∈m，j∈n）的取值為0或1，0代表非從屬關(guān)系，1指代父子鏈接關(guān)系。Qi為第i個(gè)節(jié)點(diǎn)中由個(gè)網(wǎng)頁靜態(tài)評價(jià)值組成的靜態(tài)評價(jià)矩陣，F(xiàn)i為第i個(gè)節(jié)點(diǎn)中子代的動(dòng)態(tài)網(wǎng)頁評價(jià)值矩陣。

2 實(shí)驗(yàn)仿真與分析

實(shí)驗(yàn)系統(tǒng)使用Python（2.7版本）編程語言，在Eclipse（4.6.3版本）平臺下開發(fā)，數(shù)據(jù)庫為MySQL（5.0.22版本）。

2.1 參數(shù)選擇

仿真實(shí)驗(yàn)中，為模擬互聯(lián)網(wǎng)鏈接環(huán)境，通過python語言，在數(shù)據(jù)庫中隨機(jī)生成父子代網(wǎng)頁鏈接關(guān)系，共5 000個(gè)網(wǎng)頁。在真實(shí)網(wǎng)絡(luò)環(huán)境中存在某主題流行網(wǎng)站，頻繁被鏈接。通常情況下，在特定主題領(lǐng)域內(nèi)，越被頻繁鏈接，越能體現(xiàn)出其重要性。為實(shí)現(xiàn)仿真真實(shí)網(wǎng)絡(luò)環(huán)境中這一現(xiàn)象，人工設(shè)定5個(gè)網(wǎng)頁（下文稱為候選網(wǎng)站）：www1330、www732、www4434、www1643、www3957，被鏈接頻率（下文稱為播撒頻率）分別為3組，如表1所示。

由于互聯(lián)網(wǎng)中任意主題的網(wǎng)頁鏈接結(jié)構(gòu)并不是全連通，本算法模擬用戶瀏覽網(wǎng)頁的動(dòng)作具有局部性，這樣會導(dǎo)致一次實(shí)驗(yàn)并不一定能得到目標(biāo)網(wǎng)站，因此需要多次實(shí)驗(yàn)得到某主題的重要網(wǎng)站。

2.2 評價(jià)指標(biāo)

本次實(shí)驗(yàn)通過得到3種不同的計(jì)算方式：①利用已知鏈接結(jié)構(gòu)，算出所有網(wǎng)站的綜合評價(jià)值并排序，獲取前5個(gè)網(wǎng)站名；②利用PageRank算法，對已知鏈接結(jié)構(gòu)進(jìn)行遍歷和迭代，計(jì)算出所有網(wǎng)站的PR值并排序，獲取前5個(gè)網(wǎng)站名；③利用基于Viterbi算法的網(wǎng)頁分類排序動(dòng)態(tài)爬蟲策略，計(jì)算出訪問到網(wǎng)頁的綜合評價(jià)值并排序，獲取前5個(gè)網(wǎng)站名。

將PageRank算法和動(dòng)態(tài)爬蟲算法的結(jié)果與靜態(tài)計(jì)算出來的結(jié)果進(jìn)行比較，計(jì)算查全率，并進(jìn)行效果比較。查全率公式如下：

查全率=通過動(dòng)態(tài)或PageRank算法得出的網(wǎng)站靜態(tài)算法得出的網(wǎng)站 （14）

對PageRank算法和動(dòng)態(tài)算法在不同播撒率下計(jì)算出結(jié)果所用的時(shí)間進(jìn)行比較。

2.3 實(shí)驗(yàn)結(jié)果

本次實(shí)驗(yàn)分為兩部分：①設(shè)置不同播撒頻率（如Test1、Test2、Test3），通過系統(tǒng)中查全率的變化趨勢對比不同播撒率的系統(tǒng)學(xué)習(xí)性能；②設(shè)置不同播撒頻率，經(jīng)過多次實(shí)驗(yàn)（仿真將Test1、Test2、Test3分別進(jìn)行50次實(shí)驗(yàn)）得到某主題的重要網(wǎng)站，對比播撒頻率對于得出結(jié)果的影響。

從圖3、圖5、圖7可以看出，隨著候選網(wǎng)站播撒頻率的提高，動(dòng)態(tài)爬蟲系統(tǒng)的學(xué)習(xí)速率越大，所得結(jié)果的查全率越高。并且，當(dāng)任意特定候選網(wǎng)站的播撒頻率較小時(shí)，在系統(tǒng)多次學(xué)習(xí)后，可以得到候選網(wǎng)站外新的目標(biāo)網(wǎng)站。這說明系統(tǒng)綜合分析網(wǎng)站的鏈接數(shù)和網(wǎng)頁內(nèi)容與主題的相關(guān)度，得到新的網(wǎng)站綜合評價(jià)值大于部分候選網(wǎng)站，避免網(wǎng)站評價(jià)只受鏈接數(shù)量的影響，得到更加公平、綜合的網(wǎng)站。

從圖4、圖6、圖8可以看出，經(jīng)過大數(shù)量試驗(yàn)，系統(tǒng)得到的目標(biāo)網(wǎng)站越來越接近候選網(wǎng)站，直到候選網(wǎng)站全部選出。

從表2可以看出，Test1、Test2、Test3三種試驗(yàn)中，隨著候選網(wǎng)站播撒頻率提高，系統(tǒng)單次試驗(yàn)耗費(fèi)的時(shí)間變短。這是因?yàn)椴ト鲱l率越大，候選網(wǎng)站在互聯(lián)網(wǎng)中的分布密度越大，促進(jìn)主題網(wǎng)站鏈接環(huán)的形成。根據(jù)圖3判斷條件，減少學(xué)習(xí)節(jié)點(diǎn)，加速系統(tǒng)單次試驗(yàn)的完成。3種試驗(yàn)所消耗的時(shí)間遠(yuǎn)少于PageRank與全局靜態(tài)計(jì)算所消耗的時(shí)間。

3 結(jié)語

基于Viterbi算法的網(wǎng)頁分類排序動(dòng)態(tài)爬蟲策略評價(jià)網(wǎng)站在某一主題方面的重要性時(shí)，參考網(wǎng)站的入鏈數(shù)量以及網(wǎng)站內(nèi)容與主題的相關(guān)度，綜合地避免了PageRank算法上的缺陷。在動(dòng)態(tài)爬蟲過程中，結(jié)合父代鏈接的質(zhì)量，通過轉(zhuǎn)移權(quán)值矩陣，將父代鏈接質(zhì)量信息帶給子代鏈接，從而影響子代網(wǎng)頁在動(dòng)態(tài)學(xué)習(xí)過程中的動(dòng)態(tài)綜合評價(jià)值，通過淘汰低評價(jià)值，將較高評價(jià)值的網(wǎng)頁作為下一次的爬蟲父代鏈接，有效地提高了學(xué)習(xí)效率，減少許多不必要的訪問，從而大大減少了時(shí)間消耗。在這個(gè)過程中，有效解決了PageRank耗時(shí)長、Fish-Search忽略鏈接關(guān)系導(dǎo)致查詢結(jié)果不準(zhǔn)確的問題。動(dòng)態(tài)爬蟲策略在查全率上比全局靜態(tài)略低或相等，但是消耗時(shí)間大幅度降低，在實(shí)際應(yīng)用中，這對特定主題條件下高效、準(zhǔn)確、全面地篩選出重要網(wǎng)站具有實(shí)用意義。

參考文獻(xiàn)：

[1] 孫立偉，何國輝，吳禮發(fā).網(wǎng)絡(luò)爬蟲技術(shù)的研究[J].電腦知識與技術(shù)，2010，6（15）：4112-4115.

[2] 周立柱，林玲.聚焦爬蟲技術(shù)研究綜述[J].計(jì)算機(jī)應(yīng)用，2005，25（9）：1965-1969.

[3] BRIN S， PAGE L. The anatomy of a large-scale hypertextual web search engine[J]. Computer Networks and ISDN Systems，1998，30（4）：107-117.

[4] DE BRA P M E， POST R D J. Searching for arbitrary information in the WWW：the fish-search for mosaic[DB/OL].1994-10-06.http：//archive.ncsa.uiuc.edu/SDG/IT94/Proceedings/Searching/debra/article.html.

[5] 錢功偉，倪林，MIAO Y，等.基于網(wǎng)頁鏈接和內(nèi)容分析的改進(jìn)PageRank算法[J].計(jì)算機(jī)工程與應(yīng)用，2007，43（21）：160-164.

[6] 羅方芳，陳國龍，郭文忠.基于改進(jìn)的Fish-Search算法的信息檢索研究[J].福州大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，49（21）：42-45.

[7] 李航.統(tǒng)計(jì)學(xué)習(xí)方法[M].北京：清華大學(xué)出版社，2012.

[8] 徐寧.主題爬蟲搜索策略及關(guān)鍵技術(shù)研究[D].重慶：重慶大學(xué)，2015.

[9] 滕明鑫.回歸神經(jīng)網(wǎng)絡(luò)預(yù)測模型歸一化方法分析[J].電腦知識與技術(shù)，2014，10（7）：1508-1510.

[10] 周源，劉懷蘭，杜鵬鵬，等.基于改進(jìn)TF-IDF特征提取的文本分類模型研究[J].情報(bào)科學(xué)，2017，35（5）：111-118.

（責(zé)任編輯：何 麗）