數(shù)據(jù)挖掘技術(shù)十課Bayes分類方法.ppt

數(shù)據(jù)挖掘技術(shù) 第十課 Bayes分類方法,主要內(nèi)容,樸素Bayes分類 Bayes網(wǎng)絡(luò) 集成方法,Bayes分類器,一個用于解決分類問題的概率框架 條件概率: Bayes定理:,Bayes定理舉例,給定: 50%的腦膜炎患者脖子僵硬 人得腦膜炎的概率是1/50,000 脖子僵硬的人的概率是 1/20 若某個患者脖子僵硬,則他患腦膜炎的概率是多少?,Bayes分類器,將每個屬性及類別標(biāo)記視為隨機(jī)變量 給定一個具有屬性集合(A1, A2,An)的記錄 目標(biāo)是預(yù)測類別屬性C 具體而言，要尋找使得P(C| A1, A2,An )最大的類別C,Bayes分類器,方法: 利用Bayes定理計(jì)算所有類別C的后驗(yàn)概率P(C | A1, A2, , An) 選擇使如下概率值最大的類別C P(C | A1, A2, , An) 等價于使如下概率值最大 P(A1, A2, , An|C) P(C),樸素Bayes分類器,假定給定類別的條件下屬性Ai之間是獨(dú)立的: P(A1, A2, , An |C) = P(A1| Cj) P(A2| Cj) P(An| Cj) 可以從Ai和Cj中估算出P(Ai| Cj) 類別為使P(Cj) P(Ai| Cj)最大的類Cj,如何從數(shù)據(jù)中估算概率,類: P(C) = Nc/N e.g., P(No) = 7/10, P(Yes) = 3/10 對離散屬性k: P(Ai | Ck) = |Aik|/ Nc 其中|Aik|是屬于類Ck，并具有屬性值A(chǔ)i的記錄數(shù)量 如: P(Status=Married|No) = 4/7 P(Refund=Yes|Yes)=0,如何從數(shù)據(jù)中估算概率,對連續(xù)屬性: 將區(qū)間離散化至不同的桶 違背了獨(dú)立性假設(shè) 2路分割: (A v) 或 (A v) 概率密度估計(jì): 假設(shè)屬性的取值服從正態(tài)分布 使用已有數(shù)據(jù)來估算分布的參數(shù)(如, 均值和方差) 若概率分布已知，則使用其來估算條件概率P(Ai|c),如何從數(shù)據(jù)中估算概率,正態(tài)分布: 對(Income, Class=No): 若Class=No sample mean = 110 sample variance = 2975,樸素Bayes分類舉例,P(X|Class=No) = P(Refund=No|Class=No) P(Married| Class=No) P(Income=120K| Class=No) = 4/7 4/7 0.0072 = 0.0024 P(X|Class=Yes) = P(Refund=No| Class=Yes) P(Married| Class=Yes) P(Income=120K| Class=Yes) = 1 0 1.2 10-9 = 0 Since P(X|No)P(No) P(X|Yes)P(Yes) Therefore P(No|X) P(Yes|X) = Class = No,給定一條測試記錄:,樸素Bayes分類舉例,A: attributes M: mammals N: non-mammals,P(A|M)P(M) P(A|N)P(N) = Mammals,樸素Bayes分類器小結(jié),抗噪聲能力強(qiáng) 在概率估算階段，通過忽略整條記錄來處理缺失值 抗無關(guān)屬性的能力強(qiáng) 屬性獨(dú)立的假設(shè)可能對某些屬性不成立 可以使用Bayes信度網(wǎng)絡(luò)(Bayesian Belief Networks, BBN),主要內(nèi)容,樸素Bayes分類 Bayes網(wǎng)絡(luò) 集成方法,Bayes網(wǎng)絡(luò),20世紀(jì)80年代，Bayes網(wǎng)絡(luò)(Bayes Network)成功應(yīng)用于專家系統(tǒng)，成為表示不確定性專家知識和推理的一種流行的方法。 在不確定性表示、可信度計(jì)算上還是使用概率方法。 實(shí)現(xiàn)時，要根據(jù)應(yīng)用背景采用近似計(jì)算方法。,事件的獨(dú)立性,獨(dú)立：如果X與Y相互獨(dú)立，則 P(X,Y) = P(X)P(Y) P(X|Y) = P(X) 條件獨(dú)立：如果在給定Z的條件下，X與Y相互獨(dú)立，則 P(X|Y, Z) = P(X|Z) 實(shí)際中，條件獨(dú)立比完全獨(dú)立更普遍,聯(lián)合概率,聯(lián)合概率：P(X1, X2, , XN) 如果相互獨(dú)立： P(X1, X2, , XN) = P(X1) P(X2) P(XN) 條件概率： P(X1, X2, , XN) = P(X1|X2, , XN) P(X2, , XN) 迭代表示： P(X1, X2, , XN) = P(X1) P(X2| X1) P(X3| X2X1)P(XN|XN-1, , X1) = P(XN) P(XN-1| XN) P(XN-2| XN-1XN)P(X1|X2, , XN) 實(shí)際應(yīng)用中就是利用條件獨(dú)立來簡化網(wǎng)絡(luò)。,Bayes網(wǎng)絡(luò),一系列變量的聯(lián)合概率分布的圖形表示。 一個表示變量之間相互依賴關(guān)系的數(shù)據(jù)結(jié)構(gòu)，圖論與概率論的結(jié)合。,Bayes網(wǎng)絡(luò)（續(xù)）,兩部分 結(jié)構(gòu)圖，有向無環(huán)圖(Directed Acyclic Graph, DAG)，每個節(jié)點(diǎn)代表相應(yīng)的變量。 條件概率表(Conditional Probability Table, CPT)，一系列的概率值，表示局部條件概率分布，即P(node|parents) 。,Bayes網(wǎng)絡(luò)的構(gòu)造,選擇變量，生成節(jié)點(diǎn) 從左至右（從上到下），排列節(jié)點(diǎn) 填充網(wǎng)絡(luò)連接弧，表示節(jié)點(diǎn)之間的關(guān)系 得到條件概率關(guān)系表 條件概率表示的概率網(wǎng)絡(luò)有時叫“Belief Nets”,由Bayes網(wǎng)絡(luò)計(jì)算概率,簡單的聯(lián)合概率可以直接從網(wǎng)絡(luò)關(guān)系上得到，如： P(X, Y, Z) = P(X)P(Y)P(Z|X, Y),Bayes網(wǎng)絡(luò)舉例,假設(shè)： 命題S(Smoker)：該患者是一個吸煙者 命題C(Coal Miner)：該患者是一個煤礦礦井工人 命題L(Lung Cancer)：他患了肺癌 命題E(Emphysema)：他患了肺氣腫 已知：S對L和E有因果影響，C對E也有因果影響。 命題間的關(guān)系可以描繪成Bayes網(wǎng)絡(luò)。 每個節(jié)點(diǎn)代表一個證據(jù) 每一條弧代表一條規(guī)則（假設(shè)） 弧表達(dá)了由規(guī)則給出的、節(jié)點(diǎn)間的直接因果關(guān)系。,Bayes網(wǎng)絡(luò)舉例,CPT表為： P(S) = 0.4 P(C) = 0.3 P(E|S, C) = 0.9 P(E|S, C) = 0.3 P(E|S, C) = 0.5 P(E|S, C) = 0.1,Bayes網(wǎng)絡(luò)舉例（續(xù)）,上圖例中的聯(lián)合概率密度為 變量與它在圖中的非繼承節(jié)點(diǎn)在是概率獨(dú)立的。 P(E|S,C,L) P(E|S,C) (E與L在S條件下獨(dú)立) P(L|S,C)= P(L|S) (L與C在S, E條件下獨(dú)立) P(C|S)=P(C) (C與S在E條件下獨(dú)立) 簡化后的聯(lián)合概率密度為:,Bayes網(wǎng)絡(luò)的推理,主要用于因果推理和診斷推理 由因?qū)Ч?，P(肺癌|吸煙) 執(zhí)果索因，P(吸煙|肺癌) 一般情況下是很困難的，原因 不是所有的CPT表都能夠得到 網(wǎng)絡(luò)結(jié)構(gòu)大且復(fù)雜，NP-hard問題,Bayes網(wǎng)絡(luò)的因果推理,已知父節(jié)點(diǎn)，計(jì)算子節(jié)點(diǎn)的條件概率。 主要操作： 重新表達(dá)所求的條件概率。 直到所有的概率值可從CPT中得到，推理完成。,因果推理舉例,給定患者是一個吸煙者(S)，計(jì)算他患肺氣腫(E)的概率P(E|S)。,首先，引入E的另一個父節(jié)點(diǎn)(C)，P(E|S)=P(E,C|S)+P(E,C|S) 右邊的第一項(xiàng) ， P(E,C|S)P(E,C,S)/P(S)P(E|C,S)*P(C,S)/P(S)P(E|C,S)*P(C) 同理可得右邊的第二項(xiàng)為：P(E,C|S) = P(E|C,S)*P(C)。 由此可得：P(E|S) = P(E| C,S)*P(C)+P(E|C,S)*P(C) P(C) = 1 P(C)，則有： P(E|S)0.9*0.3+0.3*(1-0.3)=0.48,Bayes網(wǎng)絡(luò)的診斷推理,在Bayes網(wǎng)中，從一個子節(jié)點(diǎn)出發(fā)計(jì)算父節(jié)點(diǎn)的條件概率，即從結(jié)果推測起因。 主要操作：使用Bayes公式把診斷推理轉(zhuǎn)換成因果推理。,診斷推理舉例,計(jì)算在不得肺氣腫的人中，不是礦工的概率，即P(C|E)。,P(C|E) = P(E|C)*P(C)/P(E) 由因果推理可知： P(E|C) = P(E, S|C)+P(E, S|C) = P (E|S,C)P(S)+P (E|S,C)P(S) = (10.3)*0.4+(10.1)* (10.4)=0.82 由此得：P(C|E) = P(E|C)*P(C) / P(E) = 0.82*(10.3) / P(E)=0.574/ P(E) 同樣， P(C|E) = P(E|C)*P(C) / P(E)=0.102 / P(E) 由于全概率公式， P(C|E)+ P(C|E)=1 代入得， P(E)=0.676 所以， P(C|E) = 0.849,Bayes方法預(yù)測2010世界杯,World Cup Group C,England beating Argentina,/,主要內(nèi)容,樸素Bayes分類 Bayes網(wǎng)絡(luò) 集成方法,集成方法(Ensemble),從訓(xùn)練數(shù)據(jù)中構(gòu)建一系列的分類器。 使用多個分類器共同分類。,核心思想,為什么使用集成方法,假設(shè)有25個基本的2分類器 每個分類器具有同樣的錯誤率 = 0.35 假定這些分類器是互相獨(dú)立的 則Ensemble方法出錯的概率為:,集成方法優(yōu)于單個分類器的條件,基本分類器相互獨(dú)立 基本分類器的正確率優(yōu)于隨機(jī)猜測。,常用的集成方法,如何構(gòu)造集成分類器 Bagging Boosting,Bagging: 基本算法,給定S個樣本。 在S中做有替代的抽樣，其結(jié)果記為T，S中原來的樣本在T中可出現(xiàn)多次，也可一次都不出現(xiàn)。 重復(fù)這種抽樣，得到k個獨(dú)立的訓(xùn)練集。 使用同樣的算法在這些訓(xùn)練集上構(gòu)建k個分類器C1, C2, , Ck。 對一個待分類樣本i，每個分類器都獨(dú)立對其進(jìn)行分類。 樣本i的類別標(biāo)記為大多數(shù)分類器給出的類別。,Bo