1、C4.5例如數據：weka中的weather數據字符型、數值型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,yesr

2、ainy,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,nooverca

3、st,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,noC4.5例如SPSS Clementine C5.0C4.5例如Weka J48C4.5算法簡介決策樹方法：利用一定的訓練樣本，從數據中學習出決策規那么自動構造出決策樹。C4.5算法: JR Quinlan, 1993分類決策樹算法,其中心算法是ID3算法。目前運用在臨

4、床決策、消費制造、文檔分析、生物信息學、空間數據建模等領域。算法的輸入是帶類標的數據，輸出是樹形的決策規那么。ID3算法：JRQuinlan- Machine learning, 1986ID3算法的原型來自于Hunt等人提出的概念學習系統concept learning system, CLS。C4.5算法簡介C4.5比ID3的改良:1) 用信息增益率來選擇屬性，抑制了用信息增益選擇屬性時偏向選擇取值多的屬性的缺乏；2) 在樹構造過程中進展剪枝；3) 可以完成對延續屬性的離散化處置；4) 可以對不完好數據進展處置。C4.5算法優點：產生的分類規那么易于了解，準確率較高。C4.5算法缺陷：在構

5、造樹的過程中，需求對數據集進展多次的順序掃描和排序，因此導致算法的低效。決策樹算法開展二級存儲:針對不能完全放入內存的數據集，在確保分類器算法效能的前提下，要做到數據集掃描遍數的極小化。BOAT算法J Gehrke, V Ganti, R Ramakrishnan - SIGMOD , 1999運用抽樣、交融、完好掃描三步得到最終的分類器。RainForest框架J Gehrke, R Ramakrishnan, V Ganti - VLDB, 1998實現了多種詳細的決策樹構建方法，適用于大規模數據集的處置。其他基于二級存儲設備的算法還有SLIQ M Mehta, R Agrawal, J

6、Rissanen - Advances in Database Technology , 1996 ，SPRINTJ Shafer, R Agrawal, M Mehta - Proc. 1996 Int. Conf. Very Large Data , 1996 - Citeseer，PUBLICR Rastogi, K Shim - VLDB, 1998 - cs.sfu.ca等。斜決策樹：斜決策樹適用于處置延續型數據，決策準那么運用屬性的線性組合。采用屬性的線性組合戰略的一個典型的決策樹分類器是OC1SK Murthy, S Kasif, S Salzberg - arXiv prepr

7、int cs/9408103, 1994 - 。集成方法：裝袋法和推舉法。R Maclin, D Opitz - arXiv preprint arXiv:1106.0257, 2021 - 算法流程：1選擇哪個屬性進展節點分裂？2何時停頓樹生長？3怎樣處置延續型屬性？4怎樣處置缺失值？5怎樣處置過擬合問題？問題：1選擇節點分裂屬性2建立新節點，劃分數據集3判別節點能否到生長停頓條件，假設是，終止生長，假設不是，轉到1選擇節點分裂屬性的問題熵Entropy：我們把一個事件的不確定程度叫做“熵，熵越大闡明這個事件的結果越難以預測，同時事件的發生將給我們帶來越多

8、的信息。增益InformationGain：在信息增益中，衡量規范是看特征可以為分類系統帶來多少信息，帶來的信息越多，該特征越重要。對一個特征而言，系統有它和沒它時信息量將發生變化，而前后信息量的差值就是這個特征給系統帶來的信息量。所謂信息量，就是熵。系統原先的熵是H(X)，在條件Y知的情況下系統的熵條件熵為H(X|Y)，信息增益就是這兩個熵的差值。outlooktemperaturehumiditywindyplaysunnyhothighFALSEnosunnyhothighTRUEnoovercasthothighFALSEyesrainymildhighFALSEyesrainycoo

9、lnormalFALSEyesrainycoolnormalTRUEnoovercastcoolnormalTRUEyessunnymildhighFALSEnosunnycoolnormalFALSEyesrainymildnormalFALSEyessunnymildnormalTRUEyesovercastmildhighTRUEyesovercasthotnormalFALSEyesrainymildhighTRUEno只看最后一列我們得到打球的概率是9/14，不打球的概率是5/14。因此在沒有任何先驗信息的情況下，系統的熵不確定性為：outlooktemperaturehumidit

10、ywindyplayyesnoyesnoyesnoyesnoyesnosunny23hot22high34FALSE6295overcast40mild42normal61TRUE33rainy32cool31假設選outlook作為決策樹的根節點，7式中的Y為集合sunny、overcast、rainy，此時的條件熵為即選擇outlook作為決策樹的根節點時，信息增益為0.94-0.693=0.247，然后計算outlook屬性的熵，得增益比。同樣方法計算中選擇temperature、humidity、windy作為根節點時系統的信息增益和屬性熵，選擇增益比最大的作為最終的根節點。選擇節點分

11、裂屬性的問題ID3算法：運用信息增益作為選擇節點分裂屬性的目的。增益準那么的一個缺陷是它偏向于選擇具有更多取值的屬性作為節點分裂屬性。C4.5算法：運用信息增益率作為選擇節點分裂屬性的目的，抑制了ID3算法的缺陷。增益比Gain ratio：增益/屬性熵其他準那么：方差不純度：誤差不純度：殊途同歸，實驗證明其他不同的分裂準那么與信息增益率準那么沒有明顯差別，準那么對精度的影響遠小于剪枝算法對精度的影響。樹停頓生長條件1節點內的數據曾經完全屬于同一類別。2節點內測數據樣本數低于某一閾值。3一切屬性都曾經被分裂過。處置延續型數據ID3算法：不能處置延續型數據，只能處置離散型數據。C4.5算法：以二

12、值離散的方式處置延續型數據。二值離散：對延續型屬性進展排序，得到多個候選閾值，選取產生最大信息增益的閾值作為分裂閾值。Temperature： 40 48 60 72 80 90Play Tennis: No No Yes Yes Yes YesUMFayyad, KB Irani - Machine learning, 1992 - SpringerUFayyad, K Irani - 1993 - 處置缺失值ID3算法：不能處置缺失值。C4.5算法：可以處置缺失值。JR Quinlan - ML, 1989 - Citeseer三種情況：1在具有缺失

13、值的屬性上如何計算信息增益率？處理方案：a) 忽略該類樣本。b) 選擇常用值或均值填充。c ) 根據缺失比例，折算信息增益/信息增益率。d) 對缺失值賦予獨特的值，參與訓練。2具有缺失值的樣本在進展數據分裂時，分配給哪個子數據集？處理方案：a) 忽略該類樣本。b) 選擇常用值或均值填充。c ) 根據其他非缺失屬性的比例，分配到子數據集中。d) 為缺失值建立單獨分支。 f) 確定最能夠的取值，按比例僅分配給一個子數據集。3對新樣本進展分類時，缺失值導致樣本到達葉子節點，怎樣處置？處理方案：a) 有缺失值單獨分支，走單獨分支。b) 走最常見的值的分支。c ) 確定最能夠取值，走相應分支。d) 走一

14、切分支，根據不同輸出結果的概率進展組合。 f) 不進展分類，直接賦給最有能夠的值。過擬合問題過擬合：有監視的算法需求思索泛化才干，在有限樣本的條件下，決策樹超越一定規模后，訓練錯誤率減小，但測試錯誤率會添加。剪枝：控制決策樹規模的方法稱為剪枝，一種是先剪枝，一種是后剪枝。所謂先剪枝，實踐上是控制決策樹的生長；后剪枝是指，對完全生成的決策樹進展修剪。先剪枝：1) 數據劃分法。劃分數據成訓練樣本和測試樣本，運用用訓練樣本進展訓練，運用測試樣本進展樹生長檢驗。2) 閾值法。當某節點的信息增益小于某閾值時，停頓樹生長。3) 信息增益的統計顯著性分析。從已有節點獲得的一切信息增益統計其分布，假設繼續生長

15、得到的信息增益與該分布相比不顯著，那么停頓樹的生長。優點：簡單直接；缺陷：對于不回溯的貪婪算法，缺乏后效性思索，能夠導致樹提早停頓。過擬合問題后剪枝：減少分類錯誤修剪法。運用獨立的剪枝集估計剪枝前后的分類錯誤率，基于此進展剪枝。最小代價與復雜性折中的剪枝。對剪枝后的樹綜合評價錯誤率和復雜性，決議能否剪枝。最小描畫長度準那么。最簡單的樹就是最好的樹。對決策樹進展編碼，經過剪枝得到編碼最小的樹。規那么后剪枝。將訓練完的決策樹轉換成規那么，經過刪除不會降低估計精度的前件修剪每一條規那么。優點: 實踐運用中有效缺陷：數據量大時，計算代價較大。C4.5的剪枝方法 C4.5采用悲觀剪枝法，它運用訓練集生成

16、決策樹又用它來進展剪枝，不需求獨立的剪枝集。C4.5的剪枝方法 數學實際：基于理想置信區間confidence intervals, CI的剪枝方法。把葉節點的錯誤率e建模成服從伯努利分布的隨機變量，對于一個置信區間閾值CI，存在e的上界emax，使得e emax以1-CI的概率成立。用正態分布來逼近e當n極大時，伯努利分布退化成為正態分布。C4.5算法的的期望誤差上界為：服從規范正態分布的隨機變量。C4.5的剪枝方法Weka J48算法參數能否對離散屬性進展二元分裂剪枝過程中的置信因子，值越小剪枝越多設置為true，控制臺會輸出調試信息葉節點的最小實例數定義用來剪枝的樣本比例能否運用減少誤差剪枝法能否保管訓練樣本數據運用減小誤差剪枝法中的隨機種子參數修剪時能否思索子樹上升能否剪枝能否在對葉子計數時運用拉普拉斯平滑Weka J48算法源碼解析Weka J48算法源碼解析高級類J48Weka J48算法源碼解析可剪枝的C4.5分類器Weka J48算法源碼解析分類樹Weka J48算法源碼解析分類樹Weka J48算法源碼解析C4.5分裂方式Weka J48算法源碼解析