摘 要：搜索引擎作為互聯(lián)網(wǎng)信息獲取的入口，實現(xiàn)高效、準(zhǔn)確的信息獲取非常重要，爬蟲作為搜索引擎的上游，其重要性不言而喻，特別是大數(shù)據(jù)時代信息更新頻繁，如何在第一時間獲取新聞是實現(xiàn)爬蟲時效性的重要因素。為了充分利用有限資源，提升帶寬利用率，設(shè)計一種基于歷史數(shù)據(jù)預(yù)測的爬蟲調(diào)度算法。該算法通過抓取網(wǎng)站歷史，更新頻次積累數(shù)據(jù)，使用隨機(jī)森林回歸建立模型，并在系統(tǒng)中實現(xiàn)爬蟲調(diào)度。實驗結(jié)果表明，該策略在抓取新鏈的命中率上提升了46%，平均成本降低了11%，平均抓取延時降低了14%。

關(guān)鍵詞：搜索引擎;爬蟲調(diào)度;回歸預(yù)測;隨機(jī)森林

DOI：10. 11907/rjdk.191420

開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

中圖分類號：TP301

文獻(xiàn)標(biāo)識碼：A

文章編號：1672-7800（2020）001-0108-05

0 引言

在過去20年里，網(wǎng)絡(luò)數(shù)據(jù)規(guī)模增長非常迅速，現(xiàn)已全面進(jìn)入大數(shù)據(jù)時代，從基礎(chǔ)行業(yè)到尖端行業(yè)，大數(shù)據(jù)無處不在[1]。搜索引擎作為互聯(lián)網(wǎng)的一大入口，其重要性尤為凸顯，搜索引擎需要從外部網(wǎng)絡(luò)獲取數(shù)據(jù)進(jìn)行加工處理，通常由網(wǎng)絡(luò)爬蟲作為其上游抓取全網(wǎng)數(shù)據(jù)[2-4]。互聯(lián)網(wǎng)上每天都有大量新網(wǎng)頁產(chǎn)生，如何高效、準(zhǔn)確地抓取到最新數(shù)據(jù)成為一項挑戰(zhàn)。如果爬蟲不能及時抓到突發(fā)事件或者相關(guān)內(nèi)容抓取不全，則搜索引擎無法建庫和收錄，導(dǎo)致用戶無法及時搜索到目標(biāo)內(nèi)容，則該技術(shù)將面臨淘汰。

搜索引擎的4個評價指標(biāo)為“快、準(zhǔn)、新、全”[5-6]?！翱臁敝杆阉魉俣瓤?，用戶等待時間越短越好;“準(zhǔn)”指搜索相關(guān)性高，返回的結(jié)果大部分應(yīng)是用戶需要的;“新”指時效性，返回的結(jié)果需盡快收錄最新文章;“全”指網(wǎng)頁覆蓋率，應(yīng)當(dāng)盡可能多地覆蓋全網(wǎng)數(shù)據(jù)。爬蟲第一時間抓取到頁面才能讓搜索引擎第一時間索引并展示相應(yīng)內(nèi)容，因此本文主要針對時效性進(jìn)行研究。

1 通用爬蟲技術(shù)

爬蟲指按照一定規(guī)則，自動抓取互聯(lián)網(wǎng)信息的程序[7]。爬蟲通常分為通用爬蟲和垂直爬蟲，通用型爬蟲設(shè)置好抓取的范圍和目標(biāo)，達(dá)到目標(biāo)就停止爬取，一般信息較多，覆蓋點比較全但需要清除一些垃圾站點;垂直型爬蟲只關(guān)注與特定主題相關(guān)的內(nèi)容或者屬于特定行業(yè)的數(shù)據(jù)，這樣減少了不必要的資源浪費，而且還縮短了網(wǎng)頁抓取時間[8]。兩者根據(jù)使用場景的不同各有優(yōu)缺點，架構(gòu)區(qū)別主要表現(xiàn)在選擇鏈接上。爬蟲從預(yù)先設(shè)置好的種子頁面開始抓取，之后抽取鏈接擴(kuò)展鏈接庫，然后根據(jù)廣度或者深度優(yōu)先深入抓取，盡可能多地覆蓋網(wǎng)頁[9-10]。

1.1 基本爬蟲框架

通常爬蟲架構(gòu)主要模塊為調(diào)度模塊、抓取模塊、下載模塊、頁面分析模塊、鏈接選擇模塊、存儲模塊，所有模塊組合起來形成一個閉環(huán)，流程架構(gòu)如圖1所示。

調(diào)度模塊（ Scheduler）從鏈接選擇模塊（Selector）接受鏈接并將它們分散到一天均勻抓取，交給抓取模塊（ Fetch-er）處理抓取參數(shù)和控制抓取策略，下載模塊（Downloader）獲取鏈接后從互聯(lián)網(wǎng)下載網(wǎng)頁回傳給分發(fā)模塊進(jìn)行處理，然后交給頁面分析模塊（ Extractor）抽取相關(guān)信息，如頁面摘要、時間因子、垃圾信息、鏈接信息等，再根據(jù)策略寫入網(wǎng)頁庫（Pages），新鏈接去重后寫入鏈接庫（Linkbase），鏈接選擇模塊根據(jù)鏈接深度決定是否選擇相關(guān)鏈接，至此整個流程形成一個持續(xù)抓取的閉環(huán)[11-13]。

1.2 時效性

爬蟲主要從抓取種子頁面獲取新網(wǎng)頁，新聞列表頁是最典型的種子頁面，搜索引擎時效性主要體現(xiàn)在新聞類網(wǎng)頁上，第一時間抓取到最新的新聞是搜索引擎最重要的功能，所以對一些更新頻繁的頁面，爬蟲也會頻繁抓取，但高頻次的抓取會讓對方網(wǎng)站承受比較大的壓力，導(dǎo)致對方封禁爬蟲，而且這種做法對自身帶寬要求比較高，網(wǎng)頁并不是隨時會更新，若大量訪問卻提取不出新鏈接，則浪費帶寬資源。因此提出時效性問題，對抓取頻次進(jìn)行精細(xì)化控制，需在壓力和時間上作出平衡決策[14-16]。

網(wǎng)頁內(nèi)容大部分都是人為編輯發(fā)布的信息，因此規(guī)律和不確定性同時存在。白天信息更新比較頻繁，夜間更新較少;一個欄目的編輯者可能是不同的人，發(fā)文時間每天可能不同;突發(fā)事件會導(dǎo)致信息更新頻繁，節(jié)假日會導(dǎo)致信息更新較少。頻次控制最先實現(xiàn)的是使每個種子頁面用固定的間隔進(jìn)行抓取，這樣爬蟲能開始初步工作，但是上述問題不能得到解決，這就需要動態(tài)地進(jìn)行頻次控制，對于網(wǎng)頁更新的變化規(guī)律，相關(guān)學(xué)者經(jīng)過研究發(fā)現(xiàn)，泊松過程是描述這種變化規(guī)律的最佳模式[17-18]。

泊松過程（ Poisson Process）是一種在實踐中常被使用的計數(shù)隨機(jī)過程，描述特定現(xiàn)象發(fā)生次數(shù)隨時間變化的規(guī)律。如果計算在某一段時間內(nèi)出現(xiàn)的隨機(jī)點數(shù)目，該數(shù)目也是隨機(jī)的，且隨著這段時間延伸的不斷變化，該變化過程為伴隨著隨機(jī)點過程的計數(shù)過程[19]。

泊松過程有3個特點：時間（或空間）上的均勻性、未來變化與過去變化沒有關(guān)系（即獨立增量性）、普遍性。

稱去非負(fù)整數(shù)的隨機(jī)過程[t，t+r]為強度（或速率）為入的泊松過程，如果滿足：①N（0）=0;②N（t）為平穩(wěn)獨立增量過程;③對任意的0≤s

在區(qū)間[t，t+r]內(nèi)發(fā)生時間的數(shù)目概率分布為：

在式（1）中，參數(shù)A是一個正數(shù)和固定參數(shù)，稱作抵達(dá)率（或強度）。所以給定在區(qū)間[t，t+r]內(nèi)發(fā)生時間的數(shù)目，則隨機(jī)變數(shù)N（T+）-N（T）呈現(xiàn)泊松過程，參數(shù)為λτ。

2 基于時效性的調(diào)度算法

本部分主要介紹基于時效性的調(diào)度算法，通過挖掘網(wǎng)頁歷史數(shù)據(jù)建模，并提出算法評價方法。

2.1 時效性調(diào)度算法

互聯(lián)網(wǎng)信息更新很頻繁，對于網(wǎng)頁更新的變化規(guī)律，可以通過歷史數(shù)據(jù)挖掘得來。該算法流程如圖2所示。

整個算法分為4個部分：①歷史數(shù)據(jù)積累;②抽取發(fā)布時間;③對歷史數(shù)據(jù)建模;④應(yīng)用調(diào)度模塊。詳細(xì)過程如下：

（1）歷史數(shù)據(jù)積累。首先爬蟲系統(tǒng)正常運行一段時間，網(wǎng)頁調(diào)度算法按默認(rèn)的間隔抓取，記錄下調(diào)度時間和首次抓取時間，保存到網(wǎng)頁庫。

（2）抽取網(wǎng)頁發(fā)布時間。爬蟲系統(tǒng)在運行一定時間后，會累積下大量網(wǎng)頁數(shù)據(jù)，其中正文頁面通常會有文章發(fā)布時間，即使沒有，也能通過算法計算出大概文章時間。設(shè)正文頁面的父頁面上次調(diào)度時間為Tlast，本次調(diào)度時間為T now，頁面發(fā)布時間T page，可以得出結(jié)論Tlast

（3）歷史數(shù)據(jù)建模。網(wǎng)頁包含發(fā)布時間后，即可把同一個種子頁面擴(kuò)散出去的頁面聚類在一起，根據(jù)每個聚類的組，通過隨機(jī)森林回歸進(jìn)行建模，得到種子頁面時效性模型。其中未能抽取出發(fā)布時間的頁面和數(shù)量過小，不進(jìn)行模型構(gòu)建。

（4）應(yīng)用調(diào)度模塊。時效性模型建立好后，在調(diào)度時先查詢是否包含有模型，若有則根據(jù)模型計算出調(diào)度頻率，按照頻率抓取種子頁面。

2.2 隨機(jī)森林回歸

隨機(jī)森林（ Random Forest，RF）是一種基于集成學(xué)習(xí)（ Ensemble Learning）的算法，屬于Bagging類型，通過組合多個弱分類器，并經(jīng)過投票或者取平均值，使最終模型結(jié)果有比較好的精度，并具有良好的泛化性能。隨機(jī)森林采用的弱分類器是分類與回歸樹（ Classification and Regres-sionrree，CART），既可以用于分類，也可以用于回歸，本文采用隨機(jī)森林回歸算法[20]，算法描述如下：

（1）為每顆決策樹產(chǎn)生訓(xùn)練集，使用Bagging抽樣方法生產(chǎn)讓訓(xùn)練數(shù)據(jù)有一定的差異性。一般使用無權(quán)重抽樣算法，每次抽取過程隨機(jī)，之后把結(jié)果放還至原樣本里，則抽出來的子集會有重復(fù)，能解決局部最優(yōu)解的問題。

（2）設(shè)訓(xùn)練樣本有N個特征，從樣本中隨機(jī)選取其中M個特征，從單顆決策樹開始，從M個特征中最優(yōu)的特征進(jìn)行分裂，直到所有訓(xùn)練樣本在該節(jié)點上均為同一類為止。

（3）重復(fù)以上兩個步驟，建立K棵決策樹，此時將待預(yù)測的樣本輸入決策樹，把所有預(yù)測結(jié)果進(jìn)行加權(quán)后作為最終結(jié)果。因為這些決策樹之間并沒有耦合關(guān)系，通常采取并行方式進(jìn)行處理，所以隨機(jī)森林算法速度大幅提高。

2.3 歷史數(shù)據(jù)建模

爬蟲系統(tǒng)在運行一定時間后，會累積大量網(wǎng)頁數(shù)據(jù)，其中正文頁面通常會有文章發(fā)布時間，即使沒有，也能通過算法計算出大概文章時間。設(shè)正文頁面的父頁面上次調(diào)度時間為Tlast，本次調(diào)度時間為T now，頁面發(fā)布時間T page，可以得出結(jié)論Tlast< Tpage≤T now。如果Tlast不存在，說明頁面的父頁面是首次調(diào)度，不能確認(rèn)該頁面出現(xiàn)時間。如果T now一T last<1h，則可以把文章發(fā)布時間約等于兩次調(diào)度的中間值。

本文根據(jù)新增數(shù)據(jù)量每一小時計算一次，每個頁面一天有24個時段的數(shù)據(jù)，共統(tǒng)計了30天的數(shù)據(jù)，得到720項數(shù)據(jù)，每項都為時段內(nèi)的新增頁面數(shù)，抽取部分?jǐn)?shù)據(jù)，算法步驟如下：

Input：網(wǎng)頁庫Pages的源數(shù)據(jù)，Output：網(wǎng)站標(biāo)識與時間戳集合S

for page in Pages

//提取page的鏈接和發(fā)布時間

url，

publish_time←extract（ page）

//如果publish_time不存在或者超過30天就跳過

if publish_time not exist or publish_time+ 30days< now then

coniinue

end if

//分離出域名和路徑

host，

path← splitHostAndPath（url）

//分離第一級path

patho ←splitFirstPath（ path）

//組合出主鍵

key←host+“一”+path0

//在S集合中S[key]中加入新的發(fā)布時間

appendTimeToData（S，key， publish_time）

end for

//遍歷S集合

for key，value in S

//如果網(wǎng)站的新增數(shù)據(jù)小于閾值不進(jìn)行后續(xù)分析

if size of value< 1000 then

if“一”in key then

//如果包含第一級path，嘗試去掉重新加入S集合

host←splitHostFromKey（ key）

appendTimesToData（S，host， value）

end if

//從S集合中刪除網(wǎng)站

deIKeyFromData（S，key）

continue

end if

//對S集合的發(fā)布時間集合進(jìn)行排序

sort（ value）

end for

//產(chǎn)出網(wǎng)站標(biāo)識一發(fā)布時間集合的數(shù)據(jù)集

return S

把上述數(shù)據(jù)繪制成時間一新增數(shù)據(jù)量圖（見圖4），可以觀察到每天更新頻率。

為了更清晰地觀察到數(shù)據(jù)整體趨勢，把時間數(shù)據(jù)的y軸累加，可以得到圖5，對比上下兩個圖可以觀察到很明顯的新增趨勢，并且有一定的周期性，每天白天為數(shù)據(jù)更新高發(fā)時段，并且在這些圖中有4段更新平緩的區(qū)域，對應(yīng)這30天的4周周末，于是把每天的小時數(shù)和每周的周數(shù)當(dāng)作回歸模型自變量。

每個種子頁面均可生成如表1的數(shù)據(jù)，該數(shù)據(jù)為模型的訓(xùn)練數(shù)據(jù)。其中，hO-h23為每天的時段，w0-w6為每周的周數(shù)，均為自變量，value為新增數(shù)據(jù)量，是模型數(shù)據(jù)的因變量。

2.4 調(diào)度算法評價方法

本文采取多種驗證方法進(jìn)行評估，一是對預(yù)測結(jié)果進(jìn)行隨機(jī)交叉驗證，其次是對順序新數(shù)據(jù)的驗證，最后是應(yīng)用本文算法預(yù)測調(diào)度的對比分析。前兩種驗證使用R2Score進(jìn)行判斷，其公式如式（2）所示，可以衡量模型預(yù)測能力優(yōu)劣。

第二種驗證方法是選擇數(shù)據(jù)尾部的數(shù)據(jù)再次計算R2的值，即可判斷預(yù)測模型誤差。

常規(guī)調(diào)度算法是間隔性抓取，不同需求選取不同的抓取間隔，本文把間隔分為10s、20s、30s、1 m、2m，5m、10m、30m、1h、2h幾種情況計算，可按3個維度評判：①每次抓取記為一次成本，統(tǒng)計總成本;②抓取時間與網(wǎng)頁真實出現(xiàn)的差值，最后算出方差;③準(zhǔn)確度，單次抓取得到新鏈接標(biāo)記為抓取準(zhǔn)確，總結(jié)后可算出最后的準(zhǔn)確度。

經(jīng)過改進(jìn)的算法僅關(guān)注成本，但命中率或延遲不是最優(yōu)，因為在定間隔抓取中，高頻次會導(dǎo)致成本高、命中率與延遲低。而低頻次的抓取通常可以實現(xiàn)低成本、高命中率與高延遲。新算法的3項指標(biāo)并不能看出明顯優(yōu)勢，因此本文把3項指標(biāo)量化后加權(quán)得到公式（4），其中設(shè)抓取成本為cost，命中次數(shù)為hit，總延遲為delay，加權(quán)結(jié)果為W。

3 實驗結(jié)果及分析

實驗使用Python開發(fā)的一套爬蟲框架，主要在鏈接選擇模塊和調(diào)度模塊進(jìn)行時效性驗證，其它模塊僅保留基礎(chǔ)功能。實驗環(huán)境為單實例1CIC的Docker集群，出口帶寬保證抓取在lOs內(nèi)返回。

通過隨機(jī)森林進(jìn)行預(yù)測后，分別使用交叉驗證和新數(shù)據(jù)驗證，得到表2的結(jié)果。

R2-Score的準(zhǔn)確度不太穩(wěn)定，但是集中在0.6-0.9左右，交叉驗證后可以看到趨勢基本吻合，如圖6所示。

把預(yù)測結(jié)果經(jīng)過動態(tài)調(diào)度算法處理后應(yīng)用于調(diào)度模塊，經(jīng)過幾種固定間隔和動態(tài)調(diào)度算法的對比，得到表3所示數(shù)據(jù)，成本上中間數(shù)為2 160，動態(tài)調(diào)度算法為1 701，減少了11%的成本;命中率上中間數(shù)為43%，動態(tài)調(diào)度算法為63%，提升了46%;平均延遲中間數(shù)為41，動態(tài)調(diào)度算法為35，降低了14%的延遲?？梢钥吹?，這些指標(biāo)均超過平均水平，并且加權(quán)后的結(jié)果優(yōu)于其它方法。

4 結(jié)語

本文針對爬蟲調(diào)度的時效性問題，提出一種根據(jù)歷史數(shù)據(jù)指導(dǎo)新數(shù)據(jù)調(diào)度抓取的算法。與傳統(tǒng)定間隔抓取相比，該算法在成本、命中率、平均延遲上均高于平均水平，很好地提高了實際抓取過程中的抓取效率，并且算法運行速度較快，由于采用比較基礎(chǔ)的回歸算法，所以針對實際抓取場景可在相對低成本下引入，使網(wǎng)絡(luò)開銷大幅降低。但是，該算法在應(yīng)對突發(fā)性增長時還不夠靈活，需進(jìn)一步改進(jìn)。

參考文獻(xiàn)：

[1]程學(xué)旗，靳小龍，王元卓，等.大數(shù)據(jù)系統(tǒng)和分析技術(shù)綜述[J].軟件學(xué)報，2014，25（09）：1889-1908.

[2] 周德懋，李舟軍.高性能網(wǎng)絡(luò)爬蟲：研究綜述[J].計算機(jī)科學(xué)，2009，（8）：26-29+53.

[3] BRIN S，PACE L.The anatomy of a large-scale hypertextual wehsearch engine [Jl. Computer networks and ISDN systems， 1998. 30 （ 1-7）：107-117.

[4]ARASU A， CHO J，GARCIA-MOLINA H， et al. Searching the web[Jl. ACM Transactions on Internet Technology， 2001，1（1）：2-43.

[5]張興華.搜索引擎技術(shù)及研究[J].現(xiàn)代情報，2004（4）：142-145.

[6] 馬志杰.國外搜索引擎評價研究綜述[J].圖書館學(xué)研究，2013（2）：2—6.

[7]KAUSAR M A， DHAKA V， SINGH S K.Web crawler：a review[J].International Journal of Computer Applications， 2013， 63（2）：3 1-36.

[8] 周立柱，林玲.聚焦爬蟲技術(shù)研究綜述[J].計算機(jī)應(yīng)用，2005（9）：1965-1969.

[9]姜杉彪，黃凱林，盧昱江，等.基于Python的專業(yè)網(wǎng)絡(luò)爬蟲的設(shè)計與實現(xiàn)[J].企業(yè)科技與發(fā)展，2016（8）：17-19.

[10] 李應(yīng).基于Hadoop的分布式主題網(wǎng)絡(luò)爬蟲研究[J].軟件導(dǎo)刊，2016. 15（3）：24-26.

[11] YU J，LI M，ZHANG D.A distributed web crawler model hased oncloud computing[C].Dalian： The 2nd Information Technology andMechatronics Engineering Conference， 2016.

[12]YE F，JINC Z， HUANC Q， et al. The research and implementationof a distributed crawler svstem based on Apache flink [C]. Interna-tional Conference on Algorithms and Architectures for Parallel Pro-cessing， 2018：90-98.

[13]YE F， JING Z， HUANC Q， et al. The research of a lightweight dis-tributed crawling system[C].2018 IEEE 16th International Confer-ence on Software Engineering Research， Management and Applica-tions（ SERA）， 2018： 200-204.

[14]孟濤，王繼民，閆宏飛.網(wǎng)頁變化與增量搜集技術(shù)[J].軟件學(xué)報，2006（5）：1051-1067.

[15]LIU C，WANG W， ZHANG Y， et al. Predicting the popularity of on-line news based on multivariate analysis[C].2017 IEEE Internation-al Conference on Computer and Information Technology （CIT），2017：9-15.

[16]SHI Z， SHI M， LIN W. The implementation of crawling news pagebased on incremental web cra，vler[C].2016 4th International Confer-ence on Applied Computing and Information Technology/3rd Interna-tional Conference on Computational Science/lntelligence and Ap-plied Informatics/lst International Conference on Big Data， CloudComputing， Data Science & Engineering （ACIT-CSII-BCD） ，2016： 348-351.

[17]CHO J， CARCIA-MOLINA H. The evolution of the web and implica-tions for an incremental crawler[ R]. Stanford， 1999.

[18]徐尚瑜.基于泊松過程的爬蟲調(diào)度策略分析[J].現(xiàn)代計算機(jī)：專業(yè)版，2009，（ 12）：68-71.

[19] FISCHER W，MEIER-HELLSTERN K.The Markov-modulated Poisson process （MMPP） cookbook [J]. Performance evaluation，1993，18（2）：149-171.

[20]BREIMAN L Random forests[ J]. Machine learning， 2001， 45（1）： 5-32.

（責(zé)任編輯：江艷）

作者簡介：韓瑞昕（1994-），男，北京工業(yè)大學(xué)信息學(xué)部碩士研究生，研究方向為軟件工程與理論。.