《數據挖掘基礎及其應用》課件第6章

第6章分類Ⅲ:概率分類與回歸6.1引言6.2貝葉斯公式6.3貝葉斯分類算法6.4貝葉斯信念網絡6.5回歸分析本章小結

6.1引言

決策樹是一種描述對實例進行分類的樹形結構。決策樹具有速度快、分類結果可解釋性高等優(yōu)勢,但是決策樹算法存在如下幾個方面的缺陷:(1)過擬合導致剪枝問題。(2)算法魯棒性低,導致決策樹的結果可能是不穩(wěn)定的,因為在數據中一個很小的變化可能導致生成一個完全不同的樹,這個問題可以通過使用集成決策樹來解決。

(3)NP難問題:學習一個最優(yōu)決策樹是NP難問題。

(4)一些概念是很難理解的:比如異或校驗或復用的問題。

(5)準確性得不到保障。

決策樹算法的缺陷如圖6-1所示。圖6-1決策樹算法的缺陷

若要有效地避免決策樹算法帶來的缺陷,則需要構建全新的算法。通過提供圖形化的方法來表示和運算概率知識,貝葉斯網絡克服了基于規(guī)則的系統(tǒng)在概念和計算上的困難。

貝葉斯網絡與統(tǒng)計方法相結合,使得其在數據分析方面擁有了許多優(yōu)點,具體如下:

(1)圖形方法描述數據間的相互關系,語義清晰,易于理解。

(2)易于處理不完備數據集。

(3)允許學習變量間的因果關系。

(4)充分利用領域知識和樣本數據的信息。

6.2貝葉斯公式

6.2.1概率基礎概率論具有堅實的數學理論基礎,是數據挖掘領域中處理不確定性問題的基礎理論之一,也是目前處理不確定性問題的方法之一。

定義6.1(條件概率)設A,B是兩個基本事件,且P(A)>0,則稱

為事件A發(fā)生的條件下事件B發(fā)生的條件概率。

定義6.2(先驗概率)設B1,B2,…,Bn為樣本空間S中的事件,P(Bi)可根據以前的數據分析得到,或根據先驗知識估計獲取,稱P(Bi)為先驗概率。

先驗概率是根據歷史資料或主觀判斷所確定的各種事件發(fā)生的概率,該概率沒有經過實驗證實,屬于檢驗前的概率。先驗概率一般分為兩類:一類是客觀先驗概率,是指利用過去的歷史資料計算得到的概率;另一類是主觀先驗概率,是指在無歷史資料或者歷史資料不全時,只憑借人們的主觀經驗來判斷取得的概率。

定義6.3(后驗概率)設B1,B2,…,Bn為樣本空間S中的事件,則事件A發(fā)生的情況下,Bi發(fā)生的概率P(Bi

A)可根據先驗概率P(Bi)和觀測信息重新修正和調整后得到,通常將P(Bi

A)稱為后驗概率。

后驗概率一般是指利用貝葉斯公式,結合調查等方式獲取了新的附加信息,對先驗概率加以修正的更符合實際的概率,即得到信息之后再重新修正的概率。

定義6.4(聯(lián)合概率)設A,B為兩個事件,且P(A)>0,則它們的聯(lián)合概率為

聯(lián)合概率也稱為乘法公式,是指兩個任意時間的乘積的概率,或稱為交事件的概率。

定義6.5(全概率公式)如果影響事件A的所有因素B1,B2,…,Bn滿足Bi·Bj=φ(i≠j),并且P(Bi)>0,則

定義6.6(貝葉斯概率)貝葉斯概率是觀測者對某一事件發(fā)生的相信程度。觀測者根據先驗知識和現(xiàn)有的統(tǒng)計數據,用概率的方法來預測未知事件發(fā)生的可能性。貝葉斯概率

不同于事件的客觀概率,客觀概率是在多次重復實驗中事件發(fā)生頻率的近似值,而貝葉斯概率則是利用現(xiàn)有的知識對未知事件的預測。

定義6.7(貝葉斯公式)貝葉斯公式也稱為后驗概率公式,或者逆概率公式,其用途很廣。設先驗概率為P(Bi),調查所獲得的新附加信息為P(A|Bi

),其中i=1,2,…,n,則后驗概率為

定義6.8(條件獨立)對概率模式M,A、B和C是U的三個互不相交的變量子集,如果對?x∈A,?y∈B和?z∈C,都有p(x|y,z)=p(x|z),其中p(y,z)>0,稱給定C時A和B條件獨立,記為I(A,C,B)M。

條件獨立性在某些文獻中定義為p(x,y|z)=p(x|z)p(y|z),可以證明這兩個定義是等價的。

定義6.9概率分類中{X1,X2,…,Xn,C}是樣本空間T的屬性集。其中,Xi(i=1,2,…,n)是特征屬性,C是類屬性。Xi

可能是離散變量,也可能是連續(xù)變量。xi和c分別表示屬性Xi

和C的任意取值。

定義6.10P(?)表示離散的概率值,p(?)表示連續(xù)的概率密度函數值。Count(?)表示樣本空間的大小。

6.2.2圖論基礎

定義6.11(有向圖G)由節(jié)點集V、邊集E表示的二元組G=G(V,E),若(x,y)∈E表示從節(jié)點x到節(jié)點y有一條有向邊,我們也稱節(jié)點x和節(jié)點y是鄰接的或x和y相互為鄰居。x也叫作y的父節(jié)點,y叫作x的子節(jié)點。通過父親和孩子概念的遞歸定義,同時獲得了祖先和后繼兩個概念。沒有父節(jié)點的節(jié)點被稱為根節(jié)點。

定義6.12(路徑)在貝葉斯網絡學習中,連接兩個節(jié)點的路徑不考慮這條路徑中邊的方向,這個定義對有向圖、無向圖和混合圖都是適用的。

定義6.13(有向循環(huán)圖)有向循環(huán)圖(DirectedAcyclicGraph,DAG)也稱有向無環(huán)圖,即不包含環(huán)路的有向圖,如圖6-2所示。

定義6.14(匯聚節(jié)點)對于一條鄰接路徑中的任何一個節(jié)點v,如果有(x,v)∈E并且(y,v)∈E,則稱v為匯聚節(jié)點或碰撞節(jié)點(Collider)。圖6-2有向無環(huán)圖

6.2.3信息理論

定義6.15(信息熵)設信源X為離散隨機變量,則用來度量X的不確定性的信息熵為

定義6.16(聯(lián)合信息熵)設X、Y為離散隨機變量,則用來度量二元隨機變量不確定性的聯(lián)合信息熵H(X,Y)為

定義6.17(條件信息熵)用來度量在得到隨機變量Y的信息后,隨機變量X仍然存在的不確定性。條件信息熵H(X|Y)為

定義6.18(互信息)用來描述隨機變量Y提供的關于X的信息量的大小,隨機變量X、Y之間的互信息為

定義6.19(條件互信息)在已知Y的前提下,隨機變量X和Z之間的條件互信息定義為

從條件互信息可以看出,在給定測試集的條件下,如果X和Z一致性條件獨立時,即P(x;z|y)=P(x|y)P(z|y)成立,則X和Z之間的條件互信息為0。當I(X;Z)小于某個極限值ε時,稱X和Z為邊際獨立;當I(X;Z|Y)小于某個極限值ε時,稱X和Z為條件獨立。X和Z之間的條件互信息越大,則說明在給定觀測集的條件下,X和Z之間的概率依賴性越明顯。反映在貝葉斯網絡上,如果Y為X的父節(jié)點集合,則當X和Z之間的條件互信息較大時,說明Z也可能是X的父節(jié)點,其關系如圖6-3所示。圖6-3互信息與信息熵關系圖

6.3貝葉斯分類算法

6.3.1算法原理貝葉斯網絡的原理是利用貝葉斯公式構建依賴關聯(lián)網絡進行分類。通常,事件X在事件Y(發(fā)生)的條件下的概率,與事件Y在事件X的條件下的概率是不一樣的。但這兩者有確定的關系,貝葉斯法則就是這種關系的陳述。

貝葉斯法則是關于隨機事件X和Y的條件概率和邊緣概率,即

式中:P(X|Y)是在Y發(fā)生的情況下X發(fā)生的可能性。貝葉斯法則可描述為

其解釋為后驗概率=似然度×先驗概率/標準化常量。也就是說,后驗概率與先驗概率和似然度的乘積成正比。P(

X|Y)/P(X)有時也被稱作標準似然度(Standardized

Likelihood),貝葉斯法則又可表述為:后驗概率=標準似然度×先驗概率。

例如,如果事先已知腦膜炎導致斜頸的概率是0.5,一個病人患有腦膜炎的先驗概率是1/50000,病人患有斜頸的先驗概率是1/20,那么在已知一個病人患有斜頸的情況下,他患腦膜炎的概率是多少?

構建貝葉斯網絡的關鍵在于如何分解任務,給定訓練數據。如圖6-4所示,預測一個貸款者是否會拖欠還款,其訓練集有如下屬性:是否有房、婚姻狀況和年收入。拖欠還款的貸款者屬于類“是”,還清貸款的貸款者屬于類“否”。貝葉斯公式分類的關鍵問題是:隨機變量是什么?目標變量是什么?目標是什么?先驗概率如何計算?條件概率如何計算?圖6-4貝葉斯網絡構建的主要問題

從數據中估計后驗概率是貝葉斯分類算法的一個難點,要估計后驗概率,可利用貝葉斯網絡將后驗概率轉化為先驗概率與條件概率之積:

(1)變量確定問題:將屬性(包括類別屬性)都看成隨機變量,其中屬性變量可表示為(X1,X2,…,Xd),類別屬性可表示為Y。

(2)目標確定問題:最大化后驗概率P

(Y|X1,X2,…,Xd)。

(3)難點:如何從數據中估計后驗概率P

(Y|X1,X2,…,Xd)。

貝葉斯網絡推理過程如圖6-5所示,假設給定已測試記錄有如下屬性集:X=(有房=否,婚姻狀況=已婚,年收入=12萬元)。要分類該記錄,我們需要利用訓練數據中的可用信息計算后驗概率P(拖欠貸款=是|X)和P(拖欠貸款=否|X)。如果P(拖欠貸款=是|X)>P(拖欠貸款=否|X),那么記錄分類為是;反之,分類為否。

要估計后驗概率,可利用貝葉斯網絡將后驗概率轉化為先驗概率與條件概率之積,即

由于分母是固定值,所以上式等價于最大化圖6-5貝葉斯網絡推理過程

6.3.2樸素貝葉斯算法

樸素貝葉斯分類器在估計類條件概率時的前提假設是:屬性之間條件獨立,即

式中:每個屬性集X={X1,X2,…,Xd}包含d個屬性。

分類測試記錄時,樸素貝葉斯分類器對每個類Y計算后驗概率:

由于對于所有的Y,P(X)都是固定的,因此只要找出使分子

最大的類就足夠了。下面描述幾種估計分類屬性和連續(xù)屬性的條件概率P

(Xi|Y)的方法。規(guī)約樸素貝葉斯分類任務和目標為:

目標:主要目標是估計先驗概率與條件概率P(Yj),P

(Xi|Yj

);

任務:新數據對象如何分類?只需計算P(Yj

)P

(Xi|Yj)。

例如,給定如下數據,對于圖6-5給定的問題,構建樸素貝葉斯網絡可分三步驟:首先利用貝葉斯公式進行轉換(如圖6-6所示),其次利用數據估計條件概率與先驗概率(如圖6-7所示),最后利用貝葉斯網絡推理概率(如圖6-8所示)。圖6-6-樸素貝葉斯網絡構建步驟1

對于分類屬性Xi,根據類Yj

中屬性值等于Xi的訓練實例的比例來估計條件概率P(Xi|Y=Yj

)。例如,在圖6-6中,還清貸款的7個人中3個人有房,因此條件概率P(有房=是|否)=3/7。同理,拖欠貸款的人中單身的條件概率P(婚姻狀況=單身|是)=2/3。

注意:上述方法的缺陷在于只能針對離散的屬性進行先驗概率估計與條件概率估計,如果屬性值是連續(xù)值,則通常采用兩類方法:

一是離散化

二是概率密度函數估計圖6-7樸素貝葉斯網絡構建步驟2１

如何解決極端情況:即通常數據不完備、樣本量少所造成的先驗知識為0的情況,這時的后驗概率難以預測,如圖6-9所示。圖6-9樸素貝葉斯在極端情況下不能有效預測

如何有效解決這類極端問題?可以通過以下方式重新估計先驗概率

問題1:樸素貝葉斯分類器算法的優(yōu)點和缺點是什么?

提示:從原理、推理方法等方面考慮。

樸素貝葉斯網絡的特點是:一個中心、三大優(yōu)勢、四項缺點。

一個中心:條件獨立性

三大優(yōu)勢:

?樸素貝葉斯模型發(fā)源于古典數學理論,有穩(wěn)定的分類效率;

?對小規(guī)模的數據表現(xiàn)很好,能處理多分類任務,適合增量式訓練,尤其是數據量超出內存時;

?對缺失數據不太敏感,算法簡單。

四項缺點:

?理論上,與其他分類方法相比,樸素貝葉斯模型具有最小的誤差率。

?需要知道先驗概率,且先驗概率很多時候取決于假設,而假設的模型可以有很多種。

?通過先驗概率和數據來決定后驗的概率從而決定分類,所以分類決策存在一定的錯誤率。

?對輸入數據的表達形式很敏感。

6.3.3算法應用

1.第一階段:確定特征屬性及劃分

確定分類隨機變量:設C=0表示真實賬號,C=1表示不真實賬號。這一步要找出可區(qū)分真實賬號與不真實賬號的特征屬性,在實際應用中,特征屬性的數量是很多的,劃分也會比較細致,但這里為了簡單起見,我們使用少量的特征屬性以及較粗的劃分。

選擇特征:選擇如表6-1所示的三個特征屬性。

獲取訓練樣本:人工檢測過的1萬個賬號作為訓練樣本。

2.第二階段:模型構建

獲取先驗概率:用訓練樣本中真實賬號和不真實賬號的數量分別除以1萬,即

獲取條件概率:每個類別條件下各個特征屬性劃分的頻率如圖6-10所示。圖6-10每個類別條件下各個特征屬性劃分的頻率

3.第三階段:分類應用

使用上面訓練得到的分類器鑒別一個賬號,這個賬號日志數量與注冊天數的比率a1為0.1,好友數與注冊天數的比率a2為0.2,使用非真實頭像a3=0。

樸素貝葉斯分類如下:

6.4貝葉斯信念網絡

6.4.1定義與推理(1)真實賬號比非真實賬號平均具有更大的日志密度、更大的好友密度,以及更多地使用真實頭像。(2)日志密度、好友密度和是否使用真實頭像在賬號真實性給定的條件下是獨立的。

為了獲取更準確的分類,可以將假設修改如下:

(1)真實賬號比非真實賬號平均具有更大的日志密度、更大的好友密度,以及更多的地使用真實頭像。

(2)日志密度與好友密度、日志密度與是否使用真實頭像在賬號真實性給定的條件下是獨立的。

(3)使用真實頭像的用戶比使用非真實頭像的用戶平均有更大的好友密度。

對于圖6-11所示的兩個數據集,利用樸素貝葉斯分類器都不能有效分類(圖中點代表數據對象,同一形狀的數據對象隸屬于同一類),其原因在于條件概率假設的前提不能成立,因此需要更復雜、更有力的工具來刻畫與描述數據之間的關系。圖6-11非條件獨立數據

貝葉斯網絡有兩個主要成分:有向無環(huán)圖和概率表。

(1)有向無環(huán)圖(DirectedAcyclicGraph,DAG)表示變量之間的依賴關系?？紤]三個隨機變量A、B和C,其中A和B相互獨立,并且都直接影響第三個變量C。三個變量之間的關

系可以用圖6-12(a)中的有向無環(huán)圖概括。圖中每個節(jié)點表示一個變量,每條弧表示兩個變量之間的依賴關系。如果從X到Y有一條有向弧,則X是Y的父母,Y是X的子女。另外,如果網絡中存在一條從X到Z的有向路經,則X是Z的祖先,而Z是X的后代。例如,在圖6-12(b)中,A是D的后代,D是B的祖先,而且B和D都不是A的后代節(jié)點。圖6-12使用DAG表示變量之間的依賴關系

貝葉斯網絡的一個重要性質表述如下:

性質6.1(條件獨立)貝葉斯網絡中的一個節(jié)點,如果它的父母節(jié)點已知,則它條件獨立于它的所有非后代節(jié)點。

(

2)每個屬性一個條件概率表(ConditionalProbabilityTable,CPT),該表把各節(jié)點和它的直接父節(jié)點關聯(lián)起來。DAG包含兩類節(jié)點,一類是無父節(jié)點,一類是有父節(jié)點。第一類節(jié)點所對應的概率是先驗概率,第二類節(jié)點對應的是條件概率,如圖6-13所示。

給定貝葉斯信念網絡,可采用聯(lián)合概率推理方式進行推理,即圖6-13DAG包含的兩類節(jié)點

圖6-14是貝葉斯網絡的一個例子,用于對心臟病患者建模。假設圖中每個變量都是二值的。心臟病節(jié)點(HD)的父母節(jié)點對應于影響該疾病的危險因素,如運動(E)和飲食(D)等。心臟病節(jié)點的子節(jié)點對應于該病的癥狀,如胸痛(CP)和高血壓(BP)等。如圖6-14所示,心臟病(HD)可能源于不健康的飲食,同時又可能導致胸痛。圖6-14貝葉斯信念網絡示意圖

圖6-15貝葉斯信念網絡概率推理過程

6.4.2結構學習(網絡構建)

貝葉斯信念網絡的建模包括兩個步驟:

①創(chuàng)建網絡結構;

②估計每一個節(jié)點概率表中的概率值,可以通過最大化后驗概率獲取最佳的貝葉斯網絡。

網絡拓撲結構可以通過對主觀的領域專家知識編碼獲得。

例如,考慮圖6-14中的變量執(zhí)行算法6.1的步驟1后,設變量次序為(E,D,HD,CP,BP)。從變量D開始,經過步驟2到步驟7,得到如下的條件概率:

當模型很復雜時,使用枚舉式的方法來求解概率就會變得非常復雜且難以計算,因此必須使用其他的替代方法。一般來說,有以下幾種求法:

(1)精確推理,包括枚舉推理法、消元算法(VariableElimination)。

(2)近似推理,包括蒙特卡洛方法、直接取樣算法、拒絕取樣算法、概率加權算法。

一般而言,推估網絡的結構會比推估節(jié)點上的參數要困難。依照對貝葉斯網絡結構的了解和觀測值的完整與否,分別討論下面兩種情況:

1.結構已知,觀測值完整

此時可以用最大似然估計法(MaximumLikelihoodEstimation,MLE)來求得參數。其

對數概率函數為

以圖6-16為例,假設有兩個服務器(S1,S2),會傳送數據包到用戶端(以U表示),但是第二個服務器的數據包傳送成功率與第一個服務器傳送成功與否有關,因此貝葉斯網絡的結構圖可以表示成圖6-16的形式。就每個數據包傳送而言,只有兩種可能值:T(成功)或F(失敗)。我們可以求出節(jié)點U的最大似然估計式為

根據該式,就可以借觀測值來估計出節(jié)點U的條件分配。當模型很復雜時,可能需要利用數值分析或其他最優(yōu)化技巧來求出參數。圖6-16-服務器與客戶端傳送貝葉斯網絡的結構圖

2.結構已知,觀測值不完整(有遺漏數據)

EM算法的步驟如下:

(1)首先給定待估參數一個初始值,然后利用此初始值和其他的觀測值,求出其他未觀測到節(jié)點的條件期望值,接著將所估計出的值視為觀測值,并將完整的觀測值帶入此模型的最大似然估計式中,如下所示(以圖6-16為例):

式中:EN(x)代表在目前的估計參數下,事件x的條件概率期望值,即

(2)最大化此最大似然估計式,求出此參數最有可能的值,并重復步驟(1)與(2),直到參數收斂為止,即可得到最佳的參數估計值。

6.4.3貝葉斯信念網絡的特點

貝葉斯信念網絡模型的一般特點如下:

(1)貝葉斯信念網絡提供了一種用圖形模型來捕獲特定領域的先驗知識的方法。該網絡還可以用來對變量間的因果依賴關系進行編碼。

(2)構造網絡可能既費時又費力,然而一旦網絡結構確定下來,添加新變量則會十分容易。

(3)貝葉斯網絡很適合處理不完整的數據。對于有屬性遺漏的實例,可以通過對該屬性的所有可能取值的概率求和或求積分來加以處理。

(4)因為數據和先驗知識以概率的方式結合起來了,所以該方法對模型的過擬合問題是非常魯棒的。

6.5回歸分析

回歸是一種預測建模技術,其中被估計的目標變量是連續(xù)的?；貧w應用的例子包括:使用其他經濟學指標預測股市指數,基于高空氣流特征預測一個地區(qū)的降水量,根據廣告開銷預測公司的總銷售,按照有機物質中的碳14殘留估計化石的年齡。

6.5.1預備知識

令D是包含N個觀測的數據集,D={(xi,yi)|i=1,2,…,N}。xi對應于第i個觀測的屬性集,xi=(xi1,xi2,…,xid)是向量,又稱說明變量(ExplanatoryVariable),而yi對應于目標變量(TargetVariable)或因變量。回歸任務的說明屬性可以是離散的或連續(xù)的。

定義6.20(回歸,Regression)一個任務,它學習一個把每個屬性集x映射到一個連續(xù)值輸出y的目標函數f。

回歸的目標是找到一個以最小誤差擬合輸入數據的目標函數。回歸任務的誤差函數(ErrorFunction)可以用絕對誤差或平方誤差和表示:

6.5.2線性回歸

考慮表6-2和圖6-17所示的生理學數據。該數據對應于熱通量和一個人睡眠時皮膚溫度的測量。假設我們希望根據熱傳感器收集的熱通量測量值預測一個人的皮膚溫度,二維散點圖表明這兩個變量之間存在很強的線性關系,即“線性回歸”(Linear