決策樹算法借助于樹的分支結構實現分類。下圖是一個決策樹的示例，樹的內部結點表示對某個屬性的判斷，該結點的分支是對應的判斷結果；葉子結點代表一個類標。

　　上表是一個預測一個人是否會購買購買電腦的決策樹，利用這棵樹，我們可以對新記錄進行分類，從根節點（年齡）開始，如果某個人的年齡為中年，我們就直接判斷這個人會買電腦，如果是青少年，則需要進一步判斷是否是學生；如果是老年則需要進一步判斷其信用等級，直到葉子結點可以判定記錄的類別。

　　決策樹算法有一個好處，那就是它可以產生人能直接理解的規則，這是貝葉斯、神經網絡等算法沒有的特性；決策樹的準確率也比較高，而且不需要了解背景知識就可以進行分類，是一個非常有效的算法。決策樹算法有很多變種，包括ID3、C4.5、C5.0、CART等，但其基礎都是類似的。下面來看看決策樹算法的基本思想：

算法：GenerateDecisionTree(D,attributeList)根據訓練數據記錄D生成一棵決策樹.

輸入：數據記錄D，包含類標的訓練數據集;

屬性列表attributeList，候選屬性集，用于在內部結點中作判斷的屬性.

屬性選擇方法AttributeSelectionMethod()，選擇最佳分類屬性的方法.

輸出：一棵決策樹.

過程：

構造一個節點N；

如果數據記錄D中的所有記錄的類標都相同（記為C類）：

則將節點N作為葉子節點標記為C，并返回結點N；

如果屬性列表為空：

則將節點N作為葉子結點標記為D中類標最多的類，并返回結點N；

調用AttributeSelectionMethod(D,attributeList)選擇最佳的分裂準則splitCriterion;

將節點N標記為最佳分裂準則splitCriterion;

如果分裂屬性取值是離散的，并且允許決策樹進行多叉分裂：

從屬性列表中減去分裂屬性，attributeLsit -= splitAttribute;

對分裂屬性的每一個取值j:

記D中滿足j的記錄集合為Dj;

如果Dj為空：

則新建一個葉子結點F，標記為D中類標最多的類，并且把結點F掛在N下;

否則：

遞歸調用GenerateDecisionTree(Dj,attributeList)得到子樹結點Nj，將Nj掛在N下;

返回結點N;

 　　算法的1、2、3步驟都很顯然，第4步的最佳屬性選擇函數會在后面專門介紹，現在只有知道它能找到一個準則，使得根據判斷結點得到的子樹的類別盡可能的純，這里的純就是只含有一個類標；第5步根據分裂準則設置結點N的測試表達式。在第6步中，對應構建多叉決策樹時，離散的屬性在結點N及其子樹中只用一次，用過之后就從可用屬性列表中刪掉。比如前面的圖中，利用屬性選擇函數，確定的最佳分裂屬性是年齡，年齡有三個取值，每一個取值對應一個分支，后面不會再用到年齡這個屬性。算法的時間復雜度是O(k*|D|*log(|D|))，k為屬性個數，|D|為記錄集D的記錄數。

三、屬性選擇方法

　　屬性選擇方法總是選擇最好的屬性最為分裂屬性，即讓每個分支的記錄的類別盡可能純。它將所有屬性列表的屬性進行按某個標準排序，從而選出最好的屬性。屬性選擇方法很多，這里我介紹三個常用的方法：信息增益（Information gain）、增益比率（gain ratio）、基尼指數（Gini index）。

信息增益（Information gain）

　　信息增益基于香濃的信息論，它找出的屬性R具有這樣的特點：以屬性R分裂前后的信息增益比其他屬性最大。這里信息的定義如下：

　　其中的m表示數據集D中類別C的個數，Pi表示D中任意一個記錄屬于Ci的概率，計算時Pi=(D中屬于Ci類的集合的記錄個數/|D|)。Info(D)表示將數據集D不同的類分開需要的信息量。

　　如果了解信息論，就會知道上面的信息Info實際上就是信息論中的熵Entropy，熵表示的是不確定度的度量，如果某個數據集的類別的不確定程度越高，則其熵就越大。比如我們將一個立方體A拋向空中，記落地時著地的面為f1，f1的取值為{1,2,3,4,5,6}，f1的熵entropy(f1)=-(1/6*log(1/6)+…+1/6*log(1/6))=-1*log(1/6)=2.58；現在我們把立方體A換為正四面體B，記落地時著地的面為f2，f2的取值為{1,2,3,4}，f2的熵entropy(1)=-（1/4*log(1/4)+1/4*log(1/4)+1/4*log(1/4)+1/4*log(1/4)) =-log(1/4)=2；如果我們再換成一個球C，記落地時著地的面為f3，顯然不管怎么扔著地都是同一個面，即f3的取值為{1}，故其熵entropy(f3)=-1*log(1)=0?？梢钥吹矫鏀翟蕉?，熵值也越大，而當只有一個面的球時，熵值為0，此時表示不確定程度為0，也就是著地時向下的面是確定的。

　　有了上面關于熵的簡單理解，我們接著講信息增益。假設我們選擇屬性R作為分裂屬性，數據集D中，R有k個不同的取值{V1,V2,…,Vk}，于是可將D根據R的值分成k組{D1,D2,…,Dk}，按R進行分裂后，將數據集D不同的類分開還需要的信息量為： 

　　信息增益的定義為分裂前后，兩個信息量只差：

　　信息增益Gain(R)表示屬性R給分類帶來的信息量，我們尋找Gain最大的屬性，就能使分類盡可能的純，即最可能的把不同的類分開。不過我們發現對所以的屬性Info(D)都是一樣的，所以求最大的Gain可以轉化為求最新的InfoR(D)。這里引入Info(D)只是為了說明背后的原理，方便理解，實現時我們不需要計算Info(D)。舉一個例子，數據集D如下：

　　這個數據集是根據一個人的年齡、收入、是否學生以及信用等級來確定他是否會購買電腦，即最后一列“是否購買電腦”是類標?，F在我們用信息增益選出最最佳的分類屬性，計算按年齡分裂后的信息量：

　　整個式子由三項累加而成，第一項為青少年，14條記錄中有5條為青少年，其中2（占2/5）條購買電腦，3（占3/5）條不購買電腦。第二項為中年，第三項為老年。類似的，有：

　　可以得出Info年齡(D)最小，即以年齡分裂后，分得的結果中類標最純，此時已年齡作為根結點的測試屬性，根據青少年、中年、老年分為三個分支：

　　注意，年齡這個屬性用過后，之后的操作就不需要年齡了，即把年齡從attributeList中刪掉。往后就按照同樣的方法，構建D1,D2,D3對應的決策子樹。ID3算法使用的就是基于信息增益的選擇屬性方法。

增益比率（gain ratio）

　　信息增益選擇方法有一個很大的缺陷，它總是會傾向于選擇屬性值多的屬性，如果我們在上面的數據記錄中加一個姓名屬性，假設14條記錄中的每個人姓名不同，那么信息增益就會選擇姓名作為最佳屬性，因為按姓名分裂后，每個組只包含一條記錄，而每個記錄只屬于一類（要么購買電腦要么不購買），因此純度最高，以姓名作為測試分裂的結點下面有14個分支。但是這樣的分類沒有意義，它每一任何泛化能力。增益比率對此進行了改進，它引入一個分裂信息：

　　增益比率定義為信息增益與分裂信息的比率：

　　我們找GainRatio最大的屬性作為最佳分裂屬性。如果一個屬性的取值很多，那么SplitInfoR(D)會大，從而使GainRatio(R)變小。不過增益比率也有缺點，SplitInfo(D)可能取0，此時沒有計算意義；且當SplitInfo(D)趨向于0時，GainRatio(R)的值變得不可信，改進的措施就是在分母加一個平滑，這里加一個所有分裂信息的平均值：

基尼指數（Gini index）

　　基尼指數是另外一種數據的不純度的度量方法，其定義如下：

其中的m仍然表示數據集D中類別C的個數，Pi表示D中任意一個記錄屬于Ci的概率，計算時Pi=(D中屬于Ci類的集合的記錄個數/|D|)。如果所有的記錄都屬于同一個類中，則P1=1，Gini(D)=0，此時不純度最低。在CART(Classification and Regression Tree)算法中利用基尼指數構造二叉決策樹，對每個屬性都會枚舉其屬性的非空真子集，以屬性R分裂后的基尼系數為：

　　D1為D的一個非空真子集，D2為D1在D的補集，即D1+D2=D，對于屬性R來說，有多個真子集，即GiniR(D)有多個值，但我們選取最小的那么值作為R的基尼指數。最后：

　　我們轉Gini(R)增量最大的屬性作為最佳分裂屬性。