混合局部因果結(jié)構(gòu)學習

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

1.山西大學計算機與信息技術學院，太原 030006

2.山西大學計算智能與中文信息處理教育部重點實驗室，太原 030006

3.安徽大學計算機科學與技術學院，合肥 230601

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

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

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

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

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

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

1 背景知識

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

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

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

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

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

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

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

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

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

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

局部因果結(jié)構(gòu)學習方法通常包括兩個步驟：（1）挖掘目標變量的MB/PC；（2）迭代進行邊的定向，得到目標變量的局部結(jié)構(gòu)。圖1 展示了一個因果網(wǎng)絡結(jié)構(gòu)，假設目標變量為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)絡結(jié)構(gòu)1

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

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

2.1 挖掘目標變量的PC 集

設與變量X依賴的集合為CSet(X)，與變量X獨立的集合為CC(X)，由于變量X的PC 集PC(X)是與X直接相連的節(jié)點集，因此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é)點不是和X直接相連的節(jié)點，因此可以對Y∈CSet(X)與X之間的路徑用d-分離進行測試，得到變量X的最終的PC 集PC(X)。

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

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

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

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

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

算法1SIAPC

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

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

2.2 迭代進行邊的定向

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

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

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

在選取數(shù)據(jù)集方面，本文目的是選取與目標變量最相關的變量集進行打分，若變量集長度太大則采用打分方法的時間效率很低，長度太小則影響打分結(jié)果，因此為了降低時間效率且盡量不損失精度，本文選擇部分數(shù)據(jù)集Z的方式如下：（1）若SPC(T)長度小于一個給定的參數(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）。對于ss和zs的選取問題，本文進行人工選取然后用實驗進行測試，其中ss選用10、20、30、40，得到ss=20 的實驗結(jié)果較好；對于zs，本文選用4、5、6、7，得到zs=5 的實驗結(jié)果較好。

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

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

算法2HLCS

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

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

算法3HLCS_sub

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

輸出：ID相對于T的因果識別。

3 實驗及其結(jié)果

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

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

Table 1 Data information of 10 benchmark networks表1 10 個基準網(wǎng)絡數(shù)據(jù)信息

3.2 評價指標

為了評價算法的性能，針對兩組實驗分別給出了不同的評價指標，具體如下：

（1）PC 發(fā)現(xiàn)算法的評價指標[2]

①Precision：算法輸出正確點的數(shù)量（和基準網(wǎng)絡對比）/算法輸出的點的數(shù)量。

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

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

④Distance：

⑤Time：運行每個點的平均時間，單位為秒（s）。

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

（2）局部因果結(jié)構(gòu)學習算法的評價指標[8]

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

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

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

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

⑤Time：運行每個點的平均時間，單位為秒（s）。

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

3.3 比較算法

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

①MMPC：基于拓撲的經(jīng)典PC 發(fā)現(xiàn)算法。

②HTION_PC：基于拓撲的經(jīng)典PC 發(fā)現(xiàn)算法。

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

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

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

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

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

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

3.4 實驗結(jié)果

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

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

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

（2）局部因果結(jié)構(gòu)學習比較算法的實驗結(jié)果

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

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

由表3 可以看出，算法HLCS 相較于已有算法，在精度方面有較大提升，但是在時間效率方面有相對較大的不足，但是因為本文主要針對的是局部因果結(jié)構(gòu)算法的精度，對時間效率方面的改進將是下一步改進的內(nèi)容。

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

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

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

設定以下兩個指標：

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

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

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

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

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

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

4 結(jié)束語

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