一种基于稳态过程的多重分形Web日志的逼真生成方法

摘要

本发明涉及一种基于稳态过程的多重分形Web日志的逼真生成方法，包括以下步骤：生成用户集合和Web文件集合，并关联用户和Web文件形成原始请求序列

说明书

技术领域

本发明涉及大数据集仿真生成技术领域，特别涉及一种基于稳态过程的多重分形Web日志的逼真生成方法，可以有效地应用于Web日志大规模数据集的仿真生成。

背景技术

在Web服务器性能测试中，分析Web日志特征对于服务器性能评测与决策有着重要意义。然而Web日志中包含用户隐私信息，企业及政府等机构极少愿意公开日志供研究人员使用；现有已公开的Web日志数据年代久远，其特征不符合当前大数据时代特征。随着数据规模的增大，生成有代表性却不失一般性的大规模数据集是有困难的，而单一的传统仿真模型很难表现出多种复杂Web日志一般性特征。如何生成逼真且一般性可控的Web日志大规模数据集，是学术界的热点问题。

以ON/OFF模型为代表的自相似模型，将自相似过程看成是无数用户数据源采用独立同分布形式叠加的结果，这种模型能对自相似现象给出明确的物理解释，但是在构造模型的过程中做了很多前提假设（如，文件大小分布是重尾的，那么访问文件所需要的时间也是重尾的），且这些前提假设条件常常与实际情况不相符合，这使得流叠加模型难以对实际流量进行仿真。随着非线性动力学的发展，通过对Web日志序列的研究发现其中含有丰富的非线性特性，逐渐开始采用计算智能的相关理论进行分析，其中以MWM（Multi-fractalWaveletModel，多分形小波模型）为代表的多重分形模型，通过将Web日志分为高频和低频，有效地揭示了突发性流量的局部较精细的本质特征。但是这类方法是建立在重构相空间（Web日志模型的非线性特征量的提取及分析）的基础上，预测结果受相空间形状的影响。如果参数选取不合适，就有可能产生较大误差。

发明内容

本发明的目的在于提供一种基于稳态过程的多重分形Web日志的逼真生成方法，该方法可以兼顾自相似性和多重分形性，从而准确地模拟真实的Web日志。

为实现上述目的，本发明的技术方案是：一种基于稳态过程的多重分形Web日志的逼真生成方法，包括以下步骤：

步骤1：生成每个用户的属性并形成用户集合U={u₁,u₂,……,u_n}，n表示用户数，u_n表示第n个用户；

步骤2：生成每个Web文件的属性并形成Web文件集合I={i₁,i₂,……,i_m}，m表示Web文件数，u_m表示第m个Web文件；

步骤3：关联用户和Web文件形成原始请求序列R={r₁,r₂,……,r_q}，q表示原始请求序列中Web日志数量，r_q表示第q条Web日志；

步骤4：采用alpha稳态过程拟合用户到达模型，计算用户的到达时间间隔∆T，作为改进的ON/OFF模型的被动OFF时间，到达时间间隔∆T表示两次用户到达时刻之间的时间间隔；

步骤5：将原始请求序列R变成由多个用户请求序列构成的用户集合R={R₁,R₂,…,R_u,…,R_n}，其中n表示用户总数量，每个用户形成一个用户请求序列R_u={r_u1,r_u2,……,r_uk}，k表示集合R_u的总序列长度，r_uk表示用户u访问的第k个文件，也即一个用户u对应k个文件，所述k个文件中可以存在重复文件；遍历每一个用户u，并记录遍历开始的时间currentTime，用于序列R_u的时间分配；

步骤6：判断遍历是否结束，是则本方法结束，否则转步骤7；

步骤7：判断用户请求序列R_u是否为空，是则转步骤8，否则返回步骤5；

步骤8：找到连续访问个数s=1；

步骤9：取出用户请求序列R_u中用户最感兴趣的前s个文件，组成连续访问序列Y_u={r_u1,r_u2,…,r_us}；

步骤10：采用二项式b模型分离连续访问序列Y_u为连续访问时间序列Y_u’={y_u1,y_u2,…,y_ut}，其中t表示Y_u’的时间区间数量，y_ut表示t时间区间内用户u的连续访问序列，并以Y_u’的每个元素的访问时间间隔∆t作为改进的ON/OFF模型的主动OFF时间，访问时间间隔∆t表示第i个文件和第i+1个文件在传输过程中的时间间隔；

步骤11：将连续访问时间序列Y_u’加入到用户的新访问序列R_u’={Y_u1’,Y_u2’,…,Y_ul’}中，其中Y_ul’表示第l次加入的连续访问时间序列；

步骤12：从用户请求序列R_u中删除所述前s个文件。

本发明的有益效果是提出了一种基于稳态过程的多分形Web日志逼真生成方法，它以alpha稳态模型代替幂律模型在大时间尺度下建立Web日志中的用户到达模型，更加符合其分布的特征，同时以简单的二项式b模型在小时间尺度下进行二项式分形，将这两个模型通过改进的ON/OFF模型进行融合，以达到同时提高Web日志仿真的自相似性和多分形性的目的，从而有效地应用于Web日志大数据集的仿真生成。同时，该方法的各项参数物理意义明确，能够方便研究人员应用于不同的Web服务器上。

附图说明

图1是本发明实施例的实现流程图。

图2是本发明实施例中改进后的ON/OFF模型。

具体实施方式

本发明提供一种基于稳态过程的多重分形Web日志的逼真生成方法，如图1所示，包括以下步骤：

步骤1：生成每个用户的属性并形成用户集合U={u₁,u₂,……,u_n}，n表示用户数，u_n表示第n个用户；

步骤2：生成每个Web文件的属性并形成Web文件集合I={i₁,i₂,……,i_m}，m表示Web文件数，u_m表示第m个Web文件；

步骤3：关联用户和Web文件形成原始请求序列R={r₁,r₂,……,r_q}，q表示原始请求序列中Web日志数量，r_q表示第q条Web日志；

步骤4：采用alpha稳态过程拟合用户到达模型，计算用户的到达时间间隔∆T，作为改进的ON/OFF模型的被动OFF时间，到达时间间隔∆T表示两次用户到达（发生点击事件）时刻之间的时间间隔；

步骤5：将原始请求序列R变成由多个用户请求序列构成的用户集合R={R₁,R₂,…,R_u,>R_n}，其中n表示用户总数量，每个用户形成一个用户请求序列R_u={r_u1,r_u2,……,r_uk}，k表示集合R_u的总序列长度，r_uk表示用户u访问的第k个文件，也即一个用户u对应k个文件，所述k个文件中可以存在重复文件；遍历每一个用户u，并记录遍历开始的时间currentTime，用于序列R_u的时间分配；

步骤6：判断遍历是否结束，是则本方法结束，否则转步骤7；

步骤7：判断用户请求序列R_u是否为空，是则转步骤8，否则返回步骤5；

步骤8：找到连续访问个数s=1；

步骤9：取出用户请求序列R_u中用户最感兴趣的前s个文件，组成连续访问序列Y_u={r_u1,r_u2,…,r_us}；

步骤10：采用二项式b模型分离连续访问序列Y_u为连续访问时间序列Y_u’={y_u1,y_u2,…,>y_ut}，其中t表示Y_u’的时间区间数量，y_ut表示t时间区间内用户u的连续访问序列，并以Y_u’的每个元素的访问时间间隔∆t作为改进的ON/OFF模型的主动OFF时间，访问时间间隔∆t表示第i个文件和第i+1个文件在传输过程中由于网络延迟等原因造成的时间间隔；

步骤11：将连续访问时间序列Y_u’加入到用户的新访问序列R_u’={Y_u1’,Y_u2’,…,Y_ul’}中，其中Y_ul’表示第l次加入的连续访问时间序列；

步骤12：从用户请求序列R_u中删除所述前s个文件。

下面对本发明涉及的相关内容作进一步的说明。

1、alpha稳态

对多组典型Web日志研究结果表明：一方面，由于应用类型不同，有的Web日志的到达模型是独立同分布的，有的Web日志到达模型则具有自相似性；另一方面，即使同样具有自相似性，有的Web日志具有高斯性，而有的Web日志体现出非高斯性。Zou等人提出了一种基于alpha稳态过程的流量模型，它既能有效刻画自相似流量中的高斯性和非高斯性，又能精确模拟各种Web服务器中的流量突发行为。之所以alpha稳态具有准确的仿真性能，是因为相对于传统方法使用的幂律分布，alpha稳态更适合于描述Web日志。随着对大量数据的调查发现，所谓的幂律仅仅适用于分布曲线的尾端部分(即x很大的部分)。另外Yakovenko等人用美国真实税收情况估计出的收入分布曲线也表明：当取坐标为双对数时，曲线尾端是直线，即幂律分布；当取半对数(y轴为对数)时，曲线顶端为直线，即指数分布。向这种尾端趋近于幂律分布，而在头端(x->0)偏离幂律，趋向于指数分布的曲线，数学家Nolan指出alpha稳态分布正好具备这种性质。即：一个随机变量X被称为具有稳定分布，若存在参数0<α≤2，σ>0，-1≤β≤1，μ∈R，使得其特征函数E的形式如公式(1)所示：

公式(1)中，sign(·)为符号函数，特征指数α表示分布中的突发程度，偏斜参数(the skewness parameter)β表示分布的尾部变化情况。如果β≠0，说明相应的密度函数是偏斜的：取负值表示密度函数偏斜向左尾部(left-tail)；反之，则表示密度函数偏斜向右尾部(right-tail)。由此可见，整个分布函数的基本形状是由参数α和β决定的。同时，尺度参数(scale parameters)σ表示分布的方差，位置参数(location parameters)μ表示分布的均值。习惯上，将具有上述参数且服从alpha稳态分布的随机变量简记为。由公式(1)可知，当α＝2时，有公式(2)所示：

此时，alpha稳态的特征函数E退化为高斯特征函数，相应的均值为μ，方差为2σ²，β无意义，因为在公式(1)中，βtanπ＝0恒成立。当0<α<2时，公式(1)表示一种非高斯特>

2、二项式b模型

对于自相似Web日志，短时间范围内的局部突发对Web服务器性能的影响更大。由于适用于描述大时间尺度上突发行为的传统自相似模型，通常难以准确描述小时间尺度上的突发行为，因此B.Hong等人用二项式多分形来描述小时间尺度的突发行为。多分形其实就是单分形自相似过程在时间相关尺度下的扩展。对于时间尺度为1的单位区间I=[0,1]，Web日志序列为Y，首先将I分离成两个等长的子区间I₀=[0,1/2]和I₁=[1/2,1]，根据偏置参数b∈[0.5,1）将Y划分到两个子区间中，则Y₀=bY,Y₁=(1-b)Y。然后，将I₀分离成两个等长的子区间I₀₀=[0,1/4]和I₀₁=[1/4,1/2]，将Y₀划分到I₀₀和I₀₁中分别为Y₀₀=b²Y₀,Y₀₁=b(1-b)Y₀。一般地，对于时间区间t的Web日志序列为Y_t，第n次分离后的某个小区间中Web日志序列为Y_tⁿ，则第n+1次分离即将Y_tⁿ一分为二，利用公式（3）和（4）来计算分离后两个子区间的Web日志。

公式(3)

公式(4)

二项式b模型近似于“二八定律”：20%的操作中包含80%的数据。在二项式b模型中，如偏置参数b=0.8意味着在一个给定的时间间隔内，80%的流量只占时间间隔的一半（剩余20%占时间间隔的另一半）。然后这个过程反复递归，通过偏置参数b反映流量的局部突发行为，因此偏置参数b具有一定的物理意义。在实际中使偏置参数b为0.5到1之间的随机数，这样能增加分形的复杂性。

3、基于UAS（UserArrivebasedonalphaStableprocess，基于alpha稳态过程的用户到达模型）的多重分形Web日志大规模数据集的逼真生成方法

在单分形模型中，ON/OFF模型因其构造简单而受到广泛使用，然而其假设存在与真实流量不符合的现象，因此本发明提出一种基于UAS的多重分形Web日志仿真生成方法。改进的ON/OFF模型如图2所示。

图2中T_u时刻表示某Web日志中某用户u到达（发生点击事件）的时刻，T_(u+1)时刻表示用户u访问结束，下一个用户（u+1）到达的时刻，将两次用户到达时刻之间的时间间隔∆T_u称为用户间隔，也称为Web对象被动OFF时间。用户的一次点击行为引发服务器发送多个Web文件，第i个文件和第i+1个文件在传输的过程中由于网络延迟等造成访问时间间隔∆t_i，也称为主动OFF时间。

可以使用alpha稳态分布生成用户间隔∆T，对于文件间隔∆t，传统的做法是采用幂律分布来建立数学模型，然而在Web服务器端收集到的用户访问Web文件时间仅为Web服务器发送Web文件时间，却没有用户访问Web时间。不同的Web服务器性能也会导致这种数学模型缺乏一般性，同时也无法表现出Web日志的多重分形特性。在实际中，主动OFF时间比被动OFF时间小很多，属于小时间尺度，本发明将二项式b模型用在小时间尺度的Web日志中。改进方法为在ON/OFF模型模拟文件间隔∆t时采用二项式b模型，具体做法如下：

对NASA网站数据分析发现，用户发出连续动作次数概率近似服从Zipf定律。假设用户u的总请求序列是R_u={r_u1,r_u2,……，r_ui}，其中r_ui为用户u访问的第i个Web文件，则第i个Web文件被访问的概率为p(r_ui)=i^ω。利用最小二乘法拟合可得ω=-0.924。这个结果与ω=-1>Zipf定律非常接近。由此可知在Web对象中，用户连续访问2个以上Web文件的概率低于60%，而用户连续访问16个以上Web文件的概率已经非常接近于0。将时间∆T_u内的流量进行n次分离即是二项式分形，但实际中的n存在限制。根据二项式b模型的偏置参数b∈(0.5,1)，不可能存在用户连续访问的16个文件都能独占一个时间区间，从而二项式分离次数0≤n≤4。

当确定用户u的连续访问序列长度s后，从R_u中取出前s个Web文件，组成用户u当前连续访问序列Y_u，随机选择二项式分离次数n，对每个用户到达时间间隔∆T_u以及连续访问的文件序列Y_u，建立一棵高度为n+1的满二叉树Tree_u,将∆T_u分为z=2ⁿ个相等区间，计算每个区间内的Web文件数量，先序遍历Tree_u的叶子节点组成的时间序列Y_u^’={y_u1^’,>y_u2^’,…,>y_ut^’,…,>y_uz^’}，其中y_ut^’表示第t个时间区间内用户访问的Web文件数量，用户访问Web文件时间为∆T_u+t*∆T_u/z，则Y_u^’是用户u的一个含有多分形特性的Web对象。

基于以上分析，提出了本发明的基于UAS的多重分形Web日志仿真生成方法，该方法通过改进的ON/OFF模型，利用alpha稳态过程模拟用户到达时间间隔∆T，利用二项式b模型模拟用户连续访问Web文件时间间隔∆t，算法流程如图1所示。

以上是本发明的较佳实施例，凡依本发明技术方案所作的改变，所产生的功能作用未超出本发明技术方案的范围时，均属于本发明的保护范围。