主題爬蟲的主題相關(guān)度算法研究

徐楊，王未央（上海海事大學(xué)信息工程學(xué)院，上?！?01306）

?

主題爬蟲的主題相關(guān)度算法研究

徐楊，王未央
（上海海事大學(xué)信息工程學(xué)院，上海201306）

摘要：

關(guān)鍵詞：

0　引言

伴隨著互聯(lián)網(wǎng)的發(fā)展，網(wǎng)絡(luò)資源日益豐富。傳統(tǒng)通用搜索引擎的弊端日益突顯，資源的覆蓋率、搜索結(jié)果的準(zhǔn)確性和相關(guān)性均有所下降，用戶的搜索難度日益增大。于是，垂直搜索引擎應(yīng)運而生，在近幾年得到了快速的發(fā)展，并成為搜索引擎領(lǐng)域的發(fā)展的熱點和難點之一。

對于搜索引擎而言，網(wǎng)絡(luò)爬蟲是核心模塊。在傳統(tǒng)搜索引擎中，網(wǎng)絡(luò)爬蟲將網(wǎng)絡(luò)資源不加區(qū)分地爬取下來，然后通過以PageRank算法為核心的排序算法對網(wǎng)頁進行打分，并按得分高低排序。而垂直搜索引擎則是針對特定主題的網(wǎng)絡(luò)資源進行下載和整合的，具有更專業(yè)、更具體，以及更高的主題相關(guān)度。主題爬蟲是垂直搜索引擎為用戶提供高相關(guān)度檢索結(jié)果的核心部分所在。

針對主題爬蟲的主題相關(guān)度識別，本文提出一種利用兩步向量空間模型算法的主題相關(guān)度識別的方法。第一步空間向量模型算法用于計算當(dāng)前頁面的主題相關(guān)度，第二步空間向量模型算法用于計算當(dāng)前頁面所包含所有出度鏈接的主題相關(guān)度，用于對當(dāng)前待爬取鏈接進行排序，進一步確定主題相關(guān)度的高低，防止主題漂移。經(jīng)實驗表明，該爬蟲在主題相關(guān)的識別的準(zhǔn)確度和運行效率均表現(xiàn)良好。

1　相關(guān)知識

在傳統(tǒng)主題爬蟲中，主題相關(guān)度識別方法主要有基于內(nèi)容的識別和基于鏈接分析的識別。

基于內(nèi)容評價的搜索策略主要是根據(jù)鏈接頁面內(nèi)容與主題之間的相似度來評價鏈接價值的高低。主要以向量空間模型為基礎(chǔ)，通過將頁面文檔映射成向量，與主題詞集向量進行余弦值計算，然后將之與人為設(shè)定的閾值進行比較，高于閾值表示符合主題相關(guān)度，低于閾值則丟棄該頁面。但是這種主題識別策略存在一定的問題，例如一些頁面設(shè)置虛假關(guān)鍵詞可能會導(dǎo)致相關(guān)度計算失真，并且忽略了鏈接在網(wǎng)絡(luò)中的相互關(guān)系，如果爬蟲繼續(xù)爬去頁面就會偏離主題。

而基于鏈接分析的主題爬蟲主要以PageRank算法為基礎(chǔ)，依靠PageRank算法來建立主題相關(guān)度模塊。然而PageRank的算法模型是建立在隨機訪問基礎(chǔ)之上的，也就是說用戶瀏覽當(dāng)前網(wǎng)頁上的任意鏈接都是隨機的，也由此假定所有鏈接被用戶點擊的概率都是相等的。但實際上往往并非如此，頁面上的出鏈并不會被用戶以相等的概率而訪問，除此之外，更重要的是并非所有的出鏈都是符合主題相關(guān)度要求的，很容易造成“主題漂移”。因此主題爬蟲的相關(guān)度并不能單純依靠PageRank算法，需要引入更多的因子以提高主題爬蟲的相關(guān)度，從而更好地改善垂直搜索引擎的發(fā)展。

有人提出結(jié)合遺傳算法或者蟻群算法，引入網(wǎng)頁的被訪問數(shù)、創(chuàng)建時間等因子，但通常這些因子的獲取都需要過程，而且許多參數(shù)因子難以獲取，并且遺傳算法的不斷迭代的過程無疑延長了主題爬蟲的抓取數(shù)據(jù)的過程和爬蟲的執(zhí)行效率。同時這種結(jié)合PageRank算法的主題識別方法要求以Web圖結(jié)構(gòu)為基礎(chǔ)，而在爬取頁面并提取其中的URL后，Web圖也會相應(yīng)地改變，所以計算量很大，會對爬蟲的速度造成一定的影響，并且在爬蟲爬行過程中，準(zhǔn)確地計算出那些從來沒有被訪問過的網(wǎng)頁的PageRank值幾乎是不可能的。

在本文中依然采用向量空間模型作為頁面相關(guān)度計算的基礎(chǔ)，通過將頁面向量與手工設(shè)定的主題關(guān)鍵詞集向量的余弦值作為主題相關(guān)的大小，與閾值進行比較，而鏈接分析同樣以向量空間模型為基礎(chǔ)，通過計算頁面中所有出度鏈接的主題相關(guān)度的余弦值，作為當(dāng)前頁面的主題相關(guān)度的加權(quán)系數(shù)，對待爬取鏈接進行相關(guān)度排序的同時進一步檢測頁面的主題相關(guān)度，防止“主題漂移”的產(chǎn)生，避免無關(guān)頁面的下載影響爬蟲的執(zhí)行效率。

2　基于兩步空間向量模型的主題爬蟲策略

2.1主題詞集確立

主題爬蟲在工作前要確定該主題爬蟲的相關(guān)主題詞集。主題詞集的確定通常有兩種，一種是人工確定，另一種是通過初始頁面分析所得。本文中采用人工確定主題詞集，并為每個主題詞指定不同的權(quán)值。主題詞的個數(shù)作為主題向量的維數(shù)，而相應(yīng)的權(quán)值則為主題向量的各個分量值。記主題詞集向量為：K=｛k1，k2，…，kn｝（n為主題詞的個數(shù)）。

2.2頁面相關(guān)度計算

為了確保頁面與主題的相關(guān)度，盡可能避免“主題漂移”的發(fā)生，必須對頁面進行主題相關(guān)度計算，這是主題爬蟲至關(guān)重要的一個步驟，所以需要對鏈接所對應(yīng)的頁面中的文本信息進行提取，以便進行主題相關(guān)度的計算。

本文關(guān)于頁面主題相關(guān)度的判別采用的是基于向量空間模型方法。向量空間模型概念簡單，通過計算頁面特征向量和主題中心向量的余弦距離來表示兩者的相似度，從而對當(dāng)前頁面的主題相關(guān)度進行評價，直觀易懂。在對頁面預(yù)處理過程中，大量HTML標(biāo)簽的存在帶來了一定的麻煩，但卻可以加以利用，從而進一步提高頁面相關(guān)度的預(yù)測。通常情況下，位于錨文本和標(biāo)題處的文本信息要比在正文中出現(xiàn)的信息具有更高的重要性。因此，不同位置出現(xiàn)的關(guān)鍵詞對頁面信息的描述能力具有一定的差異性。那么，針對關(guān)鍵詞出現(xiàn)的不同位置，需要對關(guān)鍵增加額外的權(quán)重位置權(quán)重，這樣可以更好地反映頁面與主題的相關(guān)度。關(guān)鍵詞詞頻計算公式如下：

其中，wi代表不同位置的權(quán)重系數(shù)，fi表示關(guān)鍵詞在該位置出現(xiàn)的次數(shù)。

解決了位置權(quán)重問題，就可以通過向量空間模型，將頁面文本數(shù)據(jù)就轉(zhuǎn)換成計算機可以處理的結(jié)構(gòu)化數(shù)據(jù)，頁面和主題詞集之間的相似性問題轉(zhuǎn)化成兩個向量之間的相似性問題了。計算公式如下：

其中wfi表示頁面文本特征項的第i項特征值，ki表示主題詞集特征向量第i項特征值。相似度由向量的余弦值表示，用來衡量兩個個體之間的差異的大小，當(dāng)余弦值越接近1時，就說明夾角越接近于0度，也就表示兩個向量越相似度越高，這也叫“余弦相似性”。

然而只運用向量空間模型算法對當(dāng)前頁面進行相關(guān)度計算，往往存在一定的問題。例如，頁面中一些無關(guān)的友情鏈接的存在，虛假關(guān)鍵詞的設(shè)置等等都會造成對主題相關(guān)度的誤判，從而影響主題爬蟲的前行，偏離主題。此外，在當(dāng)前頁面爬取完畢后，如何在待爬取隊列中眾多URL中選擇下一個爬取鏈接也是一個至關(guān)重要的問題。所以，要同基于鏈接分析的相關(guān)性評價結(jié)合使用，綜合考慮待分析鏈接之間的相關(guān)性。

2.3候選URL優(yōu)先級排序

對候選URL進行優(yōu)先級排序決定下一個爬行URL是主題爬蟲需要解決的另一個關(guān)鍵問題。在傳統(tǒng)主題爬蟲策略中往往采用基于PageRank算法的策略，通過考查頁面入度去計算鏈接之間的相互關(guān)系，對頁面進行“打分”，然后根據(jù)相應(yīng)的評分高低進行優(yōu)先級排序。但其中存在的一些問題在第1節(jié)已經(jīng)做出相關(guān)敘述。

那么，我們不妨考慮一下頁面的出度。因為對于一個頁面而言，出度是明確的。網(wǎng)頁中所包含的出度鏈接，也就是指向其他頁面的鏈接信息，是近幾年研究中比較關(guān)注的對象，出度不僅反映頁面之間的相互關(guān)系，并且對于判別頁面的內(nèi)容也具有很重要的作用。但是通過以往的研究表明，通過出度去研究頁面的主題，也具有一些弊端，例如廣告鏈接、版權(quán)信息、導(dǎo)航條以及一些無關(guān)的友情鏈接或者是一些惡意URL指向都可能造成判斷失真。因此，需要對這些不可靠的噪聲URL進行丟棄處理。

本文提出基于兩步向量空間模型的主題爬蟲策略，也就是在第一步判別頁面的主題相關(guān)度后，并不直接對頁面進行保留或丟棄處理，而是進一步判斷該頁面的出度URL頁面的主題相關(guān)度來對其進行與主題相關(guān)度的加權(quán)判斷。

然而存在一個問題，正如上文所述，在實際的情況中，頁面的出度鏈接中可能會對應(yīng)一些噪音頁面，那么這些噪音頁面給予待分析URL的支持是不可靠的，那么就需要進行過濾?？紤]到兩種情況，一種是待分析頁面的出度URL對應(yīng)頁面集合中，大多數(shù)均有較高的主題相關(guān)度（此相關(guān)度仍用上節(jié)所述方法計算），但由少量出度頁面具有極低的相關(guān)度或者不相關(guān)，那么直接丟棄該出度URL，出度數(shù)也做相應(yīng)的減少。另一種情況是，所有出度URL頁面集合均不具由高相關(guān)度，則直接忽略出度對待分析頁面的相關(guān)度貢獻。計算公式如下：

其中α為權(quán)重因子，score由頁面主題相關(guān)度和頁面出度URL對應(yīng)頁面相關(guān)度兩部分組成，通過對score進行排序，從而選出下一個爬行的URL。舉例如下：

如圖1所示，假設(shè)初始URL由3個出度鏈接分別為a，b，c，而這3個候選URL又各自擁有3個出度鏈接。通過VSM計算，各頁面的主題相關(guān)度如圖2所示。那么基于傳統(tǒng)向量空間模型策略的主題爬蟲第二步就會去保存頁面a，然后繼續(xù)考察a頁面中的出度鏈接。實際情況下這種a，b，c的候選URL排序可能是不合理的，按照本文所提出的策略，需要在對a，b，c三條鏈接排序時，先分別對候選鏈接a，b，c的所有子URL進行主題相關(guān)度計算，假設(shè)結(jié)果如圖2所示，依據(jù)頁面出度信息對頁面主題相關(guān)度具有一定貢獻的原則，對候選URL進行重新加權(quán)計算。按照公式（4）可以計算的到，a的頁面的得分是0.7*0.9+0.3*（（0.9+0.8+0.7）/3）=0.87（實驗表明α取值0.7附近時效果較好，故此處α取0.7），同樣，計算可得b，c的得分分別為0.65，0.76。通過公式3.1“打分”后，候選URL排序為a，c，b。

圖1　網(wǎng)頁Web簡圖

通過利用待分析頁面出度URL相關(guān)度的分析，進一步確定待分析頁面與主題的相關(guān)性程度，在一定程度上克服了頁面惡意關(guān)鍵詞的設(shè)置。此外，在一定程度上擴大了主題爬蟲的在整個網(wǎng)絡(luò)中的搜索范圍，有利于引導(dǎo)主題爬蟲穿越網(wǎng)絡(luò)隧道，解決“隧道現(xiàn)象”，提高了主題爬蟲的爬全率和爬準(zhǔn)率。

3　實驗結(jié)果及分析

3.1評估指標(biāo)

對于主題網(wǎng)絡(luò)爬蟲性能的衡量，查全率和查準(zhǔn)率是常用判斷指標(biāo)。它們可以定量化的考查主題爬蟲的“過濾能力”，即判斷頁面“保留”還是“丟棄”的能力。但是，進一步分析，就會發(fā)現(xiàn)查全率的計算具有一定的困難。眾所周知，在整個網(wǎng)絡(luò)中的主題資源數(shù)量幾乎是不可知的，那我們也就無從知曉檢漏的頁面數(shù)量。通過其它方式計算查全率又具有一定的不準(zhǔn)確性，所以本文經(jīng)不針對查全率進行計算。然而相當(dāng)于查全率，查準(zhǔn)率則要相對容易計算，查準(zhǔn)率是指在已提取頁面中與主題相關(guān)的頁面數(shù)占所提取頁面總數(shù)的比例。除此之外，時間維度也是判斷爬蟲性能的另一個至關(guān)重要的標(biāo)準(zhǔn)，從這個角度考慮，引入另一個考查標(biāo)準(zhǔn)，就是爬蟲在不同時間所能爬蟲到的相關(guān)頁面數(shù)量。

綜上所述，本文將采用查準(zhǔn)率和不同時間點的執(zhí)行情況作為主題爬蟲進行考查標(biāo)準(zhǔn)。

圖2　查準(zhǔn)率結(jié)果比較

圖3　時間維度結(jié)果比較

3.2實驗結(jié)果分析

依據(jù)上節(jié)所述評估標(biāo)準(zhǔn)，將本文所提策略爬蟲與傳統(tǒng)VSM策略爬蟲進行比較，以驗證本文所提策略的可行性。實驗以搜狐體育（http：//sports.sohu.com）為初始URL入口，爬取與“中國足球”相關(guān)的頁面。取關(guān)鍵詞集：國足，亞冠，世預(yù)賽，足球，中超。搜索策略采用傳統(tǒng)基于VSM策略和本文所提策略，結(jié)果如下：

（1）從查準(zhǔn)率的角度來看，在爬取了不同數(shù)量頁面的對比中可以發(fā)現(xiàn)本文改進策略的普遍高于傳統(tǒng)VSM的爬蟲策略。

（2）從時間的角度來看，在剛開始是基于本文策略的爬蟲爬取的相關(guān)頁面要略少，但隨著時間的推移，優(yōu)勢會逐漸顯現(xiàn)。這是因為本文的策略在計算復(fù)雜度上開銷稍大，在短時間內(nèi)雖然爬取頁面的相關(guān)度比例要高，但是總數(shù)會略少，所以在開始的時間節(jié)點比較時，會有略微的劣勢，但隨著爬取時間的不斷增加，優(yōu)勢會逐漸明顯。

4　結(jié)語

本文提出了基于兩步向量空間模型的主題爬蟲策略。同時考慮了待爬取頁面的主題相關(guān)度以及待爬取頁面所包含的URL的主題相關(guān)度，通過對多一步的頁面相關(guān)度分析可以減小惡意URL對主題相關(guān)度的“貢獻”，同時也有利于解決當(dāng)前頁面低于主題相關(guān)度閾值，但經(jīng)過子URL后進入一個高主題相關(guān)度的頁面的“隧道現(xiàn)象”，防止相關(guān)頁面的丟失。實驗表明，此方法在主題相關(guān)度識別方面具有可行性，實驗結(jié)果較好。但是關(guān)于閾值的設(shè)定以及關(guān)鍵詞集的設(shè)置都將直接影響到主題爬蟲的執(zhí)行。因為單純提高閾值，會造成一些頁面訪問不到；降低閾值，又會抓取大量不相關(guān)頁面，主題詞集的設(shè)置也直接影響到主題相關(guān)度的計算，應(yīng)該提升到語義本體的層面。所以，這也將是下一步研究的重點。

參考文獻：

[1]劉建明，郝志峰．垂直搜索引擎中的主題爬蟲技術(shù)研究[D]．廣東：廣東工業(yè)大學(xué)，2013.

[2]高琪，張永平．PageRank算法中主題漂移的研究[J]．微計算機信息，2010.

[3]劉國靖，康麗等．基于遺傳算法的主題爬蟲策略[J]．計算機應(yīng)用，2007.

[4]張翔，周明全等．基于PageRank與Bagging的主題爬蟲研究[J]．計算機工程與設(shè)計，2010，31（14）.

[5]黃正德，張文燚等．主題爬蟲關(guān)鍵技術(shù)研究[D]．哈爾濱：哈爾濱工程大學(xué)，2013.

Research on Subject Relevance Algorithm of Theme Crawler

XU Yang，WANG Wei-yang
（College of Information Engineering，Shanghai Maritime University，Shanghai 201306）

Abstract：

The core issue of the theme crawler is the discrimination of the topic.In the process of crawling，the fast and accurate identification of the topic relevance of crawling pages is the key to decide the strategy of the search strategy.Proposed method of two step vector space model is used to identify themes.And compared two-step vector space model strategy with traditional one-step vector space model strategy.Experimental results show that the two step vector space strategy in to identify topic relevance and efficiency have better performance，also has a certain improvement on the“tunnel phenomenon”.

Keywords：

主題爬蟲核心問題是主題的相關(guān)性判別問題。如何在爬取過程中，快速、準(zhǔn)確地判別爬取頁面的主題相關(guān)度，是決定主題爬蟲搜索策略好壞的關(guān)鍵所在。提出利用兩步向量空間模型計算的方法進行主題識別，并將基于兩步向量空間模型的主題爬蟲與傳統(tǒng)基于一步向量空間模型的主題爬蟲進行比較，實驗表明基于兩步向量空間的主題爬蟲在主題相關(guān)度判別和執(zhí)行效率方面都有較好的表現(xiàn)，同時對“隧道現(xiàn)象”也有一定的改善。

搜索引擎；網(wǎng)絡(luò)爬蟲；主題相關(guān)度；向量空間模型

文章編號：1007-1423（2016）14-0048-05

DOI：10.3969/j.issn.1007-1423.2016.14.010

作者簡介：

徐楊（1989-），男，安徽合肥人，在讀碩士研究生，研究方向為軟件開發(fā)方法與軟件項目管理

王未央（1963-），女，江蘇常熟人，副教授，研究方向為數(shù)據(jù)處理與挖掘

收稿日期：2016-04-06修稿日期：2016-05-10

Search Engine；Web Crawler；Theme Relevance；Vector Space Model