劉多林,呂 苗

(沈陽理工大學(xué),遼寧 沈陽 110159)

1 引言

現(xiàn)階段,大數(shù)據(jù)逐漸呈爆炸式增長(zhǎng)趨勢(shì),雖然為各行業(yè)發(fā)展提供了契機(jī),但是也為信息采集造成困難。如何確保用戶準(zhǔn)確高效地獲取感興趣的信息,是信息技術(shù)領(lǐng)域面臨的最大困難。

網(wǎng)絡(luò)爬蟲技術(shù)的高自動(dòng)化程度、強(qiáng)擴(kuò)展性等優(yōu)勢(shì),很好地解決了待采集數(shù)據(jù)量大、信息雜亂的問題,該方法的實(shí)質(zhì)是遵守制定好的規(guī)則,從網(wǎng)頁中提取相關(guān)數(shù)據(jù)的程序,最初被應(yīng)用在搜索引擎中,現(xiàn)逐漸應(yīng)用在數(shù)據(jù)采集挖掘工作中。例如,劉景發(fā)[1]等人提出基于網(wǎng)頁空間進(jìn)化的爬蟲策略。以計(jì)算測(cè)試鏈接和種子鏈接之間的最短距離,與鏈接庫中全部鏈接的平均距離作對(duì)比,不斷更新鏈接庫;對(duì)于多目標(biāo)優(yōu)化中最佳解選擇問題,提出最近最遠(yuǎn)候選解法,結(jié)合候選解確定爬蟲路線。楊宇[2]等人將深度優(yōu)先策略當(dāng)作爬蟲方式,設(shè)計(jì)數(shù)據(jù)采集方法。利用詞元字符串相似度矩陣提高檢索列表匹配的準(zhǔn)確性,在決策樹模式下進(jìn)行數(shù)據(jù)識(shí)別與采集。

由于數(shù)據(jù)采集數(shù)量的不確定性和爬蟲節(jié)點(diǎn)性能差異,上述方法容易出現(xiàn)數(shù)據(jù)采集重復(fù)現(xiàn)象,增加系統(tǒng)內(nèi)存。為解決這一問題,本文在Scrapy架構(gòu)[3]下設(shè)計(jì)一種分布式網(wǎng)絡(luò)爬蟲數(shù)據(jù)采集算法。Scrapy是在Twisted異步網(wǎng)絡(luò)庫基礎(chǔ)上開發(fā)的爬蟲框架,在數(shù)據(jù)采集、挖掘等方面具有較高的使用率。此架構(gòu)中的所有組件均為可插拔的,用戶能結(jié)合自身需求對(duì)組件重新開發(fā),實(shí)現(xiàn)高效爬蟲。此外,分布式網(wǎng)絡(luò)爬蟲能夠?qū)⒋罅咳蝿?wù)分解為小任務(wù),再對(duì)小任務(wù)做合并處理,最終完成所有任務(wù),具有較強(qiáng)的協(xié)作互聯(lián)能力和處理效率。

2 Scrapy框架下分布式網(wǎng)絡(luò)爬蟲數(shù)據(jù)采集

2.1 基于Scrapy框架的網(wǎng)絡(luò)爬蟲體系結(jié)構(gòu)設(shè)計(jì)

Scrapy架構(gòu)包括引擎[4]、調(diào)度器、下載器、數(shù)據(jù)分析與數(shù)據(jù)管道五方面構(gòu)成。本文建立的Scrapy架構(gòu)如圖1所示。

圖1 Scrapy架構(gòu)示意圖

1)中心引擎:主要工作是管理全部網(wǎng)絡(luò)數(shù)據(jù)流向,每一次的采集工作都必須經(jīng)過此模塊分析,因此在整個(gè)架構(gòu)中占據(jù)關(guān)鍵地位,如果該模塊失效,則爬蟲操作將無法完成。

2)調(diào)度器:接收來自中心引擎發(fā)出的爬蟲任務(wù),同時(shí)將該任務(wù)放入爬取隊(duì)伍中,當(dāng)中心引擎發(fā)出任務(wù)請(qǐng)求時(shí),從隊(duì)列中選出此任務(wù)。這一模塊的主要目的是分類管控爬取任務(wù)。

3)下載器:支持網(wǎng)頁下載,通過異步形式構(gòu)建和服務(wù)器之間的連接橋梁,程序無需始終等待服務(wù)器的響應(yīng),可先執(zhí)行其它任務(wù),等獲取響應(yīng)后,再做相應(yīng)處理。

4)數(shù)據(jù)解析:是開發(fā)者編寫的爬蟲程序,主要工作是解析下載器傳輸來的代碼,可以同時(shí)對(duì)應(yīng)很多程序,且任意一個(gè)程序都能解析與其對(duì)應(yīng)的網(wǎng)站。

5)數(shù)據(jù)管道:對(duì)上一模塊中的數(shù)據(jù)做深度處理,包括編碼轉(zhuǎn)換、清洗與持久化等。

在上述構(gòu)建的Scrapy架構(gòu)下,設(shè)計(jì)分布式網(wǎng)絡(luò)爬蟲的體系結(jié)構(gòu)。架構(gòu)的最下層將分布式平臺(tái)作為支撐,上層為爬蟲的不同模塊,通過分布式集群實(shí)現(xiàn)網(wǎng)頁數(shù)據(jù)的保存與計(jì)算[5]。原則上這兩部分是無法分割的,但為了邏輯清晰,需分別分析。爬蟲體系整體架構(gòu)如圖2所示。

圖2 Scrapy框架下爬蟲體系架構(gòu)

2.2 爬蟲節(jié)點(diǎn)權(quán)重計(jì)算

在Scrapy架構(gòu)下,為保證爬蟲整體負(fù)載均衡[6],需要結(jié)合每個(gè)節(jié)點(diǎn)的權(quán)重制定爬蟲策略。影響負(fù)載均衡的因素較多,但最主要的是對(duì)采集速度的影響,因此,將節(jié)點(diǎn)一定時(shí)間內(nèi)執(zhí)行的任務(wù)數(shù)量作為判斷節(jié)點(diǎn)性能的指標(biāo)。

如果某節(jié)點(diǎn)在t分鐘內(nèi)執(zhí)行了n個(gè)抓取任務(wù),則此爬蟲節(jié)點(diǎn)在的采集速度表示為

(1)

式中,隨t與n值的增大,該比值會(huì)更加平穩(wěn),此時(shí)采集速度的變化將不能通過公式表達(dá)。為此,引入滑動(dòng)窗口概念,僅統(tǒng)計(jì)近k分鐘內(nèi)的抓取任務(wù)數(shù)量。假設(shè)ni表示近i分鐘的抓取任務(wù)數(shù)量,則權(quán)值表達(dá)式如下

(2)

實(shí)際爬蟲過程中,調(diào)度器分發(fā)的速度非?？?在分發(fā)任務(wù)時(shí),需要設(shè)定任務(wù)分發(fā)量閾值,當(dāng)超出該值后不再分發(fā)。這不僅可以確保任何節(jié)點(diǎn)時(shí)刻均為工作狀態(tài),還能使調(diào)度器結(jié)合采集速度進(jìn)行相應(yīng)的任務(wù)調(diào)整。

2.3 基于蟻群優(yōu)化的爬蟲數(shù)據(jù)采集實(shí)現(xiàn)

2.3.1 蟻群優(yōu)化算法的重要因素確定

本文使用蟻群優(yōu)化算法在Scrapy架構(gòu)的基礎(chǔ)上實(shí)現(xiàn)數(shù)據(jù)采集,此方法借鑒了螞蟻覓食過程,屬于一種全局尋優(yōu)算法,算法本質(zhì)是利用蟻群獲取優(yōu)化問題的最佳解,同時(shí)產(chǎn)生一定信息素[7]。在多次優(yōu)化操作中,螞蟻會(huì)找出最佳路徑,即最優(yōu)解。在蟻群算法中路徑構(gòu)建、信息素更新與目標(biāo)解的選擇是影響算法性能的主要因素。

1)路徑構(gòu)建

針對(duì)智能體K,如果在t時(shí)間點(diǎn)時(shí),其所處網(wǎng)頁是Pi,若Pi中存在某鏈接指向網(wǎng)頁P(yáng)j,則位于Pi的蟻群將結(jié)合某條件判斷是否由Pi運(yùn)動(dòng)至Pj。假定Pi內(nèi)全部鏈接指向的新網(wǎng)頁集合表示為V,使用偽隨機(jī)比例相關(guān)規(guī)則獲取智能體K由當(dāng)前頁面Pi跳轉(zhuǎn)到Pj的幾率,偽隨機(jī)規(guī)則表達(dá)式為

(3)

2)信息素實(shí)時(shí)更新

在蟻群優(yōu)化過程中,智能體在每個(gè)周期內(nèi)都會(huì)更新全部路徑中的信息素,每條路徑中的信息素濃度也會(huì)逐漸降低。由網(wǎng)頁P(yáng)i到Pj的鏈接l(i,j)中的信息素更新表達(dá)式為

(4)

3)目標(biāo)解選取

針對(duì)蟻群優(yōu)化方法得到的每組p個(gè)最佳鏈接,通過快速非支配排列方式與最近最遠(yuǎn)候選解方法,挑選出q(q≤p)個(gè)鏈接添加在集合中,引導(dǎo)爬蟲方向。計(jì)算某兩個(gè)解XS與XY的目標(biāo)函數(shù)距離[10]

(5)

式中,Fi(XS)與Fi(XY)分別代表XS、XY的第i個(gè)目標(biāo)函數(shù)值。

本文使用一個(gè)隊(duì)列CQ保存全部非支配解,再通過最近最遠(yuǎn)候選解算法從CQ中挑選一組鏈接,將其指向的頁面當(dāng)作下個(gè)周期的原始爬取節(jié)點(diǎn)。

2.3.2 爬蟲策略設(shè)計(jì)

1)主題相似度計(jì)算

在基于蟻群優(yōu)化的爬蟲策略制定過程中,假設(shè)有M個(gè)螞蟻,每只螞蟻從當(dāng)前頁面鏈接中挑選下一階段爬行網(wǎng)頁,同時(shí)將現(xiàn)處頁面中全部鏈接保存到等待隊(duì)伍中。針對(duì)新加入的鏈接,需計(jì)算主題相關(guān)度,計(jì)算方法如下。

鏈接指向頁面中的信息一般與鏈接所處頁面的信息具有相關(guān)性,前者是后者的相關(guān)說明。所以鏈接指向頁面與所處頁面之間的主題相關(guān)度,就是評(píng)價(jià)該鏈接是否和采集內(nèi)容相關(guān)的重要標(biāo)準(zhǔn)。針對(duì)鏈接l指向頁面Pu,利用下述公式描述文本特征向量

U={u1,u2,…,ui,…,un}

(6)

則文本特征權(quán)值向量的計(jì)算公式如下

Wu=(wu1,wu2,…,wuj,…,wun)

(7)

式中,wuj代表第j個(gè)主題詞在Pu中的權(quán)值。

鏈接l指向的頁面具有的主題相關(guān)度表示為

R(Pu)=Sem(T,U)

(8)

綜上所述,獲取鏈接主題的相似度表達(dá)式

R(l)=h1×R(al)+h2×R(Pl)+h3×R(Pu)

(9)

式中,h1、h2與h3代表鏈接本身、鏈接所處網(wǎng)頁以及指向網(wǎng)頁的主題相關(guān)度權(quán)值系數(shù),符合h1+h2+h3=1的要求。R(Pl)代表l所處網(wǎng)頁具有的主題相似度。

如果計(jì)算出的主題相似度高于設(shè)定閾值η,將此鏈接指向的頁面保存到集合中。反復(fù)操作上述過程,直至所有智能體均獲得最大爬行深度,再利用式(4)實(shí)現(xiàn)信息素濃度更新。

2)重合度計(jì)算

為避免重復(fù)數(shù)據(jù)采集,需計(jì)算數(shù)據(jù)的重合度。概念C1與C2二者重合度可通過它們的公共祖先節(jié)點(diǎn)描述,C1與C2重合度影響因子IFCoi表示為

(10)

式中,count(Up(C1)∩(Up(C2)))表示C1與C2公共節(jié)點(diǎn)數(shù)量,max(Depth(C1),Depth(C2))則代表C1與C2的層次深度極大值。IFCoi值越大說明二者重合度越高,在爬蟲過程中需要舍棄一個(gè)節(jié)點(diǎn),這樣能夠有效避免采集到重復(fù)數(shù)據(jù)。

3)爬蟲數(shù)據(jù)采集步驟

因此,利用蟻群優(yōu)化算法實(shí)現(xiàn)網(wǎng)絡(luò)爬蟲數(shù)據(jù)采集的詳細(xì)過程表示為:

步驟一:建立本體領(lǐng)域,確定數(shù)據(jù)采集主體,選擇適量種子鏈接,添加到初始鏈接隊(duì)列中,對(duì)參數(shù)α與β做初始化處理,設(shè)定相關(guān)閾值η。

步驟二:初始化處理所有鏈接的信息素濃度C0,令智能體執(zhí)行爬蟲任務(wù),獲得智能體K在現(xiàn)階段頁面Pi上的全部子鏈接,同時(shí)做過濾處理,將處理后的子鏈接保存到新的集合中;獲取Pi中主體相似度。

步驟四:如果l的主題相似度高于η,將l所指網(wǎng)頁P(yáng)K添加到等待鏈接結(jié)合中,若PK相似度大于η,則保存在網(wǎng)頁集合中,反之刪除l。

步驟五:如果爬行深度已經(jīng)是最大深度,則需清空禁忌表與初始鏈接隊(duì)列,執(zhí)行下一步驟,反之返回步驟三。

步驟六:根據(jù)式(4)更新全部路徑中的信息素濃度,直到信息素濃度無法指明爬取方向?yàn)橹?算法結(jié)束,完成數(shù)據(jù)采集。

3 仿真數(shù)據(jù)分析與研究

仿真中,最重要的硬件設(shè)備是主節(jié)點(diǎn)服務(wù)器,該服務(wù)器直接影響實(shí)驗(yàn)效果。為此,本文使用的服務(wù)器配置如下:內(nèi)存為32GB,硬盤是250GB,帶寬頻率設(shè)置成10MB/S。

1)爬準(zhǔn)率與爬全率測(cè)試

爬準(zhǔn)率與爬全率是衡量網(wǎng)絡(luò)爬蟲算法性能的常用指標(biāo)。其中前者是爬蟲爬取到和需采集內(nèi)容有關(guān)的數(shù)據(jù)數(shù)量占比情況,后者則為爬蟲爬取到和需采集內(nèi)容有關(guān)的數(shù)據(jù)量,占全網(wǎng)絡(luò)中和該采集內(nèi)容有關(guān)的數(shù)據(jù)量之比。計(jì)算公式分別如下

(11)

(12)

式中,N代表爬取到和采集內(nèi)容有關(guān)的數(shù)據(jù)量,W表示網(wǎng)絡(luò)中和該采集內(nèi)容有關(guān)的數(shù)據(jù)數(shù)量,G是爬取到的總信息量。

為凸顯本文方法性能,將測(cè)試結(jié)果與網(wǎng)頁空間進(jìn)化爬蟲策略、深度優(yōu)先爬蟲算法進(jìn)行對(duì)比,兩個(gè)評(píng)價(jià)指標(biāo)的對(duì)比結(jié)果分別如圖3和4所示。

圖3 不同方法爬準(zhǔn)率對(duì)比圖

圖4 不同方法爬全率對(duì)比圖

由圖3和4可知,本文方法始終保持95%以上的爬準(zhǔn)率,沒有出現(xiàn)隨數(shù)據(jù)量增多爬準(zhǔn)率下降的表征;在爬全率對(duì)比圖中,所提方法隨數(shù)據(jù)量增加出現(xiàn)并不顯著的下降趨勢(shì),其它方法下降程度明顯。這是因?yàn)楸疚姆椒軌驕?zhǔn)確計(jì)算出網(wǎng)頁與采集內(nèi)容之間的相關(guān)度,提高爬蟲爬行準(zhǔn)確性,同時(shí)計(jì)算了每個(gè)節(jié)點(diǎn)權(quán)重,結(jié)合權(quán)重信息執(zhí)行爬行任務(wù),保證了爬取的全面性。

2)去重效果測(cè)試

圖5為不同方法的去重效果對(duì)比結(jié)果。

圖5 不同方法去重效果對(duì)比圖

圖5顯示,三種算法隨采集數(shù)據(jù)量的增多,采集到的重復(fù)數(shù)據(jù)均有所增加。但所提爬蟲算法是建立在Scrapy架構(gòu)下的,其中心引擎模塊會(huì)對(duì)數(shù)據(jù)進(jìn)行分析,有效刪除重復(fù)數(shù)據(jù),也能避免對(duì)重復(fù)數(shù)據(jù)的誤判。

3)爬蟲速度測(cè)試

對(duì)于優(yōu)秀的爬蟲算法而言,僅僅具備較高的爬行準(zhǔn)確率還遠(yuǎn)遠(yuǎn)不夠,爬行速度是衡量算法好壞的又一重要標(biāo)準(zhǔn)。假設(shè)節(jié)點(diǎn)數(shù)量分別為5個(gè)和20個(gè),在這三種情況下,上述算法的爬行速度分別如圖6和7所示。

圖6 節(jié)點(diǎn)數(shù)量為5個(gè)時(shí)爬蟲速度對(duì)比

圖7 節(jié)點(diǎn)數(shù)量為20時(shí)爬蟲速度對(duì)比

分析圖6和7得出,隨節(jié)點(diǎn)數(shù)量增加,爬蟲速度均有提高。且無論節(jié)點(diǎn)數(shù)量多少,爬行速度趨勢(shì)大致相同,在前8分鐘時(shí)爬蟲速度有不同程度起伏,8分鐘之后爬取速度逐漸平穩(wěn),表明三種方法的爬行穩(wěn)定性較強(qiáng)。其中,Scrapy架構(gòu)下的爬蟲算法通過蟻群方式合理設(shè)置爬行路徑,提高爬蟲速度,說明該方法能夠在較短時(shí)間內(nèi)采集更多數(shù)據(jù)。

4 結(jié)論

互聯(lián)網(wǎng)中的信息正以幾何倍數(shù)增長(zhǎng),用戶要想在網(wǎng)絡(luò)中采集到想要的信息十分困難。本文提出里Scrapy架構(gòu)下的分布式網(wǎng)絡(luò)爬蟲數(shù)據(jù)采集方法。通過對(duì)Scrapy各模塊的設(shè)計(jì),保證爬蟲任務(wù)有序進(jìn)行,再采用多目標(biāo)蟻群算法,設(shè)置爬蟲路徑,提高爬蟲效率。仿真從多角度驗(yàn)證了該方法性能,不但提高數(shù)據(jù)采集的精準(zhǔn)度,還能減少采集時(shí)間,避免重復(fù)采集。在未來研究中,可結(jié)合具體需求擴(kuò)展功能,設(shè)置一套完整的爬蟲系統(tǒng),使海量網(wǎng)絡(luò)信息更好地服務(wù)于用戶。