k2算法描述
说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。
K2算法： K2算法用贪婪搜索处理模型选择问题：先定义一种评价网络结构优劣的评分函数，再从一个网络开始，根据事先确定的最大父节点数目和节点次序，选择分值最高的节点作为该节点的父节点。K2 算法使用后验概率作为评分函数： p(D|Bs)score(i,pai) i1n其中score(i,pai)K2算法伪代码： [j1qi(ij)(ijNij)k1ri(ijkNijk)(ijk)] k2(X,,,) 输入：X{X1,X2,...,Xn}---------------------一组变量 -----------------------一个变量顺序(设它与变量下标一致) -----------------------变量父亲节点个数的上界 -----------------------一组完整的数据 输出：一个贝叶斯网 1.由节点X1，X2，...,Xn组成的无边图 2. for j=1 to n 3. j; 4.VoldCH(Xj,j|); 5. while(true) 6. 7. iarg maxCH(Xj,j{Xi}|) 1iij
VnewCH(Xj,j{Xi}|)
8. if(Vnew>Vold and |j|<) 9.
VoldVnew;
10.
ji{Xi};
11. 在中加边XiXj； 12. else 13. break; 14. end if 15.end while 16.end for
17.估计的参数 18.return (,);
K2的出发点是一个包含所有节点、但却没有边的无向图。在搜索过程中，K2按顺序逐个考察中的变量，确定其父亲节点，然后添加相应的边。对某一变量Xj，假设K2已经找到了它的一些父亲节点j。如果|j|<，即Xj的父亲节点个数还未达到上界，那么就要继续为它寻找父节点，具体做法是首先考虑哪些在中排在Xj之前，但却还不是Xj的父亲节点的变量，从这些变量中选出Xi，它使得新家族CH评分VnewCH(Xj,j{Xi}|)达到最大；然后将Vnew与旧家族评分比较：如果Vnew>Vold，则把Xi添加为Xj的父节点；否则停止为Xj寻找父亲节点。
本文来源：https://www.wddqw.com/doc/9bed2e71f46527d3240ce003.html