一种基于用户兴趣迁移的大数据集仿真生成方法

摘要

本发明涉及一种基于用户兴趣迁移的大数据集仿真生成方法，包括以下步骤：生成用户集合和Web文件集合，然后关联用户和Web文件形成原始请求序列R，将原始请求序列R变成由多个用户请求序列构成的用户集合，每个用户形成一个用户请求序列R

说明书

技术领域

本发明涉及大数据集仿真生成技术领域，特别涉及一种基于用户兴趣迁移的大数据集仿真生成方法，可以有效地应用于Web日志的仿真生成。

背景技术

随着大数据规模的大幅扩大，给数据处理的服务平台带来不可预知的后果。如在2012年美国总统选举时，Twitter因无法承受着有史以来最大的访问量而崩溃。对Web服务日志的分析，不仅能够帮助服务平台有效预防网络异常的产生，也能对服务平台进行压力测试分析，有利于提升服务平台的可靠性。然而Web日志中包含用户隐私信息，企业及政府等机构极少愿意公开日志供研究人员使用；同时，现已公开的Web日志数据年代久远，其特征不符合当前大数据时代特征。如何仿真生成逼真的Web日志，是学术界的热点问题。

以中科院的BDGS为代表的Web日志生成器不仅能够用于Web服务器压力测试和性能研究，而且具有很高的扩展性。但有一个显著的缺点是：Web日志的时间依赖性表达能力很弱；以ProWGen为代表的日志生成器能较好的以时间局部性拟合Web文件特征，却是采用静态分布模型。当前随着应用需求的日益扩大，要求生成器的仿真性能较高，这给Web日志生成方法带来了严重的挑战；另外，当前大数据的各种应用，对生成Web日志的自相似性要求也越来越高。事实上，当出现热点时，数据会表现为突发性地围绕热点动态变化。但当前已有的Web日志生成器的主要是基于静态数据分布设计的，忽略了分布的动态性和用户行为的复杂性，虽然引入了Web文件的时间局部性，却没有站在时间角度来衡量Web文件的时间局部性。

发明内容

本发明的目的在于提供一种基于用户兴趣迁移的大数据集仿真生成方法，该方法能够提高自相似性，从而较好的模拟真实Web日志。

为实现上述目的，本发明的技术方案是：一种基于用户兴趣迁移的大数据集仿真生成方法，包括以下步骤：

步骤1~2：生成每个用户的属性并形成用户集合U={u₁,>2, ……,>n}，n表示用户数，u_n表示第n个用户；生成每个Web文件的属性并形成Web文件集合I={i₁,>2, ……,>m}，m表示Web文件数，u_m表示第m个Web文件；

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

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

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

步骤6：计算用户u的到达时间currentTime = currentTime + ∆T，∆T由威布尔分布计算得到；

步骤7：寻找用户u的连续访问序列长度s，并判断是否找到用户u的连续访问序列长度s，是则转步骤15，否则转步骤8；

步骤8：计算用户u当前的总序列长度k =>u.length，R_u.length表示集合R_u的长度，即集合R_u中的文件数量；

步骤9：判断用户u的总序列长度k是否超过1，是则转步骤10，否则转步骤14；

步骤10~12：利用齐普夫分布计算用户u的连续访问序列长度s，判断连续访问概率p是否大于随机值的小数部分，是则转步骤13，否则转步骤8；

步骤13：找到用户u的连续访问序列长度s，转步骤7；

步骤14：不存在连续访问，用户u至少访问一个文件，找到的连续访问序列长度s=1，转步骤7；

步骤15：遍历用户u的用户请求序列R_u中的每个文件，利用艾宾浩斯遗忘函数计算用户对其序列中每个文件的兴趣度W_ui；

步骤16：按照兴趣度重新降序排序用户请求序列R_u；

步骤17：取出用户请求序列R_u中用户最感兴趣的前s个文件，组成连续访问序列Seq_uj>u₁’,>u₂’, …,>us’}，r_us’表示用户u本次访问最感兴趣的第s个文件，Seq_uj表示用户u第j次访问的连续访问序列；

步骤18：将连续访问序列Seq_uj放入到当前用户被调整过的新序列R_u’中，其中R_u’={Seq_u1,>u₂, …,>uj}；

步骤19：将连续访问序列Seq_uj从当前用户未被调整的序列R_u中删除，并转步骤5。

进一步的，在步骤1、2、3中，所述用户的属性包括用户ID和用户活跃度，所述Web文件的属性包括文件ID、文件流行度、文件大小和文件路径，其中，用户ID和文件ID是主键，所述日志包括用户ID、文件ID、文件大小和文件路径。

进一步的，在步骤3中，将用户活跃度的累积概率和文件流行度的累积概率进行负相关，以关联用户和Web文件，形成原始请求序列R。

进一步的，在步骤15中，遍历用户u的用户请求序列R_u中的每个文件，时间复杂度O(k)为用户u的活跃度大小k，以最坏的情况考虑，每个用户访问相同数量的文件，则平均时间复杂度为O(a)=O(q/n)。

进一步的，在步骤16中，降序排序用户对文件的兴趣度，使用堆排序，时间复杂度为O(alog2(a))。

进一步的，在步骤18和19中，对链表的尾端插入和首端删除，复杂度为1，则总体时间复杂度为O(n*(2a+ alog₂(a)))，在最坏情况下，总体时间复杂度为O(q*(2+log₂(q/n)))，其中q为请求序列总数量，算法复杂度随着要生成数据集的量级增大而增大。

本发明的有益效果是针对传统Web日志仿真算法无法从时间上更客观地模拟Web日志的缺陷，提出了一种与已有方法完全不同的基于用户兴趣迁移的Web日志仿真生成方法，使得Web日志在时间序列条件下自相似性更加符合实际应用。该方法通过用户的兴趣迁移，改变用户的访问序列，能够较好的模拟真实Web日志，可以有效地应用于Web日志的仿真生成。

附图说明

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

图2是本发明实施例中用户到达模式分布情况图。

图3是本发明实施例中用户到达的时间间隔累积分布情况图。

图4是本发明实施例中用户请求序列结构图。

图5是本发明实施例中艾宾浩斯遗忘曲线图。

具体实施方式

本发明提供一种基于用户兴趣迁移的大数据集仿真生成方法，如图1所示，包括以下步骤：

步骤1~2：生成每个用户的属性并形成用户集合U={u₁,>2, ……,>n}，n表示用户数，u_n表示第n个用户；生成每个Web文件的属性并形成Web文件集合I={i₁,>2, ……,>m}，m表示Web文件数，u_m表示第m个Web文件。

步骤3：将用户活跃度的累积概率和文件流行度的累积概率进行负相关，以关联用户和Web文件，形成原始请求序列R={r₁,>2, ……,>q}，q表示原始请求序列中Web日志数量，r_q表示第q条Web日志。

在步骤1、2、3中，所述用户的属性包括用户ID和用户活跃度，所述Web文件的属性包括文件ID、文件流行度、文件大小和文件路径，其中，用户ID和文件ID是主键，所述日志包括用户ID、文件ID、文件大小和文件路径。

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

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

步骤6：计算用户u的到达时间currentTime = currentTime + ∆T，∆T由威布尔分布计算得到。

步骤7：寻找用户u的连续访问序列长度s，并判断是否找到用户u的连续访问序列长度s，是则转步骤15，否则转步骤8。其中，寻找用户u的连续访问序列长度，根据分布来看，在连续访问1~4之间的概率超过50%，因此其复杂度在k/4到k之间，这里取最坏情况k。

步骤8：计算用户u当前的总序列长度k =>u.length，R_u.length表示集合R_u的长度，即集合R_u中的文件数量。

步骤9：判断用户u的总序列长度k是否超过1，是则转步骤10，否则转步骤14。

步骤10~12：利用齐普夫分布计算用户u的连续访问序列长度s，判断连续访问概率p是否大于随机值的小数部分，是则转步骤13，否则转步骤8。

步骤13：找到用户u的连续访问序列长度s，转步骤7。

步骤14：不存在连续访问，用户u至少访问一个文件，找到的连续访问序列长度s=1，转步骤7。

步骤15：遍历用户u的用户请求序列R_u中的每个文件，利用艾宾浩斯遗忘函数计算用户对其序列中每个文件的兴趣度W_ui。其中，遍历用户u的用户请求序列R_u中的每个文件，时间复杂度O(k)为用户u的活跃度大小k，以最坏的情况考虑，每个用户访问相同数量的文件，则平均时间复杂度为O(a)=O(q/n)。

步骤16：按照兴趣度重新降序排序用户请求序列R_u。其中，降序排序用户对文件的兴趣度，使用堆排序，时间复杂度为O(alog2(a))。

步骤17：取出用户请求序列R_u中用户最感兴趣的前s个文件，组成连续访问序列Seq_uj>u₁’,>u₂’, …,>us’}，r_us’表示用户u本次访问最感兴趣的第s个文件，Seq_uj表示用户u第j次访问的连续访问序列。

步骤18：将连续访问序列Seq_uj放入到当前用户被调整过的新序列R_u’中，其中R_u’={Seq_u1,>u₂, …,>uj}。

步骤19：将连续访问序列Seq_uj从当前用户未被调整的序列R_u中删除，并转步骤5。

在步骤18和19中，对链表的尾端插入和首端删除，复杂度为1，则总体时间复杂度为O(n*(2a+ alog₂(a)))，在最坏情况下，总体时间复杂度为O(q*(2+log₂(q/n)))，其中q为请求序列总数量，算法复杂度随着要生成数据集的量级增大而增大。

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

1 Web日志分布特征

1.1 日志数据中的重尾分布

通过分析各种真实网络日志数据，发现重尾分布与网络流量自相似特性有很大关联，服从重尾分布的随机变量特点是：随机变量X的抽样值中，小抽样值的数量较多，大抽样值的数量较少，这就形成了重尾现象。其概率密度函数为p(x)=1-(k/x)^a。其中参数a称为重尾度索引，它决定分布的重尾度。参数k决定重尾分布的尾起始点。

在Web日志中Pareto分布可以用于描述时间间隔和文件数量的关系。当用户请求文件时，服务器发送文件时存在延迟传输问题，因此，用户请求动作与访问动作之间的时间间隔服从重尾分布以概率p作为参数来求时间间隔∆t。如公式(1)所示：

(1)

公式(1)中∆t也能表示Web服务器主动OFF时间。通过设置主动OFF时间，很久之前被访问的文件，当其OFF时间到达时，依然能在下一刻获得被访问的机会，这就能使序列更加均衡。

1.2 用户日志中的威布尔分布

设服务器的用户请求序列为R={r₁,>2, ……,>n}，请求序列按照用户访问的时间先后排序，可以将请求序列划分成多个用户的访问序列。对95年美国国家航天航空局网站的八月份1569898条请求序列进行统计，如图2所示，横坐标为两个用户之间的时间间隔（单位：100毫秒），纵坐标为时间间隔内到达的用户数量。可以看出少部分用户都是在很短的时间间隔内到达，而大部分用户是相隔很长一段时间才能到达。其累积概率分布如图3所示，横坐标为用户到达的时间间隔（单位：100毫秒），纵坐标为累积概率。拟合结果表明，用户到达模式近似服从威布尔分布,其累计概率分布函数为p(x)=1-exp[-(x/λ)^k]，其中参数k和参数λ的拟合结果分别为0.29和7。以概率p作为参数可以得到时间间隔∆T。

(2)

公式(2)中∆T也能表示Web服务器被动OFF时间。通过设置主动OFF时间，就可以将请求序列变为用户请求序列。而用户的先后到达顺序可以由Web文件的时间局部性决定^[2]。

1.3 用户日志中的齐普夫分布

当用户点击Web服务器某链接发起请求时，浏览器展示给用户的页面是由多种类型的Web文件构成，包括商标图片，flash动画，广告链接等一系列内容构成Web对象^[9]。在分析日志中用户行为的时候会发现用户在极短时间内连续访问多个文件的现象，显然现有的Web日志生成器没有考虑这个现象。将此现象模拟成用户发送连续请求，通过对NASA网站数据分析发现，用户发出连续动作次数概率服从齐普夫分布^[8]。在Web对象中，用户连续访问2个以上文件的概率超过73%，而用户连续访问12个以上文件的概率已经非常接近0。假设用户u的总请求序列是R_u={r_u1,>u₂, ……,>uk}，其中r_uk为用户u访问的第k个Web文件。则第k个Web文件被访问的概率为p(i_uk)=k^ω，利用最小二乘法拟合可得ω=-0.964。

2 基于遗忘曲线的用户兴趣与时间依赖的ITDF模型

为了更好的理解用户兴趣与时间依赖，以OFF时间来构建用户请求序列，如图4所示，t0时刻为用户u_k到达时间，u_k向Web服务器发送连续请求，每次请求之间存在服务器主动OFF时间∆t，u_k的连续请求构成一个Web对象，u_k本次访问结束时刻为t1。在第k+1名用户u_k+1到来之前服务器处于等待状态，也即服务器被动OFF时间∆T，u_k+1在t2时刻开始向Web服务器发送请求。为了使OFF时间更加合理，考虑请求序列的负载均衡我们改进OFF时间，具体做法如下：

对于流行度高的Web文件的OFF时间间隔会很短，这样会造成短时间内同一个Web文件被频繁访问，因此我们对流行度高的Web文件的∆t加入惩罚因子1/ln^(1+Popi)，其中Pop_i表示文件i的流行度。改进公式(1)为公式(3)；同理，对活跃度高的用户的∆T加入惩罚因子1/ln^(1+Actu)，其中Act_u表示用户u的活跃度。改进公式(2)为公式(4)。

(3)

(4)

接着将用户和Web文件利用时间局部性关联，根据时间局部性定义：“最近刚刚访问过的文件比很久以前访问的文件更有可能在不久的将来被再次访问”^[2]，这里也由局部性特征而带来一个缺陷，即如果最近访问的是用户不感兴趣的Web文件，那么再次被访问的可能性会降低。同种数据在不同时刻的关系是符合艾宾浩斯遗忘曲线。在本文中提到的用户与Web文件的兴趣同样也和艾宾浩斯遗忘曲线相似，不是简单的逐步衰减，而是非线性的先快后慢。用户在短期内的兴趣度会有大幅度下降，而在长期中却能保持一个稳定的兴趣。

艾宾浩斯遗忘曲线描述了人们在学习时遗忘的过程是不均衡的，呈先快后慢的变化规律。如图5所示，图中横坐标表示经过的天数，纵坐标表示用户的记忆量百分比。可以发现在第一天内记忆量就从100%迅速下降到33.7%，之后缓慢的下降。我们用R语言中的nls函数来模拟艾宾浩斯遗忘曲线，如图4所示，其模拟函数如公式(5)所示，其中a=31.75，b=0.1306。

(5)

用户的兴趣度和记忆量变化极为相似，因此本文基于艾宾浩斯遗忘曲线, 构建的用户兴趣迁移与时间依赖关系的模型ITDF（user Interest transferring and Time-Depending based on Forgetting curve, ITDF）可以用来控制用户的兴趣漂移。用公式(5)中的W_ui表示用户u对文件i的兴趣度，t表示用户u当前访问文件i的时间与上次访问的时间间隔。

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