1 引言

日常生活中人們常需要處理不確定信息,，例如：預(yù)測明天是否會下雨，病人是否得了某種疾病,。Bayesian網(wǎng)是進(jìn)行不確定性推理的有力工具,，被廣泛應(yīng)用于人工智能、專家系統(tǒng),、數(shù)據(jù)挖掘等領(lǐng)域,，是當(dāng)前研究的熱點(diǎn)。利用Bayesian網(wǎng)可以推理不確定性知識,，從而達(dá)到較好效果,。

Markov網(wǎng)是類似于Bayesian網(wǎng)的另一種進(jìn)行不確定性推理的有力工具。Markov網(wǎng)是一個(gè)無向圖,，構(gòu)造時(shí)無需發(fā)現(xiàn)邊的方向,，要比構(gòu)造Bayesian網(wǎng)容易得多。首先構(gòu)造Markov網(wǎng),，再求出與之等價(jià)的Bayesian網(wǎng),。本文提出一種基于信息熵的方法構(gòu)造Markov網(wǎng)，給出一個(gè)有效的基于信息獨(dú)立測試的Markov網(wǎng)的構(gòu)造算法,，該算法是一種基于依賴分析的算法,。在測試樣本中的條件獨(dú)立時(shí)，利用信息論中驗(yàn)證信息獨(dú)立的一個(gè)重要結(jié)論,，從而大大提高效率,。為衡量構(gòu)造的Markov網(wǎng)的好壞，引入I-圖,、D-圖和P-圖的概念,。

2 依賴模型與MarkOV網(wǎng)

知識可以用一組條件獨(dú)立和條件概率表示，Markov網(wǎng)(無向圖)用于表示條件獨(dú)立,。下面主要討論如何用Markov網(wǎng)表示一個(gè)依賴模型M(一組條件獨(dú)立的集合)以及如何衡量Markov網(wǎng)的好壞(引入I-圖、D-圖和最小P-圖),。

定義1：依賴模型M定義為一組條件獨(dú)立的集合,，設(shè)X，Y,，Z是全集U的3個(gè)不相交的子集,，M={I(X,，Z，y)},。其中的I(X,，Z，y)表示在給定Z的條件下,，X獨(dú)立于Y,，即：p(X|Y，Z)=p(X|Z)和p(Y|X,，Z)=p(Y|Z),。

定理1：依賴模型M中的I(X，Z,，y)滿足以下4個(gè)性質(zhì),，設(shè)X，Y,，Z是全集U的3個(gè)不相交的子集,，
(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)給定一個(gè)依賴模型M，利用無向圖中節(jié)點(diǎn)分割的概念表示依賴模型中的條件獨(dú)立,。

定義2：在有向無環(huán)圖G中,，X，Y,，Z是U上3個(gè)不相交的子集,，刪去節(jié)點(diǎn)集Z及其相應(yīng)的邊，使節(jié)點(diǎn)集X,，Y之間再無邊相連,，稱Z將X，Y分割開,，記為G,。用G表示依賴模型中條件獨(dú)立信息I(X，Z,，Y),，得到一個(gè)依賴模型的圖形化表示方式，繼續(xù)用I-圖,、P-圖,、D-圖的概念衡量依賴模型M中的所有條件獨(dú)立信息和最優(yōu)Markov網(wǎng)。

定義3：設(shè)M為依賴模型,，I(X,，y，Z)M表示依賴模型M所蘊(yùn)含的依賴關(guān)系(條件獨(dú)立)I(X,，y,，Z)。無向圖G=(V,，E)為M的I-圖,、D-圖、P-圖,，定義如下：
(1)G是M的I-圖(獨(dú)立圖),，當(dāng)G=M。
(2)G是M的D-圖(依賴圖),，當(dāng)M=>G,。
(3)G是M的P-圖(理想圖)，當(dāng)M<=<G,。

由上述定義可知,，I-圖不一定包含依賴模型M所蘊(yùn)含的所有依賴關(guān)系，但I(xiàn)-圖中蘊(yùn)含的依賴關(guān)系M中一定蘊(yùn)含,；D-圖恰好相反,，D-圖包含依賴模型M所蘊(yùn)含的所有依賴關(guān)系，但D-圖中蘊(yùn)含的依賴關(guān)系M中不一定蘊(yùn)含,；P-圖是最理想的情況,，P-圖與M形成一一對應(yīng)關(guān)系?？請D(不含任何邊的無向圖)是一個(gè)平凡的D-圖,，而完全圖(包含所有邊的無向圖)是一個(gè)平凡的I-圖。

定義4：設(shè)一個(gè)無向圖G是M的一個(gè)I-圖,，若刪除G中任何一條邊后,，使得G不再是M的I-圖，則稱G為M的最小I-圖,。顯然,，最小I-圖能夠最多地表示依賴模型M中的依賴關(guān)系。

定理2：滿足對稱性,、分解性,、相交律和弱歸并律的依賴模型M,從完全圖中刪除所有條件獨(dú)立性成立的邊，則產(chǎn)生一個(gè)唯一的最小I-圖,。

3 信息熵概述

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


式中,，C為大于0的常數(shù),。

定義6：設(shè)X，Y為兩個(gè)相互關(guān)聯(lián)的隨機(jī)變量,，稱：為X,，Y的聯(lián)合熵。H(X|Y)=H(X,，i=1j=1Y)-H(Y)為給定Y時(shí)X的條件熵,。條件熵H(X|Y)表示在觀測到Y(jié)的結(jié)果后，對X保留的不確定性度量,。
定義7：設(shè)X,，Y，Z為3個(gè)不相交的變量集,，稱：的互信息,。
為給定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條件獨(dú)立時(shí)有I(X，Y)=0,。同理,，當(dāng)且僅當(dāng)在給定條件Z，X和Y條件獨(dú)立時(shí)I(X,，Y｜Z)=0,。

4 基于信息熵的Markov網(wǎng)構(gòu)造算法

給定一樣本集(n個(gè)屬性的一張二維表),，先對系統(tǒng)中N個(gè)變量構(gòu)建一個(gè)完全無向圖氏，然后利用信息獨(dú)立測試?yán)碚撚行h剪PG圖,，以得到所求的Markov網(wǎng),。
首先給出這個(gè)算法所需要的一些假設(shè)：給定的樣本數(shù)據(jù)集D是完整的；所有的變量取值均為離散性,，若取值連續(xù)可先進(jìn)行離散化,。
第1步：構(gòu)造完全有向圖

定義8：設(shè)一個(gè)系統(tǒng)含有N個(gè)變量｛X1，X2,，……，Xn},，完全有向圖PG={|,，其中i,j=1，2,，…,，n且i≠j，表示Xi與Xj有因果關(guān)系Xi→Xj},。由此定義可知，PG是一個(gè)I-圖,。

　　第2步：有效刪剪PG圖

　　從定理3的性質(zhì)2可得到一個(gè)判斷X,Y是否條件獨(dú)立的算法：當(dāng)給出一個(gè)概率分布P(x)時(shí),，可通過判斷I(X，Y|Z)=0代替I(X,，Y|Z),，從而PG圖中的X→Y和Y→X邊可刪除；否則,。在給定條件Z的情況下,，X和Y互相依賴。然而在實(shí)際計(jì)算中并沒有一個(gè)真正的概率分布P(x),，只有一個(gè)基于樣本數(shù)據(jù)集D而計(jì)算的一個(gè)經(jīng)驗(yàn)概率分布PD(x)近似估計(jì)P(x),，計(jì)算的I(X，Y｜Z)只是基于PD(x)上的I(X,，Y｜Z)近似值,，所以其值總大于0。為此,，判斷條件獨(dú)立方法可描述為：

　　定理4：設(shè)X,，Y，Z為全集U上3個(gè)不相交的子集,，基于樣本數(shù)據(jù)集D上概率分布PD(x),，如果有：I(X,，Y｜Z)<ε，則判定給定Z,，X與Y條件獨(dú)立,；否則給定Z，X與Y是條件依賴的,。其中ε為一個(gè)閾值,，通常取一個(gè)很小的正數(shù)。

　　由定理4可知,，經(jīng)這一步刪減,，在不考慮邊的方向情況下，PG圖是一個(gè)最小I-圖,，即所要構(gòu)造的Markov網(wǎng),。其算法如下：

　　(1)輸入樣本數(shù)據(jù)集D，節(jié)點(diǎn)集U,，閾值ε1

　　(4)輸出V

　　由以上算法可知：整個(gè)算法是計(jì)算復(fù)雜度為O(／N2)的條件獨(dú)立性CI(Conditional Independence)測試,。

5 實(shí)例分析

　　此例來自對華盛頓高級中學(xué)131名高年級學(xué)生的升學(xué)計(jì)劃調(diào)查，每個(gè)學(xué)生用下列變量及其相應(yīng)的狀態(tài)來描述：性別(X1)：男,、女,；社會經(jīng)濟(jì)狀態(tài)(X2)：低、中下,、中上,、高：智商(X3)：低、中下,、中上,、高；家長的鼓勵(lì)(X4)：低,、高,；升學(xué)計(jì)劃(X5)：是、否,。樣本數(shù)據(jù)：下面的數(shù)據(jù)表示對5個(gè)變量取值的某種組合統(tǒng)計(jì)所得到的人數(shù),，例如：第一個(gè)數(shù)據(jù)4表示對(X1=男，X2=低,，X3=低,，X4=低，X5=是)這種組合所統(tǒng)計(jì)出的人數(shù),。變量依次按從右到左的順序輪換,，狀態(tài)則按照上述所列各變量狀態(tài)的順序進(jìn)行輪換，依此類推,，得到完全統(tǒng)計(jì)數(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,，16*7,，91，6,，120,，74，110,，17,，92,，148，100,，*2,，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,，23*7,，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)計(jì)打分搜索算法得到如圖1所示的兩種最有可能的結(jié)構(gòu),。

　　基于圖1所示的算法計(jì)算結(jié)果如下：取閾值為0．007和0．001，經(jīng)計(jì)算得到圖2a的結(jié)構(gòu),，根據(jù)專家知識可知：性別,、社會經(jīng)濟(jì)狀態(tài)是不會有父節(jié)點(diǎn)的，所以對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)推理過程,，提高了推理效率,，對知識的不確定推理研究具有參考價(jià)值。