王雲(yún)霞，曹付元+，凌兆龍

1.山西大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院，太原 030006

2.山西大學(xué)計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室，太原 030006

3.安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230601

因果關(guān)系發(fā)現(xiàn)在計(jì)算機(jī)科學(xué)領(lǐng)域發(fā)揮著重要的作用，比如面向多源數(shù)據(jù)的因果關(guān)系發(fā)現(xiàn)[1-3]，選擇與類別屬性有因果關(guān)系的特征來增強(qiáng)機(jī)器學(xué)習(xí)模型的泛化能力與可解釋性[4]，利用因果理論解決復(fù)雜的機(jī)器學(xué)習(xí)問題[5-6]等。因果結(jié)構(gòu)學(xué)習(xí)是識(shí)別變量之間因果關(guān)系的一個(gè)學(xué)習(xí)過程，而挖掘一個(gè)與數(shù)據(jù)擬合程度較好且包含所有變量的全局（或完整）的貝葉斯網(wǎng)絡(luò)可以學(xué)習(xí)變量之間的因果關(guān)系[7-8]。但是大數(shù)據(jù)時(shí)代的到來使得越來越豐富的數(shù)據(jù)為因果結(jié)構(gòu)學(xué)習(xí)帶來更多信息的同時(shí)也帶來了相應(yīng)的挑戰(zhàn)。一方面豐富的數(shù)據(jù)含有更多的信息，為因果結(jié)構(gòu)學(xué)習(xí)提供了更多的數(shù)據(jù)支撐，另一方面數(shù)據(jù)的維度越來越高，其在計(jì)算時(shí)間和空間存儲(chǔ)上消耗較大，全局因果結(jié)構(gòu)學(xué)習(xí)將變得困難甚至在更大型的數(shù)據(jù)集上無法運(yùn)行。此外，如果僅僅對(duì)高維數(shù)據(jù)中某一部分變量之間的因果關(guān)系感興趣時(shí)，構(gòu)建全局網(wǎng)絡(luò)是浪費(fèi)時(shí)間與空間的。因此相對(duì)于全局因果結(jié)構(gòu)學(xué)習(xí)方法，局部因果結(jié)構(gòu)學(xué)習(xí)方法可以在高維數(shù)據(jù)中挖掘任意感興趣變量的局部因果結(jié)構(gòu)，且從計(jì)算資源與存儲(chǔ)資源的角度，局部因果結(jié)構(gòu)挖掘更高效且更具有實(shí)際意義。

Silverstein 等人提出第一個(gè)局部因果結(jié)構(gòu)學(xué)習(xí)算法，即LCD（local causal discovery）算法[9]，該算法利用條件獨(dú)立性學(xué)習(xí)四個(gè)變量之間的因果關(guān)系?；贚CD 算法，Mani 等人提出BLCD（Bayesian local causal discovery）算法[10]，它首先學(xué)習(xí)目標(biāo)變量的馬爾科夫毯（Markov blanket，MB），然后學(xué)習(xí)MB 中的Y 結(jié)構(gòu)來進(jìn)行局部因果結(jié)構(gòu)的學(xué)習(xí)。但是上述的兩個(gè)算法并沒有識(shí)別到目標(biāo)變量的直接原因和直接結(jié)果?；贚CD 算法和BLCD 算法的不足，Yin 等人提出了PCD-by-PCD（parents，children and some descendants）算法[11]，該算法首先利用MMPC（max-min parents and children）算法[12]學(xué)習(xí)目標(biāo)變量的PC 集，然后利用條件獨(dú)立性測試尋找其中的V 結(jié)構(gòu)，遞歸地推出PC集中變量之間的因果關(guān)系。Gao等人提出CMB（causal Markov blanket）算法[13]，其基本思想與PCD-by-PCD算法一致，該算法首先調(diào)用HTION-MB 算法[14]尋找目標(biāo)變量的MB，然后利用條件獨(dú)立性測試和Meek規(guī)則遞歸地推導(dǎo)邊的方向。但是上述兩個(gè)算法的精度相對(duì)不是很高，且有限樣本下其精度更差。其原因是一方面受到PC（parents and children）發(fā)現(xiàn)結(jié)果的影響，另一方面是邊的定向過程中對(duì)V 結(jié)構(gòu)的依賴性也會(huì)使得算法精度不穩(wěn)定。

目前已有的局部因果結(jié)構(gòu)學(xué)習(xí)算法分為兩個(gè)步驟：步驟1 是發(fā)現(xiàn)目標(biāo)變量的MB 或PC，即目標(biāo)變量的局部結(jié)構(gòu)骨架[15-16]；步驟2 是對(duì)PC 集中的變量確定其與目標(biāo)變量之間的因果關(guān)系。兩個(gè)步驟的結(jié)果都對(duì)最終的算法產(chǎn)生一定的影響。

步驟1 中PCD-by-PCD 算法和CMB 算法分別調(diào)用基于限制的因果關(guān)系發(fā)現(xiàn)算法：MMPC 算法和HTION-MB 算法來發(fā)現(xiàn)目標(biāo)變量的局部結(jié)構(gòu)骨架。而這兩個(gè)算法都是直接利用條件獨(dú)立性學(xué)習(xí)MB/PC，其對(duì)數(shù)據(jù)樣本大小有一定的要求，當(dāng)數(shù)據(jù)樣本沒有達(dá)到MB/PC 尺寸的指數(shù)級(jí)數(shù)量時(shí)，算法所用的條件獨(dú)立性測試將有較高的錯(cuò)誤率，進(jìn)而導(dǎo)致這兩個(gè)方法的精度較差。為了解決上述問題，本文在基于限制方法的基礎(chǔ)上結(jié)合打分方法來緩減有限樣本問題，原因是打分方法具有更強(qiáng)的容錯(cuò)性，能夠通過搜索一個(gè)明顯較小的空間收斂到一個(gè)更高質(zhì)量的網(wǎng)絡(luò)，且基于分?jǐn)?shù)的方法在可能的圖結(jié)構(gòu)中有更強(qiáng)的先驗(yàn)性，可以緩減影響算法精度的有限樣本問題。而單純的采用打分的方法如S2TMB（score-based simultaneous Markov blanket）算法[17]，由于其是對(duì)每一個(gè)變量逐一考慮進(jìn)行打分，時(shí)間效率極低。因此本文結(jié)合兩種思想來綜合提高步驟1 性能。

步驟2 中PCD-by-PCD 算法和CMB 算法都是直接利用條件獨(dú)立性測試尋找V 結(jié)構(gòu)，然后利用Meek規(guī)則確定邊的方向來得到目標(biāo)變量的局部結(jié)構(gòu)。一方面因?yàn)閂 結(jié)構(gòu)依賴于基本網(wǎng)絡(luò)結(jié)構(gòu)，而算法結(jié)果又依賴于V 結(jié)構(gòu)的發(fā)現(xiàn)即當(dāng)正確發(fā)現(xiàn)的V 結(jié)構(gòu)很多且與目標(biāo)變量有關(guān)系時(shí)，最終算法的精度相應(yīng)較高，當(dāng)正確發(fā)現(xiàn)的V 結(jié)構(gòu)很少且與目標(biāo)變量沒有關(guān)系時(shí)，那么最終算法的精度將會(huì)大幅度降低。因此這兩個(gè)算法最終得到的結(jié)果精度是要依賴于基本網(wǎng)絡(luò)中V 結(jié)構(gòu)的發(fā)現(xiàn)[18]。另一方面同樣由于有限樣本等影響，條件獨(dú)立性測試將存在一定的錯(cuò)誤性，這也就意味著V結(jié)構(gòu)發(fā)現(xiàn)以及Meek 規(guī)則的使用將存在一定的錯(cuò)誤性，從而導(dǎo)致最終算法精度相對(duì)不高。因此為了降低對(duì)V 結(jié)構(gòu)的依賴性且緩減有限樣本問題，同時(shí)提高相對(duì)于打分方法的時(shí)間效率，本文結(jié)合限制與打分方法對(duì)已有的局部因果結(jié)構(gòu)學(xué)習(xí)算法進(jìn)行改進(jìn)來提高算法的精度。

本文提出一種新的基于打分和限制相結(jié)合的混合局部因果結(jié)構(gòu)學(xué)習(xí)算法（hybrid local causal structure learning，HLCS）。步驟1 對(duì)基于打分的PC 發(fā)現(xiàn)算法進(jìn)行了改進(jìn)，通過加入限制思想降低所測試的節(jié)點(diǎn)數(shù)目，且輸出目標(biāo)變量與其PC 集變量的定向結(jié)果，提出一種基于打分和限制相結(jié)合的PC 發(fā)現(xiàn)算法SIAPC（score-based incremental association parents and children）；步驟2 通過利用SIAPC 算法得到的定向結(jié)果和對(duì)部分?jǐn)?shù)據(jù)集打分得到的定向結(jié)果的交集來確定邊的方向，之后結(jié)合條件獨(dú)立測試來降低對(duì)V 結(jié)構(gòu)的依賴性。實(shí)驗(yàn)結(jié)果驗(yàn)證了本文方法相對(duì)于目前的方法在精度方面有顯著提高，且有效緩減了數(shù)據(jù)效率問題。

1 背景知識(shí)

為方便可讀，本文用V=(X1,X2,…,Xn)表示n個(gè)觀測變量（節(jié)點(diǎn)），P是V上的一個(gè)離散的聯(lián)合概率分布，G代表一個(gè)有向無環(huán)圖DAG 。如果滿足馬爾科夫條件，則稱為一個(gè)貝葉斯網(wǎng)絡(luò)。在一個(gè)貝葉斯網(wǎng)絡(luò)中，Xi⊥Xj和分別表示變量Xi、Xj之間的獨(dú)立性和依賴性，Xi⊥Xj|Z表示在集合Z的條件下，變量Xi條件獨(dú)立于Xj，其中Z?V{Xi,Xj}，同理表示在Z的條件下，變量Xi條件依賴于Xj。下面給出一些相關(guān)的定義。

定義1（馬爾科夫條件）[19]給定一個(gè)有向無環(huán)圖G，馬爾科夫條件在G中成立當(dāng)且僅當(dāng)G中的每一個(gè)節(jié)點(diǎn)都獨(dú)立于它的非后裔節(jié)點(diǎn)的任何子集。

馬爾科夫條件使得貝葉斯網(wǎng)絡(luò)對(duì)一組變量V的聯(lián)合概率實(shí)現(xiàn)分解化，即P(V)可以分解為G中在給定父集條件下變量條件概率分布的乘積，其中PA(T)是G中變量X的父集，則P(V)被表示為：

定義2（條件獨(dú)立性）[19]兩個(gè)不同的變量Xi,Xj∈V被認(rèn)為在給定變量子集Z?V{Xi,Xj}下是條件獨(dú)立的當(dāng)且僅當(dāng)P(Xi,Xj|Z)=P(Xi|Z)P(Xj|Z)成立，否則Xi、Xj被認(rèn)為在變量子集Z下條件依賴。

定義3（d-分離）[20]在一個(gè)有向無環(huán)圖G中，一條路徑π被集合Z?Vd-分離當(dāng)且僅當(dāng)（1）π中包含Xi→Xk→Xj（Xi←Xk←Xj）或Xi←Xk→Xj，其中中間節(jié)點(diǎn)Xk屬于Z即Xk∈Z，或（2）π中包含一個(gè)V 結(jié)構(gòu)Xi→Xk←Xj，此時(shí)中間節(jié)點(diǎn)Xk不屬于Z，且Xk的子孫節(jié)點(diǎn)也不在Z中。集合Z被認(rèn)為d-分離Xi，Xj當(dāng)且僅當(dāng)Z阻隔了從Xi到Xj的每條路徑。

定義4（忠實(shí)性假設(shè)）[21]給定一個(gè)貝葉斯網(wǎng)絡(luò)，G忠實(shí)于P當(dāng)且僅當(dāng)P中的每個(gè)條件獨(dú)立都受G和馬爾科夫條件的影響。P是忠實(shí)的當(dāng)且僅當(dāng)G對(duì)P忠實(shí)。

定義5（馬爾科夫毯）[21]忠實(shí)性假設(shè)下，在一個(gè)貝葉斯網(wǎng)絡(luò)中，一個(gè)變量T的馬爾科夫毯MB(T)是唯一的且包含其父母PA(T)、孩子CH(T)和配偶SP(T)（變量的孩子的其他父母），即MB(T)=PA(T)?CH(T)?SP(T)。

定義6（近似PC 集）在一個(gè)貝葉斯網(wǎng)絡(luò)中，設(shè)CSet(T)為與變量T相關(guān)的節(jié)點(diǎn)集且Xi,T∈V），若T⊥Xi|Xk且Xi∈CSet(T),Xk∈CSet(T){T,Xi}，則從CSet(T)中去掉Xi，最終剩下的節(jié)點(diǎn)集定義為目標(biāo)變量T的近似PC 集，記作SPC(T)。

定義7（環(huán)繞結(jié)構(gòu)）給定一個(gè)貝葉斯網(wǎng)絡(luò)，忠實(shí)性假設(shè)下，若存在三個(gè)以上的節(jié)點(diǎn)構(gòu)成的結(jié)構(gòu)滿足以下條件：（1）節(jié)點(diǎn)數(shù)目等于邊的數(shù)目；（2）該結(jié)構(gòu)的每一節(jié)點(diǎn)都有兩條邊相連；（3）Xi⊥Xj|Z且，Z?V{Xi,Xj}，則稱該結(jié)構(gòu)為環(huán)繞結(jié)構(gòu)。

2 基于打分和限制相結(jié)合的混合局部因果結(jié)構(gòu)學(xué)習(xí)算法

局部因果結(jié)構(gòu)學(xué)習(xí)方法通常包括兩個(gè)步驟：（1）挖掘目標(biāo)變量的MB/PC；（2）迭代進(jìn)行邊的定向，得到目標(biāo)變量的局部結(jié)構(gòu)。圖1 展示了一個(gè)因果網(wǎng)絡(luò)結(jié)構(gòu)，假設(shè)目標(biāo)變量為T，則由圖1 可知T的PC 集為PC(T)={N,A,L,J,B,C}，而{T,A,D,L}和{T,B,F,M,C}構(gòu)成的結(jié)構(gòu)是定義7 的環(huán)繞結(jié)構(gòu)。

Fig.1 Causal network structure 1圖1 因果網(wǎng)絡(luò)結(jié)構(gòu)1

理論上基于限制的方法可以得到正確的PC/MB，但是有限樣本問題導(dǎo)致的條件獨(dú)立性測試存在一定的錯(cuò)誤性，因此最終得到的目標(biāo)變量的PC/MB 可能不是完全正確的。而基于打分的學(xué)習(xí)方法使用帶分?jǐn)?shù)標(biāo)準(zhǔn)的BN（Bayesian network）結(jié)構(gòu)學(xué)習(xí)算法來查找局部結(jié)構(gòu)，其在可能的圖形結(jié)構(gòu)上具有更強(qiáng)的先驗(yàn)性，且打分方法MMHC（max-min hill-climbing）在有限樣本中可以收斂到一個(gè)更高質(zhì)量的網(wǎng)絡(luò)。因此為了解決由有限樣本產(chǎn)生的條件獨(dú)立性導(dǎo)致的錯(cuò)誤以及由打分方法本身產(chǎn)生的時(shí)間效率問題，本文結(jié)合基于限制和基于打分-搜索的方法，綜合考慮PC/MB 發(fā)現(xiàn)，提出SIAPC 算法。

以圖1 為例，由于馬爾科夫等價(jià)類的存在，已有的局部因果結(jié)構(gòu)學(xué)習(xí)算法在結(jié)構(gòu){T,C,F,M,B}中，無法確定T和{B,F,M}之間的關(guān)系；同理在結(jié)構(gòu){T,A,D,L}中，也無法確定T和{A,L}之間的關(guān)系。因此已有的局部因果結(jié)構(gòu)學(xué)習(xí)算法在面對(duì)上述結(jié)構(gòu)中，需要尋找更多的V 結(jié)構(gòu)來判斷邊的方向，但是V 結(jié)構(gòu)依賴于基本網(wǎng)絡(luò)結(jié)構(gòu)，因此算法最終得到的結(jié)果精度要取決于V 結(jié)構(gòu)的發(fā)現(xiàn)。而打分方法因?yàn)樵诳赡艿膱D形結(jié)構(gòu)上具有更強(qiáng)的先驗(yàn)性，其可以降低算法對(duì)V結(jié)構(gòu)的依賴性，所以為了解決已有算法對(duì)V 結(jié)構(gòu)依賴問題，緩減數(shù)據(jù)效率問題，本文結(jié)合打分方法對(duì)基于限制的局部因果結(jié)構(gòu)學(xué)習(xí)算法進(jìn)行改進(jìn)，提出混合的局部因果結(jié)構(gòu)學(xué)習(xí)算法HLCS。

2.1 挖掘目標(biāo)變量的PC 集

設(shè)與變量X依賴的集合為CSet(X)，與變量X獨(dú)立的集合為CC(X)，由于變量X的PC 集PC(X)是與X直接相連的節(jié)點(diǎn)集，因此PC(X)是CSet(X)的子集，即PC(X)?CSet(X)。由定義3，在CSet(X)中發(fā)現(xiàn)存在集合S可以阻斷X和Y（Y∈CSet(X){S,X}）之間的路徑，則Y一定不屬于PC(X)，也就是可以被阻斷的節(jié)點(diǎn)不是和X直接相連的節(jié)點(diǎn)，因此可以對(duì)Y∈CSet(X)與X之間的路徑用d-分離進(jìn)行測試，得到變量X的最終的PC 集PC(X)。

在圖2 中，設(shè)藍(lán)色節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)T，綠色節(jié)點(diǎn)表示PC(T)={A,B,C,L}，經(jīng)分析綠色節(jié)點(diǎn)和黃色節(jié)點(diǎn)構(gòu)成CSet(T)={A,B,C,L,D,E,F,H}，此時(shí)對(duì)于目標(biāo)節(jié)點(diǎn)T來說，D被{A,L}阻斷，E被B阻斷，H被F阻斷，F(xiàn)被B阻斷，因此CSet(T)中剩下的節(jié)點(diǎn)為{A,B,C,L}，即最終變量T的PC 集為PC(T)={A,B,C,L}。

Fig.2 Causal network structure 2圖2 因果網(wǎng)絡(luò)結(jié)構(gòu)2

但是上述思想存在以下問題：（1）非常依賴條件獨(dú)立測試的正確性且僅僅關(guān)注CSet中的變量的情況；（2）當(dāng)近似PC 集的長度很大時(shí)，所需要的條件獨(dú)立測試次數(shù)將呈指數(shù)級(jí)增長，即設(shè)ns=|SPC|。由于條件集長度為1 時(shí)CSet可以去掉大部分在其中的節(jié)點(diǎn)，之后對(duì)剩下的節(jié)點(diǎn)集也就是近似PC 集考慮條件集長度為i=2,3,…,ns，此時(shí)相對(duì)于CSet的長度僅僅去掉少部分節(jié)點(diǎn)，因此本文計(jì)算條件獨(dú)立測試的次數(shù)，直接使用ns作為近似測試次數(shù)，即近似結(jié)果為：

經(jīng)分析，上述思想總的獨(dú)立性測試次數(shù)為Total=|V|+|CSet|2+Total0，但是這種方法的條件獨(dú)立性測試次數(shù)相對(duì)較多，最終的結(jié)果精度不是很高。為了進(jìn)一步減少條件獨(dú)立測試次數(shù)，本文直接將Xi∈CSet(T)作為條件集測試Xj∈CSet(T)和T之間的獨(dú)立性，進(jìn)而得到T的近似PC 集SPC(T)。此方式可以使條件獨(dú)立測試次數(shù)減少到Total=|V|+|CSet|2，且最終保留較少節(jié)點(diǎn)在SPC(T)中（PC(T)?SPC(T)）。同時(shí)為了緩減對(duì)條件獨(dú)立測試正確性的依賴，本文采用已有基于打分-搜索的方法對(duì)CC(T)與SPC(T)中的變量共同考慮，來尋找最終的PC(T)。對(duì){CC(T),SPC(T)}共同考慮的原因是：（1）目標(biāo)節(jié)點(diǎn)T與X∈SPC(T) 和Y∈CC(T)可能會(huì)構(gòu)成V 結(jié)構(gòu)。如圖2 所示，C是T的PC 節(jié)點(diǎn)，且＜T,C,M＞構(gòu)成V 結(jié)構(gòu)，可以進(jìn)一步確定C是T的PC 節(jié)點(diǎn)。（2）由于SPC(T)是對(duì)CSet(T)的精簡，每次對(duì)數(shù)據(jù)集DATA{T,X,PC(T)},X∈{SPC(T),CC(T)}進(jìn)行打分，得到的PC(T)的長度都較小，這使得算法效率更高。本文采用基于打分-搜索的全局因果結(jié)構(gòu)學(xué)習(xí)算法MMHC 進(jìn)行打分判定，且其使用的分?jǐn)?shù)準(zhǔn)則為BDeu。

基于上述分析，本文提出以下改進(jìn)的PC 發(fā)現(xiàn)算法SIAPC，如算法1。

算法1SIAPC

輸入：數(shù)據(jù)集DATA，目標(biāo)變量T，獨(dú)立性指標(biāo)w0。

輸出：PC為T的PC集，CSet為與T依賴的集合，SPC為T的近似PC 集，PA為T的父集，CH為T的子集。

2.2 迭代進(jìn)行邊的定向

由于上述的PC 發(fā)現(xiàn)算法用打分方法只能確定和目標(biāo)變量T相連的一部分邊的方向，且由于是對(duì)一部分?jǐn)?shù)據(jù)集進(jìn)行打分，最終得到錯(cuò)誤的邊定向結(jié)果是相對(duì)較多的，由此在邊的迭代定向過程中要進(jìn)行邊方向的進(jìn)一步確定與修正；在迭代邊定向過程中用到的原則就是尋找V 結(jié)構(gòu)，如圖3 中的＜A1,T1,B1 ＞，＜A2,T2,B2 ＞構(gòu)成V 結(jié)構(gòu)，但A1、B1 存在依賴關(guān)系，A2、B2 存在依賴關(guān)系，即＜Ai,Ti,Bi＞構(gòu)成V結(jié)構(gòu)，Ai、Bi之間存在依賴關(guān)系（i=1,2,…,n）。此時(shí)可以檢測＜Ai,Ti,Bi＞為V 結(jié)構(gòu)，但是對(duì)于V 結(jié)構(gòu)之外的路徑判斷不了邊的方向。面對(duì)上述結(jié)構(gòu)，已有的基于限制的方法會(huì)進(jìn)一步尋找更多的MB 或PC集去確定更多的V 結(jié)構(gòu)，算法結(jié)果依賴于發(fā)現(xiàn)的V 結(jié)構(gòu)且在大部分網(wǎng)絡(luò)中性能較低。

Fig.3 Two examples of surround structure圖3 環(huán)繞結(jié)構(gòu)的兩種示例

基于上述問題本文結(jié)合打分方法進(jìn)行改進(jìn)。由于基于打分-搜索的方法在可能的圖形結(jié)構(gòu)上具有更強(qiáng)的先驗(yàn)性，其在實(shí)踐中表現(xiàn)相對(duì)比較穩(wěn)定，尤其是在樣本量較小的情況下，基于打分-搜索的方法MMHC 算法將會(huì)收斂到一個(gè)更高質(zhì)量的網(wǎng)絡(luò)，且與基于約束的方法相比，基于打分-搜索的因果結(jié)構(gòu)發(fā)現(xiàn)方法的探索相對(duì)較少，因此其能更好地處理對(duì)V 結(jié)構(gòu)的依賴問題。由此算法總體思想是：首先通過SIAPC 算法得到目標(biāo)節(jié)點(diǎn)T的部分父集和子集；然后確定相關(guān)的數(shù)據(jù)集Z進(jìn)行打分，得到目標(biāo)節(jié)點(diǎn)T的部分父集和子集；之后取二者的交集作為確定的T的父集和子集；最后利用已有的基于限制的方法通過尋找V 結(jié)構(gòu)以及利用Meek 規(guī)則來進(jìn)行修正。

在選取數(shù)據(jù)集方面，本文目的是選取與目標(biāo)變量最相關(guān)的變量集進(jìn)行打分，若變量集長度太大則采用打分方法的時(shí)間效率很低，長度太小則影響打分結(jié)果，因此為了降低時(shí)間效率且盡量不損失精度，本文選擇部分?jǐn)?shù)據(jù)集Z的方式如下：（1）若SPC(T)長度小于一個(gè)給定的參數(shù)ss，如果其不為空則選取{SPC(T),T}作為新的數(shù)據(jù)集Z，否則選取{CSet(T),T}作為新的數(shù)據(jù)集Z；（2）若SPC(T)長度大于ss，則選取PC(X)（X∈PC(T)）的并集作為新的數(shù)據(jù)集Z；（3）最后得到的新的數(shù)據(jù)集Z需要滿足|Z|＞zs，若不滿足，則加入PC(X)到新的數(shù)據(jù)集中（X∈Z）。對(duì)于ss和zs的選取問題，本文進(jìn)行人工選取然后用實(shí)驗(yàn)進(jìn)行測試，其中ss選用10、20、30、40，得到ss=20 的實(shí)驗(yàn)結(jié)果較好；對(duì)于zs，本文選用4、5、6、7，得到zs=5 的實(shí)驗(yàn)結(jié)果較好。

2.3 基于打分和限制相結(jié)合的混合局部因果結(jié)構(gòu)學(xué)習(xí)算法

本文規(guī)定ID表示其他變量相對(duì)于目標(biāo)變量的因果識(shí)別[12]，若T是目標(biāo)變量，X是其他變量且X∈PC(T)，則ID(X)=1 說明X相對(duì)于T來說，X是T的直接原因，ID(X)=2 說明X是T的直接結(jié)果，ID(X)=3 說明X與T直接相連，但是方向不確定。本文提出基于打分-搜索方法和基于限制方法結(jié)合的混合局部因果結(jié)構(gòu)學(xué)習(xí)算法HLCS，如算法2。

算法2HLCS

輸入：數(shù)據(jù)集DATA，目標(biāo)變量T，獨(dú)立性指標(biāo)w0，數(shù)據(jù)集選取參數(shù)ss和zs。

輸出：PA為T的父節(jié)點(diǎn)集，CH為T的子節(jié)點(diǎn)集，UN為T的未定向節(jié)點(diǎn)集，PC為T的PC 集。

算法3HLCS_sub

輸入：數(shù)據(jù)集DATA，目標(biāo)變量T，當(dāng)前ID，獨(dú)立性指標(biāo)w0，數(shù)據(jù)集選取參數(shù)ss和zs。

輸出：ID相對(duì)于T的因果識(shí)別。

3 實(shí)驗(yàn)及其結(jié)果

3.1 數(shù)據(jù)集

為了驗(yàn)證算法的有效性，本文選取https://pages.mtu.edu/～lebrown/supplements/mmhc_paper/mmhc_index.html 上的10 個(gè)基準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)集作為測試數(shù)據(jù)，具體信息如表1。

Table 1 Data information of 10 benchmark networks表1 10 個(gè)基準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)信息

3.2 評(píng)價(jià)指標(biāo)

為了評(píng)價(jià)算法的性能，針對(duì)兩組實(shí)驗(yàn)分別給出了不同的評(píng)價(jià)指標(biāo)，具體如下：

（1）PC 發(fā)現(xiàn)算法的評(píng)價(jià)指標(biāo)[2]

①Precision：算法輸出正確點(diǎn)的數(shù)量（和基準(zhǔn)網(wǎng)絡(luò)對(duì)比）/算法輸出的點(diǎn)的數(shù)量。

②Recall：算法輸出正確點(diǎn)的數(shù)量（和基準(zhǔn)網(wǎng)絡(luò)對(duì)比）/基準(zhǔn)網(wǎng)絡(luò)中真正的點(diǎn)的數(shù)量。

③F1：(2×Precision×Recall)/(Precision+Recall)。

④Distance：

⑤Time：運(yùn)行每個(gè)點(diǎn)的平均時(shí)間，單位為秒（s）。

其中③和④表示的是算法的精度，⑤表示算法的時(shí)間效率。

（2）局部因果結(jié)構(gòu)學(xué)習(xí)算法的評(píng)價(jià)指標(biāo)[8]

①ArrPrecision：算法輸出中定向正確的邊的數(shù)量（和基準(zhǔn)網(wǎng)絡(luò)對(duì)比）/算法輸出的邊的數(shù)量。

②ArrRecall：算法輸出中定向正確的邊的數(shù)量（和基準(zhǔn)網(wǎng)絡(luò)對(duì)比）/基準(zhǔn)網(wǎng)絡(luò)中邊的數(shù)。

③SHD：算法輸出中定向錯(cuò)誤的邊的數(shù)量（和基準(zhǔn)網(wǎng)絡(luò)對(duì)比）。

④FDR：算法輸出中定向錯(cuò)誤的邊的數(shù)量（和基準(zhǔn)網(wǎng)絡(luò)對(duì)比）/基準(zhǔn)網(wǎng)絡(luò)中邊的數(shù)量。

⑤Time：運(yùn)行每個(gè)點(diǎn)的平均時(shí)間，單位為秒（s）。

其中①、②、③、④表示算法的精度，⑤表示算法的時(shí)間效率。

3.3 比較算法

（1）PC 發(fā)現(xiàn)比較算法

①M(fèi)MPC：基于拓?fù)涞慕?jīng)典PC 發(fā)現(xiàn)算法。

②HTION_PC：基于拓?fù)涞慕?jīng)典PC 發(fā)現(xiàn)算法。

③S2TMB_PC：本文提取了基于打分的馬爾科夫毯S2TMB 算法中發(fā)現(xiàn)PC 集的過程，命名為S2TMBPC 算法。

（2）局部因果結(jié)構(gòu)學(xué)習(xí)比較算法

①P_C：一種基于限制的代表性全局因果結(jié)構(gòu)學(xué)習(xí)算法。

②MMHC：一種基于打分的代表性全局因果結(jié)構(gòu)學(xué)習(xí)算法。

③PCD-by-PCD：已有的局部因果結(jié)構(gòu)學(xué)習(xí)算法。

④CMB：已有的局部因果結(jié)構(gòu)學(xué)習(xí)算法。

3.4 實(shí)驗(yàn)結(jié)果

（1）PC 發(fā)現(xiàn)比較算法實(shí)驗(yàn)結(jié)果

比較算法在樣本數(shù)量為5 000 的每個(gè)數(shù)據(jù)集上運(yùn)行10 次，然后取平均值，實(shí)驗(yàn)結(jié)果如表2 所示。

由表2 可以看出，SIAPC 算法與基于限制的方法（MMPC 算法和HTION_PC 算法）相比較，其時(shí)間效率很低，但是在精度方面有了很大的改進(jìn)。與基于打分的方法（S2TMB_PC 算法）比較，在時(shí)間效率和精度方面，SIAPC 算法都取得了較好的效果。

（2）局部因果結(jié)構(gòu)學(xué)習(xí)比較算法的實(shí)驗(yàn)結(jié)果

比較算法在樣本數(shù)量為5 000 的每個(gè)數(shù)據(jù)集上運(yùn)行10 次，然后取平均值，實(shí)驗(yàn)結(jié)果如表3 所示。

Table 2 Performance comparison of 4 PC discovery algorithms(size=5000）表2 4 種PC 發(fā)現(xiàn)算法的性能比較（size=5 000）

由表3 可以看出，算法HLCS 相較于已有算法，在精度方面有較大提升，但是在時(shí)間效率方面有相對(duì)較大的不足，但是因?yàn)楸疚闹饕槍?duì)的是局部因果結(jié)構(gòu)算法的精度，對(duì)時(shí)間效率方面的改進(jìn)將是下一步改進(jìn)的內(nèi)容。

HLCS 算法與全局因果結(jié)構(gòu)學(xué)習(xí)算法（P_C 算法、MMHC 算法）相比較，在精度方面明顯優(yōu)于P_C算法和MMHC 算法很多，在時(shí)間方面也優(yōu)于這兩種算法。HLCS 算法與局部因果結(jié)構(gòu)學(xué)習(xí)算法（PCDby-PCD 算法、CMB 算法）進(jìn)行比較，在精度方面優(yōu)于PCD-by-PCD 算法和CMB 算法，但是在時(shí)間效率方面有相對(duì)較大的不足。

3.5 數(shù)據(jù)量對(duì)局部因果結(jié)構(gòu)學(xué)習(xí)算法的影響

本節(jié)說明當(dāng)樣本數(shù)據(jù)量不充分時(shí)，本文算法相對(duì)于已有的局部因果結(jié)構(gòu)學(xué)習(xí)算法的比較情況。表4為在樣本數(shù)量為500 時(shí)，算法的實(shí)驗(yàn)結(jié)果。而在表5中，將分析局部因果結(jié)構(gòu)學(xué)習(xí)算法在數(shù)據(jù)量為5 000時(shí)的精度相較于數(shù)據(jù)量為500 時(shí)的精度的增長率，從而說明樣本數(shù)據(jù)量的大小對(duì)算法的影響。

設(shè)定以下兩個(gè)指標(biāo)：

其中，RP表示算法在size=5 000 的數(shù)據(jù)量下ArrPrecision精度相對(duì)于在size=500 數(shù)據(jù)量下ArrPrecision精度的增長率；RC表示算法在size=5 000 的數(shù)據(jù)量下ArrRecall精度相對(duì)于在size=500 數(shù)據(jù)量下ArrRecall精度的增長率。表5 中的數(shù)據(jù)值越大，說明算法受數(shù)據(jù)量的影響越大。

從表4 可以看出，在數(shù)據(jù)相對(duì)不充分的條件下，HLCS 算法的精度相較于其他兩個(gè)局部因果結(jié)構(gòu)學(xué)習(xí)算法較好，但是時(shí)間效率相對(duì)不足。從表5 和圖4中可以看出，隨著數(shù)據(jù)集的增加，HLCS 算法的增長率最低，說明該算法可以有效緩減數(shù)據(jù)充分性。

Table 3 Performance comparison of 5 local structure learning algorithms(size=5000)表3 5 種局部結(jié)構(gòu)學(xué)習(xí)算法的性能比較（size=5 000）

Table 4 Performance comparison of 3 local structure learning algorithms(size=500)表4 3 種局部結(jié)構(gòu)學(xué)習(xí)算法的性能比較（size=500)

Table 5 Growth rate of accuracy of algorithms at size=5000 compared with size=500表5 算法在size=5 000 時(shí)對(duì)size=500 時(shí)精度的增長率 %

Fig.4 Growth rate of RP and RC of algorithm at size=5000 compared with size=500圖4 算法在size=5 000 時(shí)對(duì)size=500 時(shí)RP和RC的增長率

4 結(jié)束語

本文針對(duì)已有算法的定向結(jié)果依賴目標(biāo)變量的MB/PC，以及其結(jié)果取決于V 結(jié)構(gòu)的發(fā)現(xiàn)的問題，提出一個(gè)基于打分和限制相結(jié)合的混合局部因果結(jié)構(gòu)學(xué)習(xí)算法——HLCS 算法。該算法在步驟1 提出了基于打分和限制相結(jié)合的PC 發(fā)現(xiàn)算法，有效地提高算法精度；在步驟2 利用PC 發(fā)現(xiàn)算法得到的定向結(jié)果和對(duì)部分?jǐn)?shù)據(jù)集打分得到的定向結(jié)果的交集來確定邊的方向，然后使用條件獨(dú)立測試進(jìn)一步修正邊的定向結(jié)果，該方法可有效降低對(duì)V 結(jié)構(gòu)的依賴性。同時(shí)因?yàn)椴襟E1 和步驟2 都是結(jié)合基于打分的方法進(jìn)行的，所以HLCS 算法可以有效緩減數(shù)據(jù)效率問題。實(shí)驗(yàn)驗(yàn)證，在標(biāo)準(zhǔn)假設(shè)下，本文算法相較于已有的算法在精度方面有較大的提高，但是由于打分方法的低效性，提高時(shí)間性能是下一步的研究工作。