決策樹演算法代碼
『壹』 決策樹演算法基礎 ID3與C4.5
決策樹演算法基礎：ID3與C4.5
設X是一個取有限個值得離散隨機變數，其概率分布為P(X=xi)=pi, i=1,2,…,n。則隨機變數X的信息熵為
條件熵H(Y|X)表示在已知隨機變數X的條件下隨機變數Y的不確定性。H(Y|X)的計算公式為
所以決策樹分支後信息總熵H(D|A)=P1*H1+P2*H2+...+Pn*Hn,(特徵A條件下D的經驗條件熵)
所以信息增益ΔH=H(D)-H(D|A)
H(D|A)越小，ΔH越大，該特徵A越適合作為當前的決策節點。
選取最佳特徵偽代碼：
計算信息總熵H(D)
遍歷每一個特徵下的關於D的經驗條件熵H(D|A)
計算每一個特徵的信息增益ΔH
將信息增益ΔH最大的特徵作為最佳特徵選為當前決策節點
ID3演算法偽代碼：
如果第一個標簽的數量等於所有的標簽數量，說明這是一個單節點樹，返回這個標簽作為該節點類
如果特徵只有一個，說明這是一個單節點樹，用多數表決法投票選出標簽返回作為該節點類
否則，按信息增益最大的特徵A作為當前決策節點，即決策樹父節點
如果該特徵的信息增益ΔH小於閾值，則用多數表決法投票選出標簽返回作為該節點類
否則，對於該特徵A的每一個可能值ai，將原空間D分割為若干個子空間Di
對於若干個非空子集Di，將每個Di中實例數最大的類作為標記，構建子節點
以Di為訓練空間，遞歸調用上述步驟
由於信息增益存在偏向於選擇取值較多的特徵的問題，而C4.5演算法中，將ID3演算法里的信息增益換成信息增益比，較好地解決了這個問題。
決策樹的優點在於計算量簡單，適合有缺失屬性值的樣本，適合處理不相關的特徵。而缺點是容易過擬合，可以通過剪枝來簡化模型，另外隨機森林也解決了這個問題。
『貳』 常見決策樹分類演算法都有哪些
在機器學習中，有一個體系叫做決策樹，決策樹能夠解決很多問題。在決策樹中，也有很多需要我們去學習的演算法，要知道，在決策樹中，每一個演算法都是實用的演算法，所以了解決策樹中的演算法對我們是有很大的幫助的。在這篇文章中我們就給大家介紹一下關於決策樹分類的演算法，希望能夠幫助大家更好地去理解決策樹。
1.C4.5演算法
C4.5演算法就是基於ID3演算法的改進，這種演算法主要包括的內容就是使用信息增益率替換了信息增益下降度作為屬性選擇的標准；在決策樹構造的同時進行剪枝操作；避免了樹的過度擬合情況；可以對不完整屬性和連續型數據進行處理；使用k交叉驗證降低了計算復雜度；針對數據構成形式，提升了演算法的普適性等內容，這種演算法是一個十分使用的演算法。
2.CLS演算法
CLS演算法就是最原始的決策樹分類演算法，基本流程是，從一棵空數出發，不斷的從決策表選取屬性加入數的生長過程中，直到決策樹可以滿足分類要求為止。CLS演算法存在的主要問題是在新增屬性選取時有很大的隨機性。
3.ID3演算法
ID3演算法就是對CLS演算法的最大改進是摒棄了屬性選擇的隨機性，利用信息熵的下降速度作為屬性選擇的度量。ID3是一種基於信息熵的決策樹分類學習演算法，以信息增益和信息熵，作為對象分類的衡量標准。ID3演算法結構簡單、學習能力強、分類速度快適合大規模數據分類。但同時由於信息增益的不穩定性，容易傾向於眾數屬性導致過度擬合，演算法抗干擾能力差。
3.1.ID3演算法的優缺點
ID3演算法的優點就是方法簡單、計算量小、理論清晰、學習能力較強、比較適用於處理規模較大的學習問題。缺點就是傾向於選擇那些屬性取值比較多的屬性，在實際的應用中往往取值比較多的屬性對分類沒有太大價值、不能對連續屬性進行處理、對雜訊數據比較敏感、需計算每一個屬性的信息增益值、計算代價較高。
3.2.ID3演算法的核心思想
根據樣本子集屬性取值的信息增益值的大小來選擇決策屬性，並根據該屬性的不同取值生成決策樹的分支，再對子集進行遞歸調用該方法，當所有子集的數據都只包含於同一個類別時結束。最後，根據生成的決策樹模型，對新的、未知類別的數據對象進行分類。
在這篇文章中我們給大家介紹了決策樹分類演算法的具體內容，包括有很多種演算法。從中我們不難發現決策樹的演算法都是經過不不斷的改造趨於成熟的。所以說，機器學習的發展在某種程度上就是由於這些演算法的進步而來的。
『叄』 python中的sklearn中決策樹使用的是哪一種演算法
sklearn中決策樹分為DecisionTreeClassifier和DecisionTreeRegressor，所以用的演算法是CART演算法，也就是分類與回歸樹演算法(classification and regression tree,CART)，劃分標准默認使用的也是Gini，ID3和C4.5用的是信息熵，為何要設置成ID3或者C4.5呢
『肆』 瀹㈡埛淇＄敤璇勪環妯″瀷鐨勫疄鐜
瀹㈡埛淇＄敤璇勪環妯″瀷錛屽彲浠ョ粨鍚圫QL鑷甯︾殑鍐崇瓥鏍戞垨紲炵粡緗戠粶綆楁硶瑙ｅ喅錛屽叿浣撶殑姝ラょ湅鑷甯︾殑鏁欑▼灝辮屻傛帹鑽愬喅絳栨爲錛屾寲鎺樼殑鐭ヨ瘑鏈夎緝濂界殑瑙ｉ噴鎬с
🌳鍐崇瓥鏍戠畻娉
鎺ㄨ崘鍐崇瓥鏍戱紝鎸栨帢鐨勭煡璇嗘湁杈冨ソ鐨勮В閲婃с
🧠紲炵粡緗戠粶綆楁硶
鍙浠ョ粨鍚圫QL鑷甯︾殑鍐崇瓥鏍戞垨紲炵粡緗戠粶綆楁硶瑙ｅ喅銆
📊鍓嶅彴灞曠幇宸ュ叿
鍓嶅彴鏄劇ず紼嬪簭涓昏佹槸鍊熷姪congos鎴栬匓O鍓嶅彴灞曠幇宸ュ叿錛孋#寮鍙戝嚭鐣岄潰鍚庣洿鎺ヨ皟鐢ㄨ繖浜涘伐鍏烽噷鎸傝澆鐨勬姤琛ㄦ垨鑰呮寲鎺樼粨鏋滅殑鐣岄潰銆
『伍』 決策樹的演算法
C4.5演算法繼承了ID3演算法的優點，並在以下幾方面對ID3演算法進行了改進：
1) 用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足；
2) 在樹構造過程中進行剪枝；
3) 能夠完成對連續屬性的離散化處理；
4) 能夠對不完整數據進行處理。
C4.5演算法有如下優點：產生的分類規則易於理解，准確率較高。其缺點是：在構造樹的過程中，需要對數據集進行多次的順序掃描和排序，因而導致演算法的低效。此外，C4.5隻適合於能夠駐留於內存的數據集，當訓練集大得無法在內存容納時程序無法運行。
具體演算法步驟如下；
1創建節點N
2如果訓練集為空，在返回節點N標記為Failure
3如果訓練集中的所有記錄都屬於同一個類別，則以該類別標記節點N
4如果候選屬性為空，則返回N作為葉節點，標記為訓練集中最普通的類；
5for each 候選屬性 attribute_list
6if 候選屬性是連續的then
7對該屬性進行離散化
8選擇候選屬性attribute_list中具有最高信息增益率的屬性D
9標記節點N為屬性D
10for each 屬性D的一致值d
11由節點N長出一個條件為D=d的分支
12設s是訓練集中D=d的訓練樣本的集合
13if s為空
14加上一個樹葉，標記為訓練集中最普通的類
15else加上一個有C4.5（R - {D},C，s）返回的點 背景：
分類與回歸樹(CART——Classification And Regression Tree)) 是一種非常有趣並且十分有效的非參數分類和回歸方法。它通過構建二叉樹達到預測目的。
分類與回歸樹CART 模型最早由Breiman 等人提出，已經在統計領域和數據挖掘技術中普遍使用。它採用與傳統統計學完全不同的方式構建預測准則，它是以二叉樹的形式給出，易於理解、使用和解釋。由CART 模型構建的預測樹在很多情況下比常用的統計方法構建的代數學預測准則更加准確，且數據越復雜、變數越多，演算法的優越性就越顯著。模型的關鍵是預測准則的構建，准確的。
定義：
分類和回歸首先利用已知的多變數數據構建預測准則, 進而根據其它變數值對一個變數進行預測。在分類中, 人們往往先對某一客體進行各種測量, 然後利用一定的分類准則確定該客體歸屬那一類。例如, 給定某一化石的鑒定特徵, 預測該化石屬那一科、那一屬, 甚至那一種。另外一個例子是, 已知某一地區的地質和物化探信息, 預測該區是否有礦。回歸則與分類不同, 它被用來預測客體的某一數值, 而不是客體的歸類。例如, 給定某一地區的礦產資源特徵, 預測該區的資源量。
『陸』 決策樹原理及演算法比較
決策樹是什麼？
和線性回歸一樣是一種模型，內部節點和葉節點。實現分類，內部節點和葉節點通過有向線（分類規 則）連接起來
決策樹的目標是什麼？
決策樹通過對數據復雜度的計算，建立特徵分類標准，確定最佳分類特徵。
表現為「熵」（entropy）和信息增益（information gain），基於決策樹思想的三種演算法：ID3，C4.5,CART演算法，三種演算法的信息衡量的指標也不同.
熵來表示信息的復雜度，熵越大，信息也就越復雜，公式如下：
那些演算法能夠實現決策樹？
在決策樹構建過程中，什麼是比較重要的。特徵選擇（按照熵變計算），演算法產生最重要的部分，
決策樹中葉節點的分類比較純，
節點順序的排列規則：
熵變：
數據的預處理：
改進思路一般有兩個1，換演算法；2，調參數
做好數據的預處理：
1，做好特徵選擇；
2，做好數據離散化、異常值處理、缺失填充
分類器：
在決策樹中，從根到達任意一個葉節點的之間最長路徑的長度，表示對應的演算法排序中最壞情況下的比較次數。這樣一個比較演算法排序中的最壞情況的比較次數就與其決策樹的高度相同，同時如果決策樹中每種排列以可達葉子的形式出現，那麼關於其決策樹高度的下界也就是關於比較排序演算法運行時間的下界，
ID3演算法存在的缺點：
1，ID3演算法在選擇根節點和內部節點分支屬性時，採用信息增益作為評價標准。信息增益的缺點是傾向於選擇取值較多的屬性
2，當數據為連續性變數的時候，ID3演算法就不是一個合理的演算法的模型了
C4.5信息增益比率，
1，在信息增益的基礎上除以split-info，是將信息增益改為信息增益比，以解決取值較多的屬性的問題，另外它還可以處理連續型屬性，其判別標準是θ，
2，C4.5演算法利用增益/熵值，克服了樹生長的過程中，總是『貪婪』選擇變數分類多的進行分類
3，處理來內需型變數，C4.5的分類樹的分支就是兩條
衡量指標：
（1）信息增益
基於ID3演算法的信息增益對於判定連續型變數的時候病不是最優選擇，C4.5演算法用了信息增益率這個概念。
分類信息類的定義如下：
這個值表示將訓練數據集D劃分成對應屬性A測試的V個輸出v個劃分產生的信息，信息增益率定義為：
選擇最大信息增益率的屬性作為分裂屬性
Gini指標，CART
表明樣本的「純凈度」。Gini系數避免了信息增益產生的問題，
過擬合問題，非常好的泛化能力，有很好的推廣能力
Gini系數的計算：
在分類問題中，假設有k個類，樣本點屬於第k類的概率為Pk，則概率分布的gini指數的定義為：
如果樣本集合D根據某個特徵A被分割為D1，D2兩個部分，那麼在特徵A的提哦啊見下，集合D的gini指數的定義為：
Gini指數代表特徵A不同分組下的數據集D的不確定性，gini指數越大，樣本集合的不確定性也就越大，這一點和熵的概念相類似
決策樹原理介紹：
第三步：對於每個屬性執行劃分：
（1）該屬性為離散型變數
記樣本中的變數分為m中
窮舉m種取值分為兩類的劃分
對上述所有劃分計算GINI系數
（2）該屬性為連續型變數
將數據集中從小到大劃分
按順序逐一將兩個相臨值的均值作為分割點
對上述所有劃分計算GINI系數
學歷的劃分使得順序的劃分有個保證，化為連續型變數處理。
決策樹的生成演算法分為兩個步驟：
預剪枝和後剪枝 CCP（cost and complexity）演算法：在樹變小和變大的的情況有個判斷標准。誤差率增益值：α值為誤差的變化
決策樹的終止條件：
1，某一個節點的分支所覆蓋的樣本都是同一類的時候
2，某一個分支覆蓋的樣本的個數如果小於一個閾值，那麼也可以產生葉子節點，從而終止Tree-Growth
確定葉子結點的類：
1，第一種方式，葉子結點覆蓋的樣本都屬於同一類
2， 葉子節點覆蓋的樣本未必是同一類，所佔的大多數，那麼該葉子節點的類別就是那個佔大多數的類
『柒』 R語言-17決策樹
是一個預測模型，分為回歸決策樹和分類決策樹，根據已知樣本訓練出一個樹模型，從而根據該模型對新樣本因變數進行預測，得到預測值或預測的分類
從根節點到葉節點的一條路徑就對應著一條規則．整棵決策樹就對應著一組表達式規則。葉節點就代表該規則下得到的預測值。如下圖決策樹模型則是根據房產、結婚、月收入三個屬性得到是否可以償還貸款的規則。
核心是如何從眾多屬性中挑選出具有代表性的屬性作為決策樹的分支節點。
最基本的有三種度量方法來選擇屬性
1. 信息增益（ID3演算法）
信息熵
一個信源發送出什麼符號是不確定的，衡量它可以根據其出現的概率來度量。概率大，出現機會多，不確定性小；反之不確定性就大。不確定性函數f是概率P的 減函數 。兩個獨立符號所產生的不確定性應等於各自不確定性之和，即f(P1,P2)=f(P1)+f(P2)，這稱為可加性。同時滿足這兩個條件的函數f是對數函數，即
在信源中，考慮的不是某一單個符號發生的不確定性，而是要考慮這個信源所有可能發生情況的平均不確定性。因此，信息熵被定義為
決策樹分類過程
2、增益率（C4.5演算法）
由於信息增益的缺點是：傾向於選擇具有大量值的屬性，因為具有大量值的屬性每個屬性對應數據量少，傾向於具有較高的信息純度。因此增益率使用【信息增益/以該屬性代替的系統熵（類似於前面第一步將play換為該屬性計算的系統熵】這個比率，試圖克服這種缺點。
g(D,A)代表D數據集A屬性的信息增益，
3. 基尼指數（CART演算法）
基尼指數：
表示在樣本集合中一個隨機選中的樣本被分錯的概率。越小表示集合中被選中的樣本被分錯的概率越小，也就是說集合的純度越高。
假設集合中有K個類別，則：
說明:
1. pk表示選中的樣本屬於k類別的概率，則這個樣本被分錯的概率是(1-pk)
2. 樣本集合中有K個類別，一個隨機選中的樣本可以屬於這k個類別中的任意一個，因而對類別就加和
3. 當為二分類是，Gini(P) = 2p(1-p)
基尼指數是將屬性A做二元劃分，所以得到的是二叉樹。當為離散屬性時，則會將離散屬性的類別兩兩組合，計算基尼指數。
舉個例子：
如上面的特徵Temperature，此特徵有三個特徵取值： 「Hot」，「Mild」， 「Cool」，
當使用「學歷」這個特徵對樣本集合D進行劃分時，劃分值分別有三個，因而有三種劃分的可能集合，劃分後的子集如下：
對於上述的每一種劃分，都可以計算出基於 劃分特徵= 某個特徵值 將樣本集合D劃分為兩個子集的純度：
決策數分類過程
先剪枝 ：提前停止樹的構建對樹剪枝，構造樹時，利用信息增益、統計顯著性等，當一個節點的劃分導致低於上述度量的預定義閾值時，則停止進一步劃分。但閾值的確定比較困難。
後剪枝 ：更為常用，先得到完全生長的樹，再自底向上，用最下面的節點的樹葉代替該節點
CART使用代價復雜度剪枝演算法 ：計算每個節點剪枝後與剪枝前的代價復雜度，如果剪去該節點，代價復雜度較小（復雜度是樹的結點與樹的錯誤率也就是誤分類比率的函數），則剪去。
C4.5採用悲觀剪枝 ：類似代價復雜度，但CART是利用剪枝集評估代價復雜度，C4.5是採用訓練集加上一個懲罰評估錯誤率
決策樹的可伸縮性
ID3C4.5CART都是為較小的數據集設計，都限制訓練元祖停留再內存中，為了解決可伸縮性，提出了其它演算法如
RainForest(雨林）：對每個屬性維護一個AVC集，描述該結點的訓練元組，所以只要將AVC集放在內存即可
BOAT自助樂觀演算法：利用統計學，創造給定訓練數據的較小樣本，每個樣本構造一個樹，導致多顆樹，再利用它們構造1顆新樹。優點是可以增量的更新，當插入或刪除數據，只需決策樹更新，而不用重新構造。
決策樹的可視化挖掘
PBC系統可允許用戶指定多個分裂點，導致多個分支，傳統決策樹演算法數值屬性都是二元劃分。並且可以實現交互地構建樹。
rpart是採用cart演算法，連續型「anova」;離散型「class」;
2）進行剪枝的函數：prune()
3）計算MAE評估回歸樹模型誤差，這里將樣本劃分成了訓練集和測試集，testdata為測試集
rt.mae為根據訓練集得到的決策樹模型對測試集因變數預測的結果與測試集因變數實際值得到平均絕對誤差