互联网中存在着大量有价值的非结构化数据, 这些数据以不同的载体呈现, 是内容全面的信息资源.图结构是互联网中非结构化数据的一种主要组织形式, 可表示为在线大图(online big graph, 简称OBG).典型的OBG包括网页、社交媒体和知识图库, 如图 1所示.OBG数据的获取, 包括数据收集和更新, 是解决大数据分析、知识工程和决策支持等实际问题的重要前提和基础^{[1, 2]}, 在Web搜索与海量数据分析^[3]、数据集成^{[4, 5]}、数据抽取与融合^[6]等领域发挥着重要作用.一个OBG包括对象和连接, 不同类型的OBG其对象和连接不同.

OBG中的数据具有海量、分布、异构和快速变化等特点^[7], 并且在数据收集之前, 其全局的图结构是未知的, 这使得OBG数据的收集和更新都面临着数据量巨大、数据分布范围广、数据结构复杂且变化迅速等方面的挑战, 因此无法获取OBG中全部对象的数据.如何优先获取OBG中有价值、重要的数据, 是一个在线优化问题.解决这一问题主要面临如下难点和挑战:(1) OBG数据的收集是在线(online)的, 初始时, OBG的结构完全未知, 随着收集到的数据不断增加, OBG的结构才逐渐被发掘, 在线性使得数据收集中对象的选取变得更加困难; (2)完全没有OBG数据的情况下, 无法根据特定需求按照重要性由大到小的次序收集OBG中的对象, 通过分析已收集的OBG数据, 发现重要对象的分布规律, 也是提升后续数据获取效率的保证.因此, 本文围绕如何优先收集重要对象和利用已收集的OBG数据来优化其数据更新过程, 讨论OBG数据的收集和更新方法, 为OBG数据处理与分析的相关问题奠定基础.

以通用爬虫(universal crawler)和优先爬虫(preferential crawler)为代表的OBG数据收集方法主要关注OBG的局部结构, 但是针对数据收集过程的在线性, 不能从全局出发寻找重要的数据; 同时, 基于网页布局^[8]或历史数据统计的OBG数据的更新方法^[9]通过分析已收集的OBG数据得到变化规律, 从而优化OBG数据的更新, 但对于数据变化规律并未包含于历史数据的情形仍不能有效更新.采样技术被广泛用于统计机器学习^[10], 它能够方便地处理全局性问题.半蒙特卡洛采样(quasi Monte Carlo sampling, 简称QMC)与传统的蒙特卡洛采样(Monte Carlo sampling, 简称MC)技术不同, 使用伪随机序列生成采样点, 使得采样更加均匀和全面, 避免了由于随机采样点过近而导致重要性评估效果下降的问题.因此, 以OBG数据的有效获取为目标, 本文借鉴优先爬虫的思想, 基于QMC采样技术, 提出自适应的OBG数据收集算法, 并在其基础之上给出用于OBG数据更新的算法.针对OBG数据的海量性, 我们利用Spark平台实现OBG数据的并行获取, 保证OBG数据的高效获取.

首先, 对于给定的OBG, 本文结合QMC采样技术和求解优化问题的分支限界方法, 提出在线算法HD-QMC, 从全局角度提升OBG数据收集的效果.我们将OBG对象集合映射到高维空间, 并对高维空间分割得到子空间, 再利用QMC采样技术, 先收集采样点对应的OBG对象, 再由此评估各个子空间的重要性, 对最重要的子空间递归地执行上述过程, 直到得到OBG中所有对象的数据, 从而完成OBG数据的收集.然后, 将已收集的数据统一表示为RDF(resource description framework)的形式^[11], 为后续研究提供统一的数据接口.进一步地, 本文从理论上给出HD-QMC算法的有效性、复杂度、标准误差、迭代次数和冲突率等指标的分析.

接着, 借鉴基于历史数据统计的传统方法, 本文结合信息熵、泊松过程^[12]和前述的数据收集方法, 提出数据更新算法EPP.作为数据收集方法的扩展, EPP算法首先通过信息熵计算各个子空间的信息量, 并利用泊松过程预测每个子空间可能产生的增量, 将QMC采样过程中得到的实际子空间增量的大小与预测增量的大小进行融合, 由此优先对增量较多的子空间进行采样, 得到采样对象的增量, 从而完成OBG数据的更新.

最后, 我们基于Spark平台实现本文提出的算法, 在真实数据集和生成数据集上, 将HD-QMC和EPP算法与现有方法在有效性和效率方面进行了对比, 展示了本文方法针对实际应用中不同OBG数据的收集和更新效果.与其他方法相比, 本文的方法能更快地发现大多数重要的对象, 且具有良好的可扩展性.

1 相关工作

●  OBG数据收集

通用爬虫和优先爬虫是主要的OBG数据收集工具.通用爬虫利用经典的广度优先^[13]和深度优先^[14]方法, 仅根据局部图结构进行数据收集.但OBG中各个部分的重要性在实际情况下并不相同, 通用爬虫没有考虑到不同部分重要性的差异.优先爬虫主要包括主题爬虫(topic crawler)和聚焦爬虫(focused crawler)^[15]:主题爬虫根据特定的主题从Web上搜索信息; 聚焦爬虫通过使用基于应用、链接^[16]和语义^[17]的方法, 在数据收集过程中能够优先收集用户关注的内容, 关注的内容可以是关键词或用户定义的其他需求.但是现有的优先爬虫大部分同样由于受到OBG的在线性限制, 主要关注局部图结构, 为了快速发现OBG中重要的部分, 还需要进一步扩展.与广度优先和深度优先方法不同, 本文方法并不是从OBG中的某个对象开始逐渐扩大收集范围, 而是从OBG的全局出发, 优先收集重要部分中的数据.

●  基于采样技术的数据收集

使用这类方法可得到全局的图结构信息^[18], 采样技术的引入, 使得数据收集过程能够区别对待重要性不同的部分, 且采样技术与OBG数据收集还有很多结合点, 例如, 图流采样方法^[19]从海量的图流数据中发现并收集重要的图数据.但与本文方法不同, 这种方法需要对所有图流数据进行分析, 并不能在部分数据未知的情况下完成采样.Yin等人^[20]提出一种基于QMC采样技术的聚焦爬虫, 将OBG中的对象映射为一维向量, 在此向量上, 通过QMC采样技术估算不同区域的重要性并收集数据.但是对于结构复杂的OBG, 一维映射会导致信息丢失, 影响重要性评估.另外, 此方法对重要性的度量依据只有连接, 对用户关注的其他信息表达不足.与上述方法不同, 本文通过将OBG中的对象映射到高维空间, 并利用高维Halton序列生成采样点, 提高了子空间重要性评估的准确性, 同时使用户可以选择需要的信息作为重要性评估的依据.

●  OBG数据更新

早期OBG数据更新的方法使用Revisit^[21]策略, 直接重新收集对象数据来替换本地已有数据.但是随着OBG数据的快速增长, 导致每次数据更新会产生巨大的开销, 并且不能满足数据更新的速度要求.为此, 很多研究专注于缩小收集范围来降低数据更新的成本.例如:Xi等人^[8]提出一种基于网页布局模式的方法, 能够适用于复杂的真实数据环境, 借助网页布局模式来判断某一页面变化的可能性, 但对于页面布局模式相似的对象来说, 并不能准确地为每个对象给出预测结果; Pavai等人^[9]根据历史数据计算每个对象发生变化的概率, 但这种方法无法预测历史数据中没有出现过的对象; Radinsky等人^[22]提出一种考虑了网页间连接结构的更新预测方法, 通过分析不同网页之间的结构关系, 得出数据更新策略, 但是随着网页间连接关系变得复杂, 预测的准确性会受到一定的影响; Cho等人^[23]提出基于采样的数据更新方法, 通过对OBG某个部分进行少量的采样, 判断其变化的可能性, 但该方法还不能用于自适应的数据更新.本文的数据更新方法建立在提出的数据收集方法之上, 同时结合了统计方法与OBG中的真实变化两个方面, 能够快速且有效地更新已收集数据.

2 基于采样的OBG数据收集

定义 1.一个OBG是一个有向图G_ON={O, E, R}, 其中, O, E和R分别是对象、连接和关系的集合.G_ON中的每个连接都有一种连接关系类型并连接两个不同对象, 即e=(o_i, o_j, r_k), e∈E, o_i, o_j∈O, i≠j, r_k∈R.

定义 2. G_ON中o_i的对象数据${\mathit{\Psi } _{{o_i}}}$是通过访问互联网获取的OBG数据, 包括对象本身和此对象产生的所有连接, 可表示为o_i以及e_i=(o_i, o_j, r_k), 其中, e_i∈E, o_i, o_j∈O, i≠j, r_k∈R, 全体对象的对象数据集合记为Ψ.

Ψ包含G_ON中的所有信息, 所以获取G_ON等价于获取Ψ.鉴于Ψ对不同对象是独立可分的, 因此可将OBG的对象集合映射到高维空间, 再对其进行子空间划分, 这样就能在高维子空间中使用QMC采样来量化不同子空间的重要性, 从而进行自适应的OBG数据收集.

2.1 OBG高维空间映射与子空间划分

我们将G_ON的对象集合O={o₁, o₂, …, o_|O|}映射到一个高维空间A, |O|为G_ON中对象的数量.映射后, 第i个对象的高维空间坐标可表示为

$\left( {\bmod \left( {\frac{{\left\lfloor {\frac{i}{{{L^0}}}} \right\rfloor }}{L}} \right),\bmod \left( {\frac{{\left\lfloor {\frac{i}{{{L^1}}}} \right\rfloor }}{L}} \right),...,\bmod \left( {\frac{{\left\lfloor {\frac{i}{{{L^{h - 2}}}}} \right\rfloor }}{L}} \right),\left\lfloor {\frac{i}{{{L^{h - 1}}}}} \right\rfloor } \right)$

(1)

其中, L为$\sqrt[h]{{|O|}}$, h代表空间维度.

QMC采样使用高维伪随机序列进行采样, 高维空间A的维度h越高, QMC采样的伪随机性和子空间覆盖性越好, 子空间分割也能够越精细, 重要性计算的结果也越准确.对于OBG而言, 恰当的h就足以表达其内部的信息, 多余的维度会造成计算资源的浪费.因此, 对于复杂的OBG, 适当提高维度h将能够更快发现重要的子空间, 提升数据获取的效率.

A中不同的子空间重要性不同, 且这些子空间内不同的子空间重要性也不相同.为了计算子空间的重要性, 可将A分割为K个等大小的子空间, 记为{A₁, …, A_s, …, A_K}, 每个子空间也可继续划分, 直到只包含单个对象.第J次划分结果表示为划分向量${\vec k_J}$, 其每个维度取值为各个子空间该维度上等分分割份数的倒数.子空间的递归细分将会产生一棵高度为log_K|O|的K叉树, 根节点对应整个高维空间, 第1层节点分别对应分割后的K个子空间, 其余层依此类推.例1展示了OBG的高维空间映射与子空间分割过程.基于此的分割方法, 下一节将讨论如何利用QMC采样递归的获取子空间重要性并进行自适应的数据收集.

例1:设图 1中社交媒体OBG对应的有向图为G_ON={O, E, R}, O={o₀, …, o₇}, E={e₀=(o₂, o₁, r₀), …, e₈}, 且R={r₀=好友, r₁=评论, r₂=转发, r₃=点赞}.若h=3, 根据公式(1)对G_ON进行空间映射可得, o₀~o₇对应坐标分别为(0, 0, 0), (1, 0, 0), (0, 1, 0), (1, 1, 0), (0, 0, 1), (1, 0.1), (0, 1, 1), (1, 1, 1).此时, OBG将会被映射到一个三维的立方体内.对这个立方体进行子空间分割, K=2时先对z轴分割, 则立方体在x, y和z这3个维度上分别被等分为1份、1份和2份, 对应的分割向量为${\vec k_1}$=(1, 1, 0.5), 如图 2(a)所示.接着, 用${\vec k_2}$=(0.5, 1, 1)和${\vec k_3}$=(1, 0.5, 1)对x轴和y轴划分, 得到8个子空间, 如图 2(b)所示.后续分割过程类似, 直到空间不再可分.

2.2 基于采样的OBG数据收集算法

结合前述OBG的高维空间映射与划分方法, 基于高维空间的QMC采样技术和分支限界方法, 本节给出自适应的OBG数据收集方法, 包括子空间重要性评估和子空间选择两个阶段.

在子空间重要性评估阶段, 我们首先将高维空间A按照子空间划分方法进行分割, 并由QMC采样得到每个子空间的重要性.将需要收集的信息视为目标信息, 例如网页OBG中特定主题的信息, 或社交媒体OBG中的用户信息和关注、转发、评论及点赞等社交行为.子空间中目标信息量又决定了子空间的重要性, 我们使用目标信息密度来度量子空间的重要性, 目标信息密度与聚焦爬虫中数据收集目标的概念类似, 反映了OBG数据收集时子空间中的目标信息量.下面给出子空间A_s中目标信息密度的概念.

${\rho _{{A_s}}} = \frac{{\sum\nolimits_{o \in {A_s}} {D({\mathit{\Psi } _o})} }}{{|{A_s}|}}$

(2)

其中, D(Ψ_o)代表一个OBG中对象o所包含的目标信息量.若将社交媒体OBG中的社交行为作为目标信息, 则子空间的目标信息密度为该子空间中社交行为的数量与子空间对象总数的比值.

为了快速计算子空间的重要性, 我们利用QMC采样技术, 通过少量采样点尽可能精确地计算不同子空间的目标信息密度, 由此找到最重要的子空间.QMC使用确定性的方法生成低差异的伪随机序列(low-discrepancy sequence)^[24], 并将其作为采样点, 这些采样点对子空间的覆盖性优于随机点.QMC通常将Halton序列作为其伪随机序列进行采样, 令b为一个素数, 则任何一个正整数Z⁺可表示为d_jb^j+…+d_ibⁱ+…+d₁b+d₀, 其中, d_i∈{0, 1, …, b-1}, 且i=0, 1, …, j.在一个Halton序列W中, 第w个元素ϕ_b(w)为$\frac{{{d_0}}}{{{b^1}}} + \frac{{{d_1}}}{{{b^2}}} + ... + \frac{{{d_j}}}{{{b^{j + 1}}}}$.同时, 对于任何w > 0, 有ϕ_b(w)∈ [0, 1].对于h个不同的素数b₁, …, b_d, n个h维的Halton序列为$\{ {\vec x_1},...,{\vec x_n}\} ,{\vec x_i}$可表示为

${\vec x_i} = {[{\phi _{{b_1}}}(i - 1),...,{\phi _{{b_n}}}(i - 1)]^T},i = 1,...,n$

(3)

因此, 第J次子空间划分后, 第i个采样点在每个子空间中的相对坐标为${\vec x_i} \circ {\vec k_1} \circ ... \circ {\vec k_J} \times \sqrt[h]{{|O|}}$, 其中, “º”代表哈达马积(Hadamard product).令采样点数n=|A_s|·R_samp, 其中, R_samp为采样比率, {o₁, …, o_i, …o_n}∈A_s为子空间A_s中用Halton序列生成的n个采样点对应的采样对象, 则${\rho _{{A_s}}}$可作如下近似计算.

${\rho _{{A_s}}} \approx \frac{1}{n}\sum\nolimits_{i = 1}^n {D({\mathit{\Psi } _{{o_i}}})} $

(4)

值得说明的是, 以上采样过程不仅可得到子空间的重要性, 还可得到采样点的对象数据${\mathit{\Psi } _{{o_i}}}.$因此, 本文的数据收集方法通过采样过程完成, 不仅并行地对每次分割得到的各个子空间进行采样, 而且并行地收集每个子空间内部的采样对象o_i, 从而得到${\mathit{\Psi } _{{o_i}}}$, 已收集的对象数据集合表示为${\mathit{\Psi } ^c} = \{ \mathit{\Psi } _1^c,\mathit{\Psi } _2^c,...,\mathit{\Psi } _{|O|}^c\} $.为了使得相关应用能通过统一的接口访问已收集数据, 我们将已收集的数据统一表示为RDF形式, 记为〈对象1, 关系, 对象2〉的三元组形式, 其中, “关系”可以表示网页OBG中的链接、社交媒体OBG中的社交操作以及知识库OBG中实体间的关系类型.

在子空间选择阶段, 我们根据QMC采样得到的子空间目标信息密度找出下一次迭代的子空间.所有本次及以往迭代中访问过的子空间的目标信息密度都被记录在一个候选子空间集合P_cand中, ${P_{cand}} = \{ {\rho _{{A_1}}},{\rho _{{A_2}}},...,$ ${\rho _{{A_K}}},{\rho _x}\} $, 其中, ρ_x是之前迭代访问过的子空间的目标信息密度.为了能够自适应地收集数据, 始终从P_cand中选取目标信息密度最大的子空间作为下一次迭代的高维空间.

由于存在某些目标信息较少且无需收集的子空间, 如分散孤立的部分, 使得数据收集效率较低.对此, 下面给出算法的结束条件.

$\bar \rho < {\rho _{\min }}$

(5)

其中, $\bar \rho $是所有采样的平均目标信息密度, ρ_min是能够接受的最小子空间目标信息密度.随着大多数高密度子空间逐渐收集完成, 剩下的子空间中的目标信息将越来越少, $\bar \rho $相应下降.最终, 当$\bar \rho < {\rho _{\min }}$时, 整个收集过程结束.

上述思想由算法1描述.

算法 1. HD-QMC.

输入:A, K, R_samp, P_cand.

输出:Ψ^c.

步骤:

IF |A| > 1 AND THEN

   S→Divide(A, K) //分为K个子空间, 得到集合S

   FOR EACH s IN S DO //s为子空间

      mass→0

      W→HaltonSeq(s, R_samp) //生成采样点集合W

      FOR EACH w IN W DO

         IF w∉Ψ^c THEN

            obj→Collect(w)

            Ψ^c→Ψ^c∪obj

         END IF

         mass→mass+NumInfo(obj) //加入新增的目标信息数量

      END FOR

      IF |s| > 1 THEN

         density→mass/|W|

         P_cand.Add([s, density])

      END IF

   END FOR

   A→P_cand.PickMax(·) //取出密度最大的子空间

   HD-QMC(·) //下一次迭代

END IF

算法1中的FOR循环可并行完成.算法迭代执行, 对子空间进行分割并产生一棵K叉树, 每个非叶子节点代表一次迭代并对应一个子空间, 每次迭代将从一个非叶子节点产生K个分支, 对原来子空间进一步划分, 并产生新的子空间.子空间不可分, 则为叶子节点且不产生新的分支.例2给出了基于算法1的OBG数据收集过程.

例2:基于例1得到的高维空间A及其子空间, 以社交行为“关注”“转发”“评论”“点赞”作为目标信息, 则子空间的重要性取决于对象的出度, 整个数据收集过程将进行多次QMC采样迭代并生成一棵二叉树, 其上部为子空间内的所有对象, 下部表示子空间的目标信息密度, 分支上标注了QMC采样点对应的对象, 如图 3所示.二叉树中的第1层~第3层节点对应的子空间, 分别由上层节点对应的子空间经过分割向量${\vec k_1},{\vec k_2},{\vec k_3}$分割得到.算法优先选择目标信息密度最大的节点进行迭代, 执行顺序为图中序号, 最终得到所有对象数据集合Ψ^c.

2.3 分析

(1) 有效性

给定高维空间A, 将对象数据收集过程中目标信息的增长曲线与坐标轴所构成区域的“面积”, 即收集过程中目标信息的积分, 作为算法1的有效性, 用S_A描述.

${S_A} = \sum\nolimits_{i = 1}^{|A|} {\sum\nolimits_{j = 1}^i {D(\mathit{\Psi }_j^c)} } $

(6)

其中, |A|是A中的对象总数, $\mathit{\Psi }_j^c$表示第j个收集到的对象数据.越重要的对象越早被收集, S_A越大.

(2) 复杂度

算法1的时间复杂度取决于K叉树的高度⌊log_K|O|⌋和采样比R_samp.K叉树中, 下一层采样是对当前这一层子空间分割并评估的过程, 每生成一层, 都会对|O|个对象按照R_samp重新采样, 并评估子空间的目标信息密度.因此, 算法1的时间复杂度可表示为O(|O|·R_samp·⌊log_K|O|⌋)=O(|O|·log|O|).

(3) 标准误差

标准误差是对子空间目标信息密度的估计误差.算法1的标准误差在不同采样点n下不同.

标准误差的估计为$|{A_s}|\frac{{{\sigma _n}}}{{\sqrt n }}$, 其中, ${\sigma _n} = \sqrt {\frac{1}{{n - 1}}\sum\nolimits_{i = 1}^n {{{\left( {D({\mathit{\Psi } _{{o_i}}}) - \frac{1}{n}\sum\nolimits_{i = 1}^n {D({\mathit{\Psi } _{{o_i}}})} } \right)}^2}} } .$

算法1的$|{A_s}|\frac{{{\sigma _n}}}{{\sqrt n }}$随着采样点数的上升以非线性趋势下降.

(4) 迭代次数

迭代次数是算法执行过程中对子空间分割并评估其重要性的次数, 记为N_iter.算法1的迭代次数取决于子空间的分割数K和对象总数|O|, 迭代次数由定理1给出.

定理 1.给定一个有|O|个对象和K个子空间的OBG(|O| > 0, K > 1), 可以得到N_iter为

$\left\{ {\begin{array}{*{20}{l}} {1,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;0 < |O| < K} \\ {|O| - {K^{m - 1}} + \sum\nolimits_{j = 0}^{m - 1} {{K^j}} ,{\rm{ }}{K^m} \leqslant |O| \leqslant 2{K^m}} \\ {\sum\nolimits_{j = 0}^m {{K^j}} ,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;2{K^m} < |O| < {K^{m + 1}}} \end{array}} \right.$

(7)

其中, m=⌊log_K|O|⌋, m∈Z⁺.

证明:根据对象数的不同可分为3种情形, 下面依次进行说明.

情形1:对象数在0到K之间, 即0 < |O| < K.由于每个子空间至少会有一个对象被收集, 所以这种情况下所有的对象将在一次迭代内收集完成, 因此N_iter=1.

情形2:对象数在K^m到2K^m之间, 即K^m≤|O|≤2K^m.首先用叶子节点代表对象, 所有非叶子节点代表一次迭代, 称为迭代节点.若K^m=|O|, 则为一棵完全K叉树有$\sum\nolimits_{j = 0}^{m - 1} {{K^j}} $个叶子节点.当一个对象被加入时, 就会有新的迭代节点形成, 该位置上原来的叶子节点和新加入的叶子节点将作为该迭代节点的孩子节点.因此, 一共有|O|-K^m-1个新加入的节点, 叶子节点按照同样的方法加入到这个K叉树中, 如图 4(a)所示.最终, ${N_{iter}} = |O| - $ ${K^{m - 1}} + \sum\nolimits_{j = 0}^{m - 1} {{K^j}} .$

情形3:对象数在2K^m到K^m+1之间, 即2K^m < |O| < K^m+1.当先前的叶子节点都变成迭代节点时, 新加入的节点将不再产生新的迭代节点, 直接加入现有的迭代节点中, 直到形成完全K叉树.这种情况下, 迭代次数将一直保持为${N_{iter}} = \sum\nolimits_{j = 0}^m {{K^j}} $, 且所有的叶节点都在K叉树的同一层, 如图 4(b)所示.

证毕.

(5) 冲突率

算法1在不同迭代节点对同一对象采样, 则产生冲突, 冲突越少, 算法1执行的效率越高.冲突用冲突率表示, 记为

${E_{conf}} = \frac{{{N_{conf}}}}{{{N_{iter}} \cdot K \cdot |{A_s}| \cdot {R_{samp}}}}$

(8)

其中, |A_s|·R_samp是每次迭代过程中各个子空间的采样点数, N_conf是整个数据收集过程中的冲突总数.

定理2定量地描述了所有的冲突.

定理 2.给定一个包含|O|个对象的OBG, 冲突总数为

${N_{conf}} = \sum\nolimits_{i = 1}^{{N_{iter}}} {\sum\nolimits_{j = 1}^{{m_i}} {{P_{ij}}} } $

(9)

其中, N_iter由定理1得出, m_i=⌊log_K|Aⁱ|⌋, Aⁱ是第i次迭代的采样子空间, P_ij是子空间Aⁱ对应的K叉树中第j层分割得到的子空间中不重叠的冲突数.

证明:当算法1从K叉树自顶向下进行采样时, 冲突最初从第1层迭代节点开始产生.

通过对子空间Aⁱ中各级分割子空间中的非重叠冲突进行求和, 得到第i次迭代的冲突数为$\sum\nolimits_{j = 1}^{{m_i}} {{P_{ij}}} $, 那么该过程的冲突总数为$\sum\nolimits_{i = 1}^{{N_{iter}}} {\sum\nolimits_{j = 1}^{{m_i}} {{P_{ij}}} } $.证毕.

假设K叉树对应的各级采样子空间中的冲突数为一个固定的值, 则N_conf的近似值为${N_{iter}} \cdot \sum\nolimits_{j = 1}^{{m_i}} {{P_{ij}}} $.因此, 冲突数以及E_conf可通过调整K和R_samp来降低.

3 基于泊松过程的OBG数据更新 3.1 数据更新概述

定义 3.令G_ON={O, E, R}为一个T时刻的OBG, 在T'(T' > T)时为${G'_{ON}} = \{ O',E',R'\} $.G_ON从T到T'的增量可表示为

$ D{G_{ON}} = \{ DIFF(O',O),DIFF(E',E),DIFF(R',R)\} $

(10)

DIFF(O', O)可表示为$[O'\backslash (O' \cap O)] \cup \overline {O\backslash (O' \cap O)} $, 用来描述新加入与删除对象的集合, 并以此作为${G'_{ON}}$以及G_ON之间的差异.△G_ON中, E和R的增量可用类似方式表达.

根据定义3, 增量可以更具体表示为O, E和R集合中元素的添加和删除操作, 因此增量可由定义4表示.

定义 4.更新操作集合U包括添加和删除, 分别记为u和$\bar u$.O, E和R的更新操作集合分别记为U_O, U_E和U_R, △G_ON={U_O, U_E, U_R}.

定义 5.从T₀到T时刻收集的OBG数据中, 统计窗口是T₀到T时刻内且结束于T时刻的时间区间, 定义为(T-α(T-T₀), T], 如图 5所示.其中, α称为窗口因子(0 < α≤1).

数据更新方法建立在数据收集方法之上, 包括增量预测和增量搜索两个阶段.数据更新方法将定义4表示的增量作为目标信息, 子空间重要性的度量依据仍采用目标信息密度, 在数据更新中为增量密度.因此, 数据更新方法可看作是对第2节中数据收集方法的扩展.

增量预测阶段利用HD-QMC算法输出的已收集数据Ψ^c, 通过使用信息熵和泊松过程对统计窗口内G_ON各子空间变化的可能性进行量化, 预测各个子空间的增量密度, 得到各个子空间的初始增量密度.增量搜索阶段以增量作为收集目标, 基于并扩展HD-QMC算法, 给出QMC采样得到的增量密度与增量预测阶段预测得到的增量密度进行合理融合的方法, 并使用融合后的增量密度作为子空间重要性的度量依据, 以此帮助发现更多的增量, 并用增量来更新本地数据, 从而优化数据更新过程.

3.2 基于信息熵的数据更新算法

在增量预测阶段, 假设当前已收集数据的统计窗口中对应数据的OBG为$G_{ON}^B$, 我们将$G_{ON}^B$映射到高维空间并分割为K个子空间, 即$G_{ON}^B = \{ {B_1},{B_2},...,{B_K}\} $.泊松过程是累计随机事件发生次数的独立增量过程^[12], 同时, B_j内增量的产生并没有确定的规律且相互独立, 是一个随机事件, 因此某段时间内, B_j中增量产生的大小可用泊松过程来描述和预测.从T到T'时刻, 用信息熵表示子空间的信息量, 则可根据信息熵运用泊松过程来预测未来一段时间内增量产生的可能性, 以此对这些子空间进行独立的更新.

定义 6.设一个OBG中从T₀到T时刻O, E和R的出现概率分别为P(o_i), P(e_i)和P(r_i), 其信息熵分别为

$ H\left( O \right) = E\left[ {I\left( {{o_i}} \right)} \right],H\left( E \right) = E\left[ {I\left( {{e_i}} \right)} \right],H\left( R \right) = E\left[ {I\left( {{r_i}} \right)} \right]. $

其中, I(o_i)=-logP(o_i), I(e_i)=-logP(e_i), I(r_i)=-logP(r_i).子空间B_j的信息量即为

$ {Y_j} = \left| {{O_j}} \right| \times H\left( O \right) + \left| {{E_j}} \right| \times H\left( E \right) + \left| {{E_j}} \right| \times H\left( R \right). $

其中, O_j和E_j即为对象集合和连接集合, o_i, e_i∈B_j, j=1, 2, …, K.

定义 7.令$\lambda = \frac{{{Y_j}}}{{\alpha (T - {T_0})}}$为泊松分布的均值, 若在△T内增量的大小为τ, 则增量产生的概率为

$ P\{ X({\rm{\Delta }}T + T) - X(T) = \tau \} = {{\rm{}}^{ - \lambda {\rm{\Delta }}T}}\frac{{{{(\lambda {\rm{\Delta }}T)}^\tau }}}{{\tau !}}$

(11)

其中, X是泊松过程, 且τ=0, 1, ….

令U_j为B_j增量大小的预测, 满足P{X(△T+T)-X(T)=U_j}=Max{P{X(△T+T)-X(T)=τ}}.

因此, 可以得到U={U₁, U₂, …, U_j, …, U_K}.

最后, 将U_j/|B_j|作为子空间的初始增量密度, 并加入到P_cand中.

在增量搜索阶段, 由于从$G_{ON}^B$的子空间B_j中得到的U_j不一定能很好地反映真实的增量大小, 但在OBG的采样过程中能对真实的增量大小进行评估, 因此我们引入融合比率β, 将U_j/|B_j|与采样得到的增量密度进行合理融合, 以便从K叉树的第2层开始指导子空间的选取, 并快速发现OBG中真实的增量.实际采样过程中, 对于K叉树中任意层的迭代节点, 第j个子空间的增量密度表示为V_jl, 通过QMC采样方法计算:

${V_{jl}} \approx \frac{1}{n}\sum\nolimits_{\varepsilon = 1}^n {\left( {\left\lceil {{N_\varepsilon }\frac{{H(O)}}{{{N_\varepsilon } + 1}}} \right\rceil + {N_\varepsilon } \cdot H(E) + {N_\varepsilon } \cdot H(R)} \right)} $

(12)

其中, N_ε和n分别为采样得到的新连接数和采样点数, l为K叉树的层数.$\left\lceil {{N_\varepsilon }\frac{{H(O)}}{{{N_\varepsilon } + 1}}} \right\rceil + {N_\varepsilon } \cdot H(E) + {N_\varepsilon } \cdot H(R)$代表第ε个采样点的增量大小, 则融合后的K叉树中第l层第j个子空间的增量密度表示为

${V'_{jl}} = (1 - \beta ){V_{jl}} + \beta \left( {\frac{{{{V'}_{j(l - 1)}}}}{K}} \right)(0 \leqslant \beta \leqslant 1,l > 1)$

(13)

${V'_{j(l - 1)}}$为包含当前子空间的上一级子空间增量密度, 即K叉树中当前迭代节点的父节点对应子空间的增量密度.特别地, ${V'_{j1}} = {U_j}/|{B_j}|$.

上述思想见算法2.

算法 2. EPP.

输入:初始增量密度最大的子空间A_max, K, R_samp, Ψ^c, 包含所有子空间增量密度初始值的P_cand.

输出:更新后的Ψ^c.

步骤:

IF |A_max| > 1 AND ρ THEN

   S←Divide(A_max, K) //K个子空间与已收集数据相同

   FOR EACH s IN S DO

      vol←0

      W←HaltonSeq(s, R_samp) //生成采样点集合W

      FOR EACH w IN W DO

         obj←Collect(w)

         temp←Find(Y^c, w) //在Y^c中查找w

         IF objtemp THEN

            vol←vol+IncVol(obj, temp) //计算增量大小

            Update(Y^c, w, obj) //用obj更新Y^c中的w

         END IF

      END FOR

      IF |s| > 1 THEN

         density←(1-b)×vol/|W|+b×HistoryDensity(·)

         P_cand.Add([s, density])

      END IF

   END FOR

   A_max←P_cand.PickMax(·) //取出下一个子空间

   EPP(·) //下一次迭代

END IF

与算法1类似, 同样使用QMC采样技术来发现全部增量, 包括新的对象、连接和连接类型.算法2中的IncVol计算当前采样点的增量大小.HistoryDensity用于得到当前子空间的${V'_{j(l - 1)}}/K$.算法2与算法1的时间复杂度相同, 都为O(|O|·log|O|).算法2的执行过程可由例3表示.

例3:基于例2得到的Ψ^c, 令α=1, β=0.2.若新产生的数据为e₉=(o₃, o₄, r₂), e₁₀=(o₄, o₅, r₃), e₁₁=(o₅, o₆, r₀), 根据定义6, $G_{ON}^B$中O, E和R的信息熵分别为H(O)=0.903, H(E)=0.954, H(R)=0.553.

数据更新过程如图 6所示, 子空间划分方式及采样序列与例2一致, 图中节点下部左侧与右侧各代表${V'_{jl}}$和V_jl.算法优先选择融合后增量密度最大的节点进行迭代, 顺序由图中的标号给出, 其中, 对o₄, o₅和o₃的采样过程中发现了新数据e₁₀, e₁₁和e₉, 并将其加入到已收集数据中, 已收集数据与当前OBG上的数据保持同步.

4 实验结果 4.1 实验设置

为了测试本文提出方法的性能, 我们基于Spark平台实现本文的算法, 分别测试了算法1(HD-QMC)和算法2(EPP)的有效性和效率.Spark集群包括6计算节点, 每个计算节点拥有2个10核心/20线程/3.6GHz的CPU和128GB内存.各计算节点共用一个千兆交换机, 且网络带宽限制为2Mb/s.Spark和HDFS版本分别为1.6.1和2.5.2.实验使用的测试数据集见表 1.

4.2 有效性测试

(1) HD-QMC算法有效性测试

为了测试HD-QMC数据收集的有效性, 本文选用Ber-Stan、Facebook、微博和Wikidata分别作为典型的网页OBG、社交媒体OBG和知识库OBG.需要说明的是, 实验所使用的Wikidata数据集是存储在维基网站上的数据, 实验中需要通过网络访问, 使用前10 000个实体作为测试数据集.Ber-Stan、Facebook和微博数据集预先下载到本地磁盘, 测试时模拟了数据收集的真实环境, 仿真了数据收集过程中网络访问的开销.

将OBG中对象之间的连接作为目标信息, 并以目标信息覆盖度来度量OBG中目标信息的收集进度, 由${\sum\nolimits_{{\mathit{\Psi }_{i}}\in {\mathit{\Psi }^{c}}}{D({\mathit{\Psi }_{i}})}}/{\sum\nolimits_{{\mathit{\Psi }_{j}}\in \Psi }{D({\mathit{\Psi }_{j}})}}\;$计算得到, 其中, Ψ^c和Ψ分别代表已收集数据的集合与全体数据的集合.针对目标信息覆盖度对本文提出的HD-QMC进行测试, 并与顺序收集(sequence)、深度优先策略(DFS)、Snowball采样(snowballing)^[13]、随机选择(random)和基于QMC采样技术的方法(BB-QMC)^[20]进行了对比, 分别如图 7(a)~图 7(d)所示.其中,

●  Sequence、DFS和Snowballing是传统的顺序、深度优先和Snowball采样方法.

●  Random方法随机选取对象进行数据收集.

●  BB-QMC是一种先进和新颖的数据收集方法, 其依照不同子空间的重要性自适应的收集OBG数据.但与本文方法不同的是, BB-QMC将OBG中的对象映射为一维向量, 在此一维向量空间上, 通过QMC采样技术估算不同子空间的重要性并收集数据.对于复杂的OBG, 由于对高维空间的投影往往会造成信息的丢失, 一维空间在信息表示上与高维空间相比存在劣势.

从图 7可以看出, 随着收集对象的增加, 由于对不同子空间的重要性考虑不足, Snowballing、Sequence和DFS的目标信息覆盖度与Random相近; 而HD-QMC和BB-QMC的目标信息覆盖度显著增加, 且HD-QMC在大多数情况下增加较快.这是由于HD-QMC将对象映射到更高维度的空间中, 从而能更细致地分割和计算子空间的重要性, 因此能优先收集目标信息较多的子空间.同时, 给定ρ_min, 由于HD-QMC能够更快地收集重要的对象, 所以相比其他方法能够更早地结束且|Ψ^c|最小, 所消耗的成本也最低.由此可见, HD-QMC能够高效地收集3类典型的OBG数据.

接着, 本文测试了HD-QMC执行过程中不同R_samp(R)对目标信息覆盖度的影响, 如图 8(a)~图 8(d)所示.可以看出, 当R_samp大于0.05时, 在前3个数据集上都可得到较好的数据收集结果; 而R_samp为0.01时, 在微博数据集上的数据收集效果最好.由此可知, 不同数据集需要选取合适的R_samp来提升数据收集效果.

同时, 本文测试了子空间分割数K对目标信息覆盖度的影响, 如图 9(a)~图 9(d)所示.在Ber-Stan、Wikidata和微博数据集上, K分别为30, 15和45时, 可得到最佳目标信息覆盖度.在Facebook数据集上, 初始K为30时得到了较好的结果; 但当已收集的对象数量大于1 500之后, K为45时得到最好的效果.由此可知, 针对不同的OBG数据可设置适当的K值, 以达到较好的数据收集效果.

进一步地, 我们根据公式(6)计算了上述对比方法与HD-QMC在各个数据集下的有效性指标(S_A), 见表 2.不难看出, 由于HD-QMC能够更精确地计算子空间的重要性, 因此所有数据集上获得了最高的S_A, 并取得了最好的数据收集效果.DFS方法由于无法在微博数据集上运行, 表 2中对应值未列出.

(2) EPP算法有效性测试

我们用2个典型的数据集测试EPP算法的有效性:第1个是时间跨度2周、约11 000个用户的真实微博数据集, 第1周数据作为已收集数据, 第2周数据作为新数据; 第2个是由扩展的LFR方法^[28]生成的LFR数据集, 以此来测试当社交媒体中存在极端变化时, EPP的数据更新效果.与HD-QMC的测试相似, 我们测试了不同方法的目标信息覆盖度, 包括本文提出的EPP、基于统计的方法(Statistic)^[9]和基于结构的方法(structure- based)^[22], 如图 10(a)、图 10(b)所示.其中, 基于统计的方法通过统计并计算历史数据中对象变化的概率进行数据更新, 基于结构的方法通过计算对象间不同连接结构的变化概率进行数据更新.

根据公式(6), 以上3种方法的有效性指标(S_A)见表 3.

结合图 10和表 3可以看出, 对于真实的微博数据集, EPP比其他方法能够更好地发现增量, 但是基于统计的方法在LFR数据集上取得了更好的数据更新效果.

我们进一步用F1值测试EPP针对数据更新的有效性.

$F1 = \frac{{2 \cdot Pr \cdot Re}}{{Pr + Re}}$

(14)

其中, Pr和Re分别表示Precision值和Recall值, Precision是EPP发现的增量与其预测增量的比值, Recall是EPP发现的增量与真实增量的比值.测试结果如图 11(a)、图 11(b)所示, 可以看出, EPP在微博和LFR数据集上优于基于统计和基于结构的方法.

为了测试EPP算法中参数对数据更新效果的影响, 本文比较了微博和LFR数据集上不同窗口因子(α)和融合比率(β)时的F1值.为了便于观察, 我们对测试结果进行归一化, 分别如图 12和图 13所示.

在微博和LRF数据集上, α分别为0.2和0.4时EPP算法取得最好的效果.在微博上, β为0.2时算法效果最好.而LFR数据集上, β为0.2, 0.4和0.6的情况较为接近:访问对象小于8 000时, β为0.2最好; 大于8 000时, β为0.6的效果最好.总体上, β为0.2时效果最好, 对应曲线与坐标轴之间所构成区域的面积最大.由此可知, 对于不同的数据集, 应选取合适的α和β.

4.3 效率测试

EPP算法与HD-QMC算法执行效率接近, 实验通过网络访问Wikidata数据集, 测试了HD-QMC的执行时间、加速比和并行效率, 分别如图 14~图 16所示.

由图 14可知, HD-QMC数据收集的执行时间随着OBG中已访问对象数的增加基本呈线性增长, 且Spark平台的计算节点越多执行时间越少, 6个节点时的总执行时间与1个节点时相比明显减少, 为1节点下执行时间的1/6.图 15中的加速比和图 16中的并行效率在HD-QMC开始执行时便趋于稳定, 加速比接近计算节点数, 同时, 并行效率也接近理论最优值1.以上情况产生的原因是由于HD-QMC的执行时间很大程度上依赖于网络带宽, 而多计算节点下的网络带宽会随着计算节点数同步增长.以上实验结果与理论分析得出的结论一致, 进一步验证了本文方法的高效性.

为了对比HD-QMC与传统算法的执行效率, 实验测试了HD-QMC与Sequence、Random、HD-QMC、Snowballing在执行时间与可扩展性上的差异.我们首先在1个计算节点情形下测试了不同算法的执行时间, 得到不同算法单线程执行效率.接着在6节点情形下再次测试算法执行时间, 获取不同算法的可扩展性表现, 分别如图 17和图 18所示.

从图 17可以看出, 1个计算节点情形下, Random和Snowballing算法执行较慢, HD-QMC和BB-QMC算法稍快, Sequence算法由于直接从对象列表中依次选取对象进行获取, 所以最快.1节点下单线程的HD-QMC没有充分发挥可扩展性上的优势, 但在6个计算节点情形下多线程测试中执行效率提升明显.从图 18中可以看出, 由于无法并行执行, 因此6个计算节点情形下Snowballing和Sequence算法执行时间与1个计算节点下一致. Random、HD-QMC与BB-QMC算法在6个节点下的算法执行效率提升明显, 由于这3种算法都使用了分割的思想同时对不同的子空间进行采样, 执行效率都随节点数增加而提升, 因此HD-QMC可扩展性很好, 适合OBG数据的收集与更新.

5 结论与展望

本文首先讨论了基于采样技术的自适应OBG数据收集, 该方法能够通过QMC采样找到重要的子空间并尽可能好地给出OBG中对象数据的收集顺序, 以实现OBG数据有效收集.同时给出数据的统一表示方法, 降低数据集成和使用的成本.进一步地, 我们扩展数据收集方法, 给出高效的数据更新算法, 既能利用历史数据中的数据变化规律, 又能利用增量中新的数据变化规律, 共同指导后续的数据更新过程.即使数据不断变化, 本文的算法总能快速发现增量, 完成高效的数据更新.实验结果表明, 在大多数情况下, 本文方法能够取得较好的效果, 可为大数据分析和知识工程提供方便易用的数据基础.但是, 对部分社交媒体OBG数据的获取, 还需针对其本身的特点进一步研究, 后续工作将针对社交媒体数据中社交行为与社区演化的具体过程, 探索相应的OBG数据获取方法, 且保证其有效性和高效性.