機(jī)器學(xué)習(xí)6.決策樹分類

1、決策樹分類王成（副教授）計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院主要內(nèi)容什么是決策樹ID3算法算法改進(jìn)C4.5算法CART算法Decision Tree Modeling決策樹是一種簡(jiǎn)單且應(yīng)用廣泛的預(yù)測(cè)方法決策樹圖3.1 常見(jiàn)的決策樹形式?jīng)Q策樹主要有二元分支（binary split）樹和多分支（multiway split）樹。一般時(shí)候采用二元分裂，因?yàn)槎至言诟F舉搜索中更加靈活。 決策樹形式?jīng)Q策樹決策樹（Decision Tree）又稱為判定樹，是運(yùn)用于分類的一種樹結(jié)構(gòu)。其中的每個(gè)內(nèi)部結(jié)點(diǎn)（internal node）代表對(duì)某個(gè)屬性的一次測(cè)試，每條邊代表一個(gè)測(cè)試結(jié)果，葉結(jié)點(diǎn)（leaf）代表某個(gè)類（class

2、）或者類的分布（class distribution），最上面的結(jié)點(diǎn)是根結(jié)點(diǎn)決策樹提供了一種展示在什么條件下會(huì)得到什么類別這類規(guī)則的方法。下例是為了解決這個(gè)問(wèn)題而建立的一棵決策樹，從中可以看到?jīng)Q策樹的基本組成部分：決策結(jié)點(diǎn)、分支和葉結(jié)點(diǎn)決策樹下圖給出了一個(gè)商業(yè)上使用的決策樹的例子。它表示了一個(gè)關(guān)心電子產(chǎn)品的用戶是否會(huì)購(gòu)買PC（ puter）的知識(shí)，用它可以預(yù)測(cè)某條記錄（某個(gè)人）的購(gòu)買意向決策樹這棵決策樹對(duì)銷售記錄進(jìn)行分類，指出一個(gè)電子產(chǎn)品消費(fèi)者是否會(huì)購(gòu)買一臺(tái)計(jì)算機(jī)“ puter”。每個(gè)內(nèi)部結(jié)點(diǎn)(方形框)代表對(duì)某個(gè)屬性的一次檢測(cè)。每個(gè)葉結(jié)點(diǎn)(橢圓框)代表一個(gè)類: puters=yes 或者 pu

3、ters=no在這個(gè)例子中，特征向量為： (age, student, credit_rating, puters)被決策數(shù)據(jù)的格式為: (age, student, credit_rating)輸入新的被決策的記錄，可以預(yù)測(cè)該記錄隸屬于哪個(gè)類。使用決策樹進(jìn)行分類第1步：利用訓(xùn)練集建立并精化一棵決策樹，建立決策樹模型。這個(gè)過(guò)程實(shí)際上是一個(gè)從數(shù)據(jù)中獲取知識(shí)，進(jìn)行機(jī)器學(xué)習(xí)的過(guò)程第2步：利用生成完畢的決策樹對(duì)輸入數(shù)據(jù)進(jìn)行分類。對(duì)輸入的記錄，從根結(jié)點(diǎn)依次測(cè)試記錄的屬性值，直到到達(dá)某個(gè)葉結(jié)點(diǎn)，從而找到該記錄所在的類主要內(nèi)容什么是決策樹ID3算法算法改進(jìn)C4.5算法CART算法如何從訓(xùn)練數(shù)據(jù)中學(xué)習(xí)決策樹?

4、IDAgeHas-jobOwn_houseCredit_ratingClass1YoungFalseFalseFairNo2YoungFalseFalseGoodNo3YoungTrueFalseGoodYes4YoungTrueTrueFairYes5YoungFalseFalseFairNo6MiddleFalseFalseFairNo7MiddleFalseFalseGoodNo8MiddleTrueTrueGoodYes9MiddleFalseTrueExcellentYes10MiddleFalseTrueExcellentYes11OldFalseTrueExcellentYes1

5、2OldFalseTrueGoodYes13OldTrueFalseGoodYes14OldTrueFalseExcellentYes15OldFalseFalsefairno貸款申請(qǐng)數(shù)據(jù)集如何從訓(xùn)練數(shù)據(jù)中學(xué)習(xí)決策樹?Age？youngmiddleoldNo:3Yes:2No:2Yes:3No:4Yes:1Own_house？truefalseNo:0Yes:6No:6Yes:3(a)(b)兩種可能的根節(jié)點(diǎn)選取方式哪種更好？ID3算法ID3算法主要針對(duì)屬性選擇問(wèn)題使用信息增益度選擇測(cè)試屬性ID3決策樹建立算法1 決定分類屬性集合；2 對(duì)目前的數(shù)據(jù)表，建立一個(gè)節(jié)點(diǎn)N3 如果數(shù)據(jù)庫(kù)中的數(shù)據(jù)都屬于同

6、一個(gè)類，N就是樹葉，在樹葉上 標(biāo)出所屬的類(純的類別)4 如果數(shù)據(jù)表中沒(méi)有其他屬性可以考慮，則N也是樹葉，按照少 數(shù)服從多數(shù)的原則在樹葉上標(biāo)出所屬類別(不純的類別)5 否則，根據(jù)平均信息期望值E或GAIN值選出一個(gè)最佳屬性作 為節(jié)點(diǎn)N的測(cè)試屬性6 節(jié)點(diǎn)屬性選定后，對(duì)于該屬性中的每個(gè)值： 從N生成一個(gè)分支，并將數(shù)據(jù)表中與該分支有關(guān)的數(shù)據(jù)收集形 成分支節(jié)點(diǎn)的數(shù)據(jù)表，在表中刪除節(jié)點(diǎn)屬性那一欄 7如果分支數(shù)據(jù)表屬性非空，則轉(zhuǎn)1，運(yùn)用以上算法從該節(jié)點(diǎn)建立子樹信息熵 (Entropy)我們常說(shuō)信息很多，或信息很少，但卻很難說(shuō)清楚信息到底有多少比如一本50多萬(wàn)字的史記有多少信息量？或一套莎士比亞全集有多少信

7、息量？這個(gè)問(wèn)題幾千年來(lái)都沒(méi)有人給出很好的解答，直到1948年，香農(nóng)(Claude Shannon)在他著名的論文“通信的數(shù)學(xué)原理”中提出了信息熵的概念，才解決了信息的度量問(wèn)題，并且量化出信息的作用信息熵 (Entropy)一條信息的信息量和它的不確定性有著直接的關(guān)系比如，要搞清楚一件非常不確定的事，或是我們一無(wú)所知的事情，就需要了解大量信息。相反，如果我們對(duì)某件事已經(jīng)有了較多了解，那么不需要太多信息就能把它搞清楚從這個(gè)角度看，信息量就等于不確定性的多少如何量化信息的度量呢？信息熵 (Entropy)假如我錯(cuò)過(guò)了一個(gè)有32支球隊(duì)參加的足球賽，賽后我問(wèn)一個(gè)知道比賽結(jié)果的觀眾“哪支球隊(duì)是冠軍”？他不

8、愿意直接告訴我，而讓我猜，每猜一次，他要收一元錢才肯告訴我是否猜對(duì)，那我需要付多少錢才能知道誰(shuí)是冠軍呢？我可以把球隊(duì)編號(hào)，從1到32，然后問(wèn)“冠軍球隊(duì)在1-16號(hào)中嗎？”，假如他告訴我猜對(duì)了，我就接著問(wèn)“冠軍在1-8號(hào)中嗎？”，假如他說(shuō)猜錯(cuò)了，那我就知道冠軍在9-16號(hào)中。這樣只要5次，我就能知道哪支球隊(duì)是冠軍當(dāng)然，香農(nóng)不是用錢，而是用比特(bit)來(lái)度量信息量，在上例中，這條消息的信息量是5比特信息量的比特?cái)?shù)和所有可能情況的對(duì)數(shù)有關(guān)，例如本例中，信息量 = log (球隊(duì)數(shù))，即 5 = log (32)信息熵 (Entropy)實(shí)際上可能不需要5次就能猜出誰(shuí)是冠軍，因?yàn)橐恍?qiáng)隊(duì)得冠的可能性

9、更高，因此第一次猜測(cè)時(shí)可以把少數(shù)幾支強(qiáng)隊(duì)分成一組，其它球隊(duì)分成另一組，然后猜冠軍球隊(duì)是否在那幾支強(qiáng)隊(duì)中這樣，也許三次或四次就能猜出結(jié)果。因此，當(dāng)每支球隊(duì)奪冠的可能性(概率)不等時(shí)，這條信息的信息量比5比特少香農(nóng)指出，它的準(zhǔn)確信息量應(yīng)該是p1,p2,.,p32分別是這32支球隊(duì)奪冠概率，香農(nóng)把它稱作信息熵，單位為比特；可以算出，當(dāng)32支球隊(duì)奪冠概率相同時(shí)，對(duì)應(yīng)的信息熵為5比特。信息熵 (Entropy)對(duì)于任意一個(gè)隨機(jī)變量X(比如奪冠球隊(duì))，它的熵定義為變量的不確定性越大，熵也就越大，把它搞清楚所需要的信息量也就越大數(shù)據(jù)集的信息熵設(shè)數(shù)據(jù)集D中有m個(gè)不同的類C1, C2, C3, ., Cm設(shè) C

10、i,D是數(shù)據(jù)集D中Ci類的樣本的集合, |D|和 |Ci,D|分別是D和 Ci,D中的樣本個(gè)數(shù)其中pi是數(shù)據(jù)集D中任意樣本屬于類Ci的概率，用 估計(jì)數(shù)據(jù)集D的信息熵:例: 計(jì)算對(duì)下列數(shù)據(jù)集分類所需的信息熵年齡收入學(xué)生信用買了電腦30高否一般否40中等否一般是40低是一般是40低是好否30-40低是好是30中否一般否40中是一般是40中否好否|D|=14|C1,D|=5|C2,D|=9使用熵衡量數(shù)據(jù)純度假設(shè)有一個(gè)數(shù)據(jù)集合D，其中只有兩個(gè)類，一個(gè)是正例類，一個(gè)是負(fù)例類計(jì)算D中正例類和負(fù)例類在三種不同的組分下熵的變化情況。（1）D中包含有50%的正例和50%的負(fù)例。 H(D) = -0.5 * lo

11、g20.5 - 0.5 * log20.5 = 1（2）D中包含有20%的正例和80%的負(fù)例。 H(D) = -0.2 * log20.2 - 0.8 * log20.8 = 0.722（3）D中包含有100%的正例和0%的負(fù)例。 H(D) = -1 * log21 - 0 * log20 =0可以看到一個(gè)趨勢(shì)，當(dāng)數(shù)據(jù)變得越來(lái)越“純”時(shí)，熵的值變得越來(lái)越小。當(dāng)D中正反例所占比例相同時(shí)，熵取最大值。當(dāng)D 中所有數(shù)據(jù)都只屬于一個(gè)類時(shí)，熵得到最小值。因此熵可以作為數(shù)據(jù)純凈度或混亂度的衡量指標(biāo)。這正是決策樹學(xué)習(xí)中需要的。數(shù)據(jù)集的信息熵假設(shè)按屬性 A 劃分 D 中的樣本，且屬性 A 根據(jù)訓(xùn)練數(shù)據(jù)的觀測(cè)具

12、有 v 個(gè)不同取值 a1, a2, ., aj , ., av 。如果 A 是離散值，可依屬性 A 將 D 劃分為 v 個(gè)子集 D1, D2, ., Dj , ., Dv 其中，Dj為D中的樣本子集，它們?cè)贏上具有屬性值aj 這些劃分將對(duì)應(yīng)于從該節(jié)點(diǎn)A出來(lái)的分支。按屬性A對(duì)D劃分后，數(shù)據(jù)集的信息熵:其中， 充當(dāng)?shù)?j 個(gè)劃分的權(quán)重。InfoA(D)越小，表示劃分的純度越高信息增益選擇具有最高信息增益Gain(A)的屬性A作為分裂屬性按照能做“最佳分類”的屬性A劃分，使完成樣本分類需要的信息量最小確定第一次分裂的屬性：按年齡劃分年齡收入學(xué)生信用買了電腦30高否一般否40中等否一般是40低是一般是

13、40低是好否30-40低是好是30中否一般否40中是一般是40中否好否年齡40的有5個(gè), 其中2個(gè)為“否” Info年齡(D) Gain(年齡) = Info(D) - Info年齡(D)= 0.940 - 0.694 = 0.246確定第一次分裂的屬性：按收入劃分年齡收入學(xué)生信用買了電腦30高否一般否40中否一般是40低是一般是40低是好否30-40低是好是30中否一般否40中是一般是40中否好否收入=高的有4個(gè), 其中2個(gè)為“否”收入=中的有6個(gè), 其中2個(gè)為“否”收入=低的有4個(gè), 其中1個(gè)為“否” Info收入(D) Gain(收入) = Info(D) - Info收入(D)= 0.

14、940 - 0.911 = 0.029確定第一次分裂的屬性：按學(xué)生劃分年齡收入學(xué)生信用買了電腦30高否一般否40中否一般是40低是一般是40低是好否30-40低是好是30中否一般否40中是一般是40中否好否是學(xué)生的有7個(gè), 其中1個(gè)為“否”不是學(xué)生的有7個(gè), 其中4個(gè)為“否” Info學(xué)生(D) Gain(學(xué)生) = Info(D) - Info學(xué)生(D)= 0.940 - 0.788 = 0.152確定第一次分裂的屬性：按信用劃分年齡收入學(xué)生信用買了電腦30高否一般否40中否一般是40低是一般是40低是好否30-40低是好是30中否一般否40中是一般是40中否好否信用好的有6個(gè), 其中3個(gè)為

15、“否”信用一般的有8個(gè), 其中2個(gè)為“否” Info信用(D) Gain(信用) = Info(D) - Info信用(D)= 0.940 - 0.892 = 0.048收入學(xué)生信用買了電腦高否一般否高否好否中否一般否低是一般是中是好是收入學(xué)生信用買了電腦高否一般是低是好是中否好是高是一般是確定第一次分裂的屬性收入學(xué)生信用買了電腦中否一般是低是一般是低是好否中是一般是中否好否年齡40“年齡”屬性具體最高信息增益，成為分裂屬性收入學(xué)生信用買了電腦高否一般否高否好否中否一般否低是一般是中是好是 Info收入(D)= 2/5 * (-2/2 * log2/2 - 0/2 * log0/2) + 2/

16、5 * (-1/2 * log1/2 - 1/2 * log1/2) + 1/5 * (-1/1 * log1/1 - 0/1 * log0/1)= 0.400 Info學(xué)生(D)= 3/5 * (-3/3 * log3/3 - 0/3 * log0/3) + 2/5 * (-2/2 * log2/2 - 0/2 * log0/2)= 0 Info信用(D)= 3/5 * (-2/3 * log2/3 - 1/3 * log1/3) + 2/5 * (-1/2 * log1/2 - 1/2 * log1/2)= 0.951“學(xué)生”屬性具體最高信息增益，成為分裂屬性確定第二次分裂的屬性年齡40學(xué)

17、生不買買不是學(xué)生是學(xué)生.買ID3決策樹建立算法1 決定分類屬性；2 對(duì)目前的數(shù)據(jù)表，建立一個(gè)節(jié)點(diǎn)N3 如果數(shù)據(jù)庫(kù)中的數(shù)據(jù)都屬于同一個(gè)類，N就是樹葉，在樹葉上 標(biāo)出所屬的類4 如果數(shù)據(jù)表中沒(méi)有其他屬性可以考慮，則N也是樹葉，按照少 數(shù)服從多數(shù)的原則在樹葉上標(biāo)出所屬類別5 否則，根據(jù)平均信息期望值E或GAIN值選出一個(gè)最佳屬性作 為節(jié)點(diǎn)N的測(cè)試屬性6 節(jié)點(diǎn)屬性選定后，對(duì)于該屬性中的每個(gè)值： 從N生成一個(gè)分支，并將數(shù)據(jù)表中與該分支有關(guān)的數(shù)據(jù)收集形 成分支節(jié)點(diǎn)的數(shù)據(jù)表，在表中刪除節(jié)點(diǎn)屬性那一欄7如果分支數(shù)據(jù)表屬性非空，則轉(zhuǎn)1，運(yùn)用以上算法從該節(jié)點(diǎn)建立子樹它首先對(duì)數(shù)據(jù)進(jìn)行處理，利用歸納法生成可讀的規(guī)則和

18、決策樹，然后使用決策對(duì)新數(shù)據(jù)進(jìn)行分析。本質(zhì)上決策樹是通過(guò)一系列規(guī)則對(duì)數(shù)據(jù)進(jìn)行分類的過(guò)程。決策樹技術(shù)發(fā)現(xiàn)數(shù)據(jù)模式和規(guī)則的核心是采用遞歸分割的貪婪算法。決策樹的基本原理 分類決策樹A decision tree is so called because the predictive model can be represented in a tree-like structure. the target is categorical, the model is a called a classification tree. 分類樹采用的標(biāo)準(zhǔn)： 分類錯(cuò)誤率: Gini 指數(shù): 信息熵: 主要內(nèi)容什么

19、是決策樹ID3算法算法改進(jìn)C4.5算法CART算法C4.5算法對(duì)ID3的改進(jìn)改進(jìn)1：用信息增益率代替信息增益來(lái)選擇屬性改進(jìn)2：能夠完成對(duì)連續(xù)值屬性的離散化處理改進(jìn)3：能處理屬性值缺失的情況改進(jìn)4：在決策樹構(gòu)造完成之后進(jìn)行剪枝十大數(shù)據(jù)挖掘算法C4.5k-MeansSVMAprioriEMPageRankAdaBoostkNNNave BayesCART改進(jìn)1：信息增益的問(wèn)題假設(shè)按屬性 A 劃分 D 中的樣本，且屬性 A 根據(jù)訓(xùn)練數(shù)據(jù)的觀測(cè)具有 v 個(gè)不同取值 a1, a2, ., aj , ., av 。如果 A 是離散值，可依屬性 A 將 D 劃分為 v 個(gè)子集 D1, D2, ., Dj ,

20、 ., Dv 其中，Dj為D中的樣本子集，它們?cè)贏上具有屬性值aj 這些劃分將對(duì)應(yīng)于從該節(jié)點(diǎn)A出來(lái)的分支。信息增益度量偏向于對(duì)取值較多的屬性進(jìn)行測(cè)試，即它傾向于選擇v較大的屬性A舉個(gè)極端的例子：考慮充當(dāng)唯一標(biāo)識(shí)的屬性PID。對(duì)PID的分裂將產(chǎn)生大量劃分（與樣本個(gè)數(shù)一樣多），每個(gè)分類只包含一個(gè)樣本，且每個(gè)劃分都是純的。對(duì)屬性PID劃分得到的信息增益最大，顯然，這種劃分對(duì)分類沒(méi)有用處。改進(jìn)1：信息增益率C4.5使用分裂信息(split information)將信息增益規(guī)范化該值表示數(shù)據(jù)集D按屬性A分裂的v個(gè)劃分產(chǎn)生的信息選擇具有最大信息增益率的屬性作為分裂屬性改進(jìn)1：信息增益率年齡收入學(xué)生信用買

21、了電腦30高否一般否40中否一般是40低是一般是40低是好否30-40低是好是30中否一般否40中是一般是40中否好否Info(D) = 0.940Info收入(D) = 0.911Gain(收入) = 0.029高收入的有4個(gè)中等收入的有6個(gè)低收入的有4個(gè)SplitInfo收入(D)= - 4/14 * log4/14 - 6/14 * log6/14 - 4/14 * log4/14= 1.557 GainRatio(收入) = Gain(收入) / SplitInfo收入(D)= 0.029 / 1.557 = 0.019改進(jìn)2：連續(xù)值屬性與分裂點(diǎn)對(duì)于連續(xù)值屬性，按屬性值大小從小到大排序

22、，取每對(duì)相鄰值的中點(diǎn)作為可能的分裂點(diǎn)split_point。假設(shè)一連續(xù)值屬性共有N個(gè)不同的屬性值，則可找到N-1個(gè)可能的分裂點(diǎn)。檢查每個(gè)可能分裂點(diǎn)，取能使得信息增益最大的分裂點(diǎn)，將D分裂成D1: A split_point(一個(gè)分裂點(diǎn)，二分法，二叉樹)56105.588C4.5不使用中點(diǎn)，而是直接使用一對(duì)值中較小的值作為可能的分裂點(diǎn)，如本例中將使用5, 6作為可能分裂點(diǎn)多個(gè)分裂點(diǎn)？多分法，多叉決策樹改進(jìn)3：缺失值的處理在某些情況下，可供使用的數(shù)據(jù)可能缺少某些屬性的值，例如一種簡(jiǎn)單的辦法是賦予它該屬性最常見(jiàn)的值，例如將“晴”或“雨”賦予第6個(gè)實(shí)例的天氣屬性一種更復(fù)雜的策略是為A的每個(gè)可能值賦予一

23、個(gè)概率改進(jìn)3：缺失值的處理建樹過(guò)程（學(xué)習(xí)過(guò)程）選定訓(xùn)練樣本實(shí)例有缺失值，如何知道要將其分配到哪個(gè)分支？分類過(guò)程（測(cè)試過(guò)程或者工作過(guò)程）待分類實(shí)例有缺失值，如何測(cè)試該實(shí)例屬于哪個(gè)分支？天氣晴多云雨(天氣=缺失，溫度=72，濕度=90.)改進(jìn)3： C4.5中缺失值的處理 - 建樹過(guò)程（學(xué)習(xí)過(guò)程）Gain(A) = F ( Info(D) InfoA(D)其中 F 為屬性值未缺失的實(shí)例所占比例；計(jì)算 Info(D) 和 InfoA(D) 時(shí)忽略屬性值缺失的實(shí)例 Info(D) = -8/13log(8/13) - 5/13log(5/13)= 0.961 bits Info天氣(D) = 5/13(

24、-2/5log(2/5) - 3/5log(3/5) + 3/13(-3/3log(3/3) - 0/3log(0/3) + 5/13(-3/5log(3/5) - 2/5log(2/5)= 0.747 bits Gain(天氣)= 13/14 (0.961 - 0.747)= 0.199 bits改進(jìn)3： C4.5中缺失值的處理 - 建樹過(guò)程（學(xué)習(xí)過(guò)程）計(jì)算 SplitInfo 時(shí)，將缺失的屬性值當(dāng)作一個(gè)正常值進(jìn)行計(jì)算，本例中，當(dāng)作天氣有四個(gè)值，分別是晴, 多云, 雨, ?，再計(jì)算其 SplitInfoSplitInfo天氣(D)= - 5/14log(5/14) - 3/14log(3/1

25、4) - 5/14log(5/14) - 1/14log(1/14)= 1.809 bits晴多云雨缺失 GainRatio(天氣)= Gain(天氣) / SplitInfo天氣(D)= 0.199 / 1.809改進(jìn)3： C4.5中缺失值的處理 - 建樹過(guò)程（學(xué)習(xí)過(guò)程）分裂時(shí)，將屬性值缺失的實(shí)例分配給所有分支，但是帶一個(gè)權(quán)重濕度有風(fēng)玩？權(quán)重709085957090有有無(wú)無(wú)無(wú)有玩不玩不玩不玩玩玩111115/13濕度有風(fēng)玩？權(quán)重90786575有無(wú)有無(wú)玩玩玩玩3/13111T1: (天氣=晴)T1: (天氣=多云)濕度有風(fēng)玩？權(quán)重807080809690有有無(wú)無(wú)無(wú)有不玩不玩玩玩玩玩11111

26、5/13T1: (天氣=雨)本例14個(gè)實(shí)例中共13個(gè)實(shí)例天氣屬性值未缺失：其中5個(gè)實(shí)例的天氣屬性為“晴”，3個(gè)實(shí)例的天氣屬性為“多云”， 5個(gè)實(shí)例的天氣屬性為“雨”本例14個(gè)實(shí)例中共1個(gè)實(shí)例天氣屬性值缺失，因此估算出天氣屬性值缺失的第6個(gè)實(shí)例：天氣是晴的概率是5/13，天氣是多云的概率是3/13，天氣是雨的概率是5/13改進(jìn)3： C4.5中缺失值的處理 - 建樹過(guò)程（學(xué)習(xí)過(guò)程）濕度有風(fēng)玩？權(quán)重709085957090有有無(wú)無(wú)無(wú)有玩不玩不玩不玩玩玩111115/13=0.4T1: (天氣=晴)濕度 75 5/13玩，3不玩濕度玩 (2.0)不玩 (3.4/0.4)75葉節(jié)點(diǎn)以 (N/E) 的形式

27、定義，其中 N 為到達(dá)該葉節(jié)點(diǎn)的實(shí)例數(shù)，E 為其中屬于其它分類的實(shí)例數(shù)。例如，不玩(3.4/0.4) 表示3.4個(gè)實(shí)例到達(dá)“不玩”節(jié)點(diǎn)，其中0.4個(gè)實(shí)例不屬于“不玩”改進(jìn)3： C4.5中缺失值的處理 - 分類過(guò)程濕度玩 (2.0)不玩 (3.4/0.4)75天氣晴(天氣=晴，溫度=90，濕度=缺失 .)對(duì)于任一實(shí)例，濕度 75 的可能性是 3.4/(2.0 + 3.4)當(dāng)濕度 75 時(shí)， 分類為玩的可能性 = 0.4/3.4=12% 分類為不玩的可能性 = 3/3.4=88%最終分類的概率分布為：玩 = 2.0/5.4100% + 3.4/5.412% = 44%不玩 = 3.4/5.488%

28、 = 56%改進(jìn)4：學(xué)習(xí)過(guò)程中的過(guò)度擬合上述的決策樹算法增長(zhǎng)樹的每一個(gè)分支的深度，直到恰好能對(duì)訓(xùn)練樣例比較完美地分類。實(shí)際應(yīng)用中，當(dāng)訓(xùn)練樣本中有噪聲或訓(xùn)練樣例的數(shù)量太少以至于不能產(chǎn)生目標(biāo)函數(shù)的有代表性的采樣時(shí)，該策略可能會(huì)遇到困難在以上情況發(fā)生時(shí)，這個(gè)簡(jiǎn)單的算法產(chǎn)生的樹會(huì)過(guò)度擬合訓(xùn)練樣例 (過(guò)度擬合: Over fitting)過(guò)度擬合產(chǎn)生的原因：訓(xùn)練樣本中有噪聲，訓(xùn)練樣例太小等改進(jìn)4：欠擬合、合適擬合、過(guò)擬合欠擬合合適擬合過(guò)擬合改進(jìn)4：過(guò)度擬合訓(xùn)練樣本中噪聲導(dǎo)致的過(guò)度擬合錯(cuò)誤的類別值/類標(biāo)簽，屬性值等訓(xùn)練樣本中缺乏代表性樣本所導(dǎo)致的過(guò)度擬合根據(jù)少量訓(xùn)練記錄作出的分類決策模型容易受過(guò)度擬合的影

29、響。由于訓(xùn)練樣本缺乏代表性的樣本，在沒(méi)有多少訓(xùn)練記錄的情況下，學(xué)習(xí)算法仍然繼續(xù)細(xì)化模型就會(huì)導(dǎo)致過(guò)度擬合改進(jìn)4：缺乏代表性樣本所導(dǎo)致的過(guò)度擬合名稱體溫胎生4條腿冬眠哺乳動(dòng)物蠑螈冷血NYYN虹鳉冷血YNNN鷹恒溫NNNN弱夜鷹恒溫NNYN鴨嘴獸恒溫YYYY哺乳動(dòng)物分類的訓(xùn)練樣例名稱體溫胎生4條腿冬眠哺乳動(dòng)物人恒溫YNNY大象恒溫YYNY鴿子恒溫NNNN體溫恒溫冷血冬眠NY N N4條腿Y N NY按照訓(xùn)練模型。人和大象都不是哺乳動(dòng)物。決策樹作出這樣的判斷是因?yàn)橹挥幸粋€(gè)訓(xùn)練樣例具有這些特點(diǎn)（鷹，恒溫，不冬眠）被劃分為非哺乳動(dòng)物。該例清楚表明，當(dāng)決策樹的葉節(jié)點(diǎn)沒(méi)有足夠的代表性時(shí)，可能會(huì)預(yù)測(cè)錯(cuò)誤。哺乳動(dòng)

30、物分類的測(cè)試樣例改進(jìn)4：決策樹剪枝How?預(yù)剪枝(prepruning)后剪枝(postpruning)在完全正確分類訓(xùn)練集之前就停止樹的生長(zhǎng)。由“完全生長(zhǎng)”的樹剪去子樹。改進(jìn)4：預(yù)剪枝yesyesno 剪枝處理yesno45311no否否否否是是是是最直接的方法：事先限定樹的最大生長(zhǎng)高度如果設(shè)為3，則如圖剪枝改進(jìn)4：后剪枝訓(xùn)練過(guò)程中允許對(duì)數(shù)據(jù)的過(guò)度擬合，然后再利用測(cè)試集對(duì)樹進(jìn)行修剪樹葉用被替換的子樹最頻繁的類標(biāo)號(hào)yesyesnoyesno41311no2yes/no2NO是是是是是是否否否否否否改進(jìn)4：后剪枝在測(cè)試集上定義損失函數(shù)C，我們的目標(biāo)是通過(guò)剪枝使得在測(cè)試集上C的值下降。例如通過(guò)剪枝

31、使在測(cè)試集上誤差率降低。1. 自底向上的遍歷每一個(gè)非葉節(jié)點(diǎn)(除了根節(jié)點(diǎn))，將當(dāng)前的非葉節(jié)點(diǎn)從樹中減去，其下所有的葉節(jié)點(diǎn)合并成一個(gè)節(jié)點(diǎn)，代替原來(lái)被剪掉的節(jié)點(diǎn)。2. 計(jì)算剪去節(jié)點(diǎn)前后的損失函數(shù)，如果剪去節(jié)點(diǎn)之后損失函數(shù)變小了，則說(shuō)明該節(jié)點(diǎn)是可以剪去的，并將其剪去；如果發(fā)現(xiàn)損失函數(shù)并沒(méi)有減少，說(shuō)明該節(jié)點(diǎn)不可剪去，則將樹還原成未剪去之前的狀態(tài)。3. 重復(fù)上述過(guò)程，直到所有的非葉節(jié)點(diǎn)(除了根節(jié)點(diǎn))都被嘗試了。從決策樹導(dǎo)出產(chǎn)生式規(guī)則大型決策樹可讀性較低，可通過(guò)從決策樹導(dǎo)出產(chǎn)生式規(guī)則以提高可讀性把從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑中遇到的所有測(cè)試條件聯(lián)合起來(lái)，便可建立相對(duì)應(yīng)的規(guī)則集從決策樹導(dǎo)出產(chǎn)生式規(guī)則但這樣的規(guī)則會(huì)

32、導(dǎo)致某些不必要的復(fù)雜性可用類似的方法對(duì)規(guī)則集進(jìn)行剪枝對(duì)于某一規(guī)則，將它的單個(gè)條件暫時(shí)去除，在測(cè)試集上估計(jì)誤差率，并與原規(guī)則的誤差率進(jìn)行比較，若新規(guī)則的結(jié)果較好，則刪除這個(gè)條件IF 天氣=晴 AND 濕度 = 75THEN 玩IF 天氣=晴THEN 玩主要內(nèi)容什么是決策樹ID3算法算法改進(jìn)C4.5算法CART算法CART算法分類回歸樹（CART:Classification and Regression Tree）其特點(diǎn)是在計(jì)算過(guò)程中充分利用二分支樹的結(jié)構(gòu)（Bianry Tree-structured），即根節(jié)點(diǎn)包含所有樣本，在一定的分裂規(guī)則下根節(jié)點(diǎn)被分裂為兩個(gè)子節(jié)點(diǎn)，這個(gè)過(guò)程又在子節(jié)點(diǎn)上重復(fù)進(jìn)

33、行，直至不可再分，成為葉節(jié)點(diǎn)為止。回歸樹（Regression Tree）因變量-continuous ，葉子為因變量的預(yù)測(cè)值。 Boston Housing DataLeaves = Boolean Rules（布爾規(guī)則）Leaf12345678RM6.56.56.56.5, 6.9)6.96.9, 7.4)7.46.9NOX.51.51, .63).63, .67).67.67.66.66.66Predicted MEDV2219272714334616If RM values & NOX values, then MEDV=valueCART算法CART: Classification

34、And Regression Trees可用于分類和回歸(數(shù)值預(yù)測(cè))使用GINI指標(biāo)來(lái)選擇分裂屬性使用二元切分(將生成二叉樹)基于代價(jià)-復(fù)雜度剪枝Gini指標(biāo) 指標(biāo)用來(lái)度量數(shù)據(jù)劃分或者數(shù)據(jù)集的不純度。其中， 是 中樣本屬于 類的概率，并用 估計(jì)。 電腦銷售數(shù)據(jù)集中，9個(gè)樣本屬于“購(gòu)買電腦”，5個(gè)樣本屬于“未購(gòu)買電腦”Gini指標(biāo)如果按照 的二元分裂，將 劃分成 和 ，則給定該劃分的 指標(biāo)為：Gini指標(biāo)最小，劃分越純。選擇具有最小Gini指標(biāo)(或最大Gini)的屬性作為分裂屬性處理離散值屬性以收入為例，對(duì)收入屬性的所有可能子集：低，中，高，低，中，低，高，中，高，低，中，高考慮所有可能的二元?jiǎng)?/p>

35、分，并計(jì)算劃分前后的Gini指標(biāo)，選擇能產(chǎn)生最小Gini指標(biāo)的子集作為分裂子集收入中，高.是否回歸樹的生成 數(shù)據(jù)：N個(gè)觀測(cè)，p個(gè)自變量，1個(gè)因變量(連續(xù)型) 目標(biāo)：自動(dòng)地選擇分裂變量及其分裂點(diǎn)假設(shè)有一個(gè)分裂把自變量空間分成M個(gè)區(qū)域:在每個(gè)區(qū)域，我們用一個(gè)常數(shù)來(lái)擬合因變量：優(yōu)化目標(biāo)：誤差平方和最小 上最優(yōu)的擬合解為 從根節(jié)點(diǎn)開始，考慮一個(gè)分裂變量j和分裂點(diǎn)s，得到2個(gè)區(qū)域：最優(yōu)的變量j和分裂點(diǎn)s，要滿足對(duì)于給定的j和s，最里層的優(yōu)化問(wèn)題的解為而對(duì)于給定的j,分裂點(diǎn)s很快能找到.這樣，遍歷所有的自變量，就能找到最佳的一對(duì)j和s.遞歸分割-greedy algorithm剪枝 最大的決策樹能對(duì)訓(xùn)練集

36、的準(zhǔn)確率達(dá)到100%，最大的分類樹的結(jié)果會(huì)導(dǎo)致過(guò)擬合（對(duì)信號(hào)和噪聲都適應(yīng)）。因此建立的樹模型不能很好的推廣到總體中的其他樣本數(shù)據(jù)。同樣，太小的決策樹僅含有很少的分支，會(huì)導(dǎo)致欠擬合。一個(gè)好的樹模型有低的偏倚和低的方差，模型的復(fù)雜性往往在偏倚和方差之間做一個(gè)折中，因此要對(duì)樹進(jìn)行剪枝。這里介紹 plexity pruning。最大樹決策樹能長(zhǎng)到每個(gè)葉子都是純的。最大的分類可以達(dá)到100%的準(zhǔn)確，最大的回歸樹殘差為0。恰當(dāng)?shù)臉湎壬梢粋€(gè)大的樹 考慮一個(gè)子樹 子樹就是由大樹進(jìn)行刪減內(nèi)部節(jié)點(diǎn)而得到. 用|T|表示樹T 的葉節(jié)點(diǎn)（最終節(jié)點(diǎn)）的個(gè)數(shù).定義cost complexity criterion:對(duì)于

37、每個(gè) ，尋找子樹 使得 達(dá)到最小.而 則起到了平衡樹的大小和數(shù)據(jù)擬合好壞的作用. 較大會(huì)得到較小的樹， 較小則會(huì)得到較大的樹.對(duì)于每個(gè) ，可以證明存在唯一的最小的子樹 使得達(dá)到最小.To find we use weakest link pruning: we successively collapse the internal node that produces the smallest per-node increase in , and continue until we produce the single-node (root) tree. This gives a sequenc

38、e of subtrees, and this sequence must contains Estimation of is achieved by cross-validation: we choose the value to minimize the cross-validation sum of squares.用于回歸要預(yù)測(cè)的屬性是數(shù)值屬性，非離散值屬性不純度度量：計(jì)算所有數(shù)據(jù)的均值，再計(jì)算每條數(shù)據(jù)的值到均值的差值的平方和葉子結(jié)點(diǎn)用均值表示C4.5k-MeansSVMAprioriEMPageRankAdaBoostkNNNave BayesCART高伸縮性決策樹算法SLIQ、SP

39、RINT、BOAT決策樹基本概念決策樹的優(yōu)點(diǎn)1、推理過(guò)程容易理解，決策推理過(guò)程可以表示成If Then形式；2、推理過(guò)程完全依賴于屬性變量的取值特點(diǎn)；3、可自動(dòng)忽略目標(biāo)變量沒(méi)有貢獻(xiàn)的屬性變量，也為判斷屬性 變量的重要性，減少變量的數(shù)目提供參考。決策樹基本概念關(guān)于歸納學(xué)習(xí)(1) 決策樹技術(shù)發(fā)現(xiàn)數(shù)據(jù)模式和規(guī)則的核心是歸納算法。 歸納是從特殊到一般的過(guò)程。歸納推理從若干個(gè)事實(shí)中表征出的特征、特性和屬性中，通過(guò)比較、總結(jié)、概括而得出一個(gè)規(guī)律性的結(jié)論。 歸納推理試圖從對(duì)象的一部分或整體的特定的觀察中獲得一個(gè)完備且正確的描述。即從特殊事實(shí)到普遍性規(guī)律的結(jié)論。歸納對(duì)于認(rèn)識(shí)的發(fā)展和完善具有重要的意義。人類知識(shí)

40、的增長(zhǎng)主要來(lái)源于歸納學(xué)習(xí)。決策樹基本概念關(guān)于歸納學(xué)習(xí)(2) 歸納學(xué)習(xí)的過(guò)程就是尋找一般化描述的過(guò)程。這種一般性描述能夠解釋給定的輸入數(shù)據(jù)，并可以用來(lái)預(yù)測(cè)新的數(shù)據(jù)。 銳角三角形內(nèi)角和等于180度； 鈍角三角形內(nèi)角和等于180度； 三角形內(nèi)角和 直角三角形內(nèi)角和等于180度； 等于180度 已知三角形ABC，A角等于76度，B角等于89度，則其C角等于15度 歸納學(xué)習(xí)由于依賴于檢驗(yàn)數(shù)據(jù)，因此又稱為檢驗(yàn)學(xué)習(xí)。歸納學(xué)習(xí)存在一個(gè)基本的假設(shè)： 任一假設(shè)如果能夠在足夠大的訓(xùn)練樣本集中很好的逼近目標(biāo)函數(shù)，則它也能在未見(jiàn)樣本中很好地逼近目標(biāo)函數(shù)。該假定是歸納學(xué)習(xí)的有效性的前提條件。決策樹基本概念關(guān)于歸納學(xué)習(xí)(3

41、)決策樹基本概念關(guān)于歸納學(xué)習(xí)(4) 歸納過(guò)程就是在描述空間中進(jìn)行搜索的過(guò)程。歸納可分為自頂向下，自底向上和雙向搜索三種方式。 自底向上法一次處理一個(gè)輸入對(duì)象。將描述逐步一般化。直到最終的一般化描述。 自頂向下法對(duì)可能的一般性描述集進(jìn)行搜索，試圖找到一些滿足一定要求的最優(yōu)的描述。決策樹基本概念從機(jī)器學(xué)習(xí)看分類及歸納推理等問(wèn)題（1） 從特殊的訓(xùn)練樣例中歸納出一般函數(shù)是機(jī)器學(xué)習(xí)的中心問(wèn)題；從訓(xùn)練樣例中進(jìn)行學(xué)習(xí)通常被視為歸納推理。每個(gè)例子都是一個(gè)對(duì)偶（序偶）（x, f(x)），對(duì)每個(gè)輸入的x，都有確定的輸出f(x)。 學(xué)習(xí)過(guò)程將產(chǎn)生對(duì)目標(biāo)函數(shù)f的不同逼近。F的每一個(gè)逼近都叫做一個(gè)假設(shè)。假設(shè)需要以某種形

42、式表示。例如，y=ax+b。通過(guò)調(diào)整假設(shè)的表示，學(xué)習(xí)過(guò)程將產(chǎn)生出假設(shè)的不同變形。在表示中通常需要修改參數(shù)（如a, b）。 決策樹基本概念從機(jī)器學(xué)習(xí)看分類及歸納推理等問(wèn)題（2） 從這些不同的變形中選擇最佳的假設(shè)（或者說(shuō)權(quán)值集合）。一般方法如定義為使訓(xùn)練值與假設(shè)值 預(yù)測(cè)出的值之間的誤差平方和E最小為最佳。 學(xué)習(xí)是在假設(shè)空間上的一個(gè)搜索。概念學(xué)習(xí)也可以看作是一個(gè)搜索問(wèn)題的過(guò)程。它在預(yù)定義的假設(shè)空間中搜索假設(shè)，使其與訓(xùn)練樣例有最佳的擬合度。多數(shù)情況下，為了高效地搜索，可以利用假設(shè)空間中一種自然形成的結(jié)構(gòu)，即一般到特殊的偏序關(guān)系。 決策樹基本概念從機(jī)器學(xué)習(xí)看分類及歸納推理等問(wèn)題（3） 分類模型的性能根據(jù)

43、模型正確和錯(cuò)誤預(yù)測(cè)也可以根據(jù)的檢驗(yàn)記錄計(jì)數(shù)進(jìn)行評(píng)估。這些計(jì)數(shù)存儲(chǔ)在混同矩陣（Confusion Matrix）的表格中，二元分類問(wèn)題混淆矩陣如下：實(shí)際的類類1f11類0f01f10f00類1類0預(yù)測(cè)的類準(zhǔn)確率=正確的預(yù)測(cè)數(shù)/預(yù)測(cè)總數(shù)=（f11+f00）/(f11+f01+f10+f00)差錯(cuò)率=錯(cuò)誤的預(yù)測(cè)數(shù)/預(yù)測(cè)總數(shù)=（f10+f01）/(f11+f01+f10+f00)歸納學(xué)習(xí)假設(shè) 機(jī)器學(xué)習(xí)的任務(wù)是在整個(gè)實(shí)例集合X上確定與目標(biāo)概念c相同的假設(shè) 。一般H表示所有可能假設(shè)。H中每個(gè)假設(shè)h表示X上定義的布爾函數(shù)。由于對(duì)c僅有的信息只是它在訓(xùn)練樣例上的值，因此歸納學(xué)習(xí)最多只能保證輸出的假設(shè)能與訓(xùn)練樣

44、例相擬合。若沒(méi)有更多的信息，只能假定對(duì)于未見(jiàn)實(shí)例最好的假設(shè)就是訓(xùn)練數(shù)據(jù)最佳擬合的假設(shè)。 定義 歸納學(xué)習(xí)假設(shè)：任一假設(shè)如果在足夠大的訓(xùn)練樣例中很好地逼近目標(biāo)函數(shù)，則它也能在未見(jiàn)實(shí)例中很好地逼近目標(biāo)函數(shù)。（Function Approximation）。 決策樹基本概念從機(jī)器學(xué)習(xí)看分類及歸納推理等問(wèn)題（4）決策樹學(xué)習(xí)是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)。從一類無(wú)序、無(wú)規(guī)則的事物（概念）中推理出決策樹表示的分類規(guī)則。概念分類學(xué)習(xí)算法：來(lái)源于Hunt,Marin和Stone 于1966年研制的CLS學(xué)習(xí)系統(tǒng)，用于學(xué)習(xí)單個(gè)概念。1979年, J.R. Quinlan 給出ID3算法，并在1983年和1986年對(duì)ID

45、3 進(jìn)行了總結(jié)和簡(jiǎn)化，使其成為決策樹學(xué)習(xí)算法的典型。Schlimmer 和Fisher 于1986年對(duì)ID3進(jìn)行改造，在每個(gè)可能的決策樹節(jié)點(diǎn)創(chuàng)建緩沖區(qū)，使決策樹可以遞增式生成，得到ID4算法。1988年，Utgoff 在ID4基礎(chǔ)上提出了ID5學(xué)習(xí)算法，進(jìn)一步提高了效率。1993年，Quinlan 進(jìn)一步發(fā)展了ID3算法，改進(jìn)成C4.5算法。另一類決策樹算法為CART，與C4.5不同的是，CART的決策樹由二元邏輯問(wèn)題生成，每個(gè)樹節(jié)點(diǎn)只有兩個(gè)分枝，分別包括學(xué)習(xí)實(shí)例的正例與反例。其基本思想是以信息熵為度量構(gòu)造一棵熵值下降最快的樹，到葉子節(jié)點(diǎn)處的熵值為零，此時(shí)每個(gè)葉節(jié)點(diǎn)中的實(shí)例都屬于同一類。決策樹

46、的基本原理 決策樹學(xué)習(xí)采用的是自頂向下的遞歸方法。決策樹的每一層節(jié)點(diǎn)依照某一屬性值向下分為子節(jié)點(diǎn)，待分類的實(shí)例在每一節(jié)點(diǎn)處與該節(jié)點(diǎn)相關(guān)的屬性值進(jìn)行比較，根據(jù)不同的比較結(jié)果向相應(yīng)的子節(jié)點(diǎn)擴(kuò)展，這一過(guò)程在到達(dá)決策樹的葉節(jié)點(diǎn)時(shí)結(jié)束，此時(shí)得到結(jié)論。從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每一條路經(jīng)都對(duì)應(yīng)著一條合理的規(guī)則，規(guī)則間各個(gè)部分（各個(gè)層的條件）的關(guān)系是合取關(guān)系。整個(gè)決策樹就對(duì)應(yīng)著一組析取的規(guī)則。決策樹學(xué)習(xí)算法的最大優(yōu)點(diǎn)是，它可以自學(xué)習(xí)。在學(xué)習(xí)的過(guò)程中，不需要使用者了解過(guò)多背景知識(shí)，只需要對(duì)訓(xùn)練例子進(jìn)行較好的標(biāo)注，就能夠進(jìn)行學(xué)習(xí)。如果在應(yīng)用中發(fā)現(xiàn)不符合規(guī)則的實(shí)例，程序會(huì)詢問(wèn)用戶該實(shí)例的正確分類，從而生成新的分枝和葉子，并添加到樹中。 決策樹的基本原理 樹是由節(jié)點(diǎn)和分枝組成的層次數(shù)據(jù)結(jié)構(gòu)。節(jié)點(diǎn)用于存貯信息或知識(shí)，分枝用于連接各個(gè)節(jié)點(diǎn)。樹是圖的一個(gè)特例，圖是更一般的數(shù)學(xué)結(jié)構(gòu)，如貝葉斯網(wǎng)絡(luò)。決策樹是描述分類過(guò)程的一種數(shù)據(jù)結(jié)構(gòu)，從上端的根節(jié)點(diǎn)開始，各種分類原則被引用進(jìn)來(lái)，并依這些分類原則將根節(jié)點(diǎn)的數(shù)