Page 229 - 《软件学报》2020年第11期

3544 Journal of Software 软件学报 Vol.31, No.11, November 2020

在子空间重要性评估阶段,我们首先将高维空间 A 按照子空间划分方法进行分割,并由 QMC 采样得到每个
子空间的重要性.将需要收集的信息视为目标信息,例如网页 OBG 中特定主题的信息,或社交媒体 OBG 中的用
户信息和关注、转发、评论及点赞等社交行为.子空间中目标信息量又决定了子空间的重要性,我们使用目标
信息密度来度量子空间的重要性,目标信息密度与聚焦爬虫中数据收集目标的概念类似,反映了 OBG 数据收集
时子空间中的目标信息量.下面给出子空间 A s 中目标信息密度的概念.
∑ D (Ψ )
∈
ρ s A = oA s s | o (2)
| A
其中,D(Ψ o )代表一个 OBG 中对象 o 所包含的目标信息量.若将社交媒体 OBG 中的社交行为作为目标信息,则子
空间的目标信息密度为该子空间中社交行为的数量与子空间对象总数的比值.
为了快速计算子空间的重要性,我们利用 QMC 采样技术,通过少量采样点尽可能精确地计算不同子空间
的目标信息密度,由此找到最重要的子空间.QMC 使用确定性的方法生成低差异的伪随机序列(low-discrepancy
sequence) [24] ,并将其作为采样点,这些采样点对子空间的覆盖性优于随机点.QMC 通常将 Halton 序列作为其伪
j
+
i
随机序列进行采样,令 b 为一个素数,则任何一个正整数 Z 可表示为 d j b +…+d i b +…+d 1 b+d 0 ,其中,d i ∈{0,1,…,
d d d j
b−1},且 i=0,1,…,j.在一个 Halton 序列 W 中,第 w 个元素φ b (w)为 0 + 1 + ...+ .同时,对于任何 w>0,有φ b (w)∈
b 1 b 2 b j+ 1

[0,1].对于 h 个不同的素数 b 1 ,…,b d ,n 个 h 维的 Halton 序列为{ ,..., },x 1 x n x 可表示为
i
x = [φ (i − 1),...,φ (i − 1)] ,i = T 1,...,n (3)
i 1 b n b
|
因此,第 J 次子空间划分后,第 i 个采样点在每个子空间中的相对坐标为 x k ... k × h | O ,其中,“ ”代表
i 1 J
哈达马积(Hadamard product).令采样点数 n=|A s |⋅R samp ,其中,R samp 为采样比率,{o 1 ,…,o i ,…o n }∈A s 为子空间 A s 中用
Halton 序列生成的 n 个采样点对应的采样对象,则 ρ 可作如下近似计算.
s A
1
ρ ≈ ∑ n D ( Ψ ) (4)
s A n i= 1 i o
值得说明的是,以上采样过程不仅可得到子空间的重要性,还可得到采样点的对象数据Ψ . 因此,本文的数
i o
据收集方法通过采样过程完成,不仅并行地对每次分割得到的各个子空间进行采样,而且并行地收集每个子空
间内部的采样对象 o i ,从而得到Ψ ,已收集的对象数据集合表示为Ψ c {Ψ = c ,Ψ c ,...,Ψ c } .为了使得相关应用能
i o 1 2 | | O
通过统一的接口访问已收集数据,我们将已收集的数据统一表示为 RDF 形式,记为〈对象 1,关系,对象 2〉的三元
组形式,其中,“关系”可以表示网页 OBG 中的链接、社交媒体 OBG 中的社交操作以及知识库 OBG 中实体间的
关系类型.
在子空间选择阶段,我们根据 QMC 采样得到的子空间目标信息密度找出下一次迭代的子空间.所有本次
及以往迭代中访问过的子空间的目标信息密度都被记录在一个候选子空间集合 P cand 中, P cand = {ρ 1 A ,ρ 2 A ,...,
ρ ,ρ } ,其中,ρ x 是之前迭代访问过的子空间的目标信息密度.为了能够自适应地收集数据,始终从 P cand 中选取
A K x
目标信息密度最大的子空间作为下一次迭代的高维空间.
由于存在某些目标信息较少且无需收集的子空间,如分散孤立的部分,使得数据收集效率较低.对此,下面
给出算法的结束条件.
ρ < ρ min (5)
其中, ρ 是所有采样的平均目标信息密度,ρ min 是能够接受的最小子空间目标信息密度.随着大多数高密度子空
间逐渐收集完成,剩下的子空间中的目标信息将越来越少, ρ 相应下降.最终,当 ρ < ρ min 时,整个收集过程结束.
上述思想由算法１描述.
算法 1. HD-QMC.
输入:A,K,R samp ,P cand .
c
输出:Ψ .
步骤: