基于市場匹配的多Agent智能爬蟲系統(tǒng)

劉　佳，杜亞軍

(西華大學計算機與軟件工程學院，四川 成都 610039)

?

基于市場匹配的多Agent智能爬蟲系統(tǒng)

劉佳，杜亞軍*

(西華大學計算機與軟件工程學院，四川 成都 610039)

摘要：在網(wǎng)絡(luò)文字、圖像視頻、音頻數(shù)量日益增長的網(wǎng)絡(luò)世界中，網(wǎng)絡(luò)爬蟲爬取結(jié)果變得越來越差，主要表現(xiàn)在爬取網(wǎng)頁的精確率低、召回率低和重復率高等方面。為解決這些問題，結(jié)合市場匹配基本原理和網(wǎng)絡(luò)爬蟲的特點，提出一種基于市場匹配算法的多Agent智能爬蟲系統(tǒng)?；谑袌銎ヅ渌惴?，設(shè)計了多Agent智能爬蟲系統(tǒng)，以雅虎一級目錄12個主題為測試數(shù)據(jù)對網(wǎng)絡(luò)爬蟲爬取網(wǎng)頁的精確率、召回率和重復率進行了分析。結(jié)果表明，與未使用市場匹配算法的系統(tǒng)相比較，基于市場匹配算法的多Agent智能爬蟲系統(tǒng)的精確率提高了9%、召回率提高了8%、重復率降低了5%，其爬蟲性能有較大改善。

關(guān)鍵詞：市場匹配算法；多Agent；智能爬蟲

隨著因特網(wǎng)的快速發(fā)展，網(wǎng)絡(luò)世界里的網(wǎng)絡(luò)文字、圖像視頻、音頻數(shù)量日益增長，導致網(wǎng)絡(luò)爬蟲爬取網(wǎng)頁信息的結(jié)果越來越差。人們結(jié)合分布式網(wǎng)絡(luò)爬蟲中包含多個爬蟲且多個爬蟲能共同工作的特點提出了多Agent網(wǎng)絡(luò)爬蟲系統(tǒng)，使多個網(wǎng)絡(luò)爬蟲可以根據(jù)相同的關(guān)鍵詞同時爬取網(wǎng)頁[1-4]；然而，這導致了網(wǎng)絡(luò)爬蟲在爬取網(wǎng)頁時重復爬取網(wǎng)頁問題的出現(xiàn)。本文在多Agent網(wǎng)絡(luò)爬蟲系統(tǒng)的基礎(chǔ)上，把市場匹配算法應(yīng)用到多Agent網(wǎng)絡(luò)爬蟲系統(tǒng)中，提出了基于市場匹配的多Agent智能爬蟲系統(tǒng)，使多個網(wǎng)絡(luò)爬蟲能夠競爭和協(xié)作。實驗表明，基于市場匹配算法的多Agent智能爬蟲系統(tǒng)中的多個爬蟲能夠相互競爭和協(xié)作，且在爬蟲的性能上有較大的改善。

1多Agent市場匹配算法

1.1　多Agent協(xié)作與競爭模型

在多Agent爬蟲系統(tǒng)中，當一些Agent爬蟲需要協(xié)作完成任務(wù)時，它們會將自己的待爬行URLs進行拍賣，其他有能力的Agent通過競爭來購買一些URLs，增加能力值。令被拍賣的URLs集合為SA={S1,S2,…,Sn}，購買的Agent爬蟲為BA={B1,B2,…,Bm}。這一拍賣過程可以形式化為二分圖。設(shè)GA=(SA,BA,EA)是一個無向圖，其中EA={(Si，Bj)，Si∈SA，Bj∈BA}，代表邊集，連接賣家和買家。如圖1所示，在多Agent爬蟲系統(tǒng)中，被拍賣的URLs為一個賣家Sp，Sp∈SA，而通過競爭來購買URLs的爬蟲為買家Bq，Bq∈BA。邊Eqp=(Sp，Bq)表示買家Bq購買Sp。

圖1　二分圖GA

1.2　估值

當進行拍賣匹配時，賣家集合SA中的每個賣家需要對自己有個估值，即為每個賣家的初始估值，初始估值一般為0，而買家集合BA中的每個買家需要對賣家集合SA中的每個賣家Sp(Sp∈SA)都有一個固定不變的估值[5]，如圖2所示。這些估值是用于在匹配時判斷此匹配是否達到最優(yōu)匹配的標準。

圖2　估值圖

1.3　最優(yōu)分配

為尋求盡可能高的分配方案質(zhì)量，即最優(yōu)分配，文獻[5]提出一個合理分配賣家和買家的方法。該方法使每個賣家和買家的滿意程度總體達到最高。根據(jù)圖2給出的一組估值，可以得到此圖的最優(yōu)分配[5]，其最優(yōu)分配的過程如圖3所示。在達到最優(yōu)匹配的二分圖中，所有匹配結(jié)果如表1所示。從表1可以看出，編號1的匹配結(jié)果達到最優(yōu)匹配，所得到的利益值是最大的，最大利益為6+4+2=12。表中Bq->SP：代表買家q購買賣家p。

編號匹配結(jié)果收益1B1->S1,B2->S2,B3->S36+4+2=122B1->S1,B2->S3,B3->S26+2+2=103B1->S2,B2->S1,B3->S34+4+-1=74B1->S2,B2->S3,B3->S14+2+1=75B1->S3,B2->S1,B3->S21+4+2=76B1->S3,B2->S2,B3->S11+4+1=6

圖3示出了以圖2為初始模型的市場匹配過程。在進行4輪匹配后，此時已經(jīng)出現(xiàn)了1組最優(yōu)匹配，即B1->S1,B2->S2,B3->S3，達到此最優(yōu)匹配的最大利益，為(9-3)+(5-1)+(2-0)=6+4+2=12。

市場匹配算法是求得一組賣家和買家的最優(yōu)匹配。文獻[5]提出了一組市場清倉價格及其對應(yīng)的賣家圖中的最優(yōu)匹配，能產(chǎn)生賣家和買家回報總和的最大可能值，對于任何一組市場清倉價格，賣家圖中的一個最優(yōu)匹配是使估值總和在所有買家和賣家的配對中達到最高。

2多Agent智能爬蟲系統(tǒng)

多Agent智能爬蟲系統(tǒng)主要有4個模塊組成，分別是爬取種子集模塊、爬取網(wǎng)頁模塊[11-12]、匹配網(wǎng)頁模塊和統(tǒng)計存儲實驗數(shù)據(jù)模塊。此系統(tǒng)的總體結(jié)構(gòu)是根據(jù)爬蟲爬取網(wǎng)頁的整個過程(從開始爬取到結(jié)束爬取來進行)設(shè)計的。系統(tǒng)流程圖如圖4所示。程序中有HostAgent、AsAgent和CAgent。

HostAgent為用于管理N個爬蟲的代理。AsAgent_n、CAgent_n分別是同一個爬蟲的不同代理，AsAgent_n用于該爬蟲進行交互(協(xié)作和競爭)，CAgent_n用于該爬蟲爬取網(wǎng)頁。在市場匹配算法的買賣雙方中， AsAgent_n表示該爬蟲進行匹配，CAgent_n不參與。一個AsAgent_n對應(yīng)一個CAgent_n，它們是相互對應(yīng)的，代表同一個爬蟲。

圖4　系統(tǒng)流程圖

2.1　爬取種子集模塊

爬取種子集模塊主要是系統(tǒng)在使用N(N≤20)個爬蟲爬取網(wǎng)頁前，需要給每個爬蟲分別設(shè)置一個初始種子集，以達到同時爬取需要的網(wǎng)頁，提高效率的目的。這部分的設(shè)計思想是先利用用戶輸入的關(guān)鍵詞和線程個數(shù)，即爬蟲個數(shù)來爬取相關(guān)網(wǎng)頁，然后再利用正則表達式的技術(shù)來分離出每個網(wǎng)頁中的統(tǒng)一資源定位符，最后創(chuàng)建出相應(yīng)個數(shù)的C-Agent來爬取分離出的鏈接。

2.2　爬取網(wǎng)頁模塊

爬取網(wǎng)頁模塊是在爬取種子集模塊的基礎(chǔ)上，利用系統(tǒng)創(chuàng)建的N(N≤20)個爬蟲爬取相關(guān)的網(wǎng)頁。當爬蟲爬取到相關(guān)的鏈接時，它會檢測是否是需要的網(wǎng)頁，如果不是，則自動跳過，如果是，系統(tǒng)會爬取此條鏈接，并顯示在系統(tǒng)面板search path tree中，如圖5所示，然后再把此條鏈接的網(wǎng)頁下載到本地存儲。系統(tǒng)每隔一段時間就會檢測每個爬蟲的爬取情況，并根據(jù)每個爬蟲的網(wǎng)頁爬取情況來進行操作。

圖5　爬蟲爬取網(wǎng)頁圖

2.3　匹配網(wǎng)頁模塊

匹配網(wǎng)頁模塊是多Agent智能爬蟲系統(tǒng)中的核心算法模塊。系統(tǒng)在此模塊構(gòu)建了基于匹配網(wǎng)頁和網(wǎng)絡(luò)爬蟲的二分圖模型。當爬蟲還有未爬取的鏈接時，它會把未爬取的鏈接根據(jù)其相似度定一個初始價格，然后向其他爬蟲進行拍賣。系統(tǒng)中成功完成爬取任務(wù)的爬蟲，如果它還有能力，它會購買一些鏈接，但不是一直都在進行鏈接拍賣和購買的過程。系統(tǒng)中有一個時間間隔，每段時間系統(tǒng)將會檢測每個爬蟲的剩余能力值、是否達到下載網(wǎng)頁的目標值等信息，如果達到拍賣的條件，如有大于等于1個網(wǎng)頁進行拍賣且大于等于1個爬蟲能夠購買網(wǎng)頁，此時將會進行網(wǎng)頁的拍賣和購買。系統(tǒng)會利用市場匹配算法進行匹配網(wǎng)絡(luò)爬蟲和網(wǎng)頁，使利益達到最大。

在利用市場匹配算法進行匹配網(wǎng)絡(luò)爬蟲和網(wǎng)頁時，每個AsAgent根據(jù)網(wǎng)頁的相似度來對每個鏈接進行估值，并且AsAgent用其下標代替。此算法只討論AsAgent和鏈接個數(shù)相等的情況。如果AsAgent的個數(shù)大于鏈接個數(shù)，則選取剩余能力值大的AsAgent進行匹配；如果AsAgent的個數(shù)小于鏈接個數(shù)，則表明需要幫助的鏈接大于爬蟲個數(shù)，去掉多余的鏈接[6-10]。算法偽代碼如下所示。

Input：N個提供幫助的AsAgent_[0..n]；需要幫助的urls；網(wǎng)頁價格增長值price。

Output：匹配完成的urls

Begin

001 Evaluation[1..maxn]//爬蟲對網(wǎng)頁的估值

002 Price[1..maxn]//網(wǎng)頁的價格

003 Connection[1..maxn,1..maxm]//連線

004 function Distribute(agent,urls) //匹配函數(shù)

005 gn=agent.length;gm=urls.size();

006 gn=gm=min(gn,gm);

007 beforePrice=(SSPandSBP.SBP(urls);

008 sort(beforePrice);

009 while(NotOver)//拍賣過程

010Connection=0;//初始沒有連線

011Evaluation=beforePrice[n++];

012fori=0 to n do//選取收益最大的網(wǎng)頁

013max=Evaluation[i][0]-Price[0];

014max1=i:int;max2=0;

015for j=1 to n do

016if(max<(Evaluation[i][j]-Price[j]))

017then max=Evaluation[i][j]-Price[j];

max2=j;

018end if;

019end for;

020for k2=0 to gm do //連線

021if max==Evaluation[i][k2]-Price[k2]

022do Connection[i][k2]=1;

023end if;

024end for;

025for i2=0 to gn //驗證是否達到完美匹配

026for j2=0 to gm

027if Connection[i2][j2]==1 do

028Perfect[j2]=1; line[j2]++;

029end if

030end for

031end for

032if Dvalue==gndo

033NotOver=false;

034else do//未達到最優(yōu)匹配

035被多條線連接的網(wǎng)頁增加價格;

036end if;

037end for;

038 end while;//匹配完成

039 if(Connection[i][j]=1)then //存儲結(jié)果

040 urls.get(j).setDistinguishAsAgent(i);

041 end if;

042 return urls;//返回結(jié)果

End

2.4　統(tǒng)計存儲實驗數(shù)據(jù)模塊

統(tǒng)計存儲實驗數(shù)據(jù)模塊是在用戶點擊search stop按鈕或者爬蟲存活時間完畢后，系統(tǒng)根據(jù)相應(yīng)的鏈接訪問數(shù)、網(wǎng)頁下載數(shù)等實驗數(shù)據(jù)計算此次系統(tǒng)爬取網(wǎng)頁的準確率、召回率和重復率。系統(tǒng)完成計算后，會把相應(yīng)的計算信息顯示在面板statistics results中，然后再把這些數(shù)據(jù)存儲到數(shù)據(jù)庫中去。

3實驗結(jié)果分析

為驗證基于市場匹配算法的多Agent智能爬蟲系統(tǒng)的性能，本文以雅虎一級目錄中12個主題,如表2所示，作為測試數(shù)據(jù)進行測試，并得到了爬蟲的相關(guān)指數(shù)，如表3、表4所示。在用雅虎一級目錄中的12個主題分別測試時，界面中的參數(shù)設(shè)置如下：keyword每次在雅虎12個主題中分別取5個關(guān)鍵詞；C-Agent的最大存活時間為系統(tǒng)默認值600，單位為s；C-Agent的個數(shù)為系統(tǒng)默認值5；關(guān)鍵詞的理解度為系統(tǒng)默認值0.2；時間間隔也為系統(tǒng)默認值120。參數(shù)α和參數(shù)β為系統(tǒng)默認值，分別為5和5.0。參數(shù)δ1、參數(shù)δ2、參數(shù)δ3和參數(shù)δ4也為系統(tǒng)默認值，分別為0.5、0.10、10 s和50 kb。每次實驗時間是300 s，即5min。參數(shù)α為每個爬蟲爬取網(wǎng)頁的目標值；參數(shù)β為每個爬蟲(CAgent)初始的能力值；參數(shù)δ1為爬蟲每爬取一個網(wǎng)頁消耗的能力值；每進行一次匹配后，若沒有達到最優(yōu)匹配且有多個爬蟲欲購買此網(wǎng)頁，則此網(wǎng)頁會增加價格，增加的價格值為參數(shù)δ2；參數(shù)δ3為成功購買網(wǎng)頁的爬蟲每次獎勵的時間值；參數(shù)δ4為成功購買網(wǎng)頁的爬蟲每次獎勵的空間值。

以下表中各數(shù)據(jù)英文簡寫分別為： VC，網(wǎng)頁數(shù)量；CC，主題相關(guān)訪問數(shù)量；CR，精確率，CR=CC/VC； DTOC，下載到本地的網(wǎng)頁數(shù)量；RCR，召回率，RCR=DTOC/VC；RC，重復下載的網(wǎng)頁數(shù)量；RR，重復率，RR=RC/VC。文中，A、B和Tn代表的意義分別為：A表示使用市場匹配算法； B表示沒有使用市場匹配算法；Tn表示第n個主題，如T1表示第1個主題news。

表2　雅虎一級目錄12個主題表

在實驗中，每個主題分別取了5個關(guān)鍵詞進行實驗，得到了每個關(guān)鍵詞的準確率、召回率和重復率等實驗數(shù)據(jù)。表3和表4分別列出了主題T1、T4和T11中的5個關(guān)鍵詞的實驗數(shù)據(jù)。其中，表3的實驗數(shù)據(jù)是在使用市場匹配算法情況下進行實驗得到的，表4的實驗數(shù)據(jù)是在沒有使用市場匹配算法情況下進行實驗得到的。準確率、召回率和重復率都精確到小數(shù)點后2位。VC和VUC值相等，但表達的意義不一樣。因召回率的需要(召回率是用下載到本地的網(wǎng)頁數(shù)量/本該下載到本地的網(wǎng)頁數(shù)量)，在這里把訪問網(wǎng)頁數(shù)量VC當作本該下載到本地的網(wǎng)頁數(shù)量。

表3　雅虎一級目錄實驗數(shù)據(jù)表(A)

表4　雅虎一級目錄實驗數(shù)據(jù)表(B)

為提高數(shù)據(jù)的可信度，把每個主題中求得的5個準確率、召回率和重復率求取平均值，分別作為此主題的準確率、召回率和重復率，其結(jié)果如表5、表6所示。

表5　平均精確率、召回率、重復率表(A)

表6　平均精確率、召回率、重復率表(B)

在上述2種情況下所得的智能爬蟲爬取網(wǎng)頁的準確率、召回率和重復率的平均值分別為：CR/N(A)=85%, RCR/N(A)=80%, RR/N(A)=0.3%；CR/N(B)=76%，RCR/N(B)=72%, RR/N(B)=0.8%。

在使用市場匹配算法和不使用市場匹配算法的2種情況下，爬取網(wǎng)頁的精確率、召回率和重復率如圖6所示。由圖知，使用了市場匹配算法提高了多Agent智能爬蟲系統(tǒng)爬取網(wǎng)頁的精確率和召回率，也降低了爬取網(wǎng)頁的重復率。此實驗中，以Yahoo12個主題為測試數(shù)據(jù)得出的精確率提高了9%，召回率提高了8%，重復率降低了5%。

(a)精確率對比圖

(b)召回率對比圖

(c)重復率對比圖

圖6系統(tǒng)爬取網(wǎng)頁的精確率、召回率、重復率對比圖

4結(jié)論

基于多Agent的智能爬蟲設(shè)計與實現(xiàn)涉及多方面的理論知識、技術(shù)和方法，本文主要完成了： 1)多Agent市場匹配算法的實現(xiàn)； 2)設(shè)計基于該算法的智能爬蟲系統(tǒng)； 3)用Yahoo一級目錄12個主題作為實驗數(shù)據(jù)進行實驗，分析了爬蟲系統(tǒng)的性能。此系統(tǒng)還有一些不足之處，需要結(jié)合實際情況不斷地積累和完善。此次實驗只是比較了2種情況，將來的工作就是在網(wǎng)絡(luò)爬蟲系統(tǒng)使用的其他方法，如深度優(yōu)先[1]、模糊規(guī)則推理[8]等方法，進行精確率、召回率等對比，使實驗更加完善。

參考文獻

[1]王瑩煜.基于多Agent系統(tǒng)的主題爬蟲理解與協(xié)作研究[D].成都:西華大學,2010.

[2]Wang Yingyu,Du Yajun,Chen Shaoming.The Understanding between Two Agent Crawlers Based on Domain Ontology[C]//Proceedings of the 2009 International Conference on Computational Intelligence and Natural Computing.[S.l.]:Neural Network World,2009:47.

[3]杜亞軍.多Agent主題爬蟲協(xié)作策略的研究與分析[J].西華大學學報(自然科學版),2013,32(1):1.

[4]Ali Hesham.Self Ranking and Evaluation Approach for Focused Crawler Based on Multi-Agent System[J].The International Arab Journal of Information Technology,2008,5(2):1.

[5]Easley David,Kleinberg Jon.網(wǎng)絡(luò)、群體與市場[M].李曉明,王衛(wèi)紅,楊韞利，譯.北京:清華大學出版社,2011:175-185.

[6]姜夢雅.基于Java的多線程網(wǎng)絡(luò)爬蟲設(shè)計與實現(xiàn)[J].Microcomputer Applications,2010,26(7):21.

[7]張亮.基于HTMLParser和HttpClient的網(wǎng)絡(luò)爬蟲原理與實現(xiàn)[J].電腦編程技巧與維護,2011(20):94.

[8]徐朝軍,李藝,楊小江.基于模糊規(guī)則推理的主題資源搜索系統(tǒng)設(shè)計與實現(xiàn)[J].情報學報,2009,28(6):815.

[9]林海霞,司海峰,張微微.基于Java技術(shù)的主題網(wǎng)絡(luò)爬蟲的研究與實現(xiàn)[J].Microcomputer Applications,2009,25(2):56.

[10]羅剛,王振東.自己動手寫網(wǎng)絡(luò)爬蟲[M].北京:清華大學出版社,2010:4-64.

[11]羅林波.基于內(nèi)容和鏈接的主題爬蟲研究與設(shè)計[D].海口:海南大學,2010.

[12]張紅云.基于頁面分析的主題網(wǎng)絡(luò)爬蟲的研究[D].武漢:武漢理工大學,2010.

(編校：饒莉)

System of Intelligent Crawler Based on Multi-Agent

LIU Jia，DU Yajun*

(SchoolofComputerandSoftwareEngineering,XihuaUniversity,Chengdu610039China)

Abstract:With the number of network texts, graphics videos,audios in the online world is growing rapidly, the web crawler becomes more and more powerless, mainly showed in the lower precise rate, lower recall rate and higher repetition rate while crawling web pages. In order to address the problem mentioned above, a multi-Agent intelligent crawler system using market-matching algorithm is proposed by combining market-matching fundamentals and characteristics of web crawler. This paper firstly analyzed and designed every important part of multi-Agent intelligent crawler system in detail based on market-matching algorithm. Then the precise rate, recall rate and repetition rate of crawling web pages were analyzed by using the directory of Yahoo as test data. Experimental results show that the multi-Agent intelligent crawler system can improve the performance of the web crawlers compared to the system without using market-matching algorithm, specifically manifest in the precision rate and recall rate increased by 9%,8% respectively, while its repetition rate decreased by 5%.

Keywords:market-matching algorithm; multi-Agent; intelligent crawler

doi:10.3969/j.issn.1673-159X.2016.01.014

中圖分類號：TP393.09

文獻標志碼：A

文章編號：1673-159X(2016)01-0067-06

*通信作者：杜亞軍( 1967—) ，男，教授，博士，碩士生導師，主要研究方向為網(wǎng)上信息挖掘與搜索引擎、計算機軟件開發(fā)技術(shù)。E-mail：duyajun@aliyun.com

基金項目：國家自然科學基金(61271413,61472329)。

收稿日期：2015-07-16

·計算機軟件理論、技術(shù)與應(yīng)用·