《數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)》第5章貝葉斯網(wǎng)絡

第5章貝葉斯網(wǎng)絡

《數(shù)據(jù)挖掘與知識發(fā)現(xiàn)》(第2版)數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-2)貝葉斯網(wǎng)絡

貝葉斯網(wǎng)絡(BayesianNetworks)結合圖論和統(tǒng)計學方面的知識，提供了一種自然表達因果信息的方法，用于表達隨機變量之間復雜的概率不確定性，發(fā)現(xiàn)數(shù)據(jù)間的潛在關系。本章介紹如下幾個方面的內容：貝葉斯網(wǎng)絡基本概念不確定性推理與聯(lián)合概率分布貝葉斯網(wǎng)絡中的獨立關系貝葉斯網(wǎng)絡學習貝葉斯網(wǎng)絡分類器數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-3)引言貝葉斯網(wǎng)絡將圖論和統(tǒng)計學相結合，用于表達隨機變量之間復雜的概率不確定性，發(fā)現(xiàn)數(shù)據(jù)間的潛在關系。優(yōu)點：(1)知識表示形式更加直觀。(2)對于問題域的建模，當條件或行為等發(fā)生變化時，不需要修正模型。(3)以圖形化表示隨機變量間的聯(lián)合概率，處理不確定性信息。(4)沒有確定的輸入或輸出結點，結點之間相互影響，可以用于估計預測。(5)將知識表示與知識推理結合統(tǒng)一為整體。1988年，Pearl建立了貝葉斯網(wǎng)基礎理論體系，將概率理論和圖論有機結合，用一種緊湊的形式表示聯(lián)合概率分布。數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-4)貝葉斯網(wǎng)絡基本概念給定一個隨機變量集X={X1,X2,…,Xn}，其中Xi是一個m維向量。貝葉斯網(wǎng)絡說明X上的聯(lián)合條件概率分布。定義為G是有向無環(huán)圖，節(jié)點分別對應于有限集X中的隨機變量X1,X2,…,Xn

，每條弧代表一個函數(shù)依賴關系。如果有一條由變量Y到X的弧，則Y是X的雙親(直接前驅)，X是Y的后繼。Xi的所有雙親變量用集合Pa(Xi)表示。一旦給定雙親，圖G中的每個變量就與其非后繼節(jié)點相獨立。代表用于量化網(wǎng)絡的一組參數(shù)。對于Xi的取值xi，參數(shù)貝葉斯網(wǎng)絡表明變量集合X上的聯(lián)合條件概率分布：數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-5)貝葉斯網(wǎng)絡基本概念貝葉斯網(wǎng)絡提供一種方便表示因果知識的途徑。網(wǎng)絡內節(jié)點可以選作“輸出”節(jié)點，代表類標號屬性?？梢杂卸鄠€輸出節(jié)點。分類過程返回類標號屬性的概率分布，預測每個類的概率。數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-6)不確定性推理與聯(lián)合概率分布不確定性的主要來源：⑴領域專家對自己掌握知識的不確定性；⑵所要建模的領域本身內在的不確定性；⑶知識工程師試圖翻譯、表示知識所產(chǎn)生的不確定性；⑷關于知識自身的精確性和知識獲取方面存在的不確定性。使用概率方法進行不確定性推理的步驟：①將待處理問題域抽象為一組隨機變量的集合X={X1,X2,…,Xn}；②把關于該問題的知識表示為一個聯(lián)合概率分布P(X)；按照概率論原則進行推理計算。例（Alarm問題）：Pearl教授的家里裝有警鈴，地震和盜竊都可能觸發(fā)警鈴。聽到警鈴后，兩個鄰居Marry和John可能會打電話給他。如果Pearl教授接到Mary的電話，說聽到他家警鈴響，那么Pearl教授家遭盜竊的概率是多大?數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-7)不確定性推理與聯(lián)合概率分布5個隨機變量：盜竊(Burgle，B)接到John的電話(JohnCall，J)地震(EarthQuake，E)接到Marry的電話(MarryCall，M)警鈴響(Alarm，A)數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-8)不確定性推理與聯(lián)合概率分布從聯(lián)合概率P(A,B,E,J,M)出發(fā)，先計算邊緣分布（5.4）得到聯(lián)合概率邊緣化分布：再按照條件概率定義，得到數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-9)不確定性推理與聯(lián)合概率分布問題：隨著變量數(shù)目增加，聯(lián)合概率分布的參數(shù)個數(shù)成指數(shù)級增長。n個二值隨機變量的聯(lián)合概率分布包含2n-1個獨立參數(shù)。當變量很多時，聯(lián)合概率的獲取、存儲和運算都十分困難。在六、七十年代，大多數(shù)學者認為概率論不適合于解決人工智能中的不確定性問題。數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-10)貝葉斯網(wǎng)絡中的獨立關系利用變量間的條件獨立關系可以將聯(lián)合概率分布分解成多個復雜度較低的概率分布，從而降低模型復雜度，提高推理效率。例如：由鏈規(guī)則可以把聯(lián)合概率分布P(A,B,E,J,M)改寫為：

獨立參數(shù)：1+2+4+8+16=31E與B相互獨立，即P(E|B)=P(E)給定A時，J與B和E相互獨立，即P(J|B,E,A)=P(J|A)給定A時，M與J、B和E都相互獨立，即P(M|J,A,B,E)=P(M|A)則有：獨立參數(shù)：l+2+4+2+2=11數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-11)貝葉斯網(wǎng)絡中的獨立關系利用鏈規(guī)則將包含n個變量的聯(lián)合分布寫為：

對于任意Xi，如果存在Pa(Xi)∈{X1，…，Xi-1}，使得己知Pa(Xi)條件下，Xi與{X1，…，Xi-1}中的其它變量條件獨立，即則聯(lián)合概率分布可改寫為獨立性可以減少表示聯(lián)合概率分布所需的信息量。獨立性斷言通常來源于領域知識。貝葉斯網(wǎng)絡中存在三類獨立關系：條件獨立因果影響獨立環(huán)境獨立數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-12)貝葉斯網(wǎng)絡中的獨立關系(一)條件獨立貝葉斯網(wǎng)絡的網(wǎng)絡結構表達節(jié)點間的條件獨立關系。三種局部結構順連(serialconnection)分連(divergingconnection)匯連(convergingconnection)數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-13)貝葉斯網(wǎng)絡中的獨立關系(二)有向分離和條件獨立貝葉斯網(wǎng)絡中任意兩個節(jié)點之間的條件獨立關系可由有向分離來判斷。定義5.1設E為節(jié)點集合，X和Y是不在E中的兩個節(jié)點。X和Y之間的通路α如果滿足下面條件之一，則稱α被E所阻塞1.α上存在一個順連節(jié)點Z，且Z在E中；2.α上存在一個分連節(jié)點Z，且Z在E中；3.α上存在一個匯連節(jié)點Z，且Z和Z的后代節(jié)點均不在E中。數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-14)貝葉斯網(wǎng)絡中的獨立關系定義5.2X，Y，E是三個互不相交的節(jié)點集，說E有向分離X和Y，當且僅當X和Y之間的通路都被E所阻塞。推論5.3設X和Y為貝葉斯網(wǎng)絡中的兩個變量。Z為貝葉斯網(wǎng)絡中一個不包含X和Y的節(jié)點集合。如果Z分離X和Y，則X和Y在給定Z的條件下相互獨立。推論5.4一個節(jié)點的馬爾科夫覆蓋包括該節(jié)點的父節(jié)點，子節(jié)點，以及子節(jié)點的父節(jié)點。推論5.5在一個貝葉斯網(wǎng)中，給定變量X的馬爾可夫覆蓋時，則X條件獨立于網(wǎng)絡中所有其它變量。推論5.6在一個貝葉斯網(wǎng)中，給定變量X的父節(jié)點Pa(X)，則X條件獨立于它的所有非后代節(jié)點。數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-15)貝葉斯網(wǎng)絡中的獨立關系(三)因果影響獨立(causalindependence)

因果影響獨立指的是多個原因獨立地影響同一個結果。定義5.7節(jié)點Y的各個父親節(jié)點X1,X2,…,Xn對于Y是因果影響獨立的，如果對應于X1,X2,…,Xn存在和Y有相同取值范圍的隨機變量，并且下面兩個條件成立：1.對任意i，依賴于Xi，在Xi已知條件下，獨立于所有其它的Xj

和

(j≠i)；2.在ΩY上存在一個滿足交換律和結合律的二元算子*，使得數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-16)貝葉斯網(wǎng)絡中的獨立關系(四)環(huán)境獨立(contextindependence)環(huán)境獨立是指在特定環(huán)境下才成立的條件獨立關系。一個環(huán)境是一組變量及其取值的組合。設環(huán)境中涉及變量的集合用C表示，C的一種取值用c表示，則C=c表示一個環(huán)境。定義5.8設X，Y，Z，C是4個兩兩交空的變量集合，如果

P(X,Y,Z,C=c)>0且P(X|Y,Z,C=c)=P(X|Z,C=c)則稱X,Y在環(huán)境C=c下關于Z條件獨立。若Z為空，則稱X,Y在環(huán)境C=c下環(huán)境獨立。數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-17)貝葉斯網(wǎng)絡學習

貝葉斯網(wǎng)絡由結構(有向無環(huán)圖)和參數(shù)(條件概率)兩部分構成，分別用于定性與定量地描述依賴關系。網(wǎng)絡中的有向邊具有因果語義。貝葉斯網(wǎng)絡學習的核心問題是結構學習，包括結構和數(shù)據(jù)集參數(shù)。有時網(wǎng)絡學習和結構學習不加區(qū)分。(一)結構學習目標是基于訓練數(shù)據(jù)找到數(shù)據(jù)匹配程度最高的貝葉斯網(wǎng)絡結構。無約束貝葉斯網(wǎng)絡可歸結為在給定數(shù)據(jù)集T后，尋找具有極大似然P(G|T)的結構G的問題。有n個變量的問題域，對應的網(wǎng)結構空間為n個結點構成的所有可能的有向無環(huán)圖，結構空間大小是n的指數(shù)次。貝葉斯網(wǎng)絡結構學習方法：基于打分搜索的方法基于依賴關系分析的方法數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-18)貝葉斯網(wǎng)絡學習(1)基于打分搜索的學習算法采用某個評分標準，評判網(wǎng)絡結構反映出的獨立及依賴關系和數(shù)據(jù)的匹配程度。給定一個關于結構的測度后，在結構空間中按照一定的搜索策略，依次計算各結構的測度值，選擇測度值最優(yōu)的結構。兩類評分標準：①基于編碼理論最小描述長度(MinimumDescriptionLength，MDL)貝葉斯信息標準(BayesianInformationCriterion，BIC)②源于貝葉斯統(tǒng)計BDe評分方法最小描述長度函數(shù)MDLMDL原理認為最優(yōu)模型是總描述長度最短的模型。貝葉斯網(wǎng)絡B=<G,θ>描述每一個樣本Di的概率，按編碼策略對每個樣本Di進行編碼。網(wǎng)絡結構G要使得網(wǎng)絡描述長度和數(shù)據(jù)D的編碼長度之和最小，必須在網(wǎng)絡結構的復雜性與網(wǎng)絡結構的準確性之間確定平衡點。數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-19)貝葉斯網(wǎng)絡學習網(wǎng)絡結構的MDL測度由3部分組成：1.網(wǎng)絡結構的描述長度：保存網(wǎng)絡結構G，要記錄各節(jié)點的父節(jié)點的編號。貝葉斯網(wǎng)絡包含n個節(jié)點，|πXi|為節(jié)點Xi的父節(jié)點數(shù)目。網(wǎng)絡結構的描述長度是：

2.參數(shù)的描述長度：為描述局部條件概率表，須存貯每個節(jié)點的條件概率表的所有參數(shù)。Xi的條件概率表需要存貯|πXi|(|Xi|-1)個參數(shù)，|Xi|表示變量Xi所有可能狀態(tài)的數(shù)目。存儲每個參數(shù)，需要logn/2二進制位，其中N是訓練樣本的數(shù)目。3.數(shù)據(jù)集合的描述長度：將數(shù)據(jù)D中每個樣本Di建立Huffman編碼，每個碼字的確切長度依賴于P(Di|G,θ)，其概率越大，編碼長度越小，概率越小，編碼長度越大。Di的二進制編碼長度近似等于log(1/P(Di|G,θ))。因而數(shù)據(jù)集合的描述長度為：其中H(Xi|πXi)為條件熵。綜上，結構MDL測度為：數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-20)貝葉斯網(wǎng)絡學習貪婪搜索:

令E表示所有可能添加到網(wǎng)絡中的候選邊集合，表示邊e加入到網(wǎng)絡中后評分函數(shù)的變化。步驟1.選擇一個網(wǎng)絡。步驟2.選擇集合E中的邊e，使得，如果找不到滿足條件的邊，則停止，否則繼續(xù)。步驟3.加入邊e到網(wǎng)絡中，并從集合E中刪除e，轉步驟2。MDL優(yōu)缺點：目標是結構簡單、參數(shù)較少的稀疏網(wǎng)絡具有一致性沒有用到先驗知識對兩個具有等價性的結構，不能保證得到相同MDL測度值。數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-21)貝葉斯網(wǎng)絡學習BDe函數(shù)Heckerman等擴展BD(BayesianDirichlet)度量，提出BDe函數(shù)。定義一個離散變量G表示未知的網(wǎng)絡結構，其取值范圍是所有可能網(wǎng)絡結構；估計G的先驗概率P(G)；計算網(wǎng)絡結構后驗概率P(G|D)和參數(shù)后驗概率P(θ|D,G)，并計算目標期望值。BDe函數(shù)取做網(wǎng)絡結構同數(shù)據(jù)集的聯(lián)合概率分布的對數(shù)形式：

（5.11）其中P(D|G)稱邊際似然函數(shù)。定義一個隨機變量Sh表示網(wǎng)絡結構對應的狀態(tài)，并賦予先驗概率分布P(Sh)。對任意樣本D，計算后驗概率分布有其中P(D)是一個與結構無關的正規(guī)化常數(shù)，P(D|Sh)是邊界似然。

數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-22)貝葉斯網(wǎng)絡學習度量公式如下：先驗概率分布的計算依據(jù)先驗知識。優(yōu)缺點：使用先驗知識，其對訓練數(shù)據(jù)集的依賴性比MDL測度要低沒有明確地包含結構復雜性指標，會傾向于選擇較復雜的網(wǎng)絡結構。數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-23)貝葉斯網(wǎng)絡學習(二)搜索算法搜索算法在某個評分函數(shù)下搜索分值最高的網(wǎng)絡結構。當數(shù)據(jù)完備時，搜索算法借助評分函數(shù)的“可分解性”來提高搜索效率。所謂評分函數(shù)可分解是指：G的分值可以通過其各個家族的分值之和求得。家族即一個節(jié)點和其所有父節(jié)點所構成的簡單圖。搜索算法執(zhí)行過程：從一個初始的網(wǎng)絡結構開始，對當前結構進行某些的修改；計算修改后結構的分值，根據(jù)分值決定是否更新結構。定義5.9.

如果給定某一問題領域的各個變量，用一個結點表示其中的一個變量，由任意兩個結點之間的無向邊連接構成的圖模型，稱為完全潛在圖。定義5.10.

如果變量X、Y和變量集Z之間存在以下關系：

即在變量集Z已知的條件下，變量Y的狀態(tài)和概率不會造成對變量X的影響，稱為在給定變量集Z的前提下，X條件獨立于Y。數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-24)貝葉斯網(wǎng)絡學習定義5.11.設X、Y和Z為有向無環(huán)圖中3個互不相交的結點子集，當且僅當沒有一條從X中一個結點到Y中一個結點的所有路徑之間，存在結點W滿足下列條件之一：i.每個匯聚結點要么是Z中的結點，要么有子孫在Z中；ii.其它的每個結點都不在Z中。滿足以上兩個條件的路徑是活躍的；否則被稱為Z阻塞。稱在給定條件集Z的情況下，X與Y為d分割。記作d(X；Z；Y)。例：X={X2}和Y={X3}被Z={X1}分割。路徑X2←X1→X3被X3∈Z阻塞；路徑X2←X4→X3也被阻塞，因為X4及它的所有子孫都不在Z中。因此，d(X2；X1；X3)。X和Y沒有被d分割，故，d(X2；{X1；X5}；X3)不成立。數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-25)貝葉斯網(wǎng)絡學習定理5.1對網(wǎng)絡結構中的結點集X、Y和Z，當且僅當P(X|Y；Z)=P(X|Z)時，X與Y為d分割。定理5.2在依賴模型M中，設X、Y和Z為互不相交的子集，條件獨立性滿足對稱性、分解律和交換律等屬性。定理5.3滿足對稱性、分布律和交換律的依賴模型M，從完整圖中刪除任意條件獨立性成立的連接(X；Y)，則產(chǎn)生一個惟一的最小獨立圖。基于獨立性測試的網(wǎng)絡結構學習算法：1.初始化圖結構B(V;A;Θ)；V={V1;V2;…;Vm}；E=Φ；S=Φ；R=Φ。2.對于每對結點Vi;Vj(Vi;Vj∈V)計算互信息I(Vi;Vj)。按互信息降序排序，將互信息大于某一閾值的結點對依次放入到集合S中。3.從集合S中取出第一對結點并將其從S中刪除，將相應的弧加入到E中(弧的方向由現(xiàn)有的結點順序所決定)。設置成由根結點指向外，把無向圖轉換成有向圖。4.從集合S中取出剩余的第一對結點并將其從S中刪除，如果該對結點之間無開放通路，將對應弧加入到E中，否則將該對結點加入到有序集合R中的末端。數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-26)貝葉斯網(wǎng)絡學習(三)基于約束的方法(Constraintbased)

通過條件獨立性測試來發(fā)現(xiàn)數(shù)據(jù)中暗含的條件獨立關系，尋找和這些條件獨立關系一致的網(wǎng)絡結構。在基于約束的方法中，貝葉斯網(wǎng)絡被看作是編碼了變量間獨立性關系的圖結構，是通過一些有效的測試手段找出數(shù)據(jù)D中各變量間的條件獨立關系，再尋找和這些條件獨立一致的網(wǎng)絡模型。算法采用互信息和條件互信息進行變量之間定量條件獨立性檢驗。對于給定的閥值ε一般取ε=0.01)，如果I(Xi，Xj|C)<ε，就認為Xi和Xj條件獨立。階段I(畫草圖，Drafting)(1)初始化圖G=(V，E)，V={數(shù)據(jù)集中的所有節(jié)點}，邊集合E={}。列表L={}，R={}；(2)對每一節(jié)點對，計算它們的互信息，并將互信息大于某一閥值的節(jié)點對按互信息值的大小順序加入到L中；(3)從列表L中取出前兩組節(jié)點對，將對應的邊加入到邊集E中(邊的方向由節(jié)點序來確定)。(4)從列表L中剩余的節(jié)點對中取出第一個點對，如果這兩個節(jié)點之間不存在開放路徑(不含碰撞節(jié)點的路徑)，則將其對應的邊加入到E，并將該節(jié)點對從L中刪除，否則將節(jié)點加入到R中。(5)重復(4)，直至L為空。

數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-27)貝葉斯網(wǎng)絡學習階段II(增厚，Thickening)(6)從R中取出第一個點對。找出能夠d-分離該點對的某一切割集，在該切割集上做CI測試，如果兩個節(jié)點條件獨立，則轉下一步；否則用一條邊連接該節(jié)點對，將該邊加入到邊集E中。(7)重復(6)，直至R為空。階段III(削減圖，Thinning)(8)對于E中的每一條邊，如果除這條邊之外在這兩個節(jié)點之間仍存在開放路徑，則暫時移走這條邊，并在相應的切割集上作CI測試，如果兩節(jié)點條件獨立，在E中永久刪除該邊，否則將該邊放回E中。確定切割集設Xi不是Xj的祖先結點(否則選擇Xi)，記Xi的父結點集為πXi，則πXi是Xi和Xj的切割集，按如下方法對πXi進行簡化：(l)把連接Xi不是Xj且經(jīng)過πXi中節(jié)點的所有開放路徑儲存到Sij中。(2)把D(Xi,Xj)初始化為空。(3)在Sij中，把路徑上只含有一個結點的這個結點放入切割集D(Xi,Xj)中；(4)把經(jīng)過這些結點的路徑從Sij中刪除；(5)返回(1)步，直到?jīng)]有滿足條件的結點為止；(6)在Sij中，把能夠堵塞最多路徑的πXi中結點放入切割集D(Xi,Xj)中；(7)在Sij中刪除經(jīng)過這點的路徑；(8)返回(4)步，直到Sij空為止。數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-28)貝葉斯網(wǎng)絡學習(四)參數(shù)學習

貝葉斯網(wǎng)的條件概率學習問題可以歸結為統(tǒng)計學中的參數(shù)估計問題。實際應用領域中，概率信息獲得方式：從統(tǒng)計數(shù)據(jù)中學習從文獻中查閱咨詢領域專家常用參數(shù)學習方法：極大似然性估計MLE(maximumlikelihoodestimation)方法Bayesian方法極大似然性估計MLE方法基本思想：一個隨機實驗可能的結果有C1,C2,…,Cn，在一次實驗中，結果Cｍ出現(xiàn)，即Cｍ出現(xiàn)的概率應該最大，可將似然函數(shù)P(C|θ)取極大值時的參數(shù)值θ作為對參數(shù)的估計值。給定參數(shù)θ，數(shù)據(jù)D的條件概率P(D|θ)稱為是θ的似然度，記為L(θ|D)=P(D|θ)。如果固定D而讓θ在其定義域上變動，那么L(θ|D)就是θ的一個函數(shù)，稱為θ的似然函數(shù)。數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-29)貝葉斯網(wǎng)絡學習參數(shù)θ的最大似然估計簡稱MLE，是L(θ|D)達到最大的那個取值θ*，即（5.14）三個假設前提：1.樣本中的數(shù)據(jù)是完備的；產(chǎn)生事例的概率分布始終相同。2.D中各樣本在給定參數(shù)θ時相互獨立，即L(θ|D)=P(D|θ)=∏P(Di|θ)3.每個樣本Di的條件概率分布P(Di|θ)相同，即P(Di|θ)≠P(Dj|θ)(i≠j)MLE方法具有以下性質：一致性(consistent)

隨著事例的增多，算法逐漸收斂于最佳可能值。2.漸進有效性(asympototicefficiency)

事例越多，接近的程度越好。3.表示靈活性(representationinvariant)

參數(shù)的不同表示形式不影響估計出的概率分布結果。數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-30)貝葉斯網(wǎng)絡分類器

貝葉斯網(wǎng)絡用結點表示變量，有向邊表示變量間的依賴關系。如果把其中代表類別變量的結點作為根結點，其余所有變量都作為它的子結點時，貝葉斯網(wǎng)絡就變成了分類器。樸素貝葉斯分類(NaiveBayesianClassification)

將訓練樣本I分解成特征向量X和決策類別變量C。假定一個特征向量的各分量相對于決策變量是獨立的(類條件獨立)。樸素貝葉斯分類的工作過程：1.用n維特征向量X={x1,x2,…,xn}表示每個數(shù)據(jù)樣本，用以描述對該樣本的n個屬性A1,A2,…,An的度量。2.假定數(shù)據(jù)樣本可以分為m個類C1,C2,…,Cm。給定一個未知類標號的數(shù)據(jù)樣本X，樸素貝葉斯分類將其分類到類Ci

，當且僅當

P(Ci|X)>P(Cj|X)，1≤j≤m，j≠i

（5.17）P(Ci|X)最大的類Ci稱為最大后驗假定。由貝葉斯公式可知數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-31)貝葉斯網(wǎng)絡分類器3.只需要P(X|Ci)P(Ci)最大即可。如果類的先驗概率未知，可取P(C1)=P(C2)=…=P(Cm)。類的先驗概率也可以用P(Ci)=si/s計算，其中si是類Ci中的訓練樣本數(shù)，s是訓練樣本總數(shù)。4.如果假定類條件獨立，可以降低計算P(X|Ci)的開銷。給定樣本的類標號，若屬性值相互條件獨立，則有：5.樸素貝葉斯以后驗概率作為分類指示

對每個類Ci

，計算P(X|Ci)P(Ci)。把樣本X指派到類Ci的充要條件是

P(X|Ci)P(Ci)>P(X|Cj)P(Cj)，1≤j≤m，j≠i

（5.21）X被分配到使P(X|Ci)P(Ci)最大的類Ci

。數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-32)貝葉斯網(wǎng)絡分類器例5.1使用樸素貝葉斯分類預測未知樣本的類標號。給定Playtennis的訓練樣本集見表5.3。使用樸素貝葉斯分類來預測在＜Outlook=Sunny,Temperature=Hot,Humidity=High,wind=Strong＞的情況下，是否打球。數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-33)貝葉斯網(wǎng)絡分類器解：要分類的未知樣本為：

X=＜Outlook=Sunny,Temperature=Hot,Humidity=High,wind=Strong＞每個類的先驗概率P(Ci)可以根據(jù)訓練樣本計算：P(Playtennis=“yes”)=9/14=0.643P(Playtennis=“no”)=5/14=0.357為計算P(X|Ci)，i=1,2，先計算下面的條件概率：P(Outlook=“Sunny”|Playtennis=“yes”)=2/9=0.222P(Outlook=“Sunny”|Playtennis=“no”)=3/5=0.600P(Temperature=“hot”|Playtennis=“yes”)=2/9=0.222P(Temperature=“hot”|Playtennis=“no”)=2/5=0.400P(Humidity=“high”|Playtennis=“yes”)=3/9=0.333P(Humidity=“high”|Playtennis=“no”)=4/5=0.800P(Windy=“Strong”|Playtennis=“yes”)=3/9=0.333P(Windy=“Strong”|Playtennis=“no”)=3/5=0.600利用以上概率，可以得到：P(X|Playtennis=“yes”)=0.222×0.222×0.333×0.333=0.005P(X|Playtennis=“no”)=0.600×0.400×0.800×0.600=0.115P(X|Playtennis=“yes”)P(Playtennis=“yes”)=0.005×0.643=0.003P(X|Playtennis=“no”)P(Playtennis=“no”)=0.115×0.357=0.041因此，將樣本X指派給類C2：Playtennis=“no”。即不去打球。數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-34)貝葉斯網(wǎng)絡分類器半樸素貝葉斯分類器(Semi-NaiveBayesianClassifier,SNBC)

依照一定的標準將關聯(lián)程度較大的特征屬性合并在一起組合成新屬性，各個組合屬性之間也是相對于類別屬性相互獨立的。這里合并并不是真正上的合并，只是在計算中體現(xiàn)出來，是概念層次上的一個抽象過程。

SNBC模型限制網(wǎng)絡的結構復雜度。計算推導過程與樸素貝葉斯相同。數(shù)據(jù)挖掘與知識發(fā)現(xiàn)(第2版)(40-35)貝葉斯網(wǎng)絡分類器選擇貝葉斯分類器(SelectiveNa?veBayesianClassifier)

使用屬性集的子集作為決策過程中的屬性結點，即選擇貝葉斯分類器選擇初始特征的子集作為屬性結點。它通過搜索特征空間，去掉特征間具有較強依賴關系的屬性。應該著重考慮的問題：l.搜索方向的選擇向前搜索是從空集開始，逐漸添加新的屬性；向后搜索是從整個屬性集開始，逐漸移走相應的屬性。2.搜索策略的選擇。