貝葉斯網(wǎng)絡(luò)構(gòu)建算法

1、3.1貝葉斯網(wǎng)絡(luò)構(gòu)建算法算法3.1：構(gòu)建完全連接圖算法輸入：樣本數(shù)據(jù)D； 一組n個變量V=V, V2，Vn變量。輸出：一個完全連接圖S算法：1、連接任意兩個節(jié)點，即連接邊L.j=1，i力。2、為任一節(jié)點Vi鄰接點集合賦值，Bj= VVi o算法3.2：構(gòu)建最小無向圖算法輸入：樣本數(shù)據(jù)。；一組n個變量V=V，V2，Vn變量。及算法3.1中得到的鄰接 點集耳，連接邊集匕先驗知識：節(jié)點Vi,Vj間連接邊是否存在變量說明：L為連接邊，ILI=n(n 1)/2為連接邊的數(shù)量，Bj表示變量Vi的直接鄰近集，IBJ 表示與變量與相鄰的變量數(shù)。(Vj 1 VIZ)表示Vi和V.在Z條件下條件獨立，設(shè)a (X，

2、Y)表示 變量X和Y的最小d-分離集。輸出：最小無向圖S1、根據(jù)先驗知識，如果乂和Vj不相連接，則Lj=o .2、對任一相連接邊，艮吼豐0，根據(jù)式(3-12)計算互信息I(VfVj)(3-12)I(X, Y) = D(p3, y) I P(x)p(y) = Elog p(X,Y)P (x, y)p( X) p(Y)if I(Vi,Vj) 網(wǎng)，令Z= Bi else Z= B. 為后面敘述方便，這里先假謝J IB.I5、逐一計算L的一階條件互信息I(V,V. IZ)，Z產(chǎn)YJ, Y e乙ij1 j 11 K Kif I(V.,Vj IZ1) I(V.,V. IZ1) then I.= I(V.,

3、V. IZ1)6、逐一計算L的二階條件互信息I(V,V IZ), Z=ZY Y ,1Ji J 12 k, l其中Yk ,Yl g乙k豐lif I(Vi,VJ IZ2) I(*,Vj IZ2) then IiJ= I(V.,VJ IZ2)7、 逐一計算L的n-1階條件互信息I(V,V IZ )，Z 1=ZY, Y g ZiJ i j n-1，n-1 i k， kif I(Vi,VJ I Zn-1) I(*,Vj I Zn-1) then IiJ= I(Vi,VJ I Zn-1)8、逐一計算匕的n階條件互信息【(七的IZni)，Zni=Biif I(Vi,VJ I Zni) I(*,Vj I Zn

4、i) then Iij= I(Vi,Vj I Zni)9、逐一計算匕的n階條件互信息【(Vj IZnj)，Znj=Bjif I(Vi,Vj I Znj) I(V.,V. I Znj) then I.= I(V.,V. I Znj)goto 410、對于2中得到的不相連接邊Lq=0if |Bi| 叫，令d Bi else dBj 為L賦最小d分離集算法3.3：基于規(guī)則一的最小無向圖邊定向算法輸入：樣本數(shù)據(jù)D； 一組n個變量V=Vl，V2,，Vn變量。及算法3.2中得到的Bi ,匕 a ( Vi, 丫)集 dij專家知識：Dij=1，表示表示變量對*,的)之間存在有向連接的TVjO1、根據(jù)先驗知識

5、，if Dij=1 then Vt V.2、對于X=Vi, Y= % Z= Vk，(i,j,k互不相等)窮舉出所有三元組變量故,丫, Z)/根據(jù)算法3.1，3.2的結(jié)果可以檢測三元組的合法性，大大減少三元組數(shù)目3、if三元組集不為空，依次選取一組三元組X,Y, Z) else go to endif (Lxz =1 , Lz =1 , R=0) and Zwdx thenDxF Dyk=1, xW-Y7三元組(X,Y, Z標(biāo)志為已處理else goto 3算法3.4：基于規(guī)則二的最小無向圖邊定向算法輸入：樣本數(shù)據(jù)D； 一組n個變量V=Vl，V2，Vn變量。算法3.2中得到的LijO算法3.3中

6、得到未處理的三元組集及丫, Z及及連接邊集Dq1、Do While三元組集不為空依次選取一組三元組X,Y, Z)if Dxz =1 ,七=1 , %=0 thenDxz=1, Dzy=1, Xf Zf YLoop算法3.5：基于規(guī)則三的最小無向圖邊定向算法輸入：樣本數(shù)據(jù)D； 一組n個變量V=Vl，V2，Vn變量。算法3.2中得到的LijO算法3.4中得到未處理的二元組集X,Y)及連接邊集Dq1、列舉所有未定向的連接邊集二元組X,Y)，即Lxy=1 and %更12、while二元組不為空then依次選取一二元組;X,Y)if (Xg Y) thenX Y, Dxy=1算法3.6：基于MAP-M

7、DL全局最優(yōu)搜索網(wǎng)絡(luò)結(jié)構(gòu)S的算法輸入：樣本數(shù)據(jù)D； 一組n個變量V=V, V2，Vn變量。算法3.2中得到的LijO算法3.4中得到連接邊集Dq及相應(yīng)邊的方向輸出：所有連接邊的方使弓即求最佳網(wǎng)絡(luò)結(jié)構(gòu)S1、列舉變量Dij豐1的所有未確定邊的所有可能連接方向的組合O2、if O不為空then依次從集合q中選取一組有向邊集構(gòu)成結(jié)構(gòu)Sielse結(jié)束。3、根據(jù)Dij及q，始化結(jié)構(gòu)斗各節(jié)點的Vi的父代集二4、if當(dāng)前結(jié)構(gòu)Si存在回路then goto 2else L(D, Si)=-log2 P(DISi)+L(Si)/對結(jié)構(gòu)Si;由式(3-24)計算L(D, Si)goto 25、選取Min(L(D,

8、)及其所對應(yīng)的結(jié)構(gòu)Si，令SM= Si，LM= L(D, Si)算法3.7：尋找遺失邊優(yōu)化算法偽代碼本算法尋找在前面算法中丟失的有向連接m，保證了網(wǎng)絡(luò)結(jié)構(gòu)的完備性。輸入：樣本數(shù)據(jù)D； 一組n個變量V=Vl，V2，Vn變量。算法3.2中得到的LijO算法3.6中得到有向連接邊鈕弓及最小LM，節(jié)點的Vi的父代集氣輸出：尋找遺失邊Dq，即求最佳網(wǎng)絡(luò)結(jié)構(gòu)Sm1、while算法3.2中得到的不相連接邊集匕=0)不為空2、依次從連接邊集中取得一條邊勺，設(shè)X=Vi,Y=Vj3、結(jié)構(gòu)SM增加一條邊X-Y或Y-X，生成新的結(jié)構(gòu)Sm4、更新節(jié)點X或Y的父代集5、if結(jié)構(gòu)Sm不存在回路thenL(D, Sm)=-log2 P(DISm)+L(Sm)對結(jié)構(gòu) Sm 由式(3-24)計算 L(D, Sm)If LMLm then LM=Lm ,SM=Sm,Dij=1更 新父節(jié)點集 算法3.8：刪除冗余邊優(yōu)化算法偽代碼本算法刪除在前面算法中得到的有向連揍ij中的冗余，保證了網(wǎng)絡(luò)結(jié)構(gòu)的簡潔性、準(zhǔn)確性。輸入：樣本數(shù)據(jù)D； 一組n個變量V=Vl，V2，Vn變量。算法3.2中得到的LijO算法3.7中得到有向連接邊鈕弓及最小LM，節(jié)點的Vi的父代集.輸出：刪除遺失邊Dq，即求最佳網(wǎng)絡(luò)結(jié)構(gòu)Sm1、while有向連接邊集。弓不為空2、依次取得有向連