第7章-決策樹(shù)與貝葉斯網(wǎng)絡(luò)課件

第七章決策樹(shù)與貝葉斯網(wǎng)絡(luò)

1

決策樹(shù)的形成與發(fā)展1.1簡(jiǎn)介決策樹(shù)方法的起源是概念學(xué)習(xí)系統(tǒng)CLS，然后發(fā)展到ID3方法而為高潮，最后又演化為能處理連續(xù)屬性的C4.5。有名的決策樹(shù)方法還有CART是應(yīng)用最廣的歸納推理算法之一語(yǔ)義可表示性對(duì)噪聲數(shù)據(jù)有很好的健壯性1.2決策樹(shù)的表示法決策樹(shù)通過(guò)把實(shí)例從根節(jié)點(diǎn)排列到某個(gè)葉子節(jié)點(diǎn)來(lái)分類實(shí)例，葉子節(jié)點(diǎn)即為實(shí)例所屬的分類。樹(shù)上的每一個(gè)節(jié)點(diǎn)說(shuō)明了對(duì)實(shí)例的某個(gè)屬性的測(cè)試，并且該節(jié)點(diǎn)的每一個(gè)后繼分支對(duì)應(yīng)于該屬性的一個(gè)可能值。圖1.3構(gòu)造決策樹(shù)決策樹(shù)分類過(guò)程從根節(jié)點(diǎn)開(kāi)始，首先對(duì)某一屬性的取值提問(wèn)?Color?與根節(jié)點(diǎn)相連的不同分支，對(duì)應(yīng)這個(gè)屬性的不同取值?green;yellow;red;根據(jù)不同的回答，轉(zhuǎn)向相應(yīng)的分支?green在新到達(dá)的節(jié)點(diǎn)處做同樣的分支判斷?Size?–big.這一過(guò)程持續(xù)，直到到達(dá)某個(gè)葉節(jié)點(diǎn)，輸出該葉節(jié)點(diǎn)的類別標(biāo)記?Watermelon

2

決策樹(shù)的基本原理：

統(tǒng)計(jì)學(xué)角度2.1決策樹(shù)的判決面2.2構(gòu)造決策樹(shù)?基本過(guò)程?從上到下，分而治之（divide-and-conquer），遞歸生長(zhǎng)

?最初，所有的樣本都在根節(jié)點(diǎn)?所有屬性都是標(biāo)稱型的（如果是連續(xù)數(shù)值型的，則需要先離散化ID3)

?所有樣本根據(jù)每次選擇出的屬性遞歸的逐漸劃分開(kāi)來(lái)

?滿足如下條件之一時(shí)，劃分操作停止

?所有落入某一節(jié)點(diǎn)的樣本均屬于同一類別?沒(méi)有特征能夠進(jìn)一步用于劃分樣本集?沒(méi)有任何樣本落入某一節(jié)點(diǎn)屬性選擇構(gòu)造好的決策樹(shù)的關(guān)鍵在于如何選擇好的邏輯判斷或?qū)傩?。?duì)于同樣一組例子，可以有很多決策樹(shù)能符合這組例子。人們研究出，一般情況下或具有較大概率地說(shuō)，樹(shù)越小則樹(shù)的預(yù)測(cè)能力越強(qiáng)。要構(gòu)造盡可能小的決策樹(shù)，關(guān)鍵在于選擇恰當(dāng)?shù)倪壿嬇袛嗷驅(qū)傩?。由于?gòu)造最小的樹(shù)是NP-難問(wèn)題，因此只能采取用啟發(fā)式策略選擇好的邏輯判斷或?qū)傩浴?/p>

度量標(biāo)準(zhǔn)——熵熵(Entropy)信息論中廣泛使用的一個(gè)度量標(biāo)準(zhǔn)刻畫任意樣例集的純度（purity）一般計(jì)算公式為：對(duì)于二元分類：給定包含關(guān)于某個(gè)目標(biāo)概念的正反樣例的樣例集S，那么S相對(duì)這個(gè)布爾型分類的熵為：

Entropy(S)-plog2p-pΘlog2pΘ其中p是在S中正例的比例，pΘ是在S中負(fù)例的比例。在有關(guān)熵的所有計(jì)算中我們定義0log0為0。例子Entropy=1-(1/6)log(1/6)-(5/6)log(5/6)=0.650Entropy=1-(3/6)log(3/6)-(3/6)log(3/6)=1Entropy=-(0/6)log(0/6)-(6/6)log(6/6)=02.3性能度量——信息增益屬性的信息增益使用這個(gè)屬性分割樣例而導(dǎo)致的期望熵降低的數(shù)量Values(A)是屬性A所有可能值的集合

Sv

是S中屬性A的值為v的子集，即Sv={sS|A(s)=v}當(dāng)對(duì)S的一個(gè)任意成員的目標(biāo)值編碼時(shí)，Gain(S,A)值是在知道屬性A的值后可以節(jié)省的二進(jìn)制位數(shù)例子假設(shè)S是有關(guān)天氣的訓(xùn)練樣例集[9+,5-]其中：wind=weak的樣例是[6+,2-]wind=strong的樣例[+3,-3]問(wèn)題:計(jì)算屬性wind的信息增益S的熵：E(S)=-(9/14)log(9/14)–(5/14)log(9/14)=0.940選擇最好的分類屬性

3

決策樹(shù)經(jīng)典算法介紹ID3算法創(chuàng)建樹(shù)的Root結(jié)點(diǎn)如果Examples都為正，那么返回label=+中的單結(jié)點(diǎn)Root如果Examples都為反，那么返回lable=-單結(jié)點(diǎn)樹(shù)Root如果Attributes為空，那么返回單節(jié)點(diǎn)樹(shù)Root，lable=Examples中最普遍的目標(biāo)屬性值否則開(kāi)始

AAttributes中分類能力最好的屬性

Root的決策屬性A

對(duì)于每個(gè)可能值 在Root下加一個(gè)新的分支對(duì)應(yīng)測(cè)試A=vi

令Example-vi為Examples中滿足A屬性值為vi的子集 如果Examples-vi為空 在這個(gè)新分支下加一個(gè)葉子結(jié)點(diǎn)，節(jié)點(diǎn)的lable=Examples中最普遍的 目標(biāo)屬性值 否則在這個(gè)新分支下加一個(gè)子樹(shù)ID3(example-vi,target- attribute,attributes-|A|結(jié)束返回RootC4.5C4.5是對(duì)ID3的改進(jìn)算法對(duì)連續(xù)值的處理對(duì)未知特征值的處理對(duì)決策樹(shù)進(jìn)行剪枝CARTCART是ClassificationAndRegressionTree的簡(jiǎn)稱，可以處理高度傾斜或多態(tài)的數(shù)值型數(shù)據(jù)，也可處理順序或無(wú)序的類屬型數(shù)據(jù)。CART選擇具有最小gini系數(shù)值的屬性作為測(cè)試屬性，gini值越小，樣本的“純凈度”越高，劃分效果越好。與C4.5算法類似，CART算法也是先建樹(shù)后剪枝，但在具體實(shí)現(xiàn)上有所不同。由于二叉樹(shù)不易產(chǎn)生數(shù)據(jù)碎片，精確度往往高于多叉樹(shù)，因此CART算法采用2分遞歸劃分，在分支節(jié)點(diǎn)上進(jìn)行布爾測(cè)試，判斷條件為真的劃歸左分支，否則劃歸右分支，最終形成一棵二叉決策樹(shù)。對(duì)于連續(xù)屬性A，判斷A≤V是否成立(同C4.5算法)；對(duì)于離散型屬性A，判斷A∈S’是否成立，其中S’是屬性A所有取值的子集，可用貪心算法或窮舉法確定，SLIQ上述算法由于要求訓(xùn)練樣本駐留內(nèi)存，因此不適合處理大規(guī)模數(shù)據(jù)。為此，IBM研究人員提出了一種快速的、可伸縮的、適合處理較大規(guī)模數(shù)據(jù)的決策樹(shù)分類算法SLIQ(SupervisedLearningInQuest)。該算法利用3種數(shù)據(jù)結(jié)構(gòu)來(lái)構(gòu)造樹(shù)，分別是屬性表、類表和類直方圖。屬性表含有兩個(gè)字段：屬性值和樣本號(hào)。類表也含有兩個(gè)字段：樣本類別和樣本所屬葉節(jié)點(diǎn)。類表的第k條記錄對(duì)應(yīng)于訓(xùn)練集中第k個(gè)樣本（樣本號(hào)為k），所以屬性表和類表之間可以建立關(guān)聯(lián)。類表可以隨時(shí)指示樣本所屬的劃分，所以必須長(zhǎng)駐內(nèi)存。每個(gè)屬性都有一張屬性表，可以駐留磁盤。類直方圖附屬在葉節(jié)點(diǎn)上，用來(lái)描述節(jié)點(diǎn)上某個(gè)屬性的類別分布。描述連續(xù)屬性分布時(shí)，它由一組二元組<類別，該類別的樣本數(shù)>組成；描述離散屬性分布時(shí)，它由一組三元組<屬性值，類別，該類別中取該屬性值的樣本數(shù)>組成。隨著算法的執(zhí)行，類直方圖中的值不斷更新。SPRINT與SLIQ算法不同，SPRINT算法采取傳統(tǒng)的深度優(yōu)先生成樹(shù)策略，SLIQ算法要求類表駐留內(nèi)存。當(dāng)訓(xùn)練集增加導(dǎo)致類表放不進(jìn)內(nèi)存時(shí)，算法就無(wú)法進(jìn)行，這限制了SLIQ處理數(shù)據(jù)的最大規(guī)模。為此，IBM研究人員提出可伸縮、可并行化的決策樹(shù)算法SPRINT，它消除了所有內(nèi)存限制，運(yùn)行速度快，且允許多個(gè)處理器協(xié)同創(chuàng)建一個(gè)決策樹(shù)模型。SPRINT定義了兩種數(shù)據(jù)結(jié)構(gòu)，分別是屬性表和直方圖。屬性表由屬性值、類別屬性和樣本號(hào)3個(gè)字段組成，它隨節(jié)點(diǎn)的擴(kuò)展而劃分，并附屬于相應(yīng)的子節(jié)點(diǎn)。直方圖附屬在節(jié)點(diǎn)上，用來(lái)描述節(jié)點(diǎn)上某個(gè)屬性的類別分布。當(dāng)描述連續(xù)屬性的類分布時(shí)，節(jié)點(diǎn)上關(guān)聯(lián)兩個(gè)直方圖Cbelow和Cabove，前者描述已處理樣本的類別分布，后者描述未處理樣本的類別分布，兩者的值皆隨算法進(jìn)行而更新；當(dāng)描述離散屬性的類分布時(shí)，節(jié)點(diǎn)上只關(guān)聯(lián)一個(gè)直方圖countmatrix。

4

決策樹(shù)的應(yīng)用4.1決策樹(shù)的適用范圍和應(yīng)用前景決策樹(shù)法作為一種決策技術(shù)，已被廣泛地應(yīng)用于企業(yè)的投資決策之中，它是隨機(jī)決策模型中最常見(jiàn)、最普及的一種規(guī)策模式和方法此方法，有效地控制了決策帶來(lái)的風(fēng)險(xiǎn)。所謂決策樹(shù)法，就是運(yùn)用樹(shù)狀圖表示各決策的期望值，通過(guò)計(jì)算，最終優(yōu)選出效益最大、成本最小的決策方法。決策樹(shù)法屬于風(fēng)險(xiǎn)型決策方法，不同于確定型決策方法，二者適用的條件也不同。應(yīng)用決策樹(shù)決策方法必須具備以下條件：①具有決策者期望達(dá)到的明確目標(biāo)；

②存在決策者可以選擇的兩個(gè)以上的可行備選方案；

③存在著決策者無(wú)法控制的兩種以上的自然狀態(tài)（如氣候變化、市場(chǎng)行情、經(jīng)濟(jì)發(fā)展動(dòng)向等）；

④不同行動(dòng)方案在不同自然狀態(tài)下的收益值或損失值（簡(jiǎn)稱損益值）可以計(jì)算出來(lái)；

⑤決策者能估計(jì)出不同的自然狀態(tài)發(fā)生概率。決策樹(shù)的應(yīng)用舉例問(wèn)題及數(shù)據(jù)集根據(jù)其他屬性，判斷周六是否玩網(wǎng)球playTennis=Y/N?Step1:確定根節(jié)點(diǎn)分別計(jì)算4個(gè)屬性的信息增益Outlook:0.246=Sunny[2+,3-]=Overcast[4+,0-]=Rain[3+,2-]Wind:0.048=weak的樣例是[6+,2-]=strong的樣例[+3,-3]Humidity:0.151Temperature:0.029因此：根節(jié)點(diǎn)為OutlookStep2:分枝選擇哪個(gè)屬性進(jìn)行劃分？Step3:循環(huán)選擇哪個(gè)屬性進(jìn)行劃分？

5

貝葉斯網(wǎng)絡(luò)的形成與發(fā)展5.1貝葉斯網(wǎng)絡(luò)貝葉斯網(wǎng)絡(luò)是為了處理人工智能研究中的不確定性(uncertainty)問(wèn)題而發(fā)展起來(lái)的。貝葉斯網(wǎng)絡(luò)是將概率統(tǒng)計(jì)應(yīng)用于復(fù)雜領(lǐng)域進(jìn)行不確定性推理和數(shù)據(jù)分析的工具。用概率論處理不確定性的主要優(yōu)點(diǎn)是保證推理結(jié)果的正確性。貝葉斯網(wǎng)絡(luò)的發(fā)展歷史1958年英國(guó)統(tǒng)計(jì)雜志

Biometrika

重新全文刊登了貝葉斯的論文。20世紀(jì)

50年代，以羅賓斯(RobbinsH.)為代表，提出了經(jīng)驗(yàn)貝葉斯方法和經(jīng)典方法相結(jié)合，引起統(tǒng)計(jì)界的廣泛注意，這一方法很快就顯示出它的優(yōu)點(diǎn)，成為很活躍的一個(gè)方向。隨著人工智能的發(fā)展，尤其是機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等興起，為貝葉斯理論的發(fā)展和應(yīng)用提供了更為廣闊的空間。貝葉斯理論的內(nèi)涵也比以前有了很大的變化。20世紀(jì)

80年代貝葉斯網(wǎng)絡(luò)用于專家系統(tǒng)的知識(shí)表示，90年代進(jìn)一步研究可學(xué)習(xí)的貝葉斯網(wǎng)絡(luò)，用于數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)。近年來(lái)，貝葉斯學(xué)習(xí)理論方面的文章更是層出不窮，內(nèi)容涵蓋了人工智能的大部分領(lǐng)域，包括因果推斷、不確定性知識(shí)表達(dá)、模式識(shí)別和聚類分析等。并且出現(xiàn)了專門研究貝葉斯理論的組織和學(xué)術(shù)刊物ISBA。幾個(gè)重要原理鏈規(guī)則(chainrule)貝葉斯定理(Bayes’theorem)利用變量間條件獨(dú)立性

6

貝葉斯網(wǎng)絡(luò)構(gòu)造6.1貝葉斯網(wǎng)絡(luò)的幾個(gè)主要問(wèn)題貝葉斯網(wǎng)絡(luò)概率推理(ProbabilisticInference)結(jié)構(gòu)學(xué)習(xí)(structurelearning)參數(shù)學(xué)習(xí)(Parameterlearning)隱變量及隱結(jié)構(gòu)學(xué)習(xí)(Hiddenvariablesandhiddenstructurelearning)一個(gè)簡(jiǎn)單貝葉斯網(wǎng)絡(luò)例子一個(gè)簡(jiǎn)單貝葉斯網(wǎng)絡(luò)例子計(jì)算過(guò)程：P(y1)=P(y1|x1)P(x1)+P(y1|x2)P(x2)=0.9*0.4+0.8*0.6=0.84P(z1)=P(z1|y1)P(y1)+P(z1|y2)P(y2)=0.7*0.84+0.4*0.16=0.652P(w1)=P(w1|z1)P(z1)+P(w1|z2)P(z2)=0.5*0.652+0.6*0.348=0.5348P(w1|y1)=P(w1|z1)P(z1|y1)+P(w1|z2)P(z2|y1)=0.5*0.7+0.6*0.3=0.53P(w1|y2)=P(w1|z1)P(z1|y2)+P(w1|z2)P(z2|y2)=0.5*0.4+0.6*0.6=0.56P(w1|x1)=P(w1|y1)P(y1|x1)+P(w1|y2)P(y2|x1)=0.53*0.9+0.56*0.1=0.533

該計(jì)算利用向上概率傳播及貝葉斯定理。

為什么要用貝葉斯網(wǎng)絡(luò)進(jìn)行概率推理？理論上，進(jìn)行概率推理所需要的只是一個(gè)聯(lián)合概率分布。但是聯(lián)合概率分布的復(fù)雜度相對(duì)于變量個(gè)數(shù)成指數(shù)增長(zhǎng)，所以當(dāng)變量眾多時(shí)不可行。貝葉斯網(wǎng)絡(luò)的提出就是要解決這個(gè)問(wèn)題。它把復(fù)雜的聯(lián)合概率分布分解成一系列相對(duì)簡(jiǎn)單的模塊，從而大大降低知識(shí)獲取和概率推理的復(fù)雜度，使得可以把概率論應(yīng)用于大型問(wèn)題。統(tǒng)計(jì)學(xué)、系統(tǒng)工程、信息論以及模式識(shí)別等學(xué)科中貝葉斯網(wǎng)絡(luò)特里的多元概率模型：樸素貝葉斯模型，隱類模型，混合模型，隱馬爾科夫模型，卡爾曼濾波器等。動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)主要用于對(duì)多維離散時(shí)間序列的監(jiān)控和預(yù)測(cè)。多層隱類模型，能夠揭示觀測(cè)變量背后的隱結(jié)構(gòu)。例子P(C,S,R,W)=P(C)P(S|C)P(R|S,C)P(W|S,R,C)chainrule=P(C)P(S|C)P(R|C)P(W|S,R,C)since=P(C)P(S|C)P(R|C)P(W|S,R)since貝葉斯網(wǎng)絡(luò)學(xué)習(xí)1.結(jié)構(gòu)學(xué)習(xí)：發(fā)現(xiàn)變量之間的圖關(guān)系，2.參數(shù)學(xué)習(xí)：決定變量之間互相關(guān)聯(lián)的量化關(guān)系。6.2結(jié)構(gòu)學(xué)習(xí)算法算法：K2:通過(guò)為每個(gè)結(jié)點(diǎn)尋找父結(jié)點(diǎn)集合來(lái)學(xué)習(xí)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)。它不斷往父結(jié)點(diǎn)集中添加結(jié)點(diǎn)，并選擇能最大化數(shù)據(jù)和結(jié)構(gòu)的聯(lián)合概率的結(jié)點(diǎn)集。HillClimbing

(operators:edgeaddition,edgedeletion,edgereversion)從一個(gè)無(wú)邊結(jié)構(gòu)開(kāi)始，在每一步，它添加能最大化BIC的邊。算法在通過(guò)添加邊不能再提高結(jié)構(gòu)得分時(shí)停止。缺值數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)：StructuralEMSEM不是每次迭代都同時(shí)優(yōu)化模型結(jié)構(gòu)和參數(shù)，而是先固定模型結(jié)構(gòu)進(jìn)行數(shù)次參數(shù)優(yōu)化后，再進(jìn)行一次結(jié)構(gòu)加參數(shù)優(yōu)化，如此交替進(jìn)行。目的：減小計(jì)算復(fù)雜度。參數(shù)學(xué)習(xí)算法1.最大似然估計(jì)完全基于數(shù)據(jù)，不需要先驗(yàn)概率2.貝葉斯估計(jì)假定在考慮數(shù)據(jù)之前，網(wǎng)絡(luò)參數(shù)服從某個(gè)先驗(yàn)分布。先驗(yàn)的主觀概率,它的影響隨著數(shù)據(jù)量的增大而減小。3.缺值數(shù)據(jù)最大似然估計(jì)：EM算法（迭代算法）a.對(duì)數(shù)據(jù)進(jìn)行修補(bǔ)，使之完整(E-step)b.修補(bǔ)后的完整數(shù)據(jù)計(jì)算的最大似然估計(jì)(M-Step)隱結(jié)構(gòu)模型學(xué)習(xí)隱變量是取值未被觀察到的變量。通過(guò)數(shù)據(jù)分析：1隱變量的個(gè)數(shù)2隱結(jié)構(gòu)3隱變量的勢(shì)4模型參數(shù)方法：基于評(píng)分函數(shù)的爬山法G是一個(gè)隱變量模型，D是一組數(shù)據(jù)。θ是G的參數(shù)的某一個(gè)最大似然估計(jì)，是G的有效維數(shù)。隱變量勢(shì)學(xué)習(xí)爬山算法隱結(jié)構(gòu)學(xué)習(xí)雙重爬山算法

7

典型貝葉斯網(wǎng)絡(luò)學(xué)習(xí)方法及其擴(kuò)展7.1貝葉斯網(wǎng)絡(luò)應(yīng)用醫(yī)療診斷，工業(yè)，金融分析，計(jì)算機(jī)（微軟Windows,Office）模式識(shí)別：分類，語(yǔ)義理解軍事（目標(biāo)識(shí)別，多目標(biāo)跟蹤，戰(zhàn)爭(zhēng)身份識(shí)別等）生態(tài)學(xué)，生物信息學(xué)（貝葉斯網(wǎng)絡(luò)在基因連鎖分析中應(yīng)用）編碼學(xué)，分類聚類，時(shí)序數(shù)據(jù)和動(dòng)態(tài)模型7.2貝葉斯網(wǎng)絡(luò)模型的擴(kuò)展1.在復(fù)雜關(guān)系數(shù)據(jù)中的擴(kuò)展

關(guān)系數(shù)據(jù)是實(shí)際中最常見(jiàn)的數(shù)據(jù)存儲(chǔ)形式之一,但是標(biāo)準(zhǔn)貝葉斯網(wǎng)絡(luò)只能處理具有單一表的二維平面數(shù)據(jù),而對(duì)于多表中的多維關(guān)系數(shù)據(jù)則無(wú)能為力.在貝葉斯網(wǎng)絡(luò)的框架下,出現(xiàn)了能夠處理多維關(guān)系數(shù)據(jù)的方法,其中最具代表性的為概率關(guān)系模型(PRMs).2.在迭代反饋過(guò)程中的擴(kuò)展

很多實(shí)際問(wèn)題中存在循環(huán)、反饋以及因素之間互為因果關(guān)系等現(xiàn)象.例如,商品的市場(chǎng)價(jià)格影響庫(kù)存量,庫(kù)存量影響供給量,反過(guò)來(lái)供給量又會(huì)影響市場(chǎng)價(jià)格.標(biāo)準(zhǔn)貝葉斯網(wǎng)絡(luò)具有無(wú)環(huán)的限制,不能對(duì)這種具有迭代和反饋過(guò)程的領(lǐng)域進(jìn)行建模.有環(huán)貝葉斯網(wǎng)絡(luò)(CBN)突破了這個(gè)限制,繼承了貝葉斯網(wǎng)絡(luò)描述非確定性邏輯關(guān)系的能力,適于處理該類問(wèn)題.3.在時(shí)變系統(tǒng)中的擴(kuò)展

許多隨機(jī)現(xiàn)象都涉及一些隨時(shí)間變化的隨機(jī)變量,如股票指數(shù)的變化、語(yǔ)音的產(chǎn)生以及連續(xù)變化的視覺(jué)圖像等.標(biāo)準(zhǔn)貝葉斯網(wǎng)絡(luò)只能對(duì)靜態(tài)系統(tǒng)進(jìn)行建模.為了能夠?qū)Υ祟悇?dòng)態(tài)時(shí)變隨機(jī)過(guò)程進(jìn)行表達(dá)和推理,引入了動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)(DBN).7.3未來(lái)的研究方向1.核方法能夠處理高維特征空間,且有很強(qiáng)的泛化性,這與概率方法的特點(diǎn)互補(bǔ).當(dāng)前應(yīng)用核方法對(duì)貝葉斯網(wǎng)絡(luò)的研究限于如何提高貝葉斯網(wǎng)絡(luò)的數(shù)據(jù)分析能力.利用核方法的特點(diǎn),探索高效率的建模方法是值得進(jìn)一步研究的問(wèn)題.2.代數(shù)方法具有獨(dú)特的理論優(yōu)勢(shì),應(yīng)用代數(shù)方法研究貝葉斯網(wǎng)絡(luò)是對(duì)數(shù)值方法的補(bǔ)充和擴(kuò)展.目前的研究主要包括貝葉斯網(wǎng)絡(luò)等價(jià)類的代數(shù)特征和貝葉斯網(wǎng)絡(luò)的代數(shù)表示.除了進(jìn)一步研究構(gòu)建貝葉斯網(wǎng)絡(luò)更有效的代數(shù)方法,還可以應(yīng)用代數(shù)方法探索貝葉斯網(wǎng)絡(luò)中的概率推理問(wèn)題.3.高效快速的實(shí)時(shí)推理算法.在有些計(jì)算量很大的貝葉斯網(wǎng)絡(luò)的推理過(guò)程中,要求在任一截止時(shí)刻都能得到一個(gè)近似結(jié)果,鑒于這個(gè)實(shí)際應(yīng)用的要求,產(chǎn)生了實(shí)時(shí)推理算法?；谒阉鞯乃惴ê统闃铀惴ǖ榷紝儆谶@類算法,但這些算法都或多或少的存在收斂很慢,或者無(wú)法分析精度等問(wèn)題,因而有必要研究有效的實(shí)時(shí)推理算法來(lái)解決上述問(wèn)題.

總結(jié)與展望8總結(jié)與展望?

本章首先介紹了決策樹(shù)算法，分析了它們目前主要的代表理論以及存在的問(wèn)題，并舉出了利用基于信息論的決策樹(shù)算法應(yīng)用實(shí)例。種決策樹(shù)算法之間的主要區(qū)別就是對(duì)這個(gè)“差異”衡量方式的區(qū)別。?對(duì)具體衡量方式算法的討論超出了本文的范圍，在此我們只需要把切分看成是把一組數(shù)據(jù)分成幾份，份與份之間盡量不同，而同一份內(nèi)的數(shù)據(jù)盡量相同。這個(gè)切分的過(guò)程也可稱為數(shù)據(jù)的“純化”。

決策樹(shù)常見(jiàn)的批評(píng)是說(shuō)其在為一個(gè)節(jié)點(diǎn)選擇怎樣進(jìn)行分割時(shí)使用“貪心”算法。此種算法在決定當(dāng)前這個(gè)分割時(shí)根本不考慮此次選擇會(huì)對(duì)將來(lái)的分割造成什么樣的影響。換句話說(shuō)，所有的分割都是順序完成的，一個(gè)節(jié)點(diǎn)完成分割之后不可能以后再有機(jī)會(huì)回過(guò)頭來(lái)再