面向多元时间序列的群体因果关系发现算法_蔡瑞初.pdf

第 49卷 第 2期2023年 2月Computer Engineering 计算机工程面向多元时间序列的群体因果关系发现算法蔡瑞初1，伍运金1，陈薇1，郝志峰1，2（1.广东工业大学 计算机学院，广州 510006；2.汕头大学 理学院，广东 汕头 515063）摘要：从多元时间序列观测数据中学习多个变量之间的因果关系是许多专业领域中的重要基本问题。现有的多元时间序列因果关系发现方法通常从每个个体的观测数据中学习个体因果关系，没有考虑部分个体之间可能存在相同的因果关系，导致样本利用不足。提出一种面向多元时间序列的群体因果关系发现算法。该算法分为 2个阶段：第一阶段基于因果关系对个体之间的相似性进行度量，并把多个个体划分成多个群体，且无须指定群体的个数；第二阶段基于变分推断方法充分利用每个群体内的所有个体数据，从而学习群体因果关系。实验结果表明，该算法在多组不同参数生成的仿真数据上均具有较好的表现，与对比算法相比，AUC 评分提升了 5%20%。在真实数据集中，该算法能够较好地区分具有不同因果关系的群体，并且能够学习到不同群体之间不同的因果关系，表明算法不仅具有因果关系发现能力，而且还具有多元时间序列聚类能力。关键词：群体因果发现；多元时间序列；因果关系；聚类；变分推断开放科学（资源服务）标志码（OSID）：中文引用格式：蔡瑞初，伍运金，陈薇，等.面向多元时间序列的群体因果关系发现算法 J.计算机工程，2023，49（2）：127-135.英文引用格式：CAI R C，WU Y J，CHEN W，et al.Collective causal relations discovery algorithm for multivariate time-series J.Computer Engineering，2023，49（2）：127-135.Collective Causal Relations Discovery Algorithm for Multivariate Time-SeriesCAI Ruichu1，WU Yunjin1，CHEN Wei1，HAO Zhifeng1，2（1.School of Computer，Guangdong University of Technology，Guangzhou 510006，China；2.College of Science，Shantou University，Shantou 515063，Guangdong，China）【Abstract】Causal discovery from multivariate time-series is a significant and fundamental problem in numerous disciplines.The existing multivariate time-series causal discovery methods learn the causal relations for each individual while some individuals may share the same causal relations；therefore，they may exploit data insufficiently.To this end，this study proposes a collective causal discovery algorithm for multivariate time-series，which is a two-stage algorithm.The first stage measures the similarity of individuals from the perspective of causal relations and clusters the individuals into different groups based on similarity without assigning the number of groups.The second stage involves learning the collective causal relations for each group using variational inference，which sufficiently utilizes the data of individuals in the same group.The experimental result shows that the proposed method outperforms existing methods on simulated data，and the AUC scores are improved by 5%-20%.On real data，the proposed algorithm can separate groups with different causal relations and determine the difference in causal relations for each group，which illustrates the capability of the proposed algorithm in causal discovery and multivariate time-series clustering.【Key words】collective causal discovery；multivariate time-series；causal relations；clustering；variational inferenceDOI：10.19678/j.issn.1000-3428.00636740概述 因果发现旨在从观测数据中发现变量之间的因果关系，可以揭露数据的生成机制，帮助人们理解数据，辅助人们进行干预和决策1。近年来，因果关系在深度学习2、金融经济3、神经科学4、生物信息学5、社会科学6等领域受到了广泛关注。当观测数据是多元时间序列数据时，现有的时序因果发现算法7-10通常认为个体之间是独立的，为每一个个体的多元时间序列数据单独学习一个因果基金项目：国家自然科学基金（61876043，61976052）；中国博士后科学基金（2020M680225）。作者简介：蔡瑞初（1983），男，教授、博士生导师，主研方向为机器学习、数据挖掘；伍运金，硕士研究生；陈薇，博士；郝志峰，教授、博士生导师。收稿日期：2021-12-31 修回日期：2022-02-28 Email：人工智能与模式识别文章编号：1000-3428（2023）02-0127-09 文献标志码：A 中图分类号：TP301.62023年 2月 15日Computer Engineering 计算机工程关系作为该个体背后的因果关系，而个体间的因果关系学习过程是彼此无关的。然而在实际中，个体之间可能存在相同的因果关系。举例来说，在电商场景下，同一群体中的个体的购买行为可能具有相同的思维方式，如对于家庭群体的个体是否购买某个商品的影响变量是商品的质量，而对于普通家庭群体的个体是否购买某个商品的影响变量则是商品的质量和价格。因此，来源于不同群体的个体的数据背后会具有不同的因果关系（产生机制），而相同群体的个体的数据背后会具有相同的因果关系。如果能知道哪些个体属于同一群体，便能利用群体内多个独立同分布的个体数据一起学习该群体共同的因果关系。然而，在实际中无法预先知道不同个体是否属于相同群体，也无法判断总共有多少个群体。针对上述问题，本文提出一种面向多元时间序列数据的群体因果关系发现算法。首先基于因果关系的相似性，将所有个体划分成多个群体且无须指定群体的个数。对于每一个群体，使用变分推断方法学习群体因果关系，从而充分利用多个个体数据。当所有个体均在一个群体时，该算法利用所有个体数据共同学习一个因果关系。当一个群体内只有一个个体时，该算法与现有时序因果关系发现算法类似，仅利用单个个体数据单独学习一个因果关系。1相关工作 因果关系发现算法按照观测数据的类型可以分为基于非时序数据的因果发现方法和基于时序数据的因果发现方法11。基于非时序数据的因果发现方法中包括基于约束的方法12、基于评分的方法13和基于函数的方法14-16。基于约束的方法利用（条件）独立性检验来判断变量之间是否存在因果关系，而基于评分的方法通过给 DAG 打分并寻找得分最高的 DAG 作为变量间的因果关系，但 2种方法都存在马尔可夫等价类的问题。为了解决这个问题，学者们提出了基于函数的方法，此类方法从数据产生机制出发，假设原因变量与结果变量存在函数映射，以及存在与原因变量独立的噪声变量，通过原因与噪声的独立性来识别因果关系。基于函数的方法包括线性非高斯无环模型（Linear Non-Gaussan Acyclic Model，LiNGAM）14、非线性加性噪声模型（nonlinear Additive Noise Model，ANM）15和后非线性因果模型（Post-NonLinear causal model，PNL）16。上述基于非时序数据的因果发现方法也被拓展到了时序数据上，如同样基于约束的PCMCI算法8、基于评分的DYNOTEARS算法9和基于函数的VAR-LiNGAM算法10。PCMCI算法基于条件独立性测试框架，使用PC算法17发现变量的马尔可夫等价类集合从而缩短条件集，进一步用瞬时条件独立性（Momentary Conditional Independence，MCI）检验降低误发现率。DYNOTEARS算法从优化问题的角度出发，最小化一个带无环约束的损失函数，从而学习变量之间的瞬时影响和时延影响。VAR-LiNGAM 算法结合自回归模型和线性非高斯无环模型来识别变量的瞬时和时延因果关系的影响权重，并通过非高斯性假设保证了算法的可识别性。目前一些工作4，18也考虑到了不同个体的样本背后的因果关系可能存在一定共性，并尝试从这种混杂样本中将样本划分成不同类别并学习因果关系。文献 4 与本文工作同样是面向多元时间序列数据，但其需要指定群体个数，并在此基础上学习个体特定的因果关系和共性的因果关系，再基于共性的因果关系计算某个个体属于不同群体的概率。文献 4 与本文工作的不同之处在于，其学习的是个体个性的因果关系以及个体间共性的因果关系，认为不同个体背后的因果关系仍然是不同的，仅是存在一定的共性因果关系，并基于共性进行聚类。本文工作则是在个体间的因果关系可能相同的场景下，对多个个体聚类并学习群体因果关系。此外，在实际应用中，群体个数往往是未知的，而本文所提出的算法无须指定群体个数。文献 18 考虑的则是二元变量之间的因果关系，在为每个样本识别了因果关系后，基于每个样本所对应的因果关系参数进行K-Means19聚类，因此也面临着需要指定群体个数的问题。2问题定义 本节对所研究的问题进行符号化定义和说明。定 义n个 个 体 的 多 元 时 间 序 列 数 据 集X=X1,X2,Xn，其中第s个个体的多元时间序列数据Xs=Xs1,Xs2,Xsm，且每个个体的变量数均为m，时间序列长度均为T。将最长的因果关系时间间隔记为k，多元时间序列数据的因果关系表示为k+1个m m的矩阵B0,B1,Bk，Bi,j 0表示第t时刻的变量xi(t)受到第t-时刻的变量xj(t-)的因果影响，且时间间隔为，0,1,k，其中=0时B表示瞬时因果关系，0时B表示时延因果关系。本文所考虑的问题是：给定多元时间序列数据集X，如何基于数据背后的因果关系将n个个体划分成c个群体，且c无须人工先验指定，并学习每个群体的因果关系。3LEAD算法 针对所研究问题，本文提出面向多元时间序列的群体因果关系发现算法 LEAD。该算法分为 2 个阶段：第一阶段是基于因果关系