影響圖的漸進式構建方法

馬 馮，劉惟一，楊 櫻

MA Feng1,LIU Weiyi2,YANG Ying3

1.云南財經大學 信息學院，昆明 650221

2.云南大學 信息學院，昆明 650091

3.云南財經大學 國際工商學院，昆明 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]作為一種有效的決策工具得到了人們廣泛的關注，并在諸多領域[2-7]中應用廣泛。然而，由于傳統的影響圖構建方法[8]需要專家或領域知識來確定原始數據集中變量間的相互關系，因此如果原始數據集增長，那么原有與之對應的影響圖可能就不再適用于新的數據集了。此時，如果用傳統的構建方法為新數據集構建影響圖，那么就需要再次引入專家或領域知識來確認新環境下，各個變量間的關系如何，并重新構建一個適合新數據的影響圖。

事實上，在大部分的實際應用中，新增長的數據集與原始數據集相比，大部分的變量變化程度很小。因此，本文針對這種情況，提出了一種影響圖的漸進式構建方法，即在已知原始數據集和與之對應的影響圖時，如果原始數據集增長，此方法可以通過調整現有影響圖的結構和參數而獲得一個適用于新數據集的新影響圖。

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

本文的主要貢獻可以歸結為以下兩點：

（1）給定一個原始的數據集合對應的影響圖，當原始數據集增長時，影響圖的漸進式構建方法可以在不需要增加專家或領域知識的前提下，構建出一個新的符合要求的新影響圖。

（2）影響圖的漸進式構建方法在構建新的影響圖時，只需要對原影響圖進行局部調整即可，從而避免了從頭開始重建一個影響圖的問題。

2 背景知識

影響圖是一種基于不確定性信息表示，用于處理復雜決策問題的圖模型[1]。它包含兩個部分：圖結構和參數表。圖結構表示數據集上變量間的依賴和時序關系，參數表體現了變量間的依賴程度。

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

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

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

然而貝葉斯網和影響圖之間，還是有差異的，具體可以總結為以下幾點[9]：

（1）影響圖中的效用節點，不能有后繼節點；貝葉斯網中無此限制。

（2）影響圖中決策節點的順序，必須要和現實世界中的實際情況一致。

（3）影響圖中至少有一個決策節點和一個效用節點，并且決策節點應該是效用節點的祖先。

（4）影響圖中的所有效用節點都要有對應的決策節點作為其祖先節點。

因此，在將影響圖轉化為其對應的簡化圖，即貝葉斯網時，或從貝葉斯網將其轉換為影響圖時，均需要遵循上述的幾點規則。

3 影響圖的漸進式構建方法

在影響圖的漸進式構建方法中，有兩個關鍵步驟：一個是構建影響圖的圖結構，另一個是計算圖中各個變量的參數表。對于后一個步驟，劉惟一已經在文獻[9]中給予了詳細的描述，因此本文在此就不再冗述。本文提出的方法將專注于如何將原有影響圖的結構調整成適合新數據的新結構。

3.1 影響圖的漸進式構建方法描述

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

定義3.1.1如果xi是go的一個節點，那么xi的直接前驅節點就成為xi的父節點，記為Pa(xi)。

定理3.1.1如果xi是go的一個節點，是xi參數表中的值集，并且是Pa(xi)參數表中的值集，那么評分函數

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

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

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

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

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

Input：

Do：原始數據集

Dn：新數據集

gido：原始數據的影響圖

T：閾值

Output：

gidn：符合新數據集的影響圖

Variables：

go：gido的簡化圖

gt：go的臨時調整結果

gn：gidn的簡化圖

CH(gt|Dn)：評分函數

xi：gt中的一個節點

步驟：

Begin

步驟1將gido轉換為與其對應的簡化圖go

步驟2

（1）將當前的go記為臨時調整結果gt。

（2）判斷當前臨時調整結果的評分制CH(gt|Dn)是否能夠大于或等于閾值T。如果不滿足條件，則循環執行下面幾步直至滿足條件為止。

①計算gt中每個節點xi的影響度，并找出影響度值最大的節點，記為xtag。

②在xtag的馬爾科夫覆蓋范圍內，嘗試著對邊進行反向，增加或刪除等操作對原圖進行調整，從而將gt變為中間調整結果gt'。

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

④將臨時調整結果gt調整成上一步找出的中間調整結果gt'，并返回（2）的判斷條件。

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

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

End

3.2 影響圖的漸進式構建方法的有效性

定理3.2.1影響圖的漸進式構建方法得出的最終結果gidn是符合新數據集Dn的。

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

4 實驗和分析

4.1 實驗

為了便于分析實驗結果，實驗選取了兩個經典的數據集Hepar II[13]和Alarm[14]。現先以Hepar II為例，說明具體的實驗過程。實驗中，選取其原數據集中的部分變量進行實驗，并將前100條記錄作為Do，構建出的相應影響圖為gido。

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

圖1 IBMIDS構造出的Hepar II影響圖

同理，可以用IBMIDS方法構建出Alarm數據集的影響圖，如圖2所示。

4.2 分析

文獻[13]中已經給出了用傳統方法基于Hepar II數據集構建的影響圖，如圖3所示。文獻[14]中已經給出了用傳統方法基于Alarm數據集構建的影響圖，如圖4所示。可以看出，圖1與圖3相比，圖2與圖4相比，兩者均是等價的。因此，可以表明影響圖的漸進式構建方法對于這兩個經典的數據集都是有效的。

由于該方法的最終結果是由貝葉斯網轉換而來的，但是對于一個給定的數據集，其有效的貝葉斯網結構并不唯一。因此，有時候影響圖的漸進式構建方法得出的結果，并不一定與傳統方法構建出的影響圖在結構上完全一致，但這并不是說明該影響圖是無效的。根據之前的討論可知，它只是一個有效，但表現形式不同的影響圖。

5 結束語

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

圖2 IBMIDS構造出的Alarm影響圖

圖3 用傳統方法構建出的Hepar II影響圖

圖4 用傳統方法構建出的Alarm影響圖

在經過大量的實驗后發現，如果新數據集與原始數據集相比，大部分的變量在其分布情況上都發生了重大的變化，那么這種方法的效率就會受到很大的影響。因為此時每個節點都會耗費很多時間在與之相關的邊調整上，以便于找到合適的新結構。如何改進這個問題，將會是下一步工作的重點。通過研究發現，現實應用中的大部分情況，其新數據集與原始數據集相比，都屬于僅有小部分的變量在分布情況上有較大改變，其余大部分的變量變化很小的情況。因此，本文提出的方法在大部分的實際應用中都可以得到較好的結果。

[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，Ferná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]劉惟一，李維華，岳昆.智能數據分析[M].北京：科學出版社，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.