1 引言
    日常生活中人們常需要處理不確定信息，例如：預(yù)測明天是否會下雨，病人是否得了某種疾病。Bayesian網(wǎng)是進(jìn)行不確定性推理的有力工具，被廣泛應(yīng)用于人工智能、專家系統(tǒng)、數(shù)據(jù)挖掘等領(lǐng)域，是當(dāng)前研究的熱點。利用Bayesian網(wǎng)可以推理不確定性知識，從而達(dá)到較好效果。
    Markov網(wǎng)是類似于Bayesian網(wǎng)的另一種進(jìn)行不確定性推理的有力工具。Markov網(wǎng)是一個無向圖，構(gòu)造時無需發(fā)現(xiàn)邊的方向，要比構(gòu)造Bayesian網(wǎng)容易得多。首先構(gòu)造Markov網(wǎng)，再求出與之等價的Bayesian網(wǎng)。本文提出一種基于信息熵的方法構(gòu)造Markov網(wǎng)，給出一個有效的基于信息獨立測試的Markov網(wǎng)的構(gòu)造算法，該算法是一種基于依賴分析的算法。在測試樣本中的條件獨立時，利用信息論中驗證信息獨立的一個重要結(jié)論，從而大大提高效率。為衡量構(gòu)造的Markov網(wǎng)的好壞，引入I-圖、D-圖和P-圖的概念。

2 依賴模型與MarkOV網(wǎng)
    知識可以用一組條件獨立和條件概率表示，Markov網(wǎng)(無向圖)用于表示條件獨立。下面主要討論如何用Markov網(wǎng)表示一個依賴模型M(一組條件獨立的集合)以及如何衡量Markov網(wǎng)的好壞(引入I-圖、D-圖和最小P-圖)。
    定義1：依賴模型M定義為一組條件獨立的集合，設(shè)X，Y，Z是全集U的3個不相交的子集，M={I(X，Z，y)}。其中的I(X，Z，y)表示在給定Z的條件下，X獨立于Y，即：p(X|Y，Z)=p(X|Z)和p(Y|X，Z)=p(Y|Z)。
    定理1：依賴模型M中的I(X，Z，y)滿足以下4個性質(zhì)，設(shè)X，Y，Z是全集U的3個不相交的子集，
    (1)對稱性：I(X，Z，Y)XXXXXXI(Y，Z，X)；
    (2)分解律：I(X，Z，Y∪W)=》I(X，Z，Y)＆I(X，Z，W)；
    (3)弱歸并律：I(X，Z，Y∪W)→I(X，Z，∪W，Y)；
    (4)減縮律：I(X，Z，y)&I(X，Z，∪Y，W)→I(X，Z，Y∪W)若聯(lián)合概率函數(shù)p嚴(yán)格為正，Vx，p(x)>0，則相交律成立。
    (5)相交律：I(X，Z，∪W，Y)＆I(X，Z，∪Y，W)→I(X，Z，Y∪W)給定一個依賴模型M，利用無向圖中節(jié)點分割的概念表示依賴模型中的條件獨立。
    定義2：在有向無環(huán)圖G中，X，Y，Z是U上3個不相交的子集，刪去節(jié)點集Z及其相應(yīng)的邊，使節(jié)點集X，Y之間再無邊相連，稱Z將X，Y分割開，記為<X|Z|Y>G。用<X|Z|Y>G表示依賴模型中條件獨立信息I(X，Z，Y)，得到一個依賴模型的圖形化表示方式，繼續(xù)用I-圖、P-圖、D-圖的概念衡量依賴模型M中的所有條件獨立信息和最優(yōu)Markov網(wǎng)。
    定義3：設(shè)M為依賴模型，I(X，y，Z)M表示依賴模型M所蘊含的依賴關(guān)系(條件獨立)I(X，y，Z)。無向圖G=(V，E)為M的I-圖、D-圖、P-圖，定義如下：
    (1)G是M的I-圖(獨立圖)，當(dāng)<X|Z|Y>G=<X|Z|Y>M。
    (2)G是M的D-圖(依賴圖)，當(dāng)<X|Z|Y>M=><X|Z|Y>G。
    (3)G是M的P-圖(理想圖)，當(dāng)<X|Z|Y>M<=<<X|Z|Y>G。
    由上述定義可知，I-圖不一定包含依賴模型M所蘊含的所有依賴關(guān)系，但I(xiàn)-圖中蘊含的依賴關(guān)系M中一定蘊含；D-圖恰好相反，D-圖包含依賴模型M所蘊含的所有依賴關(guān)系，但D-圖中蘊含的依賴關(guān)系M中不一定蘊含；P-圖是最理想的情況，P-圖與M形成一一對應(yīng)關(guān)系?？請D(不含任何邊的無向圖)是一個平凡的D-圖，而完全圖(包含所有邊的無向圖)是一個平凡的I-圖。
    定義4：設(shè)一個無向圖G是M的一個I-圖，若刪除G中任何一條邊后，使得G不再是M的I-圖，則稱G為M的最小I-圖。顯然，最小I-圖能夠最多地表示依賴模型M中的依賴關(guān)系。
    定理2：滿足對稱性、分解性、相交律和弱歸并律的依賴模型M,從完全圖中刪除所有條件獨立性成立的邊，則產(chǎn)生一個唯一的最小I-圖。

3 信息熵概述
    Markov網(wǎng)結(jié)構(gòu)用來消除不確定性的東西，信息的載體稱為消息。含有信息的消息集合稱為信源。信源的信息熵，就是信源提供整個信息的總體度量。所以如果消息消除的不確定性越大，信源的信息熵就越小，信息間的相互依賴性就越大；反之，信息間的相互獨立性就越大。具體概念作如下定義：
    定義5：設(shè)屬性X具有r種可能狀態(tài)，Pi為狀態(tài)Xi時的概率，則信息熵可定義為：

   
式中，C為大于0的常數(shù)。
    定義6：設(shè)X，Y為兩個相互關(guān)聯(lián)的隨機(jī)變量，稱：為X，Y的聯(lián)合熵。H(X|Y)=H(X，i=1j=1Y)-H(Y)為給定Y時X的條件熵。條件熵H(X|Y)表示在觀測到Y(jié)的結(jié)果后，對X保留的不確定性度量。
    定義7：設(shè)X，Y，Z為3個不相交的變量集，稱：的互信息。
    為給定Z的條件下，X和Y的互信息(條件互信息)。
    定理3：互信息I(X，Y)和I(X，Y|Z)具有如下性質(zhì)：
    (1)對稱性，即I(X，Y)=I(Y，X|Z)和I(X，Y|Z)=I(Y，X|Z)；
    (2)非負(fù)性，即I(X，Y)≥0和I(X，Y｜Z)≥0。而且，當(dāng)且僅當(dāng)X和Y條件獨立時有I(X，Y)=0。同理，當(dāng)且僅當(dāng)在給定條件Z，X和Y條件獨立時I(X，Y｜Z)=0。

4 基于信息熵的Markov網(wǎng)構(gòu)造算法
    給定一樣本集(n個屬性的一張二維表)，先對系統(tǒng)中N個變量構(gòu)建一個完全無向圖氏，然后利用信息獨立測試?yán)碚撚行h剪PG圖，以得到所求的Markov網(wǎng)。
    首先給出這個算法所需要的一些假設(shè)：給定的樣本數(shù)據(jù)集D是完整的；所有的變量取值均為離散性，若取值連續(xù)可先進(jìn)行離散化。
    第1步：構(gòu)造完全有向圖
    定義8：設(shè)一個系統(tǒng)含有N個變量｛X1，X2，……，Xn}，完全有向圖PG={<Xi,Xj>|，其中i,j=1，2，…，n且i≠j，<Xi，Xj>表示Xi與Xj有因果關(guān)系Xi→Xj}。由此定義可知，PG是一個I-圖。
    第2步：有效刪剪PG圖
    從定理3的性質(zhì)2可得到一個判斷X,Y是否條件獨立的算法：當(dāng)給出一個概率分布P(x)時，可通過判斷I(X，Y|Z)=0代替I(X，Y|Z)，從而PG圖中的X→Y和Y→X邊可刪除；否則。在給定條件Z的情況下，X和Y互相依賴。然而在實際計算中并沒有一個真正的概率分布P(x)，只有一個基于樣本數(shù)據(jù)集D而計算的一個經(jīng)驗概率分布PD(x)近似估計P(x)，計算的I(X，Y｜Z)只是基于PD(x)上的I(X，Y｜Z)近似值，所以其值總大于0。為此，判斷條件獨立方法可描述為：
    定理4：設(shè)X，Y，Z為全集U上3個不相交的子集，基于樣本數(shù)據(jù)集D上概率分布PD(x)，如果有：I(X，Y｜Z)<ε，則判定給定Z，X與Y條件獨立；否則給定Z，X與Y是條件依賴的。其中ε為一個閾值，通常取一個很小的正數(shù)。
    由定理4可知，經(jīng)這一步刪減，在不考慮邊的方向情況下，PG圖是一個最小I-圖，即所要構(gòu)造的Markov網(wǎng)。其算法如下：
    (1)輸入樣本數(shù)據(jù)集D，節(jié)點集U，閾值ε1

    (4)輸出V
    由以上算法可知：整個算法是計算復(fù)雜度為O(／N2)的條件獨立性CI(Conditional Independence)測試。

5 實例分析
    此例來自對華盛頓高級中學(xué)131名高年級學(xué)生的升學(xué)計劃調(diào)查，每個學(xué)生用下列變量及其相應(yīng)的狀態(tài)來描述：性別(X1)：男、女；社會經(jīng)濟(jì)狀態(tài)(X2)：低、中下、中上、高：智商(X3)：低、中下、中上、高；家長的鼓勵(X4)：低、高；升學(xué)計劃(X5)：是、否。樣本數(shù)據(jù)：下面的數(shù)據(jù)表示對5個變量取值的某種組合統(tǒng)計所得到的人數(shù)，例如：第一個數(shù)據(jù)4表示對(X1=男，X2=低，X3=低，X4=低，X5=是)這種組合所統(tǒng)計出的人數(shù)。變量依次按從右到左的順序輪換，狀態(tài)則按照上述所列各變量狀態(tài)的順序進(jìn)行輪換，依此類推，得到完全統(tǒng)計數(shù)據(jù)如下：4，349，13，64，9，207，33，72，12，126，38，54，10，67，49，43，2，232，27，84，7，201，64，95，12，115，93，92，17，79，119，59，8，166，47，91，6，120，74，110，17，92，148，100，6，42，198，73，4，48，39，57，5，47，123，90，9，41，224，65，8，17，414，54，5，454，9，44，5，312，14，47，8，216，56，35，13，96，28，24，11，285，29，61，19，236，47，88，12，164，62，85，15，113，72，50，7，163，36，72，13，193，75，90，12，174，91，100，20，8l，142，77，6，50，36，58，5，70，110，76，12，48，230，81，13，49，360，98Heckerman等用基于統(tǒng)計打分搜索算法得到如圖1所示的兩種最有可能的結(jié)構(gòu)。

    基于圖1所示的算法計算結(jié)果如下：取閾值為0．007和0．001，經(jīng)計算得到圖2a的結(jié)構(gòu)，根據(jù)專家知識可知：性別、社會經(jīng)濟(jì)狀態(tài)是不會有父節(jié)點的，所以對X1<=>X4和X2<=>X3兩種依賴關(guān)系可修訂為X1=>X4和X2=>X3，由此得到圖2b所示的結(jié)構(gòu)。因此，可以看出，圖1a和圖2b是一樣的。根據(jù)Markov的理論和特征，得到Markov網(wǎng)結(jié)構(gòu)，如圖3所示。

6 結(jié)束語
    通過認(rèn)真研究信息熵理論知識得到基于信息熵的Markov網(wǎng)算法，在一定程度上簡化了Bayesian網(wǎng)推理過程，提高了推理效率，對知識的不確定推理研究具有參考價值。