優先關聯的Web日志數據逼真生成算法①

丘志鵬, 肖如良, 張 銳

?

優先關聯的Web日志數據逼真生成算法①

丘志鵬, 肖如良, 張 銳

(福建師范大學軟件學院, 福州 350117) (福建省公共服務大數據挖掘與應用工程研究中心, 福州 350117)

字段關聯的構建方法是Web數據逼真生成中的困難問題. 提出一種基于MIC的字段優先關聯的Web數據逼真生成算法. 該算法與現有的方法完全不同: 首先, 提取真實Web日志數據集中相應字段間的MIC系數; 然后, 結合字段的重尾特性, 采用SE分布對字段的重尾性進行建模; 最后, 建立字段關聯模型, 模擬出真實數據集中的字段間依賴性, 從而逼真生成目標數據集. 實驗表明, 生成的數據集能夠保持合理的字段間的均衡性以及節點間的相似性.

字段關聯; 數據生成; MIC系數; 重尾

合理分析Web日志數據的字段內容, 有助于對其領域系統的構建及測試, 然而Web日志數據通常達到TB甚至PB級別, 極其耗費網絡資源, 并且數據中用戶行為及相關物品屬性等相關字段內容涉及隱私信息, 因此, 企業及政府等機構極少愿意分享其數據供研究人員使用. 隨著互聯網規模的不斷擴大, Web日志數據中重尾現象也越發普遍, 各個字段間的關聯變得愈加復雜, 生成具有真實數據特性的數據集極具難度. 因此, 構建一個可模擬出真實字段間關聯關系的數據生成算法成為眾多科研工作中模擬數據來源的基礎, 也是本文研究的重點.

現有的數據生成算法的研究主要分為時間字段相關性質的研究與非時間字段相關性質的研究兩個方面. 前者主要應用于網絡流量預測、時序分析等方面, 現已較為成熟, 有相應的商用與科研軟件供研究人員使用, 如OPNET; 而后者主要在于對字段分布特性的數學建模及字段間關聯研究, 主要應用于特定的研究項目中, 需要根據不同業務場景進行逼真生成, 復雜度高, 主要代表性工作有加拿大薩斯喀徹溫大學Busari提出的proWGen[1]數據生成器, 通過分析Web用戶行為字段值分布情況, 用Zipf-like分布刻畫字段重尾性[2]進行數據生成, 采用多參數的機制, 使得該生成器具有良好的擴展性, 能應用于Web服務器的壓力測試及緩存性能研究. 缺點在于: proWGen對字段關聯僅采用簡單的正/負相關的方式實現, 難以逼真生成實際中復雜多樣的數據.

隨著互聯網數據量的爆炸式增加, Zipf-like已經不再適用于描述具有重尾特性的Web數據分布, 文獻[3]指出采用SE分布描述Web數據的重尾性更加合理. 若采用Zipf-like進行數據生成, 對于生成數據所應用的系統而言, 其測試性能評估上會存在高估的結果, 與真實數據情況對比有較大的誤差, 意味著生成了不可靠的數據. 所以目前非時間字段相關性質研究仍處于成長階段. 本文主要以非時間字段相關性質研究作為主要工作.

針對以上問題, 本文提出了一種基于MIC的字段優先關聯的Web日志數據逼真生成(Simulate Generating Web Log algorithm using fields’ priority relevance based on maximal information coefficient, SGWL)算法. 該算法與現有的方法完全不同, 通過利用Web日志數據特征進行參數提取, 采用SE分布代替Zipf-like分布對字段重尾性進行刻畫. 然后對數據字段關聯提出一種全新的模型(基于MIC的字段優先關聯模型)代替傳統的正/負相關模型, 進行指導關聯. 通過該算法生成的數據, 不僅在整體上能擬合一個逼真的分布趨勢, 在局部上也能夠準確刻畫字段重尾性并保持合理的字段間的均衡性以及節點間的相似性, 可應用于 Web數據驅動的軟件過程.

1　相關工作

目前, 國內外已有大量的仿真數據生成研究. 按其是否與時間因素相關可分為二個類別: 其一, 與非時間字段性質相關的研究; 其二, 與時間字段性質相關的研究.

(1) 非時間字段相關性類型的研究主要涉及非時間相關字段的建模及字段間關聯研究, 例如字段值出現次數分布建模、重尾性刻畫等. 通過已有Web數據作為驅動, 對其進行數學建模, 從而來模擬生成新的數據. 中科院計算所詹劍鋒研發的可擴展大數據生成器BDGS[4]在生成量、速率、多樣性、真實性這四個角度進行仿真數據, 能夠自定義生成結構化、半結構化、非結構化數據并能保持數據的重尾性, 但是其缺陷在于: 字段關聯模型單一、缺乏物理意義; 新加坡國立大學Tay[5]通過研究照片評論數據, 指出字段關聯關系在數據生成中的重要性. 在Tay的研究工作中定義了五種數據類型, 實際上這種做法存在一定的局限性, 五種類型不足以囊括復雜多樣的真實數據; proWGen數據生成器采用多參數可調機制, 運用數學模型建模可生成具有Web訪問特征的數據. 該方法具有較大的靈活性, 可以較為逼真的模擬單列Web數據字段, 但是在多字段數據生成中僅僅采用正/負相關的方式進行仿真, 不足以描述Web數據中不同字段屬性的復雜關系; 加拿大多倫多大學Rabl設計的PDGF[6]數據生成器, 目前是TPC-DI(數據集成評測系統)的專用數據生成器, 已經被大數據測試基準BigBench廣泛使用, 但是該生成器只供特定數據進行生成, 其擴展性較為一般; 工業界現有的數據生成器Red Gate[7]、DTM[8], 可高速生成與真實業務數據相似的數據, 然而, 工業界的數據生成主要依托于相關的業務, 由于這類生成器具有通用性, 也意味著無法根據真實數據的特性隨意修改生成字段間的關聯.

(2) 時間字段相關性類型的研究, 需要為時間屬性字段建模, 通過模擬時間相關屬性特征(如網絡流量自相似性、長相關性、多分形性)來生成Web數據. 其中包括以浙江大學尹建偉研發的BURSE[9]為代表的工作負載數據生成器, 重點模擬數據的周期性、突發性特征來實現Web數據的自相似性; 法國凡爾賽大學Laurent[10]主要通過研究天氣數據的時間序列, 在不同時間尺度上依賴于多分形理論進行相應數據仿真生成; 美國新澤西理工學院Ansari[11]研究了基于FARIMA的MPEG視頻流量建模問題,采用 FARIMA過程作為自相似流量產生器, 對MPEG中的I、P和B幀的自相關結構進行建模, 從而完成數據生成. 此外, 時間字段相關性質研究領域也具備較為成熟的產品用于數據生成, 加拿大西蒙菲沙大學Michael[12]收集了蜂窩數字包數據網絡(CDPD)中的業務數據并對運用工具OPNET建模和仿真分析. 以上的這些時間字段相關性質研究成果, 均有強力的學科理論、技術模型支撐, 其涉及到自相似網絡業務ON/OFF模型、時間序列分析FARIMA模型等, 并且也有較為成熟的產品供研究人員使用, 商用軟件有OPNET, BONeS和COMNET III, 科研用軟件有NS2和SSF NET. 而非時間字段相關性質研究的數據生成方法, 目前并沒有一個通用的商用軟件供研究者使用, 并且現有的數據生成器中依然局限于簡單的數據分布與粗糙的字段關聯, 沒有一個合適且較為完備的模型來指導非時間字段相關性質研究數據生成中字段關聯的問題.

綜上所述, 數據生成器的時間字段相關性質研究已趨于成熟, 而非時間字段相關性質研究中仍存在許多需要急于解決的困難問題. 本文重點對數據生成的非時間字段相關性質研究進行相關改進工作. 通過運用SE分布來對具有重尾現象的Web字段值出現次數進行刻畫, 在所需關聯的字段間用MIC系數作為關聯度的描述, 建立全新的關聯模型, 進而使生成的數據更具有可靠性, 從而達到逼真生成的目的.

2　理論基礎

2.1 重尾數據的分布

2.1.1 Zipf-like分布

大數據背景下, Web日志數據中部分字段分布呈現出冪律分布的特性, 也就是人們常說的長尾現象, 本文中統一稱為重尾性. Zipf-like分布又稱為類齊普夫分布, 通常用于描述具有重尾性質字段的分布, 本節圖示以Movielens-1m數據集為例, 以排名位序值(Rank)作為X軸, 以出現次數(Times)t作為Y軸, 如圖1所示userID字段值出現次數(又稱為用戶活躍度)表現出重尾性, 在傳統方法中通常使用Zipf-like分布來對其進行刻畫.

圖1　用戶活躍度分布情況

假設一個數據集D中某字段A服從參數為的Zipf-like分布, 那么對其字段值所出現的次數統計進行降序排列, 序列第的字段A, 其出現的次數t滿足式(1):

其中為數據集的總記錄數, 參數的表達如式(2)所示:

若數據集D中某字段的所有值出現次數服從Zipf-like分布, 那么根據對象出現次數降序排列, 在坐標系中, 以排名位序值(Rank)作為X軸, 以出現次數(Times)t作為Y軸, 分別對X軸、Y軸上的對應所有數據進行取自然對數處理, 那么應當呈現出一條直線. 如圖2可發現, 用戶活躍度在雙對數坐標系下并非呈現一條直線, 說明用戶活躍度并不服從Zipf-like分布.

圖2雙對數坐標系下用戶活躍度分布情況

2.2.2 SE分布

SE分布(Stretched Exponential Distribution), 中文全稱為廣延指數分布, 最早由Kohlrausch于1847年研究發現, 適用于描述不同復雜系統的動態衰減現象, 其中包括自然、經濟、互聯網等領域. 美國俄亥俄州立大學張曉東[3]對不同Web系統的用戶行為日志數據進行分析, 發現Zipf-like分布不適合描述Web日志行為數據的重尾性, 而SE分布能對其進行很好的刻畫. 說明該分布適用于描述冪律模型無法準確刻畫的情況.

式(3)表示SE分布的概率密度函數:

累計分布函數如式(4)所示:

其中為廣延參數, 其參數范圍在(0, 1),x為尺度參數.

為了方便描述, 我們約定將X軸上的對應所有數據進行取自然對數處理, Y軸上的對應所有數據進行取原值的次冪處理, 這樣得到的坐標系稱為SE坐標系. 若數據集D中某字段的所有值出現次數服從SE分布, 那么根據對象出現次數降序排列, 在坐標系中, 以位序值作為X軸, 以出現次數t作為Y軸, 再將X、Y的值轉化置SE坐標系中, 那么應當呈現出一條直線. 如圖3, 可以清楚的看出用戶活躍度在SE坐標系下呈現一條近似直線, 說明用戶活躍度服從SE分布.

圖3 SE坐標系下用戶活躍度分布情況

采用公式(5)對該直線進行描述:

2.2 字段關聯性度量

記錄是由若干個字段組合而成, 而字段間必然存在著某種關聯. 為了能準確量化描述兩個字段間的關聯性, 研究者們提出了pearson系數、spearman系數、核密度估計(KDE)、互信息等度量標準. 這些度量方法復雜、不適用非線性數據, 缺乏普適性、健壯性低等問題, 難以適用于數據生成算法中. 為此本文采用MIC(The Maximal Information Coefficient)系數作為字段關聯性度量.

2011年, Reshef[13]在Science首次提出MIC系數, 中文又稱為最大信息系數. 該系數是在互信息的基礎上衍化而來, 能對不同類型的關聯關系進行評估, 其范圍為[0,1], 且具有對稱性、良好的普適性和公平性. 如果變量與獨立, 則MIC(,)=0; 如果與之間具有確定的關系, 則MIC(,)=1, 此時不存在任何噪聲影響.

計算方法主要是通過對變量對(,)中所有樣本點的構成的散點圖進行劃分, 利用動態規劃的方式計算并搜索不同劃分方式下所能達到的最大互信息值. 最后, 對最大互信息值進行標準化處理, 所得結果即為MIC, 記作e. 記’為給定數據集,和分別表示在X和Y變量軸上的劃分份數,為變量對(,)的樣本容量, G表示某種劃分. 因此在劃分G下等(×)軸劃分的最大互信息為式(6):

標準化處理得到的特征矩陣如式(7)所示:

最終得到的MIC值如式(8)所示:

其中()為網格劃分細度, 通常取值為0.6, 以上方法步驟簡稱MINE方法.

由式(8)可以發現, MIC隨著網格劃分細度的變化而變化, 當樣本容量越大的時候估計值也越準確, 這適用于當前大數據的時代背景. 表1列出四種相關系數的應用對比, 由表1可知MIC系數具有適用范圍廣、計算復雜度低, 魯棒性高, 標準化結構特性. 因此, 本文算法采用MIC作為字段關聯度參考.

表1 四種相關系數優劣對比

注: L—低; M—中; H—高; Y—是; N—否.

3　基于MIC的字段優先關聯模型

假設要生成由兩列字段組成, 共計條記錄的日志數據集, 其中字段名分別用A、B表示. 令字母S表示為集合, 那么字段A對應的值所在集合SA={A,A,A…A}, 共有種取值; 字段B對應的值所在集合SB={B,B,3…B}, 共有種取值. 每條記錄的形式為{A,B}(1≤≤,1≤≤). 令字母t代表次數, 則字段A值A出現的次數為t次,字段A中所有值分別出現次數構成集合S, 字段B中值B出現的次數為t次, 字段B中所有值分別出現次數構成集合S, 且滿足式(9)表示字段A所有值出現次數累加和等于字段B所有值出現次數累加和等于日志數據集總記錄數.

對于數據生成而言, 首先分別對字段的所有值出現次數的集合進行建模, 根據章節2.1的方法, 得到出現次數降序排列的集合S與S. 然后累積分布函數(), 其中表示字段值出現次數的排名位序. 以A字段為例, 累積分布函數具體如式(10), 到該步便完成字段建模的步驟.

記錄是由字段組合而成, 在完成字段建模之后, 需要將兩個字段進行關聯操作, 進而形成一條完整的記錄. 關聯操作即為取集合SA與SB笛卡爾積的一個元素的過程. 假定符號ξ表示(0,1)上均勻分布的隨機數, 字母r表示關聯取值數, 則在生成一條記錄時, 首先生成隨機數ξ, 令ξ=p(), 通過式(10)的逆函數解析式,計算可得唯一的實數位序, 根據位序與字段值映射關系, 求得字段值A. 然后, 根據AB字段間的相關性, 通過關聯模型計算得到r, 令r=B(), 同理可得字段值B, 即得到記錄{Ax,B}.

關聯過程存在三種情況, 分別為正相關、負相關與零相關, 其中正相關表示自變量增長, 因變量也跟著增長; 負相關表示自變量增長, 因變量反而減少; 因變量的增減與自變量的增減無關, 相互獨立. 現階段數據生成算法中主要使用關聯模型分為正相關模型與負相關模型, 其中正相關模型為r=ξ, 負相關模型為r=1-ξ, 該模型的不足之處在于關聯度量簡單, 不具備的物理意義, 且未考慮字段間零相關情況. 因此, 本文提出一種基于MIC的字段優先模型PRF(the Priority Relevance of Field based on maximal information coefficient, PRF). 令表示經過PRF模型得到的關聯取值數, 且由優先關聯部分與獨立部分組合而成. 正相關PRF模型如式(11)所示:

負相關PRF模型如式(12)所示:

其中∈[1,],∈[1,], 參數e∈[0,1]為字段A與字段B之間的MIC系數, 用于衡量字段間相關程度, 在模型中的物理意義表示優先關聯部分所占比例.表示隨機字段值A出現次數的累積分布概率()./表示在B字段中個取值內, 隨機選取第個值作為字段值的概率. 令,ξ=/分別帶入式(11)、式(12), 化簡得到式(13)、式(14).

若字段間存在關聯, 模型優先采用ξ對字段B進行關聯取值, 若字段間相互獨立, 則重新生成隨機數ξ, 進行關聯取值. 當時, 說明字段A與字段B存在線性相關關系, 表示每個字段A的值都關聯著在各自累積分布函數()下相同累積概率的字段B的值, 以正相關模型為例, PRF模型轉化為. 當時, 說明字段A與字段B相互獨立, 表示每個字段A的值都與字段B的值不存在關聯, 呈現隨機關系. 以正相關模型為例, PRF模型轉化為. 當時, 優先關聯部分所占比例為e, 獨立部分所占比例為(1-e), 通過兩部分的和, 根據式(11)計算得出, 以作為字段B中某值的累積概率, 從而可以求出字段B的值, 最終完成一次字段A與字段B的關聯.

PRF模型具有一般性與明確的物理意義, 以MIC系數作為主要參考, 能合理的描述數據間的關聯情況, 適用于大部分數據生成算法中的字段關聯步驟.

4　基于PRF的Web日志數據生成算法SGWL

圖4 基于PRF模型的Web日志數據生成算法SGWL

本文提出一種基于PRF的Web日志數據逼真生成算法SGWL. 該算法通過提取真實數據集的相關參數, 利用SE分布模擬具有重尾性質的字段值出現次數集合, 在數據生成過程中根據PRF模型完成字段關聯, 每次生成完一條記錄之后對總條數進行更新, 從而達到控制生成記錄總量的目的. 算法描述如圖4所示.

在圖4 SGWL算法流程中, 步驟1至步驟2為Web日志數據字段特征提取過程, 步驟3至步驟4表示對字段進行建模, 步驟6至步驟8為生成一條完整記錄的過程, 其中步驟7表示字段關聯.

5　實驗結果與分析

5.1 實驗數據集介紹

在生成Web日志數據結束之后需要測評仿真數據集的可靠度, 采用真實數據集作為參照比對. 實驗采用四個不同領域具有代表性的數據集進行實驗分析, 旨在驗證SGWL算法的一般性, 其分別是Movielens-1M電影評分數據集、NASA網絡請求數據集、Epinions社會網絡數據集和Xiami音樂用戶行為數據集. 其中 MovieLens 1M為6040個用戶對3952個電影產生的1000209條評分記錄; NASA為54770個請求節點對8937個路徑產生的1048576服務日志數據記錄; Epinions為40163個用戶對139738個物品產生的664823條評分記錄; Xiami為162273個用戶對8377首歌曲產生的11098957條行為記錄, 其統計結果如表2所示.

表2 四個數據集基本統計結果

5.2 評估指標

2.巴基斯坦政府做出了巨大的努力，尤其在路線選擇上。巴基斯坦政府在規劃經濟走廊路線時充分考慮了各方的利益訴求，推出了多路線方案，滿足各方的利益訴求，從根源上減少某些“變相恐怖主義”的襲擊。

5.2.1字段均衡性指標: 基尼系數

基尼系數(Gini Coefficient)[13]是意大利經濟學家基尼于1992年提出, 定量測定收入分配差異程度. 基尼系數是比例數值, 在0和1之間, 是國際上用來綜合考察居民內部收入分配差異狀況的一個重要分析指標. 假定一定數量的人口按收入由低到高排序, 分為人數相等的m組, 從第1組到第組人口累計收入占全部人口總收入的比重為其計算方法如式(15)所示. 按照聯合國有關組織規定: 0.2表示絕對平均, 0.3-0.4表示相對合理, 0.5以上表示嚴重不均衡. 而如今, 基尼系數也可以用來測度各種意義下的資源分配均衡度. 正因為數據生成的時候需要對字段值出現次數進行建模, 同理基尼系數也適用于評估字段值出現次數的均衡性, 可以通過式(15)計算Gini系數.

5.2.1節點相似性指標: PA指數、AA指數

若用二分網絡結構來描述數據集, 那么字段上的值即對應為網絡中的節點這一概念. 節點相似性指標[14]在鏈路預測、節點聚類、個性化推薦方面應用都很廣泛. 電子科技大學周濤[14]羅列了十五種相似性指標, 本文采用其中兩種穩定性較好的指標作為實驗評判標準, 分別是PA指數與AA指數. 令表示節點相似性度量,與分別表示字段值與,表示字段值,表示字段A中既關聯了又關聯了的字段值的集合,表示出現的次數,表示出現的次數,表示出現的次數.

PA(Preferential Attachment )指數計算如式(16):

AA(Adamic-Adar)指數計算方法如式(17)所示:

5.3 實驗結果及分析

首先, 就整體層面而言, 本節選用Movielens-1m數據集與Epinions數據集作為真實數據集參考, 對具有重尾性質的字段User值出現次數分別進行Zipf-like分布刻畫與SE分布刻畫, 然后選取合適分布對字段進行擬合, 并計算出擬合函數與真實數據集的擬合優度^2評估擬合效果, 其實驗結果如圖5、圖6所示, 其中點線為雙對數坐標系下真實數據分布刻畫, 虛線為SE坐標系下真實數據分布刻畫, 實線為擬合直線.

由圖5與圖6, 可以看出兩個數據集字段User值出現次數分布在雙對數坐標系下均呈現出“胖頭瘦尾“的曲線形狀, 而在SE坐標系下均呈現出一條近似直線的情況, 因此根據章節2.1所述, 驗證了SE分布在描述重尾特征的數據字段上優于傳統的Zipf-like分布. 然后對虛線進行擬合, 通過R語言中的nls方法計算得到、值, 然后在圖上繪制對應直線, 計算出虛線與實線之間的擬合優度^2. 圖5中,^2=0.9748, 圖6中,^2=0.9719, 均接近于1, 說明回歸直線對真實數據的擬合程度很高. 總體而言, 采用SE分布的SGWL在重尾性刻畫上描述要優于proWgen, 生成的數據與真實數據集更為接近, 能更準確的描述真實數據集的重尾性, 從整體上把握數據的逼真生成.

圖5 Movielens-1m字段User整體分布擬合刻畫圖

圖6 Epinions字段User整體分布擬合刻畫圖

在局部層面上, 基尼系數是研究字段均衡性的一個重要特征, 選用四個不同領域的真實數據集的某一字段分別采用SGWL算法與proWgen算法進行數據仿真, 最終與真實數據集通過計算其基尼系數進行字段均衡性對比分析. 實驗結果如表3所示.

表3 真實數據集與生成數據集字段基尼系數(Gini)對比

根據表中數據可以直觀的看到列“Gini by SGWL”的每一個數值都明顯逼近于列“Real Gini”的值, 進一步通過數據計算可以得到SGWL生成數據的基尼系數與真實數據集的平均誤差為1.5%, 而proWgen生成數據的基尼系數與真實數據集的平均誤差卻達到了11%, 由此說明, SGWL算法生成的數據在字段均衡性上要優于proWgen, 且適用于不同領域背景下的數據生成, 具有一般性.

最后在個體評估層面上對節點間相似性進行實驗分析. 以Movielens-1m數據集作為真實數據集參考, 根據5.2.2介紹的方法, 令字段”UserID”代表字段A, 字段”MovieID”代表字段B, 在字段B中隨機選取10000對節點{,}, 依次分別在真實數據集與SGWL算法生成數據集中計算對應的相似性度量, 令真實數據集中所有組成的序列為, SGWL算法生成數據集中所有組成的序列為. 實驗需在坐標軸上繪制10000個散點, 其中以上所有的10000個值歸一化后依次作為散點的X坐標, 以上所有的10000個值歸一化后依次作為散點的Y坐標. 若兩個數據集具有相同的節點相似性, 那么散點將全部散落在傾斜度為45度的實線y=x上, 偏離斜線越遠則代表兩個數據集的節點間相似性差異越大, 從而說明算法生成的數據越不可靠. 實驗結果如圖7、圖8所示.

圖7 PA下節點相似性對比

圖8 AA下節點相似性對比

如圖所示, 圖7、圖8中大多數的散點位置均落在y=x這條斜線的附近, 部分點甚至于斜線重合. 圖7中真實數據PA指數與SGWL算法生成數據PA指數誤差為0.18%, 圖8中真實數據AA指數與SGWL算法生成數據AA指數誤差為6%, 因此圖7散點分布較圖8更為稠密. 從而說明生成的數據能較好的保持真實數據集中節點間的相似性, 表明SGWL算法生成的數據具有一定的可靠性. 在圖中7中99.8%節點對PA指數集中于(0,0.4)這個區間內, 這種情況的產生源于數據集中User字段的重尾性, 由式(16)可以看到, PA指數依賴于節點對值出現次數的乘積, 因此重尾性導致該乘積值普遍較小, 從而使得散點集中落在X坐標上(0,0.4)這個區間內. 這也進一步說明了SGWL算法能逼真刻畫字段的重尾性.

6　結論

合理的字段關聯是Web日志數據生成算法中的關鍵. 本文提出了基于MIC系數的字段優先關聯的Web日志數據逼真生成算法SGWL, 該方法以SE分布代替Zipf-like分布來模擬Web數據的重尾性, 并提出一個全新且物理意義明確的字段關聯模型PRF, 指導字段關聯. SGWL算法可保證生成的數據集具有同真實數據集一致的字段間關聯和字段值的分布, 為Web數據驅動的軟件研發, 提供了可靠的逼真數據生成.

1 Busari M, Williamson C. ProWGen: A synthetic workload generation tool for simulation evaluation of web proxy caches. Computer Networks, 2002, 38(6): 779–794.

2 Sarla P, Doodipala MR, Dingari M. Self similarity analysis of web users arrival pattern at selected web centers. American Journal of Computational Mathematics, 2016, 6(1): 17–22.

3 Guo L, Tan E, Chen S, et al. The stretched exponential distribution of internet media access patterns. Twenty-Seventh ACM Symposium on Principles of Distributed Computing (PODC 2008). Toronto, Canada. August, 2008. 283–294.

4 Ming Z, Luo C, Gao W, et al. BDGS: A scalable big data generator suite in big data benchmarking. Advancing Big Data Benchmarks. Springer International Publishing, 2014: 138–154.

5 Tay YC, Dai BT, Wang DT, et al. UpSizeR: Synthetically scaling an empirical relational database. Information Systems, 2013, 38(8): 1168–1183.

6 Rabl T, Poess M, Danisch M, et al. Rapid development of data generators using meta generators in PDGF. International Workshop on Testing Database Systems. 2013. 1–6.

7 Campbell MK. SQL data generator. Sql Server Magazine, 2009.

8 Lear D, Hebbes S. Database Tools, EP1606735. 2005.

9 Yin J, Lu X, Zhao X, et al. BURSE: A bursty and self-similar workload generator for cloud computing. IEEE Trans. on Parallel & Distributed Systems, 2015, 26(3): 668–680.

10 Akrour N, Mallet C, Barthes L, et al. A rainfall simulator based on multifractal generator. EGU General Assembly Conference. EGU General Assembly Conference Abstracts. 2015.

11 Ansari N, Liu H, Shi Y Q, et al. On modeling MPEG video traffics. IEEE Trans. on Broadcasting, 2002, 48(4): 337–347.

12 Jiang M, Nikolic M, Hardy S, et al. Impact of self-similarity on wireless data network performance. IEEE ICC. IEEE. 2001. 477–481.

13 Przanowski K, Mamczarz J. Consumer finance data generator-a new approach to credit scoring technique comparison. General Information, 2012. arXiv: 1210.0057.

14 Liu JG, Lei H, Xue P, et al. Stability of similarity measurements for bipartite networks. Science Reports, 2016.

Simulate Generating Web Log Algorithm Using Fields’ Priority Relevance

QIU Zhi-Peng, XIAO Ru-Liang, ZHANG Rui

(Faculty of Software, Fujian Normal University, Fuzhou 350117, China) (Fujian Provincial Engineering Research Center of Public Service Big Data Analysis and Application, Fuzhou 350117, China)

The construction method of field relevance is a difficult problem in the Web data generation. A new algorithm for fields’ priority relevance based on maximal information coefficient is proposed. The algorithm is completely different from the existing method. Firstly, the maximal information coefficient between the appropriate fields needs to be extracted from real Web log data. Then, combined with the field of heavy tailed characteristics, the field is modeled by stretched exponential distribution. Finally, real data’s field dependence is simulated by the fields’ relevance model, so as to generate a realistic target data set. The experiments show that the generated data sets can maintain a reasonable balance between the fields and the similarity between the nodes.

fields’ relevance; data generation; maximal information coefficient; heavy tail

福建省科技計劃重大項目(2016H6007)

2016-07-04;

2016-08-08

[10.15888/j.cnki.csa.005662]