決策樹基本研究(ppt-104頁)課件

1、第 6 章 決策樹主要內容決策樹基本概念決策樹算法決策樹研究問題主要參考文獻主要內容決策樹基本概念決策樹算法決策樹研究問題主要參考文獻第6章 決策樹決策樹基本概念關于分類問題 分類（Classification）任務就是通過學習獲得一個目標函數（Target Function）f, 將每個屬性集x映射到一個預先定義好的類標號y。 分類任務的輸入數據是紀錄的集合，每條記錄也稱為實例或者樣例。用元組(X,y)表示，其中，X 是屬性集合，y是一個特殊的屬性，指出樣例的類標號（也稱為分類屬性或者目標屬性）第6章 決策樹決策樹基本概念關于分類問題名稱體溫表皮覆蓋胎生水生動物飛行動物有腿冬眠類標號人類恒溫

2、毛發(fā)是否否是否哺乳動物海龜冷血鱗片否半否是否爬行類鴿子恒溫羽毛否否是是否鳥類鯨恒溫毛發(fā)是是否否否哺乳類Xy分類與回歸分類目標屬性y是離散的，回歸目標屬性y是連續(xù)的第6章 決策樹決策樹基本概念解決分類問題的一般方法 分類技術是一種根據輸入數據集建立分類模型的系統(tǒng)方法。分類技術一般是用一種學習算法確定分類模型，該模型可以很好地擬合輸入數據中類標號和屬性集之間的聯系。學習算法得到的模型不僅要很好擬合輸入數據，還要能夠正確地預測未知樣本的類標號。因此，訓練算法的主要目標就是要建立具有很好的泛化能力模型，即建立能夠準確地預測未知樣本類標號的模型。 分類方法的實例包括：決策樹分類法、基于規(guī)則的分類法、神經

3、網絡、支持向量級、樸素貝葉斯分類方法等。第6章 決策樹決策樹基本概念解決分類問題的一般方法 通過以上對分類問題一般方法的描述，可以看出分類問題一般包括兩個步驟： 1、模型構建（歸納） 通過對訓練集合的歸納，建立分類模型。 2、預測應用（推論） 根據建立的分類模型，對測試集合進行測試。第6章 決策樹決策樹基本概念解決分類問題的一般方法TIDA1A2A3類1Y100LN2N125SN3Y400LY4N415MN學習算法學習模型模型應用模型TIDA1A2A3類1Y100L？2N125S？3Y400L？4N415M？訓練集（類標號已知）檢驗集（類標號未知）歸納推論第6章 決策樹決策樹基本概念有指導的學

4、習與無指導的學習(有監(jiān)督學習與無監(jiān)督學習)有指導的學習（supervised learning 一般用于分類） 模型的學習在被告知每個訓練樣本屬于“那個類”的指導下進行。 新數據使用訓練數據集中得到的規(guī)則進行分類。無指導的學習（unsupervised learning 一般用于聚類） 每個訓練樣本的類編號是未知的，要學習的類集合和數量也可能是事先未知的。 通過一系列的度量、觀察來建立數據中的類編號或進行聚類第6章 決策樹決策樹基本概念半監(jiān)督學習（ semi-supervised learning ） 傳統(tǒng)的機器學習技術需要使用大量有標記訓練樣本進行學習，但是在很多真實應用中，獲取大量有標記訓

5、練樣本相當困難，但是很容易獲得大量未標記訓練樣本。半監(jiān)督學習致力于利用未標記樣本來提高學習性能。 半監(jiān)督學習主要有三種學習方法： 自訓練； 協(xié)同訓練； Co-EM算法第6章 決策樹決策樹基本概念半監(jiān)督學習（ semi-supervised learning ）自訓練：先在較小的標識數據集上訓練得到初始分類器，然后 利用該分類器對未標識樣本進行分類。將分類置信度 較高的未標識數據作為新的訓練樣本，添加到原訓練 集中對模型進行更新。如此循環(huán)多次后，輸出得到的 分類器及其分類結果。特點：自訓練的方法通過將訓練得到的置信度高的未標識數據作為訓練樣本，添加到訓練集重復訓練的方法，增加了訓練集的數量，對未

6、標識數據的信息進行了很好的利用，提高了分類的性能。但要求分類器對未標識數據具有較高的分類精度。這點對于較為復雜的分類尤其重要。自訓練方法及特點第6章 決策樹半監(jiān)督學習（ semi-supervised learning ）協(xié)同訓練方法及特點 協(xié)同訓練是一種利用互補的分類器對未標識樣本特征空間進行探索的半監(jiān)督學習方法。 協(xié)同訓練利用分類器之間的相互訓練來提高分類性能?？梢詮浹a因一個分類器不準而對最終結果造成的影響。最終結果綜合了兩個分類器的結果得到。協(xié)同訓練結果一般要優(yōu)于自訓練。但也面臨未知數據分類精度對最終結果的影響問題。第6章 決策樹半監(jiān)督學習（ semi-supervised learni

7、ng ）Co-EM算法及特點 Co-EM算法是協(xié)同訓練的改進形式，它不是直接利用當前分類器對未標識樣本的分類，而利用分類后的后驗概率進行分類。 優(yōu)點在于對數據前幾輪中的預測標識可以通過后驗概率來改變。這樣在初始分類器準確率不高的情況下優(yōu)于協(xié)同訓練。但其合理性和收斂性沒有理論的保證。第6章 決策樹半監(jiān)督學習（ semi-supervised learning ）其它半監(jiān)督學習方法還包括： 生成式模型（generative models）; 最大化分離（maximizing separation）; 基于圖的方法（graph-based methods）.第6章 決策樹決策樹基本概念決策樹 決策樹

8、是一種典型的分類方法，首先對數據進行處理，利用歸納算法生成可讀的規(guī)則和決策樹，然后使用決策對新數據進行分析。本質上決策樹是通過一系列規(guī)則對數據進行分類的過程。第6章 決策樹決策樹基本概念決策樹的優(yōu)點1、推理過程容易理解，決策推理過程可以表示成If Then形式；2、推理過程完全依賴于屬性變量的取值特點；3、可自動忽略目標變量沒有貢獻的屬性變量，也為判斷屬性 變量的重要性，減少變量的數目提供參考。第6章 決策樹決策樹基本概念關于歸納學習(1) 決策樹技術發(fā)現數據模式和規(guī)則的核心是歸納算法。 歸納是從特殊到一般的過程。歸納推理從若干個事實中表征出的特征、特性和屬性中，通過比較、總結、概括而得出一個

9、規(guī)律性的結論。 歸納推理試圖從對象的一部分或整體的特定的觀察中獲得一個完備且正確的描述。即從特殊事實到普遍性規(guī)律的結論。歸納對于認識的發(fā)展和完善具有重要的意義。人類知識的增長主要來源于歸納學習。第6章 決策樹決策樹基本概念關于歸納學習(2) 歸納學習的過程就是尋找一般化描述的過程。這種一般性描述能夠解釋給定的輸入數據，并可以用來預測新的數據。 銳角三角形內角和等于180度； 鈍角三角形內角和等于180度； 三角形內角和 直角三角形內角和等于180度； 等于180度 已知三角形ABC，A角等于76度，B角等于89度，則其C角等于15度 歸納學習由于依賴于檢驗數據，因此又稱為檢驗學習。歸納學習存在

10、一個基本的假設： 任一假設如果能夠在足夠大的訓練樣本集中很好的逼近目標函數，則它也能在未見樣本中很好地逼近目標函數。該假定是歸納學習的有效性的前提條件。第6章 決策樹決策樹基本概念關于歸納學習(3)第6章 決策樹決策樹基本概念關于歸納學習(4) 歸納過程就是在描述空間中進行搜索的過程。歸納可分為自頂向下，自底向上和雙向搜索三種方式。 自底向上法一次處理一個輸入對象。將描述逐步一般化。直到最終的一般化描述。 自頂向下法對可能的一般性描述集進行搜索，試圖找到一些滿足一定要求的最優(yōu)的描述。第6章 決策樹決策樹基本概念從機器學習看分類及歸納推理等問題（1） 從特殊的訓練樣例中歸納出一般函數是機器學習的

11、中心問題；從訓練樣例中進行學習通常被視為歸納推理。每個例子都是一個對偶（序偶）（x, f(x)），對每個輸入的x，都有確定的輸出f(x)。 學習過程將產生對目標函數f的不同逼近。F的每一個逼近都叫做一個假設。假設需要以某種形式表示。例如，y=ax+b。通過調整假設的表示，學習過程將產生出假設的不同變形。在表示中通常需要修改參數（如a, b）。 第6章 決策樹決策樹基本概念從機器學習看分類及歸納推理等問題（2） 從這些不同的變形中選擇最佳的假設（或者說權值集合）。一般方法如定義為使訓練值與假設值 預測出的值之間的誤差平方和E最小為最佳。 學習是在假設空間上的一個搜索。概念學習也可以看作是一個搜索

12、問題的過程。它在預定義的假設空間中搜索假設，使其與訓練樣例有最佳的擬合度。多數情況下，為了高效地搜索，可以利用假設空間中一種自然形成的結構，即一般到特殊的偏序關系。 第6章 決策樹決策樹基本概念從機器學習看分類及歸納推理等問題（3） 分類模型的性能根據模型正確和錯誤預測也可以根據的檢驗記錄計數進行評估。這些計數存儲在混淆矩陣（Confusion Matrix）的表格中，二元分類問題混淆矩陣如下：實際的類類1f11類0f01f10f00類1類0預測的類準確率=正確的預測數/預測總數=（f11+f00）/(f11+f01+f10+f00)差錯率=錯誤的預測數/預測總數=（f10+f01）/(f11

13、+f01+f10+f00)第6章 決策樹決策樹基本概念從機器學習看分類及歸納推理等問題（4）混淆矩陣一般可以用于衡量分類器的精度。例如 有150個數據，分3類，每類50個數據。 分類結果的混淆矩陣如下類1類2類3類14352類22453類30149含義：第1行表示類1有43個分類是正確的，5個錯分為類2, 2個錯分為類3。其分類精度為.43/50.其余類同上例的數據來自 UCI Machine Learning Repository中的German Credit Dataset可以免費獲取。歸納學習假設 機器學習的任務是在整個實例集合X上確定與目標概念c相同的假設 。一般H表示所有可能假設。H

14、中每個假設h表示X上定義的布爾函數。由于對c僅有的信息只是它在訓練樣例上的值，因此歸納學習最多只能保證輸出的假設能與訓練樣例相擬合。若沒有更多的信息，只能假定對于未見實例最好的假設就是訓練數據最佳擬合的假設。 定義 歸納學習假設：任一假設如果在足夠大的訓練樣例中很好地逼近目標函數，則它也能在未見實例中很好地逼近目標函數。（Function Approximation）。 第6章 決策樹決策樹基本概念從機器學習看分類及歸納推理等問題（4）主要內容決策樹基本概念決策樹算法決策樹研究問題主要參考文獻第6章 決策樹決策樹算法與決策樹相關的重要算法1、Hunt,Marin和Stone 于1966年研制的

15、CLS學習系統(tǒng)，用于學習單個概 念。2、1979年, J.R. Quinlan 給出ID3算法，并在1983年和1986年對ID3 進行了總結和簡化，使其成為決策樹學習算法的典型。3、Schlimmer 和Fisher 于1986年對ID3進行改造，在每個可能的決策樹節(jié)點創(chuàng)建緩沖區(qū)，使決策樹可以遞增式生成，得到ID4算法。4、1988年，Utgoff 在ID4基礎上提出了ID5學習算法，進一步提高了效率。5、1993年，Quinlan 進一步發(fā)展了ID3算法，改進成C4.5算法。6、另一類決策樹算法為CART，與C4.5不同的是，CART的決策樹由二元邏輯問題生成，每個樹節(jié)點只有兩個分枝，分別

16、包括學習實例的正例與反例。CLS, ID3，C4.5，CART第6章 決策樹決策樹算法計數年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買假定公司收集了左表數據，那么對于任意給定的客人（測試樣例），你能幫助公司將這位客人歸類嗎？即：你能預測這位客人是屬于“買”計算機的那一類，還是屬于“不買”計算機的那一類？又：你需要多少有關這位客人的信息才能回答這個問題？決策樹的用途第6章 決策樹計數年

17、齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買誰在買計算機？年齡？學生？信譽？買青中老否是優(yōu)良不買買買不買決策樹的用途決策樹算法第6章 決策樹計數年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買

18、1 老中否優(yōu)買誰在買計算機？年齡？學生？信譽？買青中老否是優(yōu)良不買買買不買決策樹的用途決策樹算法第6章 決策樹決策樹算法決策樹的表示決策樹的基本組成部分：決策結點、分支和葉子。年齡？學生？信譽？買青中老否是優(yōu)良不買買買不買決策樹中最上面的結點稱為根結點。是整個決策樹的開始。每個分支是一個新的決策結點，或者是樹的葉子。每個決策結點代表一個問題或者決策.通常對應待分類對象的屬性。每個葉結點代表一種可能的分類結果 在沿著決策樹從上到下的遍歷過程中，在每個結點都有一個測試。對每個結點上問題的不同測試輸出導致不同的分枝，最后會達到一個葉子結點。這一過程就是利用決策樹進行分類的過程，利用若干個變量來判斷屬

19、性的類別第6章 決策樹決策樹算法CLS（Concept Learning System）算法 CLS算法是早期的決策樹學習算法。它是許多決策樹學習算法的基礎。 CLS基本思想 從一棵空決策樹開始，選擇某一屬性（分類屬性）作為測試屬性。該測試屬性對應決策樹中的決策結點。根據該屬性的值的不同，可將訓練樣本分成相應的子集，如果該子集為空，或該子集中的樣本屬于同一個類，則該子集為葉結點，否則該子集對應于決策樹的內部結點，即測試結點，需要選擇一個新的分類屬性對該子集進行劃分，直到所有的子集都為空或者屬于同一類。第6章 決策樹人員眼睛顏色頭發(fā)顏色所屬人種1黑色黑色黃種人2藍色金色白種人3灰色金色白種人4藍

20、色紅色白種人5灰色紅色白種人6黑色金色混血7灰色黑色混血8藍色黑色混血決策樹算法CLS算法第6章 決策樹人員眼睛顏色頭發(fā)顏色所屬人種1黑色黑色黃種人2藍色金色白種人3灰色金色白種人4藍色紅色白種人5灰色紅色白種人6黑色金色混血7灰色黑色混血8藍色黑色混血決策樹算法CLS算法-決策樹的構建眼睛顏色1，62，4，83，5，7黑色蘭色灰色不屬于同一類，非葉結點第6章 決策樹眼睛顏色頭發(fā)顏色頭發(fā)顏色頭發(fā)顏色黑色蘭色灰色決策樹算法CLS算法黃種人1混血6白種人2白種人4混血8白種人3白種人5混血7黑色金色金色紅色黑色金色紅色黑色第6章 決策樹決策樹算法CLS算法1 生成一顆空決策樹和一張訓練樣本屬性集;

21、2 若訓練樣本集T 中所有的樣本都屬于同一類, 則生成結點T , 并終止學習算法;否則3 根據某種策略從訓練樣本屬性表中選擇屬性 A 作為測試屬性, 生成測試結點A 4 若A的取值為v1,v2,vm, 則根據A 的取值的 不同,將T 劃分成 m個子集T1,T2,Tm;5 從訓練樣本屬性表中刪除屬性A;6 轉步驟2, 對每個子集遞歸調用CLS;第6章 決策樹CLS算法問題在步驟3中，根據某種策略從訓練樣本屬性表中選擇屬性A作為測試屬性。沒有規(guī)定采用何種測試屬性。實踐表明，測試屬性集的組成以及測試屬性的先后對決策樹的學習具有舉足輕重的影響。舉例加以說明，下表為調查學生膳食結構和缺鈣情況的關系，其中

22、1表示包含食物，0表示不包含決策樹算法第6章 決策樹CLS算法問題決策樹算法學生雞肉豬肉牛肉羊肉魚肉雞蛋青菜番茄牛奶健康情況1011010101不缺鈣2000011111不缺鈣3111110100缺鈣4110011001不缺鈣5100111000缺鈣6111001010缺鈣7010001111不缺鈣8010001111缺鈣9010001111不缺鈣10101111011不缺鈣學生膳食結構和缺鈣調查表第6章 決策樹CLS算法問題決策樹算法采用不同的測試屬性及其先后順序將會生成不同的決策樹雞肉豬肉豬肉牛肉牛肉牛肉不缺鈣（2）缺鈣（3，6）不缺鈣（4）不缺鈣（10）缺鈣（5）不缺鈣（1）魚肉缺鈣（5

23、）不缺鈣（7，9）是否是否否否否否否是是是是是第6章 決策樹牛奶不缺鈣（1，2，4，7，9，10）缺鈣（3，5，6，8）CLS算法問題決策樹算法 在上例中，顯然生成的兩種決策樹的復雜性和分類意義相差很大由此可見，選擇測試屬性是決策樹學習算法中需要研究的重要課題。第6章 決策樹ID3 決策樹算法 ID3算法主要針對屬性選擇問題。是決策樹學習方法中最具影響和最為典型的算法。 該方法使用信息增益度選擇測試屬性。 當獲取信息時，將不確定的內容轉為確定的內容，因此信息伴著不確定性。 從直覺上講，小概率事件比大概率事件包含的信息量大。如果某件事情是“百年一見”則肯定比“習以為常”的事件包含的信息量大。 如

24、何度量信息量的大??？第6章 決策樹決策樹算法IDAgeHas-jobOwn_houseCredit_ratingClass1YoungFalseFalseFairNo2YoungFalseFalseGoodNo3YoungTrueFalseGoodYes4YoungTrueTrueFairYes5YoungFalseFalseFairNo6MiddleFalseFalseFairNo7MiddleFalseFalseGoodNo8MiddleTrueTrueGoodYes9MiddleFalseTrueExcellentYes10MiddleFalseTrueExcellentYes11Old

25、FalseTrueExcellentYes12OldFalseTrueGoodYes13OldTrueFalseGoodYes14OldTrueFalseExcellentYes15OldFalseFalsefairno例申請貸款的數據集合第6章 決策樹決策樹算法上例可能的兩種根節(jié)點Age？youngmiddleoldNo:3Yes:2No:2Yes:3No:4Yes:1Own_house？truefalseNo:0Yes:6No:6Yes:3上例若采用Age或Own_house作為根節(jié)點。根節(jié)點可能值構成了根節(jié)點分支。對于每個分支，列出該分支上每個類（Yes或No）的訓練數據的數目。(b)顯

26、然要比(a)好。因為從分類預測的觀點來看，(b)比(a)犯錯誤的可能性要小。（a）（b）第6章 決策樹決策樹算法Age？youngmiddleoldNo:3Yes:2No:2Yes:3No:1Yes:4Own_house？truefalseNo:0Yes:6No:6Yes:3（a）（b）選擇(b)時，當Own_house=true時，每個樣例都分配到y(tǒng)se類中。在Own_house=false時如果將它們都歸類到No類中，則在整個分類中會有三個分類是錯誤的。選擇(a)時，如果我們選擇按照多數服從少數的方法，則會產生5個錯誤的分類。說明，節(jié)點的選擇對結果是有影響的。第6章 決策樹ID3 信息量大

27、小的度量決策樹算法Shannon1948年提出的信息論理論。事件ai的信息量I（ ai ）可如下度量：其中p(ai)表示事件ai發(fā)生的概率。假設有n個互不相容的事件a1,a2,a3,.,an,它們中有且僅有一個發(fā)生，則其平均的信息量可如下度量：第6章 決策樹ID3 信息量大小的度量決策樹算法上式，對數底數可以為任何數，不同的取值對應了熵的不同單位。通常取2，并規(guī)定當p(ai)=0時 =0公式1第6章 決策樹決策樹算法例：假設有一個數據集合D，其中只有兩個類，一個是正例類，一個是負例類計算D中正例類和負例類在三種不同的組分下熵的變化情況。（1）D中包含有50%的正例和50%的負例。 Entrop

28、y(D)=-0.5*log20.5-0.5*log20.5=1（2）D中包含有20%的正例和80%的負例。 Entropy(D)=-0.2*log20.2-0.8*log20.8=0.722（3）D中包含有100%的正例和0%的負例。 Entropy(D)=-1*log21-0*log20=0 從上述的結果可以看到一個趨勢，當數據變得越來越純凈時，熵的值變得越來越小。事實上可以證明，當正例（0.5）,反例（0.5）時，熵取最大值。當D 中所有數據都只屬于一個類時，熵得到最小值。 顯然，上可以作為數據純凈度或混亂度的衡量指標。這正是決策樹學習中需要的。在決策樹分類中，假設S是訓練樣本集合，|S|

29、是訓練樣本數，樣本劃分為n個不同的類C1,C2,.Cn，這些類的大小分別標記為|C1|，|C2|，.,|Cn|。則任意樣本S屬于類Ci的概率為：第6章 決策樹ID3 信息量大小的度量決策樹算法Entropy（S，A）=（|Sv|/|S|）* Entropy（Sv）公式2 是屬性A的所有可能的值v,Sv是屬性A有v值的S子集|Sv|是Sv 中元素的個數；|S|是S中元素的個數。第6章 決策樹ID3 信息量大小的度量決策樹算法Gain（S，A）是屬性A在集合S上的信息增益Gain（S，A）= Entropy（S） -Entropy（S，A） 公式3Gain（S，A）越大，說明選擇測試屬性對分類提供

30、的信息越多第6章 決策樹計數年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買決策樹算法第6章 決策樹計數年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買第1步計算決策屬性的熵決策屬

31、性“買計算機？”。該屬性分兩類：買/不買S1(買)=641 S2（不買）= 383S=S1+S2=1024P1=641/1024=0.6260P2=383/1024=0.3740I(S1,S2)=I(641,383) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9537決策樹算法第6章 決策樹計數年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)

32、買第2步計算條件屬性的熵條件屬性共有4個。分別是年齡、收入、學生、信譽。分別計算不同屬性的信息增益。決策樹算法第6章 決策樹計數年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買第2-1步計算年齡的熵年齡共分三個組： 青年、中年、老年青年買與不買比例為128/256S1(買)=128 S2（不買）= 256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(

33、128,256) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9183決策樹算法第6章 決策樹計數年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買第2-2步計算年齡的熵年齡共分三個組： 青年、中年、老年中年買與不買比例為256/0S1(買)=256 S2（不買）= 0S=S1+S2=256P1=256/256P2=0/256I(S1,S2)=

34、I(256，0) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0決策樹算法第6章 決策樹計數年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買第2-3步計算年齡的熵年齡共分三個組： 青年、中年、老年老年買與不買比例為125/127S1(買)=125 S2（不買）=127S=S1+S2=252P1=125/252P2=127/252I(S1,S2)=

35、I(125，127) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9157決策樹算法第6章 決策樹計數年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買第2-4步計算年齡的熵年齡共分三個組： 青年、中年、老年所占比例青年組 384/1024=0.375中年組 256/1024=0.25老年組 384/1024=0.375計算年齡的平均信息期望E

36、（年齡）=0.375*0.9183+ 0.25*0+ 0.375*0.9157 =0.6877G（年齡信息增益） =0.9537-0.6877 =0.2660 （1）決策樹算法第6章 決策樹計數年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買第3步計算收入的熵收入共分三個組： 高、中、低E（收入）=0.9361收入信息增益=0.9537-0.9361 =0.0176 (2)決策樹算法第6

37、章 決策樹計數年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買第4步計算學生的熵學生共分二個組： 學生、非學生E（學生）=0.7811年齡信息增益=0.9537-0.7811 =0.1726 （3）決策樹算法第6章 決策樹計數年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低

38、是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買第5步計算信譽的熵信譽分二個組： 良好，優(yōu)秀E（信譽）= 0.9048信譽信息增益=0.9537-0.9048 =0.0453 （4）決策樹算法第6章 決策樹計數年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買第6步計算選擇節(jié)點 年齡信息增益=0.9537-0.6877 =0.2660 （1）收

39、入信息增益=0.9537-0.9361 =0.0176 （2）學生信息增益=0.9537-0.7811 =0.1726 （3）信譽信息增益=0.9537-0.9048 =0.0453 （4）決策樹算法第6章 決策樹計數年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優(yōu)不買128青中否良不買64青低是良買64青中是優(yōu)買年齡青年中年老年買/不買買買/不買葉子決策樹算法第6章 決策樹計數年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優(yōu)不買128青中否良不買64青低是良買64青中是優(yōu)買青年買與不買比例為128/256S1(買)=128 S2（不買）= 256S=S1+S2=384

40、P1=128/384P2=256/384I(S1,S2)=I(128,256) =-P1Log2P1-P2Log2P2 =-(P1Log2P1+P2Log2P2) =0.9183決策樹算法第6章 決策樹計數年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優(yōu)不買128青中否良不買64青低是良買64青中是優(yōu)買如果選擇收入作為節(jié)點分高、中、低平均信息期望（加權總和）： E(收入）= 0.3333 * 0 + 0.5 * 0.9183 + 0.1667 * 0 = 0.4592Gain(收入) = I(128, 256) - E(收入)=0.9183 0.4592 = 0.4591I(0,1

41、28)=0 比例: 128/384=0.3333I(64,128)=0.9183 比例: 192/384=0.5I(64,0)=0比例: 64/384=0.1667 注意決策樹算法第6章 決策樹計數年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1 老中否優(yōu)買年齡青年中年老年學生買信譽葉子否是優(yōu)良買不買買/不買買葉子葉子葉子決策樹算法第6章 決策樹ID3 決策樹建立算法1 決定分類屬性；2 對目前的數

42、據表，建立一個節(jié)點N3 如果數據庫中的數據都屬于同一個類，N就是樹葉，在樹葉上 標出所屬的類4 如果數據表中沒有其他屬性可以考慮，則N也是樹葉，按照少 數服從多數的原則在樹葉上標出所屬類別5 否則，根據平均信息期望值E或GAIN值選出一個最佳屬性作 為節(jié)點N的測試屬性6 節(jié)點屬性選定后，對于該屬性中的每個值： 從N生成一個分支，并將數據表中與該分支有關的數據收集形 成分支節(jié)點的數據表，在表中刪除節(jié)點屬性那一欄 如果分支數據表非空，則運用以上算法從該節(jié)點建立子樹。決策樹算法第6章 決策樹決策樹算法IDAgeHas-jobOwn_houseCredit_ratingClass1YoungFalse

43、FalseFairNo2YoungFalseFalseGoodNo3YoungTrueFalseGoodYes4YoungTrueTrueFairYes5YoungFalseFalseFairNo6MiddleFalseFalseFairNo7MiddleFalseFalseGoodNo8MiddleTrueTrueGoodYes9MiddleFalseTrueExcellentYes10MiddleFalseTrueExcellentYes11OldFalseTrueExcellentYes12OldFalseTrueGoodYes13OldTrueFalseGoodYes14OldTrue

44、FalseExcellentYes15OldFalseFalsefairno例申請貸款的數據集合Age？youngmiddleoldNo:3Yes:2No:2Yes:3No:4Yes:1Own_house？truefalseNo:0Yes:6No:6Yes:3（a）（b）第6章 決策樹決策樹算法第6章 決策樹決策樹算法(1)首先計算D的熵 D有6個否類訓練樣例和9個是類訓練樣例，可計算如下： entropy(D)= - 6/15*log26/15 - 9/15*log29/15 = 0.971(2)嘗試采用age屬性劃分數據，可以劃分為三類， D1(age=young), D2(age=mid

45、de), D3(age=old) entropyage(D) = -5/15*entropy(D1)-5/15*entropy(D2)-5/15*entropy(D3) =5/15*0.971+5/15*0.971+5/15*0.722=0.888 -3/5*log23/5-2/5*log22/5=0.971 -1/5*log21/5-4/5*log24/5 =0.722(3) 嘗試采用own_house屬性將數據劃分為兩個子集 entropyown_house(D)=-6/15*entropy(D1)-9/15*entropy(D2) =6/15*0+9/15*0.918=0.551 ent

46、ropy(D1)=-0/6*log20/6-6/6*log26/6=0 entropy(D2)=-6/9*log26/9-3/9*log23/9=0.918第6章 決策樹決策樹算法(4) 分別計算采用has_job，Credit_rating屬性的熵值 entropyhas_job(D)=0.647 entropyCredit_rating(D)=0.608(5)各個屬性的信息增益 gain(D,Age)=0.971-0.888=0.083 gain(D,Own_house)=0.971-0.551=0.420 gain(D,Has_job)=0.971-0.647=0.324 gain(D,

47、Credit_rating)=0.971-0.608=0.363(6).第6章 決策樹決策樹的數據準備姓名年齡收入學生信譽電話地址郵編買計算機張三234000是良281-322-03282714 Ave. M77388買李四342800否優(yōu)713-239-78305606 Holly Cr78766買王二701900否優(yōu)281-242-32222000 Bell Blvd.70244不買趙五18900是良281-550-0544100 Main Street70244買劉蘭342500否優(yōu)713-239-7430606 Holly Ct78566買楊俊278900否優(yōu)281-355-79902

48、33 Rice Blvd.70388不買張毅389500否優(yōu)281-556-0544399 Sugar Rd.78244買。原始表決策樹算法第6章 決策樹計數年齡收入學生信譽歸類：買計算機？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買。整理后的數據表決策樹的數據準備Data cleaning刪除/減少noise， 補填missing valuesData transformation數據標準化（data normalization）數據歸納（generalize data to higher-leve

49、l concepts using concept hierarchies）例如：年齡歸納為老、中、青三類控制每個屬性的可能值不超過七種 （最好不超過五種）Relevance analysis對于與問題無關的屬性：刪對于屬性的可能值大于七種 又不能歸納的屬性：刪決策樹算法第6章 決策樹決策樹的數據準備決策樹算法處理連續(xù)屬性值 決策樹算法比較適合處理離散數值的屬性。實際應用中屬性是連續(xù)的或者離散的情況都比較常見。 在應用連續(xù)屬性值時，在一個樹結點可以將屬性Ai的值劃分為幾個區(qū)間。然后信息增益的計算就可以采用和離散值處理一樣的方法。原則上可以將Ai的屬性劃分為任意數目的空間。C4.5中采用的是二元分

50、割（Binary Split）。需要找出一個合適的分割閾值。 參考C4.5算法 Top 10 algorithms in data mining Knowledge Information System 2008 14:137第6章 決策樹決策樹算法ID3算法小結 ID3算法是一種經典的決策樹學習算法，由Quinlan于1979年提出。ID3算法的基本思想是，以信息熵為度量，用于決策樹節(jié)點的屬性選擇，每次優(yōu)先選取信息量最多的屬性，亦即能使熵值變?yōu)樽钚〉膶傩?，以構造一顆熵值下降最快的決策樹，到葉子節(jié)點處的熵值為0。此時，每個葉子節(jié)點對應的實例集中的實例屬于同一類。第6章 決策樹決策樹算法ID3算

51、法實際應用-在電信行業(yè)應用實例（1） 通過ID3算法來實現客戶流失的預警分析，找出客戶流失的特征，以幫助電信公司有針對性地改善客戶關系，避免客戶流失 利用決策樹方法進行數據挖掘，一般有如下步驟：數據預處理、決策樹挖掘操作，模式評估和應用。 電信運營商的客戶流失有三方面的含義：一是指客戶從一個電信運營商轉網到其他電信運營商，這是流失分析的重點。二是指客戶月平均消費量降低，從高價值客戶成為低價值客戶。三、指客戶自然流失和被動流失。 在客戶流失分析中有兩個核心變量：財務原因非財務原因、主動流失被動流失。 客戶流失可以相應分為四種類型：其中非財務原因主動流失的客戶往往是高價值的客戶。他們會正常支付服務

52、費用，并容易對市場活動有所響應。這種客戶是電信企業(yè)真正需要保住的客戶。 第6章 決策樹決策樹算法ID3算法實際應用-在電信行業(yè)應用實例（2）數據預處理 數據挖掘的處理對象是大量的數據，這些數據一般存儲在數據庫系統(tǒng)中（該用戶相關數據存儲在其CRM中），是長期積累的結果。但往往不適合直接挖掘，需要做數據的預處理工作，一般包括數據的選擇(選擇相關的數據)、凈化(消除冗余數據)、轉換、歸約等。數據預處理工作準備是否充分，對于挖掘算法的效率乃至正確性都有關鍵性的影響。 該公司經過多年的電腦化管理，已有大量的客戶個人基本信息(文中簡稱為客戶信息表)。在客戶信息表中，有很多屬性，如姓名用戶號碼、用戶標識、用

53、戶身份證號碼(轉化為年齡)、在網時間（竣工時間）、地址、職業(yè)、用戶類別、客戶流失（用戶狀態(tài)）等等，數據準備時必須除掉表中一些不必要的屬性，一般可采用面向屬性的歸納等方法去掉不相關或弱相關屬性。 第6章 決策樹決策樹算法ID3算法實際應用-在電信行業(yè)應用實例（3）屬性刪除：將有大量不同取值且無概化操作符的屬性或者可用其它屬性來代替它的較高層概念的那些屬性刪除。比如客戶信息表中的用戶標識、身份證號碼等，它們的取值太多應將其刪除，得到表1。 表1 客戶信息表年齡學歷職業(yè)繳費方式在網時長費用變化率客戶流失58大學公務員托收1310%NO47高中工人營業(yè)廳繳費942%NO26研究生公務員充值卡263%Y

54、ES28大學公務員營業(yè)廳繳費52.91%NO32初中工人營業(yè)廳繳費32.3%NO42高中無業(yè)人員充值卡2100%YES68初中無業(yè)人員營業(yè)廳繳費92.3%NO第6章 決策樹決策樹算法ID3算法實際應用-在電信行業(yè)應用實例（4）屬性概化：用屬性概化閾值控制技術沿屬性概念分層上卷或下鉆進行概化。文化程度分為3類：W1初中以下(含初中)，W2高中(含中專)，W3大學(?？啤⒈究萍耙陨?；職業(yè)類別：按工作性質來分共分3類：Z1一Z3；繳費方式：托收：T1,營業(yè)廳繳費：T2,充值卡：T3。連續(xù)型屬性概化為區(qū)間值：表中年齡、費用變化率和在網時間為連續(xù)型數據，由于建立決策樹時，用離散型數據進行處理速度最快，

55、因此對連續(xù)型數據進行離散化處理，根據專家經驗和實際計算信息增益，在“在網時長”屬性中，通過檢測每個劃分，得到在閾值為5年時信息增益最大，從而確定最好的劃分是在5年處，則這個屬性的范圍就變?yōu)?：H1,H2。而在“年齡”屬性中，信息增益有兩個鋒值，分別在40和50處，因而該屬性的范圍變?yōu)?0-50即變?yōu)榍嗄?，中年，老年：N1,N2,N3；費用變化率：指（當月話費近3個月的平均話費）/近3個月的平均話費）0，F1:30%，F2：30%-99%, F3:100%變?yōu)镕1,F2,F3。 表2 轉化后的客戶信息表年齡學歷職業(yè)繳費方式開戶時間費用變化率客戶流失N3W3Z1T1H2F1NON2W2Z2T2H2

56、F2NON1W3Z1T3H1F2YESN1W3Z1T2H1F1NON1W1Z2T2H1F1NON2W2Z3T3H1F3YESN3W1Z3T1H2F1NO第6章 決策樹決策樹算法ID3算法實際應用-在電信行業(yè)應用實例（5）YESNO年 齡職 業(yè)YES繳費方式YESYESNOYSESNONO在網時長NOF1F2F3N1N2N3T1T2T3Z1Z2Z3H1H2費用變化率第6章 決策樹決策樹算法ID3算法實際應用-在電信行業(yè)應用實例（6） 在圖中，NO表示客戶不流失，YES表示客戶流失。從圖可以看出，客戶費用變化率為100%的客戶肯定已經流失；而費用變化率低于30%的客戶；即每月資費相對穩(wěn)定的客戶一般

57、不會流失，費用變化率在30%99%的客戶有可能流失，其中年齡在4050歲之間的客戶流失的可能性非常大，而年齡低于40歲的客戶，用充值卡繳費的客戶和在網時間較短的客戶容易流失；年齡較大的客戶，則工人容易流失。 主要內容決策樹基本概念決策樹算法決策樹研究問題主要參考文獻第6章 決策樹決策樹研究問題理想的決策樹有三種： (1)葉子結點數最少； (2)葉子結點深度最??； (3)葉子結點數最少且葉子結點深度最小。 然而，洪家榮等人已經證明了要找到這種最優(yōu)的決策樹是NP難題。因此，決策樹優(yōu)化的目的就是要找到盡可能趨向于最優(yōu)的決策樹。第6章 決策樹關于過渡擬合 上述的決策樹算法增長樹的每一個分支的深度，直到

58、恰好能對訓練樣例比較完美地分類。實際應用中，當數據中有噪聲或訓練樣例的數量太少以至于不能產生目標函數的有代表性的采樣時，該策略可能會遇到困難。 在以上情況發(fā)生時，這個簡單的算法產生的樹會過渡擬合訓練樣例（過渡擬合：Over Fitting）.決策樹研究問題關于過渡擬合第6章 決策樹 對于一個假設，當存在其它的假設對訓練樣例的擬合比它差，但事實上在實例的整個分布上（包含訓練集合以外的實例）表現得卻更好時，則稱該假設過度擬合訓練樣例。 過度擬合：給定一個假設空間H，一個假設hH，如果存在其它的假設h1 H ,使得在訓練樣例上h的錯誤率比h1小，但在整個實例發(fā)布上h1的錯誤率比h小，則稱假設h過度擬

59、合訓練數據 過度擬合產生的原因：噪聲，訓練樣例太小等決策樹研究問題關于過渡擬合第6章 決策樹 對學習算法是否成功的真正測試是看它對于訓練中未見到的數據的執(zhí)行性能。 訓練過程應該包含訓練樣本和驗證樣本。驗證樣本用于測試訓練后的性能。如果驗證結果差，則需要考慮采用不同的結構重新進行訓練，例如使用更大的樣本集，或者改變從連續(xù)值到離散值得數據轉換等。 通常應該建立一個驗證過程，在訓練最終完成后用來檢測訓練結果的泛化能力。決策樹研究問題關于過渡擬合第6章 決策樹分類模型的誤差一般可以將分類模型的誤差分為： 1、訓練誤差（Training Error）； 2、泛化誤差（Generalization Err

60、or）決策樹研究問題關于過渡擬合第6章 決策樹分類模型的誤差 訓練誤差是在訓練記錄上誤分類樣本比例； 泛化誤差是模型在未知記錄上的期望誤差； 一個好的模型不僅要能夠很好地擬合訓練數據，而且對未知樣本也要能夠準確地分類。 一個好的分類模型必須具有低的訓練誤差和泛化誤差。因為一個具有低訓練誤差的模型，其泛化誤差可能比具有較高訓練誤差的模型高。（訓練誤差低，泛化誤差高，稱為過渡擬合）決策樹研究問題關于過渡擬合第6章 決策樹模型過渡擬合的潛在因素（1）噪聲導致的過渡擬合； 錯誤的類別值/類標簽，屬性值等（2）缺乏代表性樣本所導致的過渡擬合 根據少量訓練記錄作出的分類決策模型容易受過渡擬合的 影響。由于