融合先驗(yàn)約束的拓?fù)浠艨怂惯^程格蘭杰因果發(fā)現(xiàn)算法

收稿日期：2021-12-01；修回日期：2022-02-07" 基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目（61876043，61976052）

作者簡介：蔡瑞初（1983-），男（通信作者），浙江溫州人，教授，博導(dǎo)，博士，主要研究方向?yàn)橐蚬P(guān)系發(fā)現(xiàn)、因果性學(xué)習(xí)、深度學(xué)習(xí)及其應(yīng)用（cairuichu@gmail.com）；劉躍群（1996-），男，廣東潮州人，碩士研究生，主要研究方向?yàn)橐蚬P(guān)系；黃正婷（2000-），女，廣東東莞人，主要研究方向?yàn)橐蚬P(guān)系、自然語言處理；黃曉楷（1999-），男，廣東潮州人，主要研究方向?yàn)橐蚬P(guān)系、機(jī)器學(xué)習(xí)；陳薇（1993-），女，廣東潮州人，研究員，博士，主要研究方向?yàn)橐蚬P(guān)系發(fā)現(xiàn)、因果性學(xué)習(xí)；郝志峰（1968-），男，江蘇蘇州人，教授，博導(dǎo)，博士，主要研究方向?yàn)闄C(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘．

摘 要：離散時序數(shù)據(jù)的格蘭杰因果關(guān)系發(fā)現(xiàn)算法具有重要應(yīng)用價(jià)值。現(xiàn)有方法主要采用霍克斯過程建模，無法適用于非獨(dú)立同分布數(shù)據(jù)和帶有時間誤差的數(shù)據(jù)。為此，提出了一種融合先驗(yàn)約束的拓?fù)浠艨怂惯^程格蘭杰因果關(guān)系發(fā)現(xiàn)算法（PTHP）。首先，使用基于約束的方法篩選出一批顯著性水平較高的因果邊，提升算法對故障發(fā)生時間誤差的容忍性；隨后，將上一步獲取的邊作為先驗(yàn)約束融合到拓?fù)浠艨怂惯^程中，解決序列間的非獨(dú)立同分布問題。模擬數(shù)據(jù)和真實(shí)數(shù)據(jù)的實(shí)驗(yàn)證明了該方法的有效性，并獲得了PCIC 2021因果推理大賽第一名。

關(guān)鍵詞：格蘭杰因果；拓?fù)浠艨怂惯^程；因果關(guān)系發(fā)現(xiàn)；因果關(guān)系網(wǎng)絡(luò)；時間誤差

中圖分類號：TP181"" 文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695（2022）06-011-1668-05

doi：10.19734/j.issn.1001-3695.2021.12.0642

Granger causality discovery algorithm for topological Hawkes processes with priori-constraints

Cai Ruichu1，Liu Yuequn1，Huang Zhengting1，Huang Xiaokai1，Chen Wei1，Hao Zhifeng1，2

（1.School of Computer Science，Guangdong University of Technology，Guangzhou 510006，China；2.College of Science，Shantou University，Shantou Guangdong 515063，China）

Abstract：Granger causality discovery algorithm for discrete-time series data has important application value.The existing methods mainly use Hawkes processes modeling，which can not be applied to non-IID data and data with time-skew errors.Therefore，this paper proposed a Granger causality discovery algorithm （PTHP） for topological Hawkes processes integrating a priori constraints.Firstly，it used the constraint-based method to screen a group of causal edges with a high significance level to improve the tolerance of the algorithm to the fault time-skew errors.Then，the edges obtained in the previous step were fused into the topological Hawkes processes as a priori constraints to solve the non-IID problem between sequences.Experiments on simulated data and real-world data show the effectiveness of this method，and it won first place in PCIC 2021 causal inference competition.

Key words：Granger causality；topological Hawkes processes（THP）；causal discovery；causal network；time-skew errors

0 引言

時序數(shù)據(jù)上的因果關(guān)系發(fā)現(xiàn)算法已經(jīng)成為當(dāng)前的熱點(diǎn)問題，被廣泛應(yīng)用于智能運(yùn)維［1］、智慧交通［2］、金融交易［3］等領(lǐng)域。目前的時序數(shù)據(jù)上的因果發(fā)現(xiàn)算法主要分為基于約束的方法、基于因果函數(shù)模型的方法和基于點(diǎn)過程的方法。基于約束的方法使用假設(shè)檢驗(yàn)的方法來檢測變量之間的關(guān)系，其中PCMCI［4］算法是較為常用的算法。基于因果函數(shù)模型的方法［5～7］主要適用于連續(xù)型數(shù)據(jù)的因果關(guān)系發(fā)現(xiàn)，對于離散時序數(shù)據(jù)的建模存在一定的不足。基于點(diǎn)過程的方法則通過對數(shù)據(jù)生成過程進(jìn)行建模來捕獲變量之間的關(guān)系，其中霍克斯過程（hawkes processes，HP）［8］是常見的建模方法。上述方法都假設(shè)數(shù)據(jù)是獨(dú)立同分布的，而在實(shí)際根因定位的場景中，受設(shè)備拓?fù)涞刃畔⒂绊懀收闲蛄袛?shù)據(jù)是非獨(dú)立同分布的。為了解決這個問題，拓?fù)浠艨怂惯^程（THP）［9］在霍克斯過程的基礎(chǔ)上，將數(shù)據(jù)假設(shè)拓展到非獨(dú)立同分布特征。霍克斯過程的一個假設(shè)是，過去發(fā)生的A事件會激勵B 事件在未來的發(fā)生幾率，激勵程度由一個衰減核建模。這種假設(shè)的前提是數(shù)據(jù)的時間記錄是準(zhǔn)確無誤的。然而，在很多現(xiàn)實(shí)場景下，數(shù)據(jù)受到機(jī)器條件的制約等原因，會出現(xiàn)記錄時間存在誤差的問題，不再符合記錄時間是準(zhǔn)確的前提。例如，當(dāng)機(jī)器設(shè)備對時間記錄的精度是精確到毫秒，而兩個事件以小于1 ms的時間間隔先后發(fā)生時，收集到的數(shù)據(jù)集上這兩個事件記錄就是同時發(fā)生的。在這種情況下，霍克斯過程就無法捕獲這兩個事件之間的激勵關(guān)系。

拓?fù)浣Y(jié)構(gòu)下數(shù)據(jù)記錄存在時間誤差的問題大大降低了基于霍克斯過程的因果關(guān)系發(fā)現(xiàn)算法的準(zhǔn)確率。為了解決從有誤差和非獨(dú)立同分布時間序列數(shù)據(jù)上進(jìn)行因果關(guān)系發(fā)現(xiàn)不準(zhǔn)確的問題，本文提出融合先驗(yàn)約束的拓?fù)浠艨怂惯^程格蘭杰因果關(guān)系發(fā)現(xiàn)框架（priori-based topological Hawkes processes，PTHP），將因果網(wǎng)絡(luò)的搜索劃分為兩階段，從而把基于約束的方法的魯棒性優(yōu)勢結(jié)合到霍克斯過程中。第一階段是先驗(yàn)邊的搜索階段，通過基于約束的方法先篩選出一批可靠的因果關(guān)系邊，將這批邊作為因果網(wǎng)絡(luò)的先驗(yàn)邊固定下來，解決樣本數(shù)據(jù)存在時間誤差的問題。第二階段是拓?fù)浠艨怂惯^程的建模階段，使用爬山法［10，11］，以第一階段的先驗(yàn)因果網(wǎng)絡(luò)為起點(diǎn)，搜索似然值最大的因果網(wǎng)絡(luò)結(jié)構(gòu)，解決非獨(dú)立同分布數(shù)據(jù)下的因果發(fā)現(xiàn)問題。本文的貢獻(xiàn)在于：a）提出兩階段的融合先驗(yàn)約束的拓?fù)浠艨怂惯^程格蘭杰因果關(guān)系發(fā)現(xiàn)框架，解決序列數(shù)據(jù)帶有時間誤差和非獨(dú)立同分布問題；b）把PCMCI作為先驗(yàn)搜索方法結(jié)合到拓?fù)浠艨怂惯^程中，而無須專家知識；c）模擬數(shù)據(jù)和真實(shí)數(shù)據(jù)證實(shí)了本文方法的正確性和有效性。

1 相關(guān)工作

目前時序數(shù)據(jù)上的因果發(fā)現(xiàn)算法主要分為基于約束的方法、基于因果函數(shù)模型的方法和基于點(diǎn)過程的方法。由于基于因果函數(shù)模型的方法較少關(guān)注離散事件序列數(shù)據(jù)，所以在此僅對基于約束的方法和基于點(diǎn)過程的方法進(jìn)行介紹。

1.1 基于約束的方法

基于約束的方法［12］通過變量間的條件獨(dú)立性來判斷變量之間因果關(guān)系的存在性。此類方法同時考慮了事件滯后影響和瞬時效應(yīng)，可以較好地識別有時間誤差下的因果網(wǎng)絡(luò)結(jié)構(gòu)中顯著性明顯的邊。常見的條件獨(dú)立性檢驗(yàn)方法有偏相關(guān)檢驗(yàn)、希爾伯特—施密特獨(dú)立性準(zhǔn)則［13］、核條件獨(dú)立性檢驗(yàn)［14］、基于熵的（條件）獨(dú)立性檢驗(yàn)方法［15］。非時序數(shù)據(jù)上基于約束的經(jīng)典方法是PC（Peter-Clark）算法［16］和IC（inductive causation）算法［17］。Runge等人近期將PC算法推廣到多變量時序數(shù)據(jù)上，提出了PCMCI算法。

1.2 基于點(diǎn)過程的方法

對于如下形式的時序點(diǎn)過程數(shù)據(jù)X={vi，ti}mi=1，其中vi∈V 和t i∈T是第i個記錄的事件類型和發(fā)生時間，點(diǎn)過程模型使用強(qiáng)度函數(shù)來表示在給定歷史事件數(shù)據(jù)下，當(dāng)前時刻事件的發(fā)生強(qiáng)度：

λv（t）dt=λv（t|HVt）dt=E［dCv（t）|HVt］（1）

其中：HVt={ti，vi|tilt;t，vi∈V}表示在時間t之前所有類型的事件記錄的集合；Cv（t）∈Euclid Math TwoNAp是事件v到時間t時發(fā)生次數(shù)的記錄。經(jīng)典的點(diǎn)過程模型都是基于數(shù)據(jù)是獨(dú)立同分布的假設(shè)來建模，比如泊松點(diǎn)過程［18］、霍克斯過程［8］和神經(jīng)點(diǎn)過程［19］等。基于霍克斯過程的經(jīng)典算法是MLE-SGL［8］和ADM4［20］算法。Cai等人［9］近期提出了THP算法，將拓?fù)浣Y(jié)構(gòu)引入霍克斯過程，并從時空領(lǐng)域上對強(qiáng)度函數(shù)建模，以發(fā)現(xiàn)非獨(dú)立同分布的點(diǎn)過程數(shù)據(jù)上的格蘭杰因果關(guān)系。

以上時序點(diǎn)過程模型都是基于數(shù)據(jù)記錄時間是準(zhǔn)確無誤的假設(shè)做的工作。而在真實(shí)應(yīng)用場景下，受設(shè)備情況影響，數(shù)據(jù)可能出現(xiàn)時間誤差等各種問題，導(dǎo)致以上的模型效果欠佳。

2 PTHP

2.1 問題定義

在基于約束的方法和拓?fù)浠艨怂惯^程的基礎(chǔ)上，本文提出了一種融合先驗(yàn)約束的拓?fù)浠艨怂惯^程格蘭杰因果關(guān)系發(fā)現(xiàn)算法，以發(fā)現(xiàn)有時間誤差的非獨(dú)立同分布下的點(diǎn)過程數(shù)據(jù)背后的因果關(guān)系，稱之為融合先驗(yàn)約束的拓?fù)浠艨怂惯^程格蘭杰因果發(fā)現(xiàn)算法（priori-based topological Hawkes processes，PTHP）算法。

在PTHP中，X={ni，vi，ti}mi=1表示有時間誤差下的拓?fù)潼c(diǎn)過程數(shù)據(jù)，其中ni表示該條數(shù)據(jù)記錄所產(chǎn)生的拓?fù)湓O(shè)備。令無向圖GN=（N，EN）表示數(shù)據(jù)背后的拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu)，其中拓?fù)渚W(wǎng)絡(luò)的節(jié)點(diǎn)集合為N，無向邊的集合為EN。令有向無環(huán)圖GV=（V，EV）表示事件類型之間的因果關(guān)系網(wǎng)絡(luò)，其中事件類型集合為V，有向邊的集合為EV。本文研究的問題可以表示為如何求解PTHP中的GV。

2.2 PTHP框架

為了求解PTHP中的因果網(wǎng)絡(luò)結(jié)構(gòu)GV如圖1所示，本文提出了一個兩階段因果關(guān)系發(fā)現(xiàn)框架。在第一階段，該框架把X按不同事件類型劃分成|V|個時間序列，隨后使用基于約束的因果關(guān)系發(fā)現(xiàn)方法，篩選出其中一批置信值高的因果網(wǎng)絡(luò)邊，作為下一階段中拓?fù)浠艨怂惯^程的先驗(yàn)因果網(wǎng)絡(luò)結(jié)構(gòu)G*V。在第二階段，將G*V作為拓?fù)浠艨怂惯^程中爬山法的起點(diǎn)，并且固定先驗(yàn)因果網(wǎng)絡(luò)結(jié)構(gòu)不變動，搜尋剩余因果網(wǎng)絡(luò)結(jié)構(gòu)集合中負(fù)對數(shù)似然最小的因果網(wǎng)絡(luò)結(jié)構(gòu)GV。

綜上，PTHP算法首先使用基于約束的方法，通過高置信值篩選出一批可靠的因果網(wǎng)絡(luò)邊，將其作為先驗(yàn)約束融入第二階段的拓?fù)浠艨怂惯^程格蘭杰因果關(guān)系發(fā)現(xiàn)中。此融合方法的巧妙之處在于利用基于約束方法的魯棒性特點(diǎn)，尋找顯著性水平較高的邊，由此組成的先驗(yàn)因果網(wǎng)絡(luò)結(jié)構(gòu)可以作為后續(xù)算法步驟中可靠的約束。這大大縮小了拓?fù)浠艨怂惯^程中潛在的因果網(wǎng)絡(luò)的搜索空間，同時減少了由于時間誤差導(dǎo)致因果發(fā)現(xiàn)錯誤邊的影響，從而有效提升算法在有時間誤差的非獨(dú)立同分布數(shù)據(jù)上進(jìn)行格蘭杰因果關(guān)系發(fā)現(xiàn)的效果。

2.3 先驗(yàn)因果網(wǎng)絡(luò)結(jié)構(gòu)構(gòu)建

在PTHP的第一階段中，一個重要的問題是選用何種基于約束的方法來獲取因果網(wǎng)絡(luò)的先驗(yàn)邊。在實(shí)際應(yīng)用中，本文使用時序數(shù)據(jù)上的PCMCI算法。考慮如下形式的點(diǎn)過程數(shù)據(jù)X={ni，vi，ti}mi=1，其時間范圍為ti∈［0，T］。在使用算法之前，本文進(jìn)行了如下形式的數(shù)據(jù)預(yù)處理，以使其滿足基于約束算法所需的多變量時序數(shù)據(jù)形式：首先，將原數(shù)據(jù)按事件類型劃分成|V|個子序列X={X1，X2，…，X|V|}；隨后，根據(jù)預(yù)先設(shè)定的時間窗口大小W將每個事件類型v∈V劃分為「TW個時間區(qū)間下的離散時序變量Xv={xi}，i∈{1，2，…，「TW}，若在時間區(qū)間i內(nèi)存在事件v的記錄，則對應(yīng)xi的值為1，否則為0。

PCMCI算法分為兩階段：a）因果關(guān)系骨架連接圖的搜索階段，記變量Xv在時間滯后τ∈{0，1，…，τmax}下的表示為Xvt-τ，則PCMCI第一階段可以表示為使用獨(dú)立性檢驗(yàn)方法搜尋所有與Xvt不獨(dú)立的Xv′t-τ的集合，即找到變量Xvt所有可能的父母變量Xv′t-τ的集合（Xvt）={Xv′t-τ|0lt;τ≤τmax，XvtEuclid Math OneMBpXv′t-τ}；b）冗余邊去除階段，使用瞬時條件獨(dú)立性（momentary conditional independence，MCI）檢測的方法，判斷給定Xvt和Xv′t-τ的父母變量后第一階段變量的不獨(dú)立性關(guān)系是否仍然成立，若不再成立，則去除掉（Xvt）中的Xv′t-τ，即當(dāng)Xv′t-τ‖Xvt|（Xvt）＼{Xv′t-τ}，（Xv′t-τ），令（Xvt）=（Xvt）＼{Xv′t-τ}。

在運(yùn)行完P(guān)CMCI算法后，本文將變量間的因果關(guān)系轉(zhuǎn)換為對應(yīng)事件之間的因果關(guān)系，得到了一個因果網(wǎng)絡(luò)結(jié)構(gòu)以及每條邊對應(yīng)獨(dú)立性檢驗(yàn)結(jié)果的置信值，通過預(yù)先設(shè)定的置信值水平，本文篩選出一批高度可信的邊作為先驗(yàn)邊保留下來，作為下一階段的先驗(yàn)因果網(wǎng)絡(luò)結(jié)構(gòu)G*V。

2.4 融合先驗(yàn)信息的拓?fù)浠艨怂惯^程建模

大部分點(diǎn)過程的工作都是基于數(shù)據(jù)符合獨(dú)立同分布的假設(shè)，然而很多現(xiàn)實(shí)應(yīng)用中的數(shù)據(jù)不再符合這個要求。THP假設(shè)點(diǎn)過程數(shù)據(jù)產(chǎn)生過程背后有一個拓?fù)渚W(wǎng)絡(luò)GN=（N，EN），事件序列的因果強(qiáng)度函數(shù)不僅受到自身的歷史數(shù)據(jù)的激勵，也跟拓?fù)渚W(wǎng)絡(luò)中鄰居設(shè)備的歷史數(shù)據(jù)有關(guān)，從而使數(shù)據(jù)不再符合獨(dú)立同分布的特性。THP的目標(biāo)可表示為尋找非獨(dú)立同分布事件序列背后的因果網(wǎng)絡(luò)GV=（V，EV）。基于THP的思想，本文融合先驗(yàn)因果網(wǎng)絡(luò)信息，使用爬山法搜索最優(yōu)的因果網(wǎng)絡(luò)GV。具體過程是，以第一階段的因果先驗(yàn)網(wǎng)絡(luò)結(jié)構(gòu)G*V為初始結(jié)構(gòu)，爬山法中每一步可分為兩個子步驟：a）令S（GV）為在當(dāng)前因果網(wǎng)絡(luò)GV上非先驗(yàn)邊處執(zhí)行一次加邊或者減邊之后的網(wǎng)絡(luò)結(jié)構(gòu)集合，計(jì)算原始數(shù)據(jù)X在S（GV）中對應(yīng)的似然最大的網(wǎng)絡(luò)結(jié)構(gòu)G′V；b）若G′V對應(yīng)的似然比GV對應(yīng)的似然更大，則采納G′V作為下一輪爬山法的起點(diǎn)，否則，停止迭代，輸出當(dāng)前的因果網(wǎng)絡(luò)GV作為最終的因果網(wǎng)絡(luò)結(jié)構(gòu)。

算法1 PTHP算法

輸入：觀察數(shù)據(jù)集X；置信值閾值ρ。

輸出：GV。

將X按事件類型劃分成時間序列X1，X2，…，X|V|

將X1，X2，…，X|V|輸入PCMCI算法，求得因果網(wǎng)絡(luò)G*V和每條邊的置信值w*v′，v

for G*V中每條邊e do

if e對應(yīng)w*v′，v的小于ρ then

從G*V中刪除e

end if

end for

計(jì)算X在G*V下的似然l*和模型參數(shù)θ*

l←-∞

while llt;l*do

〈GV，θ，l〉←〈G*V，θ*，l*〉

for G′V∈S（GV） do

計(jì)算X在G′V下的l′和θ′

end for

〈G*V，θ*，l*〉←l′最大的〈G′V，θ′，l′〉

end while

return GV

3 實(shí)驗(yàn)結(jié)果與分析

為了對PTHP算法的實(shí)際效果進(jìn)行驗(yàn)證和分析，本文分別使用模擬數(shù)據(jù)和真實(shí)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，并與基準(zhǔn)方法進(jìn)行了對比。所對比的基準(zhǔn)算法有：基于獨(dú)立同分布數(shù)據(jù)下霍克斯過程的算法，包括MLE-SGL［8］和ADM4［20］；基于非獨(dú)立同分布數(shù)據(jù)下霍克斯過程的算法，包括THP［9］；基于約束的算法，包括PCMCI［4］。本文就上述基準(zhǔn)方法進(jìn)行簡單介紹，具體如下：

a）MLE-SGL［8］。該算法將最大似然估計(jì)器（MLE）與稀疏組套索（SGL）正則化器相結(jié)合以進(jìn)行霍克斯過程建模，學(xué)習(xí)事件類型間的格蘭杰因果關(guān)系。

b）ADM4［20］。該算法結(jié)合了乘法器的交替方向方法和主化最小化技術(shù)以進(jìn)行霍克斯過程建模，實(shí)現(xiàn)格蘭杰因果關(guān)系發(fā)現(xiàn)。

c）THP［9］。該算法通過在霍克斯過程中引入事件記錄背后的拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu)，從時空領(lǐng)域上建模，實(shí)現(xiàn)了非獨(dú)立同分布數(shù)據(jù)下的格蘭杰因果關(guān)系發(fā)現(xiàn)。

d）PCMCI［4］。該算法在第一階段使用基于約束的方法搜索事件類型在不同時間滯后下的父母事件類型集合，在第二階段引入瞬時條件獨(dú)立性檢測去除冗余的因果關(guān)系，提高了格蘭杰因果關(guān)系發(fā)現(xiàn)的準(zhǔn)確率。

3.1 模擬數(shù)據(jù)實(shí)驗(yàn)

模擬數(shù)據(jù)的生成方法參考了文獻(xiàn)［21，22］提出的點(diǎn)過程數(shù)據(jù)模擬生成方法，并將其拓展到數(shù)據(jù)產(chǎn)生背后存在拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu)下的非獨(dú)立同分布情況以及存在時間誤差數(shù)據(jù)的情況。主要分為四個步驟實(shí)現(xiàn)：

a）隨機(jī)生成一個有向因果圖GV和無向拓?fù)鋱DGN，并按存在時間誤差的數(shù)據(jù)比例選定部分因果邊標(biāo)記為存在時間誤差問題。在圖2中，本文展示了存在10個事件類型的因果圖GV，每條有向邊表示原因事件的發(fā)生會提高接下來結(jié)果事件的發(fā)生概率。在圖3中，本文展示了存在10個拓?fù)湓O(shè)備的拓?fù)渚W(wǎng)絡(luò)圖GN，每條無向邊連接了兩個設(shè)備，表示其中一個設(shè)備上發(fā)生的原因事件記錄也會激勵接下來拓?fù)溧従釉O(shè)備上的結(jié)果事件發(fā)生的概率。

b）隨機(jī)生成每個事件類型v對應(yīng)霍克斯過程中的基本強(qiáng)度μv的值，在每個拓?fù)湓O(shè)備上按泊松分布的參數(shù)為μv生成每個事件的根因事件序列。

c）隨機(jī)生成事件類型之間對應(yīng)霍克斯過程中的激勵系數(shù)αk，v′，v，即拓?fù)渚W(wǎng)絡(luò)下k跳鄰居設(shè)備之間事件類型v′對事件類型v激勵生成的泊松分布事件序列的參數(shù)。對于無時間誤差因果邊的影響，將αk，v′，v作為泊松分布的系數(shù)生成原因事件的傳播事件；對于存在時間誤差問題的因果邊的影響，按照原因事件記錄生成時間一致的結(jié)果事件記錄。

d）將步驟c）中生成的傳播事件作為原因事件，生成新的傳播事件，重復(fù)步驟c）直至無新的傳播事件產(chǎn)生或在給定的時間范圍內(nèi)無新的傳播事件發(fā)生。

基于上述數(shù)據(jù)生成方法，逐一改變不同參數(shù)的取值生成數(shù)據(jù)，將本文方法與基準(zhǔn)方法應(yīng)用于仿真數(shù)據(jù)中，對比不同算法的實(shí)驗(yàn)效果。默認(rèn)生成參數(shù)為：拓?fù)渚W(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為30，事件類型數(shù)為30，樣本數(shù)為20 000，因果網(wǎng)絡(luò)平均入度為1.2，α取值為［0.03，0.05］，μ取值為［0.000 05，0.000 1］，存在時間誤差的數(shù)據(jù)比例為0.03，以及置信值閾值為0.02。所有默認(rèn)參數(shù)都是基于真實(shí)數(shù)據(jù)的特點(diǎn)選定的。實(shí)驗(yàn)環(huán)境為CPU配置是Intel Xeon E5-2620v4@2.10 GHz，內(nèi)存64 GB的服務(wù)器。

在所有實(shí)驗(yàn)中，本文使用了準(zhǔn)確率（precision）、召回率（recall）和F1值（F1-score）作為算法測量到的因果網(wǎng)絡(luò)結(jié)構(gòu)的評價(jià)指標(biāo)，證明本文算法的正確性和有效性。準(zhǔn)確率是通過算法學(xué)習(xí)到事件的因果關(guān)系網(wǎng)絡(luò)圖中正確的邊數(shù)占學(xué)習(xí)到的因果圖中邊數(shù)的比例；召回率是通過算法學(xué)習(xí)到的事件因果關(guān)系網(wǎng)絡(luò)圖中正確的邊數(shù)占原始的真實(shí)因果網(wǎng)絡(luò)圖中邊數(shù)的比例；F1值是一個綜合準(zhǔn)確率和召回率的衡量指標(biāo)。

F1-score=2×precision×recallprecision+recall（2）

模擬實(shí)驗(yàn)的結(jié)果如圖4、5所示。在圖4中，本文對比了模擬數(shù)據(jù)中不同的時間誤差比例、PTHP中不同的置信值和拓?fù)渚W(wǎng)絡(luò)中不同的設(shè)備數(shù)量下的三個實(shí)驗(yàn)結(jié)果，且PTHP均取得了最好的結(jié)果。隨著數(shù)據(jù)中存在時間誤差的比例上升和拓?fù)涔?jié)點(diǎn)數(shù)的增加，PTHP相比THP等其他方法的結(jié)果更加平穩(wěn)且出色，證明其解決了數(shù)據(jù)中存在時間誤差和數(shù)據(jù)不符合獨(dú)立同分布特征的問題。而在不同置信值閾值下，PTHP實(shí)驗(yàn)結(jié)果的F1值先上升后輕微下降，是因?yàn)殡S著置信值閾值提高，PTHP選擇的因果先驗(yàn)邊數(shù)量增加，準(zhǔn)確率會隨之下降以及召回率會上升，在合適的閾值下達(dá)到整體的最佳水平。

在圖5中，本文對比了不同傳統(tǒng)參數(shù)下的模擬實(shí)驗(yàn)結(jié)果，其中PTHP算法的結(jié)果最優(yōu)，THP排在其次。在所有對比實(shí)驗(yàn)中，MLE-SGL、ADM4、PCMCI效果不佳的原因是它們不適用于非獨(dú)立同分布的數(shù)據(jù)。THP算法則因?yàn)椴荒軐W(xué)到有時間誤差下事件記錄背后的因果機(jī)制，所以效果上相比PTHP稍遜一籌。在算法的魯棒性方面，PTHP的曲線相比THP等其他對比方法更加光滑，證明了PTHP算法的實(shí)用性更好。

3.2 真實(shí)數(shù)據(jù)實(shí)驗(yàn)

3.2.1 數(shù)據(jù)集說明

實(shí)驗(yàn)數(shù)據(jù)集是PCIC 2021華為因果推理挑戰(zhàn)賽中因果發(fā)現(xiàn)賽道公布的一個無線網(wǎng)絡(luò)真實(shí)數(shù)據(jù)集。比賽的目的是征集拓?fù)渚W(wǎng)絡(luò)下告警事件記錄背后因果關(guān)系發(fā)現(xiàn)的算法，使運(yùn)維人員從海量告警事件的人工排查中抽身，達(dá)到快速定位故障記錄的根因、修復(fù)設(shè)備異常的效果。

這個真實(shí)數(shù)據(jù)集是由華為公司對實(shí)際設(shè)備告警數(shù)據(jù)進(jìn)行脫敏，隱去設(shè)備名稱和告警名稱后公開的一個數(shù)據(jù)集。數(shù)據(jù)集包含的告警事件記錄34 839條，其中事件類型18種，拓?fù)渚W(wǎng)絡(luò)的節(jié)點(diǎn)55個設(shè)備，數(shù)據(jù)背后的因果關(guān)系由專家給出。數(shù)據(jù)集的地址為https：//github.com/gcastle-hub/dataset。

3.2.2 實(shí)驗(yàn)結(jié)果分析

實(shí)驗(yàn)結(jié)果如表1所示。從表1可看出，PTHP在三個評價(jià)指標(biāo)上相比基準(zhǔn)方法表現(xiàn)都更好。在圖6中，本文展示了PTHP和基準(zhǔn)方法實(shí)驗(yàn)結(jié)果的局部結(jié)構(gòu)，其中，實(shí)線表示正確發(fā)現(xiàn)的因果邊；帶叉號的實(shí)線表示錯誤發(fā)現(xiàn)的因果邊；虛線表示沒有發(fā)現(xiàn)的因果邊。從實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)，相比THP方法，PTHP方法取得較好效果的原因是第一階段使用基于約束的因果關(guān)系發(fā)現(xiàn)方法學(xué)出了THP不能發(fā)現(xiàn)的因果邊，有效提高了召回率的水平，同時基于先驗(yàn)約束進(jìn)行爬山法搜索，減小了THP算法學(xué)習(xí)過程中因果關(guān)系發(fā)現(xiàn)錯誤的邊對結(jié)果的影響，也緩解了使用爬山法的算法容易陷入局部最優(yōu)結(jié)構(gòu)的問題。而相比ADM4、MLE-SGL和PCMCI方法，PTHP表現(xiàn)更好，這是因?yàn)镻THP在計(jì)算激勵影響時考慮了數(shù)據(jù)背后的拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu)。

通過和專家知識得到的實(shí)際情況下的無線網(wǎng)絡(luò)告警事件的因果關(guān)系圖進(jìn)行對比發(fā)現(xiàn)，PTHP算法得到的大多數(shù)因果關(guān)系和專家知識的結(jié)果是一致的，反映了本文算法發(fā)現(xiàn)拓?fù)渚W(wǎng)絡(luò)下告警事件記錄背后因果關(guān)系的結(jié)果具有一定的準(zhǔn)確性且其結(jié)果有助于指導(dǎo)運(yùn)維人員對故障進(jìn)行定位和修復(fù)。

4 結(jié)束語

本文提出了一種融合先驗(yàn)約束的拓?fù)浠艨诉^程格蘭杰因果關(guān)系發(fā)現(xiàn)框架（PTHP），將基于約束的方法結(jié)合到拓?fù)浠艨怂惯^程中，并在真實(shí)場景下的故障因果關(guān)系發(fā)現(xiàn)中證明了算法的有效性。與現(xiàn)有基于約束的算法相比，本文結(jié)合了拓?fù)浠艨怂惯^程，能夠進(jìn)一步挖掘非獨(dú)立同分布數(shù)據(jù)下的因果關(guān)系，并對因果邊進(jìn)行定向。與拓?fù)浠艨怂惯^程相比，本文結(jié)合了基于約束的方法，能夠更好地發(fā)現(xiàn)有時間誤差情況下的因果關(guān)系；同時，將兩者進(jìn)行結(jié)合可以提高拓?fù)鋾r序點(diǎn)過程下的因果發(fā)現(xiàn)的能力和準(zhǔn)確性。但是，本文考慮基于約束的方法存在不能定向馬爾可夫等價(jià)類的問題，后續(xù)將對此問題展開進(jìn)一步的研究，提出更通用的因果關(guān)系發(fā)現(xiàn)算法。

參考文獻(xiàn)：

［1］Liu Zitong，Sun Jiachen，Shen Feng，et al.Topology sensing of wireless networks based on Hawkes process［J］.Mobile Networks and Applications，2020，25（6）：2459-2470.

［2］Zhu Shixiang，Ding Ruyi，Zhang Minghe，et al.Spatio-temporal point processes with attention for traffic congestion event modeling［J/OL］.IEEE Trans on Intelligent Transportation Systems.（2021-03-30）［2022-01-26］.http：//doi.org/10.1109/TITS.2021.3068139.

［3］Da Fonseca J，Zaatour R.Hawkes process：fast calibration，application to trade clustering，and diffusive limit［J］.Journal of Futures Markets，2014，34（6）：548-579.

［4］Runge J，Nowack P，Kretschmer M，et al.Detecting and quantifying causal associations in large nonlinear time series datasets［J］.Science Advances，2019，5（11）：eaau4996.

［5］Hyvrinen A，Zhang Kun，Shimizu S，et al.Estimation of a structural vector autoregression model using non-Gaussianity［J］.Journal of Machine Learning Research，2010，11（5）：1709-1731.

［6］Peters J，Janzing D，Schlkopf B.Causal inference on time series using restricted structural equation models［C］//Advances in Neural Information Processing Systems.2013：154-162.

［7］陳薇，蔡瑞初，伍運(yùn)金，等.基于多組典型相關(guān)變量的因果關(guān)系發(fā)現(xiàn)算法［J］.計(jì)算機(jī)應(yīng)用研究，2021，38（1）：53-56.（Chen Wei，Cai Ruichu，Wu Yunjin，et al.Causal relationship discovery algorithm based on multiple groups of typical related variables［J］.Application Research of Computers，2021，38（1）：53-56.）

［8］Xu Hongteng，F(xiàn)arajtabar M，Zha Hongyuan.Learning granger causality for Hawkes processes［C］//Proc of the 33rd International Conference on International Conference on Machine Learning.2016：1717-1726.

［9］Cai Ruichu，Wu Siyu，Qiao Jie，et al.THP：topological hawkes processes for learning granger causality on event sequences［EB/OL］.（2021-05-23）.https：//arxiv.org/abs/2105.10884.

［10］張連文，郭海鵬.貝葉斯網(wǎng)引論［M］.北京：科學(xué)出版社，2006.（Zhang Lianwen，Guo Haipeng.Introduction to Bayesian networks［M］.Beijing：Science Press，2006.）

［11］Huang Biwei，Zhang Kun，Lin Yizhu，et al.Generalized score functions for causal discovery［C］//Proc of the 24th ACM SIGKDD International Conference on Knowledge Discovery amp; Data Mining.New York：ACM Press，2018：1551-1560.

［12］蔡瑞初，陳薇，張坤，等.基于非時序觀察數(shù)據(jù)的因果關(guān)系發(fā)現(xiàn)綜述［J］.計(jì)算機(jī)學(xué)報(bào)，2017，40（6）：1470-1490.（Cai Ruichu，Chen Wei，Zhang Kun，et al.Summary of causal relationship discovery based on non-time series observation data［J］.Chinese Journal of Computers，2017，40（6）：1470-1490.）

［13］Gretton A，F(xiàn)ukumizu K，Teo C H，et al.A kernel statistical test of independence［C］//Proc of the 20th International Conference on Neural Information Processing Systems.2007：585-592.

［14］Zhang Kun，Peters J，Janzing D，et al.Kernel-based conditional independence test and application in causal discovery［EB/OL］.（2012-02-14）.https：//arxiv.org/abs/1202.3775.

［15］Frenzel S，Pompe B.Partial mutual information for coupling analysis of multivariate time series［J］.Physical Review Letters，2007，99（20）：204101.

［16］Spirtes P，Glymour C N，Scheines R，et al.Causation，prediction，and search［M］.Cambridge，MA：The MIT Press，2000.

［17］Verma T，Pearl J.Equivalence and synthesis of causal models［C］//Proc of the 6th Annual Conference on Uncertainty in Artificial Intelligence.1990：255-270.

［18］Streit R L.The poisson point process［M］// Poisson Point Processes.Boston，MA：Springer，2010：11-55.

［19］Du Nan，Dai Hanjun，Trivedi R，et al.Recurrent marked temporal point processes：embedding event history to vector［C］//Proc of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM Press，2016：1555-1564.

［20］Zhou Ke，Zha Hongyuan，Song Le.Learning social infectivity in sparse low-rank networks using multi-dimensional Hawkes processes［C］//Proc of the 16th International Conference on Artificial Intelligence and Statistics.2013：641-649.

［21］Lewis P A W，Shedler G S.Simulation of nonhomogeneous Poisson processes with log linear rate function［J］.Biometrika，1976，63（3）：501-505.

［22］Pasupathy R.Generating homogeneous poisson processes［M］// Cochran J J，Cox L A，Keskinocak P，et al.Wiley Encyclopedia of Operations Research and Management Science.[S.l.]：Wiley，2010.