貝葉斯分類(lèi)器第1頁(yè)，共40頁(yè)。貝葉斯定理每個(gè)記錄用一個(gè)d維特征向量X=(x1,x2,…,xd)表示假定有k個(gè)類(lèi)y1,y2,…,yk.給定X,X屬于yj類(lèi)的后驗(yàn)概率P(yj|X)

滿足貝葉斯(Bayes)定理

MAP(maximumposteriorihypothesis,最大后驗(yàn)假設(shè))將X指派到具有最大后驗(yàn)概率P(yj|X)的類(lèi)yj，即將X指派到P(X|yj)P(yj)

最大的類(lèi)yj第2頁(yè)，共40頁(yè)。樸素貝葉斯分類(lèi)樸素貝葉斯分類(lèi)(Na?veBayesClassifier)工作原理給定一個(gè)未知的數(shù)據(jù)樣本X,分類(lèi)法將預(yù)測(cè)X屬于具有最高后驗(yàn)概率的類(lèi).即,未知的樣本分配給類(lèi)yj,當(dāng)且僅當(dāng) 根據(jù)貝葉斯定理,我們有由于P(X)

對(duì)于所有類(lèi)為常數(shù),只需要最大化P(X|yj)P(yj)即可.3第3頁(yè)，共40頁(yè)。樸素貝葉斯分類(lèi)(續(xù))估計(jì)P(yj)類(lèi)yj的先驗(yàn)概率可以用P(yj)=nj/n估計(jì)

其中,nj是類(lèi)yj中的訓(xùn)練樣本數(shù),而n是訓(xùn)練樣本總數(shù)估計(jì)P(X|yj)為便于估計(jì)P(X|yj),假定類(lèi)條件獨(dú)立----給定樣本的類(lèi)標(biāo)號(hào),假定屬性值條件地相互獨(dú)立.于是,P(X|Y=yj)可以用下式估計(jì) 其中,P(x|yj)可以由訓(xùn)練樣本估值4第4頁(yè)，共40頁(yè)。樸素貝葉斯分類(lèi)(續(xù))估計(jì)P(xi|yj)設(shè)第i個(gè)屬性Ai是分類(lèi)屬性,則

P(xi|yj)=nij/nj

其中nij是在屬性Ai上具有值xi的yj類(lèi)的訓(xùn)練樣本數(shù),而nj是yj類(lèi)的訓(xùn)練樣本數(shù)設(shè)第i個(gè)屬性Ai是連續(xù)值屬性把Ai離散化假定Ai服從高斯分布其中,

ij,

ij分別為給定yj類(lèi)的訓(xùn)練樣本在屬性Ai上的均值和標(biāo)準(zhǔn)差5第5頁(yè)，共40頁(yè)。樸素貝葉斯分類(lèi)器所需要的信息計(jì)算每個(gè)類(lèi)的先驗(yàn)概率P(yj):P(yj)=nj/n

其中,nj是yi類(lèi)的訓(xùn)練樣本數(shù),而n是訓(xùn)練樣本總數(shù)對(duì)于離散屬性Ai，設(shè)的不同值為ai1,ai2,…,ail

，對(duì)于每個(gè)類(lèi)yj，計(jì)算后驗(yàn)概率P(aik|yj),1

k

lP(aik|yj)=nikj/nj其中nikj是在屬性Ai上具有值aik

的yj類(lèi)的訓(xùn)練樣本數(shù),而nj是yj類(lèi)的訓(xùn)練樣本數(shù)對(duì)于連續(xù)屬性Ai

和每個(gè)類(lèi)yj，計(jì)算yj類(lèi)樣本的均值

ij,標(biāo)準(zhǔn)差

ij樸素貝葉斯分類(lèi)6第6頁(yè)，共40頁(yè)。貝葉斯分類(lèi)器:例例:Tid有房婚姻狀況年收入拖欠貸款12345678910是否否是否否是否否否單身已婚單身已婚離婚已婚離婚單身已婚單身125K100K70K120K95K60K220K85K75K90KNoNoNoNoYesNoNoYesNoYesP(Yes)=3/10P(No)=7/10P(有房=是|No)=3/7P(有房=否|No)=4/7P(有房=是|Yes)=0P(有房=否|Yes)=1P(婚姻狀況=單身|No)=2/7P(婚姻狀況=離婚|No)=1/7P(婚姻狀況=已婚|No)=4/7P(婚姻狀況=單身|Yes)=2/3P(婚姻狀況=離婚|Yes)=1/3P(婚姻狀況=已婚|Yes)=0年收入：類(lèi)=No：樣本均值=110

樣本方差=2975類(lèi)=Yes：樣本均值=90

樣本方差=25第7頁(yè)，共40頁(yè)。HowtoEstimateProbabilitiesfromData?Normaldistribution:Oneforeach(Ai,ci)pairFor(年收入,Class=No):IfClass=No

樣本均值=110

樣本方差=2975Tid有房婚姻狀況年收入拖欠貸款12345678910是否否是否否是否否否單身已婚單身已婚離婚已婚離婚單身已婚單身125K100K70K120K95K60K220K85K75K90KNoNoNoNoYesNoNoYesNoYes第8頁(yè)，共40頁(yè)。X=（有房=否，婚姻狀況=已婚，年收入=$120K）計(jì)算P(X|No)和P(X|Yes)

P(X|No)=P(有房=否|No)

P(婚姻狀況=已婚|No)

P(年收入=$120K|No) =4/7

4/7

0.0072=0.0024P(X|Yes)=P(有房=否|Yes)

P(婚姻狀況=已婚|Yes)

P(年收入=$120K|Yes) =1

0

1.2

10

9=0計(jì)算P(X|No)P(No)和P(X|Yes)P(Yes)

P(X|No)P(No)=0.00240.7=0.00168P(X|Yes)P(Yes)=00.3=0因?yàn)镻(X|No)P(No)>P(X|Yes)P(Yes),所以X分類(lèi)為No貝葉斯分類(lèi)器:例(續(xù))9第9頁(yè)，共40頁(yè)。貝葉斯分類(lèi)器問(wèn)題如果諸條件概率P(Xi=xi|Y=yj)中的一個(gè)為0，則它們的乘積（計(jì)算P(X|Y=yj)的表達(dá)式）為0很可能每個(gè)P(X|Y=yj)都為0解決方法使用m估計(jì)、Laplace估計(jì):

原估計(jì):P(Xi=xi|Y=yj)=nij/nj10第10頁(yè)，共40頁(yè)。ExampleofNa?veBayesClassifierA:attributesM:mammalsN:non-mammalsP(A|M)P(M)>P(A|N)P(N)=>MammalsP128數(shù)據(jù)第11頁(yè)，共40頁(yè)。對(duì)孤立的噪聲點(diǎn)的魯棒性個(gè)別點(diǎn)對(duì)概率估計(jì)的影響很小容易處理缺失值在估計(jì)概率時(shí)忽略缺失值的訓(xùn)練實(shí)例對(duì)不相關(guān)屬性的魯棒性各類(lèi)在不相關(guān)屬性上具有類(lèi)似分布類(lèi)條件獨(dú)立假設(shè)可能不成立使用其他技術(shù)，如貝葉斯信念網(wǎng)絡(luò)（BayesianBeliefNetworks，BBN）貝葉斯分類(lèi)器的特點(diǎn)12第12頁(yè)，共40頁(yè)。貝葉斯誤差率貝葉斯分類(lèi)器最小化分類(lèi)誤差的概率貝葉斯分類(lèi)使決策邊界總是位于高斯分布下兩類(lèi)1和2的交叉點(diǎn)上類(lèi)C2類(lèi)C113第13頁(yè)，共40頁(yè)。案例：檢測(cè)SNS社區(qū)中不真實(shí)賬號(hào)對(duì)于SNS社區(qū)來(lái)說(shuō)，不真實(shí)賬號(hào)（使用虛假身份或用戶的小號(hào)）是一個(gè)普遍存在的問(wèn)題，作為SNS社區(qū)的運(yùn)營(yíng)商，希望可以檢測(cè)出這些不真實(shí)賬號(hào)，從而在一些運(yùn)營(yíng)分析報(bào)告中避免這些賬號(hào)的干擾，亦可以加強(qiáng)對(duì)SNS社區(qū)的了解與監(jiān)管。

將社區(qū)中所有賬號(hào)在真實(shí)賬號(hào)和不真實(shí)賬號(hào)兩個(gè)類(lèi)別設(shè)C=0表示真實(shí)賬號(hào)，C=1表示不真實(shí)賬號(hào)。14第14頁(yè)，共40頁(yè)。1、確定特征屬性及劃分區(qū)分真實(shí)賬號(hào)與不真實(shí)賬號(hào)的特征屬性，在實(shí)際應(yīng)用中，特征屬性的數(shù)量是很多的，劃分也會(huì)比較細(xì)致為了簡(jiǎn)單起見(jiàn)，用少量的特征屬性以及較粗的劃分，并對(duì)數(shù)據(jù)做了修改。15第15頁(yè)，共40頁(yè)。選擇三個(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.05<a<0.2,a>=0.2}，a2：{a<=0.1,0.1<a<0.8,a>=0.8}，a3：{a=0（不是）,a=1（是）}。16第16頁(yè)，共40頁(yè)。

2、獲取訓(xùn)練樣本

使用運(yùn)維人員曾經(jīng)人工檢測(cè)過(guò)的1萬(wàn)個(gè)賬號(hào)作為訓(xùn)練樣本。

3、計(jì)算訓(xùn)練樣本中每個(gè)類(lèi)別的頻率

用訓(xùn)練樣本中真實(shí)賬號(hào)和不真實(shí)賬號(hào)數(shù)量分別除以一萬(wàn)，得到：

17第17頁(yè)，共40頁(yè)。4、計(jì)算每個(gè)類(lèi)別條件下各個(gè)特征屬性劃分的頻率18第18頁(yè)，共40頁(yè)。

5、使用分類(lèi)器進(jìn)行鑒別使用上面訓(xùn)練得到的分類(lèi)器鑒別一個(gè)賬號(hào)，這個(gè)賬號(hào)使用非真實(shí)頭像，日志數(shù)量與注冊(cè)天數(shù)的比率為0.1，好友數(shù)與注冊(cè)天數(shù)的比率為0.2?？梢钥吹剑m然這個(gè)用戶沒(méi)有使用真實(shí)頭像，但是通過(guò)分類(lèi)器的鑒別，更傾向于將此賬號(hào)歸入真實(shí)賬號(hào)類(lèi)別。這個(gè)例子也展示了當(dāng)特征屬性充分多時(shí)，樸素貝葉斯分類(lèi)對(duì)個(gè)別屬性的抗干擾性。19第19頁(yè)，共40頁(yè)。貝葉斯信念網(wǎng)絡(luò)(Bayesianbeliefnetwork)允許在變量的子集間定義類(lèi)條件獨(dú)立性因果關(guān)系圖模型表示變量之間的依賴給出聯(lián)合概率分布的說(shuō)明圖示結(jié)點(diǎn):隨機(jī)變量弧:依賴X,Y

是Z的父節(jié)點(diǎn)/前驅(qū),并且Y

是P的父節(jié)點(diǎn)/前驅(qū)Z

和P之間沒(méi)有依賴關(guān)系,圖中沒(méi)有環(huán)貝葉斯信念網(wǎng)絡(luò)20第20頁(yè)，共40頁(yè)。貝葉斯信念網(wǎng)絡(luò):例變量LungCance(LC)值的條件概率表(CPT),給出其雙親結(jié)點(diǎn)FamilyHistory和Smoke的每個(gè)可能值的組合的條件概率21第21頁(yè)，共40頁(yè)。給出了LungCancer的CPT.對(duì)于其雙親值的每個(gè)可能組合,表中給出了LungCancer的每個(gè)值的條件概率.例如,由左上角和右下角,分別看到：

P(LungCancer=“yes”|FamilyHistory=“yes”,Smoker=“yes”)=0.8 P(LungCancer=“no”|FamilyHistory=“no”,Smoker=“no”)=0.922第22頁(yè)，共40頁(yè)。對(duì)應(yīng)于屬性或變量Z1,…,Zn的任意元組(z1,…,zn)的聯(lián)合概率由下式計(jì)算

其中,P(zi|parents(zi))的值對(duì)應(yīng)于Zi的CPT中的表目23第23頁(yè)，共40頁(yè)。若干情況給定網(wǎng)絡(luò)結(jié)構(gòu)和所有可觀測(cè)變量只需要學(xué)習(xí)CPT網(wǎng)絡(luò)結(jié)構(gòu)已知,而某些變量是隱藏的使用梯度下降法或類(lèi)似于神經(jīng)網(wǎng)絡(luò)的方法訓(xùn)練信念網(wǎng)絡(luò)網(wǎng)絡(luò)結(jié)構(gòu)未知,所有的變量可以觀測(cè)搜索模型空間,構(gòu)造網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)結(jié)構(gòu)未知,所有變量是隱藏的沒(méi)有已知的好算法D.Heckerman,Bayesiannetworksfordatamining訓(xùn)練貝葉斯信念網(wǎng)絡(luò)24第24頁(yè)，共40頁(yè)。梯度下降法設(shè)S是s個(gè)訓(xùn)練樣本X1,X2,...,Xs的集合,wijk是具有雙親Ui=uik的變量Y=yij的CPT項(xiàng)wijk可以看作權(quán),類(lèi)似于神經(jīng)網(wǎng)絡(luò)中隱藏單元的權(quán).權(quán)的集合記作w

這些權(quán)被初始化為隨機(jī)概率值.梯度下降策略采用貪心爬山法.在每次迭代中,修改這些權(quán),并最終收斂到一個(gè)局部最優(yōu)解基于w的每個(gè)可能設(shè)置都等可能的假定,該方法搜索能最好地對(duì)數(shù)據(jù)建模wijk值.目標(biāo)是最大化訓(xùn)練貝葉斯信念網(wǎng)絡(luò)25第25頁(yè)，共40頁(yè)。使用BBN進(jìn)行推理舉例E:鍛煉,D:飲食,HD:心臟病,Hb:胸口痛,BP:血壓,CP:胸痛鍛煉飲食心口痛心臟病血壓胸痛D=健康D=健康D=不健康健康不健康健康不健康BP=高26第26頁(yè)，共40頁(yè)。通過(guò)計(jì)算先驗(yàn)概率P(HD=Yes)和P(HD=No)來(lái)確定一個(gè)人是否可能患心臟病設(shè)

∈{Yes,No}表示鍛煉的兩個(gè)值，

∈{健康,不健康}表示飲食的兩個(gè)值，由全概率公式P(HD=Yes)=

= =0.25

0.7

0.25+0.45

0.7

0.75+0.55

0.3

0.25+0.75

0.3

0.75

=0.49因?yàn)镻(HD=No)=1

P(HD=Yes)=0.51，所以，此人不得心臟病的機(jī)率略微大一點(diǎn)情況一：沒(méi)有先驗(yàn)信息27第27頁(yè)，共40頁(yè)。P(HD=Yes)=

= =0.25

0.7

0.25+0.45

0.7

0.75+0.55

0.3

0.25+0.75

0.3

0.75 =0.49P(HD=Yes)鍛煉飲食心口痛心臟病血壓胸痛D=健康D=健康D=不健康健康不健康健康不健康BP=高28第28頁(yè)，共40頁(yè)。情況二：高血壓如果一個(gè)人有高血壓，可以通過(guò)比較后驗(yàn)概率P(HD=Yes|BP=高)和P(HD=No|BP=高)來(lái)診斷他是否患有心臟病先用全概率公式，計(jì)算P(BP=高)P(BP=高)= =0.85

0.49+0.2

0.51=0.5185其中{Yes,No}用貝葉斯公式計(jì)算此人患心臟病的后驗(yàn)概率29第29頁(yè)，共40頁(yè)。情況三高血壓、飲食健康、經(jīng)常鍛煉身體患心臟病的后驗(yàn)概率飲食健康、經(jīng)常鍛煉身體，可以降低患心臟病的風(fēng)險(xiǎn)30第30頁(yè)，共40頁(yè)。BBN提供了一種用圖形模型來(lái)捕獲特定領(lǐng)域的先驗(yàn)知識(shí)的方法。網(wǎng)絡(luò)還可以用來(lái)對(duì)變量間的因果依賴關(guān)系進(jìn)行編碼構(gòu)造網(wǎng)絡(luò)可能既費(fèi)時(shí)又費(fèi)力。然而，一旦網(wǎng)絡(luò)結(jié)構(gòu)確定下來(lái)，添加新變量就十分容易貝葉斯網(wǎng)絡(luò)很適合處理不完整的數(shù)據(jù)。對(duì)有屬性遺漏的實(shí)例可以通過(guò)對(duì)該屬性的所有可能取值的概率求和或求積分來(lái)加以處理因?yàn)閿?shù)據(jù)和先驗(yàn)知識(shí)以概率的方式結(jié)合起來(lái)了，所以該方法對(duì)模型的過(guò)分?jǐn)M合問(wèn)題是非常魯棒的BBN的特點(diǎn)31第31頁(yè)，共40頁(yè)。訓(xùn)練貝葉斯信念網(wǎng)絡(luò):梯度下降法給定網(wǎng)絡(luò)結(jié)構(gòu)和wijk的初值,該算法按以下步驟處理計(jì)算梯度：對(duì)每個(gè)i,j,k，計(jì)算沿梯度方向前進(jìn)一小步:用下式更新權(quán)值

l是表示步長(zhǎng)的學(xué)習(xí)率,設(shè)置為一個(gè)小常數(shù)重新規(guī)格化權(quán)值：由于權(quán)值wijk是概率值,它們必須在0.0和1.0之間,并且對(duì)于所有的i,k，必須有32第32頁(yè)，共40頁(yè)。補(bǔ)充：梯度下降法簡(jiǎn)介梯度下降法又稱(chēng)最速下降法。函數(shù)J(a)在某點(diǎn)ak的梯度是一個(gè)向量，其方向是J(a)增長(zhǎng)最快的方向。顯然，負(fù)梯度方