貝葉斯算法分解課件

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分類的基本概念背景 近幾十年來，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í)庫系統(tǒng)、信息檢索、高性能計(jì)算和可視化等學(xué)科。而數(shù)據(jù)挖掘中的分類技術(shù)是一項(xiàng)非常重要的技術(shù)。Q1 什么是分類 超市中的物品分類 生活中的垃圾分類Q1 什么是分類 生活

2、信息的分類由此可見，分類是跟我們的生活息息相關(guān)的東西，分類讓生活更加有條理，更加精彩.Q1 什么是分類 分類就是把一些新的數(shù)據(jù)項(xiàng)映射到給定類別的中的某一個(gè)類別，比如說當(dāng)我們發(fā)表一篇文章的時(shí)候，就可以自動(dòng)的把這篇文章劃分到某一個(gè)文章類別。 分類也稱為有監(jiān)督學(xué)習(xí)(supervised learning),與之相對(duì)于的是無監(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是無？動(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)，灰色代表完全無關(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ù)庫，貝葉斯分類法也已表現(xiàn)出高準(zhǔn)確率和高速度。 目前研究較多的貝葉斯分類器主要有四種，分別是：Naive Bayes、TAN、BAN和GBN。Thomas Bayes貝葉斯定理 貝葉斯定理（Bayes theorem）是概率論中的一個(gè)結(jié)果，它跟隨機(jī)變量的條件概率以及邊緣概率分布有關(guān)。在有些關(guān)于概率的解說中，貝葉斯定理能夠告知我們?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ì)象所屬的類。也就是說，貝葉斯分類器是最小錯(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è)類別。 通俗來說，就好比這么個(gè)道理，你在街上看到一個(gè)黑人，我問你你猜這哥們哪里來的，你十有八九猜非洲。為什么呢？因?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ū)來說，不真實(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è)問題說白了，就是要將社區(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ù)庫里得到或計(jì)算出來的。 下面給出劃分：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萬個(gè)賬號(hào)作為訓(xùn)練樣本。3、計(jì)算訓(xùn)練樣本中每個(gè)類別的頻率 用訓(xùn)練樣本中真實(shí)賬號(hào)和不真實(shí)賬號(hào)數(shù)量分別除以一萬，得到：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è)很可能并不成立。一般來說，好友密度除了與賬號(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í)際情況，但問題隨之也來了，由于特征屬性間存在依賴關(guān)系，使得樸素貝葉斯分類不適用了。

19、既然這樣，我去尋找另外的解決方案。 不確定性推理是人工智能研究的重要課題之一，從20世紀(jì)六七十年代以來，人們提出了許多方法，如概率方法（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é)理論。下面我們來看一個(gè)使用概率方法進(jìn)行不確定性推理的例子。（Alarm問題）P

20、earl教授家住在洛杉磯，那里地震和盜竊時(shí)有發(fā)生，教授家里裝有警鈴，發(fā)生地震和盜竊都有可能觸發(fā)警鈴，他的兩個(gè)鄰居Mary和John聽到警鈴響后可能會(huì)打電話給他。一天，Pearl教授接到Mary的電話，說聽到他家的警鈴響了，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)困難。基于以下原因，從而產(chǎn)生了貝葉斯網(wǎng)絡(luò)：全聯(lián)合概率計(jì)算復(fù)雜性十分巨大現(xiàn)實(shí)需要一種自然、有效的方式來捕捉和推理不確定性知識(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é)模型，所謂概率推理就是通過一些變量的信息來獲取其他的概率信息的過程，基于概率推理的貝葉斯網(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)成為近幾年來研究的熱點(diǎn).。貝葉斯網(wǎng)絡(luò)的定義貝葉斯網(wǎng)絡(luò)是一個(gè)二元組，即BN=(G,P), G=(V,E),為有向無圈圖(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è)角度來理解在定性層面：貝葉斯網(wǎng)絡(luò)是一個(gè)有向無圈圖，其中的節(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è)倩剡^頭來看剛才的例子,由于是否地震與盜竊無關(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ò)是有向無循環(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í)，近年來，貝葉斯學(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)、但卻沒有邊的無向圖。在搜索過程中，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è)試來構(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è)有向無環(huán)圖，以盡可能多地涵蓋這些條件獨(dú)立性。節(jié)點(diǎn)間的卡方統(tǒng)計(jì)量：節(jié)點(diǎn)間的互信息量：經(jīng)典算法 TPDA第一階段：Drafting，計(jì)算每對(duì)節(jié)點(diǎn)間的互信息，建立完整的無向圖；第二階段：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)來確定結(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)樹傳播算法利用步驟共享來加快推理的算法。團(tuán)樹（clique tree）是一種無向樹，其中每一個(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í)別：分類，語義理解軍事（目標(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ù)雜而紛亂的海量信息，人們總感覺無從下手，即使是借助最先進(jìn)的搜索引擎也不能滿足消費(fèi)者的需求。