基于信息熵的Markov網絡結構學習算法研究
加入技術交流群
由定理4可知，經這一步刪減，在不考慮邊的方向情況下，PG圖是一個最小I-圖，即所要構造的Markov網。其算法如下：
(1)輸入樣本數據集D，節點集U，閾值ε1本文引用地址：http://www.104case.com/article/157711.htm
(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，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等用基于統計打分搜索算法得到如圖1所示的兩種最有可能的結構。
基于圖1所示的算法計算結果如下：取閾值為0．007和0．001，經計算得到圖2a的結構，根據專家知識可知：性別、社會經濟狀態是不會有父節點的，所以對X1=>X4和X2=>X3兩種依賴關系可修訂為X1=>X4和X2=>X3，由此得到圖2b所示的結構。因此，可以看出，圖1a和圖2b是一樣的。根據Markov的理論和特征，得到Markov網結構，如圖3所示。
6 結束語
通過認真研究信息熵理論知識得到基于信息熵的Markov網算法，在一定程度上簡化了Bayesian網推理過程，提高了推理效率，對知識的不確定推理研究具有參考價值。
評論