影響圖的漸進(jìn)式構(gòu)建方法

馬 馮，劉惟一，楊 櫻

MA Feng1,LIU Weiyi2,YANG Ying3

1.云南財(cái)經(jīng)大學(xué) 信息學(xué)院，昆明 650221

2.云南大學(xué) 信息學(xué)院，昆明 650091

3.云南財(cái)經(jīng)大學(xué) 國際工商學(xué)院，昆明 650221

1.School of Computer and Information,Yunnan University of Finance and Economics,Kunming 650221,China

2.School of Information Science and Engineering,Yunnan University,Kunming 650091,China

3.International Business School,Yunnan University of Finance and Economics,Kunming 650221,China

1 引言

影響圖[1]作為一種有效的決策工具得到了人們廣泛的關(guān)注，并在諸多領(lǐng)域[2-7]中應(yīng)用廣泛。然而，由于傳統(tǒng)的影響圖構(gòu)建方法[8]需要專家或領(lǐng)域知識來確定原始數(shù)據(jù)集中變量間的相互關(guān)系，因此如果原始數(shù)據(jù)集增長，那么原有與之對應(yīng)的影響圖可能就不再適用于新的數(shù)據(jù)集了。此時(shí)，如果用傳統(tǒng)的構(gòu)建方法為新數(shù)據(jù)集構(gòu)建影響圖，那么就需要再次引入專家或領(lǐng)域知識來確認(rèn)新環(huán)境下，各個(gè)變量間的關(guān)系如何，并重新構(gòu)建一個(gè)適合新數(shù)據(jù)的影響圖。

事實(shí)上，在大部分的實(shí)際應(yīng)用中，新增長的數(shù)據(jù)集與原始數(shù)據(jù)集相比，大部分的變量變化程度很小。因此，本文針對這種情況，提出了一種影響圖的漸進(jìn)式構(gòu)建方法，即在已知原始數(shù)據(jù)集和與之對應(yīng)的影響圖時(shí)，如果原始數(shù)據(jù)集增長，此方法可以通過調(diào)整現(xiàn)有影響圖的結(jié)構(gòu)和參數(shù)而獲得一個(gè)適用于新數(shù)據(jù)集的新影響圖。

這種方法的主要思想是，首先將與原始數(shù)據(jù)集對應(yīng)的影響圖轉(zhuǎn)換為相應(yīng)的簡化圖[9]，然后對變化后的數(shù)據(jù)集，采用一個(gè)評分函數(shù)來判斷當(dāng)前的簡化圖是否適用于新數(shù)據(jù)。如果仍然適用，則僅需要調(diào)整各個(gè)變量的參數(shù)表即可。否則，需要先找出現(xiàn)有的簡化圖中差異度最大的地方。此處引入一個(gè)節(jié)點(diǎn)影響度的概念，用來判斷各個(gè)節(jié)點(diǎn)對新數(shù)據(jù)的不符合程度。找出現(xiàn)有的簡化圖中影響度最大的節(jié)點(diǎn)，然后依據(jù)新數(shù)據(jù)對其進(jìn)行調(diào)整，再利用評分函數(shù)對調(diào)整后的整個(gè)簡化圖進(jìn)行評分。如果評分的結(jié)果已到達(dá)事先設(shè)定的閾值，則算法結(jié)束，否則，繼續(xù)重復(fù)上述步驟，直至評分結(jié)果達(dá)到閾值為止。最后將獲得的新簡化圖轉(zhuǎn)換為影響圖即可。

本文的主要貢獻(xiàn)可以歸結(jié)為以下兩點(diǎn)：

（1）給定一個(gè)原始的數(shù)據(jù)集合對應(yīng)的影響圖，當(dāng)原始數(shù)據(jù)集增長時(shí)，影響圖的漸進(jìn)式構(gòu)建方法可以在不需要增加專家或領(lǐng)域知識的前提下，構(gòu)建出一個(gè)新的符合要求的新影響圖。

（2）影響圖的漸進(jìn)式構(gòu)建方法在構(gòu)建新的影響圖時(shí)，只需要對原影響圖進(jìn)行局部調(diào)整即可，從而避免了從頭開始重建一個(gè)影響圖的問題。

2 背景知識

影響圖是一種基于不確定性信息表示，用于處理復(fù)雜決策問題的圖模型[1]。它包含兩個(gè)部分：圖結(jié)構(gòu)和參數(shù)表。圖結(jié)構(gòu)表示數(shù)據(jù)集上變量間的依賴和時(shí)序關(guān)系，參數(shù)表體現(xiàn)了變量間的依賴程度。

定義2.1[1]影響圖是一種有向無環(huán)圖，它包含三種類型的節(jié)點(diǎn)：自然節(jié)點(diǎn)，決策節(jié)點(diǎn)和效用節(jié)點(diǎn)。變量間的相互影響關(guān)系，用節(jié)點(diǎn)間的箭頭表示。

貝葉斯網(wǎng)，是一種可以用來表示變量間的相互影響關(guān)系的圖模型。它也可以被看成是一種有向無環(huán)圖，其中的節(jié)點(diǎn)表示隨機(jī)變量，而有向邊則表示變量間的相互關(guān)系。Pearl曾指出，貝葉斯網(wǎng)可以視為僅包含自然節(jié)點(diǎn)的影響圖[10]。

定義2.2對于一個(gè)給定的影響圖G，如果忽略節(jié)點(diǎn)的類型并將所有的節(jié)點(diǎn)都視為自然節(jié)點(diǎn)，那么它就變成了一個(gè)貝葉斯網(wǎng)，并且稱這種圖為影響圖G的簡化圖。

然而貝葉斯網(wǎng)和影響圖之間，還是有差異的，具體可以總結(jié)為以下幾點(diǎn)[9]：

（1）影響圖中的效用節(jié)點(diǎn)，不能有后繼節(jié)點(diǎn)；貝葉斯網(wǎng)中無此限制。

（2）影響圖中決策節(jié)點(diǎn)的順序，必須要和現(xiàn)實(shí)世界中的實(shí)際情況一致。

（3）影響圖中至少有一個(gè)決策節(jié)點(diǎn)和一個(gè)效用節(jié)點(diǎn)，并且決策節(jié)點(diǎn)應(yīng)該是效用節(jié)點(diǎn)的祖先。

（4）影響圖中的所有效用節(jié)點(diǎn)都要有對應(yīng)的決策節(jié)點(diǎn)作為其祖先節(jié)點(diǎn)。

因此，在將影響圖轉(zhuǎn)化為其對應(yīng)的簡化圖，即貝葉斯網(wǎng)時(shí)，或從貝葉斯網(wǎng)將其轉(zhuǎn)換為影響圖時(shí)，均需要遵循上述的幾點(diǎn)規(guī)則。

3 影響圖的漸進(jìn)式構(gòu)建方法

在影響圖的漸進(jìn)式構(gòu)建方法中，有兩個(gè)關(guān)鍵步驟：一個(gè)是構(gòu)建影響圖的圖結(jié)構(gòu)，另一個(gè)是計(jì)算圖中各個(gè)變量的參數(shù)表。對于后一個(gè)步驟，劉惟一已經(jīng)在文獻(xiàn)[9]中給予了詳細(xì)的描述，因此本文在此就不再冗述。本文提出的方法將專注于如何將原有影響圖的結(jié)構(gòu)調(diào)整成適合新數(shù)據(jù)的新結(jié)構(gòu)。

3.1 影響圖的漸進(jìn)式構(gòu)建方法描述

為了便于描述，假設(shè)Do是原始數(shù)據(jù)集，Dn是新數(shù)據(jù)集（原始數(shù)據(jù)增長以后的結(jié)果）。gido是原始數(shù)據(jù)集Do的影響圖，go是 gido的簡化圖。 gidn是新數(shù)據(jù)集Dn的影響圖，gn是 gidn的簡化圖。CH(go|Dn)是用來判斷 go和 Dn之間的相符程度的評分函數(shù)，T表示事先設(shè)定的閾值。如果CH(go|Dn)的值小于T，則表示當(dāng)前的go仍不適用于Dn。在描述具體的方法前，先給出一些相關(guān)和定義和定理，以便能夠更加明確地說明方法執(zhí)行的具體過程。

定義3.1.1如果xi是go的一個(gè)節(jié)點(diǎn)，那么xi的直接前驅(qū)節(jié)點(diǎn)就成為xi的父節(jié)點(diǎn)，記為Pa(xi)。

定理3.1.1如果xi是go的一個(gè)節(jié)點(diǎn)，是xi參數(shù)表中的值集，并且是Pa(xi)參數(shù)表中的值集，那么評分函數(shù)

可以用來表示go和Dn之間的符合程度。

這個(gè)定理是Copper在文獻(xiàn)[11]中給出的，并予以了證明。其中，Γ()是一個(gè)伽馬函數(shù)，當(dāng)n代表正整數(shù)時(shí)，Γ(n)=(n-1)!。Nijk代表Dn中符合并且條件的記錄個(gè)數(shù)。αijk代表等價(jià)樣本的個(gè)數(shù)。

定義3.1.2如果xi是go的一個(gè)節(jié)點(diǎn)，那么xi相對父節(jié)點(diǎn)的條件概率變化程度，Δ(p(xi|Pa(xi)))就稱為節(jié)點(diǎn)xi對Dn的影響度。

定理3.1.2如果U是一個(gè)概率參數(shù)集，ukj∈U表示xi=并且時(shí)的條件概率，那么節(jié)點(diǎn)x對D的影響in度 Δ(p(xi|Pa(xi)))可以寫成這里，“o”和“n”分別代表老的和新的訓(xùn)練數(shù)據(jù)集，并且r是U中概率參數(shù)的個(gè)數(shù)。

綜上所述，影響圖的漸進(jìn)式構(gòu)建方法（Incremental Building Method for Influence Diagram Structure，IBMIDS）的具體過程，可描述如下：

Input：

Do：原始數(shù)據(jù)集

Dn：新數(shù)據(jù)集

gido：原始數(shù)據(jù)的影響圖

T：閾值

Output：

gidn：符合新數(shù)據(jù)集的影響圖

Variables：

go：gido的簡化圖

gt：go的臨時(shí)調(diào)整結(jié)果

gn：gidn的簡化圖

CH(gt|Dn)：評分函數(shù)

xi：gt中的一個(gè)節(jié)點(diǎn)

步驟：

Begin

步驟1將gido轉(zhuǎn)換為與其對應(yīng)的簡化圖go

步驟2

（1）將當(dāng)前的go記為臨時(shí)調(diào)整結(jié)果gt。

（2）判斷當(dāng)前臨時(shí)調(diào)整結(jié)果的評分制CH(gt|Dn)是否能夠大于或等于閾值T。如果不滿足條件，則循環(huán)執(zhí)行下面幾步直至滿足條件為止。

①計(jì)算gt中每個(gè)節(jié)點(diǎn)xi的影響度，并找出影響度值最大的節(jié)點(diǎn)，記為xtag。

②在xtag的馬爾科夫覆蓋范圍內(nèi)，嘗試著對邊進(jìn)行反向，增加或刪除等操作對原圖進(jìn)行調(diào)整，從而將gt變?yōu)橹虚g調(diào)整結(jié)果gt'。

③找出所有臨時(shí)調(diào)整的圖中，能夠使得CH(gt'|Dn)取到最大值的那個(gè)，記為gt'。

④將臨時(shí)調(diào)整結(jié)果gt調(diào)整成上一步找出的中間調(diào)整結(jié)果gt'，并返回（2）的判斷條件。

（3）將（2）中找出的最終 gt記錄為新影響圖的簡化圖gn。

步驟3將新影響圖的簡化圖gn，按照第2部分中提到的方法轉(zhuǎn)換成最終的新影響圖gidn。

End

3.2 影響圖的漸進(jìn)式構(gòu)建方法的有效性

定理3.2.1影響圖的漸進(jìn)式構(gòu)建方法得出的最終結(jié)果gidn是符合新數(shù)據(jù)集Dn的。

證明 根據(jù)第2章中提到的影響圖定義，如果gidn的結(jié)構(gòu)能夠表示Dn中變量間的依賴和時(shí)序關(guān)系，參數(shù)表體現(xiàn)了變量間的依賴程度，那么可以說gidn是符合Dn的。由于在結(jié)構(gòu)上，gidn與gn是等價(jià)的，并且根據(jù)方法執(zhí)行的過程可知，作為一個(gè)貝葉斯網(wǎng)，有CH(gn|Dn)≥T。因此，可以說明，gidn在結(jié)構(gòu)上是符合Dn的。又由于在將gn轉(zhuǎn)換為gidn的過程中，嚴(yán)格地遵守了第2章中提到的幾條規(guī)則，因此可以確保各個(gè)變量在gidn中的時(shí)序關(guān)系與之在Dn中是一致的。獲取各個(gè)變量參數(shù)表方法的有效性已經(jīng)在文獻(xiàn)[9]中被證明過了。因此，本文中提出的影響圖的漸進(jìn)式構(gòu)建方法得出的最終結(jié)果gidn是符合新數(shù)據(jù)集Dn的。

4 實(shí)驗(yàn)和分析

4.1 實(shí)驗(yàn)

為了便于分析實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)選取了兩個(gè)經(jīng)典的數(shù)據(jù)集Hepar II[13]和Alarm[14]?，F(xiàn)先以Hepar II為例，說明具體的實(shí)驗(yàn)過程。實(shí)驗(yàn)中，選取其原數(shù)據(jù)集中的部分變量進(jìn)行實(shí)驗(yàn)，并將前100條記錄作為Do，構(gòu)建出的相應(yīng)影響圖為gido。

將Hepar II中的全部數(shù)據(jù)視為Dn，閾值T設(shè)定為0.95。首先，將 gido轉(zhuǎn)換為 go，并得出CH(go|Dn)=0.83。由于CH(go|Dn)＜T，因此下一步就是要找出影響度最大的節(jié)點(diǎn)。通過計(jì)算得知，是“Hepatic steatosis”這個(gè)節(jié)點(diǎn)。經(jīng)過計(jì)算后得知，在“Hepatic steatosis”的各種調(diào)整方法中，刪除“Hepatic steatosis”到“PBC”的邊可以使得評分函數(shù)的值達(dá)到當(dāng)前的最大值0.86。由于此時(shí)仍不滿足事先設(shè)定的閾值要求，因此需要重復(fù)上述步驟，直至找到符合條件的圖為止。最后，得到了一個(gè)合適的gn，使得CH(gn|Dn)=0.97。再將gn轉(zhuǎn)換為gidn，如圖1所示。

圖1 IBMIDS構(gòu)造出的Hepar II影響圖

同理，可以用IBMIDS方法構(gòu)建出Alarm數(shù)據(jù)集的影響圖，如圖2所示。

4.2 分析

文獻(xiàn)[13]中已經(jīng)給出了用傳統(tǒng)方法基于Hepar II數(shù)據(jù)集構(gòu)建的影響圖，如圖3所示。文獻(xiàn)[14]中已經(jīng)給出了用傳統(tǒng)方法基于Alarm數(shù)據(jù)集構(gòu)建的影響圖，如圖4所示?？梢钥闯觯瑘D1與圖3相比，圖2與圖4相比，兩者均是等價(jià)的。因此，可以表明影響圖的漸進(jìn)式構(gòu)建方法對于這兩個(gè)經(jīng)典的數(shù)據(jù)集都是有效的。

由于該方法的最終結(jié)果是由貝葉斯網(wǎng)轉(zhuǎn)換而來的，但是對于一個(gè)給定的數(shù)據(jù)集，其有效的貝葉斯網(wǎng)結(jié)構(gòu)并不唯一。因此，有時(shí)候影響圖的漸進(jìn)式構(gòu)建方法得出的結(jié)果，并不一定與傳統(tǒng)方法構(gòu)建出的影響圖在結(jié)構(gòu)上完全一致，但這并不是說明該影響圖是無效的。根據(jù)之前的討論可知，它只是一個(gè)有效，但表現(xiàn)形式不同的影響圖。

5 結(jié)束語

本文提出了一種影響圖的漸進(jìn)式構(gòu)建方法。對于一個(gè)給定的數(shù)據(jù)集和與之對應(yīng)的影響圖，如果原數(shù)據(jù)集增長，那么該方法可以通過調(diào)整原影響圖而得到一個(gè)適用于新數(shù)據(jù)集的新影響圖。與傳統(tǒng)方法相比，它可以有效減少影響圖在構(gòu)建過程中對專家或領(lǐng)域知識的依賴，避免了遇到新數(shù)據(jù)集時(shí)，需要重新構(gòu)建影響圖的情況。文中對該方法的有效性在理論上進(jìn)行了證明，并用Hepar II數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)驗(yàn)證。

圖2 IBMIDS構(gòu)造出的Alarm影響圖

圖3 用傳統(tǒng)方法構(gòu)建出的Hepar II影響圖

圖4 用傳統(tǒng)方法構(gòu)建出的Alarm影響圖

在經(jīng)過大量的實(shí)驗(yàn)后發(fā)現(xiàn)，如果新數(shù)據(jù)集與原始數(shù)據(jù)集相比，大部分的變量在其分布情況上都發(fā)生了重大的變化，那么這種方法的效率就會受到很大的影響。因?yàn)榇藭r(shí)每個(gè)節(jié)點(diǎn)都會耗費(fèi)很多時(shí)間在與之相關(guān)的邊調(diào)整上，以便于找到合適的新結(jié)構(gòu)。如何改進(jìn)這個(gè)問題，將會是下一步工作的重點(diǎn)。通過研究發(fā)現(xiàn)，現(xiàn)實(shí)應(yīng)用中的大部分情況，其新數(shù)據(jù)集與原始數(shù)據(jù)集相比，都屬于僅有小部分的變量在分布情況上有較大改變，其余大部分的變量變化很小的情況。因此，本文提出的方法在大部分的實(shí)際應(yīng)用中都可以得到較好的結(jié)果。

[1]Howard R A，Matheson J E.Influence diagram[J].Decision Analysis，2005（3）：127-143.

[2]Pauker S G，Wong J B.The influence of influence diagrams in medicine[J].Decision Analysis，2005，2：238-244.

[3]Meyer J，Phillips M H，Cho1 P S，et al.Application of influence diagrams to prostate intensity-modulated radiation therapy plan selection[J].Physics in Medicine and Biology，2004，49：1637-1653.

[4]Fernández del Pozo J A，Bielza C，Gómez M.A list-based compact representation for large decision tables management[J].European Journal of Operational Research，2005，160：638-662.

[5]Bielza C，F(xiàn)ernández del Pozo J A，Lucas P.Explaining clinical decisions by extracting regularity patterns[J].Decision Support Systems，2008，44：397-408.

[6]Shachter R D.Efficient value of information computation[C]//Proceedings of the 15th Annual Conference on Uncertainty in Artificial Intelligence（UAI-99）.San Francisco，CA：Morgan Kaufmann，1999：594-602.

[7]Liao W H，Ji Q.Efficient non-myopic value-of-information computation for influence diagrams[J].International Journal of Approximate Reasoning，2008，49（2）：436-450.

[8]Chung T Y，Kim J K，Kim S H.Building an influence diagram in a knowledge-based decision system[J].Expert Systems with Applications，1992，4（1）：33-44.

[9]劉惟一，李維華，岳昆.智能數(shù)據(jù)分析[M].北京：科學(xué)出版社，2007：244-256.

[10]Pearl J.Probabilistic reasoning in intelligent systems：networks of plausible inference[M].California：Morgen Daufmann Publishers，1998：116-131.

[11]Cooper G，Herskovits E.A Bayesian method for the induction of probabilistic networks from data[J].Machine Learning，1992，9（4）：309-347.

[12]Russel S，Norvig P.Artificial intelligence：a modern approach[M].Beijing：Posts&Telecom Press，2002：320-354.

[13]Li Oni_sko A，Druzdzel M J，Wasyluk H.Learning Bayesian network parameters from small data sets：application of Noisy-OR gates[J].International Journal of Approximate Reasoning，2001，27（2）：165-182.

[14]Beinlich I A，Suermondt H J，Chavez R M,et al.The ALARM monitoring system：a case study with two probabilistic inference techniques for belief networks[C]//Proceedings of the 2nd European Conference on Artificial Intelligence in Medical Care，1989：247-256.