郭坤，王浩，姚宏亮，李俊照

(合肥工業(yè)大學(xué)計算機(jī)與信息學(xué)院，安徽 合肥 230009)

在給定貝葉斯網(wǎng)絡(luò)(Bayesian networks)中一個變量的馬爾可夫毯(Markov blanket)時，貝葉斯網(wǎng)絡(luò)中其他變量與該變量條件獨(dú)立，一個變量的馬爾可夫毯能夠屏蔽貝葉斯網(wǎng)絡(luò)中其他變量對該變量的影響，可用來預(yù)測、分類和因果發(fā)現(xiàn)等.

確定目標(biāo)變量的馬爾可夫毯有2類方法:利用打分—搜索方法等建立貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)，然后基于貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)確定目標(biāo)變量的馬爾可夫毯，但該類方法得到的馬爾可夫毯不準(zhǔn)確，且學(xué)習(xí)方法效率低;另一類是利用局部學(xué)習(xí)的方法直接學(xué)習(xí)目標(biāo)變量的馬爾可夫毯.當(dāng)前研究者主要采用基于局部學(xué)習(xí)的方法學(xué)習(xí)馬爾可夫毯，相關(guān)工作如Margaritis和Thrun提出了 GS(Grow-Shrink)算法［1］，首先啟發(fā)式地搜索所有與目標(biāo)變量依賴的變量，然后去除冗余的變量.由于配偶節(jié)點(diǎn)較晚進(jìn)入候選的馬爾可夫毯，導(dǎo)致候選的馬爾可夫毯中引入了較多的錯誤節(jié)點(diǎn)，降低了后面的條件獨(dú)立測試的有效性和可靠性.Tsamardinos等對GS進(jìn)行了改進(jìn)，提出了IAMB(incremental association Markov blanket)算法［2］，每入選一個變量，就對該變量進(jìn)行條件獨(dú)立測試，減少了錯誤變量的引入;但該算法的條件獨(dú)立測試是在給定整個馬爾可夫毯下進(jìn)行的，條件獨(dú)立測試要求的數(shù)據(jù)量較大［3］.Tsamardinos等提出的 MMMB(max-min Markov blanket)算法［4］首先利用 MMPC(max-min parents and children)算法［4］尋找目標(biāo)節(jié)點(diǎn)的父節(jié)點(diǎn)和子節(jié)點(diǎn)，然后找到它的配偶節(jié)點(diǎn)，但該方法會引入錯誤的父子節(jié)點(diǎn)和配偶節(jié)點(diǎn)［5］.與此相似的算法還有 Hiton-MB(Hiton-Markov blanket)算法［6］.Tsamardinos等在貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法MMHC(maxmin Hill-climbing)［7］中調(diào)用 MMPC 算法時，利用父節(jié)點(diǎn)與子節(jié)點(diǎn)對稱的性質(zhì)，去除MMPC算法引入的錯誤父子節(jié)點(diǎn).而 PCMB(parents-children Markov blanket)算法［5］利用完整的條件獨(dú)立測試去除錯誤節(jié)點(diǎn)，但存在時間復(fù)雜度較大的問題.

針對上述算法存在引入錯誤節(jié)點(diǎn)和時間復(fù)雜度較大的問題，為了提高學(xué)習(xí)馬爾可夫毯的精度和效率，在馬爾可夫毯學(xué)習(xí)算法中引入回歸分析［8］.回歸分析可以在發(fā)現(xiàn)與目標(biāo)變量相關(guān)性很強(qiáng)的變量的同時，去掉與目標(biāo)變量相關(guān)性弱或無關(guān)的變量.回歸分析廣泛應(yīng)用于機(jī)器學(xué)習(xí)中的特征選擇，從變量集合中選取最優(yōu)的特征子集［9］.根據(jù)變量數(shù)據(jù)取值是否連續(xù)，將回歸分析分為線性回歸分析和邏輯回歸分析［10］(logistic regression analysis)2 類.邏輯回歸分析可以有效處理貝葉斯網(wǎng)絡(luò)中的離散數(shù)據(jù).因此，如何讓學(xué)習(xí)到的馬爾可夫毯更加精確，學(xué)習(xí)過程效率更高，是馬爾可夫毯學(xué)習(xí)算法的核心問題.提出一種基于邏輯回歸分析對MMMB算法改進(jìn)的RAMMMB(regression analysis-max min Markov blanket)算法.該算法對MMMB算法過程中的候選馬爾可夫毯與目標(biāo)變量進(jìn)行邏輯回歸分析，去掉相關(guān)性弱的變量，然后進(jìn)行條件獨(dú)立測試，去掉候選馬爾可夫毯存在的兄弟節(jié)點(diǎn)，得到最終的馬爾可夫毯.本文采用文獻(xiàn)［11］中的G2測試來判斷2個變量在給定變量集時是否條件獨(dú)立，實(shí)驗(yàn)證明，該方法能有效地去掉MMMB算法包含的錯誤變量，并減少了條件獨(dú)立測試的次數(shù).

1 貝葉斯網(wǎng)絡(luò)及相關(guān)定義

設(shè)V代表一組離散隨機(jī)變量，用〈G，θ〉來表示貝葉斯網(wǎng)絡(luò)，其中有向無環(huán)圖G中的節(jié)點(diǎn)對應(yīng)V中的變量，是指G中每個節(jié)點(diǎn)X在給定它的父節(jié)點(diǎn)Pa(X)下的條件概率分布p(X|Pa(X)).貝葉斯網(wǎng)絡(luò)的聯(lián)合概率分布可表示如下:

定義1 碰撞節(jié)點(diǎn).如果路徑P中的節(jié)點(diǎn)W含有2條指向它的邊，那么節(jié)點(diǎn)W在P中是碰撞節(jié)點(diǎn).在給定W時，它的2個父節(jié)點(diǎn)條件依賴.

定義2d分離.如果下列任意一條成立:1)路徑P上存在一個包含于集合Z的非碰撞節(jié)點(diǎn);2)路徑P上的碰撞節(jié)點(diǎn)和它的子孫節(jié)點(diǎn)均不包含在Z中，那么稱節(jié)點(diǎn)X到節(jié)點(diǎn)Y的一條路徑P被節(jié)點(diǎn)集合Z阻塞.當(dāng)且僅當(dāng)從X到Y(jié)的每條路徑均被Z阻塞，稱節(jié)點(diǎn)X和Y被Z集合d分離.當(dāng)有向無環(huán)圖G和聯(lián)合概率分布滿足忠實(shí)性條件時，d分離與條件獨(dú)立等價.本文中Ind(X;T|Z)表示變量T和X在給定變量集Z時條件獨(dú)立;Dep(X;T|Z)表示變量T和X在給定Z時條件依賴.

定義3 馬爾可夫毯.一個變量T的馬爾可夫毯MB(T)是在給定該集合時，變量集V中所有其他的節(jié)點(diǎn)與T條件獨(dú)立的最小集合.即對?X∈V(MB(T)∪T)，Ind(X;T|MB∪T)).有向無環(huán)圖G中的每個節(jié)點(diǎn)T，它的馬爾可夫毯MB(T)包括T的父節(jié)點(diǎn)、子節(jié)點(diǎn)和配偶節(jié)點(diǎn)(與T共同有一個子節(jié)點(diǎn)).

圖1中節(jié)點(diǎn)T的馬爾可夫毯包括父節(jié)點(diǎn){B，E}、子節(jié)點(diǎn){C，D}和配偶節(jié)點(diǎn)F.

圖1 T的馬爾可夫毯(陰影節(jié)點(diǎn))Fig.1 The Markov blanket of node T(shadow nodes)

2 MMMB算法

2.1 MMMB 算法描述

MMMB算法采用分治法發(fā)現(xiàn)目標(biāo)變量T的馬爾可夫毯MB(T)，首先調(diào)用MMPC算法找到T的父子節(jié)點(diǎn)集PC(T)，然后找到T的配偶節(jié)點(diǎn).T的父子節(jié)點(diǎn)集PC(T)和配偶節(jié)點(diǎn)組成了T的馬爾可夫毯MB(T).MMPC算法首先利用啟發(fā)式搜索策略使與T相關(guān)的變量依次進(jìn)入T的候選父子節(jié)點(diǎn)集CPC，然后移去CPC中被錯誤引入的變量［11］;MMMB算法對PC(T)中的每一個元素調(diào)用MMPC算法，得到T的候選馬爾可夫毯CMB，經(jīng)過條件獨(dú)立性測試，找到T的配偶節(jié)點(diǎn).然而，MMPC算法會包含未去掉的T的錯誤父子節(jié)點(diǎn)，MMMB算法也會引入T的錯誤的配偶節(jié)點(diǎn).MMPC算法和MMMB算法描述如下.

1)MMPC算法.

2)MMMB算法描述:

2.2 MMMB算法存在的問題

MMPC算法去掉錯誤節(jié)點(diǎn)的依據(jù)為:如果X?PC(T)，在給定Z?PC(T)下，X與T條件獨(dú)立，通過條件獨(dú)立測試可以將添加到CPC中的錯誤節(jié)點(diǎn)去掉.但存在有些錯誤節(jié)點(diǎn)不能被去掉，以圖2(a)為例，節(jié)點(diǎn)T的父子節(jié)點(diǎn)集合PC(T)={A}，對T調(diào)用MMPC算法:

1)CPC添加節(jié)點(diǎn).

①CPC=?，A與T鄰接，Dep(A;T|?)的值最大，節(jié)點(diǎn)A首先進(jìn)入到CPC;

②CPC={A}，路徑T→A←B→C中的碰撞節(jié)點(diǎn)A包含在{A}中，該路徑未被{A}阻塞，Dep(C;T|A);而Ind(B;T|?)，節(jié)點(diǎn)C被添加到CPC;

③CPC={A，C}，由于 Ind(B;T|?)，節(jié)點(diǎn)B不能被添加到CPC.

2)CPC={A，C}去掉錯誤節(jié)點(diǎn).

①給定任意的集合Z，Dep(A;T|Z)，所以A不會從CPC中移除.

②由于路徑T→A→C中的非碰撞節(jié)點(diǎn)A并不包含在?中，該路徑未被?阻塞，Dep(C;T|?)，且Dep(C;T|A).所以不存在CPC{C}的子集s使得Ind(C;T|s)，節(jié)點(diǎn)C并不能被移除，CPC={A，C}.但節(jié)點(diǎn)C并不在真實(shí)的PC(T)中.

圖2 MMPC算法引入錯誤節(jié)點(diǎn)CFig.2 Incorrect node C included in CPC returned MMMB算法尋找配偶節(jié)點(diǎn)的依據(jù)為:對X∈

同理，圖2(b)中的節(jié)點(diǎn)C也會包含在MMPC算法輸出的父子節(jié)點(diǎn)集合中.CMBPC(T)，Y∈PC(T)，如果存在集合Z(X，T?Z)，且Ind(X;T|Z)，使得Dep(X;T|{Y}∪Z)，那么X為Y的配偶節(jié)點(diǎn).即使MMPC算法輸出的CPC為正確的PC(T)，MMMB算法返回的MB(T)也會包含錯誤的配偶節(jié)點(diǎn).例如圖3中節(jié)點(diǎn)T的父子節(jié)點(diǎn)PC(T)為{B，D}，候選馬爾可夫毯 CMB={A，B，C，D}.由圖 3易知Ind(A;T|{B})，路徑A→C→D←T中的碰撞節(jié)點(diǎn)D包含在集合{D}∪{B}中，所以Dep(A;T|{D}∪{B}).A被添加到馬爾可夫毯中，但是實(shí)際上A并不在節(jié)點(diǎn)T的馬爾可夫毯MB(T)中.

圖3 MMMB算法引入T的錯誤的配偶節(jié)點(diǎn)AFig.3 Incorrect spouse node A included in MMMB

MMPC算法添加的錯誤節(jié)點(diǎn)會包含在最終的馬爾可夫毯MB(T)中，而且這些節(jié)點(diǎn)會引入T的錯誤的配偶節(jié)點(diǎn).即使MMPC算法返回的是正確的PC(T)，MMMB本身也會引入錯誤的配偶節(jié)點(diǎn).所以，為了提高學(xué)習(xí)馬爾可夫毯算法的精度和效率，需要去掉這些錯誤的變量，而這些變量與目標(biāo)變量的相關(guān)性不強(qiáng).

3 RA-MMMB算法

3.1 根據(jù)相關(guān)性將節(jié)點(diǎn)分類

根據(jù)貝葉斯網(wǎng)絡(luò)中各節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)T的相關(guān)性關(guān)系，把MMMB算法中候選馬爾可夫毯CMD=PC(T)∪C∈PC(T)MMPC(C){T}中的節(jié)點(diǎn)分為4類:

1)T的父節(jié)點(diǎn)和T的子節(jié)點(diǎn):這類節(jié)點(diǎn)與T有很強(qiáng)的相關(guān)性;

2)T的父節(jié)點(diǎn)的父節(jié)點(diǎn)和T的子節(jié)點(diǎn)的子節(jié)點(diǎn):由于貝葉斯網(wǎng)絡(luò)已存在T的父節(jié)點(diǎn)和T的子節(jié)點(diǎn)，故這類節(jié)點(diǎn)與T的相關(guān)性較弱;

3)T的兄弟節(jié)點(diǎn)(與T共同有一個父節(jié)點(diǎn))和T的配偶節(jié)點(diǎn):這類節(jié)點(diǎn)和T有共同的原因或結(jié)果，當(dāng)給定T的父節(jié)點(diǎn)或T的子節(jié)點(diǎn)時，與T的相關(guān)性較強(qiáng);

4)MMPC算法引入的錯誤節(jié)點(diǎn)的父子節(jié)點(diǎn)中上述3類以外的節(jié)點(diǎn)，這類節(jié)點(diǎn)與T的相關(guān)性最弱.

3.2 候選馬爾可夫毯的邏輯回歸分析

回歸分析［12］可以從自變量集合中選入與因變量相關(guān)性強(qiáng)的自變量，并去掉那些與因變量無關(guān)的變量和與因變量相關(guān)性弱的次要變量.以目標(biāo)變量T為因變量，MMMB算法中的候選馬爾可夫毯CMB為自變量集合，進(jìn)行回歸分析，可以從CMB中去掉與目標(biāo)變量相關(guān)性不強(qiáng)的變量.

3.2.1 候選馬爾可夫毯的邏輯回歸分析模型

一般貝葉斯網(wǎng)絡(luò)中的數(shù)據(jù)為離散值，所以對目標(biāo)變量和候選馬爾可夫毯采用邏輯回歸分析［11］.當(dāng)目標(biāo)變量T為0-1型(取值為2個)因變量，CMB為自變量集合時，二元邏輯回歸模型為

式中:p=P(T=1)，X1，X2，…，Xk∈CMB，β0，β1，…，βk為未知參數(shù)，稱為回歸系數(shù).采用極大似然估計方法得到回歸系數(shù)的估計值^β0，^β1，…，^βk.當(dāng)因變量取值為多個(大于2個)時，采用多元邏輯回歸.當(dāng)目標(biāo)變量T的取值有a、b、c3種，CMB為自變量集合時，多元邏輯回歸的模型為:

回歸分析通過假設(shè)檢驗(yàn)判斷回歸系數(shù)是否為零來決定是否去掉候選馬爾可夫毯中的變量.假設(shè)H0∶βi=0，i=1，2，…，k，邏輯回歸中回歸系數(shù)的檢驗(yàn)統(tǒng)計量采用Wald統(tǒng)計量，即

式中:S^βi為回歸系數(shù)的標(biāo)準(zhǔn)誤差.Wald統(tǒng)計量服從自由度為1的χ2分布.原假設(shè)是正確的卻拒絕了該假設(shè)，犯這類錯誤的概率記為p.當(dāng)概率值p小于給定的顯著性水平α(一般取α=0.05)時，則拒絕原假設(shè)，認(rèn)定該回歸系數(shù)不為零;反之，認(rèn)定該回歸系數(shù)為零，則將該變量從方程中去掉.概率p值越小，表明對應(yīng)的變量對目標(biāo)變量T的影響就越顯著.

3.2.2 候選馬爾可夫毯的邏輯回歸分析過程

采用逐步后向回歸依次去掉候選馬爾可夫毯CMB中與目標(biāo)變量T相關(guān)性弱的變量.如果邏輯回歸方程中自變量集合存在回歸系數(shù)為零的概率值p大于顯著性水平的變量，則將回歸方程中p值最大的變量從CMB中去掉，然后建立CMB中剩余的變量與目標(biāo)變量的邏輯回歸方程，繼續(xù)進(jìn)行回歸分析，再將方程中概率值p最大的變量從CMB去掉，繼續(xù)回歸分析直至回歸方程中不再含有p值大于顯著性水平的變量.

由于CMB中的第4)類節(jié)點(diǎn)與T的相關(guān)性最弱，所以會在逐步后向回歸中最先被去掉;因?yàn)榛貧w方程中含有T的父節(jié)點(diǎn)和子節(jié)點(diǎn)，接下來與T的相關(guān)性較弱的第2)類節(jié)點(diǎn)會作為回歸方程中的次要變量從CMB中被去掉;第3)類節(jié)點(diǎn)由于T的父節(jié)點(diǎn)和T的子節(jié)點(diǎn)的存在，與T的相關(guān)性較強(qiáng)，所以會保留在CMB中;而第1)類節(jié)點(diǎn)與T的相關(guān)性最強(qiáng)，也包含在CMB中.

3.3 去除兄弟節(jié)點(diǎn)

經(jīng)過逐步后向回歸分析，最終的CMB中包含T的父節(jié)點(diǎn)和子節(jié)點(diǎn)、配偶節(jié)點(diǎn)和兄弟節(jié)點(diǎn).在給定T的父節(jié)點(diǎn)時，T的兄弟節(jié)點(diǎn)與T條件獨(dú)立.對于X∈CMB{PC(T)}，Y∈PC(T)，如果 Ind(X;T|Y)，則將X從CMB中去掉.而CMB{PC(T)}中不存在給定子節(jié)點(diǎn)時與T條件獨(dú)立的變量，所以不會去掉馬爾可夫毯中的變量.通過條件獨(dú)立測試，去掉T的兄弟節(jié)點(diǎn)，得到最終的馬爾可夫毯.如果PC(T)中的元素在逐步后向回歸分析中被去掉，說明該元素為T的錯誤的父子節(jié)點(diǎn)，把它從候選馬爾可夫毯CMB中去掉的同時，從PC(T)中也把它去掉，減少不必要的條件獨(dú)立測試，并且避免在馬爾可夫毯中引入其他錯誤的變量.

3.4RA-MMMB 算法描述

基于邏輯回歸分析的馬爾可夫毯學(xué)習(xí)算法RAMMMB描述如下:

RA-MMMB算法:

RA-MMMB算法運(yùn)用逐步后向回歸依次把MMMB算法中的候選馬爾可夫毯CMB中與目標(biāo)變量相關(guān)性弱的變量去掉，再經(jīng)過條件獨(dú)立測試，去掉兄弟節(jié)點(diǎn)，返回最終的馬爾可夫毯.由于MMPC算法引入的錯誤節(jié)點(diǎn)是目標(biāo)變量的子節(jié)點(diǎn)的子節(jié)點(diǎn)，MMMB算法引入的錯誤的配偶節(jié)點(diǎn)是目標(biāo)變量的父節(jié)點(diǎn)的父節(jié)點(diǎn)，都屬于上述第2)類節(jié)點(diǎn)，它們會在回歸分析中被去掉.RA-MMMB算法的回歸分析過程去掉與目標(biāo)變量相關(guān)性弱的變量后，只需去掉回歸分析后的CMB中的兄弟節(jié)點(diǎn)就能得到馬爾可夫毯，與MMMB算法相比，減少了大量條件獨(dú)立性測試，并且由于條件變量集很小，保證了條件獨(dú)立測試的可靠性.

4 實(shí)驗(yàn)分析與算法比較

在Matlab 7.0和SPSS17的軟件環(huán)境下，利用Insurance網(wǎng)(含有27個節(jié)點(diǎn))和Alarm網(wǎng)(含有37個節(jié)點(diǎn))的500、1 000、5 000組數(shù)據(jù)，對這2個網(wǎng)絡(luò)中的每個節(jié)點(diǎn)分別使用MMMB算法、PCMB算法和RA-MMMB算法輸出它的馬爾可夫毯，并進(jìn)行對比.由于實(shí)驗(yàn)數(shù)據(jù)為離散數(shù)據(jù)，對取值為2的目標(biāo)變量，RA-MMMB算法在SPSS軟件里采用二元邏輯回歸，對取值為多個(大于2)的目標(biāo)變量，采用多元邏輯回歸.

4.1 評價標(biāo)準(zhǔn)

本文采用PCMB算法所在的文獻(xiàn)［5］里的查準(zhǔn)率(precision)、查全率(recall)以及它們之間的歐氏距離d來衡量馬爾可夫毯學(xué)習(xí)算法的好壞.對于一個目標(biāo)變量T，查準(zhǔn)率是指算法輸出的MB(T)中包含正確變量的比率;查全率是指算法輸出的MB(T)中正確變量的個數(shù)占實(shí)際MB(T)變量個數(shù)的比率.

為了對上述2個標(biāo)準(zhǔn)進(jìn)行綜合評價，定義兩者之間的歐氏距離為

式中:d表明算法準(zhǔn)確率，d越小，表明算法準(zhǔn)確率越高.

4.2 分析與比較

針對Alarm網(wǎng)進(jìn)行分析.如圖4所示，圖中的{X23，X22，X29，X21}和{X23，X22，X29，X1}均構(gòu)成了圖2(a)中的結(jié)構(gòu).節(jié)點(diǎn)X23的父子節(jié)點(diǎn)集合PC={X24，X25，X2，X22}，它的馬爾可夫毯 MB={X24，X25，X2，X22，X27，X29}.當(dāng) Alarm 網(wǎng)中數(shù)據(jù)集大小為5 000時，利用MMPC算法得到的父子節(jié)點(diǎn)集合PC'={X24，X25，X2，X22，X1，X21}.比實(shí)際網(wǎng)絡(luò)中節(jié)點(diǎn)X23的父子節(jié)點(diǎn)集合多余了X1、X21這2個節(jié)點(diǎn).MMMB算法中的候選馬爾可夫毯為 CMB={X24，X25，X2，X22，X1，X21，X4，X15，X19，X26，X27，X29}，最終返回的馬爾可夫毯為 MB'={X24，X25，X2，X22，X27，X29，X1，X21}，比節(jié)點(diǎn)X23真實(shí)的馬爾可夫毯多余了X1和X21這2個節(jié)點(diǎn)，即錯誤的父子節(jié)點(diǎn)會保留在馬爾可夫毯內(nèi).

圖4 Alarm網(wǎng)局部，陰影節(jié)點(diǎn)組成圖2(a)的結(jié)構(gòu)Fig.4 Local Alarm network，shadow nodes form the structure in Fig.2(a)

RA-MMMB算法對候選馬爾可夫毯CMB與節(jié)點(diǎn)X23進(jìn)行逐步后向回歸，依次去掉了節(jié)點(diǎn)X15、X19、X1、X21、X4、X26，逐步后向回歸去掉變量的過程如表1所示(左列的變量對應(yīng)的概率值p為該變量被去掉時在回歸方程中回歸系數(shù)為零的概率，其余的變量對應(yīng)該變量保留在最終回歸方程中的p值).其中最先被去掉的2個節(jié)點(diǎn)X15和X19是網(wǎng)絡(luò)中節(jié)點(diǎn)X21的2個子節(jié)點(diǎn)，而節(jié)點(diǎn)X21是被錯誤引入到節(jié)點(diǎn)X23的父子節(jié)點(diǎn)集合的節(jié)點(diǎn).接著被去掉的節(jié)點(diǎn)X1，X21，X4是節(jié)點(diǎn)X23的子節(jié)點(diǎn)X22的子節(jié)點(diǎn)，節(jié)點(diǎn)X26是節(jié)點(diǎn)X23的父節(jié)點(diǎn)X25的父節(jié)點(diǎn)，剩余變量集為{X24，X25，X2，X22，X27，X29}.對回歸分析后的剩余節(jié)點(diǎn)進(jìn)行條件獨(dú)立測試，發(fā)現(xiàn)這些均不是節(jié)點(diǎn)X23的兄弟節(jié)點(diǎn)，RA-MMMB算法返回的最終的馬爾可夫毯MB″={X24，X25，X2，X22，X27，X29}，跟真實(shí)的馬爾可夫毯相同，去掉了MMPC算法引入的錯誤的變量X1和X2.

表1 節(jié)點(diǎn)X23和候選馬爾可夫毯CMB逐步后向回歸過程(顯著性水平α=0.05)Table 1 The process of stepwise backward regression between node X23and CMB(significance level α=0.05)

以Alarm網(wǎng)中節(jié)點(diǎn)X19為例，如圖5所示，{X29，X21，X19，X18，X28}構(gòu)成了圖 3 中的結(jié)構(gòu).節(jié)點(diǎn)X19的父子節(jié)點(diǎn)集 PC={X20，X21，X18}，它的馬爾可夫毯MB={X20，X21，X18，X28}.當(dāng) Alarm 網(wǎng)中數(shù)據(jù)為5 000時，利用MMPC算法得到的父子節(jié)點(diǎn)集合PC'={X22，X21，X18}，與實(shí)際的父子節(jié)點(diǎn)集合相同.MMMB算法中的候選馬爾可夫毯 CMB={X20，X21，X18，X14，X15，X22，X28，X29}，最終返回的馬爾可夫毯為 MB'={X20，X21，X18，X28，X29，}，比真實(shí)的馬爾可夫毯多了節(jié)點(diǎn)X29，即引入了節(jié)點(diǎn)X19的錯誤的配偶節(jié)點(diǎn)X29.

圖5 Alarm網(wǎng)局部，陰影節(jié)點(diǎn)組成圖3的結(jié)構(gòu)Fig.5 Local Alarm network，shadow nodes form the structure in Fig.3

RA-MMMB算法對候選馬爾可夫毯與節(jié)點(diǎn)X19進(jìn)行逐步后向回歸，依次去掉了節(jié)點(diǎn)X14、X22、X29，逐步后向回歸去掉變量的過程如表2所示(左列變量含義同表1).其中節(jié)點(diǎn)X14為節(jié)點(diǎn)X19的子節(jié)點(diǎn)X18的子節(jié)點(diǎn)，節(jié)點(diǎn)X22和X29為節(jié)點(diǎn)X19的父節(jié)點(diǎn)X21的父節(jié)點(diǎn)，剩余的變量集合為{X20，X21，X18，X15，X28}.RA-MMMB算法接著通過條件獨(dú)立性測試去掉了節(jié)點(diǎn)X15，而節(jié)點(diǎn)X15為網(wǎng)絡(luò)中節(jié)點(diǎn)X19的兄弟節(jié)點(diǎn)，他們有共同的父節(jié)點(diǎn)X21.得到最終的 MB″={X20，X21，X18，X28}，與實(shí)際馬爾可夫毯相同，去掉了MMMB算法中引入的錯誤的變量X29.

表2 節(jié)點(diǎn)X19和候選馬爾可夫毯CMB逐步后向回歸過程(顯著性水平α=0.05)Table 2 The process of stepwise backward regression between node X19and CMB(significance level α =0.05)

對Insurance網(wǎng)和Alarm網(wǎng)里各數(shù)據(jù)集的每個節(jié)點(diǎn)分別使用 MMMB算法、PCMB算法和 RAMMMB算法學(xué)習(xí)它的馬爾可夫毯，并計算出這3種算法對各網(wǎng)絡(luò)的平均查準(zhǔn)率、平均查全率和平均歐氏距離，進(jìn)行比較.如圖6所示.

圖6 Insurance和Alarm數(shù)據(jù)集各算法的查準(zhǔn)率、查全率和歐氏距離Fig.6 Precision，recall and Euclidean distance of each algorithm in Insurance and Alarm network dataset

從圖6可以看出，對不同的數(shù)據(jù)集，RA-MMMB算法輸出結(jié)果的查準(zhǔn)率、查全率均比MMMB算法的結(jié)果高，相應(yīng)的歐氏距離均比MMMB算法小，表明了該算法要優(yōu)于MMMB算法;而與PCMB算法相比，雖然RA-MMMB算法查全率偏低，但查準(zhǔn)率較高，綜合評價指標(biāo)歐氏距離小，體現(xiàn)了在整體上要優(yōu)于PCMB算法.同時可以看出，數(shù)據(jù)集中樣本數(shù)目越多，歐氏距離就越小，算法的準(zhǔn)確率就越高.

5 結(jié)束語

基于邏輯回歸分析的馬爾可夫毯學(xué)習(xí)算法，對MMMB算法里存在錯誤的父子節(jié)點(diǎn)和配偶節(jié)點(diǎn)的問題進(jìn)行了分析，然后對MMMB算法中的候選馬爾可夫毯與目標(biāo)變量進(jìn)行逐步后向回歸，去掉了錯誤節(jié)點(diǎn)和其他與目標(biāo)變量相關(guān)性弱的節(jié)點(diǎn)，然后進(jìn)行條件獨(dú)立測試去掉兄弟節(jié)點(diǎn)，減少了條件獨(dú)立測試的次數(shù)，提高了學(xué)習(xí)馬爾可夫毯的精度.針對本算法的查全率較PCMB算法低的缺點(diǎn)，需要進(jìn)一步的工作去改進(jìn).

［1］MARGARITIS D，THRUN S.Bayesian network induction via local neighborhoods［C］//Advances in Neural Information Processing Systems.Denver，Colorado，USA，1999:505-511.

［2］TSAMARDINOS I，ALIFERIS C F，STATNIKOV A.Algorithms for large scale Markov blanket discovery［C］//Proceedings of the Sixteenth International Florida Artificial Intelligence Research Society Conference.St Augustine，F(xiàn)lorida，USA，2003:376-380.

［3］FU Shunkai，Desmarais M C.Markov blanket based feature selection:a review of past decade［C］//Proceedings of the World Congress on Engineering London，UK，2010:22-27.

［4］TSAMARDINOS I，ALIFERIS C F，STATNIKOV A.Time and sample efficient discovery of Markov blankets and direct causal relations［C］//Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Washington，DC，USA，2003:673-678.

［5］PE~NA J M，NILSSON R，BJRKEGREN J，et al.Towards scalable and data efficient learning of Markov boundaries［J］.International Journal of Approximate Reasoning，2007，45(2):211-232.

［6］ALIFERIS C F，TSAMARDINOS I，STATNIKOV A.HITON:a novel Markov blanket algorithm for optimal variable selection［C］//Proceedings of the 2003 American Medical Informatics Association Annual Symposium.Washington，DC，USA，2003:21-25.

［7］TSAMARDINOS I，BROWN L E，ALIFERIS C F.Themax-min hill-climbing Bayesian network structure learning algorithm［J］.Machine Learning，2006，65:31-78.

［8］孟曉東，袁道華，施惠豐.基于回歸模型的數(shù)據(jù)挖掘研究［J］.計算機(jī)與現(xiàn)代化，2010，173(1):26-28.MENG Xiaodong，YUAN Daohua，SHI Huifeng.Research on regress-base system on data mining［J］.Computer and Modernization，2010，173(1):26-28.

［9］SINGH S，KUBICA J，LARSEN S，et al.Parallel large scale feature selection for logistic regression［C］//SIAM International Conference on Data Mining(SDM).Sparks，Nevada，USA，2009:1171-1182.

［10］施朝健，張明銘.Logistic回歸模型分析［J］.計算機(jī)輔助工程，2005，14(3):74-78.SHI Chaojian，ZHANG Mingming.Analysis of logistic regression models［J］.Computer Aided Engineering，2005，14(3):74-78.

［11］高曉光，趙歡歡，任佳.基于蟻群優(yōu)化的貝葉斯網(wǎng)絡(luò)學(xué)習(xí)［J］.系統(tǒng)工程與電子技術(shù)，2010，32(7):1509-1512.

［12］SPIRTES P，GLYMOUR C，SCHEINES R.Causation，prediction，and search［M］.2nd ed.Cambrdge，USA:The MIT Press，2000:23-28.GAO Xiaoguang，ZHAO Huanhuan，REN Jia.Bayesian network learning on algorithm based on ant colony optimization［J］.Systems Engineering and Electronics，2010，32(7):1509-1512.