決策樹C算法總結(jié)課件

1、C4.5示例 數(shù)據(jù)：weka中的weather數(shù)據(jù)（字符型、數(shù)值型）outlook,temperature,humidity,windy,playsunny,hot,high,FALSE,nosunny,hot,high,TRUE,noovercast,hot,high,FALSE,yesrainy,mild,high,FALSE,yesrainy,cool,normal,FALSE,yesrainy,cool,normal,TRUE,noovercast,cool,normal,TRUE,yessunny,mild,high,FALSE,nosunny,cool,normal,FALSE,y

2、esrainy,mild,normal,FALSE,yessunny,mild,normal,TRUE,yesovercast,mild,high,TRUE,yesovercast,hot,normal,FALSE,yesrainy,mild,high,TRUE,nooutlook,temperature,humidity,windy,playsunny,85,85,FALSE,nosunny,80,90,TRUE,noovercast,83,86,FALSE,yesrainy,70,96,FALSE,yesrainy,68,80,FALSE,yesrainy,65,70,TRUE,noove

3、rcast,64,65,TRUE,yessunny,72,95,FALSE,nosunny,69,70,FALSE,yesrainy,75,80,FALSE,yessunny,75,70,TRUE,yesovercast,72,90,TRUE,yesovercast,81,75,FALSE,yesrainy,71,91,TRUE,no決策樹C算法總結(jié)C4.5示例 SPSS Clementine C5.0決策樹C算法總結(jié)C4.5示例 Weka J48決策樹C算法總結(jié)C4.5算法簡介決策樹方法：決策樹方法：利用一定的訓(xùn)練樣本，從數(shù)據(jù)中學(xué)習(xí)出決策規(guī)則自動構(gòu)造出決策樹。C4.5算法算法: C4. 5:

4、 programs for machine learningJR Quinlan, 1993分類決策樹算法,其核心算法是ID3算法。目前應(yīng)用在臨床決策、生產(chǎn)制造、文檔分析、生物信息學(xué)、空間數(shù)據(jù)建模等領(lǐng)域。算法的輸入是帶類標(biāo)的數(shù)據(jù)，輸出是樹形的決策規(guī)則。ID3算法算法：Induction of decision treesJR Quinlan - Machine learning, 1986 ID3算法的原型來自于Hunt等人提出的概念學(xué)習(xí)系統(tǒng)（concept learning system, CLS）。決策樹C算法總結(jié)C4.5算法簡介C4.5比比ID3的的改進改進:1) 用信息增益率來選擇屬性

5、，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足；2) 在樹構(gòu)造過程中進行剪枝；3) 能夠完成對連續(xù)屬性的離散化處理；4) 能夠?qū)Σ煌暾麛?shù)據(jù)進行處理。C4.5算法優(yōu)點算法優(yōu)點：產(chǎn)生的分類規(guī)則易于理解，準(zhǔn)確率較高。C4.5算法算法缺點：缺點：在構(gòu)造樹的過程中，需要對數(shù)據(jù)集進行多次的順序掃描和排序，因而導(dǎo)致算法的低效。決策樹C算法總結(jié)決策樹算法發(fā)展二級存儲二級存儲:針對不能完全放入內(nèi)存的數(shù)據(jù)集，在確保分類器算法效能的前提下，要做到數(shù)據(jù)集掃描遍數(shù)的極小化。BOAT算法（ BOAT-optimistic decision tree constructionJ Gehrke, V Ganti, R

6、 Ramakrishnan - SIGMOD , 1999）使用抽樣、融合、完整掃描三步得到最終的分類器。RainForest框架（Rainforest-a framework for fast decision tree construction of large datasetsJ Gehrke, R Ramakrishnan, V Ganti - VLDB, 1998）實現(xiàn)了多種具體的決策樹構(gòu)建方法，適用于大規(guī)模數(shù)據(jù)集的處理。其他基于二級存儲設(shè)備的算法還有SLIQ（ SLIQ: A fast scalable classifier for data mining M Mehta, R A

7、grawal, J Rissanen - Advances in Database Technology , 1996 ），SPRINT（SPRINT: A scalable parallel classi er for data miningJ Shafer, R Agrawal, M Mehta - Proc. 1996 Int. Conf. Very Large Data , 1996 - Citeseer），PUBLIC（ PUBLIC: A decision tree classifier that integrates building and pruningR Rastogi,

8、K Shim - VLDB, 1998 - cs.sfu.ca）等。斜決策樹：斜決策樹：斜決策樹適用于處理連續(xù)型數(shù)據(jù)，決策準(zhǔn)則使用屬性的線性組合。采用屬性的線性組合策略的一個典型的決策樹分類器是OC1（A system for induction of oblique decision treesSK Murthy, S Kasif, S Salzberg - arXiv preprint cs/9408103, 1994 - ）。集成方法：集成方法：裝袋法和推舉法。（Popular ensemble methods: An empirical studyR Maclin,

9、D Opitz - arXiv preprint arXiv:1106.0257, 2011 - 決策樹C算法總結(jié)算法流程：1）選擇哪個屬性進行節(jié)點分裂？2）何時停止樹生長？3）怎么處理連續(xù)型屬性？4）怎么處理缺失值？5）怎么處理過擬合問題？問題：1）選擇節(jié)點分裂屬性2）建立新節(jié)點，劃分數(shù)據(jù)集3）判斷節(jié)點是否到生長停止條件，如果是，終止生長，如果不是，轉(zhuǎn)到1）決策樹C算法總結(jié)決策樹C算法總結(jié)選擇節(jié)點分裂屬性的問題 熵（Entropy）：我們把一個事件的不確定程度叫做“熵”，熵越大表明這個事件的結(jié)果越難以預(yù)測，同時事件的發(fā)生將給我們帶來越多的信息。增益（Information

10、Gain）：在信息增益中，衡量標(biāo)準(zhǔn)是看特征能夠為分類系統(tǒng)帶來多少信息，帶來的信息越多，該特征越重要。對一個特征而言，系統(tǒng)有它和沒它時信息量將發(fā)生變化，而前后信息量的差值就是這個特征給系統(tǒng)帶來的信息量。所謂信息量，就是熵。系統(tǒng)原先的熵是H(X)，在條件Y已知的情況下系統(tǒng)的熵（條件熵）為H(X|Y)，信息增益就是這兩個熵的差值。決策樹C算法總結(jié)outlooktemperaturehumiditywindyplaysunnyhothighFALSEnosunnyhothighTRUEnoovercasthothighFALSEyesrainymildhighFALSEyesrainycoolnorm

11、alFALSEyesrainycoolnormalTRUEnoovercastcoolnormalTRUEyessunnymildhighFALSEnosunnycoolnormalFALSEyesrainymildnormalFALSEyessunnymildnormalTRUEyesovercastmildhighTRUEyesovercasthotnormalFALSEyesrainymildhighTRUEno只看最后一列我們得到打球的概率是9/14，不打球的概率是5/14。因此在沒有任何先驗信息的情況下，系統(tǒng)的熵（不確定性）為：決策樹C算法總結(jié)outlooktemperaturehu

12、miditywindyplay yesno yesno yesno yesnoyesnosunny23hot22high34FALSE6295overcast40mild42normal61TRUE33 rainy32cool31 如果選outlook作為決策樹的根節(jié)點，（7）式中的Y為集合sunny、overcast、rainy，此時的條件熵為即選擇outlook作為決策樹的根節(jié)點時，信息增益為0.94-0.693=0.247，然后計算outlook屬性的熵，得增益比。同樣方法計算當(dāng)選擇temperature、humidity、windy作為根節(jié)點時系統(tǒng)的信息增益和屬性熵，選擇增益比最大的作

13、為最終的根節(jié)點。決策樹C算法總結(jié)選擇節(jié)點分裂屬性的問題 ID3算法：使用信息增益作為選擇節(jié)點分裂屬性的指標(biāo)。增益準(zhǔn)則的一個缺陷是它偏向于選擇具有更多取值的屬性作為節(jié)點分裂屬性。 C4.5算法：使用信息增益率作為選擇節(jié)點分裂屬性的指標(biāo)，克服了ID3算法的缺點。增益增益比（比（Gain ratio）：增益）：增益/屬性熵屬性熵決策樹C算法總結(jié)樹停止生長條件1）節(jié)點內(nèi)的數(shù)據(jù)已經(jīng)完全屬于同一類別。2）節(jié)點內(nèi)測數(shù)據(jù)樣本數(shù)低于某一閾值。3）所有屬性都已經(jīng)被分裂過。決策樹C算法總結(jié)處理連續(xù)型數(shù)據(jù) ID3算法：不能處理連續(xù)型數(shù)據(jù)，只能處理離散型數(shù)據(jù)。 C4.5算法：以二值離散的方式處理連續(xù)型數(shù)據(jù)。二值離散：對

14、連續(xù)型屬性進行排序，得到多個候選閾值，選取產(chǎn)生最大信息增益的閾值作為分裂閾值。Temperature： 40 48 60 72 80 90Play Tennis: No No Yes Yes Yes YesOn the handling of continuous-valued attributes in decision tree generationUM Fayyad, KB Irani - Machine learning, 1992 - SpringerMulti-interval discretization of continuous-valued attributes for c

15、lassification learningU Fayyad, K Irani - 1993 - 決策樹C算法總結(jié)處理缺失值ID3算法：不能處理缺失值。C4.5算法：可以處理缺失值。Unknown attribute values in induction.JR Quinlan - ML, 1989 - Citeseer三種情況：1）在具有缺失值的屬性上如何計算信息增益率？解決方案：a) 忽略該類樣本。b) 選擇常用值或均值填充。c ) 依據(jù)缺失比例，折算信息增益/信息增益率。d) 對缺失值賦予獨特的值，參與訓(xùn)練。2）具有缺失值的樣本在進行數(shù)據(jù)分裂時，分

16、配給哪個子數(shù)據(jù)集？解決方案：a) 忽略該類樣本。b) 選擇常用值或均值填充。c ) 根據(jù)其他非缺失屬性的比例，分配到子數(shù)據(jù)集中。d) 為缺失值建立單獨分支。 f) 確定最可能的取值，按比例僅分配給一個子數(shù)據(jù)集。3）對新樣本進行分類時，缺失值導(dǎo)致樣本到達葉子節(jié)點，怎么處理？解決方案：a) 有缺失值單獨分支，走單獨分支。b) 走最常見的值的分支。c ) 確定最可能取值，走相應(yīng)分支。d) 走所有分支，根據(jù)不同輸出結(jié)果的概率進行組合。 f) 不進行分類，直接賦給最有可能的值。決策樹C算法總結(jié)過擬合問題過擬合：過擬合：有監(jiān)督的算法需要考慮泛化能力，在有限樣本的條件下，決策樹超過一定規(guī)模后，訓(xùn)練錯誤率減小

17、，但測試錯誤率會增加。剪枝剪枝：控制決策樹規(guī)模的方法稱為剪枝，一種是先剪枝，一種是后剪枝。所謂先剪枝，實際上是控制決策樹的生長；后剪枝是指，對完全生成的決策樹進行修剪。先先剪枝：剪枝：1) 數(shù)據(jù)劃分法。劃分數(shù)據(jù)成訓(xùn)練樣本和測試樣本，使用用訓(xùn)練樣本進行訓(xùn)練，使用測試樣本進行樹生長檢驗。2) 閾值法。當(dāng)某節(jié)點的信息增益小于某閾值時，停止樹生長。3) 信息增益的統(tǒng)計顯著性分析。從已有節(jié)點獲得的所有信息增益統(tǒng)計其分布，如果繼續(xù)生長得到的信息增 益與該分布相比不顯著，則停止樹的生長。優(yōu)點：優(yōu)點：簡單直接；缺點：缺點：對于不回溯的貪婪算法，缺乏后效性考慮，可能導(dǎo)致樹提前停止。決策樹C算法總結(jié)過擬合問題 后

18、剪枝：后剪枝：1) 減少分類錯誤修剪法。使用獨立的剪枝集估計剪枝前后的分類錯誤率，基于此進行剪枝。2) 最小代價與復(fù)雜性折中的剪枝。對剪枝后的樹綜合評價錯誤率和復(fù)雜性，決定是否剪枝。3) 最小描述長度準(zhǔn)則。最簡單的樹就是最好的樹。對決策樹進行編碼，通過剪枝得到編碼最小的樹。4) 規(guī)則后剪枝。將訓(xùn)練完的決策樹轉(zhuǎn)換成規(guī)則，通過刪除不會降低估計精度的前件修剪每一條規(guī)則。 優(yōu)點優(yōu)點: 實際應(yīng)用中有效 缺點：缺點：數(shù)據(jù)量大時，計算代價較大。決策樹C算法總結(jié)C4.5的剪枝方法 C4.5采用悲觀剪枝法，它使用訓(xùn)練集生成決策樹又用它來進行剪枝，不需要獨立的剪枝集。決策樹C算法總結(jié)C4.5的剪枝方法決策樹C算法總結(jié)C4.5的剪枝方法決策樹C算法總結(jié)Weka J48算法參數(shù)是否對離散屬性進行二元分裂剪枝過程中的置信因子，值越小剪枝越多設(shè)置為true，控制臺會輸出調(diào)試信息葉節(jié)點的最小實例數(shù)定義用來剪枝的樣本比例是否使用減少誤差剪枝法是否保存訓(xùn)練樣本數(shù)據(jù)使用減小誤差剪枝法中的隨機