【摘要】： 決策是小到個(gè)人,大到國(guó)家、社會(huì)都不可避免的事情。決策分析作為解決決策問(wèn)題的基本觀點(diǎn),成為人們研究的熱點(diǎn),決策的科學(xué)性也越來(lái)越受到社會(huì)的重視。作為一種決策分析的有效工具,影響圖被廣泛用于決策支持、預(yù)測(cè)分析、知識(shí)發(fā)現(xiàn)等領(lǐng)域中。然而,求解影響圖的算法,其計(jì)算量相對(duì)于結(jié)點(diǎn)數(shù)是指數(shù)級(jí)的,傳統(tǒng)的影響圖由于其精確的表示及決策機(jī)制,使其不能較好地滿足問(wèn)題域中變量過(guò)多的實(shí)際應(yīng)用。同時(shí),許多應(yīng)用中,用戶并不一定需要知道各個(gè)領(lǐng)域內(nèi)部瑣碎的聯(lián)系,而只需要知道各個(gè)領(lǐng)域之間的聯(lián)系。 本文針對(duì)前述問(wèn)題的實(shí)際需要,在貝葉斯網(wǎng)結(jié)點(diǎn)聚集的基礎(chǔ)上,提出影響圖結(jié)點(diǎn)聚集的算法,使得影響圖中,屬于同一個(gè)領(lǐng)域的多個(gè)結(jié)點(diǎn),聚集成為一個(gè)新的結(jié)點(diǎn),從而簡(jiǎn)化影響圖的結(jié)構(gòu),并通過(guò)實(shí)驗(yàn)驗(yàn)證了該方法的有效性。 本文的主要工作和創(chuàng)新之處總結(jié)如下: 由于影響圖包含不同類(lèi)型的結(jié)點(diǎn),且結(jié)點(diǎn)之間的關(guān)系也不是單純的概率關(guān)系,因此,根據(jù)結(jié)點(diǎn)類(lèi)型的不同,在不破壞影響圖內(nèi)部結(jié)構(gòu)的基礎(chǔ)上,將影響圖分解為兩個(gè)部分,即概率網(wǎng)絡(luò)部分(可以等價(jià)于一個(gè)貝葉斯網(wǎng))和效用網(wǎng)絡(luò)部分,構(gòu)成兩個(gè)新圖,然后分別對(duì)這兩個(gè)圖進(jìn)行聚集。 對(duì)于概率網(wǎng)絡(luò)部分,我們用貝葉斯網(wǎng)的結(jié)點(diǎn)聚集算法來(lái)實(shí)現(xiàn)其結(jié)點(diǎn)的聚集。對(duì)于效用網(wǎng)絡(luò)部分,討論了效用結(jié)點(diǎn)之間的條件效用獨(dú)立關(guān)系,提出效用結(jié)點(diǎn)的聚集算法以及效用表參數(shù)的更新。 基于影響圖的圖形特性,根據(jù)結(jié)點(diǎn)之間的父子關(guān)系,將兩個(gè)聚集后的新圖合并成一個(gè)新的影響圖。
【圖文】：

影響圖的基本概念和相關(guān)結(jié)論，作為本文后續(xù)章節(jié)的背景知識(shí)。2.1 貝葉斯網(wǎng)簡(jiǎn)介貝葉斯網(wǎng)絡(luò)（BN）[15]是一種圖形化的模型，能夠直觀地表示一組變量之間的依賴關(guān)系。一個(gè)貝葉斯網(wǎng)絡(luò)包括了一個(gè)結(jié)構(gòu)模型和與之相關(guān)的一組條件概率分布函數(shù)。結(jié)構(gòu)模型是一個(gè)有向無(wú)環(huán)圖，其中結(jié)點(diǎn)表示問(wèn)題域中的隨機(jī)變量，有向邊則 表 示 變 量 之 間 的 依 賴 關(guān) 系 ， 其 依 賴 程 度 用 條 件 概 率 進(jìn) 行 定 量 表 示[3,15,16,17,18,19,20,21]，圖 2.1 給出了一個(gè)簡(jiǎn)單的貝葉斯網(wǎng)示例。馬爾可夫網(wǎng)和貝葉斯網(wǎng)是分別用無(wú)向圖和有向無(wú)環(huán)圖來(lái)表示條件獨(dú)立關(guān)系的兩種圖形模型。下面，我們首先介紹關(guān)于圖論和概率論的基礎(chǔ)知識(shí)，然后介紹馬爾可夫網(wǎng)和貝葉斯網(wǎng)的基本概念和性質(zhì)[3,15],最后介紹鏈圖模型，作為本文研究概率網(wǎng)絡(luò)部分聚集的基礎(chǔ)。

機(jī)變量的不同狀態(tài)的概率。每一個(gè)效用結(jié)點(diǎn)都有一張效用分配表（也稱為效用矩陣）與之對(duì)應(yīng)，它描述當(dāng)前狀態(tài)下采取不同行動(dòng)的收益情況。一個(gè)效用結(jié)點(diǎn) A 的效用矩陣就是該效用結(jié)點(diǎn)的父親結(jié)點(diǎn)集的函數(shù)，用 U(Pa(A))表示。決策結(jié)點(diǎn)是決策者可控制的行為描述。下面是一個(gè)簡(jiǎn)單的影響圖。例 2.3 一家采礦公司對(duì)某礦藏的開(kāi)采決策及收益情況如下：自然結(jié)點(diǎn) O 代表礦藏的蘊(yùn)藏情況，已知儲(chǔ)量高的概率是 0.2，用 o1表示；儲(chǔ)量一般的概率是 0.5用 o2表示；儲(chǔ)量低的概率是 0.3，用 o3表示。決策結(jié)點(diǎn) D 代表開(kāi)采決策，d1表示開(kāi)采，d2表示不開(kāi)采。效用結(jié)點(diǎn) U 表示在某種礦藏儲(chǔ)量情況下，選擇開(kāi)采或不開(kāi)采所獲得的收益情況，它與一張效用函數(shù)表 U(O,D)相關(guān)聯(lián)。如果決定開(kāi)采，收益受礦藏儲(chǔ)量的影響很大，如果儲(chǔ)量高，，收益是 100；儲(chǔ)量一般，收益是 30；儲(chǔ)量低，收益是-50。如果不開(kāi)采，收益為 0。那么礦藏開(kāi)采決策的影響圖如圖 2.4 所示。
【學(xué)位授予單位】：云南大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2010
【分類(lèi)號(hào)】：N945.25

【參考文獻(xiàn)】

相關(guān)期刊論文 前3條

1 于睿箭，馮允成;影響圖的基礎(chǔ)理論和發(fā)展[J];北京航空航天大學(xué)學(xué)報(bào);1994年04期

2 李維華,劉惟一,張忠玉;基于鏈圖的Bayesian網(wǎng)結(jié)點(diǎn)聚集[J];計(jì)算機(jī)應(yīng)用;2004年03期

3 韋健;吳祈宗;黃鍇;史愛(ài)芬;;定性影響圖及其決策算法改進(jìn)研究[J];微計(jì)算機(jī)信息;2008年24期

本文編號(hào)：2621838