超貝葉斯圖模型及其聯(lián)結(jié)樹的構(gòu)建

甘亞男，耿生玲，2*，郝 立

(1.青海師范大學(xué) 計算機學(xué)院，青海 西寧 810008；2.高原科學(xué)與可持續(xù)發(fā)展研究院，青海 西寧 810008)

0 引言

在現(xiàn)實世界里，確定性事物是相對的，不確定性事物是絕對的.各行各業(yè)的飛速發(fā)展，使得我們步入了大數(shù)據(jù)的時代，這意味著會有海量的數(shù)據(jù)持續(xù)輸出，這些數(shù)據(jù)中包含大量的不確定性數(shù)據(jù)[1]，如何處理這些不確定性數(shù)據(jù)?是我們所面臨的嚴(yán)峻問題.基于此引入貝葉斯網(wǎng)絡(luò)來解決，貝葉斯網(wǎng)絡(luò)[2，3]，它是一種概率圖型模型[4，5]，早在1990年P(guān)earl就提出概率圖模型(Probability Graph Model，PGM)，概率圖模型是一種用圖論的方式來表示變量間的概率依賴性的模型[6]，Pearl[7]認(rèn)為一個有向無環(huán)圖，只有在滿足條件獨立性并具有概率語義的情況下才能被稱作為一個概率圖模型.貝葉斯網(wǎng)的概率圖模型是不確定性知識表示和推理的有效架構(gòu).

但由于數(shù)據(jù)規(guī)模的越來越大，關(guān)系越來越復(fù)雜，一般的貝葉斯網(wǎng)就顯得無能為力了，此時超圖理論得天獨厚的優(yōu)勢就顯現(xiàn)出來了.超圖的概念是在圖論的基礎(chǔ)上擴展得來的.圖論是起源于七橋問題，在1736年，瑞典的數(shù)學(xué)家歐拉(Euler)[8，9]把七橋問題轉(zhuǎn)換成圖的形式得以解決，轟動一時，圖論就由此誕生了.超圖[10-14]是有限集的子集系統(tǒng)，是最普遍的離散結(jié)構(gòu)，能夠描述復(fù)雜的關(guān)系和結(jié)構(gòu).由于超圖理論較抽象和復(fù)雜，起初的研究和應(yīng)用進(jìn)展較為緩慢，但近年來在數(shù)學(xué)、計算機科學(xué)、工程技術(shù)、通信、經(jīng)濟學(xué)、電信、物理學(xué)、運行管理、計算生物學(xué)、生物化學(xué)和分子生物學(xué)等各個領(lǐng)域，對超圖理論的研究越來越多，應(yīng)用越來越廣泛.

本文將貝葉斯網(wǎng)與超圖結(jié)合提出一個新模型-超貝葉斯圖模型，用來表示復(fù)雜數(shù)據(jù)間的相關(guān)性以及數(shù)據(jù)間不確定性的表示.分析了超貝葉斯圖的條件獨立性的性質(zhì)，從而給出超貝葉斯圖的聯(lián)結(jié)樹的構(gòu)建方法及算法，基于聯(lián)結(jié)樹不僅可以表示復(fù)雜數(shù)據(jù)間的依賴結(jié)構(gòu)，還可進(jìn)行概率化簡.為超貝葉斯圖描述和處理不確定性數(shù)據(jù)提供了理論依據(jù).經(jīng)過理論證明和實例仿真該超貝葉斯圖是一種有效的不確定性模型.在超貝葉斯網(wǎng)的基礎(chǔ)上定義了超貝葉斯圖與超貝葉斯圖的聯(lián)結(jié)樹.

1 基本概念

定義1[15]一個貝葉斯網(wǎng)是一個二元組S=(G，Θ)，其中

(1)G是有向無環(huán)圖；

(2)Θ={P(Xi|pa(Xi))|1≤i≤n}是量化網(wǎng)絡(luò)的一組變量，表示每個節(jié)點Xi在給定其父節(jié)點集pa(Xi)下的條件概率分布.

定義2[16]設(shè)R為離散變量的有限集，p(R)為聯(lián)合概率分布(jpd)，X、Y、Z是R的三個不相交子集，如果滿足：

p(X|Y，Z)=p(X，Z)或者

(1)

(2)

則稱為X，Y是關(guān)于Z條件獨立(簡稱CI)，記為I(X，Z，Y).

事實上，貝葉斯網(wǎng)絡(luò)是以圖形化的方式表示變量間的依賴關(guān)系和條件獨立關(guān)系.條件獨立關(guān)系根據(jù)覆蓋程度可分為非嵌入式條件獨立和嵌入式條件獨立.即若事件X，Y關(guān)于事件Z條件獨立：

(1)如果R=XYZ，則把I(X，Z，Y)的集合為非嵌入式條件獨立集合(簡稱UCI).

(2)如果XYZ?R，并且不存在另一個I(X′，Z，Y′)，其中X′?X或者Y′?Y，則I(X，Z，Y)的集合為嵌入式條件獨立集合(簡稱ECI).

定義3[11]超圖表示為H=(V，HE)，其中：

(1)V是H的頂點集；

(2)HE={ei≠?|e?D}是H的超邊集.

在實際應(yīng)用中，由于不確定性數(shù)據(jù)規(guī)模的越來越大，關(guān)系越來越復(fù)雜，一般的貝葉斯網(wǎng)就顯得無能為力.本文結(jié)合超圖給出超貝葉斯網(wǎng)，用來表示復(fù)雜的不確定性數(shù)據(jù)依賴關(guān)系.

2 超貝葉斯圖及其聯(lián)結(jié)樹

給定一個有向無環(huán)圖可生成一個超貝葉斯圖.假設(shè)一個有向無環(huán)圖D=(V，E)，節(jié)點集為V={ai|i=1，2，…，n}，邊集為E={ei|i=1，2，…，m}，pa(ai)為節(jié)點ai的父節(jié)點.

定義4 一個超貝葉斯圖定義為HD=(G，Θ)，其中

(1)G=(D，HE={ei=〈ai，pa(ai)〉|i=1，2，…，t，ai∈D})是一個超圖；

(2)Θ={P(ei)}是量化網(wǎng)絡(luò)的一組變量，表示每個超邊ei的條件概率分布.

定理1 一個有向無環(huán)圖，它的超貝葉斯圖是唯一的.

證明：根據(jù)定義4即可得證.

下面給出超貝葉斯圖的鍵的概念，再討論超貝葉斯圖的結(jié)構(gòu)和條件獨立性的性質(zhì).

定義5 令超貝葉斯圖HD=(D，HE)，HE={h1，h2，…，ht}，X，Y?D，若?I(X，Z，Y)都滿足以下條件：

(1)Z?h，其中h∈HE；

(2)I{XZ1，Z2，Y)?UCI(HD)，其中Z=Z1Z2，Z1≠?，Z2≠?.

則稱Z為超貝葉斯圖的鍵.

根據(jù)定義，Z必須是超貝葉斯圖的某條超邊h∈HD的子集.設(shè)節(jié)點ai，并且它的雙親pa(ai)={b1，b2，…，bm}，這就意味著超貝葉斯圖的鍵有以下四種類別，如圖1所示.

圖1 超貝葉斯圖的鍵

(1)Z=ai，節(jié)點ai本身作為超貝葉斯圖的鍵；

(2)Z=pa(ai)，節(jié)點ai的父節(jié)點pa(ai)作為超貝葉斯圖的鍵；

(3)Z=pa′(ai)?pa(ai)，節(jié)點ai的父節(jié)點pa(ai)或父節(jié)點pa(ai)的子集pa′(ai)作為超貝葉斯圖的鍵；

(4)Z=aiYpa′(ai)，節(jié)點ai和其父節(jié)點的子集pa′(ai)一同作為超貝葉斯圖的鍵.

由此可知，超貝葉斯圖的同一個鍵對于不同的超邊可以屬于不同的類別，并且一個超邊可以包含多個超貝葉斯圖的鍵.

由定義4和定義5討論超貝葉斯圖的鍵的獨立集合的性質(zhì).

定理2 設(shè)LI(HD)為超貝葉斯圖HD的鍵的獨立集合，則LI(HD)?UCI(HD).

證明：UCI(HD)表示在超貝葉斯圖上所以滿足條件獨立的集合，LI(HD)表示超貝葉斯圖的鍵，根據(jù)定義5第一個條件Z?h，其中h∈HE，可知Z一定是超貝葉斯圖的一個超邊的子集，而UCI(HD)卻沒做任何限制，則LI(HD)?UCI(HD)，證畢.

定理3 超貝葉斯圖的鍵的獨立集合設(shè)LI(HD)是唯一的.

證明：根據(jù)定義5即可得證.

定理4 對于?I(X，Z，Y)∈LI(HD)，超貝葉斯圖的鍵Z不能被LI(HD)分割.

證明：根據(jù)定義5的第一個條件Z?h，其中h∈HD，可知它的貝葉斯超圖的鍵包含在一條超邊中，這就意味著它永遠(yuǎn)不會被LI(HD)分割，證畢.

性質(zhì)1(對稱性)I(X，Z，Y)=I(Y，Z，X).

證明：根據(jù)定義5可知在刪除節(jié)點Z后節(jié)點X和Y發(fā)生的概率相互不影響，所以I(X，Z，Y)=I(Y，Z，X)成立.

性質(zhì)2(分解性)I(X，Z，YW)可分解為：I(X，Z，Y)和I(X，Z，W).

證明：根據(jù)定義5可知在刪除節(jié)點Z后，把超貝葉斯圖分成X、Y和W三部分，則X、Y和W發(fā)生的概率互不影響，所以I(X，Z，YW)可分解為：I(X，Z，Y)和I(X，Z，W).

基于以上的定義和定理，可以給出超貝葉斯圖的鍵的生成算法.

Algorithm1DAG_LI(HD)

Input：a DAG G //有向無環(huán)圖G

Output：LIs//超貝葉斯圖HD的鍵集LI(HD)

{

Step 1 V=? //有向無環(huán)圖的節(jié)點集V

Step 2 BH=?. //超貝葉斯的邊的集合

Step 3 UCIs=?. //非嵌入式條件獨立集合

Step 4 LIs=?. //超貝葉斯圖的鍵的集合

Step 5 For eachdi∈DAG，i=1，…|DAG|

Step 6 V=V∪di.self；

Step 7 Ifdi.parents≠?

Step 8BH=BH∪Set_Generator(di.self，di.parents)； //BH由節(jié)點di與其父節(jié)點組成

Step 9 For eachBHi∈BH，i=1，…，|BH|

Step 10 subset=Subset_Generator(BHi)； //生成BH集合的子集

Step 11 For eachbhj∈subset，j=1，…，|subset|

Step 12 z=I_Generator(bhj)；

Step 13 If z≠?

Step 14 UCIs=UCIs∪z；

Step 15 For eachucii∈UCIs，i=1，…，|UCIs |

Step 16 IfUCI_Filter(ucii)=true

Step 17 LHIs=LHIs∪ucii；

}

分析DAG_LI(HD)算法可知，假設(shè)全集D的長度為n，算法在Step 8運行結(jié)束最壞的情況下的時間復(fù)雜度為O(n)，假設(shè)超貝葉斯圖集合的元素數(shù)為m，可知m≤n一定成立，算法在Step 14運行結(jié)束時間復(fù)雜度為O(m)，在Step 17運行結(jié)束時間復(fù)雜度取決于非嵌入式條件獨立集合的長度(即有向無環(huán)圖的結(jié)構(gòu))，所以在最壞的情況下時間復(fù)雜度為O(max(|UCI|)).

假設(shè)一個有向無環(huán)圖D=(V，E)，節(jié)點集為V={ai|i=1，2，…，n}，邊集為E={ei|i=1，2，…，m}，它的超貝葉斯圖HD=(G，Θ).為了進(jìn)行超貝葉斯圖的概率計算與化簡，需要給出超貝葉斯圖的聯(lián)結(jié)樹.

(1)T=(D，HE)是一棵根H0的樹，且H0包含超貝葉斯圖的所有節(jié)點，其中D是超貝葉斯圖節(jié)點的集合，HE是超貝葉斯圖邊的集合；

在超貝葉斯圖中又在超貝葉斯圖的聯(lián)結(jié)樹中的邊稱為簡單超邊.在超貝葉斯圖的聯(lián)結(jié)樹中而不在超貝葉斯圖中的邊稱為復(fù)雜超邊.

超貝葉斯圖的聯(lián)結(jié)樹可以由超貝葉斯圖生成.已知由算法DAG_LI(HD)生成超貝葉斯圖的鍵的集合LI(HD)，用超貝葉斯圖的鍵來分割問題域中隨機變量集R結(jié)果放入一個集合中，判斷該集合如果不為空，則把被分割問題域中隨機變量集R的左邊部分和右邊部分的并集存入超貝葉斯圖的聯(lián)結(jié)樹的邊集LH中.下面給出生成超葉斯圖的聯(lián)結(jié)樹的過程.

Algorithm2LI(HD)_LH

Input：LI(HD)and set R

Output：a set H of Line Hypertree

{

Step 1H=?.

Step 2 For eachLIi∈LIs，i=1，…，|LIs|

Step 3 Let result=R_Split_Result(R，LIi)；

Step 4 If result≠?{

Step 5 H=R_Split(result.left)∪R_Split(result.right)；

Step 6 Return H

}

}

分析LI(HD)_LH算法可知，該算法在執(zhí)行到Step 3時需要遍歷整個超貝葉斯圖的鍵的集合LIs，則它的時間復(fù)雜度為O(|LIs|)；在Step 4用超貝葉斯圖的鍵來分割問題域中隨機變量集R時，時間復(fù)雜度最壞為O(|R|)，根據(jù)超定義5超貝葉斯圖的鍵可知|R|>|LIs|一定成立，綜上所述算法LI(HD)_LH在最壞的情況下的復(fù)雜度為O(|R|).

3 超貝葉斯圖的概率分解

根據(jù)算法LI(HD)_LH生成的超貝葉斯圖的聯(lián)結(jié)樹集合以及聯(lián)合概率分布定義的可知：

(3)

其中hi(i=1，2，…，n)表示LI(HD)_LH算法生成的超貝葉斯圖的聯(lián)結(jié)樹集合的元素即超貝葉斯圖的聯(lián)結(jié)樹的每條超邊，zj(j=1，2，…，m)表示DAG_LI(HD)算法生成的超貝葉斯圖的鍵.

定義7 令H={h1，h2，…，hn}是一個有超貝葉斯圖的聯(lián)結(jié)樹，定義hi(i=1，2…，n)的祖先集為：

An(h)={pa(ai)|ai節(jié)點在h中}

(4)

定理5 令貝葉斯網(wǎng)的節(jié)點集合為R，它的相關(guān)有向無環(huán)圖為D.如果R′∈R是一個祖先集或最小祖先集，那么有：

p(R′)=∏a∈R′p(a|pa(a))

(5)

證明：我們構(gòu)造一個有向無環(huán)圖D′，它的節(jié)點構(gòu)成集合R′，有向邊(a，b)在D′中當(dāng)且僅當(dāng)a，b∈R′，因為R是一組(最小)的祖先集，這表明對于任意節(jié)點a∈R′，它的父節(jié)點集pa(a)對原本的有向無環(huán)圖D也是父節(jié)點集，即pa(a)?R′，因此，對于D′的任意節(jié)點a，我們可以將與原始的有向無環(huán)圖D相關(guān)聯(lián)的聯(lián)合概率分布p(a|pa(a))附加到D′中的節(jié)點a上.則可得到p(R′)=∏a∈R′p(a|pa(a))，證畢.

對超貝葉斯圖的概率分解為：

p(hi)=∑An(hi)-hip(An(hi))∏ai∈hip(ai|pa(ai))=∑An(hi)-hi∏x∈An(hi)-hip(x|pa(x))

(6)

以上的累加過程可以可視化為在超貝葉斯圖中依次刪除節(jié)點及其附帶的有向邊的過程.把每條超邊看成一個超貝葉斯圖，遞歸整個過程即可得到最終的分解.

4 算例分析

例1 圖2是一個貝葉斯網(wǎng)的經(jīng)典例子，問題域中包含8個隨機變量V、S、T、L、B、C、X、D.即R={V、S、T、L、B、C、X、D}.

圖2 貝葉斯圖

圖3 超貝葉斯圖

根據(jù)定義4超貝葉斯圖為：

HD={h1=VT，h2=TCL，h3=SL，h4=SB，h5=CX，h6=BCD}

根據(jù)算法DAG_LI(HD)執(zhí)行過程，則生成的超貝葉斯圖的鍵的集合為：

LI(HD)={I{V，T，SLBCDX}，I{VT，C，SLBDX}，I{V，TC，SLBDX}，I{VT，CL，SBDX}，I{V，TL，SBDCX}，I{VT，CD，SLBX}，I{VT，CB，SLDX}}

={I{V，T，SLBCDX}，I{VT，C，SLBDX}，I{VT，CB，SLDX}}

={I{V，T，SLBCDX}，I{VT，C，SLBDX}，I{VTX，C，SLBD}，I{X，C，VTSLBD}，I{VT，CB，

SLDX}，I{VTDX，CB，SL}，I{DX，CB，VTSL}，I{VTD，CB，SLX}，I{VTX，CB，SLD}，

I{D，CB，VTSLX}，I{X，CB，VTSLB}}

={I{V，T，SLBCDX}，I{VT，C，SLBDX}，I{VTX，C，SLBD}，I{X，C，VTSLBD}，I{VTDX，CB，

SL}，I{DX，CB，VTSL}，I{VTD，CB，SLX}，I{D，CB，VTSLX}，I{X，CB，VTSLB}}

其中帶下劃線的表示該元素的位置是不確定的，即I{X，Z，YW}=I{WX，Z，Y}=I{YW，Z，X}=I{Y，Z，WX}，在上述過程中我們只取了一種結(jié)果，因為無論怎么排列組合對超貝葉斯圖的鍵Z是沒有影響的.

R集合為{V、T、S、L、B、C、D、X}，根據(jù)算法LI(HD)_LH分解集合{VTSLBCDX}過程為：

{VTSLBCDX}={VT}{TSLBCDX}={VT}{CT}{CSLBCDX}={VT}{CT}{CX}{CSLBD}

={VT}{CT}{CX}{CBD}{CBSL}={VT}{CTL}{CX}{CBD}{CBSL}

最終得到超貝葉斯圖的聯(lián)結(jié)樹為：

H={h1=VT，h2=TCL，h3=CX，h4=CBD，h5=CBSL}

圖4 超貝葉斯圖的聯(lián)結(jié)樹

超貝葉斯圖的聯(lián)結(jié)樹的聯(lián)合概率分布為：

根據(jù)定理5對超貝葉斯圖的聯(lián)結(jié)樹的邊進(jìn)行JPD分解為：

=p(V)p(T|V)

圖5中R-h1中變量的上標(biāo)表示了它們被刪除的順序.注意R-{V，T}中的所有節(jié)點都不是h1中任何節(jié)點的祖先，依次刪除，如對應(yīng)于上述中的求和序列.還要注意，超邊h1是一個簡單的超邊，c是它所包含的唯一超貝葉斯圖的鍵.刪除R-{V，T}中的所有節(jié)點后，最終結(jié)果如圖5所示：

圖5 刪除過程

同樣用定理5對每條邊進(jìn)行分解得到：

p(h1=VT)=p(V)p(T|V)

p(h2=TCL)=p(C|TL)p(L)p(T)

p(h3=XC)=p(X|C)p(C)

p(h4=CBD)=p(D|CB)p(CB)

把每條超邊看成一個DAG遞歸上述過程得到：

p(VT)=p(V)p(T|V)

p(TCL)=p(C|TL)p(L)p(T)

p(XC)=p(X|C)p(C)

p(CBD)=p(D|CB)p(CB)

p(SB)=p(S)p(B|S)

p(SL)=p(S)p(L|S)

5 結(jié)束語

本文將貝葉斯網(wǎng)與超圖結(jié)合定義了超貝葉斯圖模型，討論了超貝葉斯圖的條件獨立性性質(zhì)和聯(lián)結(jié)樹的構(gòu)建方法和算法，基于聯(lián)結(jié)樹不僅可以表示復(fù)雜數(shù)據(jù)間的依賴結(jié)構(gòu)，還可進(jìn)行概率化簡.為超貝葉斯圖描述和處理不確定性數(shù)據(jù)問題提供了理論依據(jù).基于超貝葉斯圖的推理、查詢和數(shù)據(jù)分析等問題還有待探討.