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

吳林，王永濱

(1.中國傳媒大學(xué) 計(jì)算機(jī)與網(wǎng)絡(luò)中心，北京100024；2.中國傳媒大學(xué) 科技處，北京 100024)

1 引言

隨著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，人們越來越多地參與到網(wǎng)絡(luò)活動中來，使得互聯(lián)網(wǎng)上的數(shù)據(jù)迅速膨脹，Web已經(jīng)成為一個(gè)超級全球數(shù)據(jù)庫。如何讓用戶快速從海量數(shù)據(jù)中獲取有價(jià)值的個(gè)性化數(shù)據(jù)信息，成為當(dāng)前研究的熱點(diǎn)。搜索引擎為用戶獲取有價(jià)值的信息提供了方便，但是搜索引擎返回的結(jié)果主題的垂直性不夠強(qiáng)，而主題爬蟲卻能夠?yàn)橛脩籼峁└泳?xì)和專業(yè)的信息查詢需求。

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

不同于普通的通用爬蟲，主題爬蟲是按照預(yù)先定義的爬蟲主題，在給定主題高度相關(guān)的URL種子之后，按照一定的分析算法，對網(wǎng)頁進(jìn)行主題相關(guān)性分析，過濾主題不相關(guān)網(wǎng)頁的過程。但是傳統(tǒng)的主題爬蟲是基于通用的爬蟲策略，只能在抓取之后再根據(jù)網(wǎng)頁中包含的內(nèi)容信息對網(wǎng)頁進(jìn)行主題相關(guān)性評價(jià)。傳統(tǒng)的主題爬蟲采集數(shù)據(jù)時(shí)會浪費(fèi)大量的時(shí)間采集主題不相關(guān)的網(wǎng)頁，并且將網(wǎng)絡(luò)鏈接的結(jié)構(gòu)和內(nèi)容相關(guān)性隔離開了。傳統(tǒng)的主題爬蟲在數(shù)據(jù)采集的時(shí)候只考慮鏈接地址的結(jié)構(gòu)，不考慮網(wǎng)頁內(nèi)容的主題相關(guān)性；計(jì)算網(wǎng)頁內(nèi)容的主題相關(guān)性時(shí)，忽略了鏈接結(jié)構(gòu)之間的關(guān)聯(lián)關(guān)系。

針對以上問題，本文在研究傳統(tǒng)PageRank算法的基礎(chǔ)上提出了一種基于語義相似聚合的主題爬蟲算法，創(chuàng)新點(diǎn)在于：

1.提出了網(wǎng)頁主題和鏈接結(jié)構(gòu)結(jié)合的主題聚合算法，將傳統(tǒng)主題采集時(shí)內(nèi)容評價(jià)和數(shù)據(jù)采集兩個(gè)隔離的計(jì)算過程結(jié)合在一起，在計(jì)算主題相關(guān)性時(shí)充分考慮網(wǎng)頁內(nèi)容主題相關(guān)性和鏈接結(jié)構(gòu)權(quán)重的影響；

2.在鏈接結(jié)構(gòu)和內(nèi)容結(jié)合的基礎(chǔ)上，提出了語義相似聚合方法，進(jìn)一步一高了主題數(shù)據(jù)采集的查全率。

2 相關(guān)工作

大量的研究者們?yōu)榱诉M(jìn)行高效的主題爬蟲，提出了許多與主題爬蟲相關(guān)的爬行算法和爬行策略。傳統(tǒng)的主題爬蟲分為兩類：基于文字內(nèi)容的主題爬蟲評價(jià)方法和基于Web超鏈接結(jié)構(gòu)的主題爬蟲評價(jià)方法。其中基于文字內(nèi)容的主題爬蟲方法主要有魚群搜索方法(Fish-Search)[1]、鯊魚搜索方法(Shark-Search)[2]和最佳優(yōu)先方法(best-first-Search)[3]。此類方法一般是先下載網(wǎng)頁，然后再比較網(wǎng)頁內(nèi)容是否與主題相關(guān)?；谖淖謨?nèi)容的方法只考慮文字內(nèi)容，卻忽略了超鏈接行程的網(wǎng)絡(luò)有向圖對于主題爬蟲的影響。而基于Web超鏈接結(jié)構(gòu)的評價(jià)算法主要有PageRank算法和HITS(Hyperlink-Induced Topic Search)。Brin S和Page L[4]提出了著名的PageRanks算法，該算法指出與越多重要網(wǎng)頁關(guān)聯(lián)的網(wǎng)頁，其權(quán)威性也更高?？的螤柎髮W(xué)(Cornell)的Kleinberg J[5]博士首先提出HITS算法，該算法建立在鏈接的基礎(chǔ)之上，對每一個(gè)網(wǎng)頁的內(nèi)容全維度做了評價(jià)的基礎(chǔ)上再對頁面的鏈接全維度進(jìn)行評價(jià)，最后給出網(wǎng)頁的綜合評價(jià)。近年來，許多新方法也不斷被應(yīng)用到主題爬蟲。譚嘯[6]將本體引入到主題爬蟲中來，極大地提高了主題爬蟲的查全率。崔金國[7]比較了基于蟻群算法的主題爬蟲和傳統(tǒng)的主題爬蟲兩者的不同，得出結(jié)論基于蟻群算法的主題爬蟲技術(shù)能夠更好地指導(dǎo)主題爬蟲。

3 語義相似聚合算法原理

3.1 傳統(tǒng)PageRank算法

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

若一個(gè)網(wǎng)站內(nèi)的一組網(wǎng)頁相互指向行程環(huán)，而不指向組外的鏈接，這時(shí)候PageRank的權(quán)威性就不會向外分配，導(dǎo)致不斷迭代的PageRank值累加，最終影響計(jì)算結(jié)果。所以該算法加入了阻尼系數(shù)d，經(jīng)驗(yàn)取值為d=0.85，使得PageRank算法可以以一定的概率重新選擇一個(gè)網(wǎng)頁來初始化PageRank，然后多次迭代。該算法的計(jì)算公式如下：

(1)

其中Pi是被研究的某個(gè)鏈接對象，L(Pi)是Pi鏈出的網(wǎng)頁總數(shù)量，n表示鏈入的網(wǎng)頁總數(shù)量，PageRank(Pj)是鏈接到網(wǎng)頁P(yáng)i的網(wǎng)頁P(yáng)j的PageRank值。

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

PageRank算法是計(jì)算網(wǎng)頁鏈接權(quán)威性的經(jīng)典算法，但是該算法只考慮的網(wǎng)頁鏈接的結(jié)構(gòu)，并沒有考慮到網(wǎng)頁內(nèi)容的相關(guān)性，所以并不能用來進(jìn)行主題爬蟲。本文通過改進(jìn)PageRank算法，設(shè)計(jì)了基于語義相似聚合的主題爬蟲算法，該算法通過計(jì)算人工給定關(guān)鍵詞與網(wǎng)頁中內(nèi)容的關(guān)聯(lián)關(guān)系來計(jì)算網(wǎng)頁內(nèi)容的主題相關(guān)性。算法的詳細(xì)過程闡述如下。

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

(2)

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

(3)

其中m為人工指定特征詞的個(gè)數(shù)，α代表指定關(guān)鍵詞權(quán)重，β代表網(wǎng)頁正文中所有與指定關(guān)鍵詞相關(guān)的詞的權(quán)重之和的權(quán)重。

(4)

在具體實(shí)現(xiàn)的計(jì)算過程中，利用上述公式多次迭代計(jì)算PageRank(Pi)，直到最終收斂時(shí)得到的計(jì)算結(jié)果，即為網(wǎng)頁P(yáng)i和指定主題之間的關(guān)聯(lián)程度。

4 實(shí)驗(yàn)結(jié)果及評價(jià)

本文的主題爬蟲根據(jù)人工預(yù)設(shè)先設(shè)置一組關(guān)鍵詞，并設(shè)置相應(yīng)的權(quán)重，來抓取網(wǎng)頁。實(shí)驗(yàn)時(shí)以“中國傳統(tǒng)文化”作為主題抓取數(shù)據(jù)，以百度搜索引擎檢索到的頁面為種子鏈接地址進(jìn)行抓取。本文旨在評價(jià)主題相關(guān)網(wǎng)頁的采集，采用查準(zhǔn)率作為性能評價(jià)指標(biāo)，其公式如下：

實(shí)驗(yàn)設(shè)置的關(guān)鍵詞向量如表1所示。

表1 關(guān)鍵司

本文將統(tǒng)計(jì)在相關(guān)度不同的情況下，PageRank算法、基于內(nèi)容的PageRank算法和基于語義相似聚合的PageRan算法的對比結(jié)果。其中基于語義相似聚合的PageRan算法，以同義詞詞林[8]為基礎(chǔ)計(jì)算上述關(guān)鍵詞的相似詞及相似度。同時(shí)，我們從已經(jīng)抓取到的網(wǎng)頁中隨機(jī)抽取200個(gè)，然后人工統(tǒng)計(jì)與“中國傳統(tǒng)文化”相關(guān)的網(wǎng)頁的個(gè)數(shù)。實(shí)驗(yàn)結(jié)果如表2所示。

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

由上述結(jié)果可見，傳統(tǒng)的PageRank算法進(jìn)行主題抓取效果比較差，在加入了主題相似計(jì)算之后，查準(zhǔn)率大幅度提升。在主題相關(guān)性計(jì)算的基礎(chǔ)上，添加了近義詞相似語義計(jì)算，查準(zhǔn)率提升了20.2%。

原始的PageRank算法進(jìn)行抓取的時(shí)候，無法區(qū)分主題是否相關(guān)，無法分辨內(nèi)容是否相關(guān)；添加主題相關(guān)性之后，原始的PageRank算法計(jì)算的過程中也會考慮到網(wǎng)頁鏈接的主題相關(guān)性因素，所以查準(zhǔn)率大幅度提升；添加了基于近義詞之后，主題相關(guān)性計(jì)算考慮得更全面了，等于對給定關(guān)鍵詞進(jìn)行了語義擴(kuò)展，所以查準(zhǔn)率有20.2%的提升。

5 結(jié)束語

本文在研究了傳統(tǒng)的PageRank的基礎(chǔ)上，創(chuàng)造性地將鏈接結(jié)構(gòu)和網(wǎng)頁內(nèi)容相關(guān)性結(jié)合在一起，提出了一種基于語義相似聚合的主題爬蟲方法。它讓PageRank算法在計(jì)算網(wǎng)頁的權(quán)重時(shí)考慮網(wǎng)頁本身與主題的相關(guān)性，同時(shí)通過同義詞詞林?jǐn)U展人工給定的關(guān)鍵詞集合，使得主題計(jì)算更加精確。實(shí)驗(yàn)結(jié)果表明，本文提出的基于語義相似聚合的主題爬蟲在抓取數(shù)據(jù)時(shí)，有很高的主題相關(guān)查全率。

[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]譚嘯.基于本體的網(wǎng)絡(luò)爬蟲設(shè)計(jì)及應(yīng)用[D].電子科技大學(xué)，2015.

[7]崔金國.基于蟻群算法的主題爬蟲技術(shù)研究與實(shí)現(xiàn)[D].成都理工大學(xué)，2010.

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