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

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

0 引言

在現(xiàn)實(shí)世界里，確定性事物是相對(duì)的，不確定性事物是絕對(duì)的.各行各業(yè)的飛速發(fā)展，使得我們步入了大數(shù)據(jù)的時(shí)代，這意味著會(huì)有海量的數(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)為一個(gè)有向無環(huán)圖，只有在滿足條件獨(dú)立性并具有概率語義的情況下才能被稱作為一個(gè)概率圖模型.貝葉斯網(wǎng)的概率圖模型是不確定性知識(shí)表示和推理的有效架構(gòu).

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

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

1 基本概念

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

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

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

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

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

(1)

(2)

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

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

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

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

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

(1)V是H的頂點(diǎn)集；

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

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

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

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

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

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

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

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

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

下面給出超貝葉斯圖的鍵的概念，再討論超貝葉斯圖的結(jié)構(gòu)和條件獨(dú)立性的性質(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é)點(diǎn)ai，并且它的雙親pa(ai)={b1，b2，…，bm}，這就意味著超貝葉斯圖的鍵有以下四種類別，如圖1所示.

圖1 超貝葉斯圖的鍵

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

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

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

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

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

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

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

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

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

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

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

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

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

證明：根據(jù)定義5可知在刪除節(jié)點(diǎn)Z后節(jié)點(diǎn)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é)點(diǎn)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é)點(diǎn)集V

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

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

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ǎn)di與其父節(jié)點(diǎn)組成

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的長(zhǎng)度為n，算法在Step 8運(yùn)行結(jié)束最壞的情況下的時(shí)間復(fù)雜度為O(n)，假設(shè)超貝葉斯圖集合的元素?cái)?shù)為m，可知m≤n一定成立，算法在Step 14運(yùn)行結(jié)束時(shí)間復(fù)雜度為O(m)，在Step 17運(yùn)行結(jié)束時(shí)間復(fù)雜度取決于非嵌入式條件獨(dú)立集合的長(zhǎng)度(即有向無環(huán)圖的結(jié)構(gòu))，所以在最壞的情況下時(shí)間復(fù)雜度為O(max(|UCI|)).

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

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

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

超貝葉斯圖的聯(lián)結(jié)樹可以由超貝葉斯圖生成.已知由算法DAG_LI(HD)生成超貝葉斯圖的鍵的集合LI(HD)，用超貝葉斯圖的鍵來分割問題域中隨機(jī)變量集R結(jié)果放入一個(gè)集合中，判斷該集合如果不為空，則把被分割問題域中隨機(jī)變量集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時(shí)需要遍歷整個(gè)超貝葉斯圖的鍵的集合LIs，則它的時(shí)間復(fù)雜度為O(|LIs|)；在Step 4用超貝葉斯圖的鍵來分割問題域中隨機(jī)變量集R時(shí)，時(shí)間復(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}是一個(gè)有超貝葉斯圖的聯(lián)結(jié)樹，定義hi(i=1，2…，n)的祖先集為：

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

(4)

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

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

(5)

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

對(duì)超貝葉斯圖的概率分解為：

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

(6)

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

4 算例分析

例1 圖2是一個(gè)貝葉斯網(wǎng)的經(jīng)典例子，問題域中包含8個(gè)隨機(jī)變量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é)果，因?yàn)闊o論怎么排列組合對(duì)超貝葉斯圖的鍵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對(duì)超貝葉斯圖的聯(lián)結(jié)樹的邊進(jìn)行JPD分解為：

=p(V)p(T|V)

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

圖5 刪除過程

同樣用定理5對(duì)每條邊進(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)

把每條超邊看成一個(gè)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é)合定義了超貝葉斯圖模型，討論了超貝葉斯圖的條件獨(dú)立性性質(zhì)和聯(lián)結(jié)樹的構(gòu)建方法和算法，基于聯(lián)結(jié)樹不僅可以表示復(fù)雜數(shù)據(jù)間的依賴結(jié)構(gòu)，還可進(jìn)行概率化簡(jiǎn).為超貝葉斯圖描述和處理不確定性數(shù)據(jù)問題提供了理論依據(jù).基于超貝葉斯圖的推理、查詢和數(shù)據(jù)分析等問題還有待探討.