1、貝葉斯算法,貝葉斯算法,貝葉斯，英國數(shù)學(xué)家。1702年出生于倫敦，做過神甫。1742年成為英國皇家學(xué)會會員。1763年4月7日逝世。貝葉斯在數(shù)學(xué)方面主要研究概率論。他首先將歸納推理法用于概率論基礎(chǔ)理論，并創(chuàng)立了貝葉斯統(tǒng)計理論，對于統(tǒng)計決策函數(shù)、統(tǒng)計推斷、統(tǒng)計的估算等做出了貢獻。,一個醫(yī)療診斷問題,有兩個可選的假設(shè)：病人有癌癥、病人無癌癥可用數(shù)據(jù)來自化驗結(jié)果：正+和負-有先驗知識：在所有人口中，患病率是0.008對確實有病的患者的化驗準(zhǔn)確率為98%，對確實無病的患者的化驗準(zhǔn)確率為97%總結(jié)如下P(cancer)=0.008,P(cancer)=0.992P(+|cancer)=0.98,P(-|

2、cancer)=0.02P(+|cancer)=0.03,P(-|cancer)=0.97,問題：假定有一個新病人，化驗結(jié)果為正，是否應(yīng)將病人斷定為有癌癥？求后驗概率P(cancer|+)和P(cancer|+),貝葉斯定理,解決上面的問題：已知某條件概率，如何得到兩個事件交換后的概率，也就是在已知P(A|B)的情況下如何求得P(B|A)。,癌癥,診斷正確,診斷正確,癌癥,貝葉斯定理,這里先解釋什么是條件概率,在事情B發(fā)生的條件下A發(fā)生的條件概率，其求解公式為,貝葉斯定理,貝葉斯定理的意義在于，我們在生活中經(jīng)常遇到這種情況：我們可以很容易直接得出P(A|B)，P(B|A)則很難直接得出，但我們

3、更關(guān)心P(B|A)，貝葉斯定理就為我們打通從P(A|B)獲得P(B|A)的道路。,貝葉斯定理,下面不加證明給出貝葉斯定理公式,機器語言中的定義,表示在沒有訓(xùn)練數(shù)據(jù)前假設(shè)A擁有的初始概率。P(A)被稱為A的先驗概率.,P(A|B)表示假設(shè)B成立時A的概率機器學(xué)習(xí)中我們關(guān)心的是P(B|A)，即給定A時B的成立的概率，稱為B的后驗概率，,貝葉斯定理的解釋,P(B|A)隨著P(B)和P(A|B)的增長而增長，隨著P(A)的增長而減少，即如果A獨立于B時被觀察到的可能性越大，那么B對A的支持度越小.,評分標(biāo)準(zhǔn),H：假設(shè)候選集,表示使P（B|A),最大的B值,P(A)?_,P（A|B)=,樸素貝葉斯分類器

4、,1、條件獨立性,給定類標(biāo)號y，樸素貝葉斯分類器在估計類條件概率時假設(shè)屬性之間條件獨立。條件獨立假設(shè)可以形式化的表達如下：,其中每個訓(xùn)練樣本可用一個屬性向量X=(x1,x2,x3,xn)表示，各個屬性之間條件獨立。,樸素貝葉斯分類器,比如，對于一篇文章“Goodgoodstudy,Daydayup.”,用一個文本特征向量來表示：x=(Good,good,study,Day,day,up)。,一般各個詞語之間肯定不是相互獨立的，有一定的上下文聯(lián)系。但在樸素貝葉斯文本分類時，我們假設(shè)個單詞之間沒有聯(lián)系，可以用一個文本特征向量來表示這篇文章，這就是“樸素”的來歷。,樸素貝葉斯如何工作,有了條件獨立假

5、設(shè)，就不必計算X和Y的每一種組合的類條件概率，只需對給定的Y，計算每個Xi的條件概率。后一種方法更實用，因為它不需要很大的訓(xùn)練集就能獲得較好的概率估計。,估計分類屬性的條件概率,P(Xi|Y=y)怎么計算呢？它一般根據(jù)類別y下包含屬性Xi的實例的比例來估計。以文本分類為例，Xi表示一個單詞，P(Xi|Y=y)=包含該類別下包含單詞的xi的文章總數(shù)/該類別下的文章總數(shù)。,貝葉斯分類器舉例,假設(shè)給定了如下訓(xùn)練樣本數(shù)據(jù)，我們學(xué)習(xí)的目標(biāo)是根據(jù)給定的天氣狀況判斷你對PlayTennis這個請求的回答是Yes還是No。,貝葉斯分類器,打網(wǎng)球,我們需要利用訓(xùn)練數(shù)據(jù)計算后驗概率P(Yes|x)和P(No|x)

6、，如果P(Yes|x)P(No|x)，那么新實例分類為Yes，否則為No。,貝葉斯分類器舉例,我們將使用此表的數(shù)據(jù)，并結(jié)合樸素貝葉斯分類器來分類下面的新實例：,貝葉斯分類器舉例,P(Outlook=Sunny|No)=3/5,P(Temperature=Cool|No)=1/5,P(Humidity=High|No)=4/5,P(Wind=Strong|No)=3/5,貝葉斯分類器舉例,P(Outlook=Sunny|No)=3/5,P(Temperature=Cool|No)=1/5,P(Humidity=High|No)=4/5,P(Wind=Strong|No)=3/5,貝葉斯分類器舉例

7、,P(Outlook=Sunny|Yes)=2/9,P(Temprature=Cool|Yes)=3/9,P(Humidity=High|Yes)=3/9,P(Wind=Strong|Yes)=3/9,P(Outlook=Sunny|Yes)=2/9,P(Temprature=Cool|Yes)=3/9,P(Humidity=High|Yes)=3/9,P(Wind=Strong|Yes)=3/9,貝葉斯分類器舉例,貝葉斯分類器舉例,由于,大于,所以該樣本分類為No,樸素貝葉斯分類器的工作流程,條件概率的m估計,假設(shè)有來了一個新樣本x1=(Outlook=Cloudy,Temprature=C

8、ool,Humidity=High,Wind=Strong)要求對其分類。我們來開始計算P(Outlook=Cloudy|Yes)=0/9=0P(Outlook=Cloudy|No)=0/5=0計算到這里，大家就會意識到，這里出現(xiàn)了一個新的屬性值，在訓(xùn)練樣本中所沒有的。如果有一個屬性的類條件概率為0，則整個類的后驗概率就等于0，我們可以直接得到后驗概率P(Yes|x1)=P(No|x1)=0，這時二者相等，無法分類。,條件概率的m估計,當(dāng)訓(xùn)練樣本不能覆蓋那么多的屬性值時，都會出現(xiàn)上述的窘境。簡單的使用樣本比例來估計類條件概率的方法太脆弱了，尤其是當(dāng)訓(xùn)練樣本少而屬性數(shù)目又很大時。解決方法是使用m

9、估計(m-estimate)方法來估計條件概率：,n是Y中的樣本總數(shù)，nc是Y中取值xi的樣本數(shù)，m是稱為等價樣本大小的參數(shù)，而p是用戶指定的參數(shù)。如果沒有訓(xùn)練集（即n=0），則P(xi|yj)=p,因此p可以看作是在Y的樣本中觀察屬性值xi的先驗概率。等價樣本大小決定先驗概率和觀測概率nc/n之間的平衡,多項式模型,基本原理在多項式模型中，設(shè)某文檔d=(t1,t2,tk)，tk是該文檔中出現(xiàn)過的單詞，允許重復(fù)，則:V是訓(xùn)練樣本的單詞表（即抽取單詞，單詞出現(xiàn)多次，只算一個），|V|則表示訓(xùn)練樣本包含多少種單詞。在這里，m=|V|,p=1/|V|。P(tk|c)可以看作是單詞tk在證明d屬于類c

10、上提供了多大的證據(jù)，而P(c)則可以認為是類別c在整體上占多大比例(有多大可能性)。,多項式模型舉例,給定一個新樣本ChineseChineseChineseTokyoJapan，對其進行分類。,該文本用屬性向量表示為d=(Chinese,Chinese,Chinese,Tokyo,Japan)類別集合為Y=yes,no。,多項式模型舉例,字典里包括六個單詞,P(Chinese|yes)=(5+1)/(8+6)=6/14=3/7,P(Japan|yes)=P(Tokyo|yes)=(0+1)/(8+6)=1/14,P(Chinese|no)=(1+1)/(3+6)=2/9,P(Japan|no

11、)=P(Tokyo|no)=(1+1)/(3+6)=2/9,p(yes|d)=(3/7)31/141/148/11=108/1848770.00058417P(no|d)=(2/9)32/92/93/11=32/2165130.00014780因此，這個文檔屬于類別china。,伯努利模型,1、基本原理,在這里，m=2,p=1/2。,p(|c=YES)=p(|c=yes)(1-p(|c=yes),伯努利模型舉例,d=ChineseChineseChineseTokyoJapan,伯努利模型舉例,P(Chinese|yes)=(3+1)/(3+2)=4/5,P(Beijing|yes)=P(Ma

12、cao|yes)=P(Shanghai|yes)=(1+1)/(3+2)=2/5,P(Japan|yes)=P(Tokyo|yes)=(0+1)/(3+2)=1/5,伯努利模型舉例,P(Chinese|no)=(1+1)/(1+2)=2/3,P(Japan|no)=P(Tokyo|no)=(1+1)/(1+2)=2/3,P(Beijing|no)=P(Macao|no)=P(Shanghai|no)=(0+1)/(1+2)=1/3,伯努利模型舉例,P(yes|d)=P(yes)P(Chinese|yes)P(Japan|yes)P(Tokyo|yes)(1-P(Beijing|yes)(1-P(Shanghai|yes)(1-P(Macao|yes)=3/44/51/51/5(1-2/5)(1-2/5)(1-2/5)=81/156250.005P(no|d)=1/42/32/32/3(1-1/3)(1-1/3)(1-1/3)=16/7290.022,因此，這個文檔不屬于類別china。,二者的計算粒度不一樣，多項式模型以單詞為粒度，伯努利模型以文件為粒度，因此二者的先驗概率和類條件概率的計算方法都不同。計算后驗概率時，對