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

?

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

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

摘要：

關(guān)鍵詞：

0　引言

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

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

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

1　相關(guān)知識(shí)

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

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

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

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

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

2　基于兩步空間向量模型的主題爬蟲(chóng)策略

2.1主題詞集確立

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

2.2頁(yè)面相關(guān)度計(jì)算

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1　網(wǎng)頁(yè)Web簡(jiǎn)圖

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

3　實(shí)驗(yàn)結(jié)果及分析

3.1評(píng)估指標(biāo)

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

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

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

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

3.2實(shí)驗(yàn)結(jié)果分析

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

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

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

4　結(jié)語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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

[5]黃正德，張文燚等．主題爬蟲(chóng)關(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：

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

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

文章編號(hào)：1007-1423（2016）14-0048-05

DOI：10.3969/j.issn.1007-1423.2016.14.010

作者簡(jiǎn)介：

徐楊（1989-），男，安徽合肥人，在讀碩士研究生，研究方向?yàn)檐浖_(kāi)發(fā)方法與軟件項(xiàng)目管理

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

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

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