逼真生成表格式數據的非時間屬性關聯模型

張 銳，肖如良，倪友聰，杜 欣

(1.福建師范大學 軟件學院，福州 350117； 2.福建省公共服務大數據挖掘與應用工程研究中心，福州 350117)(*通信作者電子郵箱xiaoruliang@163.com)

逼真生成表格式數據的非時間屬性關聯模型

張 銳1,2，肖如良1,2*，倪友聰1,2，杜 欣1,2

(1.福建師范大學 軟件學院，福州 350117； 2.福建省公共服務大數據挖掘與應用工程研究中心，福州 350117)(*通信作者電子郵箱xiaoruliang@163.com)

針對數據仿真過程中表格數據屬性間關聯難的問題，提出一種刻畫表格數據中非時間屬性間關聯特征的H模型。首先，從數據集中提取評價主體和被評價主體關鍵屬性，進行兩重頻數統計，得到關于關鍵屬性的4個關系對；然后，計算各關系對的最大信息系數(MIC)來評估各關系對的相關性，并采用拉伸指數分布(SE)對各關系對進行關系擬合；最后，設置評價主體和被評價主體的數據規模，根據擬合出的關系計算出評價主體的活躍度和被評價主體的流行度，通過活躍度總和等于流行度總和建立關聯，得到非時間屬性關聯的H模型。實驗結果表明，利用H模型能有效地刻畫真實數據集中非時間屬性間的關聯特征。

數據仿真；關聯；最大信息系數；拉伸指數分布；屬性關聯

0 引言

在大數據評測中，考慮到大數據集不易獲取，對大數據生成工具的研究引起了廣泛關注。文獻[1]提出，大數據生成器應該在保持真實數據特征的情況下，可以擴大或者縮小不同類型的數據集。大數據生成器應該能產生GB到PB級的數據量來滿足不同測試要求。文獻[2]提出，大數據生成器應該具有生成不同數據類型(結構化數據、半結構化數據和非結構化)，不同數據語義(文本、圖像、表格和多媒體)的功能。大數據生成器最重要的要求是能保持真實數據集中數據的特征。

當前學術界已有許多相關研究，總體看來，如何逼真地生成數據是這些相關研究的重心，其關鍵在于：如何刻畫數據集中表內屬性的特征，如何處理表內關鍵屬性間的關聯性，如何處理表與表之間的關聯性。表格數據屬性間的關聯分為與時間相關和非時間屬性相關的關聯。針對與時間相關的關聯已有許多成熟的研究。

本文針對表格數據中與非時間屬性相關的關聯性問題，創新性地通過最大信息系數(Maximum Information Coefficient, MIC)值評估字段間的相關性，采用拉伸指數(Stretched Exponential, SE)分布擬合，構建出表內非時間屬性關聯的H模型，從統計特性上刻畫非時間屬性間的關聯性，實驗結果表明H模型能保持真實數據集的統計特性。

1 相關工作

當前已有許多關于逼真生成表格數據的相關研究。

對單一屬性特征的刻畫一般有兩種方式：其一，通過隨機、枚舉或者數據字典的方式，主要作用于非關鍵屬性；其二，通過分布特征的刻畫方式，主要用于關鍵屬性。比如，Gray等[3]采用均勻分布、指數分布、正態分布、自相似分布刻畫關鍵屬性。典型的有Rabl等[4]使用β分布、二項指數分布、對數正態分布,泊松分布模擬關鍵屬性特征，設計了并行數據生成框架(Parallel Data Generation Framework, PDGF)；還有文獻[1]中提出的開源的大數據系統評測基準(open-source Big Data Benchmark suite, BigDataBench)、中國科學院計算所詹劍鋒等[2]研發的大數據基準的可擴展大數據生成器框架(scalable Big Data Generator Suite in big data benchmarking, BDGS)、雅虎公司[5]的云服務測試框架(Yahoo! Cloud Serving Benchmark, YCSB)、微軟公司[6]的多樣數據庫生成器(flexible database generators)等。

對于多表之間的關聯性研究，文獻[7]給出了一個網絡學習管理系統(見圖1)，其中主要包括三個表：學生信息表(主鍵為studentid)、課程信息表(主鍵為courseid)、學生選課信息表(主鍵為scid，外鍵為studentid和courseid)。首先生成學生選課信息表，然后根據學生選課信息表中的studentid和courseid分別生成學生信息表和課程信息表。這樣能保證學生選課信息表中的studentid來自學生信息表，courseid來自課程信息表。PDGF[4]框架中對多表之間的關聯也采用該方法。

圖1 網絡學習管理系統的一個實例

與時間有關的屬性間關聯性研究，需要為時間屬性建模(如自相似性、 多分形性等)，通過模擬時間相關屬性特征來生成數據。比如，浙江大學Yin等[8]研發的一種用于云計算的突發和自相似的工作負載生成器(a bursty and self-similar workload generator for cloud computing, BURSE)，根據數據的周期性、突發性特征來模擬數據的自相似性；法國凡爾賽大學Akrour等[9]利用多分形理論在不同單位時間內進行數據仿真；美國新澤西理工學院Ansari等[10]采用分數差分自回歸求和移動平均模型(Fractional AutoregRessive Integrated Moving-Average, FARIMA)對動態圖像(Moving Picture Experts Group, MPEG)中的I、P和B幀自相關結構進行建模。較為成熟的產品，加拿大西蒙菲沙大學 Jiang等[11]收集蜂窩數字包數據網絡中的業務數據，運用工具OPNET建模和仿真分析。

在表格形式的大規模數據生成研究工作中，已有許多學者做了大量的工作，特別是對表與表之間的關聯、某個屬性具有的特征、與時間屬性相關的特征關注比較多，而對非時間屬性間的關聯比較少。對非時間屬性間的關聯的研究，停留在相對粗糙的層面上。比如，文獻[12]中提出的一個用于評估Web代理緩存的綜合負載生成工具(synthetic Workload Generation tool for simulation evaluation of Web proxy caches, proWGen)采用的正/負相關來表達關聯、文獻[13]通過計算相關系數來表達關聯等。

綜上所述，在表格類型數據生成方面，對大數據生成器的研究已趨于成熟，但是對非時間字段相關性質研究中仍存在許多需要急于解決的困難問題。本文針對非時間字段的相關性，創新性提出了H模型，模擬不同應用背景下表格數據中非時間關鍵屬性間的相關性。

2 理論基礎

本章主要介紹構建模型所使用的到的理論基礎。

2.1 變量對間的相關性度量：MIC

在《Science》雜志上，Reshef等[14]通過網格劃分估計概率估計互信息的思想，提出最大信息系數(MIC)度量方式。Reshef等認為如果兩個變量存在某種關系，那么在它們構成的散點圖上一定存在一種網格劃分能概述出這個關系。此方法不僅能刻畫線性關系，還能很好地度量非線性關系，甚至是多種函數的疊加，具有廣泛性；對于不同關系類型，若噪聲相同，則MIC值也相同，具有公平性。

假設有n個變量對的數據集D，根據坐標軸把D分為(x×y)等份表示為G，用動態規劃算法求解的每次結果為D|G，那么D按照G這種劃分方式的最大互信息為：

I*(D,x,y)=maxI(D|G)

(1)

根據劃分的方式不同，可以得到一個的矩陣，對這個矩陣標準化得到：

(2)

在網格劃分細度下，矩陣中的最大值即為MIC值:

(3)

由于0≤I*(D,x,y)≤ln min{x,y}可得0≤MIC(D)≤1。當MIC值越接近1表示相關性越強，反之越弱。

2.2 分布擬合模型：SE分布

在人類行為動力學領域，韓筱璞等[15]對各種人類行為中的統計特性進行了廣泛的經驗研究，發現越來越多的多種形式的經驗性證據表明，許多人類行為的事件之間的時間間隔分布普遍存在寬尾特征。樊超等[16]的綜述中總結了人類在通信、訪問網絡、工作和自身生理特征4個方面表現出時間標度特征和遷移活動中表現出的空間標度特征，發現人類行為中一些普遍規律，并概述了產生重尾的動力學機制。從上述可以知道，人類行為可以通過統計特性來刻畫。

Guo等[17-18]對Web工作負載上不同類型(Web、VOD、P2P和其他)的16個數據集進行分析，發現Zipf-like分布不適合描述頻數與其排名的分布特征，而SE分布能對其進行很好的刻畫。因為針對非時間屬性間的關聯關系，將采用SE分布擬合。

Zipf分布函數為：

y=c/xa

(4)

為了方便用最小二乘法擬合，將函數變換成:

lny=lnc-alnx

(5)

SE分布的分布函數為：

y=e-(x/x0)c

(6)

其中：c為廣延參數，其參數范圍在(0,1),x0為尺度參數。為了方便用最小二乘法擬合，將分布函數變換成:

yc=-alnx+b

(7)

3 構建H模型

H模型的建模方法，其特征在于，首先從數據集中提取評價主體和被評價主體的關鍵屬性，進行兩重頻數統計，得到基于關鍵屬性的4個關系對：評價主體的活躍度與活躍度排名的關系、評價主體的活躍度與其出現頻數的關系、被評價主體的流行度與流行度排名的關系和被評價主體的流行度與其出現頻數的關系；然后計算各關系對的MIC值來評估各關系對的相關性，并采用SE分布對各關系對進行關系擬合；通過擬合的關系得到評價主體的屬性特征與其數據規模的關系，即評價主體的活躍度與其出現頻數關系和評價主體的數據規模的關系，以及被評價主體的屬性特征與其數據規模的關系，即流行度與其出現頻數關系和被評價主體的數據規模的關系，并將這兩個屬性特征通過活躍度總和等于流行度總和建立關聯，得到非時間屬性關聯的H模型，如圖2所示。

圖2 H模型

在圖2中，Freq表示活躍度，UserCount表示評價主體的數據規模，Popu表示流行度，ItemCount表示被評價主體的數據規模。式(8)表示評價主體活躍度總和等于被評價主體流行度總和。

(8)

通過評價主體的活躍度(Freq)與其頻數(FreqFreq)的SE分布關系，可以得到評價主體活躍度對應的頻數，所有活躍度對應的頻數總和是評價主體的數據規模UserCount：

(9)

通過被評價主體流行度(Popu)與其頻數(PopuFreq)的SE分布關系，可以得到被評價主體的流行度對應的頻數，所有流行度對應的頻數總和是被評價主體的數據規模ItemCount：

(10)

構建H模型具體步驟如下。

步驟1 從數據集中提取關鍵屬性，包括評價主體id和被評價主體id；

步驟2 對評價主體id出現的頻次作頻數統計得到評價主體的活躍度，對被評價對象id出現的頻次作頻數統計得到被評價對象的流行度，對活躍度降序排列得到相應的活躍度排名，對流行度降序排列得到相應的流行度排名，對活躍度出現的頻次作頻數統計得到活躍度與其出現的頻數，對流行度出現的頻次作頻數統計得到流行度與其出現的頻數，從而得到以下4個關系：活躍度與活躍度排名的關系、活躍度與其出現頻數的關系、流行度與流行度排名的關系和流行度與其出現頻數的關系；

步驟3 分別對得到的4個關系計算MIC值，得到4個關系的MIC值，以度量各個關系中兩個字段間的相關性；

步驟4 對應于4個關系分別預設4個閾值，比較4個MIC值是否都不小于預設的閾值，是則進行下一步驟，否則此模型不適用，建模結束；

步驟5 采用SE分布對得到的4個關系進行擬合，得到4個關系的SE分布參數；

步驟6 設置評價主體的數據規模和被評價主體的數據規模；

步驟7 在活躍度排名的取值范圍內隨機取一個數作為活躍度排名，通過活躍度與活躍度排名關系的SE分布，得到活躍度，進一步通過活躍度與其出現頻數關系的SE分布，得到活躍度對應的出現頻數；

步驟8 對步驟7得到的頻數求和，判斷總數是否等于評價主體的數據規模，是則轉下一步驟，否則重復步驟7；

步驟9 將活躍度乘以其對應的出現頻數得到活躍度總和；

步驟10 采用與步驟7、8同樣的方法，得到流行度對應的出現頻數，然后將流行度乘以其對應的出現頻數得到流行度總和；

步驟11 判斷步驟10得到的活躍度總和是否等于步驟9得到的流行度總和，是則建模完成，否則重復步驟10。

4 H模型的驗證與分析

實驗目的是驗證H模型能否刻畫真實數據集中非時間屬相間的關聯特征。構造H模型的關鍵是對其中4個關系關聯度的度量和對這4個關系的擬合。因此驗證這4個關系有較強的關聯度、能較好地擬合這4個關系，即能說明H模型能有效地刻畫真實數據集中非時間屬性的關聯特征。

實驗分為2步：首先驗證H模型中的4個關系具有較強的關聯度，此關聯度通過MIC值來評估；其次證明SE分布能有效地擬合這4個關系，用決定系數(R2)來評估擬合程度。

4.1 數據集描述

實驗選取6個真實數據集：MovieLens-1M、MovieLens-20M、Lastfm、Book-Crossing、Amazon-Movie、Amazon-Music。 這些數據集具有較好的代表性。主要表現在：1)數據集來源于可靠而權威的機構或組織，比如，明尼蘇達大學的社會計算研究；2)在各自所在的應用領域內，數據作為常用數據源被多次使用，如MovieLens數據集在推薦系統實驗中廣泛使用；3)結合大數據的數據特性，針對表這種數據語義，考慮到數據的數據類型，實驗中涵蓋了結構化和半結構化數據類型；4)來自同一系統的不同數據集不同大小，不同時間段。比如，MoiveLens不同時期不同大小的數據1 MB和20 MB數據集，亞馬遜的用戶對電影和音樂的評論信息。表1對各個數據集進行了簡單介紹。

MovieLens-1M數據集是結構化數據，包含2003年2月期間6 040位用戶對3 900部電影的1 000 209條評分記錄。

MovieLens-20M數據集是結構化數據，包含1995年1月—2015年3月期間138 493位用戶對27 278部電影的20 000 263條評分記錄。

Lastfm數據集是結構化數據集，包含1 892位用戶對17 632位藝術家的186 479個標簽信息。

Book-Crossing數據集是結構化數據集，包含2004年8月—9月期間278 858位用戶對2 713 798部書籍的1 149 780條評分記錄。

亞馬遜電影評論(Amazon-Movie)數據集是半結構化數據集，包含1996年5月—2014年7月期間的4 607 047條評論記錄。

亞馬遜數字音樂評論(Amazon-Music)數據集是半結構化數據集，包含1996年5月—2014年7月期間的836 006條評論記錄。

表1 實驗數據集

4.2 實驗過程及結果分析

構建H模型的4個關系為評價主體的活躍度與活躍度排名的關系、評價主體的活躍度與其出現頻數的關系、被評價主體的流行度與流行度排名的關系和被評價主體的流行度與其出現頻數的關系，依次表示為Rank-Freq、Rank-Popu、FreN-Freq、Popu-Freq。實驗結果如表2。

表2 實驗結果

對6個真實數據集分別按照H模型的構建過程得到這4個關系的數據，然后對其計算MIC值。實驗結果表2，表明6個數據集中Rank-Freq關系的MIC值都為1，Rank-Popu關系的MIC值都為1，FreN-Freq關系的平均值為0.776，Popu-Freq關系的平均值為0.724，說明這四個關系都有較強的相關性。特別是前兩個關系的MIC值都接近于1，表明有很強的相關性。

采用MovieLens-1M數據集為例說明SE分布和Zipf分布擬合的效果，如圖3～6所示。從實驗結果得出，這4個關系無論哪一個，SE分布的決定系數都比Zipf分布的更接近于1，說明SE分布比Zipf分布能夠更好地刻畫這4個關系。

圖3 MovieLens-1M數據集Rank-Freq散點圖

圖4 MovieLens-1M數據集Rank-Popu散點圖

圖5 MovieLens-1M數據集FreN-Freq散點圖

圖6 MovieLens-1M數據集Popu-Freq散點圖

實驗結果表2，表明在6個數據集中用SE分布擬合，Rank-Freq關系決定系數的平均值為0.983，Rank-Popu關系決定系數的平均值為0.985，FreN-Freq關系決定系數的平均值為0.869，Popu-Freq關系決定系數的平均值為0.872，說明用SE分布擬合這4個關系效果明顯。

實驗結果顯示，后兩個關系MIC值普遍比前兩個關系的MIC值低。從MovieLens-1M數據集中的4個關系的散點圖，如圖3～6所示，可以得出是因為數據集噪聲量比較大造成的，這也導致函數的擬合程度低于前兩個關系。在Popu-Freq這個關系的SE分布擬合圖像中，很明顯前幾個值的擬合程度非常地差，這是由于對被評價主體可以分為高頻和低頻所致。

從實驗結果可以得出4個關系有較強的相關性，并能用SE分布擬合，即說明H模型能有效地刻畫真實數據集中非時間屬性的關聯特征。

5 結語

在數據測評時，經常需要根據小的真實數據集擴展生成與真實大數據集逼真的新數據。本文針對生成表格數據技術中的非時間屬性相關性，提出H模型。H模型首先提取關鍵的4個關系，然后用MIC度量相關性，并用SE分布擬合，使得表格數據非時間屬性間的關聯特征更加明確。實驗結果表明，H模型能有效地刻畫表內非時間屬性間的關聯特性。非時間屬性的關聯技術是表格數據生成的重要組成部分，對表格數據的逼真生成軟件的研發，提供了可靠的數據生成模型。然而，噪聲也是數據的一部分，對噪聲的注入也是數據真實性的一種體現，因此如何注入噪聲是下一步要做的工作。

References)

[1] MING Z, LUO C, GAO W, et al. BDGS: a scalable big data generator suite in big data benchmarking [C]// Advancing Big Data Benchmarks, LNCS 8585. Berlin: Springer, 2014: 138-154.

[2] 詹劍鋒,高婉鈴,王磊,等.BigDataBench:開源的大數據系統評測基準[J].計算機學報,2016,39(1):196-211.(ZHAN J F, GAO W L, WANG L, et al. Bigdatabench: an open-source big data benchmark suite [J]. Chinese Journal of Computers, 2016, 39(1): 196-211.)

[3] GRAY J, SUNDARESAN P, ENGLERT S, et al. Quickly generating billion-record synthetic databases [J]. ACM SIGMOD Record, 1994, 23(2): 243-252.

[4] RABL T, FRANK M, SERGIEH H M, et al. A data generator for cloud-scale benchmarking [C]// Proceedings of the 2nd TPC Technology Conference on Performance Evaluation, Measurement and Characterization of Complex Systems. Berlin: Springer, 2010: 41-56.

[5] COOPER B F, SILBERSTEIN A, TAM E, et al. Benchmarking cloud serving systems with YCSB [C]// Proceedings of the 1st ACM Symposium on Cloud Computing. New York: ACM, 2010: 143-154.

[6] BRUNO N, CHAUDHURI S. Flexible database generators [C]// Proceedings of the 31st International Conference on Very Large Data Bases. Trondheim, Norway: VLDB Endowment, 2005: 1097-1107.

[7] RABL T, LANG A, HACKL T, et al. Generating shifting workloads to benchmark adaptability in relational database systems [M]// Technology Conference on Performance Evaluation and Benchmarking, LNCS 5895. Berlin: Springer, 2009: 116-131.

[8] YIN J, LU X, ZHAO X, et al. BURSE: a bursty and self-similar workload generator for cloud computing [J]. IEEE Transactions on Parallel & Distributed Systems, 2015, 26(3): 668-680.

[9] AKROUR N, MALLET C, BARTHES L, et al. A rainfall simulator based on multifractal generator [EB/OL]. [2016- 12- 04]. http://meetingorganizer.copernicus.org/EGU2015/EGU2015-9488.pdf.

[10] ANSARI N, LIU H, SHI Y Q, et al. On modeling MPEG video traffics [J]. IEEE Transactions on Broadcasting, 2002, 48(4): 337-347.

[11] JIANG M, NIKOLIC M, HARDY S, et al. Impact of self-similarity on wireless data network performance [C]// Proceedings of the 2001 IEEE International Conference on Communications. Piscataway, NJ: IEEE, 2001: 477-481.

[12] BUSARI M, WILLIAMSON C. ProWGen: a synthetic workload generation tool for simulation evaluation of Web proxy caches [J]. Computer Networks, 2002, 38(6): 779-794.

[13] 丘志鵬,肖如良,張銳.優先關聯的Web日志數據逼真生成算法[J].計算機系統應用,2017,26(3):126-133.(QIU Z P, XIAO R L, ZHANG R. Simulate generating Web log algorithm using Fields’ priority relevance [J]. Computer Systems and Applications, 2017, 26(3): 126-133.)

[14] RESHEF D N, RESHEF Y A, FINUCANE H K, et al. Detecting novel association in large data sets [J]. Science, 2011, 334(6062): 1518-1524.

[15] 韓筱璞,汪秉宏,周濤.人類行為動力學研究[J].復雜系統與復雜性科學,2010,7(2):132-144.(HAN X P, WANG B H, ZHOU T. Researches of human dynamics [J]. Complex Systems and Complexity Science, 2010, 7(2): 132-144.)

[16] 樊超,郭進利,韓筱璞,等.人類行為動力學研究綜述[J].復雜系統與復雜性科學,2011,8(2):1-17.(FAN C, GUO J L, HAN X P, et al. A review of research on human dynamics [J]. Complex Systems and Complexity Science, 2011, 8(2): 1-17.)

[17] GUO L, TAN E, CHEN S, et al. The stretched exponential distribution of Internet media access patterns [C]// Proceedings of the 27th ACM Symposium on Principles of Distributed Computing. New York: ACM, 2008: 283-294.

[18] GUO L, TAN E, CHEN S, et al. Analyzing patterns of user content generation in online social networks [C]// Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2009: 369-378.

Not-temporalattributecorrelationmodeltogeneratetabledatarealistically

ZHANG Rui1,2, XIAO Ruliang1,2*, NI Youcong1,2, DU Xin1,2

(1.FacultyofSoftware,FujianNormalUniversity,FuzhouFujian350117,China;2.FujianProvincialEngineeringResearchCenterofPublicServiceBigDataMiningandApplication,FuzhouFujian350117,China)

To solve the difficulty of attribute correlation in the process of simulating table data, an H model was proposed for describing not-temporal attribute correlation in table data. Firstly, the key attributes of the evaluation subject and the evaluated subject were extracted from the data set, by the twofold frequency statistics, four relationships of the key attributes were obtained. Then, the Maximum Information Coefficient (MIC) of each relationship was calculated to evaluate the correlation of each relationship, and each relationship was fitted by the Stretched Exponential (SE) distribution. Finally, the data scales of the evaluation subject and the evaluated subject were set. According to the result of fitting, the activity of the evaluation subject was calculated, and the popularity of the evaluated subject was calculated. H model was obtained through the association that was established by equal sum of activity and popularity. The experimental results show that H model can effectively describe the correlation characteristics of the non-temporal attributes in real data sets.

data simulation; correlation; Maximum Information Coefficient (MIC); Stretched Exponential (SE) distribution; attribute correlation

2017- 03- 29;

2017- 05- 16。

福建省科技計劃重大項目(2016H6007)；福州市市校合作項目(2016-G-40)。

張銳(1992—)，男，湖北孝感人，碩士研究生，主要研究方向：大數據軟件； 肖如良(1966—)，男，湖南婁底人，教授，博士，CCF高級會員，主要研究方向：大數據軟件、Web智能推薦系統、軟件工程、系統虛擬化； 倪友聰(1976—)，男，安徽合肥人，副教授，博士，主要研究方向：軟件體系結構、移動云計算； 杜欣(1979—)，女，新疆石河子人，副教授，博士，主要研究方向：智能計算、計算復雜性、基于搜索的軟件工程。

1001- 9081(2017)09- 2684- 05

10.11772/j.issn.1001- 9081.2017.09.2684

TP311.1

A

This work is partially supported by the Major Project of Fuijian Provincial Science and Technology Plan (2016H6007), Fuzhou City School Cooperation Project (2016-G-40).

ZHANGRui, born in 1992, M. S. candidate. His research interests include big data software.

XIAORuliang, born in 1966, Ph. D., professor. His research interests include big data software, Web intelligent recommendation system, software engineering, system virtualization.

NIYoucong, born in 1966, Ph. D., associate professor. His research interests include software architecture, mobile cloud computing.

DUXin, born in 1979, Ph. D., associate professor. Her research interests include computational intelligence, computational complexity, search-based software engineering.