決策樹是機器學習中一種應用比較廣泛的一種模型，比較常用的集成模型GBDT以及XGBOOST都是基於決策樹。而且決策樹在生活中也所處可見，下面用一個圖例表示某一天的活動。

上面的圖例就是一個比較簡單的決策樹模型。決策樹模型是基於一系列的問題來進行決策的，在處理實際問題的時候會比上面樹要大的多。一顆決策樹通常都會包括一個根結點（明天做什麼？）、若干個內部結點（能夠繼續分）、若干個葉結點（不能繼續分）。葉結點對應的是決策的結果，其他的結點對應的是一個屬性的測試。每個結點包含的樣本集合根據屬性測試的結果被劃分到子結點中，根結點包含了所有的樣本。從根結點到子結點的路徑就是一個判定測試序列。決策樹的泛化能力比較強，而且還遵循分而治之的策略。決策樹又根據不同的劃分方式可以分為ID3決策樹、C4.5決策樹、CART決策樹。下面就介紹一下這些決策樹之間的區別。

一、ID3決策樹

信息熵(information entropy)是度量樣本集合純度的一種最常用的指標。一個樣本集合為D，D由n類樣本所組成，第k類樣本的概率為p(k)(k為1到n的任意值)，則樣本集合D的信息熵為

當p(k)=0時，p(k)*log2(p(k))=0，Ent(D)的最小值為0，Ent(D)的值越小純度越高，因為到Ent(D)=0時,p(k)=1。

集合D根據不同屬性a可以被分為{D1,D2,D3....}，利用屬性a對於集合D進行劃分的所獲得的信息增益為

信息增益越大，表示使用屬性a進行劃分的所獲得的純度提升越大。ID3決策樹進行屬性劃分的時候每次都是根據最大信息增益的屬性進行劃分的。為了便於大家理解下面通過一個西瓜分類的例子來說明一下

上面的17條西瓜數據定為集合D，可以根據屬性色澤、根蒂、敲聲、紋理、臍部、觸感五個屬性來劃分整個集合。首先，我們來計算每個屬性的信息增益。先計算色澤的信息增益，西瓜的色澤取值有青綠、烏黑、淺白。根據西瓜的色澤將集合D可以分為D(1)色澤為青綠、D(2)色澤為烏黑、D(3)色澤為淺白。通過觀察上面的表格可以發現，屬於D(1)的西瓜編號有{1,4,6,10,13,17},其中{1,4,6}為好瓜，{10,13,17}為壞瓜。屬於D(2)的西瓜編號有{2,3,7,8,9,15}，其中{2,3,7,8}為好瓜，{9,15}為壞瓜。屬於D(3)的西瓜編號有{5,11,12,14,16}，其中{5}為好瓜，{11,12,14,16}為壞瓜。所以，不同顏色的信息熵為

根結點的信息熵為

所以，西瓜色澤屬性對於集合D的信息增益為

通過上面的方法，我們可以獲得其他屬性的信息增益

然後，選擇信息增益最大的屬性進行劃分，劃分之後需要重新計算屬性的信息增益。

二、C4.5決策樹

ID3決策樹是使用信息增益來進行劃分的，而信息增益準則對於可取值數目較多的屬性有所偏好，為了減少這種偏好可能帶來的不利影響，C4.5決策樹不直接使用信息增益準則，而是使用增益率來進行屬性的劃分選擇的，增益率定義為

其中，a為集合D的某一屬性,n表示屬性a的取值數目。n越大，IV(a)越大。所以，增益率準則對於屬性取值數目較少的屬性有所偏好。因此，C4.5算法並不是直接使用增益率最大的候選劃分屬性，而是使用了一種啟發式的方式，先從候選屬性中選擇屬性的信息增益高於平均信息增益的屬性，然後再從這些屬性中選擇增益率最高的屬性。

三、CART決策樹

CART決策樹是使用基尼係數來選擇劃分屬性的。數據集D的純度用基尼值來定義為

從基尼值定義的公式來看，從集合D中隨機抽了兩個樣本i和j，兩個樣本類別不一致的概率。Gini(D)越小，則表示集合D中的純度越高。屬性a的基尼指數定義為

在使用基尼指數在候選屬性集合中，進行劃分的時候選擇使得劃分之後基尼指數最小的屬性作為最優劃分屬性。

參考：《機器學習》周志華