基于統(tǒng)計(jì)學(xué)的Web論壇增量更新策略研究

馮 凱 陳 軍 王 鵑 王 勇

1(武漢大學(xué)國(guó)家多媒體軟件工程技術(shù)研究中心 湖北 武漢 430072)2(武漢大學(xué)計(jì)算機(jī)學(xué)院 湖北 武漢 430072)3(武漢大學(xué)空天信息安全與可信計(jì)算教育部重點(diǎn)實(shí)驗(yàn)室 湖北 武漢 430072)

基于統(tǒng)計(jì)學(xué)的Web論壇增量更新策略研究

馮 凱1,2*陳 軍1,2王 鵑2，3王 勇2，3

1(武漢大學(xué)國(guó)家多媒體軟件工程技術(shù)研究中心 湖北 武漢 430072)2(武漢大學(xué)計(jì)算機(jī)學(xué)院 湖北 武漢 430072)3(武漢大學(xué)空天信息安全與可信計(jì)算教育部重點(diǎn)實(shí)驗(yàn)室 湖北 武漢 430072)

傳統(tǒng)預(yù)測(cè)網(wǎng)頁(yè)變化的模型將一種規(guī)律應(yīng)用到所有網(wǎng)頁(yè)之上，沒(méi)有考慮各頁(yè)面之間的區(qū)別，針對(duì)網(wǎng)絡(luò)論壇索引頁(yè)面提出了一種基于統(tǒng)計(jì)學(xué)規(guī)律的增量更新策略模型。通過(guò)相關(guān)論壇版塊的索引頁(yè)面進(jìn)行數(shù)據(jù)的采集，觀察并證明其變化大致呈現(xiàn)以日為周期的規(guī)律性變化，一日之內(nèi)的變化曲線(xiàn)與人們的生活規(guī)律相吻合。然后采用最小二乘法多項(xiàng)式曲線(xiàn)擬合對(duì)其進(jìn)行數(shù)學(xué)建模，得到合適的數(shù)學(xué)模型，并將其應(yīng)用在索引頁(yè)面的增量更新之上，從而可以準(zhǔn)確預(yù)測(cè)索引頁(yè)面下一次更新的時(shí)間間隔。實(shí)驗(yàn)結(jié)果表明，該模型在10%誤差范圍內(nèi)，預(yù)測(cè)的準(zhǔn)確率為93.9%。

增量更新 網(wǎng)頁(yè)變化 統(tǒng)計(jì)學(xué) 數(shù)學(xué)建模

0 引 言

網(wǎng)絡(luò)爬蟲(chóng)是用來(lái)從互聯(lián)網(wǎng)上收集網(wǎng)頁(yè)的程序，一般用于搜索引擎上?；ヂ?lián)網(wǎng)上網(wǎng)頁(yè)千變?nèi)f化，更新速度快，所以網(wǎng)絡(luò)爬蟲(chóng)需要獲取到最新的頁(yè)面來(lái)替換舊的頁(yè)面, 更新本地存儲(chǔ)。傳統(tǒng)的方法是周期性訪(fǎng)問(wèn)網(wǎng)頁(yè)實(shí)現(xiàn)更新，其需要重新下載所有已經(jīng)下載的網(wǎng)頁(yè)，而不管該頁(yè)面是否真的發(fā)生變化。該方法不僅浪費(fèi)爬蟲(chóng)系統(tǒng)資源，還會(huì)影響網(wǎng)絡(luò)帶寬，也會(huì)耗費(fèi)一定的時(shí)間。由此，產(chǎn)生了對(duì)爬蟲(chóng)系統(tǒng)增量更新策略的研究[1]。爬蟲(chóng)系統(tǒng)增量更新主要是指只更新真正發(fā)生改變的頁(yè)面，而未改變的頁(yè)面不做處理。毫無(wú)疑問(wèn)，該方法大大節(jié)約了系統(tǒng)資源和網(wǎng)絡(luò)資源，提高了爬蟲(chóng)效率。該方法的難點(diǎn)就在于爬蟲(chóng)系統(tǒng)本身如何去判斷一個(gè)頁(yè)面是否發(fā)生了變化或者其變化程度為多少。

當(dāng)前的研究主要有兩種方法：一是通過(guò)實(shí)驗(yàn)手段對(duì)Web中的數(shù)據(jù)進(jìn)行采樣，研究樣本的變化規(guī)律，從而估計(jì)整個(gè)Web的變化規(guī)律[1]；二是事先從理論上建立數(shù)學(xué)模型，并用實(shí)驗(yàn)對(duì)模型進(jìn)行驗(yàn)證，得出模型參數(shù)，最后利用模型對(duì)頁(yè)面變化進(jìn)行預(yù)測(cè)[9]。他們的研究適用于一般性的網(wǎng)站，并且將得到的網(wǎng)頁(yè)更新頻繁度應(yīng)用到對(duì)應(yīng)網(wǎng)頁(yè)的任何時(shí)刻。但是我們相信不同的爬蟲(chóng)策略應(yīng)該適用于不同特點(diǎn)和類(lèi)型的網(wǎng)站，同一網(wǎng)頁(yè)在不同時(shí)刻的更新頻繁度也應(yīng)該不同。本文的工作重點(diǎn)在于對(duì)網(wǎng)絡(luò)論壇增量更新策略的研究。

作為UCC(User-Created Content)的典型代表，網(wǎng)絡(luò)論壇在搜索引擎、數(shù)據(jù)挖掘等領(lǐng)域具有越來(lái)越重要的作用。沈文勤等[14]利用HTTP的head請(qǐng)求獲取頁(yè)面的元信息，從而避免了整個(gè)文件的傳輸。孟慶浩等[15]提出利用網(wǎng)頁(yè)的Hash摘要來(lái)判斷網(wǎng)頁(yè)是否發(fā)生了變化。代鵬等[16]提出使用Simhash算法和漢明距離計(jì)算出網(wǎng)頁(yè)相似度，根據(jù)網(wǎng)頁(yè)相似度計(jì)算出網(wǎng)頁(yè)采集周期。Cai等[17]提出了一種基于學(xué)習(xí)的論壇采集方法，通過(guò)離線(xiàn)分析論壇的總體結(jié)構(gòu)特點(diǎn)，重建網(wǎng)站的站點(diǎn)地圖，過(guò)濾無(wú)效鏈接，獲得有效鏈接。蔡欣寶等[18]在其基礎(chǔ)上，通過(guò)泊松模型對(duì)網(wǎng)頁(yè)更新頻繁度進(jìn)行估計(jì)，實(shí)現(xiàn)論壇增量采集。李莎莎等[19]提出了一種改進(jìn)的泊松模型，基于更新頻率計(jì)算窗口、內(nèi)容分析和網(wǎng)頁(yè)隸屬分析來(lái)預(yù)測(cè)更新時(shí)間。張皓等[20]提出基于去噪Hash的增量式網(wǎng)絡(luò)爬蟲(chóng)，該算法針對(duì)經(jīng)典的Hash算法對(duì)文本產(chǎn)生的Hash值過(guò)于敏感的問(wèn)題提出了解決方法，并將其應(yīng)用在Heritrix上[21]。

Kleinberg等[22]提出將網(wǎng)站頁(yè)面分為索引頁(yè)面和信息頁(yè)面，同時(shí)Meng等[8]提出sina網(wǎng)大約0.05%的網(wǎng)頁(yè)鏈接到其他20%的網(wǎng)頁(yè)，20%的網(wǎng)頁(yè)鏈接到其他50%的網(wǎng)頁(yè)，50%的網(wǎng)頁(yè)鏈接到其他90%的網(wǎng)頁(yè)，所以通過(guò)對(duì)索引頁(yè)面的觀察可以掌握整個(gè)論壇網(wǎng)頁(yè)的變化，如果只對(duì)索引頁(yè)面進(jìn)行增量監(jiān)測(cè)，判斷是否有新的鏈接，將新鏈接指向的內(nèi)容下載下來(lái)，并不需要對(duì)所有頁(yè)面進(jìn)行對(duì)比。本文結(jié)合人們對(duì)網(wǎng)絡(luò)論壇訪(fǎng)問(wèn)的統(tǒng)計(jì)學(xué)規(guī)律，利用人們生活作息本身的規(guī)律性，將當(dāng)前主要的兩種研究方法相結(jié)合，通過(guò)對(duì)論壇索引頁(yè)面的采樣和觀察，發(fā)現(xiàn)其變化的規(guī)律性和周期性，然后采用合適的數(shù)學(xué)模型去描述該規(guī)律性和周期性，最后用該數(shù)學(xué)模型去預(yù)測(cè)索引頁(yè)面下一次變化的時(shí)間，并與其他增量更新策略進(jìn)行比較。實(shí)驗(yàn)結(jié)果證明，該模型可以有效預(yù)測(cè)網(wǎng)絡(luò)論壇索引頁(yè)面更新的時(shí)間，在10%誤差范圍內(nèi)，可以獲得93.9%的預(yù)測(cè)準(zhǔn)確率。

1 相關(guān)定義

現(xiàn)有網(wǎng)絡(luò)論壇的總體結(jié)構(gòu)一般由多個(gè)版塊組成，每個(gè)版塊中又包含多個(gè)主題鏈接。所以，論壇中Web頁(yè)面根據(jù)其功能大致可以分為兩類(lèi)：信息頁(yè)面和索引頁(yè)面[22]。前者主要用于展示基本信息內(nèi)容，多為陳述信息的普通文本。后者則主要用于信息瀏覽的導(dǎo)航和組織，其內(nèi)容主要是鏈接到信息頁(yè)面的超鏈接，超鏈接的變化意味著信息頁(yè)面也發(fā)生了變化，所以通過(guò)對(duì)索引頁(yè)面的觀察可以掌握整個(gè)論壇網(wǎng)頁(yè)的變化。索引頁(yè)面是本文的研究對(duì)象，參照文獻(xiàn)[8]，針對(duì)該種頁(yè)面我們有如下定義：

定義1 網(wǎng)絡(luò)論壇索引頁(yè)面

網(wǎng)絡(luò)論壇中包含多個(gè)信息頁(yè)面鏈接、起信息頁(yè)面目錄作用、變化頻繁的網(wǎng)頁(yè)，我們稱(chēng)之為索引頁(yè)面(如沒(méi)特殊說(shuō)明，文中的索引頁(yè)面均指網(wǎng)絡(luò)論壇中的索引頁(yè)面)。

定義2 索引頁(yè)面的有效鏈接數(shù)

索引頁(yè)面是信息頁(yè)面鏈接的合集，但是其中一般也包含指向論壇網(wǎng)站其他位置的鏈接，即噪音鏈接[23]，于是我們將索引頁(yè)面中除去噪音鏈接后的信息頁(yè)面鏈接的數(shù)量稱(chēng)為其有效鏈接數(shù)。

那么我們?nèi)绾潍@取一個(gè)索引頁(yè)面的有效鏈接數(shù)？假設(shè)我們的爬蟲(chóng)系統(tǒng)在時(shí)刻t1獲取索引頁(yè)面a，得到其中全部鏈接的集合為s1；接著爬蟲(chóng)系統(tǒng)在時(shí)刻t2再次獲取a，同樣得到其中的全部鏈接的集合為s2。當(dāng)T=t2-t1大于某一值時(shí)，索引頁(yè)面a的有效鏈接即為：

s={l|l∈s2,l?s1}

(1)

其中，s中鏈接的個(gè)數(shù)即為索引頁(yè)面中有效連接的數(shù)量。從物理含義上解釋?zhuān)诮?jīng)過(guò)時(shí)間T后，索引頁(yè)面a中信息頁(yè)面鏈接全部被新產(chǎn)生的信息頁(yè)面鏈接所替換。T的大小與論壇的活躍度相關(guān)，一般活躍度越高，T越小，反之亦然。

定義3 索引頁(yè)面有效鏈接變化數(shù)

對(duì)于索引頁(yè)面a，爬蟲(chóng)系統(tǒng)在時(shí)刻t1得到其全部鏈接集合s1，在時(shí)刻t2得到其全部鏈接集合s2，那么在時(shí)間間隔T=t2-t1內(nèi)，集合s={l|l∈s2,l?s1}中鏈接個(gè)數(shù)n即為索引頁(yè)面a在時(shí)刻t2有效鏈接變化數(shù)。其表示的物理含義是頁(yè)面a在時(shí)間間隔T內(nèi)產(chǎn)生了n條新的信息頁(yè)面鏈接。

定義4 索引頁(yè)面有效鏈接變化頻率

定義5 索引頁(yè)面變化率

索引頁(yè)面a在時(shí)間間隔T=t2-t1內(nèi)的有效鏈接變化數(shù)和索引頁(yè)面的有效鏈接數(shù)的比值稱(chēng)為a在時(shí)間間隔T內(nèi)的變化率。其表示的物理含義是索引頁(yè)面a在時(shí)間間隔T內(nèi)的變化程度。

2 策略模型

本節(jié)將對(duì)索引頁(yè)面的變化規(guī)律作出合理性的假設(shè)，并在此假設(shè)的基礎(chǔ)上對(duì)相關(guān)的數(shù)據(jù)進(jìn)行采樣和后處理，然后采用合適的數(shù)學(xué)模型去描述這種變化規(guī)律，最后將說(shuō)明新建立的模型如何進(jìn)行應(yīng)用在索引頁(yè)面的增量更新上。

2.1 變化規(guī)律假設(shè)

網(wǎng)絡(luò)論壇的使用主體是人，人都有一定的生活作息規(guī)律，如晚上睡覺(jué)、白天上班等。所以，人們生活的規(guī)律性使得人們對(duì)論壇的訪(fǎng)問(wèn)也具有一定的規(guī)律性，進(jìn)而使得網(wǎng)絡(luò)論壇本身的更新頻率也具有一定的規(guī)律性，如睡覺(jué)時(shí)間段3：00-6：00更新頻率較小，上午9：00-11：00更新頻率較大等。從而我們知道索引頁(yè)面變化頻率不是一成不變的，而是在一日之內(nèi)隨著時(shí)間的推移而發(fā)生變化，并且其變化周期為一天(我們將在3.1節(jié)中對(duì)其進(jìn)行驗(yàn)證)。

基于這樣的規(guī)律假設(shè)，我們就可以確定索引頁(yè)面的更新時(shí)間間隔不是固定的，而是動(dòng)態(tài)變化的。

2.2 數(shù)據(jù)采樣與后處理

我們對(duì)不同天的同一時(shí)間的采樣數(shù)據(jù)取平均值(即S中每一列取平均值)：

(3)

得到數(shù)據(jù)集合{(ti,ai),1≤i≤n}。同時(shí)：

(4)

其中，ri表示ti時(shí)刻索引頁(yè)面有效鏈接變化頻率，進(jìn)而可以得到我們的數(shù)據(jù)集：

Φ={(t1,r1),(t2,r2),…,(tn,rn)}

(5)

基于2.1節(jié)的假設(shè)，索引網(wǎng)頁(yè)中有效鏈接變化頻率呈現(xiàn)以日為周期的變化，此為典型的線(xiàn)性變化模型，于是我們采用最小二乘法多項(xiàng)式曲線(xiàn)擬合的方法對(duì)訓(xùn)練數(shù)據(jù)集進(jìn)行處理，得到我們的數(shù)學(xué)模型。

2.3 最小二乘法多項(xiàng)式曲線(xiàn)擬合

根據(jù)給定的n個(gè)點(diǎn)，并不要求所求的多項(xiàng)式曲線(xiàn)精確地經(jīng)過(guò)這些點(diǎn)，而是求一條近似曲線(xiàn)y=f(t)得近似曲線(xiàn)y=f(t)定的實(shí)際點(diǎn)之間的偏差最小，這就是線(xiàn)性模型中的曲線(xiàn)擬合[24]。

對(duì)于2.2節(jié)中的等式對(duì)應(yīng)的數(shù)據(jù)集，擬合曲線(xiàn)y=f(t)的偏差平方和l為：

(6)

按照偏差平方和最小的準(zhǔn)則，即求得y=f(t)使得l最小。

設(shè)擬合曲線(xiàn)滿(mǎn)足下列多項(xiàng)式：

y=f(t)=a0+a1×t+…+ak×tk

(7)

那么：

(8)

等式為a0,a1，…,ak的多元函數(shù)，由此將問(wèn)題轉(zhuǎn)化為求l=l(a0,a1,…,ak)的極值問(wèn)題。由多元函數(shù)求極值的必要條件，得：

(9)

(10)

進(jìn)一步化簡(jiǎn)得到：

(11)

即X×A=Y，從而可以得到系數(shù)矩陣A，也得到了擬合曲線(xiàn)，進(jìn)而得到了我們的數(shù)學(xué)模型。

2.4 模型應(yīng)用

由2.3節(jié)中式(6)-式(11)，我們得到了擬合曲線(xiàn)y=f(t)，其表示的物理含義為索引頁(yè)面有效鏈接變化頻率隨時(shí)間t的變化。那么索引頁(yè)面在任意時(shí)間段內(nèi)的有效鏈接變化數(shù)可以通過(guò)求曲線(xiàn)y=f(t)的積分來(lái)實(shí)現(xiàn)。

圖1表示的是曲線(xiàn)y=f(t)，橫軸為時(shí)間，縱軸表示的是索引頁(yè)面有效鏈接變化頻率。那么時(shí)刻a和時(shí)刻b間隔內(nèi)有效鏈接變化數(shù)n可以表示為：

(12)

當(dāng)索引頁(yè)面變化率達(dá)到z時(shí)，我們認(rèn)為該索引頁(yè)面應(yīng)該進(jìn)行更新。令索引頁(yè)面有效鏈接的數(shù)量為v，我們?cè)跁r(shí)刻a對(duì)索引頁(yè)面進(jìn)行了更新，下一次更新的時(shí)刻b應(yīng)該滿(mǎn)足如下公式：

(13)

從而可以計(jì)算出下一次索引頁(yè)面最合適的更新時(shí)刻b。

圖1 模型應(yīng)用說(shuō)明

3 實(shí)驗(yàn)設(shè)計(jì)及結(jié)果分析

本節(jié)將對(duì)2.1節(jié)中的規(guī)律性假設(shè)進(jìn)行實(shí)驗(yàn)驗(yàn)證，對(duì)該模型進(jìn)行測(cè)試，并與現(xiàn)有的更新策略進(jìn)行比較。

所有實(shí)驗(yàn)均在Ubuntu14.04機(jī)器上進(jìn)行，機(jī)器配置：4 GB內(nèi)存，Intel Core i7-3612QM處理器，100 MPbs網(wǎng)卡，實(shí)驗(yàn)均采用python2.7編碼實(shí)現(xiàn)。

3.1 規(guī)律性驗(yàn)證

我們選取表 1中的四大論壇相關(guān)板塊作為我們的實(shí)驗(yàn)對(duì)象，獲取版塊索引頁(yè)面的有效鏈接變化數(shù)，并將其轉(zhuǎn)化為有效鏈接變化頻率(單位時(shí)間內(nèi)鏈接變化數(shù))?？紤]到不同版塊固有的訪(fǎng)問(wèn)量不同，對(duì)應(yīng)的更新頻率也會(huì)有所區(qū)別，所以我們對(duì)不同版塊的采樣周期也會(huì)有所不同。實(shí)驗(yàn)環(huán)境下，該采樣周期通過(guò)觀察相關(guān)版塊日更新總數(shù)進(jìn)行確定。

表1 實(shí)驗(yàn)使用的網(wǎng)絡(luò)論壇及采樣周期

我們對(duì)上述四個(gè)板塊進(jìn)行30天的數(shù)據(jù)采樣，并繪制樣本數(shù)據(jù)平均值和方差隨樣本容量的變化曲線(xiàn)。圖 2和圖 3分別表示的是樣本平均值和方差的變化曲線(xiàn)。圖 2橫軸表示樣本容量，縱軸表示有效鏈接變化頻率的平均值，從中可以看出，不同論壇版塊對(duì)應(yīng)的鏈接變化頻率的平均值不同，但是隨著樣本容量的增加，總體平均值趨向穩(wěn)定。同時(shí)，圖 3說(shuō)明隨著樣本容量的增加，樣本總體方差趨向于穩(wěn)定。所以，我們可以認(rèn)為樣本對(duì)應(yīng)時(shí)間序列是穩(wěn)定的。

圖2 樣本總體平均值隨樣本數(shù)量變化曲線(xiàn)圖

同時(shí)，我們對(duì)樣本進(jìn)行FFT變換[25]，將其從時(shí)域變換到頻域，并繪制出圖4所示的頻譜圖。圖4橫軸表示的頻率成分，縱軸表示的是幅值，對(duì)其進(jìn)行主頻率成分分析，得到最大幅值對(duì)應(yīng)的頻率，得到表2的結(jié)果。從表2中可以看出，四個(gè)論壇對(duì)應(yīng)的變化周期均約為24小時(shí)。

圖3 樣本總體方差隨樣本數(shù)量變化曲線(xiàn)圖

圖4 樣本頻譜圖

通過(guò)實(shí)驗(yàn)我們可知，不同論壇相關(guān)的索引頁(yè)面更新頻率不一樣，但更新頻率的變化大致以日為周期，具有周期性，從而可以通過(guò)合適的數(shù)學(xué)模型來(lái)描述這種周期性的變化，為以后的變化趨勢(shì)做出更好地預(yù)測(cè)。

表2 論壇對(duì)應(yīng)幅值頻率及周期

3.2 模型測(cè)試及對(duì)比

從3.1節(jié)中我們得到了采集數(shù)據(jù)，根據(jù)2.2節(jié)中公式-對(duì)數(shù)據(jù)進(jìn)行處理，求得平均值，得到如公式所示的采樣數(shù)據(jù)集合，對(duì)該集合通過(guò)最小二乘法進(jìn)行多項(xiàng)式曲線(xiàn)擬合，得到預(yù)測(cè)模型。我們將以論壇2為例進(jìn)行闡述。

圖5顯示的是論壇2中公式對(duì)應(yīng)的數(shù)據(jù)集、擬合曲線(xiàn)和平均變化頻率。從該圖中可以看出，從23點(diǎn)開(kāi)始，索引頁(yè)面鏈接變化頻率開(kāi)始下降，6:00-11:00為變化頻率上升階段，18:00左右會(huì)有小幅度的下降，17:00-22:00會(huì)有小幅度的上升，這與一般人們的日常生活規(guī)律相符。

為了對(duì)該模型進(jìn)行測(cè)試，我們定義公式中的索引網(wǎng)頁(yè)變化率z為50%[1]，其物理含義是當(dāng)索引網(wǎng)頁(yè)有效鏈接變化數(shù)達(dá)到其全部有效鏈接數(shù)的一半時(shí)，我們認(rèn)為該索引網(wǎng)頁(yè)應(yīng)該得到更新，爬蟲(chóng)系統(tǒng)應(yīng)該去重新獲取該網(wǎng)頁(yè)。從而我們可以不斷利用預(yù)測(cè)模型并結(jié)合公式來(lái)預(yù)測(cè)下一次合理的更新時(shí)間。同時(shí)我們選取下面兩種方案作為對(duì)比：

? 常規(guī)的周期性更新策略，更新周期和采樣周期相同，論壇2更新周期為10 min；

? 基于學(xué)習(xí)的周期性更新策略[26]，即不考慮一天之內(nèi)更新頻率隨時(shí)間的變化，得到總的平均有效鏈接變化率，從而確定采樣周期。

對(duì)上述三種方案進(jìn)行為期10天的測(cè)試，得到每次更新索引頁(yè)面實(shí)際的變化率，并與期望的變化率z(50%)進(jìn)行比較。

圖5 索引頁(yè)面鏈接變化數(shù)學(xué)模型

圖6-圖8表示的是測(cè)試結(jié)果，橫軸均表示時(shí)間(HH:MM)，縱軸均表示索引頁(yè)面實(shí)際變化率(期望值為50%)。從圖 6和圖 7中可以看出，與期望的變化率50%相比，常規(guī)周期性更新策略和基于學(xué)習(xí)的周期性更新策略在00:00-09:00的誤差較大，09:00-24:00誤差率減少，并且后者的誤差率小于前者。圖 8為作者提出的數(shù)學(xué)模型對(duì)應(yīng)的實(shí)驗(yàn)結(jié)果，從中可以看出00:00-09:00更新次數(shù)明顯減少，這即與人們的生活規(guī)律相吻合，同時(shí)說(shuō)明模型的正確性：索引網(wǎng)頁(yè)變化頻率降低時(shí)，爬蟲(chóng)系統(tǒng)增量更新的次數(shù)也應(yīng)該降低；此外，索引頁(yè)面的實(shí)際變化率大部分都位于期望值50%的附近。表 3是對(duì)圖 6-圖 8的統(tǒng)計(jì)結(jié)果。從表中可以看出，策略③相比策略①，平均每天的更新次數(shù)減少了27.0%，預(yù)測(cè)的準(zhǔn)確性在A、B、C范圍內(nèi)分別提高了26.0%、65.3%、57.7%，總體而言，預(yù)測(cè)的準(zhǔn)確性大幅提升。策略③相比策略②，平均每天的更新次數(shù)增加了26.4%，但是預(yù)測(cè)的準(zhǔn)確性在A、B、C范圍內(nèi)分別提高了18.6%、57.5%、50.7%?？傮w而言，策略③通過(guò)犧牲一定的更新次數(shù)，在10%誤差范圍內(nèi)，可以獲得93.9%的預(yù)測(cè)準(zhǔn)確率，從而為網(wǎng)絡(luò)爬蟲(chóng)的增量更新確定合適的時(shí)間間隔。

圖6 常規(guī)周期性更新策略實(shí)驗(yàn)結(jié)果

圖7 基于學(xué)習(xí)的周期性更新策略實(shí)驗(yàn)結(jié)果

圖8 基于數(shù)學(xué)模型預(yù)測(cè)的更新策略實(shí)驗(yàn)結(jié)果

表3 不同更新策略實(shí)驗(yàn)結(jié)果比較

4 結(jié) 語(yǔ)

本文針對(duì)網(wǎng)絡(luò)論壇索引頁(yè)面提出了一種基于統(tǒng)計(jì)學(xué)規(guī)律的增量更新策略模型。通過(guò)對(duì)4大論壇相關(guān)版塊的索引頁(yè)面進(jìn)行數(shù)據(jù)的采集，觀察并證明其變化大致呈現(xiàn)以日為周期的規(guī)律性變化，一日之內(nèi)的變化曲線(xiàn)與人們的生活規(guī)律相吻合。然后采用最小二乘法多項(xiàng)式曲線(xiàn)擬合對(duì)其進(jìn)行數(shù)學(xué)建模，得到合適的數(shù)學(xué)模型，并將其應(yīng)用在索引頁(yè)面的增量更新之上，從而可以準(zhǔn)確預(yù)測(cè)索引頁(yè)面下一次更新的時(shí)間間隔。實(shí)驗(yàn)結(jié)果表明，在10%誤差范圍內(nèi)，預(yù)測(cè)的準(zhǔn)確率為93.9%。相比現(xiàn)有的方法，增加了約26%的更新次數(shù)，預(yù)測(cè)的準(zhǔn)確率提高了57.5%。因?yàn)椴煌搲鎵K訪(fǎng)問(wèn)量不同，導(dǎo)致其更新頻率不同，所以不同論壇版塊對(duì)應(yīng)的日變化曲線(xiàn)不相同，并且該模型需要對(duì)數(shù)據(jù)進(jìn)行較長(zhǎng)時(shí)間的采樣，從而限制了該模型在實(shí)際場(chǎng)景中的應(yīng)用。

[1] Junghoo, GarciaMolina, Hector. The Evolution of the Web and Implications for an Incremental Crawler[C]// International Conference on Very Large Data Bases. Morgan Kaufmann Publishers Inc. 2000:200-209.

[2] Douglis F, Feldmann A, Krishnamurthy B, et al. Rate of Change and other Metrics: a Live Study of the World Wide Web[C]//USENIX Symposium on Internet Technologies and Systems. 1997, 119.

[3] Fetterly D, Manasse M, Najork M, et al. A large-scale study of the evolution of web pages[C]//Proceedings of the 12th international conference on World Wide Web. ACM, 2003: 669-678.

[4] Fetterly D, Manasse M, Najork M. On the evolution of clusters of near-duplicate web pages[J]. Journal of Web Engineering, 2003, 2(4): 228-246.

[5] Brewington B E, Cybenko G. How dynamic is the Web?[J]. Computer Networks, 2000, 33(1): 257-276.

[6] Brewington B E, Cybenko G. Keeping up with the changing web[J]. Computer, 2000 (5): 52-58.

[7] Francisco-Revilla L, Shipman III F M, Furuta R, et al. Perception of content, structure, and presentation changes in Web-based hypertext[C]//Proceedings of the 12th ACM conference on Hypertext and Hypermedia. ACM, 2001: 205-214.

[8] Meng T, Yan H, Wang J, et al. The evolution of link-attributes for pages and its implications on web crawling[C]//Proceedings of the 2004 IEEE/WIC/ACM International Conference on Web Intelligence. IEEE Computer Society, 2004: 578-581.

[9] Cho J, Garcia-Molina H. Synchronizing a database to improve freshness[J]. ACM Sigmod Record. ACM, 2000, 29(2): 117-128.

[10] Cho J, Ntoulas A. Effective change detection using sampling[C]//Proceedings of the 28th international conference on Very Large Data Bases. VLDB Endowment, 2002: 514-525.

[11] Ntoulas A, Cho J, Olston C. What's new on the web?: the evolution of the web from a search engine perspective[C]//Proceedings of the 13th international conference on World Wide Web. ACM, 2004: 1-12.

[12] Ipeirotis P G, Ntoulas A, Cho J, et al. Modeling and managing content changes in text databases[C]//Data Engineering, 2005. ICDE 2005. Proceedings. 21st International Conference on. IEEE, 2005: 606-617.

[13] Cho J, Garcia-Molina H. Estimating frequency of change[J]. ACM Transactions on Internet Technology (TOIT), 2003, 3(3): 256-290.

[14] 沈文勤，李慶超，邵志清. 搜索引擎的漸增式爬行和備份式更新模式[J]. 華東理工大學(xué)學(xué)報(bào), 2004,30( 3): 284-287.

[15] 孟慶浩. 互聯(lián)網(wǎng)數(shù)據(jù)增量采集系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D]. 北京: 北京郵件大學(xué), 2015.

[16] 代鵬. 基于Nutch的增量網(wǎng)頁(yè)信息采集系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J]. 軟件, 2015, 36(11) : 100-104.

[17] Cai R, Yang J M, Lai W, et al. iRobot: An intelligent crawler for Web forums[C]//Proceedings of the 17th international conference on World Wide Web. ACM, 2008: 447-456.

[18] 蔡欣寶，郭若飛，趙朋朋， 等. Web 論壇數(shù)據(jù)源增量爬蟲(chóng)的研究[J]. 計(jì)算機(jī)工程, 2010, 36(9): 285-287.

[19] 李莎莎. 增量式 Web 信息采集與信息提取系統(tǒng)的研究與實(shí)現(xiàn)[D]. 武漢: 武漢理工大學(xué), 2011.

[20] 張皓，周學(xué)廣. 基于網(wǎng)頁(yè)去噪 Hash 的增量式網(wǎng)絡(luò)爬蟲(chóng)研究[J]. 艦船電子工程, 2014, 34(2): 86-90.

[21] 張皓, 周學(xué)廣. 基于 Heritrix 的增量式網(wǎng)絡(luò)爬蟲(chóng)研究[J]. 軟件導(dǎo)刊, 2013, 12(11): 135-137.

[22] Kleinberg J M. Authoritative sources in a hyperlinked environment[J]. Journal of the ACM (JACM), 1999, 46(5): 604-632.

[23] Guo Y, Li K, Zhang K, et al. Board forum crawling: a Web crawling method for Web forum[C]//Proceedings of the 2006 IEEE/WIC/ACM International Conference on Web Intelligence. IEEE Computer Society, 2006: 745-748.

[24] 李航等.統(tǒng)計(jì)學(xué)習(xí)方法[M].北京:清華大學(xué)出版社,2012.

[25] Lyons R G. Understanding digital signal processing[M]. Pearson Education, 2010.

[26] 徐文杰, 陳慶奎. 增量更新并行 Web 爬蟲(chóng)系統(tǒng)[J]. 計(jì)算機(jī)應(yīng)用, 2009, 29(4): 1117-1119.

RESEARCH ON INCREMENTAL UPDATING STRATEGY OF WEB FORUM BASED ON STATISTICS

Feng Kai1, 2*Chen Jun1,2Wang Juan2,3Wang Yong2,3

1(NationalEngineeringResearchCenterforMultimediaSoftware,WuhanUniversity,Wuhan430072,Hubei,China)2(CollegeofComputer,WuhanUniversity,Wuhan430072,Hubei,China)3(KeyLaboratoryofAerospaceInformationSecurityandTrustedComputingMinistryofEducation,WuhanUniversity,Wuhan430072,Hubei,China)

The traditional model of forecasting page changes applies a rule to all pages, without regard to the differences between pages. In this paper, we propose an incremental updating strategy model based on statistical rules for indexing web pages. Through the data collection and observation of the index page of the relevant forum, it is found that the index page shows a regular change in the daily cycle, and the curve of variation within a day coincides with the law of people’s life. The mathematical model is established by using the least square polynomial curve fitting, and it is applied to incremental updating of the index page, which can predict the time interval of the next updating of the index page. The experimental results show that the accuracy of the model is 93.9% within the 10% error range.

Incremental updating Page changes Statistics Mathematic modeling

2016-05-09。國(guó)家自然科學(xué)基金項(xiàng)目(61402342)。馮凱，碩士生，主研領(lǐng)域：模式識(shí)別與智能系統(tǒng)。陳軍，教授。王鵑，副教授。王勇，碩士生。

TP3

A

10.3969/j.issn.1000-386x.2017.06.007