機器學習6.決策樹分類

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

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

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

4、IDAgeHas-jobOwn_houseCredit_ratingClass1YoungFalseFalseFairNo2YoungFalseFalseGoodNo3YoungTrueFalseGoodYes4YoungTrueTrueFairYes5YoungFalseFalseFairNo6MiddleFalseFalseFairNo7MiddleFalseFalseGoodNo8MiddleTrueTrueGoodYes9MiddleFalseTrueExcellentYes10MiddleFalseTrueExcellentYes11OldFalseTrueExcellentYes1

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

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

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

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

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

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

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

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

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

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

15、“否”信用一般的有8個, 其中2個為“否” Info信用(D) Gain(信用) = Info(D) - Info信用(D)= 0.940 - 0.892 = 0.048收入學生信用買了電腦高否一般否高否好否中否一般否低是一般是中是好是收入學生信用買了電腦高否一般是低是好是中否好是高是一般是確定第一次分裂的屬性收入學生信用買了電腦中否一般是低是一般是低是好否中是一般是中否好否年齡40“年齡”屬性具體最高信息增益，成為分裂屬性收入學生信用買了電腦高否一般否高否好否中否一般否低是一般是中是好是 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學生(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“學生”屬性具體最高信息增益，成為分裂屬性確定第二次分裂的屬性年齡40學

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

18、決策樹，然后使用決策對新數(shù)據(jù)進行分析。本質(zhì)上決策樹是通過一系列規(guī)則對數(shù)據(jù)進行分類的過程。決策樹技術(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. 分類樹采用的標準： 分類錯誤率: Gini 指數(shù): 信息熵: 主要內(nèi)容什么

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

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

21、了電腦30高否一般否40中否一般是40低是一般是40低是好否30-40低是好是30中否一般否40中是一般是40中否好否Info(D) = 0.940Info收入(D) = 0.911Gain(收入) = 0.029高收入的有4個中等收入的有6個低收入的有4個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改進2：連續(xù)值屬性與分裂點對于連續(xù)值屬性，按屬性值大小從小到大排序

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

23、個概率改進3：缺失值的處理建樹過程（學習過程）選定訓練樣本實例有缺失值，如何知道要將其分配到哪個分支？分類過程（測試過程或者工作過程）待分類實例有缺失值，如何測試該實例屬于哪個分支？天氣晴多云雨(天氣=缺失，溫度=72，濕度=90.)改進3： C4.5中缺失值的處理 - 建樹過程（學習過程）Gain(A) = F ( Info(D) InfoA(D)其中 F 為屬性值未缺失的實例所占比例；計算 Info(D) 和 InfoA(D) 時忽略屬性值缺失的實例 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改進3： C4.5中缺失值的處理 - 建樹過程（學習過程）計算 SplitInfo 時，將缺失的屬性值當作一個正常值進行計算，本例中，當作天氣有四個值，分別是晴, 多云, 雨, ?，再計算其 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改進3： C4.5中缺失值的處理 - 建樹過程（學習過程）分裂時，將屬性值缺失的實例分配給所有分支，但是帶一個權(quán)重濕度有風玩？權(quán)重709085957090有有無無無有玩不玩不玩不玩玩玩111115/13濕度有風玩？權(quán)重90786575有無有無玩玩玩玩3/13111T1: (天氣=晴)T1: (天氣=多云)濕度有風玩？權(quán)重807080809690有有無無無有不玩不玩玩玩玩玩11111

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

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

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

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

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

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

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

33、行，直至不可再分，成為葉節(jié)點為止。回歸樹（Regression Tree）因變量-continuous ，葉子為因變量的預(yù)測值。 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ù)測)使用GINI指標來選擇分裂屬性使用二元切分(將生成二叉樹)基于代價-復雜度剪枝Gini指標 指標用來度量數(shù)據(jù)劃分或者數(shù)據(jù)集的不純度。其中， 是 中樣本屬于 類的概率，并用 估計。 電腦銷售數(shù)據(jù)集中，9個樣本屬于“購買電腦”，5個樣本屬于“未購買電腦”Gini指標如果按照 的二元分裂，將 劃分成 和 ，則給定該劃分的 指標為：Gini指標最小，劃分越純。選擇具有最小Gini指標(或最大Gini)的屬性作為分裂屬性處理離散值屬性以收入為例，對收入屬性的所有可能子集：低，中，高，低，中，低，高，中，高，低，中，高考慮所有可能的二元劃

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

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

37、每個 ，尋找子樹 使得 達到最小.而 則起到了平衡樹的大小和數(shù)據(jù)擬合好壞的作用. 較大會得到較小的樹， 較小則會得到較大的樹.對于每個 ，可以證明存在唯一的最小的子樹 使得達到最小.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ù)測的屬性是數(shù)值屬性，非離散值屬性不純度度量：計算所有數(shù)據(jù)的均值，再計算每條數(shù)據(jù)的值到均值的差值的平方和葉子結(jié)點用均值表示C4.5k-MeansSVMAprioriEMPageRankAdaBoostkNNNave BayesCART高伸縮性決策樹算法SLIQ、SP

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

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

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

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

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

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

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

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