1 引言
第2步:有效刪剪PG圖
從定理3的性質2可得到一個判斷X,Y是否條件獨立的算法:當給出一個概率分布P(x)時,可通過判斷I(X,Y|Z)=0代替I(X,Y|Z),從而PG圖中的X→Y和Y→X邊可刪除;否則。在給定條件Z的情況下,X和Y互相依賴。然而在實際計算中并沒有一個真正的概率分布P(x),只有一個基于樣本數據集D而計算的一個經驗概率分布PD(x)近似估計P(x),計算的I(X,Y|Z)只是基于PD(x)上的I(X,Y|Z)近似值,所以其值總大于0。為此,判斷條件獨立方法可描述為:
定理4:設X,Y,Z為全集U上3個不相交的子集,基于樣本數據集D上概率分布PD(x),如果有:I(X,Y|Z)<ε,則判定給定Z,X與Y條件獨立;否則給定Z,X與Y是條件依賴的。其中ε為一個閾值,通常取一個很小的正數。
由定理4可知,經這一步刪減,在不考慮邊的方向情況下,PG圖是一個最小I-圖,即所要構造的Markov網。其算法如下:
(1)輸入樣本數據集D,節點集U,閾值ε1
(4)輸出V
由以上算法可知:整個算法是計算復雜度為O(/N2)的條件獨立性CI(Conditional Independence)測試。
5 實例分析
此例來自對華盛頓高級中學131名高年級學生的升學計劃調查,每個學生用下列變量及其相應的狀態來描述:性別(X1):男、女;社會經濟狀態(X2):低、中下、中上、高:智商(X3):低、中下、中上、高;家長的鼓勵(X4):低、高;升學計劃(X5):是、否。樣本數據:下面的數據表示對5個變量取值的某種組合統計所得到的人數,例如:第一個數據4表示對(X1=男,X2=低,X3=低,X4=低,X5=是)這種組合所統計出的人數。變量依次按從右到左的順序輪換,狀態則按照上述所列各變量狀態的順序進行輪換,依此類推,得到完全統計數據如下: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等用基于統計打分搜索算法得到如圖1所示的兩種最有可能的結構。
日常生活中人們常需要處理不確定信息,例如:預測明天是否會下雨,病人是否得了某種疾病。Bayesian網是進行不確定性推理的有力工具,被廣泛應用于人工智能、專家系統、數據挖掘等領域,是當前研究的熱點。利用Bayesian網可以推理不確定性知識,從而達到較好效果。
Markov網是類似于Bayesian網的另一種進行不確定性推理的有力工具。Markov網是一個無向圖,構造時無需發現邊的方向,要比構造Bayesian網容易得多。首先構造Markov網,再求出與之等價的Bayesian網。本文提出一種基于信息熵的方法構造Markov網,給出一個有效的基于信息獨立測試的Markov網的構造算法,該算法是一種基于依賴分析的算法。在測試樣本中的條件獨立時,利用信息論中驗證信息獨立的一個重要結論,從而大大提高效率。為衡量構造的Markov網的好壞,引入I-圖、D-圖和P-圖的概念。
2 依賴模型與MarkOV網
知識可以用一組條件獨立和條件概率表示,Markov網(無向圖)用于表示條件獨立。下面主要討論如何用Markov網表示一個依賴模型M(一組條件獨立的集合)以及如何衡量Markov網的好壞(引入I-圖、D-圖和最小P-圖)。
定義1:依賴模型M定義為一組條件獨立的集合,設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個性質,設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)若聯合概率函數p嚴格為正,Vx,p(x)>0,則相交律成立。
(5)相交律:I(X,Z,∪W,Y)&I(X,Z,∪Y,W)→I(X,Z,Y∪W)給定一個依賴模型M,利用無向圖中節點分割的概念表示依賴模型中的條件獨立。
定義2:在有向無環圖G中,X,Y,Z是U上3個不相交的子集,刪去節點集Z及其相應的邊,使節點集X,Y之間再無邊相連,稱Z將X,Y分割開,記為
定義3:設M為依賴模型,I(X,y,Z)M表示依賴模型M所蘊含的依賴關系(條件獨立)I(X,y,Z)。無向圖G=(V,E)為M的I-圖、D-圖、P-圖,定義如下:
(1)G是M的I-圖(獨立圖),當
(2)G是M的D-圖(依賴圖),當
(3)G是M的P-圖(理想圖),當
由上述定義可知,I-圖不一定包含依賴模型M所蘊含的所有依賴關系,但I-圖中蘊含的依賴關系M中一定蘊含;D-圖恰好相反,D-圖包含依賴模型M所蘊含的所有依賴關系,但D-圖中蘊含的依賴關系M中不一定蘊含;P-圖是最理想的情況,P-圖與M形成一一對應關系。空圖(不含任何邊的無向圖)是一個平凡的D-圖,而完全圖(包含所有邊的無向圖)是一個平凡的I-圖。
定義4:設一個無向圖G是M的一個I-圖,若刪除G中任何一條邊后,使得G不再是M的I-圖,則稱G為M的最小I-圖。顯然,最小I-圖能夠最多地表示依賴模型M中的依賴關系。
定理2:滿足對稱性、分解性、相交律和弱歸并律的依賴模型M,從完全圖中刪除所有條件獨立性成立的邊,則產生一個唯一的最小I-圖。
3 信息熵概述
Markov網結構用來消除不確定性的東西,信息的載體稱為消息。含有信息的消息集合稱為信源。信源的信息熵,就是信源提供整個信息的總體度量。所以如果消息消除的不確定性越大,信源的信息熵就越小,信息間的相互依賴性就越大;反之,信息間的相互獨立性就越大。具體概念作如下定義:
定義5:設屬性X具有r種可能狀態,Pi為狀態Xi時的概率,則信息熵可定義為:
式中,C為大于0的常數。
定義6:設X,Y為兩個相互關聯的隨機變量,稱:為X,Y的聯合熵。H(X|Y)=H(X,i=1j=1Y)-H(Y)為給定Y時X的條件熵。條件熵H(X|Y)表示在觀測到Y的結果后,對X保留的不確定性度量。
定義7:設X,Y,Z為3個不相交的變量集,稱:的互信息。
為給定Z的條件下,X和Y的互信息(條件互信息)。
定理3:互信息I(X,Y)和I(X,Y|Z)具有如下性質:
(1)對稱性,即I(X,Y)=I(Y,X|Z)和I(X,Y|Z)=I(Y,X|Z);
(2)非負性,即I(X,Y)≥0和I(X,Y|Z)≥0。而且,當且僅當X和Y條件獨立時有I(X,Y)=0。同理,當且僅當在給定條件Z,X和Y條件獨立時I(X,Y|Z)=0。
4 基于信息熵的Markov網構造算法
給定一樣本集(n個屬性的一張二維表),先對系統中N個變量構建一個完全無向圖氏,然后利用信息獨立測試理論有效刪剪PG圖,以得到所求的Markov網。
首先給出這個算法所需要的一些假設:給定的樣本數據集D是完整的;所有的變量取值均為離散性,若取值連續可先進行離散化。
第1步:構造完全有向圖
定義8:設一個系統含有N個變量{X1,X2,……,Xn},完全有向圖PG={
基于圖1所示的算法計算結果如下:取閾值為0.007和0.001,經計算得到圖2a的結構,根據專家知識可知:性別、社會經濟狀態是不會有父節點的,所以對X1<=>X4和X2<=>X3兩種依賴關系可修訂為X1=>X4和X2=>X3,由此得到圖2b所示的結構。因此,可以看出,圖1a和圖2b是一樣的。根據Markov的理論和特征,得到Markov網結構,如圖3所示。
6 結束語
通過認真研究信息熵理論知識得到基于信息熵的Markov網算法,在一定程度上簡化了Bayesian網推理過程,提高了推理效率,對知識的不確定推理研究具有參考價值。