基于信息熵的Markov網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法研究

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

5 實例分析
此例來自對華盛頓高級中學(xué)131名高年級學(xué)生的升學(xué)計劃調(diào)查，每個學(xué)生用下列變量及其相應(yīng)的狀態(tài)來描述：性別(X1)：男、女；社會經(jīng)濟狀態(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)的順序進行輪換，依此類推，得到完全統(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)濟狀態(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)推理過程，提高了推理效率，對知識的不確定推理研究具有參考價值。