贝叶斯网络(三)--完整数据集下的结构学习

上一个章节中，讲到了贝叶斯网络常用的评分函数，本节主要讲下搜索的算法，搭配上搜索算法，对于贝叶斯网络的结构学习就完整啦。
贝叶斯网络的结构学习问题是一个NP-hard问题，所以实际上计算中并不是对所有的结构分别计算并且评分的，而是采用搜索算法按照某种评分在可能的拓扑结构中进行搜索来获取结构。最基本的搜索算法是启发式的局部搜索算法，主要是K2搜索，Hill-climbing算法、随机重复爬山算法、禁忌搜索、模拟退火以及遗传算法，主要分为以下几个步骤

计算每个节点之间互信息，建立完整无向图
如果节点对不是d分割的话，把这个点对加入到边集合
检查边集中每个点对，如果两个节点是d分割的，则移走这条边

K2算法

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

K2伪代码

$X=X_{1},..,X_{n}$ 一组变量
$\rho$ 变量的顺序
N 变量父节点的最大个数
D 完整数据集合

$\xi \leftarrow$ 由父节点X组成的无向图
for j=1 in n
$\pi_{j} \leftarrow \phi$
$V_{old} \leftarrow BDe(X_{j},\pi_{j}|D)$
while(True)
$i \leftarrow arg max BDe(<X_{j},\pi_{j} \cup \{X_{i}\}>|D)$
$V_{new} \leftarrow BDe(<X_{j},\pi_{j} \cup \{X_{i}\}>|D)$
If $V_{new} >V_{old}$ and $|\pi_{j}| < N$
$V_{old} >V_{new}$
$\pi_{j} \leftarrow \pi_{i} \cup \{X_{i}\}$
在D中加入边 $X_{i} \rightarrow X_{j}$
else
break
end If
end While
end for
估计 $\xi$ 的参数 $\theta$
return ( $\xi$ , $\theta$ )

K2算法的出发点是一个包含所有节点，但是没有边的无向图。搜索过程中，K2算法按顺序逐个考察 $\rho$ 中的变量，确定其父节点，然后添加相应的边。对某一个变量 $X_{j}$ ，假设K2已经找到它的一些父节点 $\pi_{j}$ , 如果 $|\pi_{j}| <N$ ，也就是 $X_{j}$ 的父节点个数还未达到上限，那么就继续找其他父节点。否则停止搜索

Hill-climbing搜索算法

Hill-climbing搜索算法同样也是为了找到评分最高的结构，初始的结构是一个无边的模型，搜索的每一步，就在当前的模型上做局部的修改，获得一系列的候选模型，然后计算每个模型的评分，如果评分大就替换之前的模型。
Hill-climbing搜索算法的对模型的修改主要体现在加边、减边、和转边。但是不能在网络中构成环。接下来可以一起看看伪代码。

X,一组变量
D 关于X的完整数据
f 评分函数
$\xi_{0}$ 初始的贝叶斯结构