ID3決策樹
ID3決策樹分類的根據是樣本集分類前後的資訊增益。
假設我們有一個樣本集，裡面每個樣本都有自己的分類結果。
而資訊熵可以了解為：“樣本集中分類結果的平均不确定性”，俗稱資訊的純度。
即熵值越大，不确定性也越大。
不确定性計算公式
假設樣本集中有多種分類結果，裡面某一種結果的“不确定性”計算公式如下
其中
x：為按照某特征分類後的第x種分類結果
p(x)：表示該分類結果樣本集在總樣本集中的所占比例。
Dx：表示樣本結果為x的樣本數量。
D：表示樣本的總數量
可看出某一種分類結果在總樣本集中所占比例越少，其“不确定性”也越大。
資訊熵計算公式
樣本集的熵，就是他所有分類結果的平均不确定性，即所有分類結果不确定性求期望。公式如下：
說白了，就是算出整個樣本集中每一個分類結果的不确定性，然後求一個期望值，就作為這整個樣本集的熵值。
資訊熵增益
熵越大表示事件變數越多，我們要做的就是每一次分類都讓事件集變的最穩定。是以當我們選擇某一個特征進行分類後，樣本集分類前後的熵的減小量就是熵的增益。
ID3算法的核心就是計算按照每一種特征分類後，其熵差大小，選擇能使熵差最大的特征作為分類特征。
分類前的熵就是叢集整個的熵。
分類後的熵其實是所有分類後的小樣本集的熵的期望。
ID3算法缺陷
1、抗噪聲性差，如果資料樣本數量太少或噪聲太大，就會産生過拟合的問題。
樣本少，其樹的構成基本上就是為少數樣本量身定做的樹，如果噪聲太大，或樣本少且有噪聲的話，很多樹枝都是噪聲拟合出來的。
2、在選擇最優特征時，很容易傾向于選擇“特征值種類較多”的特征，作為分類特征。
我們舉個極端點的例子，假設有100個樣本集，現在有一個特征其數值種類也是100，如果按該特征分類，就能把這個樣本集分成100份，每份一個樣本。在用ID3算法做決策樹時，肯定會選擇這個特征作為第一個最優特征，因為這個特征分出來的樣本集每一個純度都是最高。
3、無法處理特征值為連續型資料的特征。（不過可以考慮把連續型資料轉化成離散型資料）
即，可以處理像性别特征、boolen特征等離散型特征，但沒法處理特征值在某個區間内可以任意取值的特征，如身高特征、年齡特征。
C4.5決策樹
針對上面說的ID3算法的第二個缺點“最優特征選擇傾向于特征種類較多的特征”。
我們先來看下特征種類較多時，分類會發生什麼。
假設都是均分100個樣本，
特征值有2種的特征會把樣本集分成50和50.
特征值為4種的特征會把樣本集分成25、25，25，25.
可見特征值越多，就會産生越多的“小數目”樣本集，而小數目樣本集在分類效果上是不如大樣本集好的（如過拟合、抗噪差等問題），是以對于某特征分類後會産生“小數目”樣本集的分類後的熵，我們需要有一個懲罰值，即：分類後産生的樣本集越小，它的熵值也要懲罰性的增大。
這樣雖然ID3算法中會因為很多分類後的小數量樣本集而産生低值的期望熵，但做懲罰值處理後，熵值就會平衡性的增大。
資訊增益率
在C4.5中懲罰小數量樣本集的做法是，
在根據某特征分類，并計算出分類前後的熵差後，再計算該特征的懲罰值，用該分類特征的熵差除以懲罰值得出“資訊增益率”，使資訊增益率越大的特征，就是最優特征。即：
其中懲罰值實際上就是“資訊熵”，隻不過這裡的資訊指的不是計算資訊增益時“樣本集中分類結果的平均不确定性”，而是“總樣本集中分類後子樣本集數目的平均不确定性”，即：
其中：
D：分類前的總樣本數量。
i：按某特征分類後樣本子集序号。
Di：按某特征分類後的第i個子集的數量。
由此看出，樣本數量越少，懲罰值越大，相除後的資訊增益率也就越小，依此做到了一定的平衡，由于“懲罰”了小樣本數量集，其由于數量少帶來資訊增益抗噪性差的問題也得到一定程度的解決。
這就是C4.5算法最大的好處，解決了ID3算法第二個缺陷，緩解了ID3算法的第一個缺陷。
不過ID3算法的第三個不能處理連續型特征資料的問題。C4.5算法本身也不能直接處理連續資料。
另外C4.5和ID3算法還有一個特點，這倆算法的根本其實都要計算資訊增益，而資訊增益的一個大前提就是要先進行分類，然後才能計算增益，是以每計算一次增益也就代表進行了一次分類，分類用了的特征接下來就不能再用了，是以ID3和C4.5算法在分類時會不斷消耗特征。
CART決策樹
簡單來講就是，有一個類似于熵的名額叫Gini指數，其代表了分類結果的不确定性，是以自然是越小越好。
每次分類前計算分類前後的Gini指數，求差得出“Gini指數增益”，能使Gini指數增益最大的特征就是最優特征。
需要注意的是，CART算法分類時，即使特征有大于兩個特征值，也還是會把樣本集分成兩類，最後形成的是标準二叉樹。
Gini指數
首先計算分類前樣本集的Gini指數，Gini指數想表達的東西和資訊熵類似，都是想表達樣本集分類結果的不确定性，Gini指數或熵越大，表示樣本集分類結果不确定性也越大。
假設樣本集數量為D，分類結果有n種，Dk表示總樣本集中分類結果為第k種的樣本數量。
那麼從總樣本集中選出分類結果為k的樣本的機率為：
選出分類結果為k的樣本的不确定性（即選出分類不為k的樣本機率）為：
而總樣本集的分類結果不确定性，就是計算n種分類結果的不确定性，然後取期望：
這個公式就是樣本集的Gini指數，用于表達樣本集分類結果的不确定性，Gini指數越大樣本集越不确定，化簡後得：
按照某特征分類後的Gini指數為，分類後各樣本集Gini指數求期望，
假設分類前總樣本集數量為D，按特征分類後得到兩堆樣本集數量分别為S1和S2（由于CART算法生成二叉樹的特性，是以隻能分成兩堆），則樣本集分類後的Gini指數為：
如果特征值大于兩個，則列出所有可能的分類情況，依次分類并計算各分類後的Gini指數，選擇分類後Gini指數最小的分類情況作為特征的分類方法。
如，特征有a,b,c三個特征值，
則可能的分類方法有：（a,(b,c)）,（b,(a,c)）,（c,(a,b)）
假設（b,(a,c)）這種分類方式分類後的Gini指數最小，則按照特征值為b的分為第一個樹枝，特征值為a或c的分為第二個樹枝，
第一個樹枝裡該特征隻有b特征值，則後續分類時不需要再考慮該特征。
第二個樹枝裡該特征中還有a和c兩種特征值，需要注意的是“後續分類時還是要考慮該特征，且特征值為a和c”。
Gini指數增益
最終，樣本集D，按照某特征分類出S1樣本集和S2樣本集後，其Gini指數增益為：
選取能使Gini指數增益最大的特征分類作為最優特征分類。
CART和C4.5算法差別
1.C4.5本質上還是基于資訊熵得出的資訊增益比，而CART算法的分類樹是基于Gini指數得出的Gini指數增益。
2.CART是一顆二叉樹，而C4.5算法沒有這個特點。這是因為在進行特征分類上，C4.5算法每次選擇一種特征進行分類後，每一個特征值都是一個樹枝。而CART算法每次分類會把特征的所有特征值分成兩堆，符合A堆裡面的特征值的樣本算A分支，符合B堆特征值的樣本算B特征。
3.基于第二點不同，我們可看出C4.5算法每選擇一個特征按各個特征值分類後，接下來的分類就不會再考慮該特征了（因為該特征已按特征值徹底劃分完了）。而CART算法是把特征值分成兩堆，假設有abcd四個特征，經過Gini增益計算後，ab為1堆，cd為2堆，那麼按照此分類後1堆和2堆該特征都沒有被完全劃分，1堆樣本還能對a和b特征值再進行劃分。
是以CART算法的特征在分類過程中可能重複出現，而C4.5隻能出現一次。
連續型特征離散化
連續型資料離散化的方法很多，最易懂的就是憑經驗離散化，
比如一批樣本集裡有身高特征(cm)，樣本的數值有：162,164,165,166,168,170,173,180
這個時候我們就可以憑借經驗或者想要統計的結果，對這組連續資料劃分一個離散範圍，如設定小于165的是一類，165到170的是一類，大于170的是一類，這樣就把連續資料離散化成一個範圍判斷了。
但憑借經驗進行範圍劃分明顯不靠譜，
我們可以利用ID3、C4.5、CART這些算法，将連續資料離散化。
簡單來講思路就是：
依次設立劃分點，然後數值小于該劃分點的資料分為一類，大于的分為另一類。
分别計算根據各個劃分點分類前後的資訊增益(ID3)或資訊增益率(C4.5)或Gini指數增益(CART)，選出使得增益達到最大的劃分點作為分類特征值。
至于劃分點的選擇，一般是将所有連續數值從小到大排序，每兩點間取平均數建立一次劃分點進行分類，并計算資訊增益或資訊增益率。