胡　偉, 吳海濤

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院,上海 200234)

?

Nutch中網(wǎng)頁更新預(yù)測研究與優(yōu)化

胡偉, 吳海濤

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院,上海 200234)

Nutch的網(wǎng)頁更新預(yù)測方法采用的是鄰比法,相關(guān)更新參數(shù)需要人為設(shè)定,不能自適應(yīng)調(diào)整,無法應(yīng)對海量網(wǎng)頁更新的差異性.為解決這個問題,提出動態(tài)選擇策略對Nutch的網(wǎng)頁更新預(yù)測方法進(jìn)行改進(jìn).該策略在網(wǎng)頁更新歷史數(shù)據(jù)不足時,通過基于MapReduce的DBSCAN聚類算法來減少爬蟲系統(tǒng)抓取網(wǎng)頁數(shù)量,將樣本網(wǎng)頁的更新周期作為所屬類其他網(wǎng)頁的更新周期;在網(wǎng)頁更新歷史數(shù)據(jù)較多時,通過對網(wǎng)頁更新歷史數(shù)據(jù)進(jìn)行泊松過程建模,較準(zhǔn)確地預(yù)測每個網(wǎng)頁的更新周期.最后在Hadoop分布式平臺下對改進(jìn)該策略測試.實驗結(jié)果表明,優(yōu)化后的網(wǎng)頁更新預(yù)測方法表現(xiàn)更優(yōu).

Nutch; 網(wǎng)頁更新預(yù)測; 基于密度聚類算法; 泊松過程; 分布式編程

0　引　言

Nutch是一個開源Java實現(xiàn)的搜索引擎,其分布式運行模式是基于Hadoop分布式平臺[1],能夠很好地支持海量數(shù)據(jù)的計算.它提供了運行搜索引擎所需的全部工具,包括Web爬蟲、索引和查詢[2].這里,將只關(guān)注爬蟲模塊.

但是,Nutch默認(rèn)的網(wǎng)頁更新預(yù)測鄰比法不能靈活、自適應(yīng)設(shè)定參數(shù),且在網(wǎng)頁更新歷史數(shù)據(jù)不足的早期,需要較頻繁訪問每個網(wǎng)頁,資源消耗大.于是,本文作者提出動態(tài)選擇策略,在網(wǎng)頁更新歷史數(shù)據(jù)不足時,選擇基于MapReduce的DBSCAN聚類算法,對網(wǎng)頁進(jìn)行分類,再抽樣,Nutch只抓取樣本網(wǎng)頁,樣本的更新周期即是所屬分類內(nèi)的所有網(wǎng)頁的更新周期,減少了資源消耗;在數(shù)據(jù)充足時,對網(wǎng)頁的歷史數(shù)據(jù)進(jìn)行泊松過程建模,預(yù)測網(wǎng)頁更新周期.實驗表明,動態(tài)選擇策略能夠更高效、準(zhǔn)確地預(yù)測網(wǎng)頁更新周期.

1　Nutch及Hadoop介紹

1.1Nutch

Nutch有兩種運行模式:分布式(deploy)和單機(jī)(local),本文作者主要實現(xiàn)分布式的運行模式,因此只介紹Nutch分布式模式.分布式模式采用分布式文件系統(tǒng)(HDFS)作為存儲文件系統(tǒng),并利用MapReduce實現(xiàn)爬蟲抓取網(wǎng)頁的各個環(huán)節(jié),從而使Nutch能夠抓取、存儲海量網(wǎng)頁.其系統(tǒng)構(gòu)成如圖1所示.

1.2Hadoop分布式系統(tǒng)

Hadoop是一個能夠?qū)Υ罅繑?shù)據(jù)進(jìn)行分布式處理的軟件框架.它的分布式架構(gòu)底層細(xì)節(jié)對用戶是透明的,用戶可以在不了解分布式系統(tǒng)底層細(xì)節(jié)的情況下進(jìn)行程序開發(fā),該設(shè)計使Hadoop的易用性較好,使其成為現(xiàn)今分布式系統(tǒng)的主流之一.它核心設(shè)計有:HDFS和MapReduce.HDFS為海量的數(shù)據(jù)提供分布式存儲,MapReduce為海量的數(shù)據(jù)提供并行計算.

圖1　Nutch分布式文件系統(tǒng)架構(gòu)

1.2.1分布式計算框架MapReduce

MapReduce是一個易用的軟件框架,用它編寫的應(yīng)用程序能夠在上千節(jié)點的集群上可靠、容錯地并行處理大數(shù)據(jù)集.一個MapReduce作業(yè)一般會將輸入數(shù)據(jù)拆分為獨立的數(shù)據(jù)塊,交由Map任務(wù)并行處理,框架會排序Map任務(wù)的輸出,并將結(jié)果傳輸給Reduce任務(wù).框架負(fù)責(zé)任務(wù)的調(diào)度、監(jiān)控和重新執(zhí)行失敗的任務(wù),因此程序員通常只要實現(xiàn)Map方法和Reduce方法就可以實現(xiàn)分布式并行編程.

圖2　MapReduce程序數(shù)據(jù)變化模型

一個MapReduce作業(yè)分為兩個階段:Map階段和Reduce階段.這兩個階段分別用Map任務(wù)和Reduce任務(wù)表示.Map任務(wù)接收一個形式的輸入,然后輸出的中間結(jié)果,Shuffle過程會將相同key值的value集合到一起傳輸給Reduce任務(wù),Shuffle過程是指數(shù)據(jù)從Map方法輸出到Reduce方法輸入的這段過程,Reduce任務(wù)接收到是這樣的數(shù)據(jù),然后對value集合進(jìn)行處理輸出結(jié)果,結(jié)果形式為.過程如圖2所示.

1.2.2分布式文件系統(tǒng)

HDFS是Hadoop主要應(yīng)用的一個分布式文件系統(tǒng),主要用來處理存儲超大文件和基于流數(shù)據(jù)模式訪問.HDFS隱藏下層負(fù)載均衡、冗余復(fù)制等細(xì)節(jié),對上層程序提供一個統(tǒng)一的文件系統(tǒng)API接口,實現(xiàn)細(xì)節(jié)對用戶透明.可以部署在廉價的機(jī)器集群上,不需要專業(yè)的高性能機(jī)器.

2　Nutch網(wǎng)頁更新預(yù)測優(yōu)化

2.1Nutch網(wǎng)頁更新預(yù)測

稱Nutch網(wǎng)頁更新預(yù)測方法采用的是鄰比法.對第一次采集的網(wǎng)頁,鄰比法設(shè)置其更新時間為某個值.如果該網(wǎng)頁在這個時間內(nèi)更新了,則更新時間縮小一定值;如果沒有更新,則更新時間增加一定值[3].

稱Nutch網(wǎng)頁更新機(jī)制為Recrawl機(jī)制,它提供了一個adaptivefetchscheduleclass來管理爬蟲的重新抓取,工作流程如下:

(1)Generate命令在CrawlDB數(shù)據(jù)庫中查找已到回訪周期的網(wǎng)頁,將其寫入segments目錄;

(2)Fetch命令抓取segments目錄中的所有URL;

(3)Update命令將抓取的結(jié)果更新到CrawlDB,已被抓取的網(wǎng)頁更新其抓取時間和下次抓取時間,新的URL標(biāo)記為未抓取;

(4) 下次抓取時間:當(dāng)新的URL加入到CrawlDB,其回訪周期被設(shè)置為默認(rèn)的間隔時間(db.fetch.interval.default).當(dāng)URL被抓取后,判斷其與之前內(nèi)容是否相同,如果不同,回訪周期減小指定速率(db.fetch.schedule.adaptive.dec_rate),否則,回訪周期增大指定速率(db.fetch.schedule.adaptive.inc_rate).但不管增大還是減小,都不會超出最大間隔時間和最小間隔時間.

Recrawl參數(shù)如表1所示.

表1　Nutch Recrawl參數(shù)

Recrawl機(jī)制的缺點:

(1) 相關(guān)參數(shù)需要人為設(shè)定,無法自適應(yīng)調(diào)整;

(2) 對所有網(wǎng)頁進(jìn)行相同的參數(shù)設(shè)定,無法適應(yīng)海量網(wǎng)頁更新的多樣性;

(3) 在網(wǎng)頁歷史數(shù)據(jù)不足的早期,需要較頻繁地抓取每個網(wǎng)頁,資源消耗大.

2.2網(wǎng)頁更新預(yù)測優(yōu)化

2.2.1動態(tài)選擇策略

互聯(lián)網(wǎng)上的網(wǎng)頁新建、更新和刪除時刻在發(fā)生,且網(wǎng)頁在本地存儲的歷史數(shù)據(jù)不盡相同,很難用一種更新策略預(yù)測所有的網(wǎng)頁.文獻(xiàn)[4]通過大量的實驗發(fā)現(xiàn),一個網(wǎng)頁更新的前16輪中,聚類抽樣策略比歷史參考策略表現(xiàn)更好;在16輪之后,則相反,歷史參考策略效果更優(yōu).因此,提出動態(tài)選擇策略,在一個網(wǎng)頁的歷史數(shù)據(jù)不足的情況下,選擇聚類抽樣策略;相反,則選擇歷史參考策略.

(1) 歷史參考策略.歷史參考策略假設(shè)網(wǎng)頁更新規(guī)律延續(xù)歷史更新規(guī)律,即某個網(wǎng)頁將來的更新周期可以根據(jù)其歷史更新周期預(yù)測[5].

采用泊松過程對網(wǎng)頁更新情況進(jìn)行建模,在歷史數(shù)據(jù)較充足時,該方法能夠較準(zhǔn)確地預(yù)測網(wǎng)頁的更新周期.

(2) 聚類抽樣策略.聚類抽樣策略不需要網(wǎng)頁的歷史數(shù)據(jù)來預(yù)測將來的更新時間.它認(rèn)為:網(wǎng)頁有一些特征,根據(jù)這些特征可以預(yù)測其更新頻率,擁有相似特征的網(wǎng)頁,其更新頻率也相似.因此,采用聚類算法將網(wǎng)頁分類,為獲取一個分類的的更新周期,只需從這個分類抽樣,將這些抽樣網(wǎng)頁的更新周期作為這個分類內(nèi)所有網(wǎng)頁的更新周期[5].

該策略能夠有效減少Nutch為獲得網(wǎng)頁的更新數(shù)據(jù)所要重復(fù)采集的網(wǎng)頁數(shù)量.

采用基于MapReduce的DBSCAN聚類算法,改進(jìn)的DBSCAN能夠很好地支持海量網(wǎng)頁的并行分類.

動態(tài)選擇策略具體工作流程如下:

(1) 對一個網(wǎng)頁,在它未更新16次之前,選擇聚類抽樣策略.

① 系統(tǒng)記錄每個網(wǎng)頁的更新次數(shù)M,然后將M小于等于16的網(wǎng)頁使用基于MapReduce的DBSCAN聚類算法分類;

② 從每個分類中抽樣,盡量選擇靠近類中心的網(wǎng)頁,因為這些網(wǎng)頁類特征更明顯;

③ 采用鄰近法對樣本網(wǎng)頁進(jìn)行采集,其初始更新頻率、最小間隔和最大間隔根據(jù)網(wǎng)頁類型(網(wǎng)站首頁、目錄型網(wǎng)頁、其他網(wǎng)頁)設(shè)置,采用文獻(xiàn)[6]的實驗數(shù)據(jù),單位為d,具體如下:

④ 將一個分類的所有樣本網(wǎng)頁的更新周期平均值作為該分類的其他網(wǎng)頁的更新周期.

(2) 當(dāng)更新次數(shù)超過16次后,選擇歷史參考策略.

2.2.2DBSCAN聚類算法

DBSCAN(Density-BasedSpatialClusteringofApplicationswithNoise)算法是一種基于密度的聚類算法,該算法的目的在于過濾低密度區(qū)域,發(fā)現(xiàn)稠密度樣本點,跟傳統(tǒng)的基于層次聚類和劃分聚類的凸形聚類簇不同,該算法可以發(fā)現(xiàn)任意形狀的聚類簇,與傳統(tǒng)的算法相比,具有如下優(yōu)點:

(1) 與劃分聚類算法,如K-means比較,不必輸入要劃分的聚類個數(shù).

(2) 可以發(fā)現(xiàn)任意形狀的簇類.

(3) 可以過濾噪聲點.

互聯(lián)網(wǎng)上網(wǎng)頁數(shù)以億計,特征也各不相同,很難在分類前指定聚類個數(shù),且分布不規(guī)則,DBSCAN算法很好地解決了這些難點,因此選擇該算法作為網(wǎng)頁的聚類算法.

2.2.2.1基于MapReduce的DBSCAN算法

DBSCAN算法本身也有不足.它直接對整個數(shù)據(jù)集進(jìn)行操作且聚類時使用了一個全局性的表征密度的參數(shù),因此需要大量內(nèi)存支持和I/O開銷,效率低且受限單機(jī)硬件資源,特別在對海量數(shù)據(jù)進(jìn)行聚類時,不足尤為突出.因此提出基于MapReduce的DBSCAN算法,充分利用集群的硬件資源來運行DBSCAN算法,非常適合進(jìn)行海量網(wǎng)頁的聚類.

基于MapReduce的DBSCAN算法對網(wǎng)頁進(jìn)行聚類,具體流程如下:

(1) 數(shù)據(jù)預(yù)處理:特征選擇和抽取,即從網(wǎng)頁中解析出和網(wǎng)頁變化模式相關(guān)的特征.已經(jīng)有一些研究發(fā)現(xiàn)網(wǎng)頁的一些特征和網(wǎng)頁的變化周期有關(guān).Douglis等[7]指出頻繁更新的網(wǎng)頁大小較大并且有更多的圖片.Fetterly等[8]發(fā)現(xiàn)網(wǎng)頁的頂級域名和網(wǎng)頁變化模式相關(guān).文獻(xiàn)[4]中特征向量包含非標(biāo)記語言詞的數(shù)量、網(wǎng)頁的鏈出和鏈入的鏈接數(shù)量、圖片的數(shù)量、URL深度和網(wǎng)頁文件大小.作者采用文獻(xiàn)[4]的方法.

(2) 數(shù)據(jù)標(biāo)準(zhǔn)化:各特征值的單位不同,數(shù)量級也不一樣,因此要進(jìn)行數(shù)據(jù)標(biāo)準(zhǔn)化.采用的標(biāo)準(zhǔn)化方法是數(shù)據(jù)集中的各項數(shù)據(jù)減去數(shù)據(jù)集的均值再除以數(shù)據(jù)集的標(biāo)準(zhǔn)差.

(3) 聚類挖掘:對這些用特征向量表示的網(wǎng)頁,采用基于MapReduce的DBSCAN聚類算法進(jìn)行分類.其算法描述如下:

① map函數(shù):

Input:網(wǎng)頁集,key為分區(qū)編號,value為該分區(qū)中所有網(wǎng)頁對象的集合

Output:< key2,value2>鍵值對,key2為簇編號Cid,value2是邊界簇標(biāo)識BCid、簇中所有對象和中心o的組合

map(key,value)

{

初始化Cid為1.

forvalue中的每個網(wǎng)頁對象a

{

ifa為未標(biāo)記類別的對象

{

ifa不是核心對象(調(diào)用函數(shù)計算a領(lǐng)域內(nèi)對象數(shù)目是否不小于minPts,判斷a的對象類型)

標(biāo)記a為噪聲

else

{

標(biāo)記a為類別Cid;

標(biāo)記所有從a直接密度可達(dá)的未標(biāo)記對象為Cid,并存入隊列L中;

標(biāo)記所有從a直接密度可達(dá)的標(biāo)記為噪聲的對象為Cid,并標(biāo)記其為邊界對象;WhileL不為空

{

按FIFO取對象b;

ifb是核心對象

標(biāo)記所有從b直接密度可達(dá)的標(biāo)記為噪聲的對象為Cid;

標(biāo)記所有從b直接密度可達(dá)的未標(biāo)記對象為Cid,并存入隊列L中;

}

}

}

}

類別標(biāo)記Cid+1;

}

② reduce函數(shù):

Input:,即map函數(shù)的輸出

Output:,key3、value3的含義分別與key2、value2相同

reduce(key2,value2)

{

ifkey2=0(即Cid=0,該對象為噪聲)

{

ifBCid=0(該對象不是邊界噪聲)

刪除該對象;

else

調(diào)用函數(shù),對邊界處理;

}

else

{

ifBCid=0(不是邊界簇)

輸出簇所有信息;

else

調(diào)用函數(shù),對邊界處理;

}

處理下一個;

}

2.2.3網(wǎng)頁泊松過程

斯坦福大學(xué)的Cho等和貝爾實驗室的Coffman等分別進(jìn)行了大量網(wǎng)頁更新實驗,都發(fā)現(xiàn)每個獨立網(wǎng)頁的更新過程可以用泊松過程模擬,因此網(wǎng)頁更新規(guī)律近似泊松過程[9-10].

在當(dāng)網(wǎng)頁更新次數(shù)超過16次后,對網(wǎng)頁的歷史更新數(shù)據(jù)進(jìn)行泊松過程建模來預(yù)測網(wǎng)頁的更新周期.

泊松過程假設(shè)從某個時刻開始,設(shè)X(t)表示某個網(wǎng)頁到t時刻的變化次數(shù),λ表示網(wǎng)頁變化頻率,那么根據(jù)泊松分布的定義得出:

(1)

假設(shè)某個網(wǎng)頁的下次變化是開始t,則由式(1)可以得到t的概率密度函數(shù):

(2)

假設(shè)λi是某個網(wǎng)頁的平均變化頻率,那么該網(wǎng)頁在區(qū)間T=(0,t)發(fā)生變化的概率如下:

(3)

那么,網(wǎng)頁在區(qū)間T內(nèi)的平均時新性和平均過時度分別為:

(4)

(5)

以上方法是對網(wǎng)頁的更新過程進(jìn)行數(shù)學(xué)模型建模,同時給出了網(wǎng)頁的平均時新性和平均過時度2個指標(biāo)來評價爬蟲系統(tǒng)的本地網(wǎng)頁質(zhì)量.

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

3.1實驗環(huán)境

3.1.1硬件環(huán)境

由于實驗室里物理服務(wù)器有限,將分布式平臺部署在云主機(jī)上.在盛大云上申請了9臺云主機(jī)用來部署Hadoop分布式平臺,云主機(jī)配置如表2所示.

表2　云主機(jī)配置信息

3.1.2系統(tǒng)部署

Hadoop分布式平臺采用的是高可用(HA)方式,該方式有兩個master節(jié)點,一個處于Active狀態(tài),另一個則處在Standby狀態(tài),有效避免了NameNode單節(jié)點故障,提高了集群的可靠性.每個master節(jié)點包括一個NameNode和一個ResourceManager,在實際應(yīng)用中,可以將NameNode和ResourceManager部署在不同的節(jié)點上.再用4臺節(jié)點同時部署DateNode和NodeManager,其他3個節(jié)點部署Zookeeper.

集群部署圖如圖3所示.

圖3　Hadoop集群部署圖

設(shè)置兩個主節(jié)點的主機(jī)名分別為master、master2,DataNode節(jié)點主機(jī)名分別為slave1、slave2、slave3、slave4,Zookeeper節(jié)點主機(jī)名分別為zookeeper1、zookeeper2、zookeeper3.設(shè)置每臺服務(wù)器的/etc/hosts,配置IP地址和主機(jī)名的映射關(guān)系,內(nèi)容一樣.關(guān)閉每個節(jié)點的防火墻.

下面詳細(xì)介紹Hadoop分布式平臺和Nutch的具體部署.

3.1.2.1Hadoop部署

安裝步驟[11]如下:

(1) 解壓縮并安裝JDK1.6,配置Java環(huán)境變量;

(2) 配置免密碼登陸SSH,使主節(jié)點訪問其他節(jié)點無需驗證密碼;

(3) 安裝hadoop-2.5.1:tar-zxvfhadoop-2.5.1.tar.gz;

(4) 修改MYMHADOOP_HOME/etc/hadoop目錄下hadoo-env.sh、core-site.xml、hdfs-site.xml、mapred-site.xml、yarn-site.xml、slaves這六個文件;

(5) 啟動Hadoop.首先在主節(jié)點執(zhí)行bin/hdfsnamenode-format,格式化HDFS,再執(zhí)行sbin/start-dfs.sh和sbin/start-yarn.sh,啟動Hadoop集群.如果集群運行正確,可在瀏覽器中輸入http://master:50070查看分布式文件系統(tǒng)的狀況,如圖4、5所示.

圖4　Hadoop平臺50070端口Web界面-1

圖5　Hadoop平臺50070端口Web界面-2

3.1.2.2部署Nutch

(1) 安裝Ant:tar-zxvfapache-ant-1.9.2-bin.tar.gz;

(2) 在Nutch解壓后的apache-nutch-1.7根目錄下運行ant進(jìn)行編譯,即Nutch安裝成功;

(3) 配置conf/nutch-site.xml.

3.2網(wǎng)頁更新預(yù)測實驗

3.2.1實驗樣本獲取

采用文獻(xiàn)[12]的采樣實驗方法,選取150個教育網(wǎng)站點作為種子URL來進(jìn)行樣本抓取實驗.抓取頻率設(shè)置為1d.首先抓取這150個URL,利用網(wǎng)頁中的超鏈接發(fā)現(xiàn)更多的網(wǎng)頁,完成初次抓取;然后從抓取的網(wǎng)頁中選取1×1.05個作為樣本網(wǎng)頁.每天晚上11點鐘抓取一遍,和本地對應(yīng)網(wǎng)頁比較,記錄變化情況;最后分析網(wǎng)頁的更新情況及類型.

實驗詳細(xì)流程為:

(1) 以150個種子URL開始,按照深度優(yōu)先遍歷方式抓取8層,得到起始網(wǎng)頁集合.隨機(jī)選擇其中的1×1.05個網(wǎng)頁作為實驗樣本網(wǎng)頁.

(2) 每天定時抓取1×1.05樣本網(wǎng)頁.

(3) 如果網(wǎng)頁已不存在,則標(biāo)記該網(wǎng)頁無效.

(4) 如果網(wǎng)頁抓取成功,對比本地網(wǎng)頁未變化,則該網(wǎng)頁的抓取次數(shù)加1,修改最近抓取時間.

(5) 如果網(wǎng)頁抓取成功,對比本地網(wǎng)頁發(fā)生了變化,那么更新本地對應(yīng)網(wǎng)頁,網(wǎng)頁抓取次數(shù)加1,修改網(wǎng)頁最近抓取時間和最近更新時間.

(6) 執(zhí)行步驟(2).

按照上面的流程,可以得到樣本網(wǎng)頁的變化軌跡.

爬蟲一共進(jìn)行了35次的抓取樣本任務(wù),時間從2014年12月16日至2015年1月19日.抓取的開始時間設(shè)定為每晚11∶00,抓取時長大約1h.

在整個抓取過程中,網(wǎng)頁內(nèi)容發(fā)生變化的數(shù)量為15 073個,大約占樣本網(wǎng)頁總量的15.06%.由此可知,互聯(lián)網(wǎng)中在1個月內(nèi)發(fā)生變化的網(wǎng)頁占網(wǎng)頁總量的比例較小,大多數(shù)網(wǎng)頁在同時長內(nèi)是不會更新的.這一比例比第19次中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計報告顯示的1個月內(nèi)更新的網(wǎng)頁約占33.8%小很多,其原因是選取的150個URL是教育網(wǎng)點,教育類網(wǎng)站的更新頻率比常見的新聞網(wǎng)站、門戶網(wǎng)站和電商網(wǎng)站等低很多,因此統(tǒng)計數(shù)據(jù)會有差別.

3.2.2網(wǎng)頁更新評測

采用文獻(xiàn)[13]中的評測方法對網(wǎng)頁更新預(yù)測效果進(jìn)行評測,該方法主要有3個評測項:預(yù)測時間偏移率μ、預(yù)測命中率λ和預(yù)測的效率η.

(1) 預(yù)測時間偏移率μ:表示網(wǎng)頁更新預(yù)測算法的敏感度,即網(wǎng)頁變化多長時間后算法可以更正.

(6)

(2) 預(yù)測命中率λ:表示預(yù)測算法的效果,即有多少次網(wǎng)頁變化被算法預(yù)測到.

(7)

(3) 預(yù)測的效率η:表示預(yù)測算法的性能,即每抓取一個變化的網(wǎng)頁時需要抓取多少未變化的網(wǎng)頁.

(8)

采用上面3個參數(shù),在樣本網(wǎng)頁集合上對比Nutch默認(rèn)的鄰比法和動態(tài)選擇策略2個算法的差別.因本地網(wǎng)頁庫中網(wǎng)頁的歷史數(shù)據(jù)較少,只取網(wǎng)頁的前3次變化平均值,對于少于3次變化的網(wǎng)頁,取所有變化次數(shù)的平均值.結(jié)果如表3所示.

表3　預(yù)測算法效率對比

從表3可以總結(jié)出,動態(tài)選擇策略的預(yù)測效果比Nutch默認(rèn)的鄰比法好.但是在文獻(xiàn)[4]的實驗中,基于聚類更新策略的預(yù)測效果比實驗效果更好.

其主要原因:選擇的網(wǎng)站都是教育網(wǎng)站,這些網(wǎng)站的網(wǎng)頁多樣性遠(yuǎn)沒有整個互聯(lián)網(wǎng)中的網(wǎng)頁多樣性復(fù)雜,且更新周期長,因此動態(tài)選擇策略聚類后的種類較少,與根據(jù)網(wǎng)頁類型分類差別不大,這也造成優(yōu)化后的效果不明顯.

實驗不足:因時間有限,無法做長時間網(wǎng)頁更新跟蹤實驗,本地網(wǎng)頁庫中網(wǎng)頁變化的歷史數(shù)據(jù)較少,動態(tài)選擇策略中的泊松算法沒有足夠的歷史數(shù)據(jù)來預(yù)測網(wǎng)頁的更新情況.

4　結(jié)束語

主要分析了Nutch的網(wǎng)頁更新預(yù)測,針對該方法的不足進(jìn)行優(yōu)化,提出了動態(tài)選擇策略,該策略通過基于MapReduce的DBSCAN算法來避免Nutch抓取本地庫中全部網(wǎng)頁;通過對網(wǎng)頁更新歷史數(shù)據(jù)進(jìn)行泊松過程建模較準(zhǔn)確地預(yù)測每個網(wǎng)頁的更新周期.為了測試優(yōu)化后的效果,將優(yōu)化后的Nutch與Hadoop平臺結(jié)合進(jìn)行實驗.實驗結(jié)果表明,該預(yù)測策略提高了Nutch的爬蟲預(yù)測網(wǎng)頁更新的效果.

[1]YuanW,XueAR,ZhouXM.Researchonimprovementofdistributedcrawlerbasedonnutch[J].WirelessCommunicationTechnology,2014,23(3):44-47.

[2]MoreiraJE,MichaelMM,SilvaDD,etal.Scalabilityofthenutchsearchengine[C]//ACM.Proceedingsofthe21stAnnualInternationalConferenceonSupercomputing,NewYork:ACM,2007.

[3]RisvikKM,MichelsenR.Searchenginesandwebdynamics[J].ComputerNetworks,2002,39(3):289-302.

[4]TanQZ,ZhuangZM,MitraP,etal.Efficientlydetectingwebpageupdatesusingsamples[J].LectureNotesinComputerScience,2007,4607:285-300.

[5]ZhangJL.Thisisasearchengine[M].Beijing:PublishingHouseofElectronicsIndustry,2012.

[6]WuCY.Researchandimplementationofinformationcrawlingsystembasedonnutch[D].Guangzhou:SouthChinaUniversityofTechnology,2010.

[7]DouglisF,FeldmannA,KrishnamurthyB,etal.Rateofchangeandothermetrics:alivestudyoftheWorldWideWeb[C]//USENIX.USENIXSymposiumonInternetTechnologiesandSystems,Monterey:USENIX,1997.

[8]FetterlyD,ManasseM,NajorkM,etal.Alarge-scalestudyoftheevolutionofWebpages[J].Software-PracticeandExperience,2004,2(34):213-213.

[9]ChoJH,Garcia-MolinaH.Theevolutionofthewebandimplicationsforanincrementalcrawler[C]//ACM.Proceedingsofthe26thInternationalConferenceonVeryLargeDataBases26th,SanFrancisco:MorganKaufmannPublisher,2000.

[10]CoffmanJREG,ZhenL,RichardR.Weber.OptimalrobotschedulingforWebsearchengines[J].JournalofScheduling,1998,1(1):15-29.

[11]LuJH.Hadoopinaction[M].Beijing:ChinaMachinePress,2012.

[12]NtoulasA,ChoJH,OlstonC.What′snewontheweb:theevolutionofthewebfromasearchengineperspective[C]//ACM.Proceedingsofthe13thinternationalconferenceonWorldWideWeb,ACM:NewYork,2004.

[13]WangDH.Thedesignandimplementationoftiwangincrementalcrawler[D].Beijing:PekingUniversity,2006.

(責(zé)任編輯：包震宇)

Research and optimization of page updated forecast on Nutch

HU Wei, WU Haitao

(CollegeofInformation,MechanicalandElectricalEngineering,ShanghaiNormalUniversity,Shanghai200236,China)

WebpageupdatedpredictionmethodofNutchisanadjacentmethodanditsrelevantupdateparametersneedtobesetartificially,notadaptivelyadjustable,andunabletocopewiththedifferencesofmassivewebpageupdates.Toaddressthisproblem,thispaperputsforwarddynamicselectionstrategytoimprovethemethodofNutchwebpageupdatedprediction.Whenthehistoricalupdatedwebpagedataareinsufficient,thestrategyusesDBSCANclusteringalgorithmbasedonMapReducetoreducethenumberofthepagesofthecrawlersystemcrawling,theupdatecycleofthesamplewebpagesisusedasupdatecycleofotherpageswhichareinthesamecategory.Whenthehistoricalupdatedwebpagedataareenough,thedataareusedtomodelwiththePoissonProcess,whichcanmoreaccuratelypredicteachwebpageupdatecycle.FinallytheimprovingstrategyistestedintheHadoopdistributedplatform.Theexperimentalresultsshowthattheperformanceofoptimizedwebpageupdatedpredictionmethodisbetter.

Nutch;webpageupdatedprediction;DBSCAN;poissonprocess;mapReduce

10.3969/J.ISSN.1000-5137.2016.04.010

2015-03-27

吳海濤,中國上海市徐匯區(qū)桂林路100號,上海師范大學(xué)信息與機(jī)電工程學(xué)院,郵編:200234,E-mail:ht.wu@163.com

TP311.52

A

1000-5137(2016)04-0448-10