ID3選擇屬性的依據是資訊增益：
![Information Gain][equtation]
[equtation]: http://latex.codecogs.com/svg.latex?g_r(D,A)=H(D)-H(D|A)
ID3算法在選擇根節點和内部節點中的分支屬性時，采用資訊增益作為評價标準。資訊增益的缺點是傾向于選擇取值較多的屬性，在有些情況下這類屬性可能不會提供太多有價值的資訊。是以我們發展了C4.5乃至之後的C5.0算法。
C4.5算法
C4.5算法主要做出了以下方面的改進：
1.可以處理連續數值型屬性
對于離散值，C4.5和ID3的處理方法相同，對于某個屬性的值連續時，假設這這個節點上的資料集合樣本為total，C4.5算法進行如下處理：
将樣本資料該屬性A上的具體數值按照升序排列，得到屬性序列至{A1,A2,A3,...,Atotal}；
在上一步生成的序列值中生成total-1個分割點。第i個分割點的取值為Ai和Ai+1的均值，每個分割點都将屬性序列劃分為兩個子集。
計算每個分割點的資訊增益(Information Gain),得到total-1個資訊增益。
對分裂點的資訊增益進行修正：減去log2(N-1)/|D|，其中N為可能的分裂點個數，D為資料集合大小。
選擇修正後的資訊增益值最大的分類點作為該屬性的最佳分類點。
計算最佳分裂點的資訊增益率(Gain Ratio)作為該屬性的Gain Ratio。
選擇Gain Ratio最大的屬性作為分類屬性。
![Gain Ratio][equtation2]
[equtation2]: http://latex.codecogs.com/svg.latex?g_R(D,A)=\frac{g_r(D,A)}{H_A(D)}=\frac{H(D)-H(D|A)}{H_A(D)}
2.用資訊增益率(Information Gain Ratio)來選擇屬性
克服了用資訊增益來選擇屬性時偏向選擇值多的屬性的不足。
![Gain Ratio][equtation2]
3.後剪枝政策
決策樹很容易産生過拟合，剪枝能夠避免樹高度無限制增長，避免過度拟合資料。在上一節内容中，我們通過限制決策樹的最大深度，這本質是一種預剪枝。
後剪枝相對來說更難一些，是通過一個剪枝系數來實作的，這裡暫不論述。
**4.缺失值處理 **
對于某些采樣資料，可能會缺少屬性值。在這種情況下，處理缺少屬性值的通常做法是賦予該屬性的常見值，或者屬性均值。另外一種比較好的方法是為該屬性的每個可能值賦予一個機率，即将該屬性以機率形式指派。例如給定Boolean屬性B，已知采樣資料有12個B=0和88個B=1執行個體，那麼在指派過程中，B屬性的缺失值被指派為B(0)=0.12、B(1)=0.88；是以屬性B的缺失值以12%機率被分到False的分支，以88%機率被分到True的分支。這種處理的目的是計算資訊增益，使得這種屬性值缺失的樣本也能處理。
5.C4.5的缺點
算法低效，在構造樹的過程中，需要對資料集進行多次的順序掃描和排序，因而導緻算法的低效
記憶體受限，适合于能夠駐留于記憶體的資料集，當訓練集大得無法在記憶體容納時程式無法運作。
C4.5的僞代碼
Function C4.5(R:包含連續屬性的無類别屬性集合,C:類别屬性,S:訓練集)
Begin
If S為空,傳回一個值為Failure的單個節點;
If S是由相同類别屬性值的記錄組成,
傳回一個帶有該值的單個節點;
If R為空,則傳回一個單節點,其值為在S的記錄中找出的頻率最高的類别屬性值;
[注意未出現錯誤則意味着是不适合分類的記錄]；
For 所有的屬性R(Ri) Do
If 屬性Ri為連續屬性，則
Begin
sort(Ri屬性值)
将Ri的最小值賦給A1：
将Ri的最大值賦給Am；
For j From 1 To m-1 Do Aj=(A1+Aj+1)/2;
将Ri點的基于Aj(1<=j<=m-1劃分的最大資訊增益屬性(Ri,S)賦給A；
End；
将R中屬性之間具有最大資訊增益的屬性(D,S)賦給D;
将屬性D的值賦給{dj/j=1,2...m}；
将分别由對應于D的值為dj的記錄組成的S的子集賦給{sj/j=1,2...m};
傳回一棵樹，其根标記為D;樹枝标記為d1,d2...dm;
再分别構造以下樹:
C4.5(R-{D},C,S1),C4.5(R-{D},C,S2)...C4.5(R-{D},C,Sm);
End C4.5
CART算法
CART算法的重要基礎包含以下三個方面：
二分(Binary Split)：在每次判斷過程中，都是對觀察變量進行二分。
CART算法采用一種二分遞歸分割的技術，算法總是将目前樣本集分割為兩個子樣本集，使得生成的決策樹的每個非葉結點都隻有兩個分枝。是以CART算法生成的決策樹是結構簡潔的二叉樹。是以CART算法适用于樣本特征的取值為是或非的場景，對于連續特征的處理則與C4.5算法相似。
單變量分割(Split Based on One Variable)：每次最優劃分都是針對單個變量。
剪枝政策：CART算法的關鍵點，也是整個Tree-Based算法的關鍵步驟。
剪枝過程特别重要，是以在最優決策樹生成過程中占有重要地位。有研究表明，剪枝過程的重要性要比樹生成過程更為重要，對于不同的劃分标準生成的最大樹(Maximum Tree)，在剪枝之後都能夠保留最重要的屬性劃分，差别不大。反而是剪枝方法對于最優樹的生成更為關鍵。
CART的基礎是基尼系數(gini，并非經濟學中的基尼系數)：
![觀察第一個等式，對比資訊熵公式，我們把log(1/p_k)換成了(1-p_k)可以認為對log(1/p_k)在x_0=1處的泰勒展開，隻取前兩項後的結果。這種處理實際上減輕了運算壓力。][equtation3]
[equtation3]: http://latex.codecogs.com/svg.latex?Gini(p)=\sum_{k=1}{K}p_k(1-p_k)=1-\sum_{k=1}{K}p_k2=1-\sum_{k=1}{K}(\frac{\left|C_k\right|}{D})^2
GINI指數主要是度量資料劃分或訓練資料集D的不純度為主。GINI值越小，表明樣本的純淨度越高(即該樣本隻屬于同一類的機率越高)。
衡量出資料集某個特征所有取值的Gini指數後，就可以得到該特征的Gini Split info，也就是GiniGain。
Gini Gain
不考慮剪枝情況下，分類決策樹遞歸建立過程中就是每次選擇GiniGain最小的節點做分叉點，直至子資料集都屬于同一類或者所有特征用光。
CART的核心在于剪枝，我們日後再讨論這個問題。在最後一節，我們将會介紹随機森林的概念和簡單的實踐。