可動(dòng)態(tài)自適應(yīng)主題爬蟲的研究?

肖新鳳 余 偉 李石君 陳亞輝 劉倍雄 劉永明

（1.廣東環(huán)境保護(hù)工程職業(yè)學(xué)院 佛山 528216）（2.武漢大學(xué) 武漢 430079）

1 引言

通用搜索引擎逐漸暴露出其專業(yè)性不強(qiáng)、搜索結(jié)果過(guò)于寬泛的缺點(diǎn)。針對(duì)于通用搜索引擎的這些弊端和不足，相關(guān)學(xué)者專門提出了限定在某一特定主題的垂直搜索引擎的解決方案。垂直搜索引擎更專注于特定主題，搜索結(jié)果更為細(xì)致。是傳統(tǒng)的通用搜索引擎的延伸以及互補(bǔ)方案，有效地解決了通用搜。而作為垂直搜索引擎中重要的技術(shù)——主題爬蟲（topical crawler），主題爬蟲是指采用了主題搜索算法的爬蟲，在爬行的過(guò)程中，可以僅對(duì)主題相關(guān)的頁(yè)面進(jìn)行抓取［1］。業(yè)界中對(duì)主題爬蟲算法的相關(guān)研究主要集中在以下四個(gè)方面:頁(yè)面的主題判別；URL重要度排序；領(lǐng)域主題模型的表述；主題資源的覆蓋率；傳統(tǒng)的主題爬蟲使用預(yù)先訓(xùn)練好的主題模型算法來(lái)判斷所抓取得到的目標(biāo)網(wǎng)頁(yè)是否主題相關(guān)。然而，在實(shí)際的狀況中，互聯(lián)網(wǎng)中的各類信息也在始終不斷發(fā)生著變化，相關(guān)領(lǐng)域可能會(huì)不斷涌現(xiàn)出新的知識(shí)和名詞，靜態(tài)的主題模型對(duì)動(dòng)態(tài)的網(wǎng)絡(luò)信息往往無(wú)能為力。其次，用戶在定義主題時(shí)本身就可能存在著領(lǐng)域概念涵蓋不全，子領(lǐng)域信息不足等問(wèn)題。

傳統(tǒng)的主題爬蟲在面對(duì)動(dòng)態(tài)變化的互聯(lián)網(wǎng)時(shí)存在著主題知識(shí)涵蓋不全、領(lǐng)域知識(shí)更新以及主題資源中心轉(zhuǎn)移等問(wèn)題。針對(duì)傳統(tǒng)的主題爬蟲所存在的不足，本文提出了一種可動(dòng)態(tài)自適應(yīng)互聯(lián)網(wǎng)信息的主題爬蟲。本文所涉及工作及貢獻(xiàn)主要分為三個(gè)方面:

1）本文提出了一種可動(dòng)態(tài)選擇種子URL的TopicHub算法。主題爬蟲在每次抓取任務(wù)結(jié)束后，基于本次抓取得到的主題頁(yè)面集構(gòu)建出站點(diǎn)的主題資源圖，同時(shí)使用Tarjan算法和縮點(diǎn)的技巧減小圖的規(guī)模，根據(jù)節(jié)點(diǎn)的主題特征和鏈接結(jié)構(gòu)選擇出站點(diǎn)THub頁(yè)面集，最終將各個(gè)站點(diǎn)的THub頁(yè)面集進(jìn)行合并和排序，作為下次增量抓取的入口鏈接集。

2）針對(duì)于靜態(tài)本體庫(kù)所存在的主題信息涵蓋不全、領(lǐng)域知識(shí)變化更新等問(wèn)題，本文提出了一種可動(dòng)態(tài)擴(kuò)充領(lǐng)域語(yǔ)義信息的SDTP算法。結(jié)合靜態(tài)本體庫(kù)與主題的動(dòng)態(tài)語(yǔ)義來(lái)描述主題模型，并根據(jù)抓取的主題頁(yè)面抽取出新的領(lǐng)域名詞以擴(kuò)充主題信息，最終利用相應(yīng)的算法計(jì)算得出網(wǎng)頁(yè)的主題相似度。

3）基于本文提出的兩個(gè)算法:TopicHub算法和SDTP算法實(shí)現(xiàn)一個(gè)可動(dòng)態(tài)自適應(yīng)的主題爬蟲系統(tǒng)TDA-Crawler。該主題爬蟲有效地解決了傳統(tǒng)的主題爬蟲在面對(duì)動(dòng)態(tài)變化的互聯(lián)網(wǎng)信息時(shí)存在的不足之處。

2 相關(guān)工作

早在1999年，Soumen Chakrabartia等提出可以使用分類器作為主題爬蟲中網(wǎng)頁(yè)主題相關(guān)性的判斷依據(jù)，并抽取出網(wǎng)絡(luò)拓?fù)涞闹匾?jié)點(diǎn)，開啟了使用機(jī)器學(xué)習(xí)的方法指導(dǎo)主題爬蟲的先河［2］。Junghoo Cho等指出在主題爬蟲中URL的抓取順序?qū)τ谧罱K的結(jié)果有著重要的影響［3］。在該算法中，將Best-first算法的思想應(yīng)用到主題爬蟲的爬行中，有效地解決了傳統(tǒng)的廣度優(yōu)先抓取存在的不足。P.De Bra和 Michael Hersovici等分別提出了 Fish Search 算法［4］和 Shark Search 算法［5］用于計(jì)算頁(yè)面的主題相關(guān)度。

與此同時(shí)，隨著對(duì)主題爬蟲算法相關(guān)研究的日趨成熟，許多學(xué)者越來(lái)越注意到使用靜態(tài)的主題爬蟲模型已無(wú)法滿足領(lǐng)域知識(shí)的變化。Wu等嘗試將遺傳算法應(yīng)用到主題爬蟲的搜索策略中，根據(jù)種群的平均適應(yīng)度，設(shè)置動(dòng)態(tài)適應(yīng)度函數(shù)和遺傳算子，以此保證主題爬蟲可具有一定的動(dòng)態(tài)適應(yīng)性［6］。針對(duì)于主題爬蟲信息的不足，李東暉等提出了可根據(jù)網(wǎng)絡(luò)信息主題自動(dòng)擴(kuò)充的無(wú)監(jiān)督的主題網(wǎng)絡(luò)爬蟲［7］。傅向華、馮博琴等實(shí)現(xiàn)了一種主題爬蟲的在線增量自學(xué)習(xí)，并以此不斷地改善主題評(píng)估器［8］。Chang Su等提出了一種高效的基于本體自學(xué)習(xí)的聚焦爬蟲［8］。吳永輝等提出了一種站點(diǎn)排序和種子URL選擇的相關(guān)算法，可以基于動(dòng)態(tài)選擇出熱點(diǎn)的種子站點(diǎn)，將選擇出的站點(diǎn)列表作為新的種子URL列表［10］。Priyatam等提出利用Twitter中用戶發(fā)出的鏈接作為種子URL的篩選池，利用URL構(gòu)成的圖模型來(lái)計(jì)算頁(yè)面相似度的方法［11］。

針對(duì)傳統(tǒng)的主題爬蟲的不足Zheng等利用句法依賴分析來(lái)改進(jìn)聚焦爬蟲的爬行［12］，利用TF-IDF算法和句法共現(xiàn)來(lái)抽取關(guān)鍵字，并使用鏈接錨文本與上下相結(jié)合的方法來(lái)評(píng)估一個(gè)URL的優(yōu)先級(jí)。2016年Seyfi等提出T-Graph準(zhǔn)則。由T-Graph實(shí)現(xiàn)的主題爬蟲相比于傳統(tǒng)的主題爬蟲，召回率提高了接近 50%［13］。Dilip等提出了SAFSB算法用來(lái)解決主題的爬蟲本體自學(xué)習(xí)［14］。Hussain等提出了一種無(wú)監(jiān)督的方法，利用基于詞匯的本體學(xué)習(xí)框架和混合語(yǔ)義相關(guān)概念，將網(wǎng)頁(yè)與元數(shù)據(jù)進(jìn)行距離匹配，計(jì)算其主題相似度，最終實(shí)現(xiàn)了一個(gè)可自適應(yīng)語(yǔ)義的主題爬蟲［15］。

此外，在主題爬蟲中，往往需要反復(fù)對(duì)互聯(lián)網(wǎng)進(jìn)行增量抓取。在傳統(tǒng)的實(shí)現(xiàn)中，用戶往往一次性指定種子URL后，以后每次的增量抓取都從種子URL作為初始入口進(jìn)入。然而，隨著抓取內(nèi)容和抓取范圍的不斷擴(kuò)張，在增量抓取過(guò)程中，依然由固定的種子URL出發(fā)使得距離種子URL距離過(guò)遠(yuǎn)的主題頁(yè)面更新速度緩慢，且不利于發(fā)現(xiàn)新的關(guān)鍵資源。因此，本文在著力于解決主題爬蟲的領(lǐng)域模型的表述和頁(yè)面主題判別算法同時(shí)，研究了主題爬蟲在動(dòng)態(tài)網(wǎng)絡(luò)環(huán)境下的主題模型的動(dòng)態(tài)變化，提出了一種可自適應(yīng)互聯(lián)網(wǎng)中動(dòng)態(tài)信息的主題爬蟲算法。該算法從種子站點(diǎn)的再選擇和主題知識(shí)的自演變兩方面實(shí)現(xiàn)主題爬蟲的動(dòng)態(tài)適應(yīng)。

3 源URL的動(dòng)態(tài)更新策略

在實(shí)際情況中，用戶為主題爬蟲所提供的源URL往往質(zhì)量不高。同時(shí)，由于互聯(lián)網(wǎng)信息的動(dòng)態(tài)變化和網(wǎng)頁(yè)的持續(xù)增加，一方面有可能會(huì)有新的優(yōu)質(zhì)源URL，另一方面用戶先前定義的源URL有可能在新的網(wǎng)絡(luò)環(huán)境出現(xiàn)重要度下降的現(xiàn)象?；诖?，本文提出TopicHub算法，用以表示頁(yè)面在整個(gè)主題網(wǎng)頁(yè)集中的重要度，同時(shí)基于TopicHub算法在主題爬蟲的網(wǎng)頁(yè)集中動(dòng)態(tài)地選擇出新的源URL。

3.1 TopicHub算法的定義

在本文中，我們把主題爬蟲中一個(gè)優(yōu)質(zhì)的源URL對(duì)應(yīng)的頁(yè)面稱為THub頁(yè)面。一個(gè)THub網(wǎng)頁(yè)應(yīng)該具有以下特性:

1）指向大量的主題相關(guān)的頁(yè)面。在HITS算法［18］中稱這種頁(yè)面為Hub頁(yè)面，通常在現(xiàn)實(shí)世界中體現(xiàn)為導(dǎo)航式網(wǎng)站或者目錄型頁(yè)面。

2）指向的頁(yè)面更新頻繁或者所屬的站點(diǎn)網(wǎng)頁(yè)更新頻繁。

3）本身就是主題相關(guān)度很高的網(wǎng)頁(yè)。

此外，種子站點(diǎn)以及URL的爬行順序?qū)τ谥黝}爬蟲的質(zhì)量具有極大的影響，在Web網(wǎng)絡(luò)中主題相關(guān)頁(yè)面指向的網(wǎng)頁(yè)通常情況下大多數(shù)也都是與主題相關(guān)。因此URL抓取順序的先后往往決定著主題頁(yè)面是否盡快地能被抓取到。

由于互聯(lián)網(wǎng)信息過(guò)于龐大，對(duì)于互聯(lián)網(wǎng)拓?fù)鋱D往往難以進(jìn)行分析和計(jì)算。在本文中采用了一種三階段的節(jié)點(diǎn)重要度計(jì)算方法——TopicHub算法，用來(lái)減少網(wǎng)絡(luò)節(jié)點(diǎn)重要度的計(jì)算復(fù)雜度:

階段1:計(jì)算每個(gè)站點(diǎn)的重要度，并統(tǒng)計(jì)各個(gè)站點(diǎn)的數(shù)據(jù)信息；

階段2:在每個(gè)站點(diǎn)內(nèi)部求出THub頁(yè)面集及其頁(yè)面重要度；

階段3:對(duì)各個(gè)站點(diǎn)的THub頁(yè)面集進(jìn)行合并和排序。

3.1.1 站點(diǎn)重要度TSI值的計(jì)算

首先我們將抓取到的網(wǎng)頁(yè)集δ，按URL域名的劃分方法，將網(wǎng)頁(yè)集劃分為到各自的站點(diǎn)集S中，其中S∈δ。

本文將從網(wǎng)站更新頻度、主題信息和鏈接結(jié)構(gòu)等方面綜合考量一個(gè)站點(diǎn)的重要度。在本文中，使用TSI表示一個(gè)站點(diǎn)的重要度，其計(jì)算方式如式（1）所示:

其中TSI(S)指的是網(wǎng)站S的重要度。Sfreq指的是站點(diǎn)更新頻度，其計(jì)算方式如式（2）所示。該屬性在表示站點(diǎn)在單位時(shí)間段內(nèi)新增網(wǎng)頁(yè)的數(shù)目。本文在考慮新增網(wǎng)頁(yè)數(shù)目的同時(shí)，也考慮了新增網(wǎng)頁(yè)中主題相關(guān)網(wǎng)頁(yè)的比例。

在式（2）中，Sr指的是本次抓取過(guò)程中該站點(diǎn)更新的主題相關(guān)的網(wǎng)頁(yè)集，其中 p∈Sr；Sim(p)指的是網(wǎng)頁(yè)p的主題相關(guān)度，該主題相關(guān)度由主題相關(guān)度算法計(jì)算得到；Su指的是本次抓取新增的非主題相關(guān)的網(wǎng)頁(yè)集，而 ||Su則表示該網(wǎng)頁(yè)集的大?。籘指的是從上次抓取到本次抓取所用的時(shí)間，以天為單位；α為權(quán)重參數(shù)，表示站點(diǎn)更新頻度中主題因素的占比大小，取0＜α＜1。

SiteRank(S)是基于PageRank在描述站點(diǎn)重要度方面的改進(jìn)算法，其計(jì)算方式如下:

類似于PageRank算法［17］，在式（3）中，表示指向站點(diǎn)S的站點(diǎn)集合。L(Z)表示站點(diǎn)Z的出鏈總數(shù)即出度值，N表示站點(diǎn)的總數(shù)，δ是阻尼系數(shù)，表示跳轉(zhuǎn)到網(wǎng)站的概率。

與PageRank算法在初始化階段，為每個(gè)節(jié)點(diǎn)設(shè)置了一個(gè)統(tǒng)一的隨機(jī)值作為初始值不同的是，在SiteRank算法中每個(gè)站點(diǎn)的初始值為其站點(diǎn)更新頻度Sfreq，由式（2）計(jì)算所得到。與PageRank算法相似，經(jīng)過(guò)不斷的迭代計(jì)算，每個(gè)站點(diǎn)的THS值將趨于穩(wěn)定。通過(guò)使用式（1）在網(wǎng)頁(yè)集中進(jìn)行計(jì)算，我們可以得到各個(gè)站點(diǎn)的重要度THS值。

3.1.2 站點(diǎn)內(nèi)THub節(jié)點(diǎn)的選取

對(duì)主題爬蟲某個(gè)站點(diǎn)的網(wǎng)頁(yè)集進(jìn)行站點(diǎn)內(nèi)THub節(jié)點(diǎn)的選取時(shí)，對(duì)站點(diǎn)網(wǎng)頁(yè)集進(jìn)行剪枝，去掉主題無(wú)關(guān)的頁(yè)面。在本文中，我們只選擇主題相關(guān)頁(yè)面及其入鏈集和出鏈集。對(duì)于站點(diǎn)s，我們將其中所有的主題相關(guān)頁(yè)面以及其中每個(gè)頁(yè)面p的入鏈集 Γ-(p)和出鏈集 Γ+(p)，將與其構(gòu)成子圖Gs=(V，E)。本文首先從主題相關(guān)度和鏈接結(jié)構(gòu)兩方面計(jì)算了主題資源圖中各個(gè)節(jié)點(diǎn)的重要度，接著對(duì)圖模型進(jìn)行計(jì)算，選擇出主題資源圖中具有代表性的節(jié)點(diǎn)集，即THub頁(yè)面集。

1）節(jié)點(diǎn)重要度

我們將主題資源圖中一個(gè)頁(yè)面p的重要度表示為如下:

sim(p)表示頁(yè)面p的主題相似度，CAPp表示頁(yè)面p的主題聚合度歸一化處理后的值，由式（5）計(jì)算所得。α表示頁(yè)面聚合度在頁(yè)面重要度的比重。

在式（5）中，CAPp表示一個(gè)頁(yè)面的主題聚合度，所謂頁(yè)面聚合度指的是其指向頁(yè)面的個(gè)數(shù)，即外鏈數(shù)。如果指向頁(yè)面較多，則說(shuō)明該頁(yè)面極有可能是索引型頁(yè)面。我們?cè)诳紤]頁(yè)面聚合度的同時(shí)，也考慮了主題知識(shí)的影響。

其中Rp表示該頁(yè)面指向的主題相關(guān)頁(yè)面集，則代表其總個(gè)數(shù)。Up指的是該頁(yè)面指向的主題無(wú)關(guān)頁(yè)面集， ||Up則代表其總個(gè)數(shù)。β是阻尼系數(shù)，表示主題因素在頁(yè)面聚合度中所占的比重大小，其取值范圍為0＜β＜1。

同時(shí)，考慮實(shí)際情況下，某些站點(diǎn)可能每張網(wǎng)頁(yè)的主題聚合度都很大，具體表現(xiàn)為側(cè)欄索引型頁(yè)面。該類型的頁(yè)面主體部分為新聞?wù)模谧髠?cè)欄或者右側(cè)欄擁有大量的指向其他頁(yè)面的鏈接，如“熱點(diǎn)文章”、“相關(guān)文章”等。該類型的頁(yè)面將會(huì)使得該站點(diǎn)各個(gè)頁(yè)面的CAP值普遍偏高。因此，本文需要對(duì)頁(yè)面的CAP值進(jìn)行歸一化處理，其主要方式如式（6）所示。

在式（6）中，CAPavg代表各個(gè)節(jié)點(diǎn)的CAP值的平均值，CAPmax表示最大的CAP值，CAPmin表示最小的CAP值。

2）最小覆蓋集

構(gòu)建的網(wǎng)絡(luò)圖各個(gè)頂點(diǎn)之間有可能出現(xiàn)環(huán)圖或者分離的子圖。我們需要保證最終找的THub頁(yè)面可以覆蓋到站點(diǎn)主題資源圖，即從THub頁(yè)面出發(fā)可以到達(dá)主題資源圖中的任意節(jié)點(diǎn)。為此，我們提出了網(wǎng)絡(luò)圖的最小覆蓋集的概念。

本文對(duì)主題資源圖求取THub節(jié)點(diǎn)的主要算法流程圖如算法1所示:

算法1有向圖縮點(diǎn)算法流程

輸出:Gs經(jīng)過(guò)縮點(diǎn)后的有向圖。

使用算法4-2求取有向圖G的強(qiáng)連通分量集δ

Forδiin δ

forvinδi

使用式（4～5）計(jì)算得到每一個(gè)頂點(diǎn)v的重要度

end for

選擇出強(qiáng)連通分量δi的重要度最高的節(jié)點(diǎn)vmax

將vmax添加到Vs中

將E中以δi中任一節(jié)點(diǎn)為終點(diǎn)的有向邊，其終點(diǎn)均改為vmax，構(gòu)成新的有向邊，并將該新的有向邊添加到Es中

將E中以δi中任一節(jié)點(diǎn)為起點(diǎn)的有向邊，其起點(diǎn)均改為vmax，構(gòu)成新的有向邊，并將該新的有向邊添加到Es中

end for

forviinVs

forVjinVs

ifei，j∈ Es

將點(diǎn)j以及其所屬的邊移出圖Gs

else ifej，i∈ Es

將點(diǎn)i以及其所屬的邊移出圖Gs

end if

end for

end for

3.1.3 各站點(diǎn)THub頁(yè)面集的合并及排序

本文使用算法1對(duì)各站點(diǎn)計(jì)算其內(nèi)部的THub節(jié)點(diǎn)集。在得到各個(gè)站點(diǎn)THub頁(yè)面集之后，需要計(jì)算每個(gè)THub頁(yè)面的全局權(quán)重，并將其根據(jù)詞權(quán)重進(jìn)行排序后，統(tǒng)一作為待抓取隊(duì)列的初始值。其中THub頁(yè)面的全局權(quán)重計(jì)算方式如式（7）所示:

在式（7）中，THubp，S表示屬于站點(diǎn)S的THub頁(yè)面的綜合重要度。Sweight表示該頁(yè)面所屬站點(diǎn)的站點(diǎn)重要度，可由式（1）計(jì)算得到。 pweight表示該頁(yè)面的頁(yè)面重要度，由式（2）計(jì)算得到。THub頁(yè)面的全局權(quán)重計(jì)算方法非常簡(jiǎn)單，考慮了自身頁(yè)面重要度及所屬站點(diǎn)的重要度兩方面。

我們首先在各個(gè)站點(diǎn)的THub頁(yè)面集內(nèi)部進(jìn)行計(jì)算重要度和排序操作，接著對(duì)各個(gè)站點(diǎn)的有序的THub頁(yè)面集進(jìn)行歸并排序，最終得到一批頁(yè)面集或者URL集。該URL集合作為新的種子站點(diǎn)列表，將會(huì)被用來(lái)初始化主題爬蟲再次抓取時(shí)的待抓取隊(duì)列。

3.2 TopicHub算法的分析

上述三階段的TopicHub算法將站點(diǎn)重要度和頁(yè)面重要度分開計(jì)算，得到一批Thub頁(yè)面作為新的種子站點(diǎn)。采用上述的三階段算法相比于傳統(tǒng)的全網(wǎng)絡(luò)型算法來(lái)說(shuō)具有以下優(yōu)點(diǎn)。

1）相比于全局型算法來(lái)說(shuō)，三階段算法所建立的網(wǎng)絡(luò)拓?fù)鋱D規(guī)模較小，可以大大減少其圖運(yùn)算的時(shí)間。

2）在站點(diǎn)內(nèi)部求取THub頁(yè)面集，可以使得各個(gè)站點(diǎn)并行計(jì)算。在求取站點(diǎn)內(nèi)部頁(yè)面集時(shí)，不需要其他站點(diǎn)參與計(jì)算，在實(shí)際情況下，在各站點(diǎn)內(nèi)部THub頁(yè)面集時(shí)可以利用多線程或者分布式技術(shù)加快運(yùn)算速度。

4 領(lǐng)域主題的動(dòng)態(tài)自適應(yīng)策略

隨著互聯(lián)網(wǎng)信息不斷發(fā)生著變化，相關(guān)領(lǐng)域可能會(huì)不斷涌現(xiàn)出新的知識(shí)和名詞，靜態(tài)的主題模型對(duì)動(dòng)態(tài)變化的網(wǎng)絡(luò)信息往往無(wú)能為力。其次，用戶在定義主題時(shí)本身就可能存在著主題模型不夠全面，存在外延詞匱乏、子領(lǐng)域信息不足等問(wèn)題。僅僅用靜態(tài)領(lǐng)域本體庫(kù)來(lái)作為頁(yè)面主題相關(guān)性的考量標(biāo)準(zhǔn)，丟失了主題的語(yǔ)義信息。靜態(tài)領(lǐng)域本體庫(kù)的質(zhì)量完全依賴于領(lǐng)域?qū)＜覙?gòu)建的優(yōu)劣，容易造成領(lǐng)域詞不全面、新領(lǐng)域詞的出現(xiàn)。同時(shí)，也忽略了非領(lǐng)域詞對(duì)主題信息的影響。本文利用靜態(tài)領(lǐng)域本體庫(kù)來(lái)識(shí)別網(wǎng)頁(yè)的主題相關(guān)性，可以作為主題爬蟲的輔助手段，彌補(bǔ)僅僅從語(yǔ)義對(duì)頁(yè)面的主題相關(guān)度進(jìn)行計(jì)算，所造成的噪聲現(xiàn)象。利用主題相悖詞集來(lái)去除那些包含相悖詞的網(wǎng)頁(yè)。利用靜態(tài)主題相似度，來(lái)計(jì)算頁(yè)面和領(lǐng)域本體庫(kù)的匹配程度。在對(duì)頁(yè)面的主題相關(guān)度進(jìn)行評(píng)價(jià)時(shí)，加入了語(yǔ)義因素的考慮。同時(shí)實(shí)現(xiàn)了可以自動(dòng)擴(kuò)充領(lǐng)域相關(guān)詞的算法。

4.1 動(dòng)態(tài)語(yǔ)義相似度的計(jì)算

本節(jié)提出了一種基于TF-IDF以及網(wǎng)頁(yè)標(biāo)簽的關(guān)鍵詞權(quán)重計(jì)算方法，使用動(dòng)態(tài)語(yǔ)義向量的概念，提出了一種從主題網(wǎng)頁(yè)集中增量補(bǔ)充領(lǐng)域主題名詞的方法，并基于Word2vec獲取網(wǎng)頁(yè)的文檔向量［16］，計(jì)算其與動(dòng)態(tài)語(yǔ)義向量的余弦相似度，繼而得到網(wǎng)頁(yè)文本文檔的動(dòng)態(tài)語(yǔ)義相似度。

4.1.1 詞語(yǔ)權(quán)重計(jì)算

本文在計(jì)算網(wǎng)頁(yè)文本中的權(quán)重時(shí)，除了使用傳統(tǒng)的TF-IDF算法外，也考慮到現(xiàn)實(shí)情況下，關(guān)鍵詞在網(wǎng)頁(yè)中所屬的標(biāo)簽或者位置的不同，也往往可以表示權(quán)重的大小。在考慮HTML標(biāo)簽對(duì)關(guān)鍵詞因素的影響時(shí)，我們結(jié)合HTML標(biāo)簽的語(yǔ)義特征，從中提取了詞語(yǔ)的權(quán)重信息。本文主要考慮了＜title＞、＜meta＞、＜h＞、＜a＞、強(qiáng)調(diào)型幾類標(biāo)簽。也從所在的網(wǎng)頁(yè)位置中，提取了文本的權(quán)重信息。

利用式（8）來(lái)計(jì)算詞語(yǔ)的權(quán)重，如下所示:

該權(quán)重計(jì)算公式即考慮了詞語(yǔ)的傳統(tǒng)文本處理中的TF-IDF權(quán)重，也考慮了網(wǎng)頁(yè)中特有的語(yǔ)義信息和權(quán)重信息。

4.1.2 領(lǐng)域名詞的識(shí)別和抽取

互聯(lián)網(wǎng)信息也在不斷發(fā)生著變化，主題爬蟲所關(guān)注的領(lǐng)域中，可能會(huì)不斷涌現(xiàn)出新的知識(shí)和名詞。另一方面，靜態(tài)主題本體庫(kù)本身就可能存在著領(lǐng)域概念涵蓋不全的問(wèn)題。

本文基于Word2vec計(jì)算詞語(yǔ)的詞向量，通過(guò)計(jì)算兩個(gè)詞向量的余弦相似度來(lái)得到詞語(yǔ)之間的關(guān)聯(lián)度或者相似度。并基于Web網(wǎng)頁(yè)的特性對(duì)詞語(yǔ)進(jìn)行加權(quán)，通過(guò)一種離線知識(shí)抽取的方式，提取出有可能是新的領(lǐng)域名詞，將其詞向量、權(quán)重等信息加入動(dòng)態(tài)語(yǔ)義向量中。使用動(dòng)態(tài)語(yǔ)義向量的概念表示主題的動(dòng)態(tài)語(yǔ)義特征。動(dòng)態(tài)語(yǔ)義向量DSV（dynamic semantic vector）的表示方式如式（9）所示:

使用式（10）計(jì)算新增詞的關(guān)聯(lián)度，將主題關(guān)聯(lián)度大于閾值μ的新增詞加入主題的動(dòng)態(tài)語(yǔ)義向量中。

通過(guò)計(jì)算新增詞和每個(gè)靜態(tài)語(yǔ)義向量的相似度之和，然后求其平均值。將該數(shù)值與詞語(yǔ)的權(quán)重信息相結(jié)合，繼而求得該詞語(yǔ)的主題關(guān)聯(lián)度RD。如果RD值大于閾值μ，則判定該新增詞屬于領(lǐng)域新詞，將其詞向量、權(quán)重信息以及詞語(yǔ)本身加入動(dòng)態(tài)語(yǔ)義向量中。

4.1.3 基于Word2vec的網(wǎng)頁(yè)文本向量表示及相似度計(jì)算

在實(shí)際情況下，通常將文檔以向量的形式表示?；谙蛄啃问絹?lái)表示文檔的方法主要集中在:向量空間模型VSM；Doc2Vec；基于Word2Vec的文檔向量表示方法［16］。本文基于Web網(wǎng)絡(luò)中特有的HTML標(biāo)簽語(yǔ)義以及TF-IDF的加權(quán)方法，對(duì)單詞的詞向量進(jìn)行加權(quán)后，轉(zhuǎn)化為文檔的詞向量。

一個(gè)網(wǎng)頁(yè)的文本信息不僅僅是其網(wǎng)頁(yè)正文，還包括許多語(yǔ)義信息，如式（11）所示:

式（11）表明，文本將一個(gè)網(wǎng)頁(yè)的信息歸納為6項(xiàng)。其中C表示網(wǎng)頁(yè)的正文（content）；A表示其父頁(yè)面指向它的鏈接的錨文本信息（anthor）；L表示每一個(gè)HTML標(biāo)簽中所包含的文字（label）；K表示＜meta name="keywords"＞中包含的文本；D表示＜meta name="description"＞標(biāo)簽中包含的文本內(nèi)容；而T則表示網(wǎng)頁(yè)＜title＞＜/title＞標(biāo)簽中的標(biāo)題。

使用預(yù)訓(xùn)練的Word2vec模型，得到每個(gè)詞語(yǔ)的詞向量。整個(gè)文檔是由m個(gè)單詞組成，則文檔的詞向量組成的矩陣為Am×n，其中m為對(duì)應(yīng)網(wǎng)頁(yè)文本的單詞的個(gè)數(shù)，n為詞向量的維數(shù)。在矩陣A中的每一行都代表了一個(gè)詞語(yǔ)對(duì)應(yīng)的詞向量。

我們首先利用式（11）將詞向量組成的文檔矩陣A，轉(zhuǎn)化為加權(quán)矩陣Aw，如下所示。

其中，表示m個(gè)詞語(yǔ)的權(quán)重所組成的對(duì)角矩陣，該權(quán)重由式（9）計(jì)算所得，將其與文檔矩陣A相乘，即可得到加權(quán)矩陣Aw。將加權(quán)矩陣Aw轉(zhuǎn)化為該文檔所對(duì)應(yīng)的文檔向量C，具體方法如式（13）所示:

ci表示文檔向量C中的一項(xiàng)。m表示矩陣A的行數(shù)，aj，i表示第j行第i列的元素。通過(guò)該公式將各個(gè)詞語(yǔ)的詞向量每一列進(jìn)行累加，最終得到網(wǎng)頁(yè)的文檔向量。

在得到網(wǎng)頁(yè)的文檔向量之后，我們需要判定網(wǎng)頁(yè)的主題的動(dòng)態(tài)語(yǔ)義相關(guān)性。在本文中，通過(guò)計(jì)算網(wǎng)頁(yè)文檔向量與主題動(dòng)態(tài)語(yǔ)義向量的余弦相似度來(lái)得到網(wǎng)頁(yè)的動(dòng)態(tài)語(yǔ)義相似度，如式（14）所示:

在式（14）中，DynamicSim(p)表示網(wǎng)頁(yè)p的動(dòng)態(tài)語(yǔ)義相似度。Cp表示網(wǎng)頁(yè)p的文檔向量，其中每一項(xiàng)可使用式（14）計(jì)算所得。DSV表示動(dòng)態(tài)語(yǔ)義向量。最終得到的結(jié)果DynamicSim(p)的取值范圍為［0，1］之間的小數(shù)。

4.2 結(jié)合靜態(tài)本體庫(kù)和動(dòng)態(tài)語(yǔ)義的主題算法

本文將結(jié)合靜態(tài)本體庫(kù)方法和動(dòng)態(tài)語(yǔ)義算法，我們將該算法稱為SDTP算法，識(shí)別所抓取網(wǎng)頁(yè)的主題相關(guān)性。

一個(gè)網(wǎng)頁(yè)的主題相關(guān)性如式（15）所示:

其中DynamicSim(p)指的是網(wǎng)頁(yè)p的動(dòng)態(tài)語(yǔ)義相似度；StaticSim(p)指的是網(wǎng)頁(yè)p的靜態(tài)本體相似度，由式（8）計(jì)算所得。W(p)是指網(wǎng)頁(yè)p經(jīng)過(guò)分詞后的詞語(yǔ)集合。E指的是本體SDO中的主題相悖詞集合。當(dāng)W(p)∩E≠?，即網(wǎng)頁(yè)正文中包含任意一個(gè)主題相悖詞，則網(wǎng)頁(yè)的主題相似度為0，判定為該頁(yè)面屬于主題無(wú)關(guān)頁(yè)面。當(dāng)W(p)∩E=?，即網(wǎng)頁(yè)中不包含主題相悖詞時(shí)，則網(wǎng)頁(yè)的主題相似度將綜合動(dòng)態(tài)語(yǔ)義相似度和靜態(tài)相似度后得出。α是阻尼系數(shù)，表明在網(wǎng)頁(yè)的主題相關(guān)度方面，動(dòng)態(tài)語(yǔ)義相似度所占的比重。

5 實(shí)驗(yàn)結(jié)果及分析

5.1 TopicHub算法的實(shí)驗(yàn)結(jié)果

根據(jù)所提出的優(yōu)質(zhì)源URL的特性得知，一個(gè)優(yōu)質(zhì)的源URL會(huì)指向更多的主題相關(guān)頁(yè)面。因此，我們通過(guò)更新前后所抓取到的主題相關(guān)頁(yè)面的數(shù)目來(lái)衡量源URL的好壞，具體如式（16）所示:

在式（16）中，Na表示主題相關(guān)頁(yè)面的數(shù)目，T表示單位時(shí)間。在本文中，取T為4h。一次單位時(shí)間表示一次爬行的過(guò)程。

本文將構(gòu)建一個(gè)以“稅務(wù)”為主題的聚焦爬蟲，以中國(guó)稅網(wǎng)、人民網(wǎng)財(cái)經(jīng)頻道、FT中文網(wǎng)以及騰訊財(cái)經(jīng)網(wǎng)作為初始的目標(biāo)站點(diǎn)。爬蟲的初始化URL列表如表1所示。

表1 初始化URL列表

為了驗(yàn)證THub算法的有效性，在主題判別、URL過(guò)濾和系統(tǒng)調(diào)度方面的實(shí)現(xiàn)均保持一致、在進(jìn)行實(shí)驗(yàn)時(shí)，盡可能地使兩爬蟲并行進(jìn)行，同時(shí)將爬蟲環(huán)境完全隔離的前提下，我們?cè)O(shè)計(jì)了靜態(tài)源URL爬蟲和THub爬蟲兩個(gè)爬蟲進(jìn)行對(duì)比實(shí)驗(yàn)。為期24h的爬行，分別經(jīng)歷了6次的增量爬行。在THub爬蟲的增量爬行過(guò)程中，源URL不斷發(fā)生變化，如圖1所示。

圖1 Thub爬蟲源URL動(dòng)態(tài)變化曲線圖

由圖1可以看出，隨著每次增量爬取過(guò)程中，源URL在不斷發(fā)生著變化。在時(shí)刻12時(shí)，此時(shí)的源URL列表如表2所示。

表2 動(dòng)態(tài)源URL列表

針對(duì)于兩爬蟲的運(yùn)行結(jié)果，我們統(tǒng)計(jì)出兩爬蟲在各個(gè)時(shí)間段內(nèi)的具體數(shù)據(jù)，并將其繪制成折線圖，如圖2所示。

在圖2所示的結(jié)果中，展示了在不同的時(shí)間段，靜態(tài)源URL爬蟲和TopicHub爬蟲所抓取的新增主題網(wǎng)頁(yè)數(shù)目。在不同的時(shí)間段內(nèi)，互聯(lián)網(wǎng)的信息變化大小不同，但從圖中可以看出，兩爬蟲的折線趨勢(shì)基本保持一致。隨著時(shí)間的增加，各個(gè)爬蟲所可抓取的主題頁(yè)面數(shù)在不斷變少，但總體來(lái)說(shuō)，TopicHub爬蟲在抓取的新增網(wǎng)頁(yè)數(shù)目明顯多于靜態(tài)源URL爬蟲。

圖2 TopicHub算法對(duì)比實(shí)驗(yàn)結(jié)果

5.2 SDTP算法的實(shí)驗(yàn)結(jié)果

在本文中，將SDTP算法與靜態(tài)本體庫(kù)、基于VSM和基于Doc2Vec的主題識(shí)別算法進(jìn)行對(duì)比。本文的實(shí)驗(yàn)基于用戶已標(biāo)注的網(wǎng)頁(yè)數(shù)據(jù)集，主題相關(guān)頁(yè)面占據(jù)80%，即其中包含2000張非主題相關(guān)頁(yè)面和8000張主題相關(guān)頁(yè)面。將標(biāo)注網(wǎng)頁(yè)數(shù)據(jù)集按照3:2的比率分為訓(xùn)練數(shù)據(jù)集和測(cè)試數(shù)據(jù)集兩部分。使用測(cè)試數(shù)據(jù)集對(duì)SDTP算法、VSM算法和Doc2Vec算法進(jìn)行訓(xùn)練，得到語(yǔ)義向量。在測(cè)試數(shù)據(jù)集中進(jìn)行評(píng)測(cè)，得到各個(gè)算法的查準(zhǔn)率和查全率，實(shí)驗(yàn)對(duì)比的結(jié)果如圖3所示。

圖3 SDTP算法實(shí)驗(yàn)對(duì)比結(jié)果

根據(jù)圖3可以看出，在稅務(wù)網(wǎng)頁(yè)稅局?jǐn)?shù)據(jù)集中，SDTP爬蟲相比于單純的靜態(tài)本體庫(kù)有著明顯的優(yōu)勢(shì)，查準(zhǔn)率和查全率分別提升13%和9%。相比于VSM構(gòu)建的主題向量，SDTP算法的兩項(xiàng)指標(biāo)分別高出4%和3.2%。

5.3 TDA-Crawler與各爬蟲性能對(duì)比

將TDACrawler爬蟲與基于靜態(tài)本體庫(kù)的爬蟲、SharkSearch爬蟲進(jìn)行對(duì)比，在實(shí)驗(yàn)中，每一個(gè)爬蟲的種子URL設(shè)置為一致。實(shí)驗(yàn)結(jié)果對(duì)比圖如圖4和圖5所示。

從圖4和圖5可以看出各個(gè)主題爬蟲在隨著抓取范圍和抓取頁(yè)面的不斷增加，其查準(zhǔn)率略微呈現(xiàn)下降的趨勢(shì)而同時(shí)查全率均不斷上升，這與實(shí)際情況相吻合的。而在圖中可以看出，TDA-Crawler的查準(zhǔn)率明顯高于其他兩個(gè)爬蟲，基于靜態(tài)本體庫(kù)的爬蟲由于其僅僅使用關(guān)鍵字的匹配原則，在前期抓取過(guò)程中，查全率非常高，但是查準(zhǔn)率相對(duì)而言較低，當(dāng)爬蟲的爬行進(jìn)行到一定階段后，查準(zhǔn)率和查全率都將受到一定限制。而Shark-Search的爬蟲的表現(xiàn)較為中和，缺少TDA-Crawler的動(dòng)態(tài)主題擴(kuò)充機(jī)制，在查準(zhǔn)率方面也遠(yuǎn)不如TDA-Crawler。

圖4 各爬蟲查準(zhǔn)率對(duì)比圖

圖5 各爬蟲查全率對(duì)比圖

圖6 各爬蟲抓取效率對(duì)比圖

圖6 看出各個(gè)主題爬蟲在隨著爬蟲運(yùn)行時(shí)間的增加，抓取的主題頁(yè)面數(shù)逐漸增加，基于靜態(tài)本體庫(kù)的爬蟲由于其僅僅使用關(guān)鍵字的匹配原則，在前期抓取過(guò)程中可以抓取到更多的頁(yè)面，但是后期增加趨勢(shì)放緩。TDA-Crawler在爬蟲經(jīng)歷主題動(dòng)態(tài)擴(kuò)充和源URL的再選擇后，在后期的主題頁(yè)面抓取效率更為突出。

6 結(jié)語(yǔ)

本文采用了一種三階段的算法將站點(diǎn)重要度和頁(yè)面重要度分開計(jì)算，得到一批Thub頁(yè)面作為新的種子站點(diǎn)。采用上述的三階段算法相比于傳統(tǒng)的全網(wǎng)絡(luò)型算法來(lái)說(shuō)具有以下優(yōu)點(diǎn):相比于全局型算法來(lái)說(shuō)，三階段算法所建立的網(wǎng)絡(luò)拓?fù)鋱D規(guī)模較小，可以大大減少其圖運(yùn)算的時(shí)間；在站點(diǎn)內(nèi)部求取THub頁(yè)面集，可以使得各個(gè)站點(diǎn)并行計(jì)算。在求取站點(diǎn)內(nèi)部頁(yè)面集時(shí)，不需要其他站點(diǎn)的參與計(jì)算，在實(shí)際情況下，在各站點(diǎn)內(nèi)部THub頁(yè)面集時(shí)可以利用多線程或者分布式技術(shù)加快運(yùn)算速度。

在實(shí)際運(yùn)用中，我們將靜態(tài)本體庫(kù)和動(dòng)態(tài)語(yǔ)義向量的方法結(jié)合起來(lái)，用來(lái)判斷網(wǎng)頁(yè)的主題相似度。利用靜態(tài)本體庫(kù)專業(yè)、權(quán)威度高的特征，將網(wǎng)頁(yè)的文本特征始終與專家提供的靜態(tài)本體庫(kù)一致，同時(shí)利用計(jì)算網(wǎng)頁(yè)的動(dòng)態(tài)語(yǔ)義相似度，有效地解決了靜態(tài)本體庫(kù)概念涵蓋不全、非領(lǐng)域詞影響不足等問(wèn)題。TDACrawler的綜合性能進(jìn)行了評(píng)估，實(shí)驗(yàn)證明，相比于傳統(tǒng)的主題爬蟲，TDA Crawler在性能和查準(zhǔn)率方面均有一定的提高。