融合鏈接結(jié)構(gòu)的主題爬蟲(chóng)算法

劉韶濤， 李洪勝

(華僑大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 福建 廈門(mén) 361021)

融合鏈接結(jié)構(gòu)的主題爬蟲(chóng)算法

劉韶濤， 李洪勝

(華僑大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 福建 廈門(mén) 361021)

通過(guò)分析基于內(nèi)容的鏈接選擇Best-First算法,引入能夠體現(xiàn)鏈接價(jià)值的HITS(hyperlink induced topic search)算法,提出了新的鏈接選擇策略.將兩種算法相結(jié)合,新的爬蟲(chóng)不僅僅考慮頁(yè)面內(nèi)容,同時(shí)將鏈接結(jié)構(gòu)加入進(jìn)來(lái),使得在下載的過(guò)程中能夠保證主題相關(guān)性和權(quán)威性,緩解爬蟲(chóng)在爬行階段的“近視”現(xiàn)象.結(jié)果表明：新的爬行策略比單一的Best-First算法具有更好的性能表現(xiàn). 關(guān)鍵詞： Best-First算法； 鏈接結(jié)構(gòu)； HITS算法； 爬行策略

隨著互聯(lián)網(wǎng)的迅猛發(fā)展,網(wǎng)絡(luò)上的信息量也呈指數(shù)型增長(zhǎng),如何從數(shù)量巨大的網(wǎng)絡(luò)資源中獲取自己想要的信息一直是研究的熱點(diǎn).與此同時(shí),針對(duì)特定領(lǐng)域而制定的垂直搜索引擎應(yīng)運(yùn)而生.該搜索引擎具有領(lǐng)域特性,其特點(diǎn)是專(zhuān)，精，檢索范圍小，并且精度高,往往能給用戶(hù)帶來(lái)更好的體驗(yàn)[1].垂直搜索引擎通過(guò)分布在網(wǎng)絡(luò)上的主題爬蟲(chóng)，下載用戶(hù)所要獲取的網(wǎng)頁(yè),與一般搜索引擎所使用的爬蟲(chóng)不同[2],主題爬蟲(chóng)能夠根據(jù)預(yù)先定義的領(lǐng)域主題.只爬取與主題相關(guān)的頁(yè)面,而忽略不相關(guān)的鏈接.目前使用比較廣泛的爬行策略算法大都是基于網(wǎng)頁(yè)內(nèi)容的,即通過(guò)頁(yè)面內(nèi)容或者鏈接的錨文本與主題的相似度決定所要爬取鏈接的優(yōu)先級(jí).用戶(hù)希望所下載的頁(yè)面不僅僅只是主題相關(guān),還應(yīng)該是在領(lǐng)域內(nèi)比較權(quán)威的,并能夠被其他網(wǎng)頁(yè)所認(rèn)可的，優(yōu)秀的爬蟲(chóng)應(yīng)該具有持續(xù)發(fā)現(xiàn)更多相關(guān)頁(yè)面的能力.因此,本文基于內(nèi)容爬行Best-First算法的基礎(chǔ)上,融合一種能體現(xiàn)鏈接價(jià)值的HITS算法,提出一種新的爬行策略.

1 主題爬行策略與問(wèn)題分析

1.1 主題爬行策略

主題爬蟲(chóng)根據(jù)不同的爬行策略決定要下載的鏈接[3].目前,主題爬蟲(chóng)的爬行策略形式多樣,而絕大部分都是基于文本內(nèi)容的,其主要考慮以下3個(gè)要素：網(wǎng)頁(yè)正文,鏈接錨文本,以及錨文本上下文.分別計(jì)算這3部分與主題關(guān)鍵詞的相似度，決定待下載鏈接的下載權(quán)重.

Best-First[4]算法是Cho提出的一種啟發(fā)式算法,以簡(jiǎn)潔高效的特點(diǎn)而著稱(chēng).它的主要思想是設(shè)置兩個(gè)隊(duì)列,一個(gè)為權(quán)重URL隊(duì)列,一個(gè)為已訪問(wèn)URL隊(duì)列.每一個(gè)提取出的URL通過(guò)鏈接選擇策略，計(jì)算出一個(gè)得分，將其放入權(quán)重隊(duì)列,然后，每次從中選擇得分最高的一個(gè)下載.鏈接得分的計(jì)算目前有以下3種方法[5].

1) 同一個(gè)頁(yè)面中的鏈接具有相同的權(quán)重分.

2) 鏈接權(quán)重通過(guò)自身錨文本與主題的相似度計(jì)算得出,在這種情況下,同一個(gè)頁(yè)面中的鏈接可能會(huì)有不同的下載權(quán)重.

3) 結(jié)合第1),2)策略,頁(yè)面P中第i個(gè)鏈接的權(quán)重等于頁(yè)面P自身的相似度得分加上鏈接自身錨文本的相似度得分,即

(1)

Best-First算法基于如下原理：如果一個(gè)頁(yè)面是主題相關(guān)的,那么，這個(gè)頁(yè)面指向相關(guān)頁(yè)面的可能性就比較大.除此之外,鏈接錨文本被看作是鏈接所指向頁(yè)面的一個(gè)總結(jié)與概括,而錨文本又不總是可以概括所指向的頁(yè)面內(nèi)容,因此,采用第3種頁(yè)面和錨文本相結(jié)合的方式效果最好.

1.2 問(wèn)題分析

由于基于Best-First算法的爬蟲(chóng)在爬行的過(guò)程中，所采用的爬行策略是單純基于文本內(nèi)容的,即對(duì)于候選鏈接的選擇主要考慮頁(yè)面內(nèi)容，以及鏈接的錨文本,這就使得爬蟲(chóng)所爬取的鏈接雖然是主題相關(guān)的,但是不能確定這個(gè)頁(yè)面在所屬的領(lǐng)域是不是權(quán)威的,即能不能被其他相關(guān)頁(yè)面所認(rèn)可,缺乏鏈接價(jià)值方面的考慮.

此外,由于網(wǎng)絡(luò)的結(jié)構(gòu)特性,相同主題的頁(yè)面往往聚集在一起,形成一個(gè)個(gè)主題團(tuán).爬蟲(chóng)在爬行過(guò)程中,由于每次選擇得分最高的一個(gè)鏈接下載,導(dǎo)致在爬行的某些階段,爬蟲(chóng)會(huì)出現(xiàn)局部最優(yōu)的問(wèn)題[6].經(jīng)過(guò)分析發(fā)現(xiàn),爬蟲(chóng)在碰到一些中心頁(yè)面時(shí),陷入了以中心頁(yè)面為中心的主題團(tuán),導(dǎo)致產(chǎn)生了“近視”現(xiàn)象[7],難以發(fā)現(xiàn)更多的相關(guān)頁(yè)面.

因此,需要引入一個(gè)可以通過(guò)鏈接結(jié)構(gòu)體現(xiàn)鏈接價(jià)值的算法改善爬蟲(chóng)的運(yùn)行.目前,PageRank算法[8]和HITS算法[9]是比較有代表性的兩個(gè)算法,主要是通過(guò)鏈接之間相互指向關(guān)系代表鏈接的重要性,它們是基于以下兩個(gè)假設(shè)：

1) 如果一個(gè)網(wǎng)頁(yè)被其他網(wǎng)頁(yè)指向,被指向得越多,說(shuō)明這個(gè)網(wǎng)頁(yè)越權(quán)威(即有價(jià)值)；

2) 如果一個(gè)網(wǎng)頁(yè)和另外一個(gè)網(wǎng)頁(yè)有鏈接相連,說(shuō)明這兩個(gè)網(wǎng)頁(yè)的主題是相似的.

HITS算法與PageRank算法最大的不同在于：HITS算法是與主題相關(guān)的,即在某一個(gè)領(lǐng)域主題內(nèi)是有價(jià)值的,可以很好地體現(xiàn)網(wǎng)絡(luò)的結(jié)構(gòu)特性.

2 HITS算法與爬行策略改進(jìn)

2.1 HITS算法

圖1 中心頁(yè)面和權(quán)威頁(yè)面Fig.1 Hub and authority pages

HITS算法是由Kleinberg于1998年首先提出的,應(yīng)用于IBM研究中心的CLEVER工程組,用來(lái)權(quán)衡每一個(gè)頁(yè)面的重要性.它定義了兩個(gè)概念：權(quán)威值(Authority)和中心值(Hub).高權(quán)威值的權(quán)威頁(yè)面是指有很多入鏈的頁(yè)面,這些頁(yè)面在某一個(gè)主題或者領(lǐng)域中有很權(quán)威的內(nèi)容,其他網(wǎng)頁(yè)都很樂(lè)意去指向它；高中心值的中心頁(yè)面是指有很多出鏈的頁(yè)面,這些出鏈指向那些在某一主題領(lǐng)域擁有很大影響力的網(wǎng)頁(yè).通常來(lái)說(shuō),好的中心頁(yè)面會(huì)指向許多權(quán)威頁(yè)面,好的權(quán)威頁(yè)面會(huì)被許多中心頁(yè)面所指向[10],如圖1所示.

HITS算法根據(jù)關(guān)鍵詞確定一網(wǎng)絡(luò)子圖G(V,E)(V為網(wǎng)絡(luò)子圖的節(jié)點(diǎn)集,E為邊集),然后，迭代計(jì)算每一個(gè)網(wǎng)頁(yè)的權(quán)威值和中心值,具體有如下4個(gè)流程.

1) 使用領(lǐng)域主題關(guān)鍵詞在通用搜索引擎(如google，baidu)進(jìn)行查詢(xún),提取K個(gè)鏈接作為root集.

2) 使用鏈接分析擴(kuò)展root集,將鏈接的出鏈以及不多于d(d=50)個(gè)的入鏈加入到root集中,擴(kuò)展后的root集稱(chēng)為base集.

3) base集中的每個(gè)頁(yè)面都有兩個(gè)屬性ai，hi,它們分別代表頁(yè)面i的權(quán)威值和中心值.若G有n個(gè)節(jié)點(diǎn),設(shè)a，h為n維向量,并初始化a，h,a0=1,h0=1.然后，進(jìn)行I,O操作.即

I操作為

O操作為

4) 權(quán)威值和中心值的計(jì)算式分別為

頁(yè)面的價(jià)值可以通過(guò)計(jì)算出的權(quán)威值和中心值很好地體現(xiàn)，并藉此進(jìn)行規(guī)范化.同時(shí),由于HITS算法的主題相關(guān)特性,使權(quán)威頁(yè)面和中心頁(yè)面同時(shí)在領(lǐng)域主題內(nèi)是主題相關(guān)的.正是由于這一特性,可以用來(lái)指導(dǎo)爬蟲(chóng)的運(yùn)行.

2.2 改進(jìn)的爬行策略

傳統(tǒng)的主題爬蟲(chóng)選擇候選鏈接主要是基于鏈接的以下兩個(gè)屬性：

1) 鏈接所在頁(yè)面(即父頁(yè)面)的主題相似度；

2) 鏈接自身錨文本的主題相似度,這是單純基于文本內(nèi)容的考量.

如果從全局性出發(fā),通過(guò)鏈接結(jié)構(gòu)體現(xiàn)鏈接價(jià)值,每個(gè)鏈接還應(yīng)該有另外兩個(gè)屬性,也就是權(quán)威值和中心值.在鏈接權(quán)重得分的計(jì)算過(guò)程中，不僅需要考慮文本內(nèi)容，還要加入鏈接價(jià)值的考量.因此,網(wǎng)頁(yè)P(yáng)中第i個(gè)鏈接的權(quán)重得分應(yīng)該由以下兩部分組成：基于文本內(nèi)容的的權(quán)重得分和基于鏈接價(jià)值的權(quán)重得分.

LinkScore(i)=LinkScoreText(P,i)+LinkScoreValue(i).

為了實(shí)現(xiàn)在爬行過(guò)程中加入鏈接價(jià)值考量這一想法,提出了一種內(nèi)容與鏈接結(jié)構(gòu)相融合的主題爬蟲(chóng).通過(guò)將Best-First算法與HITS算法相結(jié)合,使得爬蟲(chóng)除了考慮頁(yè)面文本內(nèi)容以外,還加入了鏈接的權(quán)威值和中心值.其中，文本內(nèi)容的考量通過(guò)父頁(yè)面與主題的相似度和鏈接錨文本與主題相似度體現(xiàn)，鏈接價(jià)值通過(guò)HITS算法計(jì)算出的權(quán)威值和中心值體現(xiàn),新的鏈接分計(jì)算公式為

LinkScore(Pi)=A×(SimPage_Content(P)+B×SimAnchor_Text(i))+

(2)

為了使新的算法能同時(shí)兼顧文本內(nèi)容和鏈接價(jià)值，對(duì)各個(gè)部分分別賦予不同的權(quán)重,其中參數(shù)A+B+C=1,用于控制父頁(yè)面、錨文本及HITS算法得分的比重,α和β用來(lái)控制權(quán)威值與中心值的權(quán)重,相對(duì)于α來(lái)說(shuō),β值設(shè)置的比較小,因?yàn)楦鶕?jù)HITS算法計(jì)算出來(lái)的權(quán)威值和中心值,會(huì)將網(wǎng)頁(yè)分為以下兩種類(lèi)型：高權(quán)威值低中心值的權(quán)威頁(yè)面和低權(quán)威值高中心值的中心頁(yè)面.

如果分別將它們用X,Y代替,那么，通過(guò)以上公式的計(jì)算,能夠保證X>Y,而這正是想要得到的結(jié)果.

父頁(yè)面以及錨文本的得分是來(lái)源于父頁(yè)面、錨文本與主題的相似度[11].首先，將提取出來(lái)的文本內(nèi)容、錨文本進(jìn)行分詞、去停用詞處理；然后，映射到向量空間,使用訓(xùn)練好的TF-IDF主題模型計(jì)算每個(gè)詞的權(quán)重；最后，通過(guò)余弦相似度方法計(jì)算與主題的相似度,即

(3)

式(3)中：Text為文本內(nèi)容;t為主題表示;W1，k;W2，k分別為文本和主題中詞條k的權(quán)值.

任何一個(gè)網(wǎng)頁(yè)正文都能用一個(gè)n維特征向量表示,因此,網(wǎng)頁(yè)與主題之間的相似度也就轉(zhuǎn)變成了向量間的距離計(jì)算.在計(jì)算過(guò)程中,將文本內(nèi)容和主題分別表示成向量,并賦予TF-IDF權(quán)重,然后，通過(guò)式(3)計(jì)算相似度.

新算法描述如下：新算法通過(guò)維護(hù)3個(gè)隊(duì)列進(jìn)行爬行,分別為權(quán)重隊(duì)列、已下載隊(duì)列、錯(cuò)誤隊(duì)列,具體的實(shí)現(xiàn)由以下5個(gè)步驟組成.算法流程圖，如圖2所示.

圖2 算法流程圖Fig.2 Process of algorithm

步驟1 輸入.在主題爬蟲(chóng)的開(kāi)始階段,爬蟲(chóng)需要接受一組種子鏈接作為爬蟲(chóng)爬行過(guò)程的開(kāi)始.人工篩選出關(guān)于“體育”、“財(cái)經(jīng)”主題的各9個(gè)鏈接作為種子鏈接,將這9個(gè)種子鏈接賦予權(quán)重1，放入權(quán)重隊(duì)列中；此外,這9個(gè)鏈接也將作為HITS算法的初始root集.

步驟2 頁(yè)面下載.從權(quán)值隊(duì)列中根據(jù)式(2)提取得分最高的鏈接(在爬行初期,由于網(wǎng)頁(yè)數(shù)目較少,因此，使用式(1)計(jì)算得分),如果此鏈接在已下載隊(duì)列中,則結(jié)束當(dāng)前循環(huán)；否則,對(duì)這個(gè)鏈接進(jìn)行下載,并將其放入已下載隊(duì)列中.然后，針對(duì)已下載的這個(gè)鏈接,提取出其中的網(wǎng)頁(yè)正文,并且對(duì)正文進(jìn)行分詞、去停用詞、去低頻詞處理.

采用VSM(vector space model)向量空間模型將其轉(zhuǎn)化為空間向量,權(quán)值為T(mén)F-IDF權(quán)重(TF-IDF模型在爬行之前,通過(guò)主題相關(guān)的訓(xùn)練集可以得到),并通過(guò)式(3),計(jì)算此網(wǎng)頁(yè)與主題的相關(guān)度.如果相關(guān)度大于預(yù)先定義的閾值,那么，此網(wǎng)頁(yè)為主題相關(guān)頁(yè)面,并將此鏈接放入HITS算法節(jié)點(diǎn)集中,保存當(dāng)前網(wǎng)頁(yè).

步驟3 鏈接處理.對(duì)于頁(yè)面相關(guān)度大于閾值的網(wǎng)頁(yè)(parent_page),提取其中的鏈接(child_page),根據(jù)鏈接自身錨文本計(jì)算與主題的相關(guān)度,得到錨文本的得分.將parent_page→child_page關(guān)系加入到HITS算法邊集中,然后，將child_page加入到節(jié)點(diǎn)集中.

步驟4 權(quán)重分配.每當(dāng)頁(yè)面下載數(shù)為p的時(shí)候,進(jìn)行HITS算法的迭代計(jì)算,直到算法收斂(在爬行初期,此步可忽略).然后，根據(jù)式(2)計(jì)算出每個(gè)鏈接的最終得分,去除得分較低的鏈接,將其余的鏈接加入到權(quán)重隊(duì)列中.

步驟5 擴(kuò)展. 重復(fù)步驟2～4,直到算法滿(mǎn)足停止的條件，即下載的頁(yè)面數(shù)達(dá)到最大值，或者權(quán)重隊(duì)列為空.

3 實(shí)驗(yàn)部分

3.1 實(shí)驗(yàn)準(zhǔn)備

為檢驗(yàn)新算法的性能,設(shè)置3個(gè)實(shí)驗(yàn),分別基于Best-First算法、Best-NFirst算法及所設(shè)計(jì)的新算法.Best-NFirst算法是Best-First算法的改進(jìn)算法,其每次選擇得分最高的N個(gè)鏈接下載,意為改善Best-First算法的局部最優(yōu)現(xiàn)象.Best-First算法和Best-NFirst算法的爬蟲(chóng)使用網(wǎng)頁(yè)內(nèi)容與鏈接錨文本得分決定權(quán)重隊(duì)列中鏈接下載的優(yōu)先級(jí).

實(shí)驗(yàn)采用Python語(yǔ)言實(shí)現(xiàn),文本分詞時(shí),使用了Python編程領(lǐng)域中較為常用的jieba分詞系統(tǒng),jieba分詞支持3種分詞模式：精準(zhǔn)模式、全模式和搜索引擎模式,文中采用搜索引擎模式進(jìn)行分詞.硬件環(huán)境為：Intel 酷睿i3-2310 2.5 GHz主頻的CPU,4 GB內(nèi)存和500 GB硬盤(pán).

為檢驗(yàn)爬蟲(chóng)的性能,設(shè)置爬蟲(chóng)爬取5 000個(gè)網(wǎng)頁(yè)時(shí)自動(dòng)停止.在爬行開(kāi)始之前,通過(guò)“搜狗實(shí)驗(yàn)室”提供的新聞分類(lèi)語(yǔ)料庫(kù)對(duì)TF-IDF模型進(jìn)行訓(xùn)練,“搜狗實(shí)驗(yàn)室”提供的分類(lèi)包含“教育”、“體育”、“娛樂(lè)”等10多個(gè)不同主題的訓(xùn)練文本.實(shí)驗(yàn)選擇對(duì)“體育”、“財(cái)經(jīng)”主題的網(wǎng)頁(yè)進(jìn)行搜集,因此在爬行的過(guò)程中,通過(guò)訓(xùn)練好的相應(yīng)的TF-IDF主題模型計(jì)算網(wǎng)頁(yè)正文內(nèi)容的相關(guān)度,如果相關(guān)度得分大于閾值,那么，認(rèn)為此網(wǎng)頁(yè)為主題相關(guān)頁(yè)面，閾值通過(guò)人工挑選的200個(gè)主題相關(guān)頁(yè)面的相似度得分確定，初始種子鏈接如表1所示.

在性能評(píng)價(jià)方面,通過(guò)算法的查準(zhǔn)率、查全率以及算法的運(yùn)行時(shí)間綜合考量.查全率為爬取的主題相關(guān)頁(yè)面與所有相關(guān)頁(yè)面的比值,查準(zhǔn)率又稱(chēng)為精確率,為所爬取得相關(guān)頁(yè)面與所有頁(yè)面的比值.

表1 種子URL

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

“體育”主題、“財(cái)經(jīng)”主題精確率對(duì)比圖，如圖3，4所示.圖3,4中：r為算法收獲率；n為下載網(wǎng)頁(yè)數(shù)目.由圖3，4可知：隨著n的增加，r變化；基于Best-First算法的爬蟲(chóng)由于只是考慮了文本內(nèi)容信息,使得爬蟲(chóng)過(guò)早的陷入了局部最優(yōu)的陷阱,導(dǎo)致在爬行的過(guò)程中收獲率下降得很快,難以發(fā)現(xiàn)更多的相關(guān)頁(yè)面，而B(niǎo)est-NFirst算法的爬蟲(chóng)并沒(méi)有表現(xiàn)出預(yù)期的結(jié)果.可能是由于每次下載得分最高的N個(gè)鏈接,導(dǎo)致也將許多不相關(guān)頁(yè)面加入了進(jìn)來(lái),影響了實(shí)驗(yàn)的結(jié)果.

融合了HITS算法的新爬蟲(chóng)由于加入了鏈接結(jié)構(gòu)使得爬蟲(chóng)具有了全局特性,HITS算法是主題相關(guān)的,爬蟲(chóng)在爬行過(guò)程中可以不斷的發(fā)現(xiàn)更多的相關(guān)頁(yè)面,取得了不錯(cuò)的效果.

圖3 “體育”主題精確率對(duì)比圖 圖4 “財(cái)經(jīng)”主題精確率對(duì)比圖Fig.3 Comparing of precision Fig.4 Comparing of precision rate with sports theme rate with finance theme

在查全率方面,由于爬蟲(chóng)的爬行是一個(gè)動(dòng)態(tài)的過(guò)程,要想統(tǒng)計(jì)整個(gè)互聯(lián)網(wǎng)中所有的主題相關(guān)頁(yè)面幾乎是不可能完成的任務(wù),因此，挑選了一部分與主題相關(guān)網(wǎng)頁(yè)檢測(cè)爬蟲(chóng)的查全率.經(jīng)過(guò)測(cè)試,Best-First算法的查全率為67%,Best-NFirst算法的查全率僅為69%,而融合了HITS算法的爬蟲(chóng)的查全率為75%.這是由于HITS算法本身就是主題相關(guān)的,因此，對(duì)于相關(guān)網(wǎng)頁(yè)的判斷會(huì)更加準(zhǔn)確.算法運(yùn)行時(shí)間的對(duì)比，如表2所示.表2中：t為運(yùn)行時(shí)間.

由表2可知：在運(yùn)行時(shí)間上,雖然新算法在收獲率上有較好的表現(xiàn),可是由于融合了HITS算法,導(dǎo)致爬蟲(chóng)的運(yùn)行效率遠(yuǎn)遠(yuǎn)落后其他兩種算法,特別是隨著爬蟲(chóng)的運(yùn)行,HITS算法的迭代會(huì)占用更多的時(shí)間,這也是以后需要改進(jìn)的方向.

表2 算法運(yùn)行時(shí)間對(duì)比

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

基于內(nèi)容的主題爬蟲(chóng)由于缺乏全局特性,使爬蟲(chóng)在爬行過(guò)程中難以持續(xù)發(fā)現(xiàn)更多相關(guān)頁(yè)面問(wèn)題,提出了一種新的爬蟲(chóng)策略,引入鏈接全局特性的HITS算法,新的算法在爬蟲(chóng)的收獲率上有較好的表現(xiàn).下一步將對(duì)新算法的時(shí)間復(fù)雜度做出優(yōu)化,使爬蟲(chóng)具有更好的實(shí)用性.

[1] 閔鈺麟,黃永峰.用戶(hù)定制主題聚焦爬蟲(chóng)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與設(shè)計(jì),2015,36(1):17-21.

[2] TAYLAN D,POYRAZ M,AKYOKUS S,etal.Intelligent focused crawler:learning which links to crawl[C]∥International Symposium on Innovations in Intelligent Systems and Applications.Madrid：IEEE Press,2011:504-508.

[3] MENCZER F,PANT G,SRINIVASAN P,etal.Evaluating topic-driven web crawlers[C]∥Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.Queensland:ACM,2001:241-249.

[4] RAWAT S,PATIL D R.Efficient focused crawling based on best first search[C]∥IEEE 3rd International of Advance Computing Conference.Ghaziabad:IEEE Press,2013:908-911.

[5] BATSAKIS S,PETRAKIS E G M,MILIOS E.Improving the performance of focused web crawlers[J].Data and Knowledge Engineering,2009,68(10):1001-1013.

[6] FILIPOWSKI K.Comparison of scheduling algorithms for domain specific web crawler[C]∥IEEE Conference Publications of Network Intelligence Conference.Nara:IEEE Press,2014:69-74.

[7] 羅林波,陳綺,吳清秀.基于 Shark-Search 和 Hits 算法的主題爬蟲(chóng)研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,2010,20(11):76-79.

[8] PAGE L,BRIN S,MOTWANI R,etal.The pagerank citation ranking: Bring order to the web[R].Washington D C:Computer Science,1998:66-73.

[9] ZHENG Ling,BO Yang,ZHANG Ning.An improved link selection algorithm for vertical search engine[C]∥1st International Conference on Information Science and Engineering.Nanjing:IEEE Press,2009:778-781.

[10] 林子皓.主題爬蟲(chóng)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)技術(shù)與發(fā)展,2014,24(8):99-102.

[11] DU Yajun,PEN Qiangqiang,GAO Zhaoqiong.A topic-specific crawling strategy based on semantics similarity[J].Data and Knowledge Engineering,2013,88(18):75-93.

(責(zé)任編輯： 陳志賢 英文審校： 吳逢鐵)

Topic Crawler Algorithm With Link Structure

LIU Shaotao， LI Hongsheng

(College of Computer Science and Technology, Huaqiao University, Xiamen 361021, China)

By analyzing the content-based link selection Best-First algorithm, and introduce the HITS (hyperlink induced topic search) algorithm which can reflect the link value, a new kind of link selection strategy is proposed: Combination of two algorithms, new crawler not only consider the page content, but also the link structure, and can ensure topic relevance and authority in the process of downloading; at the same time, ease the “short-sighted” phenomenon in crawling stage. Experimental result shows the new crawling strategy has better performance than that of the single Best-First algorithm. Keywords： Best-First algorithm； link structure； HITS algorithm； crawling strategy

10.11830/ISSN.1000-5013.201702012

2015-06-24

劉韶濤(1969-)，男，副教授，主要從事軟件體系結(jié)構(gòu)與軟件復(fù)用的研究.E-mail:shaotaol@hqu.edu.cn.

福建省科技廳科研基金資助項(xiàng)目(2011H6016)

TP 311

A

1000-5013(2017)02-0195-06