丘志鵬, 肖如良, 張 銳

?

優(yōu)先關(guān)聯(lián)的Web日志數(shù)據(jù)逼真生成算法①

丘志鵬, 肖如良, 張 銳

(福建師范大學(xué)軟件學(xué)院, 福州 350117) (福建省公共服務(wù)大數(shù)據(jù)挖掘與應(yīng)用工程研究中心, 福州 350117)

字段關(guān)聯(lián)的構(gòu)建方法是Web數(shù)據(jù)逼真生成中的困難問題. 提出一種基于MIC的字段優(yōu)先關(guān)聯(lián)的Web數(shù)據(jù)逼真生成算法. 該算法與現(xiàn)有的方法完全不同: 首先, 提取真實(shí)Web日志數(shù)據(jù)集中相應(yīng)字段間的MIC系數(shù); 然后, 結(jié)合字段的重尾特性, 采用SE分布對字段的重尾性進(jìn)行建模; 最后, 建立字段關(guān)聯(lián)模型, 模擬出真實(shí)數(shù)據(jù)集中的字段間依賴性, 從而逼真生成目標(biāo)數(shù)據(jù)集. 實(shí)驗(yàn)表明, 生成的數(shù)據(jù)集能夠保持合理的字段間的均衡性以及節(jié)點(diǎn)間的相似性.

字段關(guān)聯(lián); 數(shù)據(jù)生成; MIC系數(shù); 重尾

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

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

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

針對以上問題, 本文提出了一種基于MIC的字段優(yōu)先關(guān)聯(lián)的Web日志數(shù)據(jù)逼真生成(Simulate Generating Web Log algorithm using fields’ priority relevance based on maximal information coefficient, SGWL)算法. 該算法與現(xiàn)有的方法完全不同, 通過利用Web日志數(shù)據(jù)特征進(jìn)行參數(shù)提取, 采用SE分布代替Zipf-like分布對字段重尾性進(jìn)行刻畫. 然后對數(shù)據(jù)字段關(guān)聯(lián)提出一種全新的模型(基于MIC的字段優(yōu)先關(guān)聯(lián)模型)代替?zhèn)鹘y(tǒng)的正/負(fù)相關(guān)模型, 進(jìn)行指導(dǎo)關(guān)聯(lián). 通過該算法生成的數(shù)據(jù), 不僅在整體上能擬合一個逼真的分布趨勢, 在局部上也能夠準(zhǔn)確刻畫字段重尾性并保持合理的字段間的均衡性以及節(jié)點(diǎn)間的相似性, 可應(yīng)用于 Web數(shù)據(jù)驅(qū)動的軟件過程.

1　相關(guān)工作

目前, 國內(nèi)外已有大量的仿真數(shù)據(jù)生成研究. 按其是否與時間因素相關(guān)可分為二個類別: 其一, 與非時間字段性質(zhì)相關(guān)的研究; 其二, 與時間字段性質(zhì)相關(guān)的研究.

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

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

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

2　理論基礎(chǔ)

2.1 重尾數(shù)據(jù)的分布

2.1.1 Zipf-like分布

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

圖1　用戶活躍度分布情況

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

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

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

圖2雙對數(shù)坐標(biāo)系下用戶活躍度分布情況

2.2.2 SE分布

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

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

累計(jì)分布函數(shù)如式(4)所示:

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

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

圖3 SE坐標(biāo)系下用戶活躍度分布情況

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

2.2 字段關(guān)聯(lián)性度量

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

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

計(jì)算方法主要是通過對變量對(,)中所有樣本點(diǎn)的構(gòu)成的散點(diǎn)圖進(jìn)行劃分, 利用動態(tài)規(guī)劃的方式計(jì)算并搜索不同劃分方式下所能達(dá)到的最大互信息值. 最后, 對最大互信息值進(jìn)行標(biāo)準(zhǔn)化處理, 所得結(jié)果即為MIC, 記作e. 記’為給定數(shù)據(jù)集,和分別表示在X和Y變量軸上的劃分份數(shù),為變量對(,)的樣本容量, G表示某種劃分. 因此在劃分G下等(×)軸劃分的最大互信息為式(6):

標(biāo)準(zhǔn)化處理得到的特征矩陣如式(7)所示:

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

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

由式(8)可以發(fā)現(xiàn), MIC隨著網(wǎng)格劃分細(xì)度的變化而變化, 當(dāng)樣本容量越大的時候估計(jì)值也越準(zhǔn)確, 這適用于當(dāng)前大數(shù)據(jù)的時代背景. 表1列出四種相關(guān)系數(shù)的應(yīng)用對比, 由表1可知MIC系數(shù)具有適用范圍廣、計(jì)算復(fù)雜度低, 魯棒性高, 標(biāo)準(zhǔn)化結(jié)構(gòu)特性. 因此, 本文算法采用MIC作為字段關(guān)聯(lián)度參考.

表1 四種相關(guān)系數(shù)優(yōu)劣對比

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

3　基于MIC的字段優(yōu)先關(guān)聯(lián)模型

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

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

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

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

負(fù)相關(guān)PRF模型如式(12)所示:

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

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

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

4　基于PRF的Web日志數(shù)據(jù)生成算法SGWL

圖4 基于PRF模型的Web日志數(shù)據(jù)生成算法SGWL

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

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

5　實(shí)驗(yàn)結(jié)果與分析

5.1 實(shí)驗(yàn)數(shù)據(jù)集介紹

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

表2 四個數(shù)據(jù)集基本統(tǒng)計(jì)結(jié)果

5.2 評估指標(biāo)

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

5.2.1字段均衡性指標(biāo): 基尼系數(shù)

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

5.2.1節(jié)點(diǎn)相似性指標(biāo): PA指數(shù)、AA指數(shù)

若用二分網(wǎng)絡(luò)結(jié)構(gòu)來描述數(shù)據(jù)集, 那么字段上的值即對應(yīng)為網(wǎng)絡(luò)中的節(jié)點(diǎn)這一概念. 節(jié)點(diǎn)相似性指標(biāo)[14]在鏈路預(yù)測、節(jié)點(diǎn)聚類、個性化推薦方面應(yīng)用都很廣泛. 電子科技大學(xué)周濤[14]羅列了十五種相似性指標(biāo), 本文采用其中兩種穩(wěn)定性較好的指標(biāo)作為實(shí)驗(yàn)評判標(biāo)準(zhǔn), 分別是PA指數(shù)與AA指數(shù). 令表示節(jié)點(diǎn)相似性度量,與分別表示字段值與,表示字段值,表示字段A中既關(guān)聯(lián)了又關(guān)聯(lián)了的字段值的集合,表示出現(xiàn)的次數(shù),表示出現(xiàn)的次數(shù),表示出現(xiàn)的次數(shù).

PA(Preferential Attachment )指數(shù)計(jì)算如式(16):

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

5.3 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

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

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

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

圖7 PA下節(jié)點(diǎn)相似性對比

圖8 AA下節(jié)點(diǎn)相似性對比

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

6　結(jié)論

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

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

福建省科技計(jì)劃重大項(xiàng)目(2016H6007)

2016-07-04;

2016-08-08

[10.15888/j.cnki.csa.005662]