基于語義相似聚合的主題爬蟲算法研究

吳林，王永濱

(1.中國傳媒大學 計算機與網絡中心，北京100024；2.中國傳媒大學 科技處，北京 100024)

1 引言

隨著互聯網技術的飛速發展，人們越來越多地參與到網絡活動中來，使得互聯網上的數據迅速膨脹，Web已經成為一個超級全球數據庫。如何讓用戶快速從海量數據中獲取有價值的個性化數據信息，成為當前研究的熱點。搜索引擎為用戶獲取有價值的信息提供了方便，但是搜索引擎返回的結果主題的垂直性不夠強，而主題爬蟲卻能夠為用戶提供更加精細和專業的信息查詢需求。

面對用戶越來越多的個性化需求，主題爬蟲營運而生。主題爬蟲是一種能夠下載特定主題網頁的計算機程序，它能夠根據人工設定的主題和抓取入口，從互聯網上大范圍采集主題相關的數據資源。根據主題爬蟲進行數據采集，構建專業化的主題數據庫，已經得到了非常廣泛的應用。

不同于普通的通用爬蟲，主題爬蟲是按照預先定義的爬蟲主題，在給定主題高度相關的URL種子之后，按照一定的分析算法，對網頁進行主題相關性分析，過濾主題不相關網頁的過程。但是傳統的主題爬蟲是基于通用的爬蟲策略，只能在抓取之后再根據網頁中包含的內容信息對網頁進行主題相關性評價。傳統的主題爬蟲采集數據時會浪費大量的時間采集主題不相關的網頁，并且將網絡鏈接的結構和內容相關性隔離開了。傳統的主題爬蟲在數據采集的時候只考慮鏈接地址的結構，不考慮網頁內容的主題相關性；計算網頁內容的主題相關性時，忽略了鏈接結構之間的關聯關系。

針對以上問題，本文在研究傳統PageRank算法的基礎上提出了一種基于語義相似聚合的主題爬蟲算法，創新點在于：

1.提出了網頁主題和鏈接結構結合的主題聚合算法，將傳統主題采集時內容評價和數據采集兩個隔離的計算過程結合在一起，在計算主題相關性時充分考慮網頁內容主題相關性和鏈接結構權重的影響；

2.在鏈接結構和內容結合的基礎上，提出了語義相似聚合方法，進一步一高了主題數據采集的查全率。

2 相關工作

大量的研究者們為了進行高效的主題爬蟲，提出了許多與主題爬蟲相關的爬行算法和爬行策略。傳統的主題爬蟲分為兩類：基于文字內容的主題爬蟲評價方法和基于Web超鏈接結構的主題爬蟲評價方法。其中基于文字內容的主題爬蟲方法主要有魚群搜索方法(Fish-Search)[1]、鯊魚搜索方法(Shark-Search)[2]和最佳優先方法(best-first-Search)[3]。此類方法一般是先下載網頁，然后再比較網頁內容是否與主題相關。基于文字內容的方法只考慮文字內容，卻忽略了超鏈接行程的網絡有向圖對于主題爬蟲的影響。而基于Web超鏈接結構的評價算法主要有PageRank算法和HITS(Hyperlink-Induced Topic Search)。Brin S和Page L[4]提出了著名的PageRanks算法，該算法指出與越多重要網頁關聯的網頁，其權威性也更高。康奈爾大學(Cornell)的Kleinberg J[5]博士首先提出HITS算法，該算法建立在鏈接的基礎之上，對每一個網頁的內容全維度做了評價的基礎上再對頁面的鏈接全維度進行評價，最后給出網頁的綜合評價。近年來，許多新方法也不斷被應用到主題爬蟲。譚嘯[6]將本體引入到主題爬蟲中來，極大地提高了主題爬蟲的查全率。崔金國[7]比較了基于蟻群算法的主題爬蟲和傳統的主題爬蟲兩者的不同，得出結論基于蟻群算法的主題爬蟲技術能夠更好地指導主題爬蟲。

3 語義相似聚合算法原理

3.1 傳統PageRank算法

PageRank算法是一種網頁重要性評價算法，目前很多重要的權威性分析算法都是在PageRank算法的基礎上衍生出來得。PageRank算法的權威性計算思想分為兩部分：1)一個網頁中包含其他重要網頁，也即此網頁的html源代碼中包含一個高權重的重要連接，那么該網頁的權威性就更高；2)一個網頁被其他重要網頁指向，即其他重要網頁的源代碼中包含此網頁的鏈接地址，那么該網頁的權威性也更高。

若一個網站內的一組網頁相互指向行程環，而不指向組外的鏈接，這時候PageRank的權威性就不會向外分配，導致不斷迭代的PageRank值累加，最終影響計算結果。所以該算法加入了阻尼系數d，經驗取值為d=0.85，使得PageRank算法可以以一定的概率重新選擇一個網頁來初始化PageRank，然后多次迭代。該算法的計算公式如下：

(1)

其中Pi是被研究的某個鏈接對象，L(Pi)是Pi鏈出的網頁總數量，n表示鏈入的網頁總數量，PageRank(Pj)是鏈接到網頁Pi的網頁Pj的PageRank值。

3.2 語義相似主題聚合爬蟲算法

PageRank算法是計算網頁鏈接權威性的經典算法，但是該算法只考慮的網頁鏈接的結構，并沒有考慮到網頁內容的相關性，所以并不能用來進行主題爬蟲。本文通過改進PageRank算法，設計了基于語義相似聚合的主題爬蟲算法，該算法通過計算人工給定關鍵詞與網頁中內容的關聯關系來計算網頁內容的主題相關性。算法的詳細過程闡述如下。

首先人工設定一組主題相關的關鍵詞特征向量WORD=(word1，word2，…，wordm)，每個關鍵詞的主題相關權重為W′=(α1，α2，…，αm)，WORDi=(wordi1，wordi2，…，wordix)為W′中第i個單詞的相似詞向量，其中wordiWORDi，wordij為與關鍵詞αi語義相似的詞，令Wi=(wi1，wi2，…，wix)為αi與wordij的相似度。然后根據網頁正文提取算法，將網頁中正文內容提取出來，形成網頁正文的特征向量β1，β2，…，βm)，使得每一個網頁都生成與給定關鍵詞組成的向量空間模型。對于網頁中任意一個單詞wordkWORDi，基于內容的βi的計算方法如下：

(2)

考慮制定特征詞的相似詞WORDi之后，上述公式改進為：

(3)

其中m為人工指定特征詞的個數，α代表指定關鍵詞權重，β代表網頁正文中所有與指定關鍵詞相關的詞的權重之和的權重。

(4)

在具體實現的計算過程中，利用上述公式多次迭代計算PageRank(Pi)，直到最終收斂時得到的計算結果，即為網頁Pi和指定主題之間的關聯程度。

4 實驗結果及評價

本文的主題爬蟲根據人工預設先設置一組關鍵詞，并設置相應的權重，來抓取網頁。實驗時以“中國傳統文化”作為主題抓取數據，以百度搜索引擎檢索到的頁面為種子鏈接地址進行抓取。本文旨在評價主題相關網頁的采集，采用查準率作為性能評價指標，其公式如下：

實驗設置的關鍵詞向量如表1所示。

表1 關鍵司

本文將統計在相關度不同的情況下，PageRank算法、基于內容的PageRank算法和基于語義相似聚合的PageRan算法的對比結果。其中基于語義相似聚合的PageRan算法，以同義詞詞林[8]為基礎計算上述關鍵詞的相似詞及相似度。同時，我們從已經抓取到的網頁中隨機抽取200個，然后人工統計與“中國傳統文化”相關的網頁的個數。實驗結果如表2所示。

表2 實驗結果

由上述結果可見，傳統的PageRank算法進行主題抓取效果比較差，在加入了主題相似計算之后，查準率大幅度提升。在主題相關性計算的基礎上，添加了近義詞相似語義計算，查準率提升了20.2%。

原始的PageRank算法進行抓取的時候，無法區分主題是否相關，無法分辨內容是否相關；添加主題相關性之后，原始的PageRank算法計算的過程中也會考慮到網頁鏈接的主題相關性因素，所以查準率大幅度提升；添加了基于近義詞之后，主題相關性計算考慮得更全面了，等于對給定關鍵詞進行了語義擴展，所以查準率有20.2%的提升。

5 結束語

本文在研究了傳統的PageRank的基礎上，創造性地將鏈接結構和網頁內容相關性結合在一起，提出了一種基于語義相似聚合的主題爬蟲方法。它讓PageRank算法在計算網頁的權重時考慮網頁本身與主題的相關性，同時通過同義詞詞林擴展人工給定的關鍵詞集合，使得主題計算更加精確。實驗結果表明，本文提出的基于語義相似聚合的主題爬蟲在抓取數據時，有很高的主題相關查全率。

[1]De Bra P M E，Post R D J.Information retrieval in the Worldwide Web：Making client-based searching feasible[J].Computer Networks and ISDN Systems，1994，27(2)：183-192.

[2]Hersovici M，Jacovi M，Maarek Y S.The shark-search algorithm.An application：tailored Web site mapping[J].Computer Networks and ISDN Systems，1998，30(1)：317-326.

[3]Menczer F，Pant G，Srinivasan P.Topical web crawlers：Evaluating adaptive algorithms[J].ACM Transactions on Internet Technology(TOIT)，2004，4(4)：378-419.

[4]Page L，Brins，Motwani R.The PageRank citation ranking：Bringing order to the web[R].Technical Report SIDL-WO-1999-012，standford：Standford Laboratory，1999.

[5]Kleinberg J M.Authoritative sources in a hyperlinked environment[J].Journal of the ACM(JACM)，1999，46(5)：604-632.

[6]譚嘯.基于本體的網絡爬蟲設計及應用[D].電子科技大學，2015.

[7]崔金國.基于蟻群算法的主題爬蟲技術研究與實現[D].成都理工大學，2010.

[8]田久樂，趙蔚.基于同義詞詞林的詞語相似度計算方法[J].吉林大學學報，2010，6(28).