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=V\{Vi}o算法3.2：構(gòu)建最小無向圖算法輸入：樣本數(shù)據(jù)。；一組n個變量V={V]，V2，…，Vn}變量。及算法3.1中得到的鄰接點集耳，連接邊集匕先驗知識：節(jié)點Vi,Vj間連接邊是否存在變量說明：L為連接邊，ILI=n(n1)/2為連接邊的數(shù)量，Bj表示變量Vi的直接鄰近集，IBJ表示與變量與相鄰的變量數(shù)。(Vj1V^IZ)表示Vi和V.在Z條件下條件獨立，設(shè)a(X，Y)表示變量X和Y的最小d-分離集。輸出：最小無向圖S1、根據(jù)先驗知識，如果乂和Vj不相連接，則Lj=o.2、對任一相連接邊，艮吼豐0，根據(jù)式(3-12)計算互信息I(VfVj)(3-12)I(X,Y)=D(p3,y)IP(x)p(y))=Elogp(X,Y)P(x,y)p(X)p(Y)」ifI(Vi,Vj)<sthen{Lij=0//Vi和V.不相連接Bi=V\{V.},Bj=V\{V.}〃調(diào)整Vi和Vj鄰接集}elseIij=I(Vi,Vj)//節(jié)點Vi和Vj互信息值(3-12)3、對所有連接邊，，并按^升序排序1'4、如果連接邊集匚弓不為空，那么按序選取連接邊勺,否則goto10ifIBiI>網(wǎng)，令Z=BielseZ=B.〃為后面敘述方便，這里先假謝J>IB.I5、逐一計算L的一階條件互信息I(V,V.IZ)，Z產(chǎn){YJ,Ye乙ij1j11KKifI(V.,VjIZ1)<8then{Lij=0//Vi和Vj關(guān)于Z1條件獨立Bi=V\{Vj},Bj=V\{V.}〃調(diào)整Vi和Vj鄰接集dij=Z1//Lij最小d分離集為Z1goto4}elseifI..>I(V.,V.IZ1)thenI..=I(V.,V.IZ1)6、逐一計算L的二階條件互信息I(V,VIZ),Z=Z\{YY},1JiJ12k,l其中Yk,Ylg乙k豐lifI(Vi,VJIZ2)<sthen{LiJ=0//Vi和V.關(guān)于Z2條件獨立Bi=V\{V.},BJ=V\{V.}〃調(diào)整Vi和V.鄰接集diJ=Z1//LiJ最小d分離集為Z2goto4}elseifIiJ>I(*,VjIZ2)thenIiJ=I(V.,VJIZ2)7、逐一計算L的n-1階條件互信息I(V,VIZ)，Z1=Z\{Y},YgZiJ'ijn-1，n-1ik，kifI(Vi,VJIZn-1)<sthen{LiJ=0//Vi和V.關(guān)于Zn-1條件獨立Bi=V\{V.},BJ=V\{V.}〃調(diào)整Vi和V.鄰接集dij=Zn-1//Lj最小d分離集為Zn-1goto4}elseifIiJ>I(*,VjIZn-1)thenIiJ=I(Vi,VJIZn-1)8、逐一計算匕的n階條件互信息【(七的IZni)，Zni=BiifI(Vi,VJIZni)<sthen{LiJ=0//Vi和Vj關(guān)于Zni條件獨立Bi=V\{V.},Bj=V\{V.}〃調(diào)整Vi和Vj鄰接集dij=Zni//Lij最小d分離集為Znigoto4}elseifIij>I(*,VjIZni)thenIij=I(Vi,VjIZni)9、逐一計算匕的n階條件互信息【("VjIZnj)，Znj=BjifI(Vi,VjIZnj)<sthen{Lij=0//Vi和Vj關(guān)于Znj條件獨立Bi=V\{V.},Bj=V\{V.}〃調(diào)整Vi和Vj鄰接集dij=Znj//Lij最小d分離集為ZnjelseifI..>I(V.,V.IZnj)thenI..=I(V.,V.IZnj)goto410、對于2中得到的不相連接邊Lq=0if|Bi|>叫，令d『Bielsed『Bj〃為L^賦最小d分離集算法3.3：基于規(guī)則一的最小無向圖邊定向算法輸入：樣本數(shù)據(jù)D；一組n個變量V={Vl，V2,…，Vn}變量。及算法3.2中得到的Bi,匕a(Vi,丫)集dij專家知識：Dij=1，表示表示變量對*,的)之間存在有向連接的TVjO1、根據(jù)先驗知識，ifDij=1thenVtV.2、對于X=Vi,Y=%Z=Vk，(i,j,k互不相等)窮舉出所有三元組變量故,丫,Z)//根據(jù)算法3.1，3.2的結(jié)果可以檢測三元組的合法性，大大減少三元組數(shù)目3、if三元組集不為空，依次選取一組三元組X,Y,Z)elsegotoendif(Lxz=1,Lz=1,R=0)andZwdxthenDxFDyk=1,xW-Y7三元組(X,Y,Z標(biāo)志為已處理elsegoto3算法3.4：基于規(guī)則二的最小無向圖邊定向算法輸入：樣本數(shù)據(jù)D；一組n個變量V={Vl，V2，…，Vn}變量。算法3.2中得到的LijO算法3.3中得到未處理的三元組集及丫,Z及及連接邊集Dq1、DoWhile三元組集不為空依次選取一組三元組X,Y,Z)ifDxz=1,七=1,%=0thenDxz=1,Dzy=1,XfZfYLoop算法3.5：基于規(guī)則三的最小無向圖邊定向算法輸入：樣本數(shù)據(jù)D；一組n個變量V={Vl，V2，…，Vn}變量。算法3.2中得到的LijO算法3.4中得到未處理的二元組集X,Y)及連接邊集Dq1、列舉所有未定向的連接邊集二元組X,Y)，即Lxy=1and%更12、while二元組不為空then{依次選取一二元組;X,Y)if(XgY)thenX—Y,Dxy=1}算法3.6：基于MAP-MDL全局最優(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、ifO不為空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存在回路thengoto2elseL(D,Si)=-log2P(DISi)+L(Si)//對結(jié)構(gòu)Si;由式(3-24)計算L(D,Si)goto25、選取Min(L(D,§))及其所對應(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)不為空{(diào)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)=-log2P(DISm)+L(Sm)〃對結(jié)構(gòu)Sm由式(3-24)計算L(D,Sm)IfLM>LmthenLM=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ò)