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

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

已收集数据 新数据

T T
T 0
统计窗口
Fig.5 Statistic window of data updating
图 5 数据更新的统计窗口
数据更新方法建立在数据收集方法之上,包括增量预测和增量搜索两个阶段.数据更新方法将定义 4 表示
的增量作为目标信息,子空间重要性的度量依据仍采用目标信息密度,在数据更新中为增量密度.因此,数据更
新方法可看作是对第 2 节中数据收集方法的扩展.
c
增量预测阶段利用 HD-QMC 算法输出的已收集数据Ψ ,通过使用信息熵和泊松过程对统计窗口内 G ON 各
子空间变化的可能性进行量化,预测各个子空间的增量密度,得到各个子空间的初始增量密度.增量搜索阶段以
增量作为收集目标,基于并扩展 HD-QMC 算法,给出 QMC 采样得到的增量密度与增量预测阶段预测得到的增
量密度进行合理融合的方法,并使用融合后的增量密度作为子空间重要性的度量依据,以此帮助发现更多的增
量,并用增量来更新本地数据,从而优化数据更新过程.
3.2 基于信息熵的数据更新算法
B
B
在增量预测阶段,假设当前已收集数据的统计窗口中对应数据的 OBG 为 G ON ,我们将 G ON 映射到高维空间
B
并分割为 K 个子空间,即 G ON = {,B B 2 ,...,B K }.泊松过程是累计随机事件发生次数的独立增量过程 [12] ,同时,B j 内
1
增量的产生并没有确定的规律且相互独立,是一个随机事件,因此某段时间内,B j 中增量产生的大小可用泊松过
程来描述和预测.从 T 到 T′时刻,用信息熵表示子空间的信息量,则可根据信息熵运用泊松过程来预测未来一段
时间内增量产生的可能性,以此对这些子空间进行独立的更新.
定义 6. 设一个 OBG 中从 T 0 到 T 时刻 O,E 和 R 的出现概率分别为 P(o i ),P(e i )和 P(r i ),其信息熵分别为
H(O)=E[I(o i )],H(E)=E[I(e i )],H(R)=E[I(r i )].
其中,I(o i )=−logP(o i ),I(e i )=−logP(e i ),I(r i )=−logP(r i ).子空间 B j 的信息量即为
Y j =|O j |⋅H(O)+|E j |⋅H(E)+|E j |⋅H(R).
其中,O j 和 E j 即为对象集合和连接集合,o i ,e i ∈B j ,j=1,2,…,K.
Y
定义 7. 令 λ = j 为泊松分布的均值,若在ΔT 内增量的大小为τ,则增量产生的概率为
α (T − T 0 )

{(ΔT +
T
PX T ) − X T = ( ) τ = } е − λ Δ ( Δ )Tλ τ (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 1 ,U 2 ,…,U j ,…,U K }.
最后,将 U j /|B j |作为子空间的初始增量密度,并加入到 P cand 中.
B
在增量搜索阶段,由于从 G ON 的子空间 B j 中得到的 U j 不一定能很好地反映真实的增量大小,但在 OBG 的
采样过程中能对真实的增量大小进行评估,因此我们引入融合比率β,将 U j /|B j |与采样得到的增量密度进行合理
融合,以便从 K 叉树的第 2 层开始指导子空间的选取,并快速发现 OBG 中真实的增量.实际采样过程中,对于 K
叉树中任意层的迭代节点,第 j 个子空间的增量密度表示为 V jl ,通过 QMC 采样方法计算:
( ) ⎤
1 n ⎛ HO ⎞ ⎡
V ≈ jl ε = ⎜ 1 ⎢ ∑ ⎜ N ε ⎥ + N ⋅ ε H ()E + N ⋅ ε H ( )R ⎟ ⎟ (12)
n ⎢ N + 1 ⎥ ⎝ ⎠
ε
() ⎤
⎡ HO
() +
其中,N ε 和 n 分别为采样得到的新连接数和采样点数,l 为 K 叉树的层数. N ε ⎥ + N ⋅ ε H E N ⋅ ε H ( ) R 代表
⎢
⎢ N + 1 ⎥
ε