k2算法描述

【#文档大全网# 导语】以下是®文档大全网的小编为您整理的《k2算法描述》，欢迎阅读！

K2算法：

K2算法用贪婪搜索处理模型选择问题：先定义一种评价网络结构优劣的评分函数，再从一个网络开始，根据事先确定的最大父节点数目和节点次序，选择分值最高的节点作为该节点的父节点。K2 算法使用后验概率作为评分函数：

p(D|Bs)score(i,pai)

i1

n

其中score(i,pai)K2算法伪代码：

[

j1

qi

(ij)(ijNij

)

k1

ri

(ijkNijk)(ijk)

]

k2(X,,,)

输入：X{X1,X2,...,Xn}---------------------一组变量

-----------------------一个变量顺序(设它与变量下标一致)

-----------------------变量父亲节点个数的上界 -----------------------一组完整的数据

输出：一个贝叶斯网

1.由节点X1，X2，...,Xn组成的无边图 2. for j=1 to n 3.

j;

4.VoldCH(Xj,j|); 5. while(true) 6. 7.



iarg maxCH(Xj,j{Xi}|)

1iij

VnewCH(Xj,j{Xi}|)

8. if(Vnew>Vold and |j|<) 9.







VoldVnew;

10.

ji{Xi};

11. 在中加边XiXj； 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评分VnewCH(Xj,j{Xi}|)达到最大；然后将Vnew与旧家族评分比较：如果Vnew>Vold，则把Xi添加为Xj的父节点；否则停止为Xj寻找父亲节点。

本文来源：https://www.wddqxz.cn/9bed2e71f46527d3240ce003.html