基于信息熵的Markov网络结构学习算法研究

作者：时间：2009-12-23来源：网络收藏

由定理4可知，经这一步删减，在不考虑边的方向情况下，PG图是一个最小I-图，即所要构造的Markov网。其算法如下：
(1)输入样本数据集D，节点集U，阈值ε1

本文引用地址：http://www.eepw.com.cn/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所示。