主題網(wǎng)絡(luò)爬蟲(chóng)關(guān)鍵技術(shù)研究

1、摘 要隨著互聯(lián)網(wǎng)的迅速發(fā)展，Web的信息量越來(lái)越大。人們往往通過(guò)搜索引擎去從互聯(lián)網(wǎng)上搜索想要的信息，比如:百度，谷歌，搜狗等。這類搜索引擎稱之為通用搜索引擎，其為所有的用戶提供用戶想要的所有信息。隨著互聯(lián)網(wǎng)上的信息量越來(lái)越大，用戶搜索出來(lái)的信息可能與自己想要的信息大相徑庭。對(duì)于這種問(wèn)題，就需要更加專業(yè)的，面向特定領(lǐng)域的搜索引擎來(lái)解決。主題網(wǎng)絡(luò)爬蟲(chóng)是垂直搜索引擎的關(guān)鍵部分，本文主要是對(duì)主題網(wǎng)絡(luò)爬蟲(chóng)中的關(guān)鍵技術(shù)進(jìn)行研究。主要研究?jī)?nèi)容如下：（1）主題內(nèi)容的抽取是網(wǎng)頁(yè)主題識(shí)別的重要步驟，本文結(jié)合網(wǎng)頁(yè)內(nèi)容分布特征以及主題內(nèi)容的相關(guān)特征，設(shè)計(jì)了一種網(wǎng)頁(yè)主題內(nèi)容抽取方法。（2）提出了一種基于實(shí)體鏈接的主題識(shí)

2、別算法，去識(shí)別網(wǎng)頁(yè)的主題。將基于知識(shí)庫(kù)的實(shí)體鏈接方法運(yùn)用于特征抽取，實(shí)驗(yàn)表明該方法提高了主題網(wǎng)頁(yè)識(shí)別的準(zhǔn)確率。（3）提出了一種基于Best-First算法的主題搜索策略。主題搜索策略是指導(dǎo)主題網(wǎng)絡(luò)爬蟲(chóng)抓取網(wǎng)頁(yè)的關(guān)鍵，本文采用基于Best-First算法的主題搜索策略。關(guān)鍵詞：主題網(wǎng)絡(luò)爬蟲(chóng)，實(shí)體鏈接，Best-First算法，主題搜索策略V碩士學(xué)位論文第一章 緒論1.1 背景與意義隨著Internet的飛速發(fā)展，互聯(lián)網(wǎng)信息呈指數(shù)增長(zhǎng)。根據(jù)中國(guó)互聯(lián)網(wǎng)絡(luò)信息中心（CNNIC）發(fā)布的第40次中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告1數(shù)據(jù)顯示:“截至2017年6月，中國(guó)網(wǎng)民規(guī)模達(dá)到7.51億，占全球網(wǎng)民總數(shù)的五分之

3、一?；ヂ?lián)網(wǎng)普及率為54.3%；中國(guó)網(wǎng)站數(shù)量為506萬(wàn)個(gè)，半年增長(zhǎng)4.8%。”如此大量的網(wǎng)站中包含著不計(jì)其數(shù)的網(wǎng)頁(yè)，網(wǎng)頁(yè)是信息的載體，人們一般通過(guò)百度、谷歌等通用搜索引擎去從互聯(lián)網(wǎng)上獲取想要的信息。然而，利用通用搜索引擎搜索出的信息，往往比較寬泛。垂直搜索引擎針對(duì)的是一個(gè)特定的行業(yè)，是通用搜索引擎的細(xì)分，其將某一領(lǐng)域的網(wǎng)頁(yè)信息進(jìn)行整合，處理后再以某種形式返回給用戶。垂直搜索針引擎對(duì)某一領(lǐng)域，為特定用戶或特定需求提供相關(guān)的信息和服務(wù)。垂直搜索引擎專注于某一領(lǐng)域或?qū)I(yè)，所以顯得更加專注、具體及深入。主題網(wǎng)絡(luò)爬蟲(chóng)，又稱聚焦爬蟲(chóng)是垂直搜索引擎的重要組成部分，所以對(duì)主題網(wǎng)絡(luò)爬蟲(chóng)的研究具有重要的意義。主題網(wǎng)

4、絡(luò)爬蟲(chóng)是一個(gè)自動(dòng)從互聯(lián)網(wǎng)上抓取網(wǎng)頁(yè)的程序，它根據(jù)預(yù)設(shè)的主題去訪問(wèn)互聯(lián)網(wǎng)上與主題相關(guān)的鏈接，獲取網(wǎng)頁(yè)信息。通用網(wǎng)絡(luò)爬蟲(chóng)從若干種子鏈接開(kāi)始，先抓取種子鏈接的網(wǎng)頁(yè)，然后從這些網(wǎng)頁(yè)中抽取新的鏈接放入待抓取隊(duì)列中，直到滿足系統(tǒng)設(shè)定的抓取結(jié)束條件或者待抓取隊(duì)列為空。相比之下，主題網(wǎng)絡(luò)爬蟲(chóng)的抓取流程較為復(fù)雜，在抓取的過(guò)程中，需要預(yù)測(cè)鏈接的主題相似度，然后放入根據(jù)主題相似度排序的待抓取隊(duì)列中。1.2 主題網(wǎng)絡(luò)爬蟲(chóng)的國(guó)內(nèi)外研究現(xiàn)狀1999 年，S.Chakrabani2第一次提出了聚焦爬蟲(chóng)這一概念，并設(shè)計(jì)并實(shí)現(xiàn)了 Focus Proiect 系統(tǒng)3。該技術(shù)一經(jīng)提出很快獲得了廣泛關(guān)注。接下來(lái)，從理論與實(shí)現(xiàn)的系統(tǒng)兩

5、個(gè)方面介紹主題網(wǎng)絡(luò)爬蟲(chóng)的國(guó)內(nèi)外研究現(xiàn)狀。1.2.1 主題識(shí)別算法及主題搜索策略P.DeBra4等人提出利用Fish-Search 算法來(lái)作為爬蟲(chóng)的搜索策略，該算法假設(shè)主題相關(guān)頁(yè)面邏輯上相接近來(lái)搜索主題相關(guān)的網(wǎng)頁(yè)。Shark-Search 爬蟲(chóng)5是在Fish-Search算法的的基礎(chǔ)上進(jìn)行了改進(jìn)，F(xiàn)ish-Search算法是利用二值模型來(lái)評(píng)估主題相關(guān)性，而Shark-Search算法根據(jù)鏈接錨文本和網(wǎng)頁(yè)主題相關(guān)內(nèi)容計(jì)算出的相關(guān)性值為0-1內(nèi)的值。該算法能提高主題爬蟲(chóng)的召回率。 Best-First爬蟲(chóng)6，由 CHO J 等人在 1998 年提出，其主要思想是構(gòu)建一個(gè)待抓取隊(duì)列，按照評(píng)價(jià)策略對(duì)隊(duì)列

6、中的鏈接進(jìn)行評(píng)價(jià)，挑選最好的鏈接進(jìn)行抓取。Larry Page 和 Sergey Brin7提出了 PageRank 算法，運(yùn)用于Google搜索引擎。leinberg博士首先提出HITS算法。Diligenti8利用“語(yǔ)境圖”構(gòu)造分類器來(lái)作為爬蟲(chóng)的搜索策略。主題頁(yè)面較近的頁(yè)面將會(huì)被優(yōu)先抓取，認(rèn)為此部分頁(yè)面的主題相關(guān)度較高。陳軍13提出了一種基于網(wǎng)頁(yè)分塊的的 Shark-Search 算法，該算法以塊為基本單位計(jì)算鏈接的價(jià)值。熊忠陽(yáng)14等人提出一種基于信息自增益的主題爬蟲(chóng)搜索策略。1.2.2 主題爬蟲(chóng)系統(tǒng)根據(jù)理論研究，國(guó)內(nèi)外專家設(shè)計(jì)并實(shí)現(xiàn)了很多高效的主題爬蟲(chóng)系統(tǒng)。（1）Scirus系統(tǒng)。Sci

7、rus系統(tǒng)15是由Elsevier Science和FAST合作開(kāi)發(fā)的垂直搜索引擎，其為學(xué)生和科研工作者服務(wù)。該系統(tǒng)曾多次被評(píng)為最佳垂直搜索引擎。（2）美國(guó)國(guó)家數(shù)字科學(xué)圖書(shū)館 Collection Building Programe（CBP）系統(tǒng)。該系統(tǒng)主要面向于科學(xué)、數(shù)學(xué)在線數(shù)字圖書(shū)。其操作簡(jiǎn)單，用戶只需要輸入簡(jiǎn)單的查詢信息，就能查詢到相關(guān)度較高的鏈接。（3）NEC 研究院的 CiteSeer 系統(tǒng)。該系統(tǒng)是面向計(jì)算機(jī)領(lǐng)域的科學(xué)論文檢索系統(tǒng)。（4） STIP系統(tǒng)。該系統(tǒng)是中科院文獻(xiàn)情報(bào)中心實(shí)施中科院文獻(xiàn)信息共享系統(tǒng)的一個(gè)子課題，主要面向科技信息類資源。（5） 南京大學(xué)的互聯(lián)網(wǎng)數(shù)據(jù)采集系統(tǒng)（I

8、DGS)。該系統(tǒng)釆用模式匹配技術(shù)來(lái)實(shí)現(xiàn)自動(dòng)搜索互聯(lián)網(wǎng)上的中英文技術(shù)資料。（6） 北大天網(wǎng)。該系統(tǒng)16采用一組關(guān)鍵詞來(lái)表示一個(gè)主題，爬蟲(chóng)利用這組主題關(guān)鍵詞按照策略從互聯(lián)網(wǎng)中抓取數(shù)據(jù)，使其可以盡可能快且盡可能全面地抓取到與某主題相關(guān)的信息資源。（7） 主題信息采集系統(tǒng)Gsearch。由周鑫等設(shè)計(jì)并實(shí)現(xiàn)。Gsearch 系統(tǒng)17在企業(yè)決策支持、行業(yè)市場(chǎng)分析等領(lǐng)域有著廣泛的引用前景。1.3 本文的研究?jī)?nèi)容本文在通用網(wǎng)絡(luò)爬蟲(chóng)的基礎(chǔ)上，通過(guò)引入網(wǎng)頁(yè)主題內(nèi)容的提取以及基于實(shí)體鏈接的主題識(shí)別算法去識(shí)別主題網(wǎng)頁(yè)，然后使用基于Best-First算法的主題搜索策略去指導(dǎo)主題網(wǎng)絡(luò)爬蟲(chóng)從互聯(lián)網(wǎng)上抓取主題相關(guān)的網(wǎng)頁(yè)。本

9、文的研究?jī)?nèi)容如下：（1）集合網(wǎng)頁(yè)內(nèi)容分布特征以及主題內(nèi)容的相關(guān)特征，設(shè)計(jì)了一種網(wǎng)頁(yè)主題內(nèi)容抽取方法。（2）在對(duì)主題網(wǎng)頁(yè)的識(shí)別方面，采用基于實(shí)體鏈接的主題識(shí)別算法來(lái)識(shí)別主題網(wǎng)頁(yè)。（3）在搜索策略上，采用基于Best-First算法的主題搜索策略來(lái)指導(dǎo)主題網(wǎng)絡(luò)爬蟲(chóng)抓取主題相關(guān)的網(wǎng)頁(yè)。本文共分為六章，篇節(jié)安排如下：第一章，緒論。介紹了研究的背景與意義，主題網(wǎng)絡(luò)爬蟲(chóng)的國(guó)內(nèi)外研究現(xiàn)狀，以及本文研究?jī)?nèi)容和篇章結(jié)構(gòu)。第二章，主要介紹了爬蟲(chóng)的體系結(jié)構(gòu)。通過(guò)介紹通用網(wǎng)絡(luò)爬蟲(chóng)和主題網(wǎng)絡(luò)爬蟲(chóng)的體系結(jié)構(gòu)來(lái)闡述主題網(wǎng)絡(luò)爬蟲(chóng)與通用網(wǎng)絡(luò)爬蟲(chóng)的區(qū)別。第三章，主要介紹網(wǎng)頁(yè)主題內(nèi)容的抽取。先介紹了HTML結(jié)構(gòu)，然后介紹了網(wǎng)頁(yè)的解

10、析以及如何對(duì)網(wǎng)頁(yè)進(jìn)行去噪處理，最后闡述了如何抽取網(wǎng)頁(yè)的主題內(nèi)容以及分詞的相關(guān)內(nèi)容。第四章，重點(diǎn)介紹了基于實(shí)體鏈接的主題識(shí)別算法。這部分主要介紹了主要介紹了實(shí)體鏈接以及如何將主題鏈接運(yùn)用于特征抽取中，進(jìn)而來(lái)提高主題識(shí)別算法的準(zhǔn)確率。第五章，提出了基于Best-First算法的主題搜索策略。首先，介紹了通用網(wǎng)絡(luò)爬蟲(chóng)的搜索策略以及相關(guān)算法，然后，介紹了兩種主要的主題搜索策略以及相關(guān)的比較有代表性的算法，最后，詳細(xì)闡述了本文所研究的基于Best-First算法的主題搜索策略第六章，對(duì)論文工作進(jìn)行總結(jié)與展望。第二章 主題網(wǎng)絡(luò)爬蟲(chóng)的體系結(jié)構(gòu)2.1 組成模塊2.1.1 基本組成圖2-1是主題網(wǎng)絡(luò)爬蟲(chóng)的體系結(jié)

11、構(gòu)圖圖2-1 主題網(wǎng)絡(luò)爬蟲(chóng)的體系結(jié)構(gòu)如圖所示主題網(wǎng)絡(luò)爬蟲(chóng)分為5個(gè)部分:下載,主題內(nèi)容抽取,主題網(wǎng)頁(yè)識(shí)別和鏈接評(píng)價(jià)模塊。(1) 下載模塊。對(duì)于網(wǎng)絡(luò)爬蟲(chóng)來(lái)說(shuō)，下載網(wǎng)頁(yè)始終是其主要的工作。下載模塊需要考慮到多方面的因素，比如：在往往利用多線程下載網(wǎng)頁(yè)，在多線程下載中，對(duì)資源的調(diào)度是很重要的。另外，還要設(shè)定超時(shí)機(jī)制，舍棄掉等待時(shí)間過(guò)長(zhǎng)的網(wǎng)頁(yè)，提高爬蟲(chóng)性能。(2) 主題內(nèi)容抽取。主題網(wǎng)絡(luò)爬蟲(chóng)需要細(xì)致地分析網(wǎng)頁(yè)。主題內(nèi)容抽取對(duì)很大程度上影響了網(wǎng)頁(yè)的主題識(shí)別。噪音內(nèi)容會(huì)影響后續(xù)對(duì)網(wǎng)頁(yè)的主題識(shí)別效果，所以需要消噪。除了消噪，預(yù)處理還包括網(wǎng)頁(yè)主題內(nèi)容的提取、中文分詞、停用詞刪除等操作。(3) 主題網(wǎng)頁(yè)識(shí)別。本文

12、主要通過(guò)判斷網(wǎng)頁(yè)內(nèi)容是否與主題相關(guān)來(lái)對(duì)主題網(wǎng)頁(yè)進(jìn)行識(shí)別。在本文中，主題即預(yù)設(shè)的某一類信息資源的統(tǒng)稱。主題選擇是主題信息抽取的第一步，網(wǎng)頁(yè)的主題由一組主題相關(guān)的特征來(lái)表示。在本文使用文本分類技術(shù)來(lái)識(shí)別網(wǎng)頁(yè)主題。其過(guò)程是:選定一定的主題及與主題相關(guān)的數(shù)據(jù)訓(xùn)練集，用特征向量表示網(wǎng)頁(yè)，然后，利用分類算法對(duì)其進(jìn)行分類。首先用特征向量表示網(wǎng)頁(yè)，然后，利用分類算法對(duì)其進(jìn)行分類。(4) 鏈接主題相關(guān)性評(píng)價(jià)及抽取首先去除掉明顯的廣告鏈接，然后將相對(duì)鏈接轉(zhuǎn)換為絕對(duì)鏈接，最后評(píng)估鏈接的主題相關(guān)性并將其放入待抓取隊(duì)列中。鏈接的主題相關(guān)性的計(jì)算主題要考慮父頁(yè)面和鏈接錨文本的主題相關(guān)性。2.1.2 基本流程爬蟲(chóng)的基本流程

13、可以分成下載過(guò)程和網(wǎng)頁(yè)分析過(guò)程兩個(gè)過(guò)程。下載過(guò)程主要的任務(wù)是從待抓取的鏈接隊(duì)列中獲取鏈接然后從互聯(lián)網(wǎng)上下載網(wǎng)頁(yè)，網(wǎng)頁(yè)分析主要包括網(wǎng)頁(yè)主題內(nèi)容的抽取和主題網(wǎng)頁(yè)的識(shí)別兩個(gè)步驟。(1) 下載過(guò)程step1 調(diào)度模塊從待提取鏈接隊(duì)列中得到鏈接,然后啟動(dòng)相應(yīng)數(shù)量的下載線程。step2 每個(gè)下載線程建立會(huì)話。step3建立連接然后下載網(wǎng)頁(yè)。step4講網(wǎng)頁(yè)存儲(chǔ)到本地,然后再次獲取待下載鏈接,并轉(zhuǎn)到step3,如果已經(jīng)沒(méi)有待下載鏈接則線程退出。(2) 網(wǎng)頁(yè)分析過(guò)程step1 網(wǎng)頁(yè)預(yù)處理模塊先將原始網(wǎng)頁(yè)構(gòu)建成dom樹(shù)。step2 抽取出網(wǎng)頁(yè)中所有錨文本及文本節(jié)點(diǎn)，分別存放到兩個(gè)容器：anchors和texts

14、中。step3 過(guò)濾掉無(wú)關(guān)節(jié)點(diǎn)。step4 過(guò)濾噪音文本。step5 根據(jù)網(wǎng)頁(yè)主題內(nèi)容的特征進(jìn)一步抽取出網(wǎng)頁(yè)的主題內(nèi)容。step6 對(duì)抽取出的網(wǎng)頁(yè)主題內(nèi)容進(jìn)行分詞處理。step7 提取特征，用待分類的特征向量代表網(wǎng)頁(yè)。step8 預(yù)先用訓(xùn)練網(wǎng)頁(yè)集合，訓(xùn)練基于樸素貝葉斯算法的分類器。將待分類向量用分類器分類，判斷是否與主題相關(guān)。step9 如果網(wǎng)頁(yè)與主題相關(guān)，則將網(wǎng)頁(yè)保存到網(wǎng)頁(yè)庫(kù)。step10 從anchors中得到的所有錨節(jié)點(diǎn)，剔除一些鏈接,并評(píng)估鏈接的主題相關(guān)度。將新的鏈接及其主題相關(guān)度存到待抓取的鏈接隊(duì)列中。2.2 主題頁(yè)面的分布特性主題頁(yè)面的分布往往符合四個(gè)特性:Hub/Authorit

15、y特性,Linkage/siblingLocality特性,站點(diǎn)的主題特性,隧道特性。2.2.1 Hub/Authority特性美國(guó)康奈爾大學(xué)Kleinberg教授發(fā)現(xiàn)頁(yè)面大體可以分成兩種,即中心頁(yè)面和權(quán)威頁(yè)面。中心頁(yè)面含有許多鏈接。另外一種頁(yè)面是權(quán)威頁(yè)面,這種頁(yè)面傾向于說(shuō)明單一主題。Kleinberg教授對(duì)一個(gè)頁(yè)面引入Hub和Authority值體現(xiàn)上述特性18,并依據(jù)這種特性提出HITS算法。2.2.2 Linkage/Sibling Locality特性Linkage特性是指網(wǎng)頁(yè)包含的鏈接所指向的網(wǎng)頁(yè)的主題通常與該主題的主題相關(guān)。Sibling Locality特性是指網(wǎng)頁(yè)內(nèi)同一區(qū)域的鏈

16、接通常主題相關(guān)19。2.2.3 站點(diǎn)的主題特性一個(gè)站點(diǎn)往往包含一個(gè)或多個(gè)主題。往往相關(guān)主題的頁(yè)面聚集在一起，而不同主題的頁(yè)面團(tuán)之間的鏈接較少。2.2.4 隧道特性主題頁(yè)面分布還有一種特性，即站點(diǎn)上的各個(gè)主題頁(yè)面團(tuán)往往會(huì)通過(guò)一些主題無(wú)關(guān)鏈接連接在一起。這些鏈接像是橫跨在主題頁(yè)面團(tuán)之間的隧道，這就是隧道特性。在抓取過(guò)程中，隧道會(huì)影響抓取效率。2.3 搜索策略以及鏈接提取搜索策略是網(wǎng)絡(luò)爬蟲(chóng)爬蟲(chóng)從互聯(lián)網(wǎng)上抓取網(wǎng)頁(yè)的核心，其很大程度上決定了爬蟲(chóng)的效率。其中部分鏈接需要根據(jù)相關(guān)協(xié)議排除掉。2.3.1 robots協(xié)議和相對(duì)鏈接的轉(zhuǎn)換 robots.txt文件和META標(biāo)簽（1）robots.

17、txt。往往網(wǎng)站的一些內(nèi)容不希望被爬蟲(chóng)抓取。ROBOTS開(kāi)發(fā)界提供了兩個(gè)解決方案:一個(gè)是robots.txt,另一個(gè)是META標(biāo)簽。robots.txt是存放于網(wǎng)站根目錄下的文件名小寫(xiě)的一個(gè)純文本文件,網(wǎng)站中不想被網(wǎng)絡(luò)爬蟲(chóng)訪問(wèn)的部分可在該文件中申明。“robots.txt”文件包含許多的記錄,每條記錄的格式如下所示:robots.txt文件針對(duì)整個(gè)網(wǎng)站的，用來(lái)描述站點(diǎn)的爬蟲(chóng)的訪問(wèn)情況，而META標(biāo)簽則是主要用于單個(gè)具體的頁(yè)面。（2）META標(biāo)簽中沒(méi)有大小寫(xiě)之分,name=”Robots”表示作用于所有的網(wǎng)絡(luò)爬蟲(chóng)，也可以針對(duì)某個(gè)具體網(wǎng)絡(luò)爬蟲(chóng)寫(xiě)為name=”BaiduSpider”。

18、 相對(duì)鏈接的轉(zhuǎn)換相對(duì)URL有服務(wù)器相對(duì)URL和文檔相對(duì)URL。絕對(duì)URL的格式如下:scheme: /server/path/resource其中:scheme指定資源所使用的協(xié)議,有http,mailto,ftp等協(xié)議。server是指資源所在服務(wù)器的名稱比如。path是指到達(dá)資源的路徑,比如/18/0402/09。resource通常是文件名比如:DECL75C900118017.html。它可能是單個(gè)二進(jìn)制流的“簡(jiǎn)單文件”,也可能是“結(jié)構(gòu)化文檔”。定位資源的所有信息都包括在“絕對(duì)URL”中。相對(duì)URL相對(duì)于某一網(wǎng)頁(yè)位置的目標(biāo)鏈接。因?yàn)樵诂F(xiàn)實(shí)環(huán)境中，網(wǎng)站服務(wù)器發(fā)生變更會(huì)引發(fā)鏈接錯(cuò)誤，所以使

19、用相對(duì)鏈接指向同一服務(wù)器下的網(wǎng)頁(yè)。當(dāng)前網(wǎng)頁(yè)位置一般可視為特定網(wǎng)頁(yè)位置,或者用base標(biāo)簽定義,如,那么該網(wǎng)頁(yè)中所有的鏈接都是以為前綴。2.3.2 搜索策略概述通用網(wǎng)絡(luò)爬蟲(chóng)為了較高的覆蓋率，一般采用圖的廣度優(yōu)先策略去遍歷互聯(lián)網(wǎng)上的網(wǎng)頁(yè);主題網(wǎng)絡(luò)爬蟲(chóng)需要搜索的內(nèi)容只會(huì)針對(duì)特定的主題，而不需遍歷整個(gè)網(wǎng)絡(luò)，只需要選擇主題相關(guān)的網(wǎng)頁(yè)進(jìn)行遍歷。主題網(wǎng)絡(luò)爬蟲(chóng)通常采用“最好優(yōu)先”原則從互聯(lián)網(wǎng)上搜索網(wǎng)頁(yè)。每次對(duì)“最有價(jià)值”的鏈接進(jìn)行訪問(wèn)來(lái)高效地獲取到更多與主題相關(guān)的網(wǎng)頁(yè)。主題網(wǎng)絡(luò)爬蟲(chóng)不同的搜索策略由鏈接的價(jià)值評(píng)價(jià)方法決定。鏈接往往包含在頁(yè)面內(nèi)容之中，所以一般父頁(yè)面的價(jià)值高，其所包含的鏈接一般也具有較高價(jià)值，因此

20、對(duì)評(píng)價(jià)鏈接價(jià)值往往要結(jié)合對(duì)網(wǎng)頁(yè)內(nèi)容的分析。2.4 本章小結(jié)本章概述了主題網(wǎng)絡(luò)爬蟲(chóng)的基本流程和組成部分，介紹了鏈接提取規(guī)則。最后介紹了網(wǎng)絡(luò)爬蟲(chóng)搜索策略的概念。第三章 網(wǎng)頁(yè)主題內(nèi)容抽取3.1 HTML簡(jiǎn)介目前大部分網(wǎng)頁(yè)都是由HTML編寫(xiě)。網(wǎng)頁(yè)通過(guò)超鏈接鏈接在一起，進(jìn)而形成一個(gè)緊密連接在一起的網(wǎng)絡(luò)結(jié)構(gòu)。對(duì)于通用網(wǎng)絡(luò)爬蟲(chóng)來(lái)說(shuō)，只需要抽取網(wǎng)頁(yè)中的鏈接;然而對(duì)于主題網(wǎng)絡(luò)爬蟲(chóng)則需要分析并提取網(wǎng)頁(yè)內(nèi)容，然后對(duì)鏈接進(jìn)行價(jià)值評(píng)估及對(duì)其進(jìn)行取舍。大致可將標(biāo)簽分為三類:（1）對(duì)網(wǎng)頁(yè)進(jìn)行布局的標(biāo)簽。常用的標(biāo)簽有、等。（2）描述信息顯示特點(diǎn)的標(biāo)簽。常用的重要信息標(biāo)簽有、等十幾種。（3）包含超鏈接的標(biāo)簽:超鏈接用于連接各個(gè)

21、頁(yè)面能表示網(wǎng)頁(yè)之間的關(guān)系。這類標(biāo)簽有、等。HTML文檔主要由頭部(head)和主體(body)組成20HTML文檔主要有以下兩個(gè)部分:（1）頭部區(qū)段。（2）主體區(qū)段,包含這些標(biāo)簽:標(biāo)題、文本和段落、換行和非換行空格、標(biāo)線、列表、文本屬性。標(biāo)簽由屬性和標(biāo)簽名組成，而屬性由屬性名以及對(duì)應(yīng)的屬性值組成。有些屬性要求用引號(hào),有些則不要。本文將會(huì)忽略掉一些與內(nèi)容無(wú)關(guān)的標(biāo)簽和它們所包含的內(nèi)容。這也有助于消除一些噪音。3.2 網(wǎng)頁(yè)文件解析HTML文件一般用dom樹(shù)表示。解釋HTML文件的過(guò)程就是將字符流表示成HTML樹(shù)21的過(guò)程。如下一個(gè)html文檔可以表示成如圖3-1所示的html樹(shù)。標(biāo)題a href=a

22、 href=段落上述html文件的樹(shù)結(jié)構(gòu)表示如圖3-1所示:圖3-1 html文件的樹(shù)結(jié)構(gòu)目前，有很多構(gòu)造標(biāo)簽樹(shù)的工具，如：htmlParser,W3C HTML lexical analyzer22等。3.3 網(wǎng)頁(yè)去噪許多網(wǎng)頁(yè)都包含與主題內(nèi)容無(wú)關(guān)的內(nèi)容。如圖3-2所示的新聞網(wǎng)頁(yè)截圖的網(wǎng)頁(yè)，可以認(rèn)為正文塊以外的部分都是噪音。圖3-2 網(wǎng)頁(yè)的正文塊從網(wǎng)頁(yè)的截圖可以看出，網(wǎng)頁(yè)除了正文塊外，其余部分由廣告、導(dǎo)航鏈接、搜索服務(wù)等組成。在主題搜索領(lǐng)域，大量的噪音內(nèi)容會(huì)導(dǎo)致主題漂移。在提取主題相關(guān)內(nèi)容時(shí)，如果不去除原始網(wǎng)頁(yè)中的噪音內(nèi)容，往往容易將噪音內(nèi)容作為主題相關(guān)的內(nèi)容，影響對(duì)網(wǎng)頁(yè)主題的識(shí)別。3.3.1

23、 利用統(tǒng)計(jì)學(xué)去噪用統(tǒng)計(jì)的方法去噪23的流程如下。(1) 刪除噪音塊：網(wǎng)頁(yè)去噪的基本方法是利用各種通用的特征來(lái)區(qū)分有效的正文和頁(yè)眉、頁(yè)腳、廣告等其他信息。其中一個(gè)常用的特征是鏈接文字比率。根據(jù)鏈接文字比率過(guò)濾掉噪音。(2) 劃分段落。可以把HTML頁(yè)面劃分成多個(gè)段落(Paragraph)。簡(jiǎn)單的實(shí)現(xiàn)方法是，根據(jù)這些標(biāo)簽來(lái)劃分段落。(3) 評(píng)估段落。每個(gè)段落內(nèi)的文字因其視覺(jué)上或者是主題上對(duì)文檔的貢獻(xiàn)程度而具有不同的權(quán)重。選取分值最大段落最為正文塊。流程圖如下：圖3-3 去噪流程3.4 主題內(nèi)容的抽取網(wǎng)頁(yè)主題內(nèi)容的抽取是網(wǎng)頁(yè)主題識(shí)別的第一步，主題內(nèi)容抽取的準(zhǔn)確率直接影響到網(wǎng)頁(yè)主題識(shí)別的準(zhǔn)確率。劉軍等

24、24（基于DOM的網(wǎng)頁(yè)主題信息的抽?。┨岢鰳?gòu)建文檔對(duì)象模型DOM樹(shù)，然后添加顯示語(yǔ)義等屬性來(lái)解決HTML文檔半結(jié)構(gòu)化的不足，并提出一種聚類規(guī)則來(lái)對(duì)其進(jìn)行分塊，最后提取出主題信息。在此基礎(chǔ)上，通過(guò)對(duì)大量網(wǎng)頁(yè)的分析發(fā)現(xiàn)，除了正文的內(nèi)容塊，網(wǎng)頁(yè)的標(biāo)題(title標(biāo)簽的內(nèi)容)及meta標(biāo)簽的屬性content的內(nèi)容往往也攜帶有網(wǎng)頁(yè)的主題信息，所以抽取的時(shí)候這部分內(nèi)容也應(yīng)該被抽取。網(wǎng)頁(yè)一般可分為索引型網(wǎng)頁(yè)和主題型網(wǎng)頁(yè)，網(wǎng)頁(yè)主題的識(shí)別是針對(duì)于主題型網(wǎng)頁(yè)。主題網(wǎng)頁(yè)所包含的鏈接文本往往是廣告等與主題無(wú)關(guān)的文本，所以，應(yīng)該先去除掉。然后還應(yīng)去除掉網(wǎng)頁(yè)版本信息等與主題無(wú)關(guān)的噪音文本。綜上所述，網(wǎng)頁(yè)主題內(nèi)容的抽取算

25、法如下：Step1首先選取p,li,td,h1作為分塊節(jié)點(diǎn)Step2去除網(wǎng)頁(yè)a標(biāo)簽及其內(nèi)容Step3獲取title標(biāo)簽中的文本，然后刪除title標(biāo)簽及其內(nèi)容Step4獲取meta標(biāo)簽的屬性content的值,然后刪除meta標(biāo)簽Step5對(duì)p標(biāo)簽進(jìn)行與3相同的操作Step6對(duì)li標(biāo)簽進(jìn)行與3相同的操作Step7對(duì)于td標(biāo)簽進(jìn)行與3相同的操作Step8對(duì)于h1標(biāo)簽進(jìn)行與3相同的操作取“，。？；、,.?”標(biāo)點(diǎn)符號(hào)作為分塊節(jié)點(diǎn)的特征，如果節(jié)點(diǎn)中的文本包含這些特征則認(rèn)為內(nèi)容是主題相關(guān)，就對(duì)其進(jìn)行抽取。3.5 本章小結(jié)本章先介紹了網(wǎng)頁(yè)處理中的各種預(yù)處理過(guò)程,包括HTML解析、網(wǎng)頁(yè)消噪。為了提取網(wǎng)頁(yè)中的

26、主要內(nèi)容,有必要剔除原始網(wǎng)頁(yè)的噪音。然后根據(jù)網(wǎng)頁(yè)的主題內(nèi)容的特征，提取出網(wǎng)頁(yè)的主題內(nèi)容。第四章 基于實(shí)體鏈接的主題識(shí)別算法4.1 實(shí)體鏈接簡(jiǎn)介在介紹實(shí)體鏈接之前，首先，需要了解實(shí)體的概念。實(shí)體是存在于世界上的某一個(gè)對(duì)象或者對(duì)象的集合，實(shí)體一般用屬性來(lái)描述。實(shí)體鏈接就是把文本中的實(shí)體表述鏈接到知識(shí)庫(kù)中的相應(yīng)實(shí)體的過(guò)程29。在實(shí)體鏈接中所使用的知識(shí)庫(kù)包括Wikipedia、Freebase、YAGO、DBpedia等30。目前復(fù)旦大學(xué)圖數(shù)據(jù)管理實(shí)驗(yàn)室的知識(shí)工廠構(gòu)建了知識(shí)庫(kù)，并提供了比較全面的接口，本文所使用的就是知識(shí)工廠提供的知識(shí)庫(kù)以及相關(guān)接口。在一段文本中，實(shí)體鏈接主要有兩件事，一方便是識(shí)別出文

27、本中的實(shí)體指稱，另一方面就是將識(shí)別出的實(shí)體指稱與知識(shí)庫(kù)中的相應(yīng)實(shí)體相關(guān)聯(lián)。由于自然語(yǔ)言中普遍存在以此多義和別名現(xiàn)象，因此需要根據(jù)文本中實(shí)體表述的上下文信息去確定實(shí)體表述所指向的實(shí)體。所以，實(shí)體鏈接主要包含兩項(xiàng)關(guān)鍵技術(shù)：實(shí)體識(shí)別、實(shí)體消歧。實(shí)體識(shí)別31是指識(shí)別一個(gè)文本中的實(shí)體表述，這個(gè)實(shí)體表述可能是指向?qū)嶓w的詞或者短語(yǔ)。實(shí)體消歧32是指給定實(shí)體指稱及其所在上下文、候選實(shí)體，判斷其在當(dāng)前上下文中所指向?qū)嶓w的過(guò)程。4.2 CN-DBpediaCN-DBpedia33是由復(fù)旦大學(xué)知識(shí)工場(chǎng)實(shí)驗(yàn)室（Knowledge Works）研發(fā)并維護(hù)的大規(guī)模通用領(lǐng)域結(jié)構(gòu)化百科，其前身是復(fù)旦GDM中文知識(shí)圖譜，是國(guó)內(nèi)

28、最早推出的也是目前最大規(guī)模的開(kāi)放百科中文知識(shí)圖譜，涵蓋數(shù)千萬(wàn)實(shí)體和數(shù)億級(jí)的關(guān)系。CN-DBpedia以通用百科知識(shí)沉淀為主線，以垂直縱深領(lǐng)域圖譜積累為支線，致力于為機(jī)器語(yǔ)義理解提供了豐富的背景知識(shí)，為實(shí)現(xiàn)機(jī)器語(yǔ)言認(rèn)知提供必要支撐。CN-DBpedia已經(jīng)從百科領(lǐng)域延伸至法律、工商、金融、文娛、科技、軍事、教育、醫(yī)療等十多個(gè)垂直領(lǐng)域，為各類行業(yè)智能化應(yīng)用提供支撐性知識(shí)服務(wù)，目前已有近百家單位在使用。CN-DBpedia具有體量巨大、質(zhì)量精良、實(shí)時(shí)更新、豐富的API服務(wù)等特色。CN-DBpedia已經(jīng)成為業(yè)界開(kāi)放中文知識(shí)圖譜的首選。本文主要用CN-DBpedia作為知識(shí)庫(kù)，并利用知識(shí)工廠提供的相關(guān)

29、接口識(shí)別文本中的實(shí)體，然后進(jìn)行再利用其提供的接口進(jìn)行實(shí)體鏈接。例如如下文本:圖 4.1調(diào)用知識(shí)工廠的接口，獲取到如下結(jié)果:圖 4.2其中cuts字段是對(duì)文本的詞集合,entities字段是識(shí)別出的文本中的實(shí)體。然后調(diào)用知識(shí)工廠提供的獲取知識(shí)庫(kù)中的實(shí)體詳情的接口，獲取的實(shí)體信息如下所示:圖 4.3其中，status表示接口調(diào)用狀態(tài)，ret字段表示獲取的結(jié)果，其中包含實(shí)體的詳細(xì)信息:拼音、中文名、亦稱、外文名稱、CATEGORY_ZH、DESC。上述過(guò)程就是識(shí)別文本中的實(shí)體并鏈接到知識(shí)庫(kù)中獲取實(shí)體信息的過(guò)程，也即實(shí)體鏈接的過(guò)程。4.3 基于實(shí)體鏈接的特征抽取特征抽取對(duì)于主題識(shí)別來(lái)說(shuō)，是特別重要的一

30、步，抽取出的特征準(zhǔn)確與否，決定著主題識(shí)別的準(zhǔn)確率。傳統(tǒng)的方式，由于分詞的問(wèn)題，無(wú)法很好的把某些主題特征抽取出來(lái)，所以本文將實(shí)體鏈接引入到特征抽取的過(guò)程中，以知識(shí)庫(kù)為支撐，來(lái)更加準(zhǔn)確的將主題特征抽取出來(lái)。4.3.1 候選特征集合抽取首先，從訓(xùn)練語(yǔ)料中抽取出候選特征集合34。圖 4.4如上圖所示，具體步驟如下：(1)準(zhǔn)備訓(xùn)練語(yǔ)料。準(zhǔn)備若干主題相關(guān)的文本。(2)實(shí)體鏈接處理。使用知識(shí)工廠的接口將這些主題相關(guān)的文本逐句進(jìn)行實(shí)體識(shí)別并分詞，且獲取實(shí)體信息從實(shí)體信息中抽取出更多的候選特征。(3)獲取候選特征集合。將上一步獲取到的詞集合進(jìn)行去重，去停用詞處理，獲取到候選特征集合。從搜狗語(yǔ)料中選擇與“軍事”主

31、題相關(guān)50篇的新聞文章作為選擇候選特征的語(yǔ)料集合。首先，利用知識(shí)工程的接口對(duì)語(yǔ)料文章進(jìn)行分詞并識(shí)別語(yǔ)料文章的實(shí)體，由于有知識(shí)庫(kù)的支撐，所以能更好的將文章中的潛在的特征切分出來(lái)。對(duì)于，識(shí)別出的實(shí)體，進(jìn)行實(shí)體鏈接，獲取到實(shí)體的信息。如下圖所示：圖 4.5如上圖所示，實(shí)體“防空導(dǎo)彈”的實(shí)體信息中，可將“別稱”、“類別”及“CATEGORY_ZH”屬性抽取出來(lái)合并到候選特征集合中。“DESC”屬性加入到提取候選特征的語(yǔ)料集合中做進(jìn)一步處理。如上所述，基于實(shí)體鏈接的方式，由于有知識(shí)庫(kù)的支撐，一方面，能較準(zhǔn)確地將潛在的特征抽取出來(lái)，另一方面，由于抽取特征的訓(xùn)練語(yǔ)料是有限的，可以從實(shí)體信息中抽取出更多的特征

32、。如下圖所示，為使用了實(shí)體鏈接所挑選出的候選特征集合實(shí)例:圖 常見(jiàn)特征抽取算法 目前，常用的特征選擇算法如下：文檔頻率35、信息增益36、互信息37及詞條的統(tǒng)計(jì)38等。（1）文檔頻率。 訓(xùn)練語(yǔ)料中包含某一詞語(yǔ)的文檔的條數(shù)就是該詞語(yǔ)的文檔頻率。該方法的基本思想是：出現(xiàn)頻率較低的詞語(yǔ)往往攜帶很少的信息量，因而無(wú)法很好的將類別區(qū)分開(kāi)來(lái)，因此可以刪除較低頻率的詞語(yǔ)，這樣既能降低特征維度又能提高分類的準(zhǔn)確率。（2） 信息增益（Information Gain）。信息增益（IG）是計(jì)算某一特征出現(xiàn)出現(xiàn)和不出現(xiàn)兩種情況下，系統(tǒng)攜帶信息量的差值。對(duì)于文本分類而言，包含特征詞 t和不包含特征詞

33、t的文檔頻數(shù)差值代表了特征詞t的IG值。IG值采用如下的公式計(jì)算： (4-1) 公式中，表示類文檔在語(yǔ)料中出現(xiàn)的概率，表示語(yǔ)料中包含詞語(yǔ)的文檔概率，表示文檔包含詞語(yǔ) 時(shí)屬于類的條件概率，表示語(yǔ)料中不包含詞語(yǔ)的文檔概率，表示文檔不包含詞語(yǔ)時(shí)屬于類的條件概率，表示類別數(shù)。（3） CHI統(tǒng)計(jì)CHI統(tǒng)計(jì)常常稱為開(kāi)方統(tǒng)計(jì)，用于檢驗(yàn)兩個(gè)變量是否獨(dú)立。在兩個(gè)變量是相互獨(dú)立的前提下，將樣本的實(shí)際觀測(cè)值和理論值的偏離程度計(jì)算出來(lái)，表示為CHI值。CHI值越大，兩變量趨于相關(guān);反之則兩變量趨于獨(dú)立。特征詞和文檔類別的相關(guān)程度也可以用此方式來(lái)衡量。先預(yù)設(shè)詞條與某一類別是獨(dú)立的，以此為基礎(chǔ)計(jì)算出的詞條的CHI值越大則

34、說(shuō)明結(jié)果與假設(shè)偏差越大，則該詞條與類別越相關(guān)。因此，該方法特征選擇的過(guò)程即:計(jì)算每個(gè)詞條與類別的CHI值，并從大到小排序，靠前的值則為特征。詞語(yǔ)對(duì)于類別的CHI值計(jì)算公式如下： (4-2)（4） 互信息（Mutual Information）在信息論中，互信息（MI）表示兩個(gè)事件發(fā)生相關(guān)聯(lián)而提供的信息量?；バ畔⒘吭酱螅嚓P(guān)性也就越大。詞語(yǔ)和類別的互信息計(jì)算公式如下：（4-3）公式(4-3)中A、B、C、D和N的含義與公式（4-2）中一致。實(shí)驗(yàn)表明，信息增益能比較有效的進(jìn)行特征提取，所以本文采用信息增益的算法進(jìn)行特征提取。4.3.3 最終特征抽取在候選特征集合的基礎(chǔ)上，抽取最終的特征集合，具體步

35、驟如下：圖 4.7(1)計(jì)算信息增益值。在訓(xùn)練語(yǔ)料中計(jì)算候選特征集合中每個(gè)特征的信息增益值。(2)獲取特征。按照信息增益值遞減排序，選擇靠前的若干特征。(4)獲取最終特征。將從實(shí)體信息中獲取到特征加入到（2）步驟中獲取的特征集合中，將這個(gè)特征集合作為最終的特征集合。4.4 基于樸素貝葉斯算法的分類器本文采用樸素貝葉斯算法構(gòu)造分類器。假設(shè)用特征集合來(lái)表示每個(gè)實(shí)例A，而類c從某有限集合C中取值?，F(xiàn)提供一訓(xùn)練實(shí)例集和一測(cè)試實(shí)例(a1,a2,am)。需要分類的實(shí)例A的目標(biāo)是獲取實(shí)例(a1,a2,am)的類標(biāo)記。得到： （4-4）現(xiàn)在要做的就是基于訓(xùn)練實(shí)例集估計(jì)式(4-14)中的兩個(gè)概率值。樸素貝葉斯分

36、類器(nave Bayes classifiers)39假定：在給定類標(biāo)記時(shí)屬性值之間是相互條件獨(dú)立的。也就是說(shuō)，聯(lián)合概率正好是每個(gè)單獨(dú)特征概率的乘積。具體的公式如下： (4-5)代入式（4-14）中，可得樸素貝葉斯分類器的分類公式： (4-6)式中，為x的第j個(gè)特征值、概率p(c)和可以通過(guò)計(jì)算訓(xùn)練實(shí)例集中不同類和特征值組合的出現(xiàn)頻率來(lái)簡(jiǎn)單計(jì)算,具體的公式如下: (4-7)(4-8)式中,n為訓(xùn)練實(shí)例的個(gè)數(shù)、為第i個(gè)訓(xùn)練實(shí)例的類標(biāo)記、為第i個(gè)訓(xùn)練實(shí)例的第j個(gè)屬性值, 為一個(gè)二值函數(shù),當(dāng)時(shí)為l,否則為0。顯然,當(dāng)出現(xiàn)零頻率屬性值的時(shí)候，這種方法會(huì)導(dǎo)致過(guò)低估計(jì)概率。更極端的情況會(huì)使得某個(gè)概率值為

37、0,進(jìn)而導(dǎo)致由式(4-6)計(jì)算的整個(gè)量為0。常常使用Laplace估計(jì)來(lái)進(jìn)行平滑處理進(jìn)而避免上述問(wèn)題,重寫(xiě)式(4-7)和式(4-8)得到: (4-9)(4-10)式中,為類的個(gè)數(shù)、為訓(xùn)練實(shí)例第個(gè)屬性的取值個(gè)數(shù)?；趯?shí)體鏈接的樸素貝葉斯分類器的整體框架如圖3.3所示。圖 4.8其工作流程如下：(1)使用基于實(shí)體鏈接的特征抽取方法進(jìn)行特征提取。(2)根據(jù)獲取到的特征集合，構(gòu)建樸素貝葉斯分類器，并對(duì)其進(jìn)行訓(xùn)練。(3)對(duì)爬蟲(chóng)抓取到的網(wǎng)頁(yè)進(jìn)行預(yù)處理，包括，主題信息抽取、分詞等預(yù)處理，然后將網(wǎng)頁(yè)向量化表示。(4)利用分類器對(duì)向量化處理后的網(wǎng)頁(yè)進(jìn)行主題識(shí)別，如果網(wǎng)頁(yè)屬于主題類，則將網(wǎng)頁(yè)保存到主題頁(yè)面庫(kù)，否則

38、舍棄該頁(yè)面。4.5 實(shí)驗(yàn)分析本小節(jié)來(lái)通過(guò)實(shí)驗(yàn)驗(yàn)證本章提出的基于實(shí)體鏈接的樸素貝葉斯分類器在主題識(shí)別中的效果。對(duì)于主題識(shí)別效果的評(píng)判，主要采用三個(gè)指標(biāo)：準(zhǔn)確率(P)、召回率(R)和F值40。準(zhǔn)確率是表示準(zhǔn)確識(shí)別出的主題相關(guān)的文本數(shù)量比例;召回率是準(zhǔn)確識(shí)別出的主題相關(guān)的文本數(shù)量與訓(xùn)練集中所有主題相關(guān)的文本數(shù)量的比例;F值是一個(gè)綜合評(píng)價(jià)指標(biāo)。假定：在訓(xùn)練語(yǔ)料中，屬于與主題相關(guān)且被判定為與主題相關(guān)的文本是a,與主題無(wú)關(guān)但被判定為主題相關(guān)的文本數(shù)目是b,屬于與主題相關(guān)但未能被判定為與主題相關(guān)的文本數(shù)量是c,那么三個(gè)評(píng)價(jià)指標(biāo)的計(jì)算公式如下：準(zhǔn)確率： 召回率： F值： 現(xiàn)從搜狗新聞?wù)Z料中選擇軍事（587篇）

39、及非軍事(856篇)的文章共計(jì)1443篇，作為訓(xùn)練語(yǔ)料。使用本章提出基于實(shí)體鏈接的方法去構(gòu)建樸素貝葉斯分類器，進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如下：表4.1 實(shí)驗(yàn)結(jié)果識(shí)別出主題相關(guān)文本識(shí)別正確的文本準(zhǔn)確率(P)召回率(R)F值(F)NB61351684.2%87.9%86%基于實(shí)體鏈接的NB62755280%94%90.9%從實(shí)驗(yàn)結(jié)果來(lái)看，相比與傳統(tǒng)的樸素貝葉斯分類器，引入實(shí)體鏈接技術(shù)對(duì)其進(jìn)行改進(jìn)能取得較好的效果。4.6 本章小結(jié)本章主要介紹了基于實(shí)體鏈接的樸素貝葉斯分類器。首先，介紹了實(shí)體鏈接的相關(guān)概念，接著介紹了本文所用的知識(shí)庫(kù)CN-DBpedia以及相關(guān)接口。然后，重點(diǎn)闡述了基于實(shí)體鏈接的特征抽取方法

40、，將實(shí)體鏈接技術(shù)運(yùn)用于特征抽取中來(lái)更好的提取出主題相關(guān)的特征。接著，詳細(xì)介紹了基于樸素貝葉斯算法的分類器的構(gòu)造以及工作流程。最后，通過(guò)實(shí)驗(yàn)分析，證明，本章提出的基于實(shí)體鏈接的主題識(shí)別算法能取得較好的效果。第5章 基于Best-First算法的主題搜索策略搜索策略是爬蟲(chóng)預(yù)設(shè)的一種爬行方法，用于指導(dǎo)網(wǎng)絡(luò)爬蟲(chóng)抓取互聯(lián)網(wǎng)上的網(wǎng)頁(yè)。本章在前人的基礎(chǔ)上，設(shè)計(jì)一種主題爬蟲(chóng)策略去指導(dǎo)主題爬蟲(chóng)去抓取網(wǎng)頁(yè)。5.1 通用搜索策略互聯(lián)網(wǎng)可以看成一個(gè)復(fù)雜而龐大的非連通圖41。參照?qǐng)D的遍歷方法，通用網(wǎng)絡(luò)爬蟲(chóng)一般有兩種遍歷策略，即廣度優(yōu)先策略和深度優(yōu)先策略42。圖5.1 網(wǎng)絡(luò)鏈接結(jié)構(gòu)圖圖5.1是個(gè)簡(jiǎn)單的網(wǎng)絡(luò)鏈接結(jié)構(gòu)圖，其中

41、網(wǎng)絡(luò)中的網(wǎng)頁(yè)由節(jié)點(diǎn)表示，而鏈接則由邊來(lái)表示。深度優(yōu)先搜索的思路是，爬蟲(chóng)沿著某一方向一直搜索，直到此方向沒(méi)有可繼續(xù)搜索的節(jié)點(diǎn)則換個(gè)方向繼續(xù)進(jìn)行。以圖5.1為例，爬蟲(chóng)的搜索順序?yàn)锳BDECFG。廣度有限搜索策略的思路是由近及遠(yuǎn)一層層抓取搜索網(wǎng)絡(luò)上的節(jié)點(diǎn)，同樣以圖5.1所代表的網(wǎng)絡(luò)結(jié)構(gòu)為例，其中，A節(jié)點(diǎn)為第一層頁(yè)面，B、C節(jié)點(diǎn)為第二層頁(yè)面，D、E、F、G為第三層頁(yè)面，所以按照廣度優(yōu)先的策略，爬蟲(chóng)的抓取網(wǎng)頁(yè)的路徑為ABCDEFG。理論上來(lái)說(shuō)，這兩種搜索策略都是可行的。但是，真實(shí)環(huán)境的互聯(lián)網(wǎng)龐大且復(fù)雜，深度優(yōu)先策略往往會(huì)陷入某一方向，而且，一般網(wǎng)頁(yè)的層次越深價(jià)值越低，所以，通用網(wǎng)絡(luò)爬蟲(chóng)一般采用廣度優(yōu)先策

42、略。然而，通常通用網(wǎng)絡(luò)爬蟲(chóng)為了追求覆蓋率，所以抓取到的資源往往價(jià)值不高。5.2 常用主題搜索策略主題網(wǎng)絡(luò)爬蟲(chóng)的目標(biāo)是抓取與給定主題相關(guān)的網(wǎng)頁(yè)，所以，需要預(yù)測(cè)鏈接內(nèi)容的主題相關(guān)性，然后決定是否進(jìn)行抓取。不同于通用搜索策略，主題搜索策略是在主題的指導(dǎo)下，對(duì)鏈接的價(jià)值進(jìn)行評(píng)估。根據(jù)鏈接的主題相關(guān)性的大小，將鏈接插入到待抓取隊(duì)列中，并選擇主題相關(guān)度高的鏈接繼續(xù)抓取43。這樣主題網(wǎng)絡(luò)爬蟲(chóng)能盡可能快且多的抓取到主題相關(guān)的網(wǎng)頁(yè)，提高了抓取效率。近年來(lái)，人們對(duì)主題搜索策略主要分為兩類：一種是基于內(nèi)容評(píng)價(jià)，另一種是基于鏈接結(jié)構(gòu)評(píng)價(jià)44。5.2.1 基于內(nèi)容評(píng)價(jià)的搜索策略該搜索策略主要是通過(guò)分析網(wǎng)頁(yè)內(nèi)容與所給主題

43、的相關(guān)性來(lái)指導(dǎo)主題網(wǎng)絡(luò)爬蟲(chóng)抓取網(wǎng)頁(yè)。下面主要通過(guò)介紹如下算法來(lái)對(duì)這類搜索策略進(jìn)行分析。（1）Best-First算法最佳優(yōu)先搜索（Best First Search），是一種啟發(fā)式搜索算法,它可以看做是廣度優(yōu)先搜索算法的一種改進(jìn)。最佳優(yōu)先搜索算法在廣度優(yōu)先搜索的基礎(chǔ)上，用啟發(fā)估價(jià)函數(shù)對(duì)將要被遍歷到的點(diǎn)進(jìn)行評(píng)價(jià)，然后選擇代價(jià)小的進(jìn)行遍歷，直到找到目標(biāo)節(jié)點(diǎn)或者遍歷完所有點(diǎn)。用來(lái)做主題網(wǎng)絡(luò)爬蟲(chóng)的搜索策略的基本思路是:對(duì)鏈接的價(jià)值進(jìn)行評(píng)估，優(yōu)先抓取價(jià)值高的鏈接所指向的網(wǎng)頁(yè)。（2）Fish-Search算法De Bra等于提出Fish-Search算法，該算法模擬魚(yú)群覓食行為。該算法假設(shè)每個(gè)鏈接就是一條

44、魚(yú)，該鏈接的頁(yè)面中的鏈接代表魚(yú)的后代。如果魚(yú)找到事務(wù)，即鏈接找到主題相關(guān)頁(yè)面，那么將繼續(xù)沿這個(gè)方向繼續(xù)搜索。反之，如果魚(yú)找不到食物，則后代變得虛弱，即此方向找不到主題相關(guān)頁(yè)面。經(jīng)過(guò)多次尋找，直到此線路再無(wú)其他鏈接則從其他方向重新開(kāi)始搜索。（3） Shark-Search算法Fish-Search算法使用二值模型來(lái)來(lái)判斷魚(yú)是否找到食物，這樣無(wú)法精確的對(duì)鏈接優(yōu)先隊(duì)列進(jìn)行排序。Hersovici 提出了Shark-Search算法來(lái)改進(jìn)Fish-Search算法。其相關(guān)度一般在0和1之間取值44。5.2.1 基于鏈接結(jié)構(gòu)評(píng)價(jià)的搜索策略基于鏈接結(jié)構(gòu)評(píng)價(jià)的搜索策略中，PageRank 算法和 Hits

45、算法是最為基礎(chǔ)、典型的兩種算法。（1）PageRank 算法。定義“入度”和“出度”的概念，“入度”即指向網(wǎng)頁(yè)的鏈接，“出度”即網(wǎng)頁(yè)中指向其他頁(yè)面的鏈接。PageRank 算法主要是依據(jù)入度和出度，對(duì)鏈接價(jià)值進(jìn)行評(píng)估。頁(yè)面 A 的 PageRank的計(jì)算公式如下: （5-1）在公式中： 代表網(wǎng)頁(yè) A 的 PageRank 值。代表鏈接到 A 的網(wǎng)頁(yè)的 PageRank 值。代表網(wǎng)頁(yè) Ti的出度。d 是阻尼系數(shù)，主要起調(diào)控作用，在 0 到 1 之間取值，一般設(shè)置 d 為0.85。（2）HITS 算法。HITS 算法的基本流程為：1）網(wǎng)頁(yè) i 具有兩個(gè)特征分值：中心度h(i)和權(quán)威度a(i)。初始

46、情況下， h(i)=1，a(i)=1。2）每次通過(guò)迭代計(jì)算頁(yè)面的中心度和權(quán)威度。網(wǎng)頁(yè)的中心度 h (i)為：網(wǎng)頁(yè)的權(quán)威度 a (i)為：標(biāo)準(zhǔn)化處理：，。其中，|h(i)|和|a(i)|分別代表了網(wǎng)頁(yè)集合里的最大中心度和最大權(quán)威度。3）不斷重復(fù) 2)的過(guò)程，計(jì)算上一輪迭代的權(quán)值和本輪迭代之后權(quán)值的差異，如果二者差異較小，則說(shuō)明系統(tǒng)已趨于穩(wěn)定。5.3 基于Best-First算法的主題搜索策略5.3.1 鏈接價(jià)值評(píng)估 Best-First算法的基本思想是構(gòu)建一個(gè)待抓取鏈接列表，然后從中選擇最有價(jià)值的鏈接進(jìn)行搜索。通常利用頁(yè)面內(nèi)容與主題的相似度來(lái)對(duì)頁(yè)面的價(jià)值進(jìn)行評(píng)估。利用向量空間模型來(lái)表示一個(gè)頁(yè)面，

47、將歐式距離和權(quán)重計(jì)算相結(jié)合的方法計(jì)算出頁(yè)面與主題之間的相關(guān)性，其計(jì)算公式如下： （5.2）以上公式在歐式距離計(jì)算公式的基礎(chǔ)上進(jìn)行歸一化并取反處理后的公式，其中，q,p分別表示主題向量和頁(yè)面特征向量，向量的維數(shù)都為n,表示特征關(guān)鍵字i在頁(yè)面p中權(quán)重，表示k在主題向量q中的權(quán)重，權(quán)重采用TF-IDF方式計(jì)算。公式表示，當(dāng)計(jì)算值最小為0，表示網(wǎng)頁(yè)向量與主題向量相似度最低，當(dāng)計(jì)算值最大為1，此時(shí)表示網(wǎng)頁(yè)向量與主題向量相似度最高。一個(gè)主題相關(guān)的網(wǎng)頁(yè)上，并非所有的鏈接都是主題相關(guān)的；反之，一個(gè)主題不相關(guān)的網(wǎng)頁(yè)上不一定所有的鏈接都是主題無(wú)關(guān)的46。所以鏈接的價(jià)值應(yīng)該由兩部分來(lái)評(píng)估，一部分是鏈接繼承父頁(yè)面的價(jià)值。另一部分則是鏈接的錨文本。假設(shè)父頁(yè)面的向量表示為d1,鏈接錨文本的向量表示為d2,主題向量表示為q,通過(guò)前文的分析，得到最終的計(jì)算鏈接價(jià)值的公式: (5.3)5.3.1 主題搜索策略本文所使用的搜索策略，主要依賴于兩個(gè)隊(duì)列來(lái)指導(dǎo)主題網(wǎng)絡(luò)爬蟲(chóng)來(lái)抓取網(wǎng)絡(luò)上的網(wǎng)頁(yè)資源。一個(gè)是待抓取鏈接隊(duì)列，另一個(gè)是已抓取鏈接隊(duì)列。其中，待抓取鏈接隊(duì)列是本文搜索策略的關(guān)鍵。待抓取鏈接隊(duì)列示例:depth=2, url= l, thematicCorr