決策樹基本研究課件

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、包括學(xué)習(xí)實例的正例與反例。CLS, ID3，C4.5，CART第6章 決策樹決策樹算法計數(shù)年齡收入學(xué)生信譽(yù)歸類：買計算機(jī)？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)買假定公司收集了左表數(shù)據(jù)，那么對于任意給定的客人（測試樣例），你能幫助公司將這位客人歸類嗎？即：你能預(yù)測這位客人是屬于“買”計算機(jī)的那一類，還是屬于“不買”計算機(jī)的那一類？又：你需要多少有關(guān)這位客人的信息才能回答這個問題？決策樹的用途第6章 決策樹計數(shù)年

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

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

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

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

22、1表示包含食物，0表示不包含決策樹算法第6章 決策樹CLS算法問題決策樹算法學(xué)生雞肉豬肉牛肉羊肉魚肉雞蛋青菜番茄牛奶健康情況1011010101不缺鈣2000011111不缺鈣3111110100缺鈣4110011001不缺鈣5100111000缺鈣6111001010缺鈣7010001111不缺鈣8010001111缺鈣9010001111不缺鈣10101111011不缺鈣學(xué)生膳食結(jié)構(gòu)和缺鈣調(diào)查表第6章 決策樹CLS算法問題決策樹算法采用不同的測試屬性及其先后順序?qū)刹煌臎Q策樹雞肉豬肉豬肉牛肉牛肉牛肉不缺鈣（2）缺鈣（3，6）不缺鈣（4）不缺鈣（10）缺鈣（5）不缺鈣（1）魚肉缺鈣（5

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

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

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

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

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

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

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

30、的信息越多第6章 決策樹計數(shù)年齡收入學(xué)生信譽(yù)歸類：買計算機(jī)？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章 決策樹計數(shù)年齡收入學(xué)生信譽(yù)歸類：買計算機(jī)？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、性“買計算機(jī)？”。該屬性分兩類：買/不買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章 決策樹計數(shù)年齡收入學(xué)生信譽(yù)歸類：買計算機(jī)？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個。分別是年齡、收入、學(xué)生、信譽(yù)。分別計算不同屬性的信息增益。決策樹算法第6章 決策樹計數(shù)年齡收入學(xué)生信譽(yù)歸類：買計算機(jī)？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章 決策樹計數(shù)年齡收入學(xué)生信譽(yù)歸類：買計算機(jī)？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章 決策樹計數(shù)年齡收入學(xué)生信譽(yù)歸類：買計算機(jī)？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章 決策樹計數(shù)年齡收入學(xué)生信譽(yù)歸類：買計算機(jī)？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章 決策樹計數(shù)年齡收入學(xué)生信譽(yù)歸類：買計算機(jī)？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、章 決策樹計數(shù)年齡收入學(xué)生信譽(yù)歸類：買計算機(jī)？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步計算學(xué)生的熵學(xué)生共分二個組： 學(xué)生、非學(xué)生E（學(xué)生）=0.7811年齡信息增益=0.9537-0.7811 =0.1726 （3）決策樹算法第6章 決策樹計數(shù)年齡收入學(xué)生信譽(yù)歸類：買計算機(jī)？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ù)的熵信譽(yù)分二個組： 良好，優(yōu)秀E（信譽(yù)）= 0.9048信譽(yù)信息增益=0.9537-0.9048 =0.0453 （4）決策樹算法第6章 決策樹計數(shù)年齡收入學(xué)生信譽(yù)歸類：買計算機(jī)？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é)點(diǎn) 年齡信息增益=0.9537-0.6877 =0.2660 （1）收

39、入信息增益=0.9537-0.9361 =0.0176 （2）學(xué)生信息增益=0.9537-0.7811 =0.1726 （3）信譽(yù)信息增益=0.9537-0.9048 =0.0453 （4）決策樹算法第6章 決策樹計數(shù)年齡收入學(xué)生信譽(yù)歸類：買計算機(jī)？64青高否良不買64青高否優(yōu)不買128青中否良不買64青低是良買64青中是優(yōu)買年齡青年中年老年買/不買買買/不買葉子決策樹算法第6章 決策樹計數(shù)年齡收入學(xué)生信譽(yù)歸類：買計算機(jī)？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章 決策樹計數(shù)年齡收入學(xué)生信譽(yù)歸類：買計算機(jī)？64青高否良不買64青高否優(yōu)不買128青中否良不買64青低是良買64青中是優(yōu)買如果選擇收入作為節(jié)點(diǎn)分高、中、低平均信息期望（加權(quán)總和）： 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章 決策樹計數(shù)年齡收入學(xué)生信譽(yù)歸類：買計算機(jī)？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)買年齡青年中年老年學(xué)生買信譽(yù)葉子否是優(yōu)良買不買買/不買買葉子葉子葉子決策樹算法第6章 決策樹ID3 決策樹建立算法1 決定分類屬性；2 對目前的數(shù)

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

43、FalseFairNo2YoungFalseFalseGoodNo3YoungTrueFalseGoodYes4YoungTrueTrueFairYes5YoungFalseFalseFairNo6MiddleFalseFalseFairNo7MiddleFalseFalseGoodNo8MiddleTrueTrueGoodYes9MiddleFalseTrueExcellentYes10MiddleFalseTrueExcellentYes11OldFalseTrueExcellentYes12OldFalseTrueGoodYes13OldTrueFalseGoodYes14OldTrue

44、FalseExcellentYes15OldFalseFalsefairno例申請貸款的數(shù)據(jù)集合Age？youngmiddleoldNo:3Yes:2No:2Yes:3No:4Yes:1Own_house？truefalseNo:0Yes:6No:6Yes:3（a）（b）第6章 決策樹決策樹算法第6章 決策樹決策樹算法(1)首先計算D的熵 D有6個否類訓(xùn)練樣例和9個是類訓(xùn)練樣例，可計算如下： entropy(D)= - 6/15*log26/15 - 9/15*log29/15 = 0.971(2)嘗試采用age屬性劃分?jǐn)?shù)據(jù)，可以劃分為三類， 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屬性將數(shù)據(jù)劃分為兩個子集 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章 決策樹決策樹的數(shù)據(jù)準(zhǔn)備姓名年齡收入學(xué)生信譽(yù)電話地址郵編買計算機(jī)張三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章 決策樹計數(shù)年齡收入學(xué)生信譽(yù)歸類：買計算機(jī)？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買。整理后的數(shù)據(jù)表決策樹的數(shù)據(jù)準(zhǔn)備Data cleaning刪除/減少noise， 補(bǔ)填missing valuesData transformation數(shù)據(jù)標(biāo)準(zhǔn)化（data normalization）數(shù)據(jù)歸納（generalize data to higher-leve

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

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

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

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

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

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

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

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

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

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

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

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