第7章-分類與預(yù)測-數(shù)據(jù)挖掘：概念與技術(shù)-教學(xué)課件1

1、第7章 分類與預(yù)測1第7章 分類與預(yù)測1分類的任務(wù)是通過分析由已知類別數(shù)據(jù)對象組成的訓(xùn)練數(shù)據(jù)集，建立描述并區(qū)分?jǐn)?shù)據(jù)對象類別的分類函數(shù)或分類模型（也常常稱作分類器）。分類的目的是利用分類模型預(yù)測未知類別數(shù)據(jù)對象的所屬類別。2分類的任務(wù)是通過分析由已知類別數(shù)據(jù)對象組成的訓(xùn)練數(shù)據(jù)集，建立分類和聚類是兩個(gè)容易混淆的概念，事實(shí)上它們具有顯著區(qū)別。在分類中，為了建立分類模型而分析的數(shù)據(jù)對象的類別是已知的，然而，在聚類時(shí)處理的所有數(shù)據(jù)對象的類別都是未知的。因此，分類是有指導(dǎo)的，而聚類是無指導(dǎo)的。 3分類和聚類是兩個(gè)容易混淆的概念，事實(shí)上它們具有顯著區(qū)別。在分第7章-分類與預(yù)測-數(shù)據(jù)挖掘：概念與技術(shù)-教學(xué)課件

2、1第7章-分類與預(yù)測-數(shù)據(jù)挖掘：概念與技術(shù)-教學(xué)課件11. 學(xué)習(xí)階段（1）建立分類模型：通過分類算法分析訓(xùn)練數(shù)據(jù)集建立分類模型。訓(xùn)練數(shù)據(jù)集S中的元組或記錄稱為訓(xùn)練樣本，每個(gè)訓(xùn)練樣本由m+1個(gè)屬性描述，其中有且僅有一個(gè)屬性稱為類別屬性，表示訓(xùn)練樣本所屬的類別。屬性集合可用矢量X=（A1, , Am, C）表示，其中Ai（1im）對應(yīng)描述屬性，可以具有不同的值域，當(dāng)一個(gè)屬性的值域?yàn)檫B續(xù)域時(shí)，該屬性稱為連續(xù)屬性（Numerical Attribute），否則稱為離散屬性（Discrete Attribute）；C表示類別屬性，C=（c1, c2, , ck），即訓(xùn)練數(shù)據(jù)集有k個(gè)不同的類別。61. 學(xué)

3、習(xí)階段6分類算法有決策樹分類算法、神經(jīng)網(wǎng)絡(luò)分類算法、貝葉斯分類算法、k-最近鄰分類算法、遺傳分類算法、粗糙集分類算法、模糊集分類算法等。分類算法可以根據(jù)下列標(biāo)準(zhǔn)進(jìn)行比較和評估。1）準(zhǔn)確率。涉及分類模型正確地預(yù)測新樣本所屬類別的能力。2）速度。涉及建立和使用分類模型的計(jì)算開銷。3）強(qiáng)壯性。涉及給定噪聲數(shù)據(jù)或具有空缺值的數(shù)據(jù)，分類模型正確地預(yù)測的能力。4）可伸縮性。涉及給定大量數(shù)據(jù)，有效地建立分類模型的能力。5）可解釋性。涉及分類模型提供的理解和洞察的層次。分類模型有分類規(guī)則、判定樹等。7分類算法有決策樹分類算法、神經(jīng)網(wǎng)絡(luò)分類算法、貝葉斯分類算法、（2）評估分類模型的準(zhǔn)確率：利用測試數(shù)據(jù)集評估分類

4、模型的準(zhǔn)確率。測試數(shù)據(jù)集中的元組或記錄稱為測試樣本。分類模型正確分類的測試樣本數(shù)占總測試樣本數(shù)的百分比稱為該分類模型的準(zhǔn)確率。如果分類模型的準(zhǔn)確率可以接受，就可以利用該分類模型對新樣本進(jìn)行分類。否則，需要重新建立分類模型。 8（2）評估分類模型的準(zhǔn)確率：利用測試數(shù)據(jù)集評估分類模型的準(zhǔn)確評估分類模型準(zhǔn)確率的方法有保持（holdout）、k-折交叉確認(rèn)等。保持方法將已知類別的樣本隨機(jī)地劃分為訓(xùn)練數(shù)據(jù)集與測試數(shù)據(jù)集兩個(gè)集合，一般，訓(xùn)練數(shù)據(jù)集占2/3，測試數(shù)據(jù)集占1/3。分類模型的建立在訓(xùn)練數(shù)據(jù)集上進(jìn)行，分類模型準(zhǔn)確率的評估在測試數(shù)據(jù)集上進(jìn)行。k-折交叉確認(rèn)方法將已知類別的樣本隨機(jī)地劃分為大小大致相等

5、的k個(gè)子集S1, , Sk，并進(jìn)行k次訓(xùn)練與測試。第i次，子集Si作為測試數(shù)據(jù)集，分類模型準(zhǔn)確率的評估在其上進(jìn)行，其余子集的并集作為訓(xùn)練數(shù)據(jù)集，分類模型的建立在其上進(jìn)行。進(jìn)行k次訓(xùn)練得到k個(gè)分類模型，當(dāng)利用分類模型對測試樣本或者新樣本進(jìn)行分類時(shí)，可以綜合考慮k個(gè)分類模型的分類結(jié)果，將出現(xiàn)次數(shù)最多的分類結(jié)果作為最終的分類結(jié)果。9評估分類模型準(zhǔn)確率的方法有保持（holdout）、k-折交叉2. 分類階段分類階段就是利用分類模型對未知類別的新樣本進(jìn)行分類。 數(shù)值預(yù)測過程：與數(shù)據(jù)分類過程相似。首先通過分析由預(yù)測屬性取值已知的數(shù)據(jù)對象組成的訓(xùn)練數(shù)據(jù)集，建立描述數(shù)據(jù)對象特征與預(yù)測屬性之間的相關(guān)關(guān)系的預(yù)測模

6、型，然后利用預(yù)測模型對預(yù)測屬性取值未知的數(shù)據(jù)對象進(jìn)行預(yù)測。數(shù)值預(yù)測技術(shù)主要采用回歸統(tǒng)計(jì)技術(shù)，例如，一元線性回歸、多元線性回歸、非線性回歸等。102. 分類階段107.2 決策樹分類決策樹：一棵決策樹由一個(gè)根節(jié)點(diǎn)，一組內(nèi)部節(jié)點(diǎn)和一組葉節(jié)點(diǎn)組成。每個(gè)內(nèi)部節(jié)點(diǎn)（包括根節(jié)點(diǎn)）表示在一個(gè)屬性上的測試，每個(gè)分枝表示一個(gè)測試輸出，每個(gè)葉節(jié)點(diǎn)表示一個(gè)類，有時(shí)不同的葉節(jié)點(diǎn)可以表示相同的類。 7.2.1 決策樹117.2 決策樹分類決策樹：一棵決策樹由一個(gè)根節(jié)點(diǎn)，一組內(nèi)一棵決策樹年齡？是3031.4041否是否是否是優(yōu)中學(xué)生？信譽(yù)？12一棵決策樹年齡？是3031.4041否是否是否是優(yōu)中學(xué)建立一棵決策樹，需要解決

7、的問題主要有：1）如何選擇測試屬性？測試屬性的選擇順序影響決策樹的結(jié)構(gòu)甚至決策樹的準(zhǔn)確率，一般使用信息增益度量來選擇測試屬性。2）如何停止劃分樣本？從根節(jié)點(diǎn)測試屬性開始，每個(gè)內(nèi)部節(jié)點(diǎn)測試屬性都把樣本空間劃分為若干個(gè)（子）區(qū)域，一般當(dāng)某個(gè)（子）區(qū)域的樣本同類時(shí)，就停止劃分樣本，有時(shí)也通過閾值提前停止劃分樣本。13建立一棵決策樹，需要解決的問題主要有：131. 算法思想及描述首先，在整個(gè)訓(xùn)練數(shù)據(jù)集S、所有描述屬性A1, A2, , Am上遞歸地建立決策樹。即將S作為根節(jié)點(diǎn)；如果S中的樣本屬于同一類別，則將S作為葉節(jié)點(diǎn)并用其中的類別標(biāo)識，決策樹建立完成（遞歸出口）；否則在S上計(jì)算當(dāng)給定Ak（1km）

8、時(shí)類別屬性C的信息增益G(C, Ak)，選擇信息增益最大的Ai作為根節(jié)點(diǎn)的測試屬性；如果Ai的取值個(gè)數(shù)為v（取值記為a1, a2, , av），則Ai將S劃分為v個(gè)子集S1, S2, , Sv（Sj（1jv）為S中Ai=aj的樣本集合），同時(shí)根節(jié)點(diǎn)產(chǎn)生v個(gè)分枝與之對應(yīng)。其次，分別在訓(xùn)練數(shù)據(jù)子集S1, S2, , Sv、剩余描述屬性A1, , Ai-1, Ai+1, , Am上采用相同方法遞歸地建立決策樹子樹（遞歸）。 7.2.2 建立決策樹141. 算法思想及描述7.2.2 建立決策樹14可能出現(xiàn)如下情況，需要停止建立決策（子）樹的遞歸過程。1）某節(jié)點(diǎn)對應(yīng)的訓(xùn)練數(shù)據(jù)（子）集為空。此時(shí)，該節(jié)點(diǎn)作

9、為葉節(jié)點(diǎn)并用父節(jié)點(diǎn)中占多數(shù)的樣本類別標(biāo)識。2）某節(jié)點(diǎn)沒有對應(yīng)的（剩余）描述屬性。此時(shí)，該節(jié)點(diǎn)作為葉節(jié)點(diǎn)并用該節(jié)點(diǎn)中占多數(shù)的樣本類別標(biāo)識。 15可能出現(xiàn)如下情況，需要停止建立決策（子）樹的遞歸過程。15算法：決策樹分類算法Generate_decision_tree（S, A）輸入：訓(xùn)練數(shù)據(jù)集S，描述屬性集合A輸出：決策樹步驟：（1）創(chuàng)建對應(yīng)S的節(jié)點(diǎn)Node;（2）if S中的樣本屬于同一類別c then以c標(biāo)識Node并將Node作為葉節(jié)點(diǎn)返回;（3）if A為空 then以S中占多數(shù)的樣本類別c標(biāo)識Node并將Node作為葉節(jié)點(diǎn)返回;決策樹ID3算法16算法：決策樹分類算法Generate_

10、decision_tr（4）從A中選擇對S而言信息增益最大的描述屬性Ai作為Node的測試屬性;（5）for Ai的每個(gè)可能取值aj（1jv ） /設(shè)Ai的可能取值為a1, a2, , av（5.1）產(chǎn)生S的一個(gè)子集Sj /Sj（1jv）為S中Ai=aj的樣本集合;（5.2）if Sj為空 then創(chuàng)建對應(yīng)Sj的節(jié)點(diǎn)Nj，以S中占多數(shù)的樣本類別c標(biāo)識Nj，并將Nj作為葉節(jié)點(diǎn)形成Node的一個(gè)分枝（5.3）else 由Generate_decision_tree（Sj, A-Ai）創(chuàng)建子樹形成Node的一個(gè)分枝;17（4）從A中選擇對S而言信息增益最大的描述屬性Ai作為Nod2. 信息增益 在決

11、策樹分類算法中使用信息增益度量來選擇測試屬性。從信息論角度看，通過描述屬性可以減少類別屬性的不確定性。假設(shè)有蕃茄、茄子、黃瓜三種蔬菜，現(xiàn)在對某蔬菜分類。在不給任何描述時(shí)，該蔬菜可能是蕃茄、茄子、黃瓜三種之一，不確定性大。在給出該蔬菜是“長的”形狀描述時(shí)，該蔬菜可能是茄子、黃瓜兩種之一，不確定性減小。在給出該蔬菜是“紫的”顏色描述時(shí)，該蔬菜只可能是茄子了，不確定性為零。182. 信息增益18離散型隨機(jī)變量X的無條件熵定義為 式中，p(xi)為X= xi的概率；u為X的可能取值個(gè)數(shù)。根據(jù)H(X)的極值性，當(dāng) 時(shí)，即當(dāng)不確定性最大時(shí)，H(X)最大。根據(jù)H(X)的確定性，當(dāng) 時(shí)，即當(dāng)不確定性為零時(shí)，H

12、(X)=0。所以，H(X)反映X的不確定性。 19離散型隨機(jī)變量X的無條件熵定義為19給定離散型隨機(jī)變量Y，離散型隨機(jī)變量X的條件熵定義為 式中，p(xiyj)為X=xi, Y=yj的聯(lián)合概率；p(xi/yj)為已知Y=yj時(shí)，X= xi的條件概率；u、v分別為X、Y的可能取值個(gè)數(shù)?？梢宰C明，H(X/Y)H(X)。所以，通過Y可以減少X的不確定性。20給定離散型隨機(jī)變量Y，離散型隨機(jī)變量X的條件熵定義為20假設(shè)訓(xùn)練數(shù)據(jù)集是關(guān)系數(shù)據(jù)表r1, r2, , rn，其中描述屬性為A1, A2, , Am、類別屬性為C，類別屬性C的無條件熵定義為 式中，u為C的可能取值個(gè)數(shù)，即類別個(gè)數(shù)，類別記為c1,

13、c2, , cu；si為屬于類別ci的記錄集合，|si|即為屬于類別ci的記錄總數(shù)。21假設(shè)訓(xùn)練數(shù)據(jù)集是關(guān)系數(shù)據(jù)表r1, r2, , rn，其中描給定描述屬性Ak（1km），類別屬性C的條件熵定義為 式中，v為Ak的可能取值個(gè)數(shù)，取值記為a1, a2, , av；sj為Ak=aj的記錄集合，|sj|即為Ak=aj的記錄數(shù)目；sij為Ak=aj且屬于類別ci的記錄集合，|sij|即為Ak=aj且屬于類別ci的記錄數(shù)目。 22給定描述屬性Ak（1km），類別屬性C的條件熵定義為 2不同描述屬性減少類別屬性不確定性的程度不同，即不同描述屬性對減少類別屬性不確定性的貢獻(xiàn)不同。例如，假設(shè)有蕃茄、茄子、黃

14、瓜三種蔬菜，現(xiàn)在對某蔬菜分類，形狀描述與顏色描述的貢獻(xiàn)是不同的。在給出該蔬菜的顏色描述時(shí)，如果顏色是紅的，則該蔬菜是蕃茄；如果顏色是紫的，則該蔬菜是茄子；如果顏色是綠的，則該蔬菜是黃瓜，不確定性減少為0。而在給出該蔬菜的形狀描述時(shí)，如果形狀是圓的，則該蔬菜是蕃茄；如果形狀是長的，則該蔬菜可能是茄子，也可能是黃瓜，不確定性還是存在。23不同描述屬性減少類別屬性不確定性的程度不同，即不同描述屬性對采用類別屬性的無條件熵與條件熵的差（信息增益）來度量描述屬性減少類別屬性不確定性的程度。 給定描述屬性Ak（1km），類別屬性C的信息增益定義為：G(C, Ak)=E(C)-E(C, Ak)可以看出，G(

15、C, Ak)反映Ak減少C不確定性的程度，G(C, Ak)越大，Ak對減少C不確定性的貢獻(xiàn)越大。 24采用類別屬性的無條件熵與條件熵的差（信息增益）來度量描述屬性例如，假設(shè)蔬菜數(shù)據(jù)表如表7.1所示，“顏色”、“形狀”是描述屬性，“蔬菜”是類別屬性，分別求給定“顏色”、“形狀”屬性時(shí)，“蔬菜”屬性的信息增益。表7.1 蔬菜數(shù)據(jù)表 顏色形狀蔬菜紅圓蕃茄紫長茄子綠長黃瓜結(jié)論屬性條件屬性25例如，假設(shè)蔬菜數(shù)據(jù)表如表7.1所示，“顏色”、“形狀”是描述解：顏色形狀蔬菜紅圓蕃茄紫長茄子綠長黃瓜共有3個(gè)記錄，蕃茄、茄子和黃瓜各計(jì)一個(gè)記錄。26解：顏色形狀蔬菜紅圓蕃茄紫長茄子綠長黃瓜共有3個(gè)記錄，蕃茄、顏色形

16、狀蔬菜紅圓蕃茄紫長茄子綠長黃瓜按顏色分類，再按蔬菜分類，每種蔬菜只有一種顏色。27顏色形狀蔬菜紅圓蕃茄紫長茄子綠長黃瓜按顏色分類，再按蔬菜分類顏色形狀蔬菜紅圓蕃茄紫長茄子綠長黃瓜按形狀分類，再按蔬菜分類，圓形狀只有一種蔬菜，而長形狀有兩種蔬菜。28顏色形狀蔬菜紅圓蕃茄紫長茄子綠長黃瓜按形狀分類，再按蔬菜則有：G(蔬菜，顏色)1.5850-0=1.5850G(蔬菜，形狀)1.5850-0.6667=0.9183說明顏色對蔬菜分類的不確定性小，而形狀對蔬菜分類的不確定性大。信息熵反映不確定的程度，為1時(shí)表示最大不確定性，為0時(shí)表示最小不確定性。信息增益G(C, A)=E(C)-E(C, A)反映屬

17、性A減少C不確定性的程度，G(C, A)越大，屬性A對減少C不確定性的貢獻(xiàn)越大。 29則有：信息熵反映不確定的程度，為1時(shí)表示最大不確定性，為例如，建立上例的決策樹。 因?yàn)镚(蔬菜，顏色)G(蔬菜，形狀)，所以選擇“顏色”屬性作為根節(jié)點(diǎn)的測試屬性，得到的決策樹如下圖所示。顏色？蕃茄茄子黃瓜紅紫綠30例如，建立上例的決策樹。顏色？蕃茄茄子黃瓜紅紫綠30例如，假設(shè)顧客數(shù)據(jù)表如下表所示，“購買計(jì)算機(jī)”屬性是類別屬性，其余屬性是描述屬性，建立決策樹。年齡收入學(xué)生信譽(yù)購買計(jì)算機(jī)30高否中是30高否優(yōu)否31.40高否中是41中否中是41低是中是41低是優(yōu)否31.40低是優(yōu)是30中否中否30低是中是41中是

18、中是30中是優(yōu)是31.40中否優(yōu)是31.40高是中是41中否優(yōu)否31例如，假設(shè)顧客數(shù)據(jù)表如下表所示，“購買計(jì)算機(jī)”屬性是類別屬性解： 考慮根節(jié)點(diǎn)：G(購買計(jì)算機(jī)，年齡)=0.246G(購買計(jì)算機(jī)，收入)=0.029G(購買計(jì)算機(jī)，學(xué)生)=0.151G(購買計(jì)算機(jī)，信譽(yù))=0.048所以根節(jié)點(diǎn)的測試屬性為“年齡”32解：32 考慮分枝“年齡=30”節(jié)點(diǎn)G(購買計(jì)算機(jī)，收入)=0.571G(購買計(jì)算機(jī)，學(xué)生)=0.971G(購買計(jì)算機(jī)，信譽(yù))=0.02所以分枝“年齡=30”節(jié)點(diǎn)的測試屬性為“學(xué)生”。年齡收入學(xué)生信譽(yù)購買計(jì)算機(jī)30高否中是30高否優(yōu)否30中否中否30低是中是30中是優(yōu)是33 考慮分枝

19、“年齡=30”節(jié)點(diǎn)年齡收入學(xué)生信譽(yù)購買計(jì)算 考慮分枝“年齡=3140”節(jié)點(diǎn)因?yàn)樗杏涗泴儆谕活悇e是，所以分枝“年齡=3140”節(jié)點(diǎn)為葉節(jié)點(diǎn)。年齡收入學(xué)生信譽(yù)購買計(jì)算機(jī)31.40高否中是31.40低是優(yōu)是31.40中否優(yōu)是31.40高是中是34 考慮分枝“年齡=3140”節(jié)點(diǎn)年齡收入學(xué)生信譽(yù)購買 考慮分枝“年齡=41”節(jié)點(diǎn)G(購買計(jì)算機(jī)，收入)=0.02G(購買計(jì)算機(jī)，學(xué)生)=0.02G(購買計(jì)算機(jī)，信譽(yù))=0.971所以分枝“年齡=41”節(jié)點(diǎn)的測試屬性為“信譽(yù)”年齡收入學(xué)生信譽(yù)購買計(jì)算機(jī)41中否中是41低是中是41低是優(yōu)否41中是中是41中否優(yōu)否35 考慮分枝“年齡=41”節(jié)點(diǎn)年齡收入學(xué)生信

20、譽(yù)購買計(jì)算 考慮分枝“學(xué)生=否”節(jié)點(diǎn)因?yàn)樗杏涗泴儆谕活悇e否，所以分枝“學(xué)生=否”節(jié)點(diǎn)為葉節(jié)點(diǎn)。年齡收入學(xué)生信譽(yù)購買計(jì)算機(jī)41中否中是41中否優(yōu)否36 考慮分枝“學(xué)生=否”節(jié)點(diǎn)年齡收入學(xué)生信譽(yù)購買計(jì)算機(jī) 考慮分枝“學(xué)生=是”節(jié)點(diǎn)因?yàn)樗杏涗泴儆谕活悇e是所以分枝“學(xué)生=是”節(jié)點(diǎn)為葉節(jié)點(diǎn)。 考慮分枝“信譽(yù)=優(yōu)”節(jié)點(diǎn)因?yàn)樗杏涗泴儆谕活悇e否所以分枝“信譽(yù)=否”節(jié)點(diǎn)為葉節(jié)點(diǎn)。 考慮分枝“信譽(yù)=中”節(jié)點(diǎn)因?yàn)樗杏涗泴儆谕活悇e是所以分枝“信譽(yù)=是”節(jié)點(diǎn)為葉節(jié)點(diǎn)。建立的決策樹如下圖所示。37 考慮分枝“學(xué)生=是”節(jié)點(diǎn)37一棵決策樹 購買計(jì)算機(jī)年齡？是3031.4041否是否是否是優(yōu)中學(xué)生？信譽(yù)？38

21、一棵決策樹 購買計(jì)算機(jī)年齡？是3031.4041否是否7.2.3 提取分類規(guī)則建立了決策樹之后，可以對從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每條路徑創(chuàng)建一條IF-THEN分類規(guī)則，即沿著路徑，每個(gè)內(nèi)部屬性-值對（內(nèi)部節(jié)點(diǎn)-分枝對）形成規(guī)則前件（IF部分）的一個(gè)合取項(xiàng)，葉節(jié)點(diǎn)形成規(guī)則后件（THEN部分）。 例如， 沿著從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每條路徑，上圖的決策樹可以轉(zhuǎn)換成以下IF-THEN分類規(guī)則：IF 年齡=30 AND 學(xué)生=否 THEN 購買計(jì)算機(jī)=否IF 年齡=30 AND 學(xué)生=是 THEN 購買計(jì)算機(jī)=是IF 年齡=3140 THEN 購買計(jì)算機(jī)=是IF 年齡=41 AND 信譽(yù)=優(yōu) THEN 購買計(jì)算機(jī)=

22、否IF 年齡=41 AND 信譽(yù)=中 THEN 購買計(jì)算機(jī)=是397.2.3 提取分類規(guī)則建立了決策樹之后，可以對從根節(jié)7.2.4 對新樣本分類 假如現(xiàn)在來了一位新顧客，他是一名教師，年齡為45歲，收入較低但信譽(yù)很好。 商場需要判斷該顧客是否會購買計(jì)算機(jī)？即將該顧客劃分到“購買計(jì)算機(jī)”類呢？還是將他劃分到“不購買計(jì)算機(jī)”類？很顯然，利用上面的分類規(guī)則，可以判定該顧客不會購買計(jì)算機(jī)。407.2.4 對新樣本分類 假如現(xiàn)在來了一位新7.2.5 C4.5算法Quinlan建議將E(C,Ak)改為：GRatio=E(C,Ak)/SplitE(C,Ak)，其中：SplitE(C,Ak)=I(|T1|/|

23、T|, |T2|/|T|, |Tn|/|T|)，而T1,T2,Tn表示以C的取值分割T所產(chǎn)生的T的子集。I的定義若給定的概率分布P=(p1,p2,pn)，則由該分布傳遞的信息量稱為P的熵，即： I(P)=-(p1*log2p1+p2*log2p2+pn*log2pn) 原描述屬性Ak（1km），類別屬性C的條件熵定義為：417.2.5 C4.5算法Quinlan建議將E(C,Ak)前饋神經(jīng)網(wǎng)絡(luò)是分層網(wǎng)絡(luò)模型，具有一個(gè)輸入層和一個(gè)輸出層，輸入層和輸出層之間有一個(gè)或多個(gè)隱藏層。每個(gè)層具有若干單元，前一層單元與后一層單元之間通過有向加權(quán)邊相連。 7.3.1 前饋神經(jīng)網(wǎng)絡(luò)7.3 前饋神經(jīng)網(wǎng)絡(luò)分類42前

24、饋神經(jīng)網(wǎng)絡(luò)是分層網(wǎng)絡(luò)模型，具有一個(gè)輸入層和一個(gè)輸出層，輸入輸入層單元的數(shù)目與訓(xùn)練樣本的描述屬性數(shù)目對應(yīng)，通常一個(gè)連續(xù)屬性對應(yīng)一個(gè)輸入層單元，一個(gè)p值離散屬性對應(yīng)p個(gè)輸入層單元；輸出層單元的數(shù)目與訓(xùn)練樣本的類別數(shù)目對應(yīng)，當(dāng)類別數(shù)目為2時(shí)，輸出層可以只有一個(gè)單元；目前，隱藏層的層數(shù)及隱藏層的單元數(shù)尚無理論指導(dǎo)，一般通過實(shí)驗(yàn)選取。在輸入層，各單元的輸出可以等于輸入，也可以按一定比例調(diào)節(jié)，使其值落在1和+1之間。 43輸入層單元的數(shù)目與訓(xùn)練樣本的描述屬性數(shù)目對應(yīng)，通常一個(gè)連續(xù)屬在隱藏層、輸出層，每個(gè)單元的輸入都是前一層各單元輸出的加權(quán)和，輸出是輸入的某種函數(shù)，稱為激活函數(shù)。隱藏層、輸出層任意單元j的輸

25、入為 式中，wij是單元j與前一層單元i之間的連接權(quán)值；Oi是單元i的輸出； 為改變單元j活性的偏置，一般在區(qū)間1，1上取值。44在隱藏層、輸出層，每個(gè)單元的輸入都是前一層各單元輸出的加權(quán)和單元j的輸出為Oj=f(netj) 如果f采用S型激活函數(shù)，即 則 45單元j的輸出為45計(jì)算隱藏層、輸出層任意單元j的輸出的過程46計(jì)算隱藏層、輸出層任意單元j的輸出的過程46例如，定義蔬菜分類的前饋神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)。表7.1 蔬菜數(shù)據(jù)表 顏色形狀蔬菜紅圓蕃茄紫長茄子綠長黃瓜47例如，定義蔬菜分類的前饋神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)。表7.1 蔬菜數(shù)兩層前饋神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu) 因?yàn)殡x散屬性“顏色”有三個(gè)取值、“形狀”有兩個(gè)取值，分別

26、采用3位、2位編碼，所以輸入層有5個(gè)單元。因?yàn)轭悇e屬性“蔬菜”有三個(gè)取值，采用3位編碼，所以輸出層有3個(gè)單元。如果只用一個(gè)具有4個(gè)單元的隱藏層并且采用全連接，則兩層前饋神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)如下圖所示。48兩層前饋神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu) 因?yàn)殡x散屬性“顏色”有三個(gè)取值、“7.3.2 學(xué)習(xí)前饋神經(jīng)網(wǎng)絡(luò)確定了網(wǎng)絡(luò)結(jié)構(gòu)（網(wǎng)絡(luò)層數(shù)，各層單元數(shù)）之后，應(yīng)該確定各單元的偏置及單元之間的連接權(quán)值。學(xué)習(xí)過程就是調(diào)整這組權(quán)值和偏置，使每個(gè)訓(xùn)練樣本在輸出層單元上獲得期望輸出。學(xué)習(xí)目的就是找出一組權(quán)值和偏置，這組權(quán)值和偏置能使所有訓(xùn)練樣本在輸出層單元上獲得期望輸出。 497.3.2 學(xué)習(xí)前饋神經(jīng)網(wǎng)絡(luò)確定了網(wǎng)絡(luò)結(jié)構(gòu)（網(wǎng)絡(luò)層數(shù)，各層誤差后

27、向傳播的基本思想是：首先賦予每條有向加權(quán)邊初始權(quán)值、每個(gè)隱藏層與輸出層單元初始偏置；然后迭代地處理每個(gè)訓(xùn)練樣本；輸入它的描述屬性值，計(jì)算輸出層單元的實(shí)際輸出；比較實(shí)際輸出與期望輸出（類別屬性值），將它們之間的誤差從輸出層經(jīng)每個(gè)隱藏層到輸入層“后向傳播”；根據(jù)誤差修改每條有向加權(quán)邊的權(quán)值及每個(gè)隱藏層與輸出層單元的偏置，使實(shí)際輸出與期望輸出之間的誤差最小。 50誤差后向傳播的基本思想是：50對于某個(gè)訓(xùn)練樣本，實(shí)際輸出與期望輸出的誤差Error定義為 式中，c為輸出層的單元數(shù)目；Tk為輸出層單元k的期望輸出；Ok為輸出層單元k的實(shí)際輸出。希望Error越小越好！51對于某個(gè)訓(xùn)練樣本，實(shí)際輸出與期望輸

28、出的誤差Error定義為希首先考慮輸出層單元k與前一層單元j之間的權(quán)值wjk的修改量wjk、單元k的偏置 的修改量 。 式中，l為避免陷入局部最優(yōu)解的學(xué)習(xí)率，一般在區(qū)間0, 1上取值。這里采用的是梯度下降法。52首先考慮輸出層單元k與前一層單元j之間的權(quán)值wjk的修改量求解上式可以得到權(quán)值、偏置的修改量為 式中，Oj為單元j的輸出；Errk是誤差Error對單元k的輸入netk的負(fù)偏導(dǎo)數(shù)，即 53求解上式可以得到權(quán)值、偏置的修改量為53類似地，隱藏層單元j與前一層單元i之間的權(quán)值wij的修改量wij、單元j的偏置j的修改量j為 式中，l為學(xué)習(xí)率；Oi為單元i的輸出；Oj為單元j的輸出；Errk

29、為與單元j相連的后一層單元k的誤差；wjk為單元j與單元k相連的有向加權(quán)邊的權(quán)值。54類似地，隱藏層單元j與前一層單元i之間的權(quán)值wij的修改量權(quán)值、偏置的修改公式為 權(quán)值、偏置的更新有兩種策略：1）處理一個(gè)訓(xùn)練樣本更新一次，稱為實(shí)例更新，一般采用這種策略。2）累積權(quán)值、偏置，當(dāng)處理所有訓(xùn)練樣本后再一次更新，稱為周期更新。 55權(quán)值、偏置的修改公式為 55一般，在訓(xùn)練前饋神經(jīng)網(wǎng)絡(luò)時(shí)，誤差后向傳播算法經(jīng)過若干周期以后，可以使誤差Error小于設(shè)定閾值，此時(shí)認(rèn)為網(wǎng)絡(luò)收斂，結(jié)束迭代過程。此外，也可以定義如下結(jié)束條件：1）前一周期所有的權(quán)值變化都很小，小于某個(gè)設(shè)定閾值；2）前一周期預(yù)測的準(zhǔn)確率很大，大

30、于某個(gè)設(shè)定閾值；3）周期數(shù)大于某個(gè)設(shè)定閾值。 56一般，在訓(xùn)練前饋神經(jīng)網(wǎng)絡(luò)時(shí)，誤差后向傳播算法經(jīng)過若干周期以后算法：誤差后向傳播算法輸入：訓(xùn)練數(shù)據(jù)集S，前饋神經(jīng)網(wǎng)絡(luò)NT，學(xué)習(xí)率l輸出：經(jīng)過訓(xùn)練的前饋神經(jīng)網(wǎng)絡(luò)NT步驟：（1）在區(qū)間-1, 1上隨機(jī)初始化NT中每條有向加權(quán)邊的權(quán)值、每個(gè)隱藏層與輸出層單元的偏置（2）while 結(jié)束條件不滿足（2.1）for S中每個(gè)訓(xùn)練樣本s57算法：誤差后向傳播算法57（2.1.1）for 隱藏層與輸出層中每個(gè)單元j /從第一個(gè)隱藏層開始向前傳播輸入（2.1.2）for 輸出層中每個(gè)單元k Errk=Ok(1- Ok)( Tk - Ok)58（2.1.1）for

31、 隱藏層與輸出層中每個(gè)單元j /（2.1.3）for 隱藏層中每個(gè)單元j /從最后一個(gè)隱藏層開始向后傳播誤差 （2.1.4）for NT中每條有向加權(quán)邊的權(quán)值wij wij= wij+lErrjOi（2.1.5）for 隱藏層與輸出層中每個(gè)單元的偏置j j=j+lErrj59（2.1.3）for 隱藏層中每個(gè)單元j 誤差后向傳播算法要求輸入層單元的輸入是連續(xù)值，并對連續(xù)值進(jìn)行規(guī)格化以便提高訓(xùn)練的效率與質(zhì)量。如果訓(xùn)練樣本的描述屬性是離散屬性，則需要對其編碼，編碼方法有兩種：1）p值離散屬性：可以采用p位編碼。假設(shè)p值離散屬性的可能取值為a1, a2,ap，當(dāng)某訓(xùn)練樣本的該屬性值為a1時(shí)，則編碼為

32、1,0,0；當(dāng)某訓(xùn)練樣本的該屬性值為a2時(shí)，則編碼為0,1,0；依次類推。2）二值離散屬性：除采用2位編碼外還可以采用1位編碼。當(dāng)編碼為1時(shí)表示一個(gè)屬性值；當(dāng)編碼為0時(shí)表示另一個(gè)屬性值。60誤差后向傳播算法要求輸入層單元的輸入是連續(xù)值，并對連續(xù)值進(jìn)行例如，假設(shè)訓(xùn)練樣本s的描述屬性值與類別屬性值分別為1, 0, 1與1，前饋神經(jīng)網(wǎng)絡(luò)NT如下圖所示，NT中每條有向加權(quán)邊的權(quán)值、每個(gè)隱藏層與輸出層單元的偏置如表7.3所示，學(xué)習(xí)率為0.9。寫出輸入s訓(xùn)練NT的過程。 一個(gè)前饋神經(jīng)網(wǎng)絡(luò)NT61例如，假設(shè)訓(xùn)練樣本s的描述屬性值與類別屬性值分別為1, 0NT中邊的權(quán)值、單元的偏置 x1 x2 x3 w14

33、w15 w24 w25 w34 w35 w46 w56 4 5 6 1010.2 0.3 0.4 0.1 0.5 0.2 0.3 0.2 0.4 0.2 0.1 wij和j是隨機(jī)產(chǎn)生的，l0.962NT中邊的權(quán)值、單元的偏置 x1 x2 x3 w14 w15隱藏層與輸出層中單元的輸入、輸出 單元j 輸入netj 輸出Oj 40.2*1+0.4*0+(0.5)*1+(0.4)=0.7 1/(1+e(0.7)=0.332 5(0.3)*1+0.1*0+(0.2)*1+0.2=0.1 1/(1+e0.1)=0.525 6(0.3) *0.332+(0.2)*0.525+0.1=0.105 1/(1+

34、e(0.105)=0.474 63隱藏層與輸出層中單元的輸入、輸出 單元j 輸入netj 輸出隱藏層與輸出層中單元的Err 單元j Errj 60.474*(10.474)*(10.474)=0.131150.525*(10.525)*(0.1311*(0.2)=0.006540.332*(10.332)*(0.1311*(0.3)=0.0087Errk=Ok(1- Ok)( Tk - Ok)64隱藏層與輸出層中單元的Err 單元j Errj 60.474NT中邊的新權(quán)重、單元的新偏置 w46 0.3+0.9*0.1311*0.332=0.261 w56 0.2+0.9*0.1311*0.52

35、5=0.138 w14 0.2+0.9*(0.0087)*1=0.192w15 0.3+0.9*(0.0065)*1=0.306w24 0.4+0.9*(0.0087)*0=0.4w25 0.1+0.9*(0.0065)*0=0.1w34 0.5+0.9*(0.0087)*1=0.508 w35 0.2+0.9*(0.0065)*1=0.1946 0.1+0.9*0.1311=0.2185 0.2+0.9*(0.0065)=0.194 4 0.4+0.9*(0.0087)=0.408 wij= wij+lErrjOi j=j+lErrj這里只有一個(gè)訓(xùn)練樣本，只示例了學(xué)習(xí)過程中的一次迭代過程。在

36、實(shí)際應(yīng)用中，訓(xùn)練樣本多，迭代次數(shù)多，這樣得到的結(jié)果好。激活函數(shù)的選取很重要：收斂收斂速度65NT中邊的新權(quán)重、單元的新偏置 w46 0.3+0.9*07.3.3 神經(jīng)網(wǎng)絡(luò)分類學(xué)習(xí)結(jié)束后，神經(jīng)網(wǎng)絡(luò)得到一組固定的權(quán)值及偏置。新樣本到來后，將其描述屬性值送入輸入層各單元，從輸入層到輸出層正向傳播，計(jì)算輸出層各單元的值O1, O2, , On，令r=max(O1, O2, , On)，則第r個(gè)輸出層單元所代表的類別就是該樣本所屬的類別。 例如，在上例中，只有一個(gè)輸出層單元，表示只有兩個(gè)類別（A類、B類）。神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)結(jié)束后，表7.6中的各權(quán)值和偏置都固定。將一個(gè)新樣本X=（x1, x2, x3）送入輸

37、入層后可以計(jì)算出O6，若O61，則表示X應(yīng)屬于A類；若O60，則表示X應(yīng)屬于B類；若O60.5，則拒絕分類。 667.3.3 神經(jīng)網(wǎng)絡(luò)分類學(xué)習(xí)結(jié)束后，神經(jīng)網(wǎng)絡(luò)得到一組固定的7.4 貝葉斯分類 1. 貝葉斯公式 式中，p(x)、p(y)為隨機(jī)變量X=x、Y=y的概率；p(x|y)為已知Y=y時(shí)，X=x的條件概率；p(y|x)為已知X=x時(shí)，Y=y的條件概率。7.4.1 貝葉斯分類概述677.4 貝葉斯分類 1. 貝葉斯公式7.4.1 貝葉斯根據(jù)貝葉斯公式，可以得到貝葉斯分類公式： 式中，p(a1, , am)為m個(gè)描述屬性A1=a1, , Am=am的聯(lián)合概率；p(c)為類別屬性C=c的概率，也

38、稱為類別c的先驗(yàn)概率；p(a1, , am|c)為已知C=c時(shí)，A1=a1, , Am=am的條件概率，也稱為類條件概率；p(c|a1, , am)為已知A1=a1, , Am=am時(shí)，C=c的條件概率，也稱為類別c的后驗(yàn)概率。 68根據(jù)貝葉斯公式，可以得到貝葉斯分類公式：68貝葉斯分類的分類階段就是給定新樣本的描述屬性值a1,am，根據(jù)上述公式，計(jì)算各個(gè)類別的后驗(yàn)概率，后驗(yàn)概率最大的類別就是新樣本的類別屬性值，即新樣本的類別為：綜合上述兩式，得到新樣本的類別為：貝葉斯分類的學(xué)習(xí)階段就是根據(jù)訓(xùn)練樣本，計(jì)算各個(gè)類別的先驗(yàn)概率、各個(gè)類條件概率。 69貝葉斯分類的分類階段就是給定新樣本的描述屬性值a

39、1,am例如，訓(xùn)練樣本如下表：年齡收入學(xué)生信譽(yù)購買計(jì)算機(jī)30高否中是30高否優(yōu)否31.40高否中是41中否中是41低是中是41低是優(yōu)否31.40低是優(yōu)是30中否中否30低是中是41中是中是30中是優(yōu)是31.40中否優(yōu)是31.40高是中是41中否優(yōu)否70例如，訓(xùn)練樣本如下表：年齡收入學(xué)生信譽(yù)購買計(jì)算機(jī)30高否中新樣本為（3140,中,否,優(yōu)），應(yīng)用貝葉斯分類對新樣本進(jìn)行分類。因?yàn)閜(是)9/14，p(否)5/14；p(3140,中,否,優(yōu))| 是)1/9；p(3140,中,否,優(yōu))| 否)0；p(3140,中,否,優(yōu))| 是)p(是)1/99/141/14；p(3140,中,否,優(yōu))| 否)p(

40、否)05/140；結(jié)論：新樣本的類別為是。 71新樣本為（3140,中,否,優(yōu)），應(yīng)用2. 貝葉斯網(wǎng)如果隨機(jī)變量（或不相交的隨機(jī)變量集合）X、Y和Z滿足P(X,Y|Z)=P(X|Z)P(Y|Z)，則稱X和Y在已知Z時(shí)條件獨(dú)立，記為XY|Z。式中，P(X|Z)、P(Y|Z)分別為已知Z時(shí)X、Y的條件概率分布，P(X,Y|Z)為已知Z時(shí)X、Y的聯(lián)合條件概率分布。一個(gè)貝葉斯網(wǎng)（Bayesian Network, BN）由一個(gè)有向無環(huán)圖G和一組參數(shù)組成，記為BN(G,)。其中，有向無環(huán)圖G中的節(jié)點(diǎn)表示隨機(jī)變量，有向邊表示隨機(jī)變量之間的直接依賴關(guān)系；參數(shù)為節(jié)點(diǎn)X在已知父節(jié)點(diǎn)(X)時(shí)的條件概率分布P(|(

41、X)，如果節(jié)點(diǎn)X沒有父節(jié)點(diǎn)，即(X)，則P(X|(X)P(X)。 722. 貝葉斯網(wǎng)72在貝葉斯網(wǎng)中，如果已知節(jié)點(diǎn)X的父節(jié)點(diǎn)(X)，則X和它的所有非后代節(jié)點(diǎn)nd(X)-(X)條件獨(dú)立，即Xnd(X)-(X)|(X)，稱為局部馬爾可夫性。 根據(jù)局部馬爾可夫性，貝葉斯網(wǎng)節(jié)點(diǎn)X1, ., Xm的聯(lián)合概率分布可以分解為條件概率分布的乘積，即 73在貝葉斯網(wǎng)中，如果已知節(jié)點(diǎn)X的父節(jié)點(diǎn)(X)，則X和它的所有例如，在如下圖所示的貝葉斯網(wǎng)中，X和Y在已知Z時(shí)條件獨(dú)立，即XY|Z，并且P(X,Y,Z)=P(Z)P(X|Z)P(Y|Z)。貝葉斯網(wǎng)示例ZXY如，P(X=0,Y=0,Z=0)=P(Z=0)P(X=0|

42、Z=0)P(Y=0|Z=0) =0.5*0.7*0.2=0.07。 74例如，在如下圖所示的貝葉斯網(wǎng)中，X和Y在已知Z時(shí)條件獨(dú)立，即貝葉斯網(wǎng)可以用于計(jì)算貝葉斯分類中的類條件概率。然而，通過分析訓(xùn)練數(shù)據(jù)集，構(gòu)造貝葉斯網(wǎng)是一個(gè)NP-complete問題。為了簡化計(jì)算，一般應(yīng)用條件獨(dú)立假設(shè)，限定貝葉斯網(wǎng)結(jié)構(gòu)。不同的條件獨(dú)立假設(shè)形成了不同的貝葉斯分類。 樸素貝葉斯分類樹增強(qiáng)樸素貝葉斯分類 75貝葉斯網(wǎng)可以用于計(jì)算貝葉斯分類中的類條件概率。然而，通過分析7.4.2 樸素貝葉斯分類樸素貝葉斯分類（Nave Bayesian Classifier）將類別屬性C和描述屬性A1, ., Am放在不同的地位，C的

43、取值決定了A1, ., Am的取值，C和A1, ., Am有直接依賴關(guān)系，也就是說，在貝葉斯網(wǎng)中，節(jié)點(diǎn)C和節(jié)點(diǎn)A1, ., Am有有向邊相連，C是A1, ., Am的父節(jié)點(diǎn)。為了簡化計(jì)算，樸素貝葉斯分類假設(shè)A1, ., Am在已知C時(shí)條件獨(dú)立，也就是說，在貝葉斯網(wǎng)中，節(jié)點(diǎn)A1, ., Am之間沒有有向邊相連。因此，樸素貝葉斯分類限定貝葉斯網(wǎng)結(jié)構(gòu)為：(C)，(Ai)C，如下圖所示。767.4.2 樸素貝葉斯分類樸素貝葉斯分類（Nave Ba樸素貝葉斯分類的貝葉斯網(wǎng)結(jié)構(gòu) CA1Am77樸素貝葉斯分類的貝葉斯網(wǎng)結(jié)構(gòu) CA1Am77在樸素貝葉斯分類中，類條件概率可以通過下式估計(jì)綜合公式，得到新樣本a1

44、,am的類別為： 78在樸素貝葉斯分類中，類條件概率可以通過下式估計(jì)78例如，訓(xùn)練樣本如下：年齡收入學(xué)生信譽(yù)購買計(jì)算機(jī)30高否中是30高否優(yōu)否31.40高否中是41中否中是41低是中是41低是優(yōu)否31.40低是優(yōu)是30中否中否30低是中是41中是中是30中是優(yōu)是31.40中否優(yōu)是31.40高是中是41中否優(yōu)否79例如，訓(xùn)練樣本如下：年齡收入學(xué)生信譽(yù)購買計(jì)算機(jī)30高否中是新樣本為（3140,中,否,優(yōu)），應(yīng)用樸素貝葉斯分類對新樣本進(jìn)行分類。貝葉斯網(wǎng)結(jié)構(gòu)購買計(jì)算機(jī)年齡收入學(xué)生信譽(yù)結(jié)論：是或否：p(是)p(3140|是)p(中|是)p(否|是)p(優(yōu)|是)p(否)p(3140|否)p(中|否)p(否

45、|否)p(優(yōu)|否)哪個(gè)值大？所有屬性獨(dú)立80新樣本為（3140,中,否,優(yōu)），應(yīng)用樸素因?yàn)閜(是)9/14，p(3140|是)4/9；p(中|是)4/9；p(否|是)3/9；p(優(yōu)|是)3/9；p(是)p(3140|是)p(中|是)p(否|是)p(優(yōu)|是)9/144/94/93/93/98/567；p(否)5/14；p(3140|否)0；p(中|否)2/5；p(否|否)4/5；p(優(yōu)|否)3/5；p(否)p(3140|否)p(中|否)p(否|否)p(優(yōu)|否)5/1402/54/53/50；所以新樣本的類別是是。新樣本為（3140,中,否,優(yōu)），81因?yàn)閜(是)9/14，p(3140|是)4算法

46、：樸素貝葉斯分類參數(shù)學(xué)習(xí)算法輸入：訓(xùn)練數(shù)據(jù)集S輸出：各個(gè)類別的先驗(yàn)概率p(c)，各個(gè)類條件概率p(a1, , am|c)步驟：（1）for S中每個(gè)訓(xùn)練樣本s(as1, , asm, cs) （1.1）增加類別cs的計(jì)數(shù)cs.count （1.2）for 每個(gè)描述屬性值asi 增加類別cs中描述屬性值asi的計(jì)數(shù)cs.asi.count82算法：樸素貝葉斯分類參數(shù)學(xué)習(xí)算法82（2）for 每個(gè)類別c（2.1）（2.2）for 每個(gè)描述屬性Ai（2.2.1）for 每個(gè)描述屬性值ai （2.3）for 每個(gè)a1, , am83（2）for 每個(gè)類別c83算法：樸素貝葉斯分類算法輸入：各個(gè)類別的先

47、驗(yàn)概率p(c)，各個(gè)類條件概率p(a1, , am|c)，新樣本r( ar1, , arm )輸出：新樣本的類別cr步驟：求所屬的最大類別值84算法：樸素貝葉斯分類算法求所屬的最大類別值84樹增強(qiáng)樸素貝葉斯分類（Tree Augmented Nave Bayesian Classifier, TAN）在樸素貝葉斯分類的基礎(chǔ)上，允許各個(gè)描述屬性之間形成樹型結(jié)構(gòu)，從而削弱了各個(gè)描述屬性在給定類別屬性時(shí)條件獨(dú)立假設(shè)，增強(qiáng)了樸素貝葉斯分類，因此，稱為樹增強(qiáng)樸素貝葉斯分類。也就是說，在貝葉斯網(wǎng)中，節(jié)點(diǎn)C和節(jié)點(diǎn)A1, ., Am有有向邊相連，C是A1, ., Am的父節(jié)點(diǎn)，此外，A1, ., Am之間有有

48、向邊相連并形成樹，根節(jié)點(diǎn)的父節(jié)點(diǎn)只有C，其它節(jié)點(diǎn)的父節(jié)點(diǎn)除了C之外還有一個(gè)節(jié)點(diǎn)。7.4.3 樹增強(qiáng)樸素貝葉斯分類85樹增強(qiáng)樸素貝葉斯分類（Tree Augmented Nav例如，一個(gè)包括5個(gè)描述屬性A1, ., A5和1個(gè)類別屬性C的樹增強(qiáng)樸素貝葉斯分類的貝葉斯網(wǎng)結(jié)構(gòu)如下圖所示。 樹增強(qiáng)樸素貝葉斯分類的貝葉斯網(wǎng)結(jié)構(gòu)CA1A2A4A5A386例如，一個(gè)包括5個(gè)描述屬性A1, ., A5和1個(gè)類別屬在樹增強(qiáng)樸素貝葉斯分類中，如果通過分析訓(xùn)練數(shù)據(jù)集，得到了各個(gè)描述屬性之間的樹型結(jié)構(gòu)，就可以估計(jì)類條件概率，從而可以得到新樣本的類別。例如，在如上圖所示的樹增強(qiáng)樸素貝葉斯分類中，類條件概率可以通過下式估

49、計(jì)：新樣本a1, , a5的類別可以通過下式得到：CA1A2A4A5A387在樹增強(qiáng)樸素貝葉斯分類中，如果通過分析訓(xùn)練數(shù)據(jù)集，得到了各個(gè)樹增強(qiáng)樸素貝葉斯分類樹型結(jié)構(gòu)構(gòu)造方法的基本思想是：首先，計(jì)算在給定類別屬性C時(shí)，描述屬性A1, ., Am之間的依賴強(qiáng)度，共得到 個(gè)依賴強(qiáng)度；然后，根據(jù)從強(qiáng)到弱的原則選擇m-1個(gè)依賴強(qiáng)度，添加相應(yīng)描述屬性之間的無向邊，并使各個(gè)描述屬性之間形成無向樹；最后，選擇根節(jié)點(diǎn)，為無向邊添加方向形成有向樹。其中，可以利用條件互信息描述在給定類別屬性C時(shí)，描述屬性A1, ., Am之間的依賴強(qiáng)度。88樹增強(qiáng)樸素貝葉斯分類樹型結(jié)構(gòu)構(gòu)造方法的基本思想是：88在給定離散隨機(jī)變量Z

50、時(shí)，離散隨機(jī)變量X和Y之間的條件互信息定義為 式中，p(x,y,z)為X=x,Y=y,Z=z的聯(lián)合概率；p(x,y|z)為已知Z=z時(shí)，X=x,Y=y的聯(lián)合條件概率；p(x|z)為已知Z=z時(shí)，X=x的條件概率；p(y|z)為已知Z=z時(shí)，Y=y的條件概率?？梢宰C明，X和Y在給定Z時(shí)條件獨(dú)立當(dāng)且僅當(dāng)I(X;Y|Z)=0。89在給定離散隨機(jī)變量Z時(shí)，離散隨機(jī)變量X和Y之間的條件互信息定類似地，可以定義在給定類別屬性C時(shí)，描述屬性Ai和Aj之間的條件互信息I(Ai;Aj|C) 式中，p(ai, aj, c)為Ai= ai, Aj=aj, C=c的聯(lián)合概率；p(ai, aj|c)為已知C=c時(shí)，Ai

51、=ai, Aj=aj的聯(lián)合條件概率；p(ai|c)為已知C=c時(shí)，Ai=ai的條件概率；p(aj|c)為已知C=c時(shí)，Aj=aj的條件概率。 90類似地，可以定義在給定類別屬性C時(shí)，描述屬性Ai和Aj之間的算法：樹增強(qiáng)樸素貝葉斯分類結(jié)構(gòu)學(xué)習(xí)算法輸入：訓(xùn)練數(shù)據(jù)集S輸出：樹增強(qiáng)樸素貝葉斯分類的貝葉斯網(wǎng)結(jié)構(gòu)TAN步驟：（1）掃描S，通過式（7.22）計(jì)算在給定類別屬性C時(shí)，描述屬性A1, ., Am之間的條件互信息（2）構(gòu)造一個(gè)無向完全圖，以描述屬性為節(jié)點(diǎn)，以條件互信息為邊的權(quán)重（3）構(gòu)造上述無向完全圖的最大生成樹（4）在上述最大生成樹中選擇一個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)，為無向邊添加方向形成有向樹（5）在上述有

52、向樹中添加節(jié)點(diǎn)C和C到各個(gè)A1, ., Am的有向邊，得到TAN91算法：樹增強(qiáng)樸素貝葉斯分類結(jié)構(gòu)學(xué)習(xí)算法91例如，訓(xùn)練樣本如下表所示L年齡收入學(xué)生信譽(yù)購買計(jì)算機(jī)30高否中是30高否優(yōu)否31.40高否中是41中否中是41低是中是41低是優(yōu)否31.40低是優(yōu)是30中否中否30低是中是41中是中是30中是優(yōu)是31.40中否優(yōu)是31.40高是中是41中否優(yōu)否92例如，訓(xùn)練樣本如下表所示L年齡收入學(xué)生信譽(yù)購買計(jì)算機(jī)30高新樣本為（3140，中，否，優(yōu)），應(yīng)用樹增強(qiáng)樸素貝葉斯分類對新樣本進(jìn)行分類。因?yàn)镮(年齡；收入|購買計(jì)算機(jī))0.4196I(年齡；學(xué)生 | 購買計(jì)算機(jī))0.2228I(年齡；信譽(yù) |

53、購買計(jì)算機(jī))0.3118I(收入；學(xué)生 | 購買計(jì)算機(jī))0.4196I(收入；信譽(yù) | 購買計(jì)算機(jī))0.1689I(學(xué)生；信譽(yù) | 購買計(jì)算機(jī))0.0611所以樹增強(qiáng)樸素貝葉斯分類的貝葉斯網(wǎng)結(jié)構(gòu)如下圖所示。 93新樣本為（3140，中，否，優(yōu)），應(yīng)用樹增貝葉斯網(wǎng)結(jié)構(gòu)購買計(jì)算機(jī)信譽(yù)年齡收入學(xué)生94貝葉斯網(wǎng)結(jié)構(gòu)購買計(jì)算機(jī)信譽(yù)年齡收入學(xué)生94因?yàn)閜(是)9/14；p(3140 | 是)4/9；p(中 | 是，3140)1/4；p(否 | 是，中)2/4；p(優(yōu) | 是，3140)2/4；p(是)p(3140 | 是)p(中 | 是，3140)p(否 | 是，中)p(優(yōu) | 是，3140)9/144/

54、91/42/42/41/56；p(否)5/14；p(3140 | 否)0；p(中 | 否，3140)0；p(否 | 否，中)1；p(優(yōu) | 否，3140)0；p(否)p(3140 | 否)p(中 | 否，3140)p(否 | 否，中)p(優(yōu) | 否，3140)5/1400100；所以新樣本的類別是是。 95因?yàn)閜(是)9/14；957.5 回歸分析事物之間的因果關(guān)系涉及兩個(gè)或兩個(gè)以上的變量，只要其中一個(gè)變量變動了，另一個(gè)變量也會跟著變動。表示原因的變量稱為自變量，用X表示，它是固定的（試驗(yàn)時(shí)預(yù)先確定的），沒有隨機(jī)誤差。表示結(jié)果的變量稱為依變量，用Y表示。Y隨X的變化而變化，有隨機(jī)誤差。如果兩個(gè)

55、變量間的關(guān)系屬于因果關(guān)系，一般用回歸來研究。一元回歸：依變量Y在一個(gè)自變量X上的回歸稱為一元回歸；多元回歸：依變量Y在多個(gè)自變量X1, X2, , Xn上的回歸稱為多元回歸。 967.5 回歸分析事物之間的因果關(guān)系涉及兩個(gè)或兩個(gè)以上的變量7.5.1 一元回歸分析1. 建立一元線性回歸方程如果兩個(gè)變量在散點(diǎn)圖上呈線性關(guān)系，就可用一元線性回歸方程來描述。其一般形式為 Y=a+bX 式中，X是自變量；Y是依變量；a、b是一元線性回歸方程的系數(shù)。977.5.1 一元回歸分析1. 建立一元線性回歸方程97a、b的估計(jì)值應(yīng)是使誤差平方和Q(a, b)取最小值的 、 。 式中，n是訓(xùn)練樣本數(shù)目，(x1, y

56、1), , (xn, yn)是訓(xùn)練樣本。98a、b的估計(jì)值應(yīng)是使誤差平方和Q(a, b)取最小值的 為了使Q(a, b)取最小值，分別取Q關(guān)于a、b的偏導(dǎo)數(shù)，并令它們等于零：99為了使Q(a, b)取最小值，分別取Q關(guān)于a、b的偏導(dǎo)數(shù)，并求解上述方程組，得到唯一的一組解 、 ：其中，100求解上述方程組，得到唯一的一組解 、 ：100算法：一元線性回歸分析算法輸入：訓(xùn)練數(shù)據(jù)集S輸出：一元線性回歸方程的系數(shù)估計(jì) 、步驟：（1）初始化Sx、Sy、Sxy、Sxx為零（2）for S中的每個(gè)訓(xùn)練樣本(x, y)（2.1）Sx= Sx +x /計(jì)算（2.2）Sy= Sy +y /計(jì)算 （2.3）Sxy=

57、 Sxy +xy /計(jì)算（2.4）Sxx= Sxx +x2 /計(jì)算 101算法：一元線性回歸分析算法101（3） （4）2. 假設(shè)檢驗(yàn)：檢驗(yàn)兩個(gè)變量之間的線性關(guān)系假設(shè)是否可以接受。 如果變量X與Y之間的線性關(guān)系假設(shè)符合實(shí)際，則一元線性回歸方程的系數(shù)b不應(yīng)為零。因此，檢驗(yàn)假設(shè)H0：b=0，H1：b0。如果拒絕假設(shè)H0：b=0，則認(rèn)為變量X與Y之間的線性關(guān)系假設(shè)符合實(shí)際。 102（3） 102t檢驗(yàn)是一種比較常用的假設(shè)檢驗(yàn)方法。t檢驗(yàn)采用以下檢驗(yàn)統(tǒng)計(jì)量 t(n-2) 式中， 為 的標(biāo)準(zhǔn)差。 103t檢驗(yàn)是一種比較常用的假設(shè)檢驗(yàn)方法。t檢驗(yàn)采用以下檢驗(yàn)統(tǒng)計(jì)量當(dāng)H0為真時(shí)，b=0， t(n-2)。所以，H0的拒絕域?yàn)?t/2(n-2) 式中，為顯著性水平。給定顯著性水平，如果|t|t/2(n-2)，則拒絕假設(shè)H0：b=0，認(rèn)為回歸效果顯著，變量X與Y之間的線性關(guān)系假設(shè)符合實(shí)際。 104當(dāng)H0為真時(shí)，b=0， t(n-2)。所3. 預(yù)測：經(jīng)過假設(shè)檢驗(yàn)，如果變量X與Y之間的線性關(guān)系假設(shè)符合實(shí)際，則可用一元線性回歸方程進(jìn)行預(yù)測。對于任意x，將其代入方程即可預(yù)測出與之對應(yīng)的y。1053. 預(yù)測：經(jīng)過假設(shè)檢驗(yàn)，如果變量X與Y之間的線性關(guān)系假設(shè)