主題網(wǎng)絡爬蟲關鍵技術研究

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

2、別算法，去識別網(wǎng)頁的主題。將基于知識庫的實體鏈接方法運用于特征抽取，實驗表明該方法提高了主題網(wǎng)頁識別的準確率。（3）提出了一種基于Best-First算法的主題搜索策略。主題搜索策略是指導主題網(wǎng)絡爬蟲抓取網(wǎng)頁的關鍵，本文采用基于Best-First算法的主題搜索策略。關鍵詞：主題網(wǎng)絡爬蟲，實體鏈接，Best-First算法，主題搜索策略V碩士學位論文第一章 緒論1.1 背景與意義隨著Internet的飛速發(fā)展，互聯(lián)網(wǎng)信息呈指數(shù)增長。根據(jù)中國互聯(lián)網(wǎng)絡信息中心（CNNIC）發(fā)布的第40次中國互聯(lián)網(wǎng)絡發(fā)展狀況統(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è)，是通用搜索引擎的細分，其將某一領域的網(wǎng)頁信息進行整合，處理后再以某種形式返回給用戶。垂直搜索針引擎對某一領域，為特定用戶或特定需求提供相關的信息和服務。垂直搜索引擎專注于某一領域或專業(yè)，所以顯得更加專注、具體及深入。主題網(wǎng)絡爬蟲，又稱聚焦爬蟲是垂直搜索引擎的重要組成部分，所以對主題網(wǎng)絡爬蟲的研究具有重要的意義。主題網(wǎng)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18、分,name=”Robots”表示作用于所有的網(wǎng)絡爬蟲，也可以針對某個具體網(wǎng)絡爬蟲寫為name=”BaiduSpider”。 相對鏈接的轉換相對URL有服務器相對URL和文檔相對URL。絕對URL的格式如下:scheme: /server/path/resource其中:scheme指定資源所使用的協(xié)議,有http,mailto,ftp等協(xié)議。server是指資源所在服務器的名稱比如。path是指到達資源的路徑,比如/18/0402/09。resource通常是文件名比如:DECL75C900118017.html。它可能是單個二進制流的“簡單文件”,也可能是“結構化文檔”。定位

19、資源的所有信息都包括在“絕對URL”中。相對URL相對于某一網(wǎng)頁位置的目標鏈接。因為在現(xiàn)實環(huán)境中，網(wǎng)站服務器發(fā)生變更會引發(fā)鏈接錯誤，所以使用相對鏈接指向同一服務器下的網(wǎng)頁。當前網(wǎng)頁位置一般可視為特定網(wǎng)頁位置,或者用base標簽定義,如<base href="" />,那么該網(wǎng)頁中所有的鏈接都是以""為前綴。2.3.2 搜索策略概述通用網(wǎng)絡爬蟲為了較高的覆蓋率，一般采用圖的廣度優(yōu)先策略去遍歷互聯(lián)網(wǎng)上的網(wǎng)頁;主題網(wǎng)絡爬蟲需要搜索的內(nèi)容只會針對特定的主題，而不需遍歷整個網(wǎng)絡，只需要選擇主題相關的網(wǎng)頁進行遍歷。主題網(wǎng)絡爬蟲通常采用“最好優(yōu)先”原則從互

20、聯(lián)網(wǎng)上搜索網(wǎng)頁。每次對“最有價值”的鏈接進行訪問來高效地獲取到更多與主題相關的網(wǎng)頁。主題網(wǎng)絡爬蟲不同的搜索策略由鏈接的價值評價方法決定。鏈接往往包含在頁面內(nèi)容之中，所以一般父頁面的價值高，其所包含的鏈接一般也具有較高價值，因此對評價鏈接價值往往要結合對網(wǎng)頁內(nèi)容的分析。2.4 本章小結本章概述了主題網(wǎng)絡爬蟲的基本流程和組成部分，介紹了鏈接提取規(guī)則。最后介紹了網(wǎng)絡爬蟲搜索策略的概念。第三章 網(wǎng)頁主題內(nèi)容抽取3.1 HTML簡介目前大部分網(wǎng)頁都是由HTML編寫。網(wǎng)頁通過超鏈接鏈接在一起，進而形成一個緊密連接在一起的網(wǎng)絡結構。對于通用網(wǎng)絡爬蟲來說，只需要抽取網(wǎng)頁中的鏈接;然而對于主題網(wǎng)絡爬蟲則需要分析

21、并提取網(wǎng)頁內(nèi)容，然后對鏈接進行價值評估及對其進行取舍。大致可將標簽分為三類:（1）對網(wǎng)頁進行布局的標簽。常用的標簽有<table>、<tr>、<td>、<p>、<div>等。（2）描述信息顯示特點的標簽。常用的重要信息標簽有<b>、<I>、<strong>、<h1>、<h2>等十幾種。（3）包含超鏈接的標簽:超鏈接用于連接各個頁面能表示網(wǎng)頁之間的關系。這類標簽有<a>、<img>、<frame>等。HTML文檔主要由頭部(head)和主體(

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

23、;</head><body><table><tr><a href="<a href="</tr><tr><p>段落</p></tr></table><body></html>上述html文件的樹結構表示如圖3-1所示:圖3-1 html文件的樹結構目前，有很多構造標簽樹的工具，如：htmlParser,W3C HTML lexical analyzer22等。3.3 網(wǎng)頁去噪許多網(wǎng)頁都包含與主題內(nèi)容無關的內(nèi)容。如圖3-2

24、所示的新聞網(wǎng)頁截圖的網(wǎng)頁，可以認為正文塊以外的部分都是噪音。圖3-2 網(wǎng)頁的正文塊從網(wǎng)頁的截圖可以看出，網(wǎng)頁除了正文塊外，其余部分由廣告、導航鏈接、搜索服務等組成。在主題搜索領域，大量的噪音內(nèi)容會導致主題漂移。在提取主題相關內(nèi)容時，如果不去除原始網(wǎng)頁中的噪音內(nèi)容，往往容易將噪音內(nèi)容作為主題相關的內(nèi)容，影響對網(wǎng)頁主題的識別。3.3.1 利用統(tǒng)計學去噪用統(tǒng)計的方法去噪23的流程如下。(1) 刪除噪音塊：網(wǎng)頁去噪的基本方法是利用各種通用的特征來區(qū)分有效的正文和頁眉、頁腳、廣告等其他信息。其中一個常用的特征是鏈接文字比率。根據(jù)鏈接文字比率過濾掉噪音。(2) 劃分段落。可以把HTML頁面劃分成多個段落(

25、Paragraph)。簡單的實現(xiàn)方法是，根據(jù)<td><p><br><div><table>這些標簽來劃分段落。(3) 評估段落。每個段落內(nèi)的文字因其視覺上或者是主題上對文檔的貢獻程度而具有不同的權重。選取分值最大段落最為正文塊。流程圖如下：圖3-3 去噪流程3.4 主題內(nèi)容的抽取網(wǎng)頁主題內(nèi)容的抽取是網(wǎng)頁主題識別的第一步，主題內(nèi)容抽取的準確率直接影響到網(wǎng)頁主題識別的準確率。劉軍等24（基于DOM的網(wǎng)頁主題信息的抽取）提出構建文檔對象模型DOM樹，然后添加顯示語義等屬性來解決HTML文檔半結構化的不足，并提出一種聚類規(guī)則來對其進行分塊，最

26、后提取出主題信息。在此基礎上，通過對大量網(wǎng)頁的分析發(fā)現(xiàn)，除了正文的內(nèi)容塊，網(wǎng)頁的標題(title標簽的內(nèi)容)及meta標簽的屬性content的內(nèi)容往往也攜帶有網(wǎng)頁的主題信息，所以抽取的時候這部分內(nèi)容也應該被抽取。網(wǎng)頁一般可分為索引型網(wǎng)頁和主題型網(wǎng)頁，網(wǎng)頁主題的識別是針對于主題型網(wǎng)頁。主題網(wǎng)頁所包含的鏈接文本往往是廣告等與主題無關的文本，所以，應該先去除掉。然后還應去除掉網(wǎng)頁版本信息等與主題無關的噪音文本。綜上所述，網(wǎng)頁主題內(nèi)容的抽取算法如下：Step1首先選取p,li,td,h1作為分塊節(jié)點Step2去除網(wǎng)頁a標簽及其內(nèi)容Step3獲取title標簽中的文本，然后刪除title標簽及其內(nèi)容S

27、tep4獲取meta標簽的屬性content的值,然后刪除meta標簽Step5對p標簽進行與3相同的操作Step6對li標簽進行與3相同的操作Step7對于td標簽進行與3相同的操作Step8對于h1標簽進行與3相同的操作取“，。？；、,.?”標點符號作為分塊節(jié)點的特征，如果節(jié)點中的文本包含這些特征則認為內(nèi)容是主題相關，就對其進行抽取。3.5 本章小結本章先介紹了網(wǎng)頁處理中的各種預處理過程,包括HTML解析、網(wǎng)頁消噪。為了提取網(wǎng)頁中的主要內(nèi)容,有必要剔除原始網(wǎng)頁的噪音。然后根據(jù)網(wǎng)頁的主題內(nèi)容的特征，提取出網(wǎng)頁的主題內(nèi)容。第四章 基于實體鏈接的主題識別算法4.1 實體鏈接簡介在介紹實體鏈接之前

28、，首先，需要了解實體的概念。實體是存在于世界上的某一個對象或者對象的集合，實體一般用屬性來描述。實體鏈接就是把文本中的實體表述鏈接到知識庫中的相應實體的過程29。在實體鏈接中所使用的知識庫包括Wikipedia、Freebase、YAGO、DBpedia等30。目前復旦大學圖數(shù)據(jù)管理實驗室的知識工廠構建了知識庫，并提供了比較全面的接口，本文所使用的就是知識工廠提供的知識庫以及相關接口。在一段文本中，實體鏈接主要有兩件事，一方便是識別出文本中的實體指稱，另一方面就是將識別出的實體指稱與知識庫中的相應實體相關聯(lián)。由于自然語言中普遍存在以此多義和別名現(xiàn)象，因此需要根據(jù)文本中實體表述的上下文信息去確定

29、實體表述所指向的實體。所以，實體鏈接主要包含兩項關鍵技術：實體識別、實體消歧。實體識別31是指識別一個文本中的實體表述，這個實體表述可能是指向實體的詞或者短語。實體消歧32是指給定實體指稱及其所在上下文、候選實體，判斷其在當前上下文中所指向實體的過程。4.2 CN-DBpediaCN-DBpedia33是由復旦大學知識工場實驗室（Knowledge Works）研發(fā)并維護的大規(guī)模通用領域結構化百科，其前身是復旦GDM中文知識圖譜，是國內(nèi)最早推出的也是目前最大規(guī)模的開放百科中文知識圖譜，涵蓋數(shù)千萬實體和數(shù)億級的關系。CN-DBpedia以通用百科知識沉淀為主線，以垂直縱深領域圖譜積累為支線，致力

30、于為機器語義理解提供了豐富的背景知識，為實現(xiàn)機器語言認知提供必要支撐。CN-DBpedia已經(jīng)從百科領域延伸至法律、工商、金融、文娛、科技、軍事、教育、醫(yī)療等十多個垂直領域，為各類行業(yè)智能化應用提供支撐性知識服務，目前已有近百家單位在使用。CN-DBpedia具有體量巨大、質量精良、實時更新、豐富的API服務等特色。CN-DBpedia已經(jīng)成為業(yè)界開放中文知識圖譜的首選。本文主要用CN-DBpedia作為知識庫，并利用知識工廠提供的相關接口識別文本中的實體，然后進行再利用其提供的接口進行實體鏈接。例如如下文本:圖 4.1調用知識工廠的接口，獲取到如下結果:圖 4.2其中cuts字段是對文本的詞

31、集合,entities字段是識別出的文本中的實體。然后調用知識工廠提供的獲取知識庫中的實體詳情的接口，獲取的實體信息如下所示:圖 4.3其中，status表示接口調用狀態(tài)，ret字段表示獲取的結果，其中包含實體的詳細信息:拼音、中文名、亦稱、外文名稱、CATEGORY_ZH、DESC。上述過程就是識別文本中的實體并鏈接到知識庫中獲取實體信息的過程，也即實體鏈接的過程。4.3 基于實體鏈接的特征抽取特征抽取對于主題識別來說，是特別重要的一步，抽取出的特征準確與否，決定著主題識別的準確率。傳統(tǒng)的方式，由于分詞的問題，無法很好的把某些主題特征抽取出來，所以本文將實體鏈接引入到特征抽取的過程中，以知識

32、庫為支撐，來更加準確的將主題特征抽取出來。4.3.1 候選特征集合抽取首先，從訓練語料中抽取出候選特征集合34。圖 4.4如上圖所示，具體步驟如下：(1)準備訓練語料。準備若干主題相關的文本。(2)實體鏈接處理。使用知識工廠的接口將這些主題相關的文本逐句進行實體識別并分詞，且獲取實體信息從實體信息中抽取出更多的候選特征。(3)獲取候選特征集合。將上一步獲取到的詞集合進行去重，去停用詞處理，獲取到候選特征集合。從搜狗語料中選擇與“軍事”主題相關50篇的新聞文章作為選擇候選特征的語料集合。首先，利用知識工程的接口對語料文章進行分詞并識別語料文章的實體，由于有知識庫的支撐，所以能更好的將文章中的潛在

33、的特征切分出來。對于，識別出的實體，進行實體鏈接，獲取到實體的信息。如下圖所示：圖 4.5如上圖所示，實體“防空導彈”的實體信息中，可將“別稱”、“類別”及“CATEGORY_ZH”屬性抽取出來合并到候選特征集合中?！癉ESC”屬性加入到提取候選特征的語料集合中做進一步處理。如上所述，基于實體鏈接的方式，由于有知識庫的支撐，一方面，能較準確地將潛在的特征抽取出來，另一方面，由于抽取特征的訓練語料是有限的，可以從實體信息中抽取出更多的特征。如下圖所示，為使用了實體鏈接所挑選出的候選特征集合實例:圖 常見特征抽取算法 目前，常用的特征選擇算法如下：文檔頻率35、信息增益36、互信

34、息37及詞條的統(tǒng)計38等。（1）文檔頻率。 訓練語料中包含某一詞語的文檔的條數(shù)就是該詞語的文檔頻率。該方法的基本思想是：出現(xiàn)頻率較低的詞語往往攜帶很少的信息量，因而無法很好的將類別區(qū)分開來，因此可以刪除較低頻率的詞語，這樣既能降低特征維度又能提高分類的準確率。（2） 信息增益（Information Gain）。信息增益（IG）是計算某一特征出現(xiàn)出現(xiàn)和不出現(xiàn)兩種情況下，系統(tǒng)攜帶信息量的差值。對于文本分類而言，包含特征詞 t和不包含特征詞t的文檔頻數(shù)差值代表了特征詞t的IG值。IG值采用如下的公式計算： (4-1) 公式中，表示類文檔在語料中出現(xiàn)的概率，表示語料中包含詞語的文檔概率，表示文檔包含

35、詞語 時屬于類的條件概率，表示語料中不包含詞語的文檔概率，表示文檔不包含詞語時屬于類的條件概率，表示類別數(shù)。（3） CHI統(tǒng)計CHI統(tǒng)計常常稱為開方統(tǒng)計，用于檢驗兩個變量是否獨立。在兩個變量是相互獨立的前提下，將樣本的實際觀測值和理論值的偏離程度計算出來，表示為CHI值。CHI值越大，兩變量趨于相關;反之則兩變量趨于獨立。特征詞和文檔類別的相關程度也可以用此方式來衡量。先預設詞條與某一類別是獨立的，以此為基礎計算出的詞條的CHI值越大則說明結果與假設偏差越大，則該詞條與類別越相關。因此，該方法特征選擇的過程即:計算每個詞條與類別的CHI值，并從大到小排序，靠前的值則為特征。詞語對于類別的CHI

36、值計算公式如下： (4-2)（4） 互信息（Mutual Information）在信息論中，互信息（MI）表示兩個事件發(fā)生相關聯(lián)而提供的信息量?；バ畔⒘吭酱螅嚓P性也就越大。詞語和類別的互信息計算公式如下：（4-3）公式(4-3)中A、B、C、D和N的含義與公式（4-2）中一致。實驗表明，信息增益能比較有效的進行特征提取，所以本文采用信息增益的算法進行特征提取。4.3.3 最終特征抽取在候選特征集合的基礎上，抽取最終的特征集合，具體步驟如下：圖 4.7(1)計算信息增益值。在訓練語料中計算候選特征集合中每個特征的信息增益值。(2)獲取特征。按照信息增益值遞減排序，選擇靠前的若干特征。(4)獲

37、取最終特征。將從實體信息中獲取到特征加入到（2）步驟中獲取的特征集合中，將這個特征集合作為最終的特征集合。4.4 基于樸素貝葉斯算法的分類器本文采用樸素貝葉斯算法構造分類器。假設用特征集合來表示每個實例A，而類c從某有限集合C中取值?，F(xiàn)提供一訓練實例集和一測試實例(a1,a2,am)。需要分類的實例A的目標是獲取實例(a1,a2,am)的類標記。得到： （4-4）現(xiàn)在要做的就是基于訓練實例集估計式(4-14)中的兩個概率值。樸素貝葉斯分類器(naïve Bayes classifiers)39假定：在給定類標記時屬性值之間是相互條件獨立的。也就是說，聯(lián)合概率正好是每個單獨特征概率的乘

38、積。具體的公式如下： (4-5)代入式（4-14）中，可得樸素貝葉斯分類器的分類公式： (4-6)式中，為x的第j個特征值、概率p(c)和可以通過計算訓練實例集中不同類和特征值組合的出現(xiàn)頻率來簡單計算,具體的公式如下: (4-7)(4-8)式中,n為訓練實例的個數(shù)、為第i個訓練實例的類標記、為第i個訓練實例的第j個屬性值, 為一個二值函數(shù),當時為l,否則為0。顯然,當出現(xiàn)零頻率屬性值的時候，這種方法會導致過低估計概率。更極端的情況會使得某個概率值為0,進而導致由式(4-6)計算的整個量為0。常常使用Laplace估計來進行平滑處理進而避免上述問題,重寫式(4-7)和式(4-8)得到: (4-9

39、)(4-10)式中,為類的個數(shù)、為訓練實例第個屬性的取值個數(shù)?；趯嶓w鏈接的樸素貝葉斯分類器的整體框架如圖3.3所示。圖 4.8其工作流程如下：(1)使用基于實體鏈接的特征抽取方法進行特征提取。(2)根據(jù)獲取到的特征集合，構建樸素貝葉斯分類器，并對其進行訓練。(3)對爬蟲抓取到的網(wǎng)頁進行預處理，包括，主題信息抽取、分詞等預處理，然后將網(wǎng)頁向量化表示。(4)利用分類器對向量化處理后的網(wǎng)頁進行主題識別，如果網(wǎng)頁屬于主題類，則將網(wǎng)頁保存到主題頁面庫，否則舍棄該頁面。4.5 實驗分析本小節(jié)來通過實驗驗證本章提出的基于實體鏈接的樸素貝葉斯分類器在主題識別中的效果。對于主題識別效果的評判，主要采用三個指標

40、：準確率(P)、召回率(R)和F值40。準確率是表示準確識別出的主題相關的文本數(shù)量比例;召回率是準確識別出的主題相關的文本數(shù)量與訓練集中所有主題相關的文本數(shù)量的比例;F值是一個綜合評價指標。假定：在訓練語料中，屬于與主題相關且被判定為與主題相關的文本是a,與主題無關但被判定為主題相關的文本數(shù)目是b,屬于與主題相關但未能被判定為與主題相關的文本數(shù)量是c,那么三個評價指標的計算公式如下：準確率： 召回率： F值： 現(xiàn)從搜狗新聞語料中選擇軍事（587篇）及非軍事(856篇)的文章共計1443篇，作為訓練語料。使用本章提出基于實體鏈接的方法去構建樸素貝葉斯分類器，進行實驗。實驗結果如下：表4.1 實驗

41、結果識別出主題相關文本識別正確的文本準確率(P)召回率(R)F值(F)NB61351684.2%87.9%86%基于實體鏈接的NB62755280%94%90.9%從實驗結果來看，相比與傳統(tǒng)的樸素貝葉斯分類器，引入實體鏈接技術對其進行改進能取得較好的效果。4.6 本章小結本章主要介紹了基于實體鏈接的樸素貝葉斯分類器。首先，介紹了實體鏈接的相關概念，接著介紹了本文所用的知識庫CN-DBpedia以及相關接口。然后，重點闡述了基于實體鏈接的特征抽取方法，將實體鏈接技術運用于特征抽取中來更好的提取出主題相關的特征。接著，詳細介紹了基于樸素貝葉斯算法的分類器的構造以及工作流程。最后，通過實驗分析，證明

42、，本章提出的基于實體鏈接的主題識別算法能取得較好的效果。第5章 基于Best-First算法的主題搜索策略搜索策略是爬蟲預設的一種爬行方法，用于指導網(wǎng)絡爬蟲抓取互聯(lián)網(wǎng)上的網(wǎng)頁。本章在前人的基礎上，設計一種主題爬蟲策略去指導主題爬蟲去抓取網(wǎng)頁。5.1 通用搜索策略互聯(lián)網(wǎng)可以看成一個復雜而龐大的非連通圖41。參照圖的遍歷方法，通用網(wǎng)絡爬蟲一般有兩種遍歷策略，即廣度優(yōu)先策略和深度優(yōu)先策略42。圖5.1 網(wǎng)絡鏈接結構圖圖5.1是個簡單的網(wǎng)絡鏈接結構圖，其中網(wǎng)絡中的網(wǎng)頁由節(jié)點表示，而鏈接則由邊來表示。深度優(yōu)先搜索的思路是，爬蟲沿著某一方向一直搜索，直到此方向沒有可繼續(xù)搜索的節(jié)點則換個方向繼續(xù)進行。以圖5

43、.1為例，爬蟲的搜索順序為ABDECFG。廣度有限搜索策略的思路是由近及遠一層層抓取搜索網(wǎng)絡上的節(jié)點，同樣以圖5.1所代表的網(wǎng)絡結構為例，其中，A節(jié)點為第一層頁面，B、C節(jié)點為第二層頁面，D、E、F、G為第三層頁面，所以按照廣度優(yōu)先的策略，爬蟲的抓取網(wǎng)頁的路徑為ABCDEFG。理論上來說，這兩種搜索策略都是可行的。但是，真實環(huán)境的互聯(lián)網(wǎng)龐大且復雜，深度優(yōu)先策略往往會陷入某一方向，而且，一般網(wǎng)頁的層次越深價值越低，所以，通用網(wǎng)絡爬蟲一般采用廣度優(yōu)先策略。然而，通常通用網(wǎng)絡爬蟲為了追求覆蓋率，所以抓取到的資源往往價值不高。5.2 常用主題搜索策略主題網(wǎng)絡爬蟲的目標是抓取與給定主題相關的網(wǎng)頁，所以，

44、需要預測鏈接內(nèi)容的主題相關性，然后決定是否進行抓取。不同于通用搜索策略，主題搜索策略是在主題的指導下，對鏈接的價值進行評估。根據(jù)鏈接的主題相關性的大小，將鏈接插入到待抓取隊列中，并選擇主題相關度高的鏈接繼續(xù)抓取43。這樣主題網(wǎng)絡爬蟲能盡可能快且多的抓取到主題相關的網(wǎng)頁，提高了抓取效率。近年來，人們對主題搜索策略主要分為兩類：一種是基于內(nèi)容評價，另一種是基于鏈接結構評價44。5.2.1 基于內(nèi)容評價的搜索策略該搜索策略主要是通過分析網(wǎng)頁內(nèi)容與所給主題的相關性來指導主題網(wǎng)絡爬蟲抓取網(wǎng)頁。下面主要通過介紹如下算法來對這類搜索策略進行分析。（1）Best-First算法最佳優(yōu)先搜索（Best Firs

45、t Search），是一種啟發(fā)式搜索算法,它可以看做是廣度優(yōu)先搜索算法的一種改進。最佳優(yōu)先搜索算法在廣度優(yōu)先搜索的基礎上，用啟發(fā)估價函數(shù)對將要被遍歷到的點進行評價，然后選擇代價小的進行遍歷，直到找到目標節(jié)點或者遍歷完所有點。用來做主題網(wǎng)絡爬蟲的搜索策略的基本思路是:對鏈接的價值進行評估，優(yōu)先抓取價值高的鏈接所指向的網(wǎng)頁。（2）Fish-Search算法De Bra等于提出Fish-Search算法，該算法模擬魚群覓食行為。該算法假設每個鏈接就是一條魚，該鏈接的頁面中的鏈接代表魚的后代。如果魚找到事務，即鏈接找到主題相關頁面，那么將繼續(xù)沿這個方向繼續(xù)搜索。反之，如果魚找不到食物，則后代變得虛弱，

46、即此方向找不到主題相關頁面。經(jīng)過多次尋找，直到此線路再無其他鏈接則從其他方向重新開始搜索。（3） Shark-Search算法Fish-Search算法使用二值模型來來判斷魚是否找到食物，這樣無法精確的對鏈接優(yōu)先隊列進行排序。Hersovici 提出了Shark-Search算法來改進Fish-Search算法。其相關度一般在0和1之間取值44。5.2.1 基于鏈接結構評價的搜索策略基于鏈接結構評價的搜索策略中，PageRank 算法和 Hits 算法是最為基礎、典型的兩種算法。（1）PageRank 算法。定義“入度”和“出度”的概念，“入度”即指向網(wǎng)頁的鏈接，“出度”即網(wǎng)頁中指向其他頁面的

47、鏈接。PageRank 算法主要是依據(jù)入度和出度，對鏈接價值進行評估。頁面 A 的 PageRank的計算公式如下: （5-1）在公式中： 代表網(wǎng)頁 A 的 PageRank 值。代表鏈接到 A 的網(wǎng)頁的 PageRank 值。代表網(wǎng)頁 Ti的出度。d 是阻尼系數(shù)，主要起調控作用，在 0 到 1 之間取值，一般設置 d 為0.85。（2）HITS 算法。HITS 算法的基本流程為：1）網(wǎng)頁 i 具有兩個特征分值：中心度h(i)和權威度a(i)。初始情況下， h(i)=1，a(i)=1。2）每次通過迭代計算頁面的中心度和權威度。網(wǎng)頁的中心度 h (i)為：網(wǎng)頁的權威度 a (i)為：標準化處理：

48、，。其中，|h(i)|和|a(i)|分別代表了網(wǎng)頁集合里的最大中心度和最大權威度。3）不斷重復 2)的過程，計算上一輪迭代的權值和本輪迭代之后權值的差異，如果二者差異較小，則說明系統(tǒng)已趨于穩(wěn)定。5.3 基于Best-First算法的主題搜索策略5.3.1 鏈接價值評估 Best-First算法的基本思想是構建一個待抓取鏈接列表，然后從中選擇最有價值的鏈接進行搜索。通常利用頁面內(nèi)容與主題的相似度來對頁面的價值進行評估。利用向量空間模型來表示一個頁面，將歐式距離和權重計算相結合的方法計算出頁面與主題之間的相關性，其計算公式如下： （5.2）以上公式在歐式距離計算公式的基礎上進行歸一化并取反處理后的

49、公式，其中，q,p分別表示主題向量和頁面特征向量，向量的維數(shù)都為n,表示特征關鍵字i在頁面p中權重，表示k在主題向量q中的權重，權重采用TF-IDF方式計算。公式表示，當計算值最小為0，表示網(wǎng)頁向量與主題向量相似度最低，當計算值最大為1，此時表示網(wǎng)頁向量與主題向量相似度最高。一個主題相關的網(wǎng)頁上，并非所有的鏈接都是主題相關的；反之，一個主題不相關的網(wǎng)頁上不一定所有的鏈接都是主題無關的46。所以鏈接的價值應該由兩部分來評估，一部分是鏈接繼承父頁面的價值。另一部分則是鏈接的錨文本。假設父頁面的向量表示為d1,鏈接錨文本的向量表示為d2,主題向量表示為q,通過前文的分析，得到最終的計算鏈接價值的公式: (5.3)5.3.1 主題搜索策略本文所使用的搜索策略，主要依賴于兩個隊列來指導主題網(wǎng)絡爬蟲來抓取網(wǎng)絡上的網(wǎng)頁資源。一個是待抓取鏈接隊列，另一個是已抓取鏈接隊列。其中，待抓取鏈