浙江大學(xué)研究生《人工智能引論》課件徐從富(CongfuXu)

PhD,AssociateProfessorEmail:xucongfu@InstituteofArtificialIntelligence,CollegeofComputerScience,ZhejiangUniversity,Hangzhou310027,P.R.ChinaMarch10,2002第一稿April18,2007第四次修改稿第四講不確定性推理概述

(Chapter4UncertaintyReasoning)浙江大學(xué)研究生《人工智能引論》課件徐從富(CongfuXu1Outline本章的主要參考文獻(xiàn)基本概念基本問題不確定性推理方法的分類不確定性度量的測度理論不確定性的其它度量方法Shannon信息熵及在決策樹中的應(yīng)用模糊推理Outline本章的主要參考文獻(xiàn)2[1]王永慶.人工智能原理與方法.西安交通大學(xué)出版社,1998.pp156-252.(偏重基本概念)[2]張文修,梁怡.不確定性推理原理.西安交通大學(xué)出版社,1996.（偏重數(shù)學(xué)原理）[3]陸汝鈐.人工智能(下冊).

科學(xué)出版社,2000.pp1133-1170.（偏重Bayes概率推理、可信度、模糊推理）[4]史忠植.知識發(fā)現(xiàn).清華大學(xué)出版社,2002.pp24-26,pp141-202.（偏重Roughset和貝葉斯網(wǎng)絡(luò)）本章的主要參考文獻(xiàn)[1]王永慶.人工智能原理與方法.西安交通大學(xué)出版社3[5]Mitchell,T.M.著,曾華軍等譯.機(jī)器學(xué)習(xí).機(jī)械工業(yè)出版社,2003.pp112-143.（偏重貝葉斯學(xué)習(xí)）[6]Russell,S.,Norvig,P.ArtificialIntelligence:AModernApproach.人民郵電出版社,2002.pp413-522.（偏重貝葉斯網(wǎng)絡(luò)及其應(yīng)用）本章的主要參考文獻(xiàn)（續(xù)）“BlessedisthenationwhoseGodistheLORD,thepeoplehechoseforhisinheritance.”

FromPSALMS33:12NIV

[5]Mitchell,T.M.著,曾華軍等譯.44.1.1精確推理的局限性推理依據(jù)已知事實(shí)（證據(jù)）、相關(guān)知識（規(guī)則）證明某個假設(shè)成立or不成立

精確推理及其不足將原本為不確定性的關(guān)系“硬性”轉(zhuǎn)化為精確關(guān)系將原本不存在明確界限的事物“人為”劃定界限歪曲了現(xiàn)實(shí)情況的本來面目舍棄了事物的某些重要屬性失去了真實(shí)性4.1基本概念4.1.1精確推理的局限性4.1基本概念54.1.2不確定性推理的定義及意義1.定義也稱“不精確性推理”從不確定性的初始證據(jù)（即已知事實(shí)）出發(fā)運(yùn)用不確定性的知識（或規(guī)則）推出具有一定程度的不確定性但卻是合理或近乎合理的結(jié)論2.意義使計算機(jī)對人類思維的模擬更接近于人類的真實(shí)思維過程4.1.2不確定性推理的定義及意義1.定義64.2不確定性推理中的基本問題不確定性的表示與度量不確定性匹配不確定性的傳遞算法不確定性的合成4.2不確定性推理中的基本問題不確定性的表示與度量74.2.1不確定性的表示與度量1.不確定性的表示選擇不確定性表示方法時應(yīng)考慮的因素充分考慮領(lǐng)域問題的特征恰當(dāng)?shù)孛枋鼍唧w問題的不確定性滿足問題求解的實(shí)際需求便于推理過程中對不確定性的推算4.2.1不確定性的表示與度量1.不確定性的表示8不確定性的表示與度量（續(xù)1）2.不確定性的度量針對不同的領(lǐng)域問題采用不同的度量方法用不同的數(shù)值刻畫不同的不確定性程度事先規(guī)定不確定性程度的取值范圍3.常用的度量方法測度理論（基于概率統(tǒng)計的度量方法）Shannon信息熵其它度量方法……不確定性的表示與度量（續(xù)1）2.不確定性的度量9不確定性的表示與度量（續(xù)2）在選擇不確定性度量方法時應(yīng)考慮的因素：充分表達(dá)相應(yīng)知識及證據(jù)不確定性的程度度量范圍便于領(lǐng)域?qū)＜壹坝脩艄烙嫴淮_定性便于計算過程中的不確定性傳遞，結(jié)論的不確定性度量不超出規(guī)定的范圍度量的確定應(yīng)直觀，且有相應(yīng)的理論依據(jù)不確定性的表示與度量（續(xù)2）在選擇不確定性度量方法時應(yīng)考慮的104.2.2不確定性匹配解決不確定性匹配的常用方法設(shè)計一個匹配算法用以計算相似度指定一個相似度的“限定”（即閾值）“TodowhatisrightandjustismoreacceptabletotheLORDthansacrifice.”

FromPROVERBS21:3NIV

4.2.2不確定性匹配“Todowhatisri114.2.3證據(jù)不確定性的組合單一證據(jù)&

組合證據(jù)單一證據(jù)：前提條件僅為一個簡單條件組合證據(jù)：一個復(fù)合條件對應(yīng)于一組證據(jù)前提條件用AND（與）或OR（或）把多個簡單條件連接起來構(gòu)成復(fù)合條件4.2.3證據(jù)不確定性的組合12（1）最大最小法T(E1ANDE2)=min{T(E1),T(E2)}T(E1ORE2)=max{T(E1),T(E2)（2）概率方法（要求事件之間完全獨(dú)立）

T(E1ANDE2)=T(E1)×T(E2)T(E1ORE2)=T(E1)+T(E2)-T(E1)×T(E2)（3）有界方法T(E1ANDE2)=max{0,T(E1)+T(E2)-1}T(E1ORE2)=min{1,T(E1)+T(E2)}【注】：上述T(E)表示證據(jù)E為真的程度，如可信度、概率等。每組公式都有相應(yīng)的適用范圍和使用條件。常用的組合證據(jù)不確定性計算方法（1）最大最小法常用的組合證據(jù)不確定性計算方法134.2.4不確定性的傳遞包含兩個子問題在每一步推理中，如何把證據(jù)及知識的不確定性傳遞給給結(jié)論在多步推理中，如何把初始證據(jù)的不確定性傳遞給最終結(jié)論4.2.4不確定性的傳遞144.2.5結(jié)論不確定性的合成用不同知識進(jìn)行推理得到相同的結(jié)論同個結(jié)論的不確定性程度卻不相同需要用合適的算法對它們進(jìn)行合成4.2.5結(jié)論不確定性的合成154.3不確定性推理方法的分類4.3.1不確定性推理的兩條研究路線模型方法在推理一級上擴(kuò)展確定性推理不確定證據(jù)和知識與某種度量標(biāo)準(zhǔn)對應(yīng)給出更新結(jié)論不確定性的算法構(gòu)成相應(yīng)的不確定性推理模型控制方法在控制策略一級上處理不確定性無統(tǒng)一的不確定性處理模型，其效果依賴于控制策略4.3不確定性推理方法的分類4.3.1不確定性推理164.3.2不確定性推理方法的分類不確定性推理模型方法控制方法數(shù)值方法非數(shù)值方法概率統(tǒng)計方法模糊推理方法粗糙集方法絕對概率方法貝葉斯方法證據(jù)理論方法HMM方法發(fā)生率計算相關(guān)性制導(dǎo)回溯、機(jī)緣控制、啟發(fā)式搜索等可信度方法4.3.2不確定性推理方法的分類不確定性推理模型控制數(shù)值非174.3.3關(guān)于不確定性推理方法的說明數(shù)值方法對不確定性的一種定量表示和處理方法其研究及應(yīng)用較多，已形成多種應(yīng)用模型非數(shù)值方法除數(shù)值方法外的其它處理不確定性的模型方法典型代表：“發(fā)生率計算方法”，它采用集合來描述和處理不確定性，且滿足概率推理的性質(zhì)4.3.3關(guān)于不確定性推理方法的說明18關(guān)于不確定性推理方法的說明（續(xù)1）概率統(tǒng)計方法有完整、嚴(yán)密的數(shù)學(xué)理論為不確定性的合成與傳遞提供了現(xiàn)成的數(shù)學(xué)公式最早、最廣泛地用于不確定性知識的表示與處理已成為不確定性推理的重要手段證據(jù)理論方法1967年Dempster首次提出，1976年Shafer完善可表示并處理“不知道”等不確定性信息關(guān)于不確定性推理方法的說明（續(xù)1）19關(guān)于不確定性推理方法的說明（續(xù)2）模糊推理方法可表示并處理由模糊性引起的不確定性已廣泛應(yīng)用于不確定性推理粗糙集理論方法1981年Z.Pawlak首次提出一種新的可表示并處理“含糊”等不確定性的數(shù)學(xué)方法可用于不確定性推理、數(shù)據(jù)挖掘等領(lǐng)域關(guān)于不確定性推理方法的說明（續(xù)2）204.4描述不確定性信息的測度理論4.4.1測度及其分類

設(shè)(X)是有限集合X上的子集合的全體，測度的定義如下：定義6.1（測度）若g:(X)[0,1]滿足條件： (1)g(X)=1; (2)當(dāng)AB=時，有 g(AB)=g(A)+g(B)+g(A)g(B)稱為g測度。【注】：關(guān)于測度理論的詳細(xì)論述請參見夏道行編著的《實(shí)變函數(shù)與泛函分析》，復(fù)旦大學(xué)出版社。4.4描述不確定性信息的測度理論21定義4.2（模糊測度）模糊測度被定義為一個映射M:(X)[0,1]具有如下性質(zhì)：(1)有界性：M()=0,M(X)=1;(2)單調(diào)性：對任意A,B(X),AB時，有M(A)M(B)由模糊測度定義可知：

（1）有界性表示：一個非空元素不可能屬于，它必然屬于全集；（2）單調(diào)性表示：一個元素隸屬于一個集合的確定度不大于它隸屬于更大的一個集合的確定度。定義4.2（模糊測度）模糊測度被定義為一個映射22定理4.1當(dāng)>-1時，測度g是模糊測度。定理4.2當(dāng)>-1時，測度g具有如下性質(zhì)：模糊測度及其性質(zhì)定理4.1當(dāng)>-1時，測度g是模糊測度。模糊測度23定義4.3（概率測度）稱P：(X）→[0，1]為概率測度，若滿足：（1）有界性：P(X)=1（2）可加性：A∩B=Φ時，P(A∪B)=P(A)+P(B)【注】：可證明概率測度是＝0時模糊測度。定義4.4

(條件概率)如果P是X上的概率測度，EX，且P(E)>0，稱為給定條件E下，事件A發(fā)生的條件概率。定義4.3（概率測度）稱P：(X）→[0，1]為24

對于條件概率有如下聯(lián)合概率公式：

若A1,A2,...,An為X中的n個事件，可得

若A,B兩個事件滿足P(A|B)=P(A)，即A發(fā)生的可能性與B無關(guān)，稱A,B是相互獨(dú)立的。這時有

若n個事件A1,A2,...,An相互獨(dú)立，則對于條件概率有如下聯(lián)合概率公式：若A1,25Markov條件獨(dú)立性定義4.5(馬氏條件獨(dú)立性)若A1,A2,...,An是按時間順序發(fā)生的一系列事件，而且具有如下特性：未來某一事件Ak+1發(fā)生的可能性只依賴于當(dāng)前時刻的事件Ak，而與過去發(fā)生的事件無關(guān)，即這時稱n個事件具有馬氏（Markov）獨(dú)立性。對n個滿足馬氏獨(dú)立性條件的事件滿足Markov條件獨(dú)立性定義4.5(馬氏條件獨(dú)立性)26定義4.6（全概率公式）設(shè)Hi(i<=m)是X上的分劃，HiHj(ij)，且H1H2…

Hm=X。由概率可加性，對于任意事件A，有

對于條件概率有如下全概率公式：

定義4.7

(后驗(yàn)概率公式）

：Bayes公式定義4.6（全概率公式）設(shè)Hi(i<=m)是X上的分27Bayes公式與全概率公式的區(qū)別全概率公式由原因到結(jié)果的計算公式不如Bayes公式使用廣泛Bayes公式后驗(yàn)概率公式已知某結(jié)果發(fā)生，尋求這個結(jié)果發(fā)生的原因在實(shí)際問題中有著十分重要的應(yīng)用Bayes公式與全概率公式的區(qū)別28定義4.8（信任測度）設(shè)X是有限集，稱B：(X)[0,1]為信任測度，若滿足：(1)B()=0,B(X)=1;(2)對于X中任意子集A1，A2，…，An有如果僅僅滿足，對于X中任意兩個子集A1及A2有稱為弱信任測度?！咀ⅰ浚嚎勺C明信任測度與弱信任測度都是模糊測度。信任測度是證據(jù)理論的最基礎(chǔ)概念。定義4.8（信任測度）設(shè)X是有限集，稱B：(X)29定義4.9（似然測度）設(shè)X是有限集，稱L：(X)[0,1]為似然測度，若滿足：(1)L()=0,L(X)=1;(2)對于X中任意子集A1，A2，…，An有如果僅僅滿足，對于X中任意兩個子集A1及A2有稱為弱似然測度。【注】：可證明似然測度與弱似然測度都是模糊測度。似然測度是證據(jù)理論的最基礎(chǔ)概念。定義4.9（似然測度）設(shè)X是有限集，稱L：(X)30定義4.10（mass函數(shù)）稱m：(X)→[0，1]是mass函數(shù)，若滿足：（1）m(Ф)=0（2）mass函數(shù)是專家的一種評價或確認(rèn)程度。比如X={x1,x2,…,xn}是n中疾病，某專家認(rèn)為某人得疾病x1的可能性為0.7，于是得到一個mass函數(shù)：在證據(jù)理論中，mass函數(shù)對構(gòu)造信任測度與似然測度中有著重要的作用。定義4.10（mass函數(shù)）稱m：(X)→[0，1]是m31定義4.11（必然性測度）設(shè)X是有限集，稱N：(X)[0,1]為必然性測度，若滿足：(1)N()=0,N(X)=1;(2)N(AB)=N(A)N(B)定義4.12（可能性測度）設(shè)X是有限集，稱：(X)[0,1]為可能性測度，若滿足：(1)()=0,(X)=1;(2)(AB)=(A)(B)【注】：可證明必然測度與可能性測度都是模糊測度。它們是Zadel提出的可能性理論的最基礎(chǔ)概念。定義4.11（必然性測度）設(shè)X是有限集，稱N：(X)32概率測度必然測度可能測度信任測度似然測度模糊測度各種模糊測度之間的關(guān)系示意圖4.4.2模糊測度各類之間的關(guān)系概率測度必然測度可能測度信任測度似然測度模糊測度各種模糊測度33模糊測度各類之間的關(guān)系（續(xù)）模糊測度是一大類測度，它除了有界性條件外，只要求測度滿足單調(diào)性，即當(dāng)AB時，有M(A)M(B)。上述各類模糊測度之間的關(guān)系如下：必然性測度一定是信任測度可能性測度一定是似然測度概率測度是信任測度與似然測度的交集……模糊測度各類之間的關(guān)系（續(xù)）模糊測度是一大類測度，344.5不確定性的其它度量方法1、不協(xié)調(diào)度定義4.17(不協(xié)調(diào)度)設(shè)m是X上的mass函數(shù)，L為由m生成的似然測度，即稱為[X,m]的不協(xié)調(diào)度。4.5不確定性的其它度量方法稱為[X,m]的不協(xié)調(diào)度。35若m是X上的概率分布，即這時信任測度與似然測度均為概率測度，于是顯然，這時的不協(xié)調(diào)度與香農(nóng)信息量（即信息熵）一致。此時的不協(xié)調(diào)度就是不確定度。不協(xié)調(diào)度（續(xù)）若m是X上的概率分布，即這時信任測度與似然測度均為概率測度，362、混淆度

定義4.18(混淆度)設(shè)m是X上的mass函數(shù)，B為由m生成的信任測度，即稱為[X,m]的混淆度。其中，={A|m(A)>0}。【注】：與不協(xié)調(diào)度相似，當(dāng)m是概率分布時，混淆度即為不確定度（香農(nóng)信息熵）。2、混淆度稱為[X,m]的混淆度。其中，={A|373、信息量

一個概念是內(nèi)涵與外延的統(tǒng)一體。內(nèi)涵的多少表示了信息量的大小，但是內(nèi)涵一般是無法度量的。由于內(nèi)涵與外延是某種相反關(guān)系，我們可用外延補(bǔ)集作為信息，用外延補(bǔ)集的測度作為信息量。于是就得到如下信息量的概念。定義4.19(信息量)設(shè)X是有限集，包含n個元素。P是X上的概率分布，稱是[X,P]的信息量。其中，3、信息量是[X,P]的信息量。其中，38

在不確定性推理過程中，經(jīng)常遇到兩類問題：(1)匹配（檢索）問題，需要相似度的概念；(2)推理規(guī)則的條件與結(jié)論之間的蘊(yùn)涵關(guān)系，就需要蘊(yùn)涵度的概念。經(jīng)專家研究發(fā)現(xiàn)，相似度與蘊(yùn)涵度的共性即為包含度?！咀ⅰ浚罕菊n件只簡要介紹上述三個概念的定義，有關(guān)包含度理論的詳細(xì)論述請參見文獻(xiàn)：張文修、梁怡《不確定性推理原理》，西安交通大學(xué)出版社，1996。補(bǔ)充說明：在不確定性推理過程中，經(jīng)常遇到兩類問題：補(bǔ)充說明394、包含度

設(shè)X是一個普通集合，(X)表示X中所有子集的全體，(X)表示X中模糊集合的全體。定義4.19(包含度)：設(shè)0(X)(X)，對A,B0(X)有數(shù)D(B/A)對應(yīng)，且滿足：

(1)0<=D(B/A)<=1

(2)對A,B0(X),A

B時，有D(B/A)=1

(3)對A,B,C0(X),A

B

C時，有 D(A/C)D(A/B)稱D為0(X)上的包含度。【注】：關(guān)于包含度的數(shù)學(xué)原理請詳見張文修《不確定性推理原理》。BACX4、包含度BACX404.6.1Shannon信息論信息論的創(chuàng)立1948年Shannon首次提出以數(shù)學(xué)方法度量并研究通信信號

信息論對不確定性推理的作用為不確定性知識的度量提供理論依據(jù)用信息熵來衡量不確定性程度的高低在決策樹等方法中發(fā)揮重要作用4.6信息論及其在決策樹中的應(yīng)用4.6.1Shannon信息論4.6信息論及其在決策414.6.2信息論中的基本概念定義4.13（自信息量）在收到ai之前，收信者對信源發(fā)出ai的不確定性定義為信息符號ai的自信息量I(ai)。即其中，p(ai)為信源發(fā)出ai的概率，為表達(dá)簡便起見，本課件的對數(shù)lg均以2為底。

【說明】:（1）自信息量只能反映符號的不確定性。（2）有的文獻(xiàn)采用以10或e為底的對數(shù)，但是在某個具體的信息系統(tǒng)中，一旦確定并保持某個底數(shù)，對不確定性信息的度量和計算不會有任何影響。4.6.2信息論中的基本概念其中，p(ai)為信源發(fā)出a42定義4.14（信息熵）設(shè)r為信源X所有可能的符號數(shù)，p(ai)為信源發(fā)出ai的概率，則信源每發(fā)一個符號所提供的平均自信息量即為信息熵?！菊f明】：（1）信息熵也稱香農(nóng)信息量，或稱不確定度。（2）信息熵可用來度量整個信源X整體的不確定性。Shannon信息熵定義4.14（信息熵）設(shè)r為信源X所有可能的符號數(shù)，43定義4.15（條件熵）如果信源X與隨機(jī)變量Y不是相互獨(dú)立的，那么用條件熵H(X|Y)來度量收信者在收到隨機(jī)變量Y之后，對隨機(jī)變量X仍然存在的不確定性。設(shè)X對應(yīng)信源符號ai，Y對應(yīng)信源符號bj，p(ai|bj)為當(dāng)Y為bj時X為ai的概率，則有可得由于定義4.15（條件熵）如果信源X與隨機(jī)變量Y不是相互44定義4.16（平均互信息量，也稱信息論測度值）表示信號Y所能提供的關(guān)于X的信息量的大小，用I(X,Y)表示【說明】：信息論在決策樹學(xué)習(xí)中具有非常重要的意義。在決策樹學(xué)習(xí)方法中，最關(guān)鍵的問題就是如何根據(jù)每個屬性提供的信息量構(gòu)造出一棵決策樹，以此對整個實(shí)例空間進(jìn)行合理的分類（劃分）。平均互信息量定義4.16（平均互信息量，也稱信息論測度值）表示信454.6.3信息論在決策樹中的應(yīng)用

設(shè)訓(xùn)練實(shí)例集為X，目的是將訓(xùn)練實(shí)例分為n類。設(shè)屬于第i類的訓(xùn)練實(shí)例個數(shù)是Ci，X中總的訓(xùn)練實(shí)例個數(shù)為|X|，若記一個實(shí)例屬于第i類的概率為P(Ci)，則此時，決策樹對劃分C的不確定程度為：【注意】：在無混淆的情況下，習(xí)慣將H(X,C)簡記為H(X)。4.6.3信息論在決策樹中的應(yīng)用此時，決策樹對劃分C的不46

決策樹學(xué)習(xí)過程就是使得決策樹對劃分的不確定程度逐漸減小的過程。大致過程如下：

（1）選擇測試屬性a進(jìn)行測試，在得知a=aj的情況下，屬于第i類的實(shí)例個數(shù)為Cij個。記p(Ci;a=aj)=Cij/|X|p(Ci;a=aj)為在測試屬性a的取值為aj時它屬于第i類的概率。此時決策樹對分類的不確定程度就是訓(xùn)練實(shí)例集對屬性X的條件熵。決策樹的學(xué)習(xí)過程決策樹學(xué)習(xí)過程就是使得決策樹對劃分的不確定程度47訓(xùn)練實(shí)例集對屬性X的條件熵的計算公式即訓(xùn)練實(shí)例集對屬性X的條件熵的計算公式即48可知屬性a對于分類提供的信息量I(X;a)為：（2）信息量I(X;a)的值越大，說明選擇測試屬性a對于分類提供的信息量越大，選擇屬性a之后對分類的不確定程度越小。（3）依次類推，不斷地計算剩余樣本的條件熵及信息量，直至構(gòu)造出完整的決策樹。決策樹的學(xué)習(xí)過程（續(xù)）可知屬性a對于分類提供的信息量I(X;a)為：（2）494.6.4信息熵在決策樹中的應(yīng)用實(shí)例—ID3算法屬性O(shè)utlook TemperatureHumidity Windy類

Overcast Hot HighNotN

Overcast Hot HighVeryN

OvercastHot High MediumNSunny Hot HighNotPSunny Hot High MediumPRain Mild High NotNRain Mild High MediumNRain Hot NormalNotPRain Cool NormalMediumNRain Hot NormalVeryNSunny Cool NormalVeryPSunny Cool NormalMediumP4.6.4信息熵在決策樹中的應(yīng)用實(shí)例—ID3算法屬性5013 Overcast Mild High Not N14Overcast Mild High MediumN15

Overcast Cool NormalNotP16 Overcast Cool NormalMediumP17Rain Mild NormalNotN18Rain Mild NormalMediumN19Overcast Mild NormalMediumP20Overcast Mild NormalVeryP21Sunny Mild High Veryp22Sunny Mild High MediumP23Sunny Hot NormalNotP24Rain Mild High VeryN屬性O(shè)utlook TemperatureHumidityWindy類（續(xù)上表）13 Overcast Mild Hig51在決策樹方法中，所要做的工作就是構(gòu)造決策樹將數(shù)據(jù)進(jìn)行分類。因初始時屬于P類和N類的實(shí)例個數(shù)均為12，故初始熵值為：(1)若選擇Outlook作為測試屬性，其條件熵為：本實(shí)例中的條件熵計算過程在決策樹方法中，所要做的工作就是構(gòu)造決策樹將數(shù)據(jù)進(jìn)行52(2)若選擇Temp作為測試屬性，其條件熵為：(3)若選擇Humidity作為測試屬性，其條件熵為：(2)若選擇Temp作為測試屬性，其條件熵為：(3)若選53(4)若選擇Windy作為測試屬性，其條件熵為：

由上述計算結(jié)果可知：

（1）H(X|Outlook)最小，即有關(guān)Outlook的信息對于分類有最大的幫助，提供最大的信息量，故應(yīng)選擇Outlook屬性作為測試屬性。（2）H(X)=H(X|Windy),即I(X;Windy)=0，說明有關(guān)Windy的信息不能提供任何分類信息。（3）選擇Outlook作為測試屬性之后，將訓(xùn)練實(shí)例集分為三個子集，即生成三個節(jié)點(diǎn)，分別對每個節(jié)點(diǎn)依次利用上述過程，即可生成決策樹：(4)若選擇Windy作為測試屬性，其條件熵為：54HumidityPOutlookWindyNPTempNNNNNSunnyOvercastRainHighNormalNotMediumVeryCoolMildHot依據(jù)信息熵對上述實(shí)例集進(jìn)行訓(xùn)練所生成的決策樹HumidityPOutlookWindyNPTempNNN55【補(bǔ)充說明】：

（1）有關(guān)“決策樹”（Decisiontree）的詳細(xì)內(nèi)容，請參見史忠植《知識發(fā)現(xiàn)》（清華大學(xué)出版社，2002年）中的“第2章決策樹”（pp21-56）和《高級人工智能》中的“決策樹學(xué)習(xí)”pp116-121。（2）決策樹方法的幾個有代表性的研究成果分別是：

a)1966年Hunt等人提出的早期決策樹學(xué)習(xí)算法——CLS學(xué)習(xí)算法；

b)1979年Quinlan提出的以信息熵的下降速度作為選取測試屬性的標(biāo)準(zhǔn)的ID3算法。

c)1986年Schlimmer等人構(gòu)造了ID4算法，該算法允許遞增式構(gòu)造決策樹。d)1986年Utgoff提出ID5算法，它允許通過修改決策樹來增加新的訓(xùn)練實(shí)例，而無需重建決策樹。【補(bǔ)充說明】：56[1]QuinlanJ.R.Discoveringrulesfromlargecollectionsofexamples:acasestudy.In:MichieD.ed.ExpertSystemsintheMicroElectronicAge,EdinburghUniversityPress,1979.[2]QuinlanJ.R.Learningefficientclassificationproceduresandtheirapplicationtochessandgames.In:Michalski,R.S.etc,eds.MachineLearning:AnArtificialIntelligenceApproach,Tioga,1983.[3]QuinlanJ.R.Inductionofdecisiontrees.MachineLearning,1986,1(1):81.與決策樹相關(guān)的經(jīng)典文獻(xiàn)[1]QuinlanJ.R.Discovering57[4]Schlimmer,J.C.,Fisher,D.Acasestudyofincrementalconceptinduction.in:ProceedingsofAAAI-86,1986.[5]Schlimmer,J.C.,Grander,R.H.Incrementallearningfromnoisydata.MachineLearning,1987,1(3):318.[6]Utgoff,P.E.ID5:AnincrementalID3.in:ProceedingsofICML-88,SanMateo,CA,1988.[7]Utgoff,P.E.Perceptrontrees:Acasestudyinhybridconceptrepresentations.in:ProceedingsofAAAI-88,SaintPaul,Minnesota,1988.與決策樹相關(guān)的經(jīng)典文獻(xiàn)（續(xù)）[4]Schlimmer,J.C.,Fisher,584.7

模糊推理主要參考文獻(xiàn)模糊推理的發(fā)展簡況模糊集合及其運(yùn)算模糊邏輯模糊推理模糊推理的神經(jīng)網(wǎng)絡(luò)算法4.7模糊推理主要參考文獻(xiàn)594.7.1主要參考文獻(xiàn)高濟(jì).基于知識的軟件智能化技術(shù).浙江大學(xué)出版社,2000.pp.201-213張文修,梁怡.不確定性推理原理.西安交通大學(xué)出版社,1996.pp.207-2544.7.1主要參考文獻(xiàn)高濟(jì).基于知識的軟件智能化技術(shù).604.7.2模糊推理的發(fā)展簡況1965，L.A.Zadeh發(fā)表“FuzzySets”論文，提出模糊集理論1966，Marinos首先提出“模糊邏輯”的概念1969，Guguen研究不精確概念的邏輯問題后來，Zadeh又提出可能度理論隨后，Dubois&Prade發(fā)展了基于可能度的模糊推理1974，E.H.Mamdani提出了模糊控制，并給出著名的Mamdani算法4.7.2模糊推理的發(fā)展簡況1965，L.A.Zad614.7.3模糊集合及其運(yùn)算基本思想把傳統(tǒng)集合論中由特征函數(shù)決定的絕對隸屬關(guān)系模糊化元素x對子集A的隸屬度可[0,1]上的任何值，以指示元素x隸屬于子集A的模糊程度定義在論域U上定義一個模糊集A，其對U的任意元素x均指定一個值uA(x)∈[0,1]，以表示它對A的隸屬程度

uA：→

[0,1]

（uA—A的隸屬函數(shù)）

A

={x/uA(x)}4.7.3模糊集合及其運(yùn)算基本思想62模糊集合及其運(yùn)算（續(xù)1）當(dāng)U={x1,x2,…,xn}，模糊集A可表示為

A

=x1/uA(x1)+x2/uA(x2)+…+xn/uA(xn)uA(xi)=0的項可省略隸屬度的概念是構(gòu)成模糊集理論的基石模糊集運(yùn)算公式uA∪B(x)=max[uA(x),uB(x)]uA∩B(x)=min[uA(x),uB(x)]u~A(x)=1-uA(x)模糊集合及其運(yùn)算（續(xù)1）當(dāng)U={x1,x2,…,x63模糊集合及其運(yùn)算（續(xù)2）模糊集隸屬函數(shù)舉例論域：人的年齡以定性（模糊）術(shù)語描述年齡，值域?yàn)椋耗挲g={青，中，老}隸屬函數(shù)：uY,uM,uO圖形表示01305065YMOu年齡（歲）模糊集合及其運(yùn)算（續(xù)2）模糊集隸屬函數(shù)舉例01305065Y644.7.4模糊邏輯基本思想由定性術(shù)語構(gòu)成模糊命題定性術(shù)語由隸屬函數(shù)表示對模糊命題進(jìn)行合取、析取、取反等邏輯操作基本公式uP∨

=max[uP1(xp1),uP2(xp2),…,uPm(xpm)](析取)uP∧

=min[uP1(xp1),uP2(xp2),…,uPm(xpm)]（合取）u~Pi(xpi)=1-uPi(xpi)（取反）4.7.4模糊邏輯基本思想654.7.5模糊推理模糊關(guān)系uR:U1×U2×…×Un→[0,1]R={(XU1,XU2,…,XUn)/uR(XU1,XU2,…,XUn)}模糊推理方法主流方法：基于max-min原則的算法直接基于模糊規(guī)則的推理基于模糊關(guān)系的推理4.7.5模糊推理模糊關(guān)系66直接基于模糊規(guī)則的推理適用條件：當(dāng)模糊推理的輸入信息為量化數(shù)值時推理原理階段一：計算每條模糊規(guī)則的結(jié)論步驟1：輸入量模糊化，即求出輸入量相對于語言變量各定性值的隸屬度步驟2：計算規(guī)則前提部分模糊命題的邏輯組合步驟3：將規(guī)則前提邏輯組合的隸屬度與結(jié)論命題的隸屬函數(shù)做min運(yùn)算，求得結(jié)論的模糊程度。階段二對所有規(guī)則結(jié)論的模糊程度做max運(yùn)算，得到模糊推理結(jié)果。直接基于模糊規(guī)則的推理適用條件：當(dāng)模糊推理的輸入信息為量化數(shù)67直接基于模糊規(guī)則的推理舉例請參見高濟(jì)教授編著的教材《基于知識的軟件智能化技術(shù)》pp205-206基本要求：能熟練解答類似的模糊推理習(xí)題直接基于模糊規(guī)則的推理舉例請參見高濟(jì)教授編著的教材《基于知識68基于模糊關(guān)系的推理適用條件：當(dāng)模糊推理的輸入信息為定性術(shù)語時Mamdani模糊推理方法階段一：關(guān)系生成規(guī)則模糊規(guī)則為：P=>H，令R(P;H)為從P推出H的模糊關(guān)系R(P;H)=AP×AH={(xP,xH)/uR(xP,xH)}uR(xP,xH)=uAp(xP)∧uAH(xH)階段二：推理合成規(guī)則（max-min復(fù)合運(yùn)算）當(dāng)實(shí)際的輸入信息為模糊命題P’時，則模糊推理的輸出H’AH’=AP’

·R(P;H)可得基于模糊關(guān)系的推理適用條件：當(dāng)模糊推理的輸入信息為定性術(shù)語時69基于模糊關(guān)系的推理舉例請參見高濟(jì)教授編著的教材《基于知識的軟件智能化技術(shù)》pp206-208有興趣的同學(xué)可進(jìn)一步參考張文修、梁怡編著的《不確定性推理原理》pp228-235中的“5-4Mamdani模糊推理”基本要求：能熟練解答與高濟(jì)教授教材中類似的模糊推理習(xí)題基于模糊關(guān)系的推理舉例請參見高濟(jì)教授編著的教材《基于知識的軟704.7.6模糊推理的神經(jīng)網(wǎng)絡(luò)算法特別聲明這一節(jié)屬于補(bǔ)充材料，考試時不做要求感興趣的同學(xué)可參見張文修、梁怡編著的《不確定性推理原理》pp244-248中的“5-7模糊推理的神經(jīng)網(wǎng)絡(luò)算法”模糊推理的神經(jīng)網(wǎng)絡(luò)算法思想將“Ai=>Bi”規(guī)則作為第i個輸入，則形成一個神經(jīng)網(wǎng)絡(luò)可通過神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)算法得到權(quán)重wi4.7.6模糊推理的神經(jīng)網(wǎng)絡(luò)算法特別聲明71模糊推理的神經(jīng)網(wǎng)絡(luò)算法學(xué)習(xí)過程當(dāng)Y是單點(diǎn)集{y}時，訓(xùn)練模型為(A,B)，學(xué)習(xí)算法的過程如下：步1：給出初始權(quán)重w1和訓(xùn)練樣本H=(A,B)步2：利用如下公式計算步3：若B’(y)=B(y)

，則終止；否則，修正w1;步4：若上述過程進(jìn)行到第k步，得到Wk=(wk1,wk2,…,wkn)，使得則終止，其中，gk為形成的模糊測度，即gk(i)=wki；否則，修正權(quán)重wki。【注】：權(quán)重修正方法詳見張文修、梁怡編著的《不確定性推理原理》pp246模糊推理的神經(jīng)網(wǎng)絡(luò)算法學(xué)習(xí)過程當(dāng)Y是單點(diǎn)集{y}時，訓(xùn)練模型72THANKSFORYOURPRESENCE!“Butseekfirsthiskingdomandhisrighteousness,andallthesethingswillbegiventoyouaswell.Thereforedonotworryabouttomorrow,fortomorrowwillworryaboutitself.Eachdayhasenoughtroubleofitsown.”

fromMATTHEW6:33-34NIVTHANKSFORYOURPRESENCE!“But73浙江大學(xué)研究生《人工智能引論》課件徐從富(CongfuXu)

PhD,AssociateProfessorEmail:xucongfu@InstituteofArtificialIntelligence,CollegeofComputerScience,ZhejiangUniversity,Hangzhou310027,P.R.ChinaMarch10,2002第一稿April18,2007第四次修改稿第四講不確定性推理概述

(Chapter4UncertaintyReasoning)浙江大學(xué)研究生《人工智能引論》課件徐從富(CongfuXu74Outline本章的主要參考文獻(xiàn)基本概念基本問題不確定性推理方法的分類不確定性度量的測度理論不確定性的其它度量方法Shannon信息熵及在決策樹中的應(yīng)用模糊推理Outline本章的主要參考文獻(xiàn)75[1]王永慶.人工智能原理與方法.西安交通大學(xué)出版社,1998.pp156-252.(偏重基本概念)[2]張文修,梁怡.不確定性推理原理.西安交通大學(xué)出版社,1996.（偏重數(shù)學(xué)原理）[3]陸汝鈐.人工智能(下冊).

科學(xué)出版社,2000.pp1133-1170.（偏重Bayes概率推理、可信度、模糊推理）[4]史忠植.知識發(fā)現(xiàn).清華大學(xué)出版社,2002.pp24-26,pp141-202.（偏重Roughset和貝葉斯網(wǎng)絡(luò)）本章的主要參考文獻(xiàn)[1]王永慶.人工智能原理與方法.西安交通大學(xué)出版社76[5]Mitchell,T.M.著,曾華軍等譯.機(jī)器學(xué)習(xí).機(jī)械工業(yè)出版社,2003.pp112-143.（偏重貝葉斯學(xué)習(xí)）[6]Russell,S.,Norvig,P.ArtificialIntelligence:AModernApproach.人民郵電出版社,2002.pp413-522.（偏重貝葉斯網(wǎng)絡(luò)及其應(yīng)用）本章的主要參考文獻(xiàn)（續(xù)）“BlessedisthenationwhoseGodistheLORD,thepeoplehechoseforhisinheritance.”

FromPSALMS33:12NIV

[5]Mitchell,T.M.著,曾華軍等譯.774.1.1精確推理的局限性推理依據(jù)已知事實(shí)（證據(jù)）、相關(guān)知識（規(guī)則）證明某個假設(shè)成立or不成立

精確推理及其不足將原本為不確定性的關(guān)系“硬性”轉(zhuǎn)化為精確關(guān)系將原本不存在明確界限的事物“人為”劃定界限歪曲了現(xiàn)實(shí)情況的本來面目舍棄了事物的某些重要屬性失去了真實(shí)性4.1基本概念4.1.1精確推理的局限性4.1基本概念784.1.2不確定性推理的定義及意義1.定義也稱“不精確性推理”從不確定性的初始證據(jù)（即已知事實(shí)）出發(fā)運(yùn)用不確定性的知識（或規(guī)則）推出具有一定程度的不確定性但卻是合理或近乎合理的結(jié)論2.意義使計算機(jī)對人類思維的模擬更接近于人類的真實(shí)思維過程4.1.2不確定性推理的定義及意義1.定義794.2不確定性推理中的基本問題不確定性的表示與度量不確定性匹配不確定性的傳遞算法不確定性的合成4.2不確定性推理中的基本問題不確定性的表示與度量804.2.1不確定性的表示與度量1.不確定性的表示選擇不確定性表示方法時應(yīng)考慮的因素充分考慮領(lǐng)域問題的特征恰當(dāng)?shù)孛枋鼍唧w問題的不確定性滿足問題求解的實(shí)際需求便于推理過程中對不確定性的推算4.2.1不確定性的表示與度量1.不確定性的表示81不確定性的表示與度量（續(xù)1）2.不確定性的度量針對不同的領(lǐng)域問題采用不同的度量方法用不同的數(shù)值刻畫不同的不確定性程度事先規(guī)定不確定性程度的取值范圍3.常用的度量方法測度理論（基于概率統(tǒng)計的度量方法）Shannon信息熵其它度量方法……不確定性的表示與度量（續(xù)1）2.不確定性的度量82不確定性的表示與度量（續(xù)2）在選擇不確定性度量方法時應(yīng)考慮的因素：充分表達(dá)相應(yīng)知識及證據(jù)不確定性的程度度量范圍便于領(lǐng)域?qū)＜壹坝脩艄烙嫴淮_定性便于計算過程中的不確定性傳遞，結(jié)論的不確定性度量不超出規(guī)定的范圍度量的確定應(yīng)直觀，且有相應(yīng)的理論依據(jù)不確定性的表示與度量（續(xù)2）在選擇不確定性度量方法時應(yīng)考慮的834.2.2不確定性匹配解決不確定性匹配的常用方法設(shè)計一個匹配算法用以計算相似度指定一個相似度的“限定”（即閾值）“TodowhatisrightandjustismoreacceptabletotheLORDthansacrifice.”

FromPROVERBS21:3NIV

4.2.2不確定性匹配“Todowhatisri844.2.3證據(jù)不確定性的組合單一證據(jù)&

組合證據(jù)單一證據(jù)：前提條件僅為一個簡單條件組合證據(jù)：一個復(fù)合條件對應(yīng)于一組證據(jù)前提條件用AND（與）或OR（或）把多個簡單條件連接起來構(gòu)成復(fù)合條件4.2.3證據(jù)不確定性的組合85（1）最大最小法T(E1ANDE2)=min{T(E1),T(E2)}T(E1ORE2)=max{T(E1),T(E2)（2）概率方法（要求事件之間完全獨(dú)立）

T(E1ANDE2)=T(E1)×T(E2)T(E1ORE2)=T(E1)+T(E2)-T(E1)×T(E2)（3）有界方法T(E1ANDE2)=max{0,T(E1)+T(E2)-1}T(E1ORE2)=min{1,T(E1)+T(E2)}【注】：上述T(E)表示證據(jù)E為真的程度，如可信度、概率等。每組公式都有相應(yīng)的適用范圍和使用條件。常用的組合證據(jù)不確定性計算方法（1）最大最小法常用的組合證據(jù)不確定性計算方法864.2.4不確定性的傳遞包含兩個子問題在每一步推理中，如何把證據(jù)及知識的不確定性傳遞給給結(jié)論在多步推理中，如何把初始證據(jù)的不確定性傳遞給最終結(jié)論4.2.4不確定性的傳遞874.2.5結(jié)論不確定性的合成用不同知識進(jìn)行推理得到相同的結(jié)論同個結(jié)論的不確定性程度卻不相同需要用合適的算法對它們進(jìn)行合成4.2.5結(jié)論不確定性的合成884.3不確定性推理方法的分類4.3.1不確定性推理的兩條研究路線模型方法在推理一級上擴(kuò)展確定性推理不確定證據(jù)和知識與某種度量標(biāo)準(zhǔn)對應(yīng)給出更新結(jié)論不確定性的算法構(gòu)成相應(yīng)的不確定性推理模型控制方法在控制策略一級上處理不確定性無統(tǒng)一的不確定性處理模型，其效果依賴于控制策略4.3不確定性推理方法的分類4.3.1不確定性推理894.3.2不確定性推理方法的分類不確定性推理模型方法控制方法數(shù)值方法非數(shù)值方法概率統(tǒng)計方法模糊推理方法粗糙集方法絕對概率方法貝葉斯方法證據(jù)理論方法HMM方法發(fā)生率計算相關(guān)性制導(dǎo)回溯、機(jī)緣控制、啟發(fā)式搜索等可信度方法4.3.2不確定性推理方法的分類不確定性推理模型控制數(shù)值非904.3.3關(guān)于不確定性推理方法的說明數(shù)值方法對不確定性的一種定量表示和處理方法其研究及應(yīng)用較多，已形成多種應(yīng)用模型非數(shù)值方法除數(shù)值方法外的其它處理不確定性的模型方法典型代表：“發(fā)生率計算方法”，它采用集合來描述和處理不確定性，且滿足概率推理的性質(zhì)4.3.3關(guān)于不確定性推理方法的說明91關(guān)于不確定性推理方法的說明（續(xù)1）概率統(tǒng)計方法有完整、嚴(yán)密的數(shù)學(xué)理論為不確定性的合成與傳遞提供了現(xiàn)成的數(shù)學(xué)公式最早、最廣泛地用于不確定性知識的表示與處理已成為不確定性推理的重要手段證據(jù)理論方法1967年Dempster首次提出，1976年Shafer完善可表示并處理“不知道”等不確定性信息關(guān)于不確定性推理方法的說明（續(xù)1）92關(guān)于不確定性推理方法的說明（續(xù)2）模糊推理方法可表示并處理由模糊性引起的不確定性已廣泛應(yīng)用于不確定性推理粗糙集理論方法1981年Z.Pawlak首次提出一種新的可表示并處理“含糊”等不確定性的數(shù)學(xué)方法可用于不確定性推理、數(shù)據(jù)挖掘等領(lǐng)域關(guān)于不確定性推理方法的說明（續(xù)2）934.4描述不確定性信息的測度理論4.4.1測度及其分類

設(shè)(X)是有限集合X上的子集合的全體，測度的定義如下：定義6.1（測度）若g:(X)[0,1]滿足條件： (1)g(X)=1; (2)當(dāng)AB=時，有 g(AB)=g(A)+g(B)+g(A)g(B)稱為g測度?！咀ⅰ浚宏P(guān)于測度理論的詳細(xì)論述請參見夏道行編著的《實(shí)變函數(shù)與泛函分析》，復(fù)旦大學(xué)出版社。4.4描述不確定性信息的測度理論94定義4.2（模糊測度）模糊測度被定義為一個映射M:(X)[0,1]具有如下性質(zhì)：(1)有界性：M()=0,M(X)=1;(2)單調(diào)性：對任意A,B(X),AB時，有M(A)M(B)由模糊測度定義可知：

（1）有界性表示：一個非空元素不可能屬于，它必然屬于全集；（2）單調(diào)性表示：一個元素隸屬于一個集合的確定度不大于它隸屬于更大的一個集合的確定度。定義4.2（模糊測度）模糊測度被定義為一個映射95定理4.1當(dāng)>-1時，測度g是模糊測度。定理4.2當(dāng)>-1時，測度g具有如下性質(zhì)：模糊測度及其性質(zhì)定理4.1當(dāng)>-1時，測度g是模糊測度。模糊測度96定義4.3（概率測度）稱P：(X）→[0，1]為概率測度，若滿足：（1）有界性：P(X)=1（2）可加性：A∩B=Φ時，P(A∪B)=P(A)+P(B)【注】：可證明概率測度是＝0時模糊測度。定義4.4

(條件概率)如果P是X上的概率測度，EX，且P(E)>0，稱為給定條件E下，事件A發(fā)生的條件概率。定義4.3（概率測度）稱P：(X）→[0，1]為97

對于條件概率有如下聯(lián)合概率公式：

若A1,A2,...,An為X中的n個事件，可得

若A,B兩個事件滿足P(A|B)=P(A)，即A發(fā)生的可能性與B無關(guān)，稱A,B是相互獨(dú)立的。這時有

若n個事件A1,A2,...,An相互獨(dú)立，則對于條件概率有如下聯(lián)合概率公式：若A1,98Markov條件獨(dú)立性定義4.5(馬氏條件獨(dú)立性)若A1,A2,...,An是按時間順序發(fā)生的一系列事件，而且具有如下特性：未來某一事件Ak+1發(fā)生的可能性只依賴于當(dāng)前時刻的事件Ak，而與過去發(fā)生的事件無關(guān)，即這時稱n個事件具有馬氏（Markov）獨(dú)立性。對n個滿足馬氏獨(dú)立性條件的事件滿足Markov條件獨(dú)立性定義4.5(馬氏條件獨(dú)立性)99定義4.6（全概率公式）設(shè)Hi(i<=m)是X上的分劃，HiHj(ij)，且H1H2…

Hm=X。由概率可加性，對于任意事件A，有

對于條件概率有如下全概率公式：

定義4.7

(后驗(yàn)概率公式）

：Bayes公式定義4.6（全概率公式）設(shè)Hi(i<=m)是X上的分100Bayes公式與全概率公式的區(qū)別全概率公式由原因到結(jié)果的計算公式不如Bayes公式使用廣泛Bayes公式后驗(yàn)概率公式已知某結(jié)果發(fā)生，尋求這個結(jié)果發(fā)生的原因在實(shí)際問題中有著十分重要的應(yīng)用Bayes公式與全概率公式的區(qū)別101定義4.8（信任測度）設(shè)X是有限集，稱B：(X)[0,1]為信任測度，若滿足：(1)B()=0,B(X)=1;(2)對于X中任意子集A1，A2，…，An有如果僅僅滿足，對于X中任意兩個子集A1及A2有稱為弱信任測度?！咀ⅰ浚嚎勺C明信任測度與弱信任測度都是模糊測度。信任測度是證據(jù)理論的最基礎(chǔ)概念。定義4.8（信任測度）設(shè)X是有限集，稱B：(X)102定義4.9（似然測度）設(shè)X是有限集，稱L：(X)[0,1]為似然測度，若滿足：(1)L()=0,L(X)=1;(2)對于X中任意子集A1，A2，…，An有如果僅僅滿足，對于X中任意兩個子集A1及A2有稱為弱似然測度。【注】：可證明似然測度與弱似然測度都是模糊測度。似然測度是證據(jù)理論的最基礎(chǔ)概念。定義4.9（似然測度）設(shè)X是有限集，稱L：(X)103定義4.10（mass函數(shù)）稱m：(X)→[0，1]是mass函數(shù)，若滿足：（1）m(Ф)=0（2）mass函數(shù)是專家的一種評價或確認(rèn)程度。比如X={x1,x2,…,xn}是n中疾病，某專家認(rèn)為某人得疾病x1的可能性為0.7，于是得到一個mass函數(shù)：在證據(jù)理論中，mass函數(shù)對構(gòu)造信任測度與似然測度中有著重要的作用。定義4.10（mass函數(shù)）稱m：(X)→[0，1]是m104定義4.11（必然性測度）設(shè)X是有限集，稱N：(X)[0,1]為必然性測度，若滿足：(1)N()=0,N(X)=1;(2)N(AB)=N(A)N(B)定義4.12（可能性測度）設(shè)X是有限集，稱：(X)[0,1]為可能性測度，若滿足：(1)()=0,(X)=1;(2)(AB)=(A)(B)【注】：可證明必然測度與可能性測度都是模糊測度。它們是Zadel提出的可能性理論的最基礎(chǔ)概念。定義4.11（必然性測度）設(shè)X是有限集，稱N：(X)105概率測度必然測度可能測度信任測度似然測度模糊測度各種模糊測度之間的關(guān)系示意圖4.4.2模糊測度各類之間的關(guān)系概率測度必然測度可能測度信任測度似然測度模糊測度各種模糊測度106模糊測度各類之間的關(guān)系（續(xù)）模糊測度是一大類測度，它除了有界性條件外，只要求測度滿足單調(diào)性，即當(dāng)AB時，有M(A)M(B)。上述各類模糊測度之間的關(guān)系如下：必然性測度一定是信任測度可能性測度一定是似然測度概率測度是信任測度與似然測度的交集……模糊測度各類之間的關(guān)系（續(xù)）模糊測度是一大類測度，1074.5不確定性的其它度量方法1、不協(xié)調(diào)度定義4.17(不協(xié)調(diào)度)設(shè)m是X上的mass函數(shù)，L為由m生成的似然測度，即稱為[X,m]的不協(xié)調(diào)度。4.5不確定性的其它度量方法稱為[X,m]的不協(xié)調(diào)度。108若m是X上的概率分布，即這時信任測度與似然測度均為概率測度，于是顯然，這時的不協(xié)調(diào)度與香農(nóng)信息量（即信息熵）一致。此時的不協(xié)調(diào)度就是不確定度。不協(xié)調(diào)度（續(xù)）若m是X上的概率分布，即這時信任測度與似然測度均為概率測度，1092、混淆度

定義4.18(混淆度)設(shè)m是X上的mass函數(shù)，B為由m生成的信任測度，即稱為[X,m]的混淆度。其中，={A|m(A)>0}?！咀ⅰ浚号c不協(xié)調(diào)度相似，當(dāng)m是概率分布時，混淆度即為不確定度（香農(nóng)信息熵）。2、混淆度稱為[X,m]的混淆度。其中，={A|1103、信息量

一個概念是內(nèi)涵與外延的統(tǒng)一體。內(nèi)涵的多少表示了信息量的大小，但是內(nèi)涵一般是無法度量的。由于內(nèi)涵與外延是某種相反關(guān)系，我們可用外延補(bǔ)集作為信息，用外延補(bǔ)集的測度作為信息量。于是就得到如下信息量的概念。定義4.19(信息量)設(shè)X是有限集，包含n個元素。P是X上的概率分布，稱是[X,P]的信息量。其中，3、信息量是[X,P]的信息量。其中，111

在不確定性推理過程中，經(jīng)常遇到兩類問題：(1)匹配（檢索）問題，需要相似度的概念；(2)推理規(guī)則的條件與結(jié)論之間的蘊(yùn)涵關(guān)系，就需要蘊(yùn)涵度的概念。經(jīng)專家研究發(fā)現(xiàn)，相似度與蘊(yùn)涵度的共性即為包含度?！咀ⅰ浚罕菊n件只簡要介紹上述三個概念的定義，有關(guān)包含度理論的詳細(xì)論述請參見文獻(xiàn)：張文修、梁怡《不確定性推理原理》，西安交通大學(xué)出版社，1996。補(bǔ)充說明：在不確定性推理過程中，經(jīng)常遇到兩類問題：補(bǔ)充說明1124、包含度

設(shè)X是一個普通集合，(X)表示X中所有子集的全體，(X)表示X中模糊集合的全體。定義4.19(包含度)：設(shè)0(X)(X)，對A,B0(X)有數(shù)D(B/A)對應(yīng)，且滿足：

(1)0<=D(B/A)<=1

(2)對A,B0(X),A

B時，有D(B/A)=1

(3)對A,B,C0(X),A

B

C時，有 D(A/C)D(A/B)稱D為0(X)上的包含度?！咀ⅰ浚宏P(guān)于包含度的數(shù)學(xué)原理請詳見張文修《不確定性推理原理》。BACX4、包含度BACX1134.6.1Shannon信息論信息論的創(chuàng)立1948年Shannon首次提出以數(shù)學(xué)方法度量并研究通信信號

信息論對不確定性推理的作用為不確定性知識的度量提供理論依據(jù)用信息熵來衡量不確定性程度的高低在決策樹等方法中發(fā)揮重要作用4.6信息論及其在決策樹中的應(yīng)用4.6.1Shannon信息論4.6信息論及其在決策1144.6.2信息論中的基本概念定義4.13（自信息量）在收到ai之前，收信者對信源發(fā)出ai的不確定性定義為信息符號ai的自信息量I(ai)。即其中，p(ai)為信源發(fā)出ai的概率，為表達(dá)簡便起見，本課件的對數(shù)lg均以2為底。

【說明】:（1）自信息量只能反映符號的不確定性。（2）有的文獻(xiàn)采用以10或e為底的對數(shù)，但是在某個具體的信息系統(tǒng)中，一旦確定并保持某個底數(shù)，對不確定性信息的度量和計算不會有任何影響。4.6.2信息論中的基本概念其中，p(ai)為信源發(fā)出a115定義4.14（信息熵）設(shè)r為信源X所有可能的符號數(shù)，p(ai)為信源發(fā)出ai的概率，則信源每發(fā)一個符號所提供的平均自信息量即為信息熵?！菊f明】：（1）信息熵也稱香農(nóng)信息量，或稱不確定度。（2）信息熵可用來度量整個信源X整體的不確定性。Shannon信息熵定義4.14（信息熵）設(shè)r為信源X所有可能的符號數(shù)，116定義4.15（條件熵）如果信源X與