一種基于鏈接和內(nèi)容分析的自適應(yīng)主題爬蟲(chóng)算法

朱慶生，徐 寧，周 瑜

(重慶大學(xué)計(jì)算機(jī)學(xué)院軟件理論與技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400044)

0 引言

隨著互聯(lián)網(wǎng)的迅猛發(fā)展，網(wǎng)絡(luò)上信息資源在快速膨脹，根據(jù)中國(guó)互聯(lián)網(wǎng)絡(luò)信息中心(CNNIC)發(fā)布的第33 次《中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告》［1］，截至2013 年12 月，中國(guó)網(wǎng)站數(shù)量全年增長(zhǎng)52 萬(wàn)個(gè)，增長(zhǎng)率為19.4%，達(dá)到320 萬(wàn)，而中國(guó)網(wǎng)頁(yè)數(shù)量同比增長(zhǎng)了22.2%，達(dá)到1500 億個(gè)。為了能夠從這浩如煙海的信息資源中找到用戶所需的信息，則往往需要求助于搜索引擎。但是，目前通用的搜索引擎如百度、谷歌等只能滿足用戶的一般性搜索，在查準(zhǔn)率和查全率上較低而無(wú)法滿足用戶的個(gè)性化需求，并且具有無(wú)法保證網(wǎng)頁(yè)及時(shí)更新等多方面的問(wèn)題［2］。因此，基于主題爬蟲(chóng)的垂直搜索引擎成為第4 代搜索引擎的發(fā)展方向?；谥黝}爬蟲(chóng)的垂直搜索引擎在數(shù)字圖書(shū)［3］、社交網(wǎng)站［4］、輿情監(jiān)測(cè)［5］、醫(yī)療信息［6］等方面均有廣泛的應(yīng)用，主題爬蟲(chóng)不僅可以用于個(gè)性化搜索引擎，也可以用作數(shù)據(jù)挖掘數(shù)據(jù)源頭［7］。

主題爬蟲(chóng)(Focused Crawler)［8］是由Chakrabarti等在1999 年首次提出，目的是為了盡可能多地下載與給定主題相關(guān)的網(wǎng)頁(yè)，避免下載與給定主題不相關(guān)的網(wǎng)頁(yè)。主題爬蟲(chóng)能夠節(jié)省大量的時(shí)間、網(wǎng)絡(luò)帶寬和存儲(chǔ)空間，更好地滿足用戶的個(gè)性化需求。相對(duì)于通用爬蟲(chóng)，主題爬蟲(chóng)需要解決的關(guān)鍵問(wèn)題是如何判斷和計(jì)算未下載網(wǎng)頁(yè)的優(yōu)先級(jí)，優(yōu)先級(jí)高的網(wǎng)頁(yè)被認(rèn)為是重要且相關(guān)的網(wǎng)頁(yè)而被優(yōu)先下載，從而最大限度地下載主題相關(guān)的網(wǎng)頁(yè)。目前主要的搜索算法從2 個(gè)方面來(lái)判斷:基于網(wǎng)頁(yè)內(nèi)容相關(guān)性分析的方法和基于鏈接分析的方法?；阪溄臃治龅姆椒ㄊ腔谝粋€(gè)假設(shè)-主題相關(guān)的網(wǎng)頁(yè)更可能相互鏈接在一起，通過(guò)分析鏈接結(jié)構(gòu)和鏈接之間的相互引用判斷鏈接的重要性程度，從而決定鏈接的下載優(yōu)先級(jí)，這類算法有著名的PageRank 算法［9］和HITS 算法［10］;基于網(wǎng)頁(yè)內(nèi)容分析方法則是通過(guò)計(jì)算網(wǎng)頁(yè)頁(yè)面內(nèi)容與給定主題相似度來(lái)決定網(wǎng)頁(yè)的下載優(yōu)先級(jí)，相似度高的網(wǎng)頁(yè)其下載優(yōu)先級(jí)就越大;Fish-Search 算法［11］和基于Fish-Search 的改進(jìn)的Shark-Search 算法［12］是這種算法的典型代表。WANG 等［13］提出了主題網(wǎng)頁(yè)重要性在線估算的方法(OTIE)算法則是通過(guò)結(jié)合鏈接結(jié)構(gòu)和網(wǎng)頁(yè)內(nèi)容分析的方法，提出一種不平均分配現(xiàn)金值的方法。該算法的優(yōu)點(diǎn)是能夠在線計(jì)算網(wǎng)頁(yè)的優(yōu)先級(jí)，僅需要更少的時(shí)間和資源，使得網(wǎng)絡(luò)爬蟲(chóng)更加高效和準(zhǔn)確，該算法的不足之處在于考慮網(wǎng)頁(yè)相關(guān)性的評(píng)判上不全，導(dǎo)致其在內(nèi)容相關(guān)性評(píng)分上不準(zhǔn)確。

筆者在OTLE 算法的基礎(chǔ)上進(jìn)行改進(jìn)，提出綜合考慮網(wǎng)頁(yè)鏈接和內(nèi)容分析的自適應(yīng)算法，同時(shí)解決在爬取主題網(wǎng)頁(yè)過(guò)程中的隧道穿越問(wèn)題。

1 相關(guān)研究

1.1 OTIE 算法

OTIE(Online Topical Importance Estimation)算法可以看作是OPIC 算法的一種改進(jìn)。OPIC(Online Page Importance Computation)［14］由Abiteboul 等提出的在線計(jì)算網(wǎng)頁(yè)鏈接重要性的算法，它可以看作是一種改進(jìn)的PageRank 算法。OPIC 算法的主要思想是根據(jù)網(wǎng)頁(yè)鏈接擁有現(xiàn)金(cash)的多少來(lái)決定網(wǎng)頁(yè)的重要程度，擁有現(xiàn)金數(shù)最多的網(wǎng)頁(yè)優(yōu)先被下載。當(dāng)網(wǎng)頁(yè)被下載之后，它所擁有的現(xiàn)金值被平均分配給它所指向的鏈接，在初始化時(shí)，每個(gè)網(wǎng)頁(yè)都給與相同的現(xiàn)金值?？梢钥闯鯫PIC 算法與PageRank 算法在思路大體上一致，但是它的計(jì)算速度比PageRank 快得多，因此適合在線計(jì)算，這是因?yàn)镻ageRank 算法每次需要迭代計(jì)算，而OPIC 不需要。OTIE 算法對(duì)于OPIC算法的主要改進(jìn)在于不平均分配網(wǎng)頁(yè)擁有的現(xiàn)金值，而是根據(jù)網(wǎng)頁(yè)內(nèi)容的相關(guān)性程度大小來(lái)分配網(wǎng)頁(yè)的現(xiàn)金值，主題相關(guān)性高的網(wǎng)頁(yè)得到更多的現(xiàn)金值，這樣使得重要且相關(guān)的網(wǎng)頁(yè)得到更多的激勵(lì)，這將在優(yōu)先下載重要資源的基礎(chǔ)上很好地解決主題漂流的現(xiàn)象。改進(jìn)后網(wǎng)頁(yè)鏈接獲取現(xiàn)金值如公式(1)所示。

其中，cash_gain(j，i)表示網(wǎng)頁(yè)j 從網(wǎng)頁(yè)i 獲取的現(xiàn)金值，Oi表示網(wǎng)頁(yè)i 所指向的網(wǎng)頁(yè)集合，sim(j，t)表示頁(yè)面j 對(duì)主題t 的相似度，cash［i］表示網(wǎng)頁(yè)i 在爬取過(guò)程中所擁有的現(xiàn)金值。

1.2 Shark-Search 算法

Shark-Search 算法［6］可以看成是Fish-Search 算法的變種，它在計(jì)算子鏈接的相關(guān)性評(píng)分時(shí)，不再是根據(jù)網(wǎng)頁(yè)全文文本與給定主題的是否相關(guān)的0-1 判斷，而是根據(jù)父網(wǎng)頁(yè)全文文本、鏈接錨文本、鏈接上下文三者綜合決定，最終的計(jì)算結(jié)果取0～1 之間連續(xù)值。下載隊(duì)列中的鏈接主題相關(guān)性評(píng)分由父網(wǎng)頁(yè)得分和鏈接鄰近得分共同決定，其計(jì)算如公式(2)所示。

在公式(2)中，inherited(url)表示從父網(wǎng)頁(yè)節(jié)點(diǎn)繼承的相關(guān)性評(píng)分，其計(jì)算如公式(3)所示，它是由父網(wǎng)頁(yè)文本內(nèi)容與給定主題之間的相似性計(jì)算得到，其中α 是小于1 的衰減因子，sim(topic，current_url)表示在當(dāng)前主題下當(dāng)前網(wǎng)頁(yè)current_url 的相似度評(píng)分。neighborhood(url)表示鄰近鏈接的評(píng)分，其計(jì)算如公式(4)所示，它是由錨本文得分和鏈接上下文得分共同決定。

在公式(4)中，anchor_score 表示錨文本的相關(guān)性評(píng)分，其計(jì)算如公式(5)所示，它是通過(guò)計(jì)算錨文本內(nèi)容與主題topic 的相似性得到。anchor_text_score表示鏈接上下文得分，其計(jì)算如公式(6)所示，由鏈接上下文與主題的相似性計(jì)算得到。

Shark-Search 算法是基于網(wǎng)頁(yè)文本內(nèi)容分析的典型代表，只根據(jù)網(wǎng)頁(yè)內(nèi)容的相關(guān)性得分來(lái)決定網(wǎng)頁(yè)的下載優(yōu)先級(jí)。這種方法沒(méi)有考慮網(wǎng)絡(luò)的整體結(jié)構(gòu)信息，容易受到噪音內(nèi)容的影響，造成在爬取主題網(wǎng)頁(yè)的“近視”問(wèn)題，因此它的查準(zhǔn)率和查全率并不高。

1.3 隧道穿越

隧道穿越問(wèn)題是主題爬蟲(chóng)在爬取過(guò)程中的一個(gè)難點(diǎn)問(wèn)題。通常主題爬蟲(chóng)在爬取的過(guò)程根據(jù)網(wǎng)頁(yè)相關(guān)性得分高低進(jìn)行優(yōu)先爬取，使得那些相關(guān)性較低的網(wǎng)頁(yè)被舍棄，這是主題爬蟲(chóng)的優(yōu)勢(shì)所在，也是基于一個(gè)假設(shè)-主題相關(guān)的網(wǎng)頁(yè)是鏈接在一起的，但實(shí)際情況是相同主題網(wǎng)頁(yè)聚成團(tuán)，相同主題下不同主題團(tuán)之間需要通過(guò)一個(gè)或多個(gè)主題不相關(guān)的網(wǎng)頁(yè)才能到達(dá)。如果舍棄這些網(wǎng)頁(yè)，那么很多主題相關(guān)網(wǎng)頁(yè)將不能被發(fā)現(xiàn)和下載，影響主題爬蟲(chóng)的召回率。隧道穿越需要解決的主要問(wèn)題是決定何時(shí)停止穿越。Bergmark等［15］提到并驗(yàn)證的幾個(gè)假設(shè)，需要一段比較長(zhǎng)的距離從一個(gè)主題相關(guān)團(tuán)到下一個(gè)主題相關(guān)團(tuán)，通常是7或8;好的父網(wǎng)頁(yè)節(jié)點(diǎn)往往預(yù)示著好的孩子節(jié)點(diǎn)，反之，則不然;一個(gè)好的穿越路徑的好壞往往預(yù)示一個(gè)好的子網(wǎng)頁(yè)節(jié)點(diǎn)。因此，得到一個(gè)自適應(yīng)隧道穿越的算法，如公式(7)所示。

在公式(7)中，c 表示網(wǎng)頁(yè)的相關(guān)性得分，dp表示父網(wǎng)頁(yè)的穿越距離，C 是一個(gè)常數(shù)，表示穿越距離的最大值。從上面的公式可以看出，網(wǎng)頁(yè)的穿越距離隨著父節(jié)點(diǎn)的穿越距離呈指數(shù)增長(zhǎng)，而網(wǎng)頁(yè)的相關(guān)性越低，網(wǎng)頁(yè)的穿越距離就越大。

2 基于鏈接和內(nèi)容分析的自適應(yīng)算法

Liu 等［16］指出網(wǎng)頁(yè)標(biāo)題和網(wǎng)頁(yè)文本內(nèi)容一樣對(duì)網(wǎng)頁(yè)的相關(guān)性度量評(píng)分有較大影響。因此，本文在計(jì)算網(wǎng)頁(yè)相關(guān)性得分時(shí)加入標(biāo)題相似性的得分。網(wǎng)頁(yè)從父節(jié)點(diǎn)獲得的得分如公式(8)所示，因此得到待下載網(wǎng)頁(yè)鏈接最終主題預(yù)測(cè)值的大小由父網(wǎng)頁(yè)內(nèi)容、父網(wǎng)頁(yè)標(biāo)題、鏈接錨文本和鏈接上下文來(lái)綜合決定。

將Shark-Search 算法計(jì)算得出的相關(guān)性綜合評(píng)分改寫OTIE 算法中的現(xiàn)金分配策略，由此得到新的現(xiàn)金分配算法，如公式(9)所示。

至此，通過(guò)結(jié)合OTIE 算法和Shark-Search 算法提出了帶隧道穿越的基于網(wǎng)頁(yè)鏈接和內(nèi)容分析的自適應(yīng)算法，本算法描述如算法1 所示。其中frontier包含著未訪問(wèn)的URLs 列表。fetched 表示已下載的網(wǎng)頁(yè)列表，S(t)表示主題向量。

算法1 基于鏈接和內(nèi)容分析的自適應(yīng)主題爬算法

算法1 中第1～3 行是初始化，從ODP 中選擇種子網(wǎng)頁(yè)，等量初始化cash 值并從中使用TF-IDF 算法訓(xùn)練出基準(zhǔn)向量。第4～6 行是選擇下載擁有最大現(xiàn)金值的網(wǎng)頁(yè)，然后計(jì)算網(wǎng)頁(yè)與主題相似度。第10～13 行是當(dāng)前網(wǎng)頁(yè)計(jì)算相關(guān)度大于閾值時(shí)，則根據(jù)公式(9)不平均分配它所擁有的現(xiàn)金值。第17～24 行當(dāng)前網(wǎng)頁(yè)計(jì)算相關(guān)度小于閾值時(shí)，則需要看當(dāng)前網(wǎng)頁(yè)的穿越距離是否大于臨界值cutoff，如果大于則舍棄該路徑，否則同樣根據(jù)公式(9)不平均分配它所擁有的現(xiàn)金值，可以繼續(xù)穿越。第21 行是為了刪除網(wǎng)頁(yè)中存在的公共部分，從而避免同一網(wǎng)站內(nèi)重復(fù)導(dǎo)航鏈接的影響。第31 行則是根據(jù)網(wǎng)頁(yè)擁有的現(xiàn)金從大到小排序。算法在下載隊(duì)列為空或者達(dá)到最大下載數(shù)量時(shí)停止。

另外，在算法自適應(yīng)階段，根據(jù)新下載相關(guān)網(wǎng)頁(yè)對(duì)主題向量進(jìn)行反饋。在新下載主題網(wǎng)頁(yè)數(shù)量達(dá)到100時(shí)，重新訓(xùn)練得到新的主題基準(zhǔn)向量，這樣通過(guò)新主題網(wǎng)頁(yè)的反饋信息，可以使得主題基準(zhǔn)向量更加準(zhǔn)確。

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

本實(shí)驗(yàn)中的算法全部使用Java 語(yǔ)言實(shí)現(xiàn)，從Open Directory Project(ODP，http://dmoz.org/)中選擇10 個(gè)主題進(jìn)行驗(yàn)證，每個(gè)主題下面爬取5000 個(gè)網(wǎng)頁(yè)，對(duì)應(yīng)每個(gè)主題選取20 個(gè)種子網(wǎng)頁(yè)。采用Srinivasan［17］提出的收獲率和召回率來(lái)評(píng)價(jià)本文算法的性能。收獲率(harvest-rate)用來(lái)估計(jì)主題爬取的查準(zhǔn)率，harvest-rate 的計(jì)算如公式(10)所示，目標(biāo)召回率(target recall)用來(lái)估算在互聯(lián)網(wǎng)中相關(guān)網(wǎng)頁(yè)被獲取的比例，是對(duì)爬取查全率的一個(gè)模擬，而且更能說(shuō)明主題爬蟲(chóng)算法的性能，其計(jì)算如公式(10)所示。

在公式(10)中，relevant_pages 是在下載網(wǎng)頁(yè)中與主題相關(guān)頁(yè)面的數(shù)量，pages_downloaded 表示爬取網(wǎng)頁(yè)總量。在公式(11)中，R 表示網(wǎng)絡(luò)中所有主題相關(guān)網(wǎng)頁(yè)的集合，C(t)是所獲取的網(wǎng)頁(yè)集合，T 是R的一個(gè)隨機(jī)子集。

將本算法與Best-First 算法、文獻(xiàn)［3］提出的OTIE 算法以及Shark-Search 算法進(jìn)行比較。其中Best-First 算法作為主題爬蟲(chóng)算法的比較基準(zhǔn)，Best-First 算法通過(guò)Web 網(wǎng)頁(yè)和給定主題進(jìn)行相似性得分決定網(wǎng)頁(yè)下載優(yōu)先級(jí)，將未爬行的網(wǎng)頁(yè)鏈接添加到爬行隊(duì)列，該隊(duì)列按照網(wǎng)頁(yè)的優(yōu)先級(jí)權(quán)值進(jìn)行排序，優(yōu)先級(jí)最高的URL 最先被下載。圖1 和圖2 分別給出了4 種算法在各個(gè)主題平均目標(biāo)召回率和平均收獲率隨網(wǎng)頁(yè)下載數(shù)量變化的情況。

圖1 不同算法平均目標(biāo)召回率隨網(wǎng)頁(yè)數(shù)量變化的變化情況

圖2 不同算法平均收獲率隨網(wǎng)頁(yè)數(shù)量變化情況

從圖1 中可以看出，本算法的目標(biāo)召回率明顯高于其他3 個(gè)算法，而Shark-Search 收斂比較快。從圖2 中可以看到本算法收獲比一開(kāi)始并不如OTIE 算法，但還是明顯好于其他的2 個(gè)算法，這是由于本文算法采用了隧道穿越技術(shù)，在穿越的過(guò)程中下載了一些主題不相關(guān)的網(wǎng)頁(yè)，盡管最后并沒(méi)有保留這些網(wǎng)頁(yè)。但是可以看到隨著下載網(wǎng)頁(yè)數(shù)量的增多，本算法的收獲率和OTIE 相比差別不大?？煽闯霰舅惴ㄔ谂廊≈黝}網(wǎng)頁(yè)時(shí)具有較好的性能。

4 結(jié)束語(yǔ)

本文提出基于鏈接和內(nèi)容分析的自適應(yīng)算法，通過(guò)綜合分析鏈接重要性和網(wǎng)頁(yè)內(nèi)容的相關(guān)性得分，采取不平均分配現(xiàn)金值的方法，激勵(lì)重要且與主題相關(guān)性高的鏈接，并且考慮主題爬蟲(chóng)過(guò)程中的隧道穿越問(wèn)題，使得更多的主題相關(guān)網(wǎng)頁(yè)被發(fā)現(xiàn)和下載。通過(guò)實(shí)驗(yàn)證明了本算法的可行性和有效性。

［1］中國(guó)互聯(lián)網(wǎng)絡(luò)信息中心(CNNIC).第34 次《中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告》［EB/OL］.http://www.cnnic.net.cn/hlwfzyj/hlwxzbg/hlwtjbg/201407/P020140721507223212132.pdf，2014-07-23.

［2］Du Yajun，Pen Qiangqiang，Gao Zhaoqiong.A topic-specific crawling strategy based on semantics similarity［J］.Data ＆ Knowledge Engineering，2013，88 (2013)75-93.

［3］常智榮.搜索引擎Nutch 在數(shù)字圖書(shū)館中集成應(yīng)用的研究與實(shí)現(xiàn)［D］.北京:北京郵電大學(xué)，2010.

［4］曾銘.垂直搜索技術(shù)在社交網(wǎng)站中的應(yīng)用與研究［D］.北京:北京郵電大學(xué)，2013.

［5］羅磊.微博輿情熱點(diǎn)檢測(cè)與跟蹤方法研究［D］.杭州:杭州電子科技大學(xué)，2013.

［6］Tang T T，Hawking D，Craswell N，et al.Focused crawling for both topical relevance and quality of medical information［C］// Proc.the 14th ACM Int.Conf.on Information and Knowledge Management.2005:147-154.

［7］Pirkola A.Focused Crawling:A Means to Acquire Biological Data from the Web［EB/OL］.http://www.researchgate.net/publication/228783841_Focused_Crawling_A_Means_to_Acquire_Biological_Data_from_the_Web，2015-03-30.

［8］Chakrabarti S，Berg M van Den，Dom B.Focused crawling:A new approach to topic-specific Web resource discovery［J］.Computer Networks，1999，31(11-16):1623-1640.

［9］Page L，Brin S，Motwani R，et al.The PageRank Citation Ranking:Bringing Order to the Web ［R］.California:Stanford University，1998.

［10］Kleinberg M.Authoritative sources in a hyperlinked environment［J］.Journal of the ACM，1999，46(5):604-632.

［11］Debra P，Post R.Information retrieval in the World Wide Web:Making client-based searching feasible［C］// Proceedings of the 1st International World Wide Web Conference.1994:183-192.

［12］Hersovici M，Jacovi M，Maarek Y，et al.The shark-search algorithm-an application:Tailored Web site mapping［C］//Proceedings of the 7th World Wide Web Conference.1998:317-326.

［13］Wang Can，Guan Zi-yu，Chen Chun，et al.On-line topical importance estimation:An effective focused crawling algorithm combining link and content analysis［J］.Journal of Zhejiang University(Science A)，2009，10 (8):1114-1124.

［14］Abiteboul S，Preda M，Cobena G.Adaptive on-line page importance computation［C］// Proceedings of the 12th international World Wild Web Conference.2003:280-290.

［15］Bergmark D，Lagoze C，Sbityakov A.Focused crawls，tunneling，and digital libraries［C］// Proceedings of the 6th European Conference on Digital Libraries.2002:91-106.