決策樹算法借助于樹的分支結(jié)構(gòu)實現(xiàn)分類。下圖是一個決策樹的示例，樹的內(nèi)部結(jié)點表示對某個屬性的判斷，該結(jié)點的分支是對應(yīng)的判斷結(jié)果；葉子結(jié)點代表一個類標(biāo)。

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

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

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

輸入：數(shù)據(jù)記錄D，包含類標(biāo)的訓(xùn)練數(shù)據(jù)集;

屬性列表attributeList，候選屬性集，用于在內(nèi)部結(jié)點中作判斷的屬性.

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

輸出：一棵決策樹.

過程：

構(gòu)造一個節(jié)點N；

如果數(shù)據(jù)記錄D中的所有記錄的類標(biāo)都相同（記為C類）：

則將節(jié)點N作為葉子節(jié)點標(biāo)記為C，并返回結(jié)點N；

如果屬性列表為空：

則將節(jié)點N作為葉子結(jié)點標(biāo)記為D中類標(biāo)最多的類，并返回結(jié)點N；

調(diào)用AttributeSelectionMethod(D,attributeList)選擇最佳的分裂準(zhǔn)則splitCriterion;

將節(jié)點N標(biāo)記為最佳分裂準(zhǔn)則splitCriterion;

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

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

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

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

如果Dj為空：

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

否則：

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

返回結(jié)點N;

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

三、屬性選擇方法

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

信息增益（Information gain）

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

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

　　如果了解信息論，就會知道上面的信息Info實際上就是信息論中的熵Entropy，熵表示的是不確定度的度量，如果某個數(shù)據(jù)集的類別的不確定程度越高，則其熵就越大。比如我們將一個立方體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；現(xiàn)在我們把立方體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?？梢钥吹矫鏀?shù)越多，熵值也越大，而當(dāng)只有一個面的球時，熵值為0，此時表示不確定程度為0，也就是著地時向下的面是確定的。

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

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

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

　　這個數(shù)據(jù)集是根據(jù)一個人的年齡、收入、是否學(xué)生以及信用等級來確定他是否會購買電腦，即最后一列“是否購買電腦”是類標(biāo)。現(xiàn)在我們用信息增益選出最最佳的分類屬性，計算按年齡分裂后的信息量：

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

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

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

增益比率（gain ratio）

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

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

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

基尼指數(shù)（Gini index）

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

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

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

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