Page 101 - 《软件学报》2021年第10期

王双成 等:基于贝叶斯网络的时间序列因果关系学习 3073

我们能够发现,丢失数据的迭代修复实际上采用的是贝叶斯网络局部随机模拟技术.由于 X 1 [t],X 2 [t],...,X n [t]
的真实贝叶斯网络未知,因此使用最大似然树来代替贝叶斯网络.在迭代中,使用最大似然树产生的局部模拟数
据依次更新上一次迭代修正过的丢失数据(或者初始化的数据),这一迭代过程在理论上将收敛到全局平稳分
布.这样的迭代修复能够有效减少信息的丢失和降低噪声的引入量,提高经过丢失数据修复的数据集质量.
1.2 时间序列的因果关系结构学习

时间序列的因果关系结构学习是因果关系学习的核心,在时间序列预处理的基础上,我们结合变量排序,转
换数据集构建和局部贪婪打分-搜索进行时间序列的因果关系结构学习.
(1) 时间序列变量的排序
目前,基于数据的变量排序主要采用打分-搜索方法(打分函数一般使用卡方或 MDL 标准等,搜索策略则选
择贪婪或启发式搜索等),不但效率低,而且往往不能完全排序(存在一些变量无法排序).我们基于信息理论给出
变量删除法来排序变量,不但效率高,还可完全排序变量.时间序列变量(简称时序变量)包括非时滞变量和时滞
变量,我们首先采用变量删除法来排序非时滞变量(时序变量排序的主要部分),然后依据专家知识(数据产生的
先后顺序)对非时滞变量的顺序进行调整.调整的具体过程是:当依据变量删除法对非时滞变量进行排序之后,
如果存在两个非时滞变量之间的顺序与专家知识不一致,则交换这两个非时滞变量在序列中的位置;这时也可
能产生新的不一致,继续调整,直到非时滞变量的顺序与专家知识没有冲突为止;最后,再按照时间顺序加入时
滞变量,得到最终时序变量的顺序.
对于非时滞变量矩阵( ij ) nn ,首先选取 ij ≥0(i,j=1,…,n,当且仅当 i=j 时 ij =0)的行所对应的变量作为第 1 个
变量(排在最前面的变量), ij ≥0 的行表示 X i 对 X j (j=1,…,i1,i+1,…,n)的影响要大于 X j 对 X i 的影响.在矩阵中删
除满足条件的行和对应的列(对应的第 i 列则表示 X j 对 X i 的影响要小于 X i 对 X j 的影响),剩下的是一个 n1 阶
矩阵,在这个 n1 阶矩阵中重复第 1 个变量的选择方法可得到第 2 个变量,如此下去便可对所有变量排序.为表
述方便,仍用 X 1 [t],X 2 [t],...,X n [t]和 D d [n,T]表示排序后的非时滞变量以及对应的时序数据集, ij 的计算方法如下:
 HX [ ]|t X [])t H (X []|t X [ ])t
(
  1, i j  j i
(
[ ])
 HX i [ ]) t H (X t
j
 HX t []) H (X t [ ])
[]| X t
[ ]| X t
(
 ij   ji    0, i j  j i (6)
[ ])
[ ])
(
 HX t H (X t
i
j
 HX t []) H (X t [ ])
(
[ ]| X t
[]| X t
  1, i j  j i
  HX i [ ]) t H (X t
(
[ ])
j
HX i [ ]|t X j [ ])t
(
其中,H(X i [t]|X j [t])和 H(X j [t]|X i [t])是条件熵; 是条件相对熵,表示 X j [t]为 X i [t]提供的相对信息.如果
HX i [ ])t
(
X i [t]是 X j [t]的原因,那么相对于 X j [t]为 X i [t]提供的相对信息,X i [t]将为 X j [t]提供更多的相对信息.我们将这种非时
滞变量的排序方法称为变量删除法.可以证明,使用变量删除法排序非时滞变量不会产生环路.
(2) 转换数据集构建
转换数据集能够实现时滞与非时滞信息的统一,从而可在转换数据集的基础上,采用贝叶斯网络方法发现
多变量时间序列中所蕴含的时滞、非时滞和混合因果关系.
定义 1. 对给定的时序数据集 D d [n,T]={x 1 [t],x 2 [t],...,x n [t]}(n≥1,1≤t≤T),称数据集
t
[ , , ] { [T q
Dn  x t v 1 ],..., [x t v 1 ], [ ],..., [x t x t v n ],..., [x t v n ], [ ]}(max{ , ,..., } 1x t q q q  ≤≤ ) T (7)
d 1 1 q 1 1 1 n n q n 1 n 1 2 n
为 D d [n,T]的转换数据集,其中,q=(q 1 ,q 2 ,…,q n )(q i ≥0,1≤i≤n)是时滞阶数向量,{Xt v [ i ],...,X [t v i ]} 是 X i [t]的
i i q i i
n
时滞变量集,时序变量的数量是 n   q i , 记录的数量是 Tmax{q 1 ,q 2 ,…,q n }.
i 1
定义 1 给出的转换数据集可用于单变量和多变量时间序列的因果关系学习,对于单变量时间序列(n=1),一
i
般设置 v  q i (1≤≤ n ). 假设 n>1,在 D d [n,T,q]中,我们将 X 1 [t],...,X i1 [t],X i+1 [t],...,X n [t]与 X i [t]之间的因果关系称
i
i q