基于Viterbi算法的網頁分類排序動態爬蟲策略

張鴻飛 邵玉斌 龍華 杜慶治

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

關鍵詞：網頁排名；爬蟲策略；Viterbi算法

DOI：10.11907/rjdk.172674

中圖分類號：TP312

文獻標識碼：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 引言

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

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

綜合以上問題，本文采用基于Viterbi算法[7]的動態分析思想，利用網頁入鏈數量和網頁內容與主題相關度兩個參量，在逐層訪問的過程中選取綜合條件最優的網站，優勝劣汰，形成Viterbi過程，將靜態的網頁評價轉化為動態學習過程，提高收集分類主題網站綜合重要性最高網頁的效率和準確性、全面性。

1 網頁分類排序動態爬蟲策略模型

1.1 模型框架設計

動態網絡爬蟲流程如圖1所示。

1.2 網頁分類排序動態爬蟲策略

在互聯網中，任一分類主題條件下，一個網頁的綜合評價主要由兩方面決定：入鏈數和主題相關度[8]。入鏈數代表網頁在該主題互聯網環境內的受歡迎程度，入鏈數越大表示越受歡迎，越容易被訪問。主題相關度代表網頁在該主題領域內的專業度，相關度越大表示越專業，在該領域越關注專業內容。本文中網頁的綜合評價公式如下：

其中，f是網頁綜合評價值；LV為網頁鏈接價值；CV為網頁內容價值；φ1與φ2分別為網頁鏈接價值和網頁內容價值的權值，設φ1=0.7，φ2=0.3。

1.2.1 網頁鏈接價值與內容價值

網頁鏈接價值計算公式如下：

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

網頁內容價值是通過TF-IDF算法[10]計算的。

詞頻統計公式如下：

其中，TF為詞頻，wi為某詞在網頁中出現的次數，ws為網頁中詞的總數。

逆文檔頻率公式如下：

其中，IDF為逆文檔頻率，D為文檔總數，DW為某詞出現的文檔數。

網頁內容價值計算公式如下：

其中，G為某個詞的TF-IDF值，Key為網頁中t個關鍵詞的G集合，CV為網頁內容價值，n為Key集合中主題詞的數量，N為Key集合數量。

1.2.2 維特比過程

Viterbi算法思想為：若每個狀態取概率最大路徑，則最后得到最優路徑。公式體現為：

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

其中，xN為N個爬蟲節點，圖2中用橢圓圈住的部分為選取的網頁簇。

本文涉及到兩個評價標準：第一個由式（1）表示，該標準處于網絡爬蟲結束后，是網頁靜態評價值；第二個評價標準處在維特比過程中。在維特比過程中，為了體現出網絡鏈接結構信息以及網絡結構中父代鏈接對子代鏈接的影響，引入了轉移轉移權值w。將轉移權值與靜態評價值相乘可以得到帶有父代鏈接信息的綜合評價值。

動態網頁綜合價值評價公式如下：

其中，wi為某節點中第i個網頁的權值，fi為該網頁的靜態綜合評價值。Wi為第i節點中的網頁作為父代鏈接的轉移權值矩陣，M為父代鏈接與子代鏈接的關系矩陣，mij（i∈m，j∈n）的取值為0或1，0代表非從屬關系，1指代父子鏈接關系。Qi為第i個節點中由個網頁靜態評價值組成的靜態評價矩陣，Fi為第i個節點中子代的動態網頁評價值矩陣。

2 實驗仿真與分析

實驗系統使用Python（2.7版本）編程語言，在Eclipse（4.6.3版本）平臺下開發，數據庫為MySQL（5.0.22版本）。

2.1 參數選擇

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

由于互聯網中任意主題的網頁鏈接結構并不是全連通，本算法模擬用戶瀏覽網頁的動作具有局部性，這樣會導致一次實驗并不一定能得到目標網站，因此需要多次實驗得到某主題的重要網站。

2.2 評價指標

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

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

查全率=通過動態或PageRank算法得出的網站靜態算法得出的網站 （14）

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

2.3 實驗結果

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

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

從圖4、圖6、圖8可以看出，經過大數量試驗，系統得到的目標網站越來越接近候選網站，直到候選網站全部選出。

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

3 結語

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

參考文獻：

[1] 孫立偉，何國輝，吳禮發.網絡爬蟲技術的研究[J].電腦知識與技術，2010，6（15）：4112-4115.

[2] 周立柱，林玲.聚焦爬蟲技術研究綜述[J].計算機應用，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，等.基于網頁鏈接和內容分析的改進PageRank算法[J].計算機工程與應用，2007，43（21）：160-164.

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

[7] 李航.統計學習方法[M].北京：清華大學出版社，2012.

[8] 徐寧.主題爬蟲搜索策略及關鍵技術研究[D].重慶：重慶大學，2015.

[9] 滕明鑫.回歸神經網絡預測模型歸一化方法分析[J].電腦知識與技術，2014，10（7）：1508-1510.

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

（責任編輯：何 麗）