一種可度量的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)方法

綦小龍 高 陽 王 皓 宋 蓓 周春蕾 張友衛(wèi)

1(南京大學(xué)計算機(jī)科學(xué)與技術(shù)系 南京 210046)2(伊犁師范學(xué)院電子與信息工程學(xué)院 新疆伊寧 835000)3 (江蘇方天電力技術(shù)有限公司 南京 211102) (qxl_0712@sina.com)

貝葉斯網(wǎng)絡(luò)是個有向無圈圖，圖中節(jié)點表示隨機(jī)變量，節(jié)點間的弧表示變量之間的直接依賴關(guān)系.每個節(jié)點都擁有一個概率分布，根節(jié)點所附的是它的邊緣分布，而非根節(jié)點所附的是條件概率分布[1].

近幾十年來，從數(shù)據(jù)中自動學(xué)習(xí)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)受到研究者的普遍關(guān)注[2-7].一般來說，目前有2類結(jié)構(gòu)學(xué)習(xí)方式[2,8]:1)基于約束的結(jié)構(gòu)學(xué)習(xí).該方法根據(jù)整體Markov性，使用統(tǒng)計假設(shè)檢驗對數(shù)據(jù)中的條件依賴和條件獨立性關(guān)系進(jìn)行檢驗，找到對依賴和獨立關(guān)系最好解釋的某個結(jié)構(gòu)[9-10].2)基于優(yōu)化的結(jié)構(gòu)學(xué)習(xí).該方式定義了測量模型對觀測數(shù)據(jù)擬合程度的評分函數(shù)，如貝葉斯評分和最小描述長度(minimum description length, MDL)評分[2].結(jié)構(gòu)學(xué)習(xí)的任務(wù)是找到一個最大化該評分函數(shù)的結(jié)構(gòu).這2種方法有各自的優(yōu)缺點：基于約束的方式是有效的，但是它對個體獨立性檢驗中的失敗敏感[8-9]；基于優(yōu)化的方法每次都考慮整個網(wǎng)絡(luò)，因此對于個體錯誤并不敏感，但是搜索的結(jié)構(gòu)空間包含超指數(shù)個結(jié)構(gòu).一般來說，該問題是NP-hard問題[8,11].

針對上述2種方法的主要挑戰(zhàn)，學(xué)者們做了大量的研究.對于基于搜索-評分的學(xué)習(xí)方法，根據(jù)尋找到的解是全局最優(yōu)還是局部最優(yōu)提出了精確學(xué)習(xí)方式和近似學(xué)習(xí)方式：精確方式[3,6,12-13]的解是全局最優(yōu)，但是由于其指數(shù)級的時空復(fù)雜性，這些方法只適合于數(shù)據(jù)集規(guī)模小的領(lǐng)域；而近似方式[14-19]的解雖是局部最優(yōu)，但是易于擴(kuò)展到大規(guī)模數(shù)據(jù)上.

基于約束的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)一直以來不論是方法的研究[5,20-24]還是應(yīng)用[25-28]都受到了學(xué)者們的廣泛關(guān)注.然而，高階獨立性檢驗、指數(shù)級的檢驗次數(shù)、變量序的影響依然制約著現(xiàn)有算法的性能.為此，本文針對基于約束算法存在的部分問題，提出了一種基于度量信息矩陣的“偷懶”啟發(fā)式策略方法.新方法不僅與現(xiàn)有算法在時間和精度性能上是可比的，而且易于處理大規(guī)模的稀疏網(wǎng)絡(luò).

1 相關(guān)工作

經(jīng)典的基于約束的方法通常包含2個步驟：1)結(jié)構(gòu)的骨骼識別;2)邊定向.其中對于邊定向一般有2類策略:一類是評分-搜索策略[22]，這種策略也被稱之為混合策略;另一類是識別DAG的Markov等價類策略[5,20-24]，這類策略首先定向υ-結(jié)構(gòu)，再進(jìn)一步對其他邊定向.

在這里，我們關(guān)注結(jié)構(gòu)骨骼的識別，即通過一系列條件獨立性檢驗確定潛在DAG結(jié)構(gòu)是否存在邊.常用的條件獨立性檢驗方法有統(tǒng)計假設(shè)檢驗或互信息、條件互信息等[10].

根據(jù)采用的不同條件獨立性檢驗策略，我們將基于約束的學(xué)習(xí)方式大致分為基于啟發(fā)式策略學(xué)習(xí)[21-22]和基于PC(Peter-Clark)算法策略學(xué)習(xí)[5,20-24]兩類.下面，我們分別對這2類方法中具有代表性的方法進(jìn)行概述.

基于啟發(fā)式的策略通過設(shè)置某種啟發(fā)式函數(shù)來實現(xiàn)減少檢驗次數(shù)的目的或減少假陰性節(jié)點的目的，主要包括以下2種.

1) 文獻(xiàn)[21]給出了一種三階段依賴分析算法TPDA.該算法在Monotone DAG-faithful假定下，通過逐漸縮小條件集規(guī)模的啟發(fā)式策略來減少獨立性檢驗次數(shù).雖然該算法的條件獨立性測試次數(shù)是O(n4)，但是Monotone DAG-faithful假定和DAG-faithful假定是不相容的[2].

2) 文獻(xiàn)[22]中的MMHC(max-min hill-climbing)雖然采用了一種可納的啟發(fā)式策略，但是也產(chǎn)生了大量的假陽性節(jié)點.為了減少假陽性節(jié)點，該方法對目標(biāo)變量的CPC(candidate parents and children)中所有元素執(zhí)行條件獨立性檢驗，該檢驗次數(shù)是CPC規(guī)模的指數(shù)級.

除了基于啟發(fā)式策略的學(xué)習(xí)方法外，也有很多學(xué)者通過改進(jìn)經(jīng)典的PC算法來進(jìn)行結(jié)構(gòu)學(xué)習(xí).他們設(shè)計邊排序方法[23]或序獨立方法[24]來解決PC算法中變量序?qū)撛诮Y(jié)構(gòu)的影響.然而，這類方法雖然在一定程度上緩解了假陰節(jié)點問題，卻無法很好地解決假陽性節(jié)點問題或檢驗次數(shù)指數(shù)級問題.

首先，介紹眾所周知的PC算法[20].該算法也被廣泛應(yīng)用于解決實際問題，尤其在生物信息學(xué)[25-27]、關(guān)系型數(shù)據(jù)的因果模型挖掘[28]等領(lǐng)域.PC算法從一個由節(jié)點構(gòu)成的完全無向圖開始，隨著條件集規(guī)模的增長，檢驗每一個變量對.主要特點是條件集隨著完全無向圖呈動態(tài)變化，這樣避免了高階獨立性檢測.但是為了防止假陽性節(jié)點的產(chǎn)生，在相同條件集規(guī)模下，除非變量的鄰居集合的某個子集使得變量對獨立，否則，還要考慮另一變量的鄰居集合的子集情況.這樣一來，條件獨立性檢驗次數(shù)顯著增加.另外，檢驗過程對變量順序非常敏感，嚴(yán)重影響了PC算法的性能[25].

文獻(xiàn)[23]提出了使用BDe(Bayesian Dirichlet extension)評分函數(shù)測量每條邊的強(qiáng)度并根據(jù)強(qiáng)度執(zhí)行條件獨立性檢驗的方法.因為存在沒有進(jìn)行獨立性檢測變量對(邊)，算法不能保證添加到最終圖的變量對就是正確的決策.

文獻(xiàn)[24]設(shè)計了一種序獨立的PC-Stable算法，即條件獨立性檢驗不會受到變量序的影響.該算法和PC算法的本質(zhì)區(qū)別在于對相同條件集規(guī)模下的變量對執(zhí)行條件獨立性檢驗后，暫不更新無向圖；而是當(dāng)條件集規(guī)模增加后，再相應(yīng)地更新無向圖.相比之下，雖然減少了假陽性節(jié)點，卻需要執(zhí)行更多的條件獨立性測試而且易于遭遇高階獨立性檢驗，效率比PC算法低.

為了提高其執(zhí)行效率，文獻(xiàn)[5]基于PC-Stable算法提出了一種多核并行化的處理方式.根據(jù)無向圖的變化規(guī)律，將變量的鄰接邊分配到不同的處理器上，由于遵循了PC-Stable算法更新無向圖的策略，所以在并行化計算條件獨立性時，沒有額外的通信開銷.雖然極大地提升了PC-Stable算法效率，但是假陰性點依然沒有得到好的解決.

上述方法的共同點是盲目地對到來的變量對立刻執(zhí)行條件獨立性檢測，并沒有考慮合適的時機(jī)；此外，由于條件集的選擇也是盲目的，只要是變量鄰居就有可能成為條件集元素，也會導(dǎo)致學(xué)習(xí)錯誤.

因此，本文提出了可度量的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)方法，創(chuàng)新點如下：1)提出了一種無需任何先驗知識僅從樣本中為每個變量自動地學(xué)習(xí)相應(yīng)的變量序的方法，該方法稱之為度量信息矩陣學(xué)習(xí)；2)根據(jù)度量信息矩陣提出了一種用于條件獨立性檢驗的可靠啟發(fā)式策略.該策略在度量信息矩陣的指導(dǎo)下，不僅能夠合理地選擇執(zhí)行條件獨立性檢驗的變量對，而且能合理地為其選擇條件集.

2 BNSvo-learning算法

2.1 算法描述

數(shù)據(jù)中表現(xiàn)出來的變量間的依賴性包括直接依賴和間接依賴，我們期望在貝葉斯網(wǎng)絡(luò)中評分最高的變量對就是直接依賴的變量對.測量變量對依賴強(qiáng)度的方法有互信息、偏相關(guān)性[29].

雖然全局最佳網(wǎng)絡(luò)的學(xué)習(xí)是NP-hard問題，但是我們可以尋找一個近似最佳的網(wǎng)絡(luò).為此，選擇高依賴關(guān)系的變量對(X,Y)并用這些邊作為創(chuàng)建網(wǎng)絡(luò)的啟發(fā)式是合理的.因此，我們提出了一種可度量的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)方法，簡稱為BNSvo-learning.該方法與以往方法的本質(zhì)區(qū)別在于不是盲目地執(zhí)行條件獨立性檢測，而是根據(jù)度量信息利用“偷懶”啟發(fā)式策略有序進(jìn)行.該方法主要包含度量信息矩陣學(xué)習(xí)和“偷懶”啟發(fā)式策略2部分.

度量信息矩陣學(xué)習(xí)過程從給定的數(shù)據(jù)中使用互信息度量了所有變量之間依賴程度.根據(jù)該依賴程度，它為每個變量分配了一個變量序.我們把這些變量序組成的矩陣稱之為度量信息矩陣mn×n.

度量信息矩陣刻畫了變量間依賴程度的強(qiáng)弱，我們認(rèn)為這是一種粗粒度上的刻畫.原因是它并沒有進(jìn)一步刻畫這種依賴程度是直接依賴還是間接依賴.此外，在實驗觀察中，我們發(fā)現(xiàn)互信息強(qiáng)的變量對在真實的網(wǎng)絡(luò)結(jié)構(gòu)中并不存在邊，反而互信息相對弱的變量對在真實的網(wǎng)絡(luò)中存在邊.為了高效地獲得潛在結(jié)構(gòu)中真實的邊，我們設(shè)計了一種“偷懶”啟發(fā)式策略.根據(jù)度量信息矩陣，對變量序中任意一對變量執(zhí)行條件獨立性檢驗時，任意階條件獨立性斷言都不依賴于序中前面的變量，除非該變量與行變量不獨立.

算法具體描述如下：首先初始化了2個由節(jié)點構(gòu)成的無向圖矩陣mn×n和Gn×n.其中，mn×n是由變量序構(gòu)成的度量信息矩陣.該矩陣中的每一行暗含了與行變量對應(yīng)的變量的檢驗順序.其中m(i,j)=k指示了矩陣的第i行、第j列元素變量k與變量i的依賴強(qiáng)度排在第j個位置.矩陣mn×n是動態(tài)變化，條件集的規(guī)模以及獨立性計算由它決定.矩陣Gn×n刻畫了最終每個變量的鄰居集合，它隨著度量信息矩陣變化.初始化時，i=j,G(i,j)=0，否則G(i,j)=1.在這里，0表示變量對之間沒有邊，1表示有邊.

算法根據(jù)度量信息首先選擇依賴程度最弱的變量對(i,m(i,j))執(zhí)行條件獨立性檢測Ind(i,m(i,j)|S)，S?V{i,m(i,j)}，如果Ind(i,m(i,j)|S)=1，則設(shè)置G(i,m(i,j))=0同時設(shè)置m(i,j)=0；如果矩陣m中有0元素出現(xiàn)，那么后續(xù)變量的條件獨立性檢驗的條件集就不再考慮該元素.即當(dāng)處理變量對(i,m(i,j+k))時，如果?j∈[1,j+k-1]滿足m(i,j)=0,則S?V{i,m(i,j),m(i,j+k)}，否則S?V{i,m(i,j+k)}.

算法1. 基于變量序的貝網(wǎng)結(jié)構(gòu)學(xué)習(xí)算法BNSvo-learning.

輸入：數(shù)據(jù)集data;

輸出：BNS結(jié)構(gòu)G.

① 初始化矩陣Gn×n;

② 根據(jù)互信息學(xué)習(xí)信息度量矩陣mn×n;

③ for對矩陣m中的元素執(zhí)行獨立性檢驗

④ 初始化條件集規(guī)模:order←0;

⑤ 獲取當(dāng)前的條件集S;

⑥ while |S|

⑦ 執(zhí)行條件獨立性檢驗;

⑧ if條件獨立性檢驗

⑨G(i,m(i,j))←0;*更新矩陣G和m*

⑩m(i,j)←0;

2.2 理論分析

BNSvo-learning算法根據(jù)度量信息矩陣執(zhí)行條件獨立性檢驗時，實際上采用了一種“偷懶”啟發(fā)式的檢驗策略.下面分析該算法的一些重要性質(zhì).

在給出這些性質(zhì)之前，先介紹需用到的信息論知識：H(X)指示了一個離散隨機(jī)變量X的熵；H(X|Y)指示了2個隨機(jī)變量X和Y之間的條件熵；I(X;Y)指示了2個隨機(jī)變量X和Y之間的互信息.

定理1. 對任意2個隨機(jī)變量X和Y，有:

1)I(X;Y)≥0;

2)H(X|Y)≤H(X).

上面兩式當(dāng)且僅當(dāng)X和Y相互獨立時等號成立[1].

定理2. 對任意3個離散隨機(jī)變量X,Y和Z有:

1)I(X;Y|Z)≥0;

2)H(X|Y,Z)≤H(X|Z).

上面兩式當(dāng)且僅當(dāng)X和Y相互獨立時等號成立[1].

定理3. BNSvo-learning算法中，當(dāng)I(X;Y)>I(X;Z)，給定Z時，X和Y不滿足條件獨立性.

證明. 充分條件，反證法.假定I(X;Y|Z)=0成立.

由定理2可得：

H(X|Y,Z)=H(X|Z)，

由I(X;Y)=H(X)-H(X|Y)可得：

H(X|Z)=H(X)-I(X;Z).

由H(X|Z,Y)=H(X)-I(X;Z,Y)可得：

H(X)-I(X;Z)=H(X)-I(X;Z,Y).

由I(X;Z)=I(X;Z,Y)可得：

I(X;Z)>I(X;Y).

與已知I(X;Y)>I(X;Z)相矛盾，充分條件得證.

必要條件：

由I(X;Y|Z)=H(X|Z)-H(X|Z,Y)，
且H(X|Z)=H(X)-I(X,Z)可得：
I(X;Y|Z)=H(X)-I(X;Z)-H(X|Z,Y)，
由H(X|Z,Y)≤H(X|Y)
且H(X)-I(X;Z)-H(X|Z,Y)≥
H(X)-I(X;Z)-H(X)+I(X;Y)可得：
H(X)-I(X;Z)-H(X|Z,Y)≥
I(X;Y)-I(X;Z).
由I(X;Y)>I(X;Z)可得：
H(X)-I(X;Z)-H(X|Z,Y)>0，
可得：I(X:Y|Z)>0.

證畢.

定理3證明了在一階條件獨立性檢驗過程中，互信息強(qiáng)的變量對是否獨立一定不依賴于互信息弱的變量.為此，BNSvo-learning算法對任意一變量對執(zhí)行一階條件獨立性檢驗時，沒有考慮變量序中前面的變量作為其條件集.

為了進(jìn)一步說明BNSvo-learning算法的有效性，我們給出定理4和推論1.

定理4. BNSvo-learning算法中，當(dāng)I(X;Y)>I(X;Z)，I(X;Y)>I(X;W)且I(X;Z|Φ)=0或I(X;W|Φ)=0時,給定Z，X和Y不滿足條件獨立性.

證明.

由I(X;Y)>I(X;Z)，
I(X;Y)>I(X;W)，
I(X;Z|Φ)=0可得：
I(X;Z,W)

由定理3可知，定理4成立.

證畢.

定理4說明了邊緣獨立的變量對和互信息弱的變量組合得到高階的條件集不能影響互信息強(qiáng)的變量對的條件獨立性斷言.為此，在檢驗過程中算法不考慮這樣的條件集.

推論1. 當(dāng)I(X;Y)

直觀上來說，該啟發(fā)式策略遵循：如果互信息強(qiáng)的變量組合的條件集不能使得變量對獨立，那么含有強(qiáng)度弱的變量的條件集也不能使得變量對獨立.形式化說明如下：

假定I(X;W)0,那么I(X;Y|Z,W)>0或者I(X;Y|W,H)>0.尤其當(dāng)條件集的規(guī)模較大時，弱的變量提供的信息會更少.

在做條件獨立性斷言的決策時，我們期望2種情況出現(xiàn)：①I(X;Y|Φ)=0,這意味著無論2個隨機(jī)變量X和Y在矩陣mn×n中的順序如何，二者滿足邊緣獨立.②對于變量X而言，S?V{X,Y}，?I(X;Y)

定義1. 不一致性斷言.隨機(jī)變量X和Y分別執(zhí)行完條件獨立性檢驗后，存在X∈adj(Y),Y?adj(X)，我們稱隨機(jī)變量X和Y之間的條件獨立性斷言為不一致性斷言.

我們不期望不一致性斷言的出現(xiàn).因為我們很難對該類斷言做出合理的決策.如果選擇獨立性成立，那么可能造成假陰性邊，否則造成假陽性邊.事實上，選擇不成立是可靠的.最糟糕的情況就是執(zhí)行條件獨立性檢測后，變量X的鄰居集合沒有任何變化，簡單地說，花了大量的時間做了無用功，但是這至少保證了沒有假陰性邊，保證了存在找到最佳的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的可能性.

定理5. BNSvo-learning算法是可納的.

算法采用的啟發(fā)式策略避免了由高階獨立性檢驗造成的假陰性節(jié)點.另外，對任意變量對(X,Y)執(zhí)行條件獨立性檢驗時，如果獨立，則對X的鄰居集合修訂adj(X)=adj(X)Y；變量Y的鄰居集合adj(Y)保持不變.換句話說，對于變量Y而言，它和X是否條件獨立只與Y和其對應(yīng)的變量序有關(guān).這樣防止由變量X的誤判對變量Y的影響.

為了進(jìn)一步減少時間代價，算法在保證質(zhì)量的前提下，對BNSvo-learning算法做了進(jìn)一步的改進(jìn)，當(dāng)m(i,j)=0，對于變量m(i,j)而言，在變量i的索引iindex滿足iindex

這樣做的想法很直觀，對于變量X而言,如果變量對(X,Y)條件獨立性成立，那么對于變量Y而言，如果變量X之后仍有許多互信息強(qiáng)的變量，那么(X,Y)條件獨立性成立的概率很大.

算法2. 改進(jìn)后的學(xué)習(xí)算法IBNSvo-learning.

輸入:數(shù)據(jù)集data;

輸出：更新后的m.

① for矩陣m中第m(i,j)行的每一個元素

② if變量i在第m(i,j)行中的索引為iindex

④m(m(i,j),iindex)←0;

⑤G(m(i,j),i)←0;

⑥ end if

⑦ end if

⑧ end for

⑨ returnm.

改進(jìn)后算法的實現(xiàn)，只需將IBNSvo-learning算法的行①～⑨嵌入在BNSvo-learning算法的行⑩～之間即可.

3 實 驗

為了說明BNSvo-learning算法的性能，我們從貝葉斯網(wǎng)絡(luò)知識庫(the Bayesian network repository, BNR)[30]中選擇了5個不同規(guī)模的網(wǎng)絡(luò).同時也使用了拼貼技術(shù)[31]生成了一個適中規(guī)模網(wǎng)絡(luò)Insurance 1和大網(wǎng)絡(luò)Insurance 2.表1展示了7個網(wǎng)絡(luò)中的節(jié)點數(shù)、弧數(shù)、最大父節(jié)點數(shù)和最大狀態(tài)數(shù).

Table 1 Bayesian Networks Used in the Evaluation Study表1 在評估研究中使用的貝葉斯網(wǎng)絡(luò)

3.1 實驗結(jié)果對比

為了說明算法的可靠性，我們從以下4個方面來驗證算法：1)變量的狀態(tài)數(shù)少，屬性數(shù)少，樣本量10 000時(Asia-8,Sachs-11)； 2)變量的狀態(tài)數(shù)多，屬性數(shù)適中，樣本量10 000時(Alarm-37，Child-20)；3)變量狀態(tài)數(shù)多，屬性數(shù)多，樣本量5 000時(Insurance1，Insurance2);4)變量的狀態(tài)數(shù)少，屬性數(shù)多，樣本量5 000時(Pigs-441).

我們采用了邊評分的評價方法來驗證算法的精度性能即計算缺失邊數(shù)(Missing)、多余邊數(shù)(Additional)以及反向邊數(shù)(Reverse).Edge Type越低表明算法的性能越好.表2給出了學(xué)習(xí)結(jié)構(gòu)的邊評分結(jié)果,其中，HC(Hill-Climbing)是指經(jīng)典的基于評分方式的近似結(jié)構(gòu)學(xué)習(xí)算法[1].

Table 2 Results Comparison of Our Method with Classic Algorithms表2 和經(jīng)典算法的對比實驗結(jié)果

表2中的空白項表示由于內(nèi)存不足或時間代價過高沒有得到最終解.對于HC算法，在實驗中發(fā)現(xiàn)，當(dāng)數(shù)據(jù)維數(shù)超過200時，就警示“內(nèi)存不足”.其原因是：當(dāng)前結(jié)構(gòu)的候選鄰居接近n2，每一個候選鄰居都是一個n×n的矩陣，故需要n4的存儲空間.對于PC和PC-Stable以及MMHC算法，時間代價過高.究其原因：隨著數(shù)據(jù)維數(shù)的增加以及變量對的非獨立性關(guān)系的成立，導(dǎo)致條件集規(guī)模迅速增大，從而使得獨立性檢測次數(shù)的指數(shù)級增長速度很快.

然而，本文提出的BNSvo-learning算法不僅不會遭遇到上述其他算法內(nèi)存不足或時間代價高的情況，而且通過和真實結(jié)構(gòu)的對比，除了Child數(shù)據(jù)外，解的質(zhì)量優(yōu)于對比算法.這不僅表現(xiàn)在簡單的數(shù)據(jù)集Asia和Sachs上，而且對于高維稀疏的數(shù)據(jù)集Pigs依然出色.

為了說明BNSvo-learning算法在有限樣本條件下的可靠性，我們分別在屬性數(shù)是370，樣本量是500，1 000，5 000的Alarm數(shù)據(jù)集[31]上進(jìn)行了驗證.由表3可以看出，在處理樣本量小、屬性數(shù)多的數(shù)據(jù)集時，BNSvo-learning算法依然表現(xiàn)良好.

Table3ResultsComparisonofOurMethodwithConstraint-BasedAlgorithms

表3 與經(jīng)典基于約束的算法的對比實驗結(jié)果

3.2 時間代價對比實驗結(jié)果

本文提出的BNSvo-learning算法不僅在網(wǎng)絡(luò)的結(jié)構(gòu)質(zhì)量上有保障，而且在時間的需求上也合理.下面我們分別從實驗和理論進(jìn)行驗證和說明.表4給出了和經(jīng)典算法在時間需求上的對比實驗.

Table 4 Performance Comparison of Algorithms in Time Cost表4 算法在時間代價上的性能比較 s

從表4中可以看出，所提算法BNSvo-learning在時間性能上顯著優(yōu)于經(jīng)典的算法，尤其在處理高維稀疏數(shù)據(jù)集Pigs時，該算法能在6 943 s中求解，而對比算法在以天為單位的時間內(nèi)得不到解.其原因在之前的精度性能實驗中已作了分析，這里不再贅述.

3.3 BNSvo-learning及其改進(jìn)算法時間代價對比

我們分別選取了不同規(guī)模的數(shù)據(jù)集，從時間代價層面展示了2種算法的性能，如表5所示.從表5中可以看出，隨著數(shù)據(jù)集屬性數(shù)的增多，改進(jìn)后的算法明顯優(yōu)于BNSvo-learning算法.

IBNSvo-learning算法時間代價小的主要原因有2點：1)當(dāng)設(shè)置m(m(i,j),iindex)=0，算法沒有再對變量對(m(i,j),i)執(zhí)行條件獨立性檢測.具體而言，假設(shè)對于變量m(i,j)而言，還有w個待檢變量，那么最壞的情況可能要執(zhí)行2w次條件獨立性檢測.2)變量m(i,j)對應(yīng)的其他變量的條件獨立性檢測次數(shù)減少.如果沒有置0，最壞的情況下，條件獨立性檢測次數(shù)是2w+1；置0，最壞的情況下是2w.

Table 5 Performance Comparison of Algorithms in Time Cost表5 算法在時間代價上的性能比較 s

3.4 真實世界實驗

為了評估所提出算法在實際應(yīng)用中的效果，我們用真實的數(shù)據(jù)集進(jìn)行了實驗.該數(shù)據(jù)集來源于供熱機(jī)組3個月全工況監(jiān)測數(shù)據(jù).其中數(shù)據(jù)維數(shù)為50，每個月的樣本量分別為43 200，44 640，44 641條，變量的最大狀態(tài)數(shù)是10.由于沒有真實的網(wǎng)絡(luò)結(jié)構(gòu)，我們僅在時間代價性能上做了對比實驗.表6給出了在真實的電力數(shù)據(jù)集上關(guān)于需求時間的對比實驗.

Table 6 Performance Comparison of Algorithms in Time Cost表6 算法在時間代價上的性能比較 s

從表6可以看出，當(dāng)數(shù)據(jù)維數(shù)適中、樣本量較大時，所提算法依然能夠在合理的時間內(nèi)求解，這表明BNSvo-learning算法能夠很好地擴(kuò)展到大樣本量的數(shù)據(jù)集上.此外，經(jīng)典的爬山算法表現(xiàn)得相對很差，主要原因是樣本量過大使得評分函數(shù)需要的計算時間加長.

4 總結(jié)與展望

本文的貢獻(xiàn)如下：1)首次嘗試提出使用變量間互信息來刻畫變量序的度量信息矩陣，以實現(xiàn)條件獨立性檢驗不是盲目地選擇變量對，而是依賴于度量信息矩陣提供的信息有選擇地進(jìn)行；2)基于度量信息矩陣提議了一種合理的“偷懶”啟發(fā)式策略，有效地避免高階獨立性，減少檢驗次數(shù)，保證了檢驗可靠性.我們從理論上證明算法的有效性，從實驗上驗證了算法的高效性和可靠性.但是由于在定向階段我們采用了與PC算法類似的方式，這種方式對個體定向錯誤敏感，尤其是υ-結(jié)構(gòu)的定向，后期將探討采用評分-搜索的策略解決定向問題；另外，對于數(shù)據(jù)集Child，本文所提算法雖然在時間性能和Missing上優(yōu)于對比算法，但會導(dǎo)致過多的Additional和Reverse.跟蹤實驗發(fā)現(xiàn)，Additional主要是由于當(dāng)樣本數(shù)小于自由度時(相關(guān)概念讀者可查閱文獻(xiàn)[20])經(jīng)典的算法和所提算法都采用了選擇依賴的方法，后期我們將針對該問題進(jìn)行研究.

QiXiaolong, born in 1981. PhD candidate and lecturer. His main research interests include probabilistic graphical models, machine learning.

GaoYang, born in 1972. PhD, professor, PhD supervisor. Committee member of CCF. His main research interests include reinforcement learning, agent theory (belief revision) and multi-agent systems, intelligent system, image process and video surveillance.

WangHao, born in 1983. PhD, assistant researcher. His main research interests include rank-aware query processing, reco-mmender systems, reinforcement learning & transfer learning (wanghao@nju.edu.cn).

SongBei, born in 1994. Master candidate. Her main research interests include industrial big data analysis, probabilistic graph model (songbei07@gmail.com).

ZhouChunlei, born in 1973. Engineer. Her main research interests include informationization of energy conservation and emission reduction in power industry and industrial big data mining (13913918185@163.com).

ZhangYouwei, born in 1986. Engineer. His main research interests include informationization of energy conservation and emission reduction in power industry and industrial big data mining (15905166639@163.com).