畢業(yè)論文參考.doc

齊齊哈爾大學(xué)畢業(yè)設(shè)計（論文）齊 齊 哈 爾 大 學(xué)畢業(yè)設(shè)計（論文）題 目 基于Matlab的貝葉斯網(wǎng)絡(luò)學(xué)習(xí)方法研究_學(xué) 院 計算機(jī)與控制工程學(xué)院_專業(yè)班級 計本062班_學(xué)生姓名 王麗娟_指導(dǎo)教師 張劍飛_成 績 2010年 6 月 19 日50摘 要貝葉斯網(wǎng)絡(luò)提供了一種表達(dá)因果關(guān)系的方法。它結(jié)合圖模型理論和統(tǒng)計學(xué)來表達(dá)隨機(jī)變量之間的不確定性知識，成為目前不確定知識表達(dá)和推理領(lǐng)域最有效的模型之一。貝葉斯網(wǎng)絡(luò)學(xué)習(xí)主要包括：結(jié)構(gòu)學(xué)習(xí)和參數(shù)學(xué)習(xí)，通過網(wǎng)絡(luò)結(jié)構(gòu)與數(shù)據(jù)集可以確定參數(shù)，因此結(jié)構(gòu)學(xué)習(xí)是貝葉斯網(wǎng)絡(luò)學(xué)習(xí)的核心，有效的結(jié)構(gòu)學(xué)習(xí)方法和算法是構(gòu)建最優(yōu)網(wǎng)絡(luò)結(jié)構(gòu)的基礎(chǔ)。本文在對貝葉斯網(wǎng)絡(luò)的起源、發(fā)展、特點及應(yīng)用情況進(jìn)行介紹的基礎(chǔ)上，著重對貝葉斯網(wǎng)絡(luò)的學(xué)習(xí)算法進(jìn)行了研究，闡述了幾種貝葉斯網(wǎng)絡(luò)學(xué)習(xí)算法的思想。采用MATLAB語言編制的貝葉斯網(wǎng)絡(luò)工具箱(Bayesian Networks Toolbox, BNT)實現(xiàn)這幾種學(xué)習(xí)算法的應(yīng)用，并結(jié)合實際給出了兩個實例進(jìn)行了說明分析，本文的研究對于充分運(yùn)用MATLAB的貝葉斯網(wǎng)絡(luò)工具箱的強(qiáng)大功能,學(xué)習(xí)和利用貝葉斯方法來解決實際問題有著重要而深遠(yuǎn)的意義。關(guān)鍵詞：貝葉斯網(wǎng)絡(luò)；結(jié)構(gòu)學(xué)習(xí)；參數(shù)學(xué)習(xí)；貝葉斯網(wǎng)絡(luò)工具箱AbstractBayesian network (BN) is an important method for presenting causality and uncertainty among random variables based on graphical model theory and statistics. It is one of the most efficient models in the fields of uncertain knowledge expression and inference. The learning Bayesian networks mainly includes: structural and parameter learning, parameters can be fixed through networks structure and data sets, so structural learning is the core of learning Bayesian network. The efficient structural learning is the basis constructing the most efficient network structure. The paper illustrates the origin, development, characteristics and application of Bayesian networks, emphatically studying Bayesian networks learning algorithm and introducing the theory of some Bayesian networks learning algorithms. The paper implements the application of these learning algorithms with Bayesian Networks Toolbox (BNT) based on MATLAB, and presents two instances to explain and analysis.The research makes full use of the powerful function of BNT based on MATLAB.Learning and using Bayesian method to solve actual problem have important and far-reaching significance.Key words: Bayesian network; Structural learning; Parameter learning; Bayesian Networks Toolbox目 錄摘要IAbstractII第1章 緒論11.1 研究背景和意義11.2 貝葉斯網(wǎng)絡(luò)的發(fā)展及研究現(xiàn)狀11.3 本文的研究內(nèi)容21.4 論文組織2第2章 貝葉斯網(wǎng)絡(luò)概述42.1 貝葉斯網(wǎng)絡(luò)42.1.1 貝葉斯網(wǎng)絡(luò)的描述42.1.2 貝葉斯網(wǎng)絡(luò)的數(shù)學(xué)表示42.1.3 貝葉斯網(wǎng)絡(luò)的構(gòu)造52.1.4 貝葉斯網(wǎng)絡(luò)的類型62.2 貝葉斯網(wǎng)絡(luò)的應(yīng)用62.2.1 應(yīng)用于分類和回歸分析62.2.2 應(yīng)用于不確定知識表達(dá)和推理62.2.3 應(yīng)用于數(shù)據(jù)挖掘72.2.4 應(yīng)用于聚類模式發(fā)現(xiàn)72.3 貝葉斯網(wǎng)絡(luò)學(xué)習(xí)的前提假設(shè)問題82.3.1 數(shù)據(jù)完整性假設(shè)82.3.2 無選擇偏好假設(shè)82.3.3 變量離散化假設(shè)82.4 國內(nèi)外研究現(xiàn)狀9第3章 貝葉斯網(wǎng)絡(luò)學(xué)習(xí)103.1 貝葉斯網(wǎng)絡(luò)學(xué)習(xí)概述103.2 Matlab簡介113.3 貝葉斯網(wǎng)絡(luò)工具箱簡介113.3.1 BNT中貝葉斯網(wǎng)絡(luò)的表示方式123.3.2 貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法函數(shù)133.3.3 貝葉斯網(wǎng)絡(luò)參數(shù)學(xué)習(xí)算法函數(shù)133.4 貝葉斯網(wǎng)絡(luò)工具箱的安裝143.5 手動創(chuàng)建一個貝葉斯網(wǎng)絡(luò)14第4章 貝葉斯網(wǎng)絡(luò)學(xué)習(xí)算法174.1 主要的結(jié)構(gòu)學(xué)習(xí)算法174.1.1 K2算法174.1.2 馬爾可夫鏈蒙特卡羅算法194.2 主要的參數(shù)學(xué)習(xí)算法204.2.1 最大似然性估計算法204.2.2 貝葉斯方法214.2.3 最大期望算法214.3 算法應(yīng)用224.3.1 K2算法應(yīng)用224.3.2 馬爾可夫鏈蒙特卡羅算法應(yīng)用244.3.3 貝葉斯網(wǎng)絡(luò)參數(shù)學(xué)習(xí)算法應(yīng)用26第5章 基于BNT的貝葉斯網(wǎng)絡(luò)學(xué)習(xí)舉例305.1 醫(yī)療診斷網(wǎng)絡(luò)305.1.1 問題描述305.1.2 解決方案305.1.3 建立模型315.1.4 數(shù)據(jù)采集325.1.5 構(gòu)造醫(yī)療診斷網(wǎng)絡(luò)345.1.6 結(jié)論分析395.2 汽車診斷網(wǎng)絡(luò)405.2.1 問題描述405.2.2 解決方案405.2.3 建立模型415.2.4 數(shù)據(jù)采集425.2.5 構(gòu)造汽車診斷網(wǎng)絡(luò)435.2.6 結(jié)論分析47結(jié)論48參考文獻(xiàn)49致謝50第1章 緒 論1.1 研究背景和意義隨著計算機(jī)技術(shù)和網(wǎng)絡(luò)技術(shù)的迅猛發(fā)展，使得人們利用信息技術(shù)收集數(shù)據(jù)的能力大幅度提高。人們深刻地認(rèn)識到，存儲在計算機(jī)系統(tǒng)中的各種各樣的數(shù)據(jù)都是寶貴的信息資源，其中有可能蘊(yùn)藏著許多有用的知識，這些信息或知識，將可能提供或預(yù)示無限的商機(jī)、關(guān)鍵性的技術(shù)改進(jìn)、乃至重要的科學(xué)發(fā)現(xiàn)，從而產(chǎn)生顯著的經(jīng)濟(jì)、社會效益。但是，由于人們目前所用工具的局限性而無法將其挖掘出來。因此，如何從各種類型的數(shù)據(jù)中獲得實際領(lǐng)域中可利用的、有價值的信息和知識，提高商務(wù)管理、生產(chǎn)控制、市場分析和科學(xué)研究等方面的效率，成為計算機(jī)研究人員面臨的具有挑戰(zhàn)性的任務(wù)。知識發(fā)現(xiàn)和數(shù)據(jù)挖掘正是適應(yīng)這些需求而提出來的，是當(dāng)前數(shù)據(jù)庫與人工智能領(lǐng)域研究的熱點課題，其目標(biāo)是在現(xiàn)實世界中，針對具有量的、質(zhì)的、復(fù)雜形態(tài)的各種信息源，挖掘先前未知的、具有潛在應(yīng)用價值的、最終可被用戶所理解的模式。近年來，人們研究出多種用于知識發(fā)現(xiàn)和數(shù)據(jù)挖掘的方法和技術(shù)，主要分為基于統(tǒng)計的方法、基于機(jī)器學(xué)習(xí)的方法、基于數(shù)學(xué)的方法。在眾多的知識發(fā)現(xiàn)和數(shù)據(jù)挖掘方法中，貝葉斯網(wǎng)絡(luò)結(jié)合圖論和統(tǒng)計學(xué)方面的知識，提供了一種表示變量之間因果關(guān)系的方法。以概率論和圖論為基礎(chǔ)，結(jié)點表示了隨機(jī)變量，結(jié)點間的有向邊表示了變量之間的因果關(guān)系，變量間影響的程度由網(wǎng)絡(luò)中依附在父、子結(jié)點對上的條件概率來表示。它是表示和處理不確定知識的理想模型。第2章 貝葉斯網(wǎng)絡(luò)概述貝葉斯網(wǎng)絡(luò)是一種概率網(wǎng)絡(luò)，它是基于概率推理的圖形化網(wǎng)絡(luò)，而貝葉斯公式則是這個概率網(wǎng)絡(luò)的基礎(chǔ)。貝葉斯網(wǎng)絡(luò)是基于概率推理的數(shù)學(xué)模型，所謂概率推理就是通過一些變量的信息來獲取其他的概率信息的過程，基于概率推理的貝葉斯網(wǎng)絡(luò)(Bayesian network)是為了解決不定性和不完整性問題而提出的，它對于解決復(fù)雜設(shè)備不確定性和關(guān)聯(lián)性引起的故障有很大的優(yōu)勢，在多個領(lǐng)域中獲得廣泛應(yīng)用。2.1 貝葉斯網(wǎng)絡(luò)2.1.1 貝葉斯網(wǎng)絡(luò)的描述貝葉斯網(wǎng)絡(luò)又稱信度網(wǎng)絡(luò)，是Bayes方法的擴(kuò)展，是目前不確定知識表達(dá)和推理領(lǐng)域最有效的理論模型之一。從1988年由Pearl提出后，已經(jīng)成為近幾年來研究的熱點。一個貝葉斯網(wǎng)絡(luò)是一個有向無環(huán)圖(Directed Acyclic Graph, DAG)，由代表變量的結(jié)點及連接這些結(jié)點的有向邊構(gòu)成。結(jié)點代表隨機(jī)變量，結(jié)點間的有向邊代表了結(jié)點間的相互關(guān)系(由父結(jié)點指向其后代結(jié)點)，用條件概率表達(dá)關(guān)系強(qiáng)度，沒有父結(jié)點的用先驗概率進(jìn)行信息表達(dá)。結(jié)點變量可以是任何問題的抽象，如：測試值、觀測現(xiàn)象、意見征詢等。適用于表達(dá)和分析不確定性和概率性的事件，應(yīng)用于有條件地依賴多種控制因素的決策，可以從不完全、不精確或不確定的知識或信息中做出推理。貝葉斯網(wǎng)絡(luò)具有如下特性：(1)貝葉斯網(wǎng)絡(luò)本身是一種不定性因果關(guān)聯(lián)模型。貝葉斯網(wǎng)絡(luò)與其他決策模型不同，它本身是將多元知識圖解可視化的一種概率知識表達(dá)與推理模型，更為貼切地蘊(yùn)含了網(wǎng)絡(luò)結(jié)點變量之間的因果關(guān)系及條件相關(guān)關(guān)系。(2)貝葉斯網(wǎng)絡(luò)具有強(qiáng)大的不確定性問題處理能力。貝葉斯網(wǎng)絡(luò)用條件概率表達(dá)各個信息要素之間的相關(guān)關(guān)系，能在有限的、不完整的、不確定的信息條件下進(jìn)行學(xué)習(xí)和推理。(3)貝葉斯網(wǎng)絡(luò)能有效地進(jìn)行多源信息表達(dá)與融合。貝葉斯網(wǎng)絡(luò)有助于故障診斷與維修決策。第3章 貝葉斯網(wǎng)絡(luò)學(xué)習(xí)學(xué)習(xí)貝葉斯網(wǎng)絡(luò)就是要尋找一種網(wǎng)絡(luò)，能按某種測度最好地與給定實例數(shù)據(jù)集擬合。就一般意義而言，尋找一種網(wǎng)絡(luò)包括尋找一種有向無環(huán)圖(DAG)結(jié)構(gòu)和獲得與DAG中各個結(jié)點相關(guān)的條件概率表(CPT)。前者稱為網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)，后者稱為網(wǎng)絡(luò)參數(shù)學(xué)習(xí)。由于通過網(wǎng)絡(luò)結(jié)構(gòu)與數(shù)據(jù)集可以確定參數(shù)，因此結(jié)構(gòu)學(xué)習(xí)是學(xué)習(xí)貝葉斯網(wǎng)絡(luò)的核心，有效的結(jié)構(gòu)學(xué)習(xí)方法和算法是構(gòu)建最優(yōu)網(wǎng)絡(luò)結(jié)構(gòu)的基礎(chǔ)。3.1 貝葉斯網(wǎng)絡(luò)學(xué)習(xí)概述一般貝葉斯網(wǎng)絡(luò)的構(gòu)建是首先由相關(guān)領(lǐng)域的專家根據(jù)事物間的關(guān)系來確定出結(jié)構(gòu)模型，即有向無環(huán)圖，然后再利用其它方法確定每個結(jié)點的條件概率，將這種利用先驗知識構(gòu)造的貝葉斯網(wǎng)絡(luò)稱為先驗貝葉斯網(wǎng)絡(luò)，但這樣構(gòu)建的網(wǎng)絡(luò)模型無法保證其客觀性和可靠性。近年來，國內(nèi)外的研究者們嘗試引入客觀的觀測數(shù)據(jù)，希望通過將觀測數(shù)據(jù)與專家知識相結(jié)合來共同構(gòu)建貝葉斯網(wǎng)絡(luò)，將這種利用先驗貝葉斯網(wǎng)絡(luò)和數(shù)據(jù)相結(jié)合而得到的貝葉斯網(wǎng)絡(luò)稱為后驗貝葉斯網(wǎng)絡(luò)。貝葉斯網(wǎng)絡(luò)學(xué)習(xí)是利用數(shù)據(jù)對先驗知識的修正，貝葉斯網(wǎng)絡(luò)能夠持續(xù)學(xué)習(xí)，上次學(xué)習(xí)得到的后驗貝葉斯網(wǎng)絡(luò)變成下一次學(xué)習(xí)的先驗貝葉斯網(wǎng)絡(luò)，每一次學(xué)習(xí)前都可以對先驗貝葉斯網(wǎng)絡(luò)進(jìn)行調(diào)整，使得新的貝葉斯網(wǎng)絡(luò)更能體現(xiàn)數(shù)據(jù)中蘊(yùn)涵的知識，因此貝葉斯網(wǎng)絡(luò)具有綜合先驗知識的增量學(xué)習(xí)特性。進(jìn)一步研究在沒有專家先驗知識的情況下，嘗試完全從觀測數(shù)據(jù)中學(xué)習(xí)得到網(wǎng)絡(luò)結(jié)構(gòu)和參數(shù)，生成貝葉斯網(wǎng)絡(luò)的方法?，F(xiàn)有的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)方法可分成兩類，一類是基于打分搜索的學(xué)習(xí)方法，這種方法可追溯到Chow-Liu Tree Constructing Algorithm，打分搜索方法過程簡單規(guī)范，但由于搜索空間大，一般是在結(jié)點有序的前提下，根據(jù)打分函數(shù)的可分解性進(jìn)行局部確定或隨機(jī)搜索(完全搜索是N-P困難問題)，這樣不僅降低了學(xué)習(xí)效率，而且易陷入局部最優(yōu)結(jié)構(gòu)，只適用于變量少或在一定范圍內(nèi)的結(jié)構(gòu)學(xué)習(xí)；另一類是基于依賴分析的學(xué)習(xí)方法，依賴分析方法過程比較復(fù)雜，但在一些假設(shè)下學(xué)習(xí)效率較高，而且能夠獲得全局最優(yōu)結(jié)構(gòu)。在現(xiàn)有的依賴分析方法中，冗余邊檢驗是在確定邊的方向之前進(jìn)行，這樣無法準(zhǔn)確地確定切割集，從而導(dǎo)致大量的高維條件概率計算，這樣往往不能定向所有的邊。這些問題的存在降低了學(xué)習(xí)效率和準(zhǔn)確性。參考文獻(xiàn)要在相應(yīng)的引用位置加上標(biāo)注3.2 Matlab簡介在科學(xué)研究和工程應(yīng)用中，為了克服一般語言對大量的數(shù)學(xué)運(yùn)算，尤其當(dāng)涉及矩陣運(yùn)算時編制程序復(fù)雜、調(diào)試麻煩等困難，美國Math Works公司于1967年構(gòu)思并開發(fā)了矩陣實驗室(Matrix Laboratory，MATLAB)軟件包。經(jīng)過不斷的更新和補(bǔ)充，該公司于1984年推出MATLAB的正式版，特別是1992年推出具有劃時代意義的MATLAB 4.0版，并于1993年推出其微機(jī)版，以配合當(dāng)時日益流行的Micrrosoft Windows操作系統(tǒng)一起使用。截止到2005年，該公司先后推出了MATLAB 4.x，MATLAB 6.x以及MATLAB 7.x等版本，該軟件的應(yīng)用范圍越來越廣。由于MATLAB的基本數(shù)據(jù)單元是維數(shù)不加限制的矩陣，用戶無需考慮大量的有關(guān)矩陣的運(yùn)算該采用何種算法等低層問題，更不必深入了解相應(yīng)算法的具體細(xì)節(jié)，因而對用戶算法語言方面的要求十分寬松。因此，在貝葉斯軟件包BNT中，采用的貝葉斯網(wǎng)絡(luò)的表示方式為矩陣方式。即用矩陣的形式表示貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)，若結(jié)點i到結(jié)點j有一條弧，則對應(yīng)的矩陣中(i，j)值為1，否則為0。如圖3-1所示的貝葉斯網(wǎng)絡(luò)，其結(jié)構(gòu)的矩陣表示形式如圖3-2所示。對圖表要給出相應(yīng)的說明12345圖3-1 表示5個變量間因果關(guān)系的Bayesian網(wǎng) 圖3-2 矩陣表示法注意圖名的字體和字號及位置3.3.2 貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法函數(shù)貝葉斯軟件包BNT提供了較為豐富的結(jié)構(gòu)學(xué)習(xí)函數(shù)，它們是：(1)學(xué)習(xí)樹擴(kuò)展貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的TANC算法Learn_struct_tan( )。(2)數(shù)據(jù)完整條件下學(xué)習(xí)一般貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的K2算法learn_struct_K2( )、貪婪搜索GS(Greedy Search)算法learn_struct_gs( )和爬山HC(Hill Climbing)算法learn_struct_hc( )等。(3)數(shù)據(jù)缺失條件下學(xué)習(xí)一般貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的最大期望EM(Expectation Maximization)算法learn_struct_em( )和馬爾可夫鏈蒙特卡羅MCMC(Markov Chain Monte Carlo) 算法learn_struct_mcmc( )。3.3.3 貝葉斯網(wǎng)絡(luò)參數(shù)學(xué)習(xí)算法函數(shù)貝葉斯軟件包BNT同時還提供了較為豐富的參數(shù)學(xué)習(xí)函數(shù)，它們是：(1)數(shù)據(jù)完整時，學(xué)習(xí)參數(shù)的方法主要有兩種：最大似然性估計算法learn_params( )和貝葉斯方法bayes_update_params( )。(2)數(shù)據(jù)缺失時，如果已知網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，用EM算法learn_params_em( )來計算參數(shù)，倘若未知網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，還可以使用結(jié)構(gòu)最大期望SEM(Structural EM)算法。表3-2 變量Sprinkler的條件概率表對表名要放在表的上面，注意字體和字號。CP(S=F)P(S=T)F0.50.5T0.90.1表3-3 變量Rain的條件概率表CP(R=F)P(R=T)F0.80.2T0.20.8表3-4 變量Wet Grass的條件概率表S RP(W=F)P(W=T)F F1.00.0T F0.10.9F T0.10.9T T0.010.99假設(shè)所有變量都是離散變量，這個例子描述的整個情景抽象為4個變量，所有變量都是布爾變量：Cloudy(C=T表示陰天)，Sprinkler(S=T表示灑水車)，Rain(R=T表示下雨)，Wet Grass(W=T表示草地濕)。從表3-1至表3-4中，每個變量的條件概率表中的每一行都記錄了給定變量的某個實例后，該變量為“TRUE”或“FALSE”的概率值。例如，如果是灑水車灑水并且下雨，那么草地濕的概率為0.99。對表的內(nèi)容在正文中進(jìn)行說明。從圖3-3中的貝葉斯網(wǎng)絡(luò)，直觀上可知，W依賴于S和R，S和R相互獨立。通常，貝葉斯網(wǎng)絡(luò)可以表示一組條件獨立性語句。在一定的假設(shè)下，貝葉斯網(wǎng)絡(luò)也可以表示變量之間的依賴關(guān)系。具體程序代碼見程序清單中的程序1csrw1.m，運(yùn)行結(jié)果如圖3-4所示。圖3-4 csrw1.m的運(yùn)行結(jié)果最終構(gòu)造出整個網(wǎng)絡(luò)結(jié)構(gòu)，如圖4-1所示。圖4-1 csrwK2.m的運(yùn)行結(jié)果觀察此網(wǎng)絡(luò)圖，可知與手動構(gòu)造的CSRW貝葉斯網(wǎng)絡(luò)圖以及真實的網(wǎng)絡(luò)結(jié)構(gòu)一致。具體程序代碼見程序清單中的程序2csrwK2.m。結(jié) 論結(jié)論是對設(shè)計的內(nèi)容，設(shè)計的技術(shù)，設(shè)計功能，設(shè)計所達(dá)到的要求進(jìn)行說明。參考文獻(xiàn)參考文獻(xiàn)的格式和字體字號。1 Heckerman D，Mamdani A，Wellman MReal-World Applications of Bayesian NetworksJCommunications of ACM,1995,38(3)：38-452 Friedman N.Bayesian network classifiersJ.Machine Learning,1997,2(6)：131-163.3 林士敏，田鳳占，陸玉昌.用于數(shù)據(jù)采掘的貝葉斯分類器研究J.計算機(jī)科學(xué)，2000，27(10)：73-76.4 羌磊，肖田元，喬桂秀.一種改進(jìn)的Bayesian網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法J.計算機(jī)研究與發(fā)展，2002，39(l0)：1221-1226.5 蔣望東,林士敏.基于貝葉斯網(wǎng)絡(luò)工具箱的貝葉斯學(xué)習(xí)和推理J.信息技術(shù)，2007，25(2)：6-8.6 張劍飛.貝葉斯網(wǎng)絡(luò)學(xué)習(xí)方