貝葉斯算法分解課件

1、數(shù)據(jù)挖掘分類之主講人：軟件學(xué)院 盧衛(wèi)剛貝葉斯網(wǎng)絡(luò)目錄貝葉斯網(wǎng)絡(luò) 2貝葉斯分類 1總結(jié) 4貝葉斯網(wǎng)絡(luò)的應(yīng)用及實(shí)例 3致謝 51.1分類的基本概念1.2貝葉斯分類概述1.貝葉斯分類1.1分類的基本概念背景 近幾十年來(lái)，Internet互聯(lián)網(wǎng)的普及使得人們獲得和存儲(chǔ)數(shù)據(jù)的能力得到逐步的提高，數(shù)據(jù)規(guī)模不斷壯大。面對(duì)“數(shù)據(jù)豐富而知識(shí)匱乏”的挑戰(zhàn)，數(shù)據(jù)挖掘技術(shù)應(yīng)運(yùn)而生。數(shù)據(jù)挖掘是一門多學(xué)科的交叉領(lǐng)域，涉及統(tǒng)計(jì)學(xué)，機(jī)器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)、模式識(shí)別、知識(shí)庫(kù)系統(tǒng)、信息檢索、高性能計(jì)算和可視化等學(xué)科。而數(shù)據(jù)挖掘中的分類技術(shù)是一項(xiàng)非常重要的技術(shù)。Q1 什么是分類 超市中的物品分類 生活中的垃圾分類Q1 什么是分類 生活

2、信息的分類由此可見，分類是跟我們的生活息息相關(guān)的東西，分類讓生活更加有條理，更加精彩.Q1 什么是分類 分類就是把一些新的數(shù)據(jù)項(xiàng)映射到給定類別的中的某一個(gè)類別，比如說(shuō)當(dāng)我們發(fā)表一篇文章的時(shí)候，就可以自動(dòng)的把這篇文章劃分到某一個(gè)文章類別。 分類也稱為有監(jiān)督學(xué)習(xí)(supervised learning),與之相對(duì)于的是無(wú)監(jiān)督學(xué)習(xí)(unsupervised learning),比如聚類。 分類與聚類的最大區(qū)別在于，分類數(shù)據(jù)中的一部分的類別是已知的，而聚類數(shù)據(jù)的類別未知。 分類在數(shù)據(jù)挖掘中的學(xué)術(shù)定義Q2 分類問題名稱胎生會(huì)飛水中生活有腿類別Human是否否是哺乳動(dòng)物python否否否否非哺乳動(dòng)物sal

3、mon否否是否非哺乳動(dòng)物whale是否是否哺乳動(dòng)物frog否否有時(shí)是非哺乳動(dòng)物komodo否否否是非哺乳動(dòng)物bat是是否是哺乳動(dòng)物pigeon否是否是非哺乳動(dòng)物cat是否否是哺乳動(dòng)物leopard_shark是否是否非哺乳動(dòng)物turtle否否有時(shí)是非哺乳動(dòng)物penguin否否有時(shí)是非哺乳動(dòng)物porcupine是否否是哺乳動(dòng)物eel否否是否非哺乳動(dòng)物salamander否否有時(shí)是非哺乳動(dòng)物gila_monster否否否是非哺乳動(dòng)物platypus否否否是哺乳動(dòng)物owl否是否是非哺乳動(dòng)物dolphin是否是否哺乳動(dòng)物eagle否是否是非哺乳動(dòng)物胎生會(huì)飛水中生活有腿類別是否是否？Q2 分類問題稅號(hào)去

4、年退稅婚姻狀況可征稅收入逃稅1是單身125k否2否婚姻中100k否3否單身70k否4是婚姻中120k否5否離婚95k是6否婚姻中60k否7是離婚220k否8否單身85k是9否婚姻中75k否10否單身90k是Q2 分類的流程 動(dòng)物種類體型翅膀數(shù)量腳的只數(shù)是否產(chǎn)蛋是否有毛類別狗中04否是爬行動(dòng)物豬大04否是爬行動(dòng)物牛大04否是爬行動(dòng)物麻雀小22是是鳥類天鵝中22是是鳥類大雁中22是是鳥類動(dòng)物A大02是無(wú)？動(dòng)物B中22否是？根據(jù)現(xiàn)有的知識(shí)，我們得到了一些關(guān)于爬行動(dòng)物和鳥類的信息，我們能否對(duì)新發(fā)現(xiàn)的物種，比如動(dòng)物A，動(dòng)物B進(jìn)行分類？動(dòng)物種類體型翅膀數(shù)量腳的只數(shù)是否產(chǎn)蛋是否有毛類別狗中04否是爬行動(dòng)物豬

5、大04否是爬行動(dòng)物牛大04否是爬行動(dòng)物麻雀小22是是鳥類天鵝中22是是鳥類大雁中22是是鳥類步驟一：將樣本轉(zhuǎn)化為等維的數(shù)據(jù)特征（特征提?。Ｋ袠颖颈仨毦哂邢嗤瑪?shù)量的特征兼顧特征的全面性和獨(dú)立性Q2 分類的流程動(dòng)物種類體型翅膀數(shù)量腳的只數(shù)是否產(chǎn)蛋是否有毛類別狗中04否是爬行動(dòng)物豬大04否是爬行動(dòng)物牛大04否是爬行動(dòng)物麻雀小22是是鳥類天鵝中22是是鳥類大雁中22是是鳥類步驟二：選擇與類別相關(guān)的特征（特征選擇）。比如，綠色代表與類別非常相關(guān)，黑色代表部分相關(guān)，灰色代表完全無(wú)關(guān)Q2 分類的流程步驟三：建立分類模型或分類器（分類）。分類器通?？梢钥醋饕粋€(gè)函數(shù)，它把特征映射到類的空間上Q2 分類的流程

6、Q3 分類的方法 對(duì)數(shù)據(jù)挖掘中心的可信技術(shù)分類算法的內(nèi)容及其研究現(xiàn)狀進(jìn)行綜述。認(rèn)為分類算法大體可以分為傳統(tǒng)分類算法和基于軟件計(jì)算的分類法兩類，主要包括相似函數(shù)，關(guān)聯(lián)規(guī)則分類算法，K近鄰分類算法，決策樹分類算法，貝葉斯分類算法和基于模糊邏輯，遺傳算法，粗糙集和神經(jīng)網(wǎng)絡(luò)的分類算法。 分類的算法有很多種，他們都有各自的優(yōu)缺點(diǎn)和應(yīng)用范圍，本次我就貝葉斯分類算法展開我的演講。1.2 貝葉斯分類概述背景 貝葉斯分類基于貝葉斯定理，貝葉斯定理是由18世紀(jì)概率論和決策論的早起研究者Thomas Bayes發(fā)明的，故用其名字命名為貝葉斯定理。 分類算法的比較研究發(fā)現(xiàn)，一種稱為樸素貝葉斯分類法的簡(jiǎn)單貝葉斯分類法可

7、以與決策樹和經(jīng)過挑選的神經(jīng)網(wǎng)絡(luò)分類器相媲美。用于大型數(shù)據(jù)庫(kù)，貝葉斯分類法也已表現(xiàn)出高準(zhǔn)確率和高速度。 目前研究較多的貝葉斯分類器主要有四種，分別是：Naive Bayes、TAN、BAN和GBN。Thomas Bayes貝葉斯定理 貝葉斯定理（Bayes theorem）是概率論中的一個(gè)結(jié)果，它跟隨機(jī)變量的條件概率以及邊緣概率分布有關(guān)。在有些關(guān)于概率的解說(shuō)中，貝葉斯定理能夠告知我們?nèi)绾卫眯伦C據(jù)修改已有的看法。 通常，事件A在事件B（發(fā)生）的條件下的概率，與事件B在事件A的條件下的概率是不一樣的；然而，這兩者是有確定的關(guān)系，貝葉斯定理就是這種關(guān)系的陳述。 貝葉斯公式提供了從先驗(yàn)概率P(A)、P

8、(B)和P(B|A)計(jì)算后驗(yàn)概率P(A|B)的方法：P(A|B)=P(B|A)*P(A)/P(B) ，P(A|B)隨著P(A)和P(B|A)的增長(zhǎng)而增長(zhǎng)，隨著P(B)的增長(zhǎng)而減少，即如果B獨(dú)立于A時(shí)被觀察到的可能性越大，那么B對(duì)A的支持度越小。 貝葉斯公式貝葉斯法則 機(jī)器學(xué)習(xí)的任務(wù)：在給定訓(xùn)練數(shù)據(jù)D時(shí)，確定假設(shè)空間H中的最佳假設(shè)。 最佳假設(shè)：一種方法是把它定義為在給定數(shù)據(jù)D以及H中不同假設(shè)的先驗(yàn)概率的有關(guān)知識(shí)下的最可能假設(shè)。貝葉斯理論提供了一種計(jì)算假設(shè)概率的方法，基于假設(shè)的先驗(yàn)概率、給定假設(shè)下觀察到不同數(shù)據(jù)的概率以及觀察到的數(shù)據(jù)本身。貝葉斯分類的原理 貝葉斯分類器的分類原理是通過某對(duì)象的先驗(yàn)概

9、率，利用貝葉斯公式計(jì)算出其后驗(yàn)概率，即該對(duì)象屬于某一類的概率，選擇具有最大后驗(yàn)概率的類作為該對(duì)象所屬的類。也就是說(shuō)，貝葉斯分類器是最小錯(cuò)誤率意義上的優(yōu)化。根據(jù)貝葉斯定理：由于P(X)對(duì)于所有類為常數(shù)，只需要P(X|H)*P(H)最大即可。 樸素貝葉斯 樸素貝葉斯分類是一種十分簡(jiǎn)單的分類算法，叫它樸素貝葉斯分類是因?yàn)檫@種方法的思想真的很樸素，樸素貝葉斯的思想基礎(chǔ)是這樣的：對(duì)于給出的待分類項(xiàng)，求解在此項(xiàng)出現(xiàn)的條件下各個(gè)類別出現(xiàn)的概率，哪個(gè)最大，就認(rèn)為此待分類項(xiàng)屬于哪個(gè)類別。 通俗來(lái)說(shuō)，就好比這么個(gè)道理，你在街上看到一個(gè)黑人，我問你你猜這哥們哪里來(lái)的，你十有八九猜非洲。為什么呢？因?yàn)楹谌酥蟹侵奕说谋?/p>

10、率最高，當(dāng)然人家也可能是美洲人或亞洲人，但在沒有其它可用信息下，我們會(huì)選擇條件概率最大的類別，這就是樸素貝葉斯的思想基礎(chǔ)。 黑人 非洲人概率最大 第一階段準(zhǔn)備工作階段，這個(gè)階段的任務(wù)是為樸素貝葉斯分類做必要的準(zhǔn)備，主要工作是根據(jù)具體情況確定特征屬性，并對(duì)每個(gè)特征屬性進(jìn)行適當(dāng)劃分，然后由人工對(duì)一部分待分類項(xiàng)進(jìn)行分類，形成訓(xùn)練樣本集合。這一階段的輸入是所有待分類數(shù)據(jù)，輸出是特征屬性和訓(xùn)練樣本。這一階段是整個(gè)樸素貝葉斯分類中唯一需要人工完成的階段，其質(zhì)量對(duì)整個(gè)過程將有重要影響，分類器的質(zhì)量很大程度上由特征屬性、特征屬性劃分及訓(xùn)練樣本質(zhì)量決定。 第二階段分類器訓(xùn)練階段，這個(gè)階段的任務(wù)就是生成分類器，主

11、要工作是計(jì)算每個(gè)類別在訓(xùn)練樣本中的出現(xiàn)頻率及每個(gè)特征屬性劃分對(duì)每個(gè)類別的條件概率估計(jì)，并將結(jié)果記錄。其輸入是特征屬性和訓(xùn)練樣本，輸出是分類器。這一階段是機(jī)械性階段，根據(jù)前面討論的公式可以由程序自動(dòng)計(jì)算完成。 第三階段應(yīng)用階段。這個(gè)階段的任務(wù)是使用分類器對(duì)待分類項(xiàng)進(jìn)行分類，其輸入是分類器和待分類項(xiàng)，輸出是待分類項(xiàng)與類別的映射關(guān)系。這一階段也是機(jī)械性階段，由程序完成。樸素貝葉斯分類的流程 樸素貝葉斯分類實(shí)例檢測(cè)SNS社區(qū)中不真實(shí)賬號(hào) 下面討論一個(gè)使用樸素貝葉斯分類解決實(shí)際問題的例子。 這個(gè)問題是這樣的，對(duì)于SNS社區(qū)來(lái)說(shuō)，不真實(shí)賬號(hào)（使用虛假身份或用戶的小號(hào)）是一個(gè)普遍存在的問題，作為SNS社區(qū)的

12、運(yùn)營(yíng)商，希望可以檢測(cè)出這些不真實(shí)賬號(hào)，從而在一些運(yùn)營(yíng)分析報(bào)告中避免這些賬號(hào)的干擾，亦可以加強(qiáng)對(duì)SNS社區(qū)的了解與監(jiān)管。 如果通過純?nèi)斯z測(cè)，需要耗費(fèi)大量的人力，效率也十分低下，如能引入自動(dòng)檢測(cè)機(jī)制，必將大大提升工作效率。這個(gè)問題說(shuō)白了，就是要將社區(qū)中所有賬號(hào)在真實(shí)賬號(hào)和不真實(shí)賬號(hào)兩個(gè)類別上進(jìn)行分類。 下面我們一步一步實(shí)現(xiàn)這個(gè)過程。是真是假？首先設(shè)C=0表示真實(shí)賬號(hào)，C=1表示不真實(shí)賬號(hào)。1、確定特征屬性及劃分 這一步要找出可以幫助我們區(qū)分真實(shí)賬號(hào)與不真實(shí)賬號(hào)的特征屬性，在實(shí)際應(yīng)用中，特征屬性的數(shù)量是很多的，劃分也會(huì)比較細(xì)致，但這里為了簡(jiǎn)單起見，我們用少量的特征屬性以及較粗的劃分，并對(duì)數(shù)據(jù)做了修

13、改。 我們選擇三個(gè)特征屬性：a1：日志數(shù)量/注冊(cè)天數(shù) a2：好友數(shù)量/注冊(cè)天數(shù) a3：是否使用真實(shí)頭像 在SNS社區(qū)中這三項(xiàng)都是可以直接從數(shù)據(jù)庫(kù)里得到或計(jì)算出來(lái)的。 下面給出劃分：a1：a=0.05, 0.05a=0.2 a2：a=0.1, 0.1a=0.8 a3：a=0（不是）,a=1（是）2、獲取訓(xùn)練樣本 這里使用運(yùn)維人員曾經(jīng)人工檢測(cè)過的1萬(wàn)個(gè)賬號(hào)作為訓(xùn)練樣本。3、計(jì)算訓(xùn)練樣本中每個(gè)類別的頻率 用訓(xùn)練樣本中真實(shí)賬號(hào)和不真實(shí)賬號(hào)數(shù)量分別除以一萬(wàn)，得到：P(C = 0) = 8900/10000 = 0.89P(C = 1) = 1100/10000 = 0.114、計(jì)算每個(gè)類別條件下各個(gè)特征

14、屬性劃分的頻率P(a1=0.05| C = 0) = 0.3 P(a1=0.05| C = 1) = 0.8 P(0.05a10.2|C = 0) = 0.5 P(0.05a10.2| C = 0) = 0.2 P(a10.2| C = 1) = 0.1P(a2=0.1| C = 0) = 0.1 P(a2=0.1| C = 1) = 0.7P(0.1a20.8 | C=0) = 0.7 P(0.1a20.8| C = 0) = 0.2 P(a20.8| C = 0) = 0.1P(a3 = 0|C = 0) = 0.2 P(a3 = 1|C = 0) = 0.8 P(a3 = 0|C = 1

15、) = 0.9 P(a3 = 1|C = 1) = 0.1 5、使用分類器進(jìn)行鑒別 下面我們使用上面訓(xùn)練得到的分類器鑒別一個(gè)賬號(hào)，屬性如下 a1:日志數(shù)量與注冊(cè)天數(shù)的比率為0.1 a2 :好友數(shù)與注冊(cè)天數(shù)的比率為 0.2 a3:不使用真實(shí)頭像 (a = 0) P(C = 0)P( x|C = 0)= P(C = 0) P(0.05a10.2|C = 0)P(0.1a20.8|C = 0)P(a3=0|C = 0)= 0.89*0.5*0.7*0.2= 0.0623 P(C = 1)P( x|C = 1)= P(C = 1) P(0.05a10.2|C = 1)P(0.1a20.8|C = 1)

16、P(a3=0|C = 1)= 0.11*0.1*0.2*0.9= 0.00198 可以看到，雖然這個(gè)用戶沒有使用真實(shí)頭像，但是通過分類器的鑒別，更傾向于將此賬號(hào)歸入真實(shí)賬號(hào)類別。 樸素貝葉斯模型發(fā)源于古典數(shù)學(xué)理論，有著堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)，以 及穩(wěn)定的分類效率。同時(shí)，NBC模型所需估計(jì)的參數(shù)很少，對(duì)缺失數(shù)據(jù)不太敏感，算法也比較簡(jiǎn)單。理論上，NBC模型與其他分類方法相比具有最小的誤差率。但是樸素貝葉斯分類有一個(gè)限制條件，就是特征屬性必須有條件獨(dú)立或基本獨(dú)立（實(shí)際上在現(xiàn)實(shí)應(yīng)用中幾乎不可能做到完全獨(dú)立）。當(dāng)這個(gè)條件成立時(shí)，樸素貝葉斯分類法的準(zhǔn)確率是最高的，但不幸的是，現(xiàn)實(shí)中各個(gè)特征屬性間往往并不條件獨(dú)立，

17、而是具有較強(qiáng)的相關(guān)性，這樣就限制了樸素貝葉斯分類的能力。于是誕生了一種更高級(jí)、應(yīng)用范圍更廣的貝葉斯網(wǎng)絡(luò)。2.1貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)概述2.2貝葉斯網(wǎng)絡(luò)學(xué)習(xí)2.貝葉斯網(wǎng)絡(luò)2.3貝葉斯網(wǎng)絡(luò)推理計(jì)算 在上一篇文章中我們討論了樸素貝葉斯分類。 這一篇文章中，我們接著上一篇文章的例子，討論貝葉斯分類中更高級(jí)、應(yīng)用范圍更廣的一種算法貝葉斯網(wǎng)絡(luò)（又稱貝葉斯信念網(wǎng)絡(luò)或信念網(wǎng)絡(luò)）。復(fù)雜的網(wǎng)絡(luò)2.1貝葉斯網(wǎng)絡(luò)概述 上一篇文章我們使用樸素貝葉斯分類實(shí)現(xiàn)了SNS社區(qū)中不真實(shí)賬號(hào)的檢測(cè)。在那個(gè)解決方案中，我做了如下假設(shè)： i、真實(shí)賬號(hào)比非真實(shí)賬號(hào)平均具有更大的日志密度、各大的好友密度以及更多的使用真實(shí)頭像。 ii、日志密度、

18、好友密度和是否使用真實(shí)頭像在賬號(hào)真實(shí)性給定的條件下是獨(dú)立的。 但是，上述第二條假設(shè)很可能并不成立。一般來(lái)說(shuō)，好友密度除了與賬號(hào)是否真實(shí)有關(guān)，還與是否有真實(shí)頭像有關(guān)，因?yàn)檎鎸?shí)的頭像會(huì)吸引更多人加其為好友。因此，我們?yōu)榱双@取更準(zhǔn)確的分類，可以將假設(shè)修改如下： i、真實(shí)賬號(hào)比非真實(shí)賬號(hào)平均具有更大的日志密度、各大的好友密度以及更多的使用真實(shí)頭像。 ii、日志密度與好友密度、日志密度與是否使用真實(shí)頭像在賬號(hào)真實(shí)性給定的條件下是獨(dú)立的。 iii、使用真實(shí)頭像的用戶比使用非真實(shí)頭像的用戶平均有更大的好友密度。上述假設(shè)更接近實(shí)際情況，但問題隨之也來(lái)了，由于特征屬性間存在依賴關(guān)系，使得樸素貝葉斯分類不適用了。

19、既然這樣，我去尋找另外的解決方案。 不確定性推理是人工智能研究的重要課題之一，從20世紀(jì)六七十年代以來(lái)，人們提出了許多方法，如概率方法（Nilsson,1965; Duda and Hart,1973）、非單調(diào)邏輯（Ginsberg,1987）、確定因子（Shortliffe and Buchhanan, 1975）、Dempster-Shafer證據(jù)理論（Shafer,1976）、模糊邏輯（Zadeh,1965）等。在這些方法中，概率方法是最自然也是最早被嘗試的方法之一，因?yàn)楦怕收摫旧硎顷P(guān)于隨機(jī)現(xiàn)象和不確定性的數(shù)學(xué)理論。下面我們來(lái)看一個(gè)使用概率方法進(jìn)行不確定性推理的例子。（Alarm問題）P

20、earl教授家住在洛杉磯，那里地震和盜竊時(shí)有發(fā)生，教授家里裝有警鈴，發(fā)生地震和盜竊都有可能觸發(fā)警鈴，他的兩個(gè)鄰居Mary和John聽到警鈴響后可能會(huì)打電話給他。一天，Pearl教授接到Mary的電話，說(shuō)聽到他家的警鈴響了，Pearl教授想知道他家遭盜竊的概率有多大？ 貝葉斯網(wǎng)絡(luò)的產(chǎn)生這個(gè)問題包含5個(gè)隨機(jī)變量：盜竊（B）、地震（E）、警鈴（A）、接到Mary的電話（M）、接到John的電話（J）；假設(shè)所有變量均取兩個(gè)值：yes or no. 這里各變量間的關(guān)系存在不確定性：盜竊和地震以一定的概率隨機(jī)發(fā)生；它們發(fā)生后并不一定會(huì)觸發(fā)警鈴；而警鈴響后，瑪麗和瓊可能會(huì)因?yàn)槟承┰颍缭诼犚魳坊蚵犃τ袉栴}

21、等，而沒有聽到警鈴；有時(shí)候兩人也會(huì)將其他聲音誤聽為警鈴聲。 因此這是一個(gè)不確定性推理問題。假設(shè)Pearl教授根據(jù)自己以往的經(jīng)驗(yàn)對(duì)這5個(gè)變量的聯(lián)合概率分布有如下的估計(jì)（如右圖），從聯(lián)合概率分布 出發(fā)，先計(jì)算邊緣分布 BEAMJProbabilityynnyy1.2E-4ynnyn5.1E-5yynny5.7E-6yyynn8.5E-5yyyyy7.2E-6nnnyn9.1E-1nnnny2.6E-4nyynn7.0E-9nyyny1.3E-2nyyyn1.7E-4 貝葉斯網(wǎng)絡(luò)的產(chǎn)生從這個(gè)例子中我們可以看出，需要計(jì)算的聯(lián)合概率分布 上式包含 個(gè)參數(shù)，假設(shè)有n個(gè)二元變量，則需要的獨(dú)立參數(shù)數(shù)目為： ，

22、所以，直接使用聯(lián)合概率分布進(jìn)行不確定性推理的計(jì)算復(fù)雜度很大，隨著變量的個(gè)數(shù)呈指數(shù)級(jí)增長(zhǎng)。因此，當(dāng)變量很多時(shí)，聯(lián)合概率的獲取、存儲(chǔ)和運(yùn)算都變得相當(dāng)困難?；谝韵略颍瑥亩a(chǎn)生了貝葉斯網(wǎng)絡(luò)：全聯(lián)合概率計(jì)算復(fù)雜性十分巨大現(xiàn)實(shí)需要一種自然、有效的方式來(lái)捕捉和推理不確定性知識(shí)變量之間的獨(dú)立性和條件獨(dú)立性可大大減少為了定義全聯(lián)合概率分布所需的概率數(shù)目 貝葉斯網(wǎng)絡(luò)的產(chǎn)生貝葉斯網(wǎng)絡(luò)的簡(jiǎn)介簡(jiǎn)介 貝葉斯網(wǎng)絡(luò)是一種概率網(wǎng)絡(luò)，它是基于概率推理的圖形化網(wǎng)絡(luò)，而貝葉斯公式則是這個(gè)概率網(wǎng)絡(luò)的基礎(chǔ)。貝葉斯網(wǎng)絡(luò)是基于概率推理的數(shù)學(xué)模型，所謂概率推理就是通過一些變量的信息來(lái)獲取其他的概率信息的過程，基于概率推理的貝葉斯網(wǎng)絡(luò)(Ba

23、yesian network)是為了解決不定性和不完整性問題而提出的，它對(duì)于解決復(fù)雜設(shè)備不確定性和關(guān)聯(lián)性引起的故障有很的優(yōu)勢(shì)，在多個(gè)領(lǐng)域中獲得廣泛應(yīng)用。 貝葉斯網(wǎng)絡(luò)又稱信度網(wǎng)絡(luò)，是Bayes方法的擴(kuò)展，目前不確定知識(shí)表達(dá)和推理領(lǐng)域最有效的理論模型之一。從1988年由Pearl提出后，已經(jīng)成為近幾年來(lái)研究的熱點(diǎn).。貝葉斯網(wǎng)絡(luò)的定義貝葉斯網(wǎng)絡(luò)是一個(gè)二元組，即BN=(G,P), G=(V,E),為有向無(wú)圈圖(Directed Acyclic Graph) ,其中V為節(jié)點(diǎn)集合，與領(lǐng)域的隨機(jī)變量一一對(duì)應(yīng)，E為有向邊集，反映節(jié)點(diǎn)變量之間的因果依賴關(guān)系；P為節(jié)點(diǎn)的概率分布，表示節(jié)點(diǎn)之間因果影響強(qiáng)度從定性和定

24、量?jī)蓚€(gè)角度來(lái)理解在定性層面：貝葉斯網(wǎng)絡(luò)是一個(gè)有向無(wú)圈圖，其中的節(jié)點(diǎn)代表隨機(jī)變量，節(jié)點(diǎn)之間的邊代表變量之間的直接依賴關(guān)系；在定量層面：每個(gè)節(jié)點(diǎn)都有一個(gè)條件概率表(Conditional Probability Table) P(Xi|Parents(Xi) ,刻畫了父變量對(duì)子變量的影響程度。給定BN,則存在一個(gè)離散變量集和 上的聯(lián)合概率分布： 貝葉斯網(wǎng)絡(luò)示例（1）貝葉斯網(wǎng)絡(luò)示例（2）我們?cè)倩剡^頭來(lái)看剛才的例子,由于是否地震與盜竊無(wú)關(guān),于是假設(shè)E和B是相互獨(dú)立的;另外,瓊和瑪麗是否打電話直接取決于他們是否聽到警鈴響,因此,假定給定A時(shí),J與B和E,以及M與J、B和E都是相互獨(dú)立的,從而可以構(gòu)造下面

25、的貝葉斯網(wǎng)絡(luò)；根據(jù)所構(gòu)造的貝葉斯網(wǎng)絡(luò)，聯(lián)合概率分布可以表示為：這樣就把聯(lián)合概率分布分解成了若干個(gè)復(fù)雜度較低的概率分布的乘積。上式右端僅包含1+1+4+2+2=10個(gè)獨(dú)參數(shù)。 By0.01n0.99Ey0.02n0.98ABEyyy0.95nyy0.05yyn0.94nyn0.06yny0.29nny0.71ynn0.001nnn0.999JAyy0.7ny0.3yn0.01nn0.99MAyy0.9ny0.1yn0.95nn0.05貝葉斯網(wǎng)絡(luò)示例（3）貝葉斯網(wǎng)絡(luò)又名：信念網(wǎng)(Belief Network)、概率網(wǎng)絡(luò)(Probability Network)、因果網(wǎng)絡(luò)(Causal Networ

26、k)、圖模型(Graphical Model)或概率圖模型(PGM)、決策網(wǎng)絡(luò)(Decision Network)、影響圖(Influence Diagram)、知識(shí)圖(Knowledge Map)貝葉斯網(wǎng)絡(luò)作為不確定性知識(shí)表示的理想模型，具有以下主要特點(diǎn)： 1.具有堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)：貝葉斯理論是貝葉斯概率和經(jīng)典的統(tǒng)計(jì)學(xué)理論相結(jié)合的結(jié)果，它給出了信任函數(shù)在數(shù)學(xué)上的計(jì)算方法，刻畫了信任度與樣本數(shù)據(jù)的一致性以及信任度隨數(shù)據(jù)而變化的增量學(xué)習(xí)特性，長(zhǎng)期的理論研究和實(shí)踐應(yīng)用，證明了其有效性和正確性。 2.貝葉斯網(wǎng)絡(luò)是有向無(wú)循環(huán)圖，能夠清晰和直觀地顯示變量之間的因果關(guān)系。 3.貝葉斯網(wǎng)絡(luò)可以圖形化表示隨機(jī)變

27、量間的聯(lián)合概率，利用概率理論能夠處理各種不確定性信息。 4. 貝葉斯網(wǎng)絡(luò)可以處理不完整和帶噪音的數(shù)據(jù)集。 貝葉斯網(wǎng)絡(luò)的特點(diǎn)貝葉斯網(wǎng)絡(luò)的研究現(xiàn)狀20世紀(jì)80年代，隨著人工智能的發(fā)展，尤其是機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等興起，為貝葉斯理論的發(fā)展和應(yīng)用提供了更為廣闊的空間。Pearl等于1988年提出貝葉斯網(wǎng)絡(luò)，并將貝葉斯網(wǎng)絡(luò)成功地應(yīng)用于專家系統(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)了專門研究貝葉斯理論的組織和

28、學(xué)術(shù)刊物ISBA。隨著人工智能的發(fā)展，貝葉斯理論的內(nèi)涵也比以前有了很大的變化。目前，貝葉斯網(wǎng)絡(luò)研究領(lǐng)域主要集中在以下四個(gè)方面：貝葉斯網(wǎng)絡(luò)的學(xué)習(xí)、利用貝葉斯網(wǎng)絡(luò)進(jìn)行推理，計(jì)算和基于貝葉斯網(wǎng)絡(luò)的應(yīng)用。2.2貝葉斯網(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)系 貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)結(jié)構(gòu)學(xué)習(xí)是利用訓(xùn)練樣本集，盡可能結(jié)合先驗(yàn)知識(shí)，確定和樣本數(shù)據(jù)集合D匹配最好的的貝葉斯網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)；對(duì)于含有n個(gè)變量的數(shù)據(jù)集進(jìn)行網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)，可能的結(jié)構(gòu)數(shù)目為：因此貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的學(xué)習(xí)是一個(gè)NP難問題。在計(jì)算機(jī)學(xué)科中，存在多項(xiàng)式時(shí)間的算法的一類問題，稱之為P類問題；而像梵塔問題、

29、推銷員旅行問題、（命題表達(dá)式）可滿足問題這類，至今沒有找到多項(xiàng)式時(shí)間算法解的一類問題，稱之為NP類問題。目前貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)方法主要分成兩類：基于搜索和評(píng)分的方法(score and search method）；基于約束的方法(constraint-based method).基于評(píng)分和搜索的方法將結(jié)構(gòu)學(xué)習(xí)視為結(jié)構(gòu)優(yōu)化的過程，即利用一個(gè)評(píng)分函數(shù)尋找與樣本數(shù)據(jù)匹配程度最高的網(wǎng)絡(luò)結(jié)構(gòu) ，即主要由兩部分組成：評(píng)分函數(shù)和空間搜索策略 該算法的主要思想是從一個(gè)給定的網(wǎng)絡(luò)出發(fā)(比如一個(gè)沒有任何弧的網(wǎng)絡(luò)),利用搜索方法對(duì)該網(wǎng)絡(luò)進(jìn)行一些操作(增加邊，刪除邊，逆轉(zhuǎn)邊的方向)，根據(jù)評(píng)分函數(shù)對(duì)網(wǎng)絡(luò)進(jìn)行評(píng)分，計(jì)算

30、這一操作對(duì)網(wǎng)絡(luò)評(píng)分函數(shù)的貢獻(xiàn)度，檢驗(yàn)新的網(wǎng)絡(luò)結(jié)構(gòu)是否優(yōu)于舊的網(wǎng)絡(luò)結(jié)構(gòu)，如果優(yōu)于則保留新加入的邊并繼續(xù)該操作，直到找到得分最大的網(wǎng)絡(luò)結(jié)構(gòu)作為最優(yōu)的網(wǎng)絡(luò)結(jié)構(gòu)。 主要的評(píng)分函數(shù)和搜索機(jī)制 評(píng)分函數(shù)：最早是由Cooper and Herskovits等人在1992年提出的K2評(píng)分函數(shù)，K2評(píng)分函數(shù)假設(shè)觀測(cè)到的數(shù)據(jù)是完備的，且服從多項(xiàng)式分布：基于K2評(píng)分函數(shù)，Heckerman等人在1995年，假設(shè)觀測(cè)數(shù)據(jù)服從Dirichlet分布，給出了BD評(píng)分函數(shù)：主要的搜索機(jī)制：貪婪搜索、模擬退火、最優(yōu)最先搜索、基于智能優(yōu)化的搜索等 經(jīng)典算法 K2算法 1992年，Cooper和Herskovits建立了著名的基

31、于貝葉斯評(píng)分函數(shù)（Bayesian score）和爬山法搜索策略的K2算法。K2算法要求事先確定節(jié)點(diǎn)的次序，應(yīng)用貝葉斯評(píng)分，通過不斷向網(wǎng)絡(luò)中增加能提高評(píng)分函數(shù)的邊的貪婪搜索方法發(fā)現(xiàn)最評(píng)分最高的的信念網(wǎng)絡(luò)結(jié)構(gòu)，找出最佳網(wǎng)絡(luò)結(jié)構(gòu)。K2算法是結(jié)合先驗(yàn)信息進(jìn)行貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的一個(gè)有實(shí)際意義的重要算法，在整個(gè)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法的研究發(fā)展過程中占有重要地位。K2 算法使用后驗(yàn)概率作為評(píng)分函數(shù)：其中 貪婪搜索K2算法描述Procedure K2For i:=1 to n do i = ;Pold = g(i, i );OKToProceed := truewhile OKToProceed and

32、| i | Pold then Pold := Pnew ; i :=i z ;else OKToProceed := false;end whilewrite(“Node:”, “parents of this nodes :”, i );end forend K2K2的出發(fā)點(diǎn)是一個(gè)包含所有節(jié)點(diǎn)、但卻沒有邊的無(wú)向圖。在搜索過程中，K2按順序逐個(gè)考察 中的變量，確定其父親節(jié)點(diǎn)，然后添加相應(yīng)的邊。對(duì)某一變量 ，假設(shè)K2已經(jīng)找到了它的一些父親節(jié)點(diǎn) 。如果 父親節(jié)點(diǎn)個(gè)數(shù)還未達(dá)到上界 ，那么就要繼續(xù)為它尋找父節(jié)點(diǎn)，具體做法是首先考慮哪些在 p中排在xj 之前，但卻還不是 xj的父親節(jié)點(diǎn)的變量，從這些變

33、量中選出 ，它使得新家族CH評(píng)分 達(dá)到最大；然后將 新家族與舊家族評(píng)分比較：如果評(píng)分高 ，則把 添加為 的父節(jié)點(diǎn)；否則停止為 尋找父親節(jié)點(diǎn)?；诩s束的方法 將結(jié)構(gòu)學(xué)習(xí)視為約束滿足問題，即通過卡方假設(shè)檢驗(yàn)或互信息量對(duì)變量間的條件獨(dú)立性關(guān)系進(jìn)行測(cè)試來(lái)構(gòu)造貝葉斯網(wǎng)絡(luò)結(jié)構(gòu) 核心思想是：首先對(duì)訓(xùn)練數(shù)據(jù)集進(jìn)行統(tǒng)計(jì)測(cè)試，尤其是條件獨(dú)立性測(cè)試，確定出不同結(jié)點(diǎn)集之間的一致條件獨(dú)立性；然后，利用結(jié)點(diǎn)集之間的條件獨(dú)立性，構(gòu)造一個(gè)有向無(wú)環(huán)圖，以盡可能多地涵蓋這些條件獨(dú)立性。節(jié)點(diǎn)間的卡方統(tǒng)計(jì)量：節(jié)點(diǎn)間的互信息量：經(jīng)典算法 TPDA第一階段：Drafting，計(jì)算每對(duì)節(jié)點(diǎn)間的互信息，建立完整的無(wú)向圖；第二階段：Thick

34、ening，如果節(jié)點(diǎn)對(duì)不是d-分割的話，把這一點(diǎn)對(duì)加入到邊集中；第三階段：Thinning，檢察邊集中的每個(gè)點(diǎn)對(duì)，如果兩個(gè)節(jié)點(diǎn)是d-分割的，則移走這條邊。 2002年，Cheng將信息論與統(tǒng)計(jì)測(cè)試相結(jié)合，使用相互信息代替了條件獨(dú)立測(cè)試，經(jīng)過Drafting、Thickening、Thinning三個(gè)步驟，通過計(jì)算相互信息量(Mutual Information)來(lái)確定結(jié)點(diǎn)間的條件獨(dú)立性，從而構(gòu)造多連接有向圖模型。被稱為TPDA算法。貝葉斯網(wǎng)絡(luò)的參數(shù)學(xué)習(xí)最大似然估計(jì) 完全基于數(shù)據(jù)，不需要先驗(yàn)概率： 貝葉斯估計(jì) 假定在考慮數(shù)據(jù)之前，網(wǎng)絡(luò)參數(shù)服從某個(gè)先驗(yàn)分布。先驗(yàn)的主觀概率,它的影響隨著數(shù)據(jù)量的增大

35、而減小。 缺值數(shù)據(jù)最大似然估計(jì)：EM算法 （迭代算法） 1 基于 對(duì)數(shù)據(jù)進(jìn)行修補(bǔ)，使之完整 (E-step) 2 基于修補(bǔ)后的完整數(shù)據(jù)計(jì)算的最大似然估計(jì) (M-Step)EM算法是收斂的。貝葉斯網(wǎng)絡(luò)參數(shù)學(xué)習(xí)2.3貝葉斯網(wǎng)絡(luò)的推理和計(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è)問題。它把復(fù)雜的聯(lián)合概率分布分解成一系列相對(duì)簡(jiǎn)單的模塊，從而大大降低知識(shí)獲取和概率推理的復(fù)雜度，使得可以把概率論應(yīng)用于大型問題。貝葉斯網(wǎng)絡(luò)推理 貝葉斯網(wǎng)絡(luò)推理是在一個(gè)不定性環(huán)境和

36、不完全信息下進(jìn)行決策支持和因果發(fā)現(xiàn)的工具。 貝葉斯網(wǎng)絡(luò)推理基于如下假設(shè)：令人感興趣的變量受概率分布的控制，人們結(jié)合觀察數(shù)據(jù)，對(duì)這些概率進(jìn)行推算便可以做出最優(yōu)的決策。 兩個(gè)基本任務(wù)概率推理最大驗(yàn)后概率解釋1 變量消元算法(Variable elimination) 利用概率分解降低推理復(fù)雜度。 使得運(yùn)算局部化。消元過程實(shí)質(zhì)上就是一個(gè)邊緣化的過程。 最優(yōu)消元順序：最大勢(shì)搜索，最小缺邊搜索貝葉斯網(wǎng)絡(luò)推理算法2. 團(tuán)樹傳播算法利用步驟共享來(lái)加快推理的算法。團(tuán)樹（clique tree）是一種無(wú)向樹，其中每一個(gè)節(jié)點(diǎn)代表一個(gè)變量集合，稱為團(tuán)(clique)。團(tuán)樹必須滿足變量連通性，即包含同一變量的所有團(tuán)所

37、導(dǎo)出的子圖必須是連通的。 用團(tuán)樹組織變量消元的算法。計(jì)算共享團(tuán)樹傳播算法基本步驟：將貝葉斯網(wǎng)絡(luò)轉(zhuǎn)化為團(tuán)樹團(tuán)樹初始化在團(tuán)樹中選一個(gè)團(tuán)作為樞紐全局概率傳播：CollectMessage; DistributeMessage邊緣化，歸一化 團(tuán)樹傳播算法示例 （TLR是樞紐節(jié)點(diǎn)） 變量消元和團(tuán)樹傳播算法都是精確推理算法3 . 近似推理 由于近似方法已犧牲推導(dǎo)結(jié)果精度換取推導(dǎo)效率的提高，故已在許多應(yīng)用中顯示了很好的實(shí)用性。面對(duì)現(xiàn)實(shí)世界實(shí)時(shí)性、響應(yīng)性等要求，近似推理的方法逐漸成為主流方法，隨機(jī)模擬采樣法就是其中應(yīng)用最廣的概率推理方法。3 . 近似推理 隨機(jī)抽樣算法：順序抽樣法，MCMC抽樣是一類應(yīng)用于數(shù)值

38、積分和統(tǒng)計(jì)物理中的近似計(jì)算方法?；舅枷胧菑哪硞€(gè)概率分布隨機(jī)抽樣，生成一組樣本，然后從樣本出發(fā)近似計(jì)算感興趣的量。隨機(jī)抽樣算法理論基礎(chǔ)是大數(shù)定律。 MCMC算法吉布斯抽樣(Gibbs sampling)。它首先隨機(jī)生成一個(gè)與證據(jù)E=e相一致的樣本s1作為起始樣本。此后，每個(gè)樣本si的產(chǎn)生都依賴于前一個(gè)樣本si-1,且si與si-1最多只有一個(gè)非證據(jù)變量的取值不同，記改變量為X。X的取值可以從非證據(jù)變量中隨機(jī)選取，也可以按某個(gè)固定順序輪流決定。在si中，X的值通過隨機(jī)抽樣決定，抽樣分布是：當(dāng)樣本數(shù) 時(shí)，馬氏鏈理論保證了算法返回的結(jié)果收斂于真正的后驗(yàn)概率。吉布斯抽樣的缺點(diǎn)是收斂速度慢，因?yàn)轳R氏鏈往往需要花很長(zhǎng)時(shí)間才能真正達(dá)到平穩(wěn)分布。 3.貝葉斯網(wǎng)絡(luò)的應(yīng)用3.1貝葉斯網(wǎng)絡(luò)應(yīng)用概述3.1貝葉斯網(wǎng)絡(luò)應(yīng)用實(shí)例醫(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)模型3.1貝葉斯網(wǎng)絡(luò)應(yīng)用概述3.1貝葉斯網(wǎng)絡(luò)應(yīng)用實(shí)例 隨著計(jì)算機(jī)和網(wǎng)絡(luò)的飛速發(fā)展，電子商務(wù)的出現(xiàn)，網(wǎng)上購(gòu)物已經(jīng)成為了一種潮流。但是面對(duì)網(wǎng)上復(fù)雜而紛亂的海量信息，人們總感覺無(wú)從下手，即使是借助最先進(jìn)的搜索引擎也不能滿足消費(fèi)者的需求。