2. 福建省公共服务大数据挖掘与应用工程研究中心, 福州 350117
2. Fujian Provincial Engineering Research Center of Public Service Big Data Mining and Application, Fuzhou Fujian 350117, China
在大数据评测中，考虑到大数据集不易获取，对大数据生成工具的研究引起了广泛关注。文献[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 网络学习管理系统的一个实例 Figure 1 An instance of e-learning management system |
与时间有关的属性间关联性研究，需要为时间属性建模(如自相似性、多分形性等)，通过模拟时间相关属性特征来生成数据。比如，浙江大学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) = \max I(D{|_G})$ | (1) |
根据划分的方式不同，可以得到一个的矩阵，对这个矩阵标准化得到：
| $M{(D)_{x,y}} = \frac{{{I^ * }(D,x,y)}}{{\ln \;\min \left\{ {x,y} \right\}}}$ | (2) |
在网格划分细度下，矩阵中的最大值即为MIC值:
| $MIC(D) = \mathop {\max }\limits_{xy ＜ B(n)} \left\{ {M{{(D)}_{x,y}}} \right\}$ | (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/{x^a}$ | (4) |
为了方便用最小二乘法拟合，将函数变换成:
| $\ln y = \ln c - a\ln x$ | (5) |
SE分布的分布函数为：
| $y = {e^{ - {{\left( {x/{x_0}} \right)}^c}}}$ | (6) |
其中：c为广延参数，其参数范围在(0, 1), x0为尺度参数。为了方便用最小二乘法拟合，将分布函数变换成:
| ${y^c} = - a\;\ln \;x + b$ | (7) |
其中：a=x0c，b=y1c。
3 构建H模型H模型的建模方法，其特征在于，首先从数据集中提取评价主体和被评价主体的关键属性，进行两重频数统计，得到基于关键属性的4个关系对：评价主体的活跃度与活跃度排名的关系、评价主体的活跃度与其出现频数的关系、被评价主体的流行度与流行度排名的关系和被评价主体的流行度与其出现频数的关系；然后计算各关系对的MIC值来评估各关系对的相关性，并采用SE分布对各关系对进行关系拟合；通过拟合的关系得到评价主体的属性特征与其数据规模的关系，即评价主体的活跃度与其出现频数关系和评价主体的数据规模的关系，以及被评价主体的属性特征与其数据规模的关系，即流行度与其出现频数关系和被评价主体的数据规模的关系，并将这两个属性特征通过活跃度总和等于流行度总和建立关联，得到非时间属性关联的H模型，如图 2所示。
|
图 2 H模型 Figure 2 H model |
在图 2中，Freq表示活跃度，UserCount表示评价主体的数据规模，Popu表示流行度，ItemCount表示被评价主体的数据规模。式(8) 表示评价主体活跃度总和等于被评价主体流行度总和。
| $\sum\limits_{i = 1}^{UserCount} {\mathit{\boldsymbol{Freq}}} \; = \;\sum\limits_{j = 1}^{ItemCount} {\mathit{\boldsymbol{Popu}}} $ | (8) |
通过评价主体的活跃度(Freq)与其频数(FreqFreq)的SE分布关系，可以得到评价主体活跃度对应的频数，所有活跃度对应的频数总和是评价主体的数据规模UserCount：
| $\sum\limits_{i = 1}^n {\mathit{\boldsymbol{FreqFreq}}\; = \;UserCount} $ | (9) |
通过被评价主体流行度(Popu)与其频数(PopuFreq)的SE分布关系，可以得到被评价主体的流行度对应的频数，所有流行度对应的频数总和是被评价主体的数据规模ItemCount：
| $\sum\limits_{j = 1}^m {\mathit{\boldsymbol{PopuFreq}}\; = \;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对各个数据集进行了简单介绍。
|
表 1 实验数据集 Table 1 Experiment data set |
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条评论记录。
4.2 实验过程及结果分析构建H模型的4个关系为评价主体的活跃度与活跃度排名的关系、评价主体的活跃度与其出现频数的关系、被评价主体的流行度与流行度排名的关系和被评价主体的流行度与其出现频数的关系，依次表示为Rank-Freq、Rank-Popu、FreN-Freq、Popu-Freq。实验结果如表 2。
|
|
表 2 实验结果 Table 2 Experimental result |
对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散点图 Figure 3 Rank-Freq scatter diagram of MovieLens-1M |
|
图 4 MovieLens-1M数据集Rank-Popu散点图 Figure 4 Rank-Popu scatter diagram of MovieLens-1M |
|
图 5 MovieLens-1M数据集FreN-Freq散点图 Figure 5 FreN-Freq scatter diagram of MovieLens-1M |
|
图 6 MovieLens-1M数据集Popu-Freq散点图 Figure 6 Popu-Freq scatter diagram of MovieLens-1M |
实验结果表 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模型能有效地刻画表内非时间属性间的关联特性。非时间属性的关联技术是表格数据生成的重要组成部分，对表格数据的逼真生成软件的研发，提供了可靠的数据生成模型。然而，噪声也是数据的一部分，对噪声的注入也是数据真实性的一种体现，因此如何注入噪声是下一步要做的工作。
| [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. DOI:10.11897/SP.J.1016.2016.00196) |
| [3] | GRAY J, SUNDARESAN P, ENGLERT S, et al. Quickly generating billion-record synthetic databases[J]. ACM SIGMOD Record, 1994, 23(2): 243-252. DOI:10.1145/191843 |
| [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. DOI:10.1109/TBC.2002.806794 |
| [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. DOI:10.1016/S1389-1286(01)00285-7 |
| [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. DOI:10.1126/science.1205438 |
| [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. |