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

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