基于統計學的Web論壇增量更新策略研究

馮 凱 陳 軍 王 鵑 王 勇

1(武漢大學國家多媒體軟件工程技術研究中心 湖北 武漢 430072)2(武漢大學計算機學院 湖北 武漢 430072)3(武漢大學空天信息安全與可信計算教育部重點實驗室 湖北 武漢 430072)

基于統計學的Web論壇增量更新策略研究

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

1(武漢大學國家多媒體軟件工程技術研究中心 湖北 武漢 430072)2(武漢大學計算機學院 湖北 武漢 430072)3(武漢大學空天信息安全與可信計算教育部重點實驗室 湖北 武漢 430072)

傳統預測網頁變化的模型將一種規律應用到所有網頁之上，沒有考慮各頁面之間的區別，針對網絡論壇索引頁面提出了一種基于統計學規律的增量更新策略模型。通過相關論壇版塊的索引頁面進行數據的采集，觀察并證明其變化大致呈現以日為周期的規律性變化，一日之內的變化曲線與人們的生活規律相吻合。然后采用最小二乘法多項式曲線擬合對其進行數學建模，得到合適的數學模型，并將其應用在索引頁面的增量更新之上，從而可以準確預測索引頁面下一次更新的時間間隔。實驗結果表明，該模型在10%誤差范圍內，預測的準確率為93.9%。

增量更新 網頁變化 統計學 數學建模

0 引 言

網絡爬蟲是用來從互聯網上收集網頁的程序，一般用于搜索引擎上。互聯網上網頁千變萬化，更新速度快，所以網絡爬蟲需要獲取到最新的頁面來替換舊的頁面, 更新本地存儲。傳統的方法是周期性訪問網頁實現更新，其需要重新下載所有已經下載的網頁，而不管該頁面是否真的發生變化。該方法不僅浪費爬蟲系統資源，還會影響網絡帶寬，也會耗費一定的時間。由此，產生了對爬蟲系統增量更新策略的研究[1]。爬蟲系統增量更新主要是指只更新真正發生改變的頁面，而未改變的頁面不做處理。毫無疑問，該方法大大節約了系統資源和網絡資源，提高了爬蟲效率。該方法的難點就在于爬蟲系統本身如何去判斷一個頁面是否發生了變化或者其變化程度為多少。

當前的研究主要有兩種方法：一是通過實驗手段對Web中的數據進行采樣，研究樣本的變化規律，從而估計整個Web的變化規律[1]；二是事先從理論上建立數學模型，并用實驗對模型進行驗證，得出模型參數，最后利用模型對頁面變化進行預測[9]。他們的研究適用于一般性的網站，并且將得到的網頁更新頻繁度應用到對應網頁的任何時刻。但是我們相信不同的爬蟲策略應該適用于不同特點和類型的網站，同一網頁在不同時刻的更新頻繁度也應該不同。本文的工作重點在于對網絡論壇增量更新策略的研究。

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

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

1 相關定義

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

定義1 網絡論壇索引頁面

網絡論壇中包含多個信息頁面鏈接、起信息頁面目錄作用、變化頻繁的網頁，我們稱之為索引頁面(如沒特殊說明，文中的索引頁面均指網絡論壇中的索引頁面)。

定義2 索引頁面的有效鏈接數

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

那么我們如何獲取一個索引頁面的有效鏈接數？假設我們的爬蟲系統在時刻t1獲取索引頁面a，得到其中全部鏈接的集合為s1；接著爬蟲系統在時刻t2再次獲取a，同樣得到其中的全部鏈接的集合為s2。當T=t2-t1大于某一值時，索引頁面a的有效鏈接即為：

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

(1)

其中，s中鏈接的個數即為索引頁面中有效連接的數量。從物理含義上解釋，在經過時間T后，索引頁面a中信息頁面鏈接全部被新產生的信息頁面鏈接所替換。T的大小與論壇的活躍度相關，一般活躍度越高，T越小，反之亦然。

定義3 索引頁面有效鏈接變化數

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

定義4 索引頁面有效鏈接變化頻率

定義5 索引頁面變化率

索引頁面a在時間間隔T=t2-t1內的有效鏈接變化數和索引頁面的有效鏈接數的比值稱為a在時間間隔T內的變化率。其表示的物理含義是索引頁面a在時間間隔T內的變化程度。

2 策略模型

本節將對索引頁面的變化規律作出合理性的假設，并在此假設的基礎上對相關的數據進行采樣和后處理，然后采用合適的數學模型去描述這種變化規律，最后將說明新建立的模型如何進行應用在索引頁面的增量更新上。

2.1 變化規律假設

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

基于這樣的規律假設，我們就可以確定索引頁面的更新時間間隔不是固定的，而是動態變化的。

2.2 數據采樣與后處理

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

(3)

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

(4)

其中，ri表示ti時刻索引頁面有效鏈接變化頻率，進而可以得到我們的數據集：

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

(5)

基于2.1節的假設，索引網頁中有效鏈接變化頻率呈現以日為周期的變化，此為典型的線性變化模型，于是我們采用最小二乘法多項式曲線擬合的方法對訓練數據集進行處理，得到我們的數學模型。

2.3 最小二乘法多項式曲線擬合

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

對于2.2節中的等式對應的數據集，擬合曲線y=f(t)的偏差平方和l為：

(6)

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

設擬合曲線滿足下列多項式：

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

(7)

那么：

(8)

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

(9)

(10)

進一步化簡得到：

(11)

即X×A=Y，從而可以得到系數矩陣A，也得到了擬合曲線，進而得到了我們的數學模型。

2.4 模型應用

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

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

(12)

當索引頁面變化率達到z時，我們認為該索引頁面應該進行更新。令索引頁面有效鏈接的數量為v，我們在時刻a對索引頁面進行了更新，下一次更新的時刻b應該滿足如下公式：

(13)

從而可以計算出下一次索引頁面最合適的更新時刻b。

圖1 模型應用說明

3 實驗設計及結果分析

本節將對2.1節中的規律性假設進行實驗驗證，對該模型進行測試，并與現有的更新策略進行比較。

所有實驗均在Ubuntu14.04機器上進行，機器配置：4 GB內存，Intel Core i7-3612QM處理器，100 MPbs網卡，實驗均采用python2.7編碼實現。

3.1 規律性驗證

我們選取表 1中的四大論壇相關板塊作為我們的實驗對象，獲取版塊索引頁面的有效鏈接變化數，并將其轉化為有效鏈接變化頻率(單位時間內鏈接變化數)。考慮到不同版塊固有的訪問量不同，對應的更新頻率也會有所區別，所以我們對不同版塊的采樣周期也會有所不同。實驗環境下，該采樣周期通過觀察相關版塊日更新總數進行確定。

表1 實驗使用的網絡論壇及采樣周期

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

圖2 樣本總體平均值隨樣本數量變化曲線圖

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

圖3 樣本總體方差隨樣本數量變化曲線圖

圖4 樣本頻譜圖

通過實驗我們可知，不同論壇相關的索引頁面更新頻率不一樣，但更新頻率的變化大致以日為周期，具有周期性，從而可以通過合適的數學模型來描述這種周期性的變化，為以后的變化趨勢做出更好地預測。

表2 論壇對應幅值頻率及周期

3.2 模型測試及對比

從3.1節中我們得到了采集數據，根據2.2節中公式-對數據進行處理，求得平均值，得到如公式所示的采樣數據集合，對該集合通過最小二乘法進行多項式曲線擬合，得到預測模型。我們將以論壇2為例進行闡述。

圖5顯示的是論壇2中公式對應的數據集、擬合曲線和平均變化頻率。從該圖中可以看出，從23點開始，索引頁面鏈接變化頻率開始下降，6:00-11:00為變化頻率上升階段，18:00左右會有小幅度的下降，17:00-22:00會有小幅度的上升，這與一般人們的日常生活規律相符。

為了對該模型進行測試，我們定義公式中的索引網頁變化率z為50%[1]，其物理含義是當索引網頁有效鏈接變化數達到其全部有效鏈接數的一半時，我們認為該索引網頁應該得到更新，爬蟲系統應該去重新獲取該網頁。從而我們可以不斷利用預測模型并結合公式來預測下一次合理的更新時間。同時我們選取下面兩種方案作為對比：

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

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

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

圖5 索引頁面鏈接變化數學模型

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

圖6 常規周期性更新策略實驗結果

圖7 基于學習的周期性更新策略實驗結果

圖8 基于數學模型預測的更新策略實驗結果

表3 不同更新策略實驗結果比較

4 結 語

本文針對網絡論壇索引頁面提出了一種基于統計學規律的增量更新策略模型。通過對4大論壇相關版塊的索引頁面進行數據的采集，觀察并證明其變化大致呈現以日為周期的規律性變化，一日之內的變化曲線與人們的生活規律相吻合。然后采用最小二乘法多項式曲線擬合對其進行數學建模，得到合適的數學模型，并將其應用在索引頁面的增量更新之上，從而可以準確預測索引頁面下一次更新的時間間隔。實驗結果表明，在10%誤差范圍內，預測的準確率為93.9%。相比現有的方法，增加了約26%的更新次數，預測的準確率提高了57.5%。因為不同論壇版塊訪問量不同，導致其更新頻率不同，所以不同論壇版塊對應的日變化曲線不相同，并且該模型需要對數據進行較長時間的采樣，從而限制了該模型在實際場景中的應用。

[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]. 華東理工大學學報, 2004,30( 3): 284-287.

[15] 孟慶浩. 互聯網數據增量采集系統的設計與實現[D]. 北京: 北京郵件大學, 2015.

[16] 代鵬. 基于Nutch的增量網頁信息采集系統的設計與實現[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 論壇數據源增量爬蟲的研究[J]. 計算機工程, 2010, 36(9): 285-287.

[19] 李莎莎. 增量式 Web 信息采集與信息提取系統的研究與實現[D]. 武漢: 武漢理工大學, 2011.

[20] 張皓，周學廣. 基于網頁去噪 Hash 的增量式網絡爬蟲研究[J]. 艦船電子工程, 2014, 34(2): 86-90.

[21] 張皓, 周學廣. 基于 Heritrix 的增量式網絡爬蟲研究[J]. 軟件導刊, 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] 李航等.統計學習方法[M].北京:清華大學出版社,2012.

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

[26] 徐文杰, 陳慶奎. 增量更新并行 Web 爬蟲系統[J]. 計算機應用, 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。國家自然科學基金項目(61402342)。馮凱，碩士生，主研領域：模式識別與智能系統。陳軍，教授。王鵑，副教授。王勇，碩士生。

TP3

A

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