邏輯回歸分析的馬爾可夫毯學習算法

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

(合肥工業大學計算機與信息學院，安徽 合肥 230009)

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

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

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

1 貝葉斯網絡及相關定義

設V代表一組離散隨機變量，用〈G，θ〉來表示貝葉斯網絡，其中有向無環圖G中的節點對應V中的變量，是指G中每個節點X在給定它的父節點Pa(X)下的條件概率分布p(X|Pa(X)).貝葉斯網絡的聯合概率分布可表示如下:

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

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

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

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

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

2 MMMB算法

2.1 MMMB 算法描述

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

1)MMPC算法.

2)MMMB算法描述:

2.2 MMMB算法存在的問題

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

1)CPC添加節點.

①CPC=?，A與T鄰接，Dep(A;T|?)的值最大，節點A首先進入到CPC;

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

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

2)CPC={A，C}去掉錯誤節點.

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

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

圖2 MMPC算法引入錯誤節點CFig.2 Incorrect node C included in CPC returned MMMB算法尋找配偶節點的依據為:對X∈

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

圖3 MMMB算法引入T的錯誤的配偶節點AFig.3 Incorrect spouse node A included in MMMB

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

3 RA-MMMB算法

3.1 根據相關性將節點分類

根據貝葉斯網絡中各節點與目標節點T的相關性關系，把MMMB算法中候選馬爾可夫毯CMD=PC(T)∪C∈PC(T)MMPC(C){T}中的節點分為4類:

1)T的父節點和T的子節點:這類節點與T有很強的相關性;

2)T的父節點的父節點和T的子節點的子節點:由于貝葉斯網絡已存在T的父節點和T的子節點，故這類節點與T的相關性較弱;

3)T的兄弟節點(與T共同有一個父節點)和T的配偶節點:這類節點和T有共同的原因或結果，當給定T的父節點或T的子節點時，與T的相關性較強;

4)MMPC算法引入的錯誤節點的父子節點中上述3類以外的節點，這類節點與T的相關性最弱.

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

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

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

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

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

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

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

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

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

由于CMB中的第4)類節點與T的相關性最弱，所以會在逐步后向回歸中最先被去掉;因為回歸方程中含有T的父節點和子節點，接下來與T的相關性較弱的第2)類節點會作為回歸方程中的次要變量從CMB中被去掉;第3)類節點由于T的父節點和T的子節點的存在，與T的相關性較強，所以會保留在CMB中;而第1)類節點與T的相關性最強，也包含在CMB中.

3.3 去除兄弟節點

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

3.4RA-MMMB 算法描述

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

RA-MMMB算法:

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

4 實驗分析與算法比較

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

4.1 評價標準

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

為了對上述2個標準進行綜合評價，定義兩者之間的歐氏距離為

式中:d表明算法準確率，d越小，表明算法準確率越高.

4.2 分析與比較

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

圖4 Alarm網局部，陰影節點組成圖2(a)的結構Fig.4 Local Alarm network，shadow nodes form the structure in Fig.2(a)

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

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

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

圖5 Alarm網局部，陰影節點組成圖3的結構Fig.5 Local Alarm network，shadow nodes form the structure in Fig.3

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

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

對Insurance網和Alarm網里各數據集的每個節點分別使用 MMMB算法、PCMB算法和 RAMMMB算法學習它的馬爾可夫毯，并計算出這3種算法對各網絡的平均查準率、平均查全率和平均歐氏距離，進行比較.如圖6所示.

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

從圖6可以看出，對不同的數據集，RA-MMMB算法輸出結果的查準率、查全率均比MMMB算法的結果高，相應的歐氏距離均比MMMB算法小，表明了該算法要優于MMMB算法;而與PCMB算法相比，雖然RA-MMMB算法查全率偏低，但查準率較高，綜合評價指標歐氏距離小，體現了在整體上要優于PCMB算法.同時可以看出，數據集中樣本數目越多，歐氏距離就越小，算法的準確率就越高.

5 結束語

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

［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，Florida，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］孟曉東，袁道華，施惠豐.基于回歸模型的數據挖掘研究［J］.計算機與現代化，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］.計算機輔助工程，2005，14(3):74-78.SHI Chaojian，ZHANG Mingming.Analysis of logistic regression models［J］.Computer Aided Engineering，2005，14(3):74-78.

［11］高曉光，趙歡歡，任佳.基于蟻群優化的貝葉斯網絡學習［J］.系統工程與電子技術，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.