3.1 贝叶斯网络构建算法算法3.1：构建完全连接图算法输入：样本数据D ；一组n 个变量V={V l ，V 2，…，V n }变量。

输出：一个完全连接图S算法：1、 连接任意两个节点，即连接边 L ij=1，i ≠j 。

2、 为任一节点V i 邻接点集合赋值，B i= V\{V i }。

算法3.2：构建最小无向图算法输入：样本数据D ；一组n 个变量V={V l ，V 2，…，V n }变量。

及算法3.1中得到的邻接点集B i ，连接边集 L ij先验知识：节点V i ,V j 间连接边是否存在变量说明：L 为连接边，|L|=n(n –1)/2为连接边的数量，B i 表示变量V i 的直接邻近集，|B i |表示与变量B i 相邻的变量数。

(V i ⊥V j |Z)表示V i 和V j 在Z 条件下条件独立，设∧(X ，Y)表示变量X 和Y 的最小d-分离集。

输出：最小无向图S1、根据先验知识，如果V i 和V j 不相连接，则L ij =0 .2、对任一相连接边，即L ij ≠0，根据式（3-12）计算互信息I （V i ,V j ）),(Y X I =))()(|),((y p x P y x p D =⎥⎦⎤⎢⎣⎡)()(),(log ),(Y p X p Y X p E y x P (3-12) if I （V i ,V j ）ε≤ then{ L ij =0 //V i 和V j 不相连接B i= V\{V j }, B j= V\{V i } //调整V i 和V j 邻接集}else I ij = I （V i ,V j ） //节点V i 和V j 互信息值3、对所有连接边，并按I ij 升序排序4、如果连接边集L ij 不为空，那么按序选取连接边L ij ,否则 goto 10 if |B i |≥ |B j |，令Z= B i else Z= B j //为后面叙述方便，这里先假设|B i |≥ |B j |5、逐一计算L ij 的一阶条件互信息I(V i ,V j |Z 1)，Z 1={Y k }, Y k ∈Z,if I(V i ,V j |Z 1)ε≤ then{ L ij =0 //V i 和V j 关于Z 1条件独立B i= V\{V j }, B j= V\{V i } //调整V i 和V j 邻接集d ij = Z 1 //L ij 最小d 分离集为Z 1goto 4}elseif I ij> I(V i,V j |Z1) then I ij= I(V i,V j |Z1)6、逐一计算L ij的二阶条件互信息I(V i,V j |Z1)，Z2=Z\{Y k, Y l },其中Y k ,Y l∈Z, k≠l if I(V i,V j |Z2)ε≤then{ L ij=0 //V i和V j关于Z2条件独立B i= V\{V j }, B j= V\{V i } //调整V i和V j邻接集d ij= Z1 //L ij最小d分离集为Z2goto 4}elseif I ij> I(V i,V j |Z2) then I ij= I(V i,V j |Z2)7、逐一计算L ij的n-1阶条件互信息I(V i,V j |Z n-1)，Z n-1=Z\{Y k}, Y k∈Zif I(V i,V j | Z n-1)ε≤then{ L ij=0 //V i和V j关于Z n-1条件独立B i= V\{V j }, B j= V\{V i } //调整V i和V j邻接集d ij= Z n-1 //L ij最小d分离集为Z n-1goto 4}elseif I ij> I(V i,V j | Z n-1) then I ij= I(V i,V j | Z n-1)8、逐一计算L ij的n阶条件互信息I(V i,V j |Z ni)，Z ni=B iif I(V i,V j | Z ni)ε≤then{ L ij=0 //V i和V j关于Z ni条件独立B i= V\{V j }, B j= V\{V i } //调整V i和V j邻接集d ij= Z ni //L ij最小d分离集为Z nigoto 4}elseif I ij> I(V i,V j | Z ni) then I ij= I(V i,V j | Z ni)9、逐一计算L ij的n阶条件互信息I(V i,V j |Z nj)，Z nj=B jif I(V i,V j | Z nj)ε≤then{ L ij=0 //V i和V j关于Z nj条件独立B i= V\{V j }, B j= V\{V i } //调整V i和V j邻接集d ij= Z nj //L ij最小d分离集为Z nj}elseif I ij> I(V i,V j | Z nj) then I ij= I(V i,V j | Z nj)goto 410、对于2中得到的不相连接边L ij=0if |B i|≥|B j|，令d ij= B i else d ij= B j //为L ij赋最小d分离集算法3.3：基于规则一的最小无向图边定向算法输入：样本数据D；一组n个变量V={V l，V2，…，V n}变量。

及算法3.2中得到的B i , L ij，∧( V i, V j)集d ij专家知识：D ij=1，表示表示变量对(V i,V j)之间存在有向连接V i→V j。

1、根据先验知识，if D ij=1 then V i→V j2、对于X=V i, Y= V j，Z= V k，（i,j,k互不相等）穷举出所有三元组变量(X,Y, Z)//根据算法3.1，3.2的结果可以检测三元组的合法性，大大减少三元组数目3、if 三元组集不为空，依次选取一组三元组(X,Y, Z) else go to endif (L xz =1 , L yz =1 , L xy=0) and Z∉d xy thenD xz=1, D yk=1, X→Z←Y三元组(X,Y, Z)标志为已处理else goto 3算法3.4：基于规则二的最小无向图边定向算法输入：样本数据D；一组n个变量V={V l，V2，…，V n}变量。

算法3.2中得到的L ij。

算法3.3中得到未处理的三元组集(X,Y, Z)及及连接边集D ij1、Do While 三元组集不为空依次选取一组三元组(X,Y, Z)if D xz =1 , L yz =1 , L xy=0 thenD xz=1, D zy=1, X→Z→YLoop算法3.5：基于规则三的最小无向图边定向算法输入：样本数据D；一组n个变量V={V l，V2，…，V n}变量。

算法3.2中得到的L ij。

算法3.4中得到未处理的二元组集（X,Y）及连接边集D ij1、列举所有未定向的连接边集二元组（X,Y），即L xy=1 and D xy≠12、while 二元组不为空then{依次选取一二元组(X,Y)if (X∈Y) then X→Y, D xy=1}算法3.6：基于MAP-MDL全局最优搜索网络结构S的算法输入：样本数据D；一组n个变量V={V l，V2，…，V n}变量。

算法3.2中得到的L ij。

算法3.4中得到连接边集D ij及相应边的方向输出：所有连接边的方向D ij，即求最佳网络结构S1、列举变量D ij≠1的所有未确定边的所有可能连接方向的组合O2、if O不为空then 依次从集合O i中选取一组有向边集,构成结构S ielse 结束。

Γ3、根据D ij及O i，始化结构S i各节点的V i的父代集i4、if 当前结构S i存在回路then goto 2else L(D, S i)=-log2 P(D|S i)+L(S i) //对结构S i; 由式(3-24)计算L(D, S i)goto 25、选取Min(L(D, S i))及其所对应的结构S i，令S M= S i，L M= L(D, S i)。

算法3.7：寻找遗失边优化算法伪代码本算法寻找在前面算法中丢失的有向连接L m，保证了网络结构的完备性。

输入：样本数据D；一组n个变量V={V l，V2，…，V n}变量。

算法3.2中得到的L ij。

Γ算法3.6中得到有向连接边集D ij及最小L M，节点的V i的父代集i输出：寻找遗失边D ij，即求最佳网络结构S m1、while 算法3.2中得到的不相连接边集(L ij=0) 不为空{2、依次从连接边集中取得一条边L ij，设X=V i,Y=V j3、结构S M增加一条边, X→Y或Y→X,生成新的结构S m4、更新节点X或Y的父代集5、if 结构S m不存在回路thenL(D, S m)=-log2 P(D|S m)+L(S m) //对结构S m由式(3-24)计算L(D, S m)If L M>L m then L M=L m ,S M=S m ,D ij=1,更新父节点集}算法3.8：删除冗余边优化算法伪代码本算法删除在前面算法中得到的有向连接D ij中的冗余，保证了网络结构的简洁性、准确性。

输入：样本数据D；一组n个变量V={V l，V2，…，V n}变量。

算法3.2中得到的L ij。

Γ算法3.7中得到有向连接边集D ij及最小L M，节点的V i的父代集i输出：删除遗失边D ij，即求最佳网络结构S m1、while 有向连接边集D ij不为空{2、依次取得有向连接边集D ij，删除有向连接边D ij，构成新的结构S m3、if S m为有效连接图模型thenL(D, S m)=-log2 P(D|S m)+L(S m) //对结构S m由式(3-24)计算L(D, S m)If L M>L m then L M=L m ,S M=S m ,D ij=0, L ij=0,更新父节点集}。