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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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