張鴻飛 邵玉斌 龍華 杜慶治

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

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

DOI：10.11907/rjdk.172674

中圖分類號：TP312

文獻標(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]。其中一個關(guān)鍵問題是如何高效獲取分類主題網(wǎng)頁排序信息，網(wǎng)絡(luò)爬蟲技術(shù)應(yīng)運而生?；ヂ?lián)網(wǎng)是一個以網(wǎng)頁為結(jié)點、超鏈接為邊的有向圖，因此爬蟲過程就可以抽象為對這個有向圖的遍歷過程[2]。爬蟲分為兩大類：普通爬蟲與主題爬蟲。PageRank算法[3]與Fish-Search算法[4]是與之對應(yīng)的兩種廣泛應(yīng)用的網(wǎng)頁排序算法。

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

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

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

1.1 模型框架設(shè)計

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

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

在互聯(lián)網(wǎng)中，任一分類主題條件下，一個網(wǎng)頁的綜合評價主要由兩方面決定：入鏈數(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)頁的綜合評價公式如下：

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

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

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

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

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

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

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

逆文檔頻率公式如下：

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

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

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

1.2.2 維特比過程

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

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

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

本文涉及到兩個評價標(biāo)準(zhǔn)：第一個由式（1）表示，該標(biāo)準(zhǔn)處于網(wǎng)絡(luò)爬蟲結(jié)束后，是網(wǎng)頁靜態(tài)評價值；第二個評價標(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)評價值相乘可以得到帶有父代鏈接信息的綜合評價值。

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

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

2 實驗仿真與分析

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

2.1 參數(shù)選擇

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

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

2.2 評價指標(biāo)

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

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

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

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

2.3 實驗結(jié)果

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

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

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

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

3 結(jié)語

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

參考文獻：

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

[2] 周立柱，林玲.聚焦爬蟲技術(shù)研究綜述[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)容分析的改進PageRank算法[J].計算機工程與應(yīng)用，2007，43（21）：160-164.

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

[7] 李航.統(tǒng)計學(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] 周源，劉懷蘭，杜鵬鵬，等.基于改進TF-IDF特征提取的文本分類模型研究[J].情報科學(xué)，2017，35（5）：111-118.

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