決策樹方法在分類、預測等領域有廣泛的應用，在機器學習研究者Quinlan提出ID3算法之後，決策樹在機器學習、數據挖掘領域得到極大的發展。

ID3算法：該算法是以信息論為基礎，以信息熵和信息增益為衡量標準，從而實現對數據的歸納分類。根據信息論理論，採用劃分後樣本集的不確定性作為衡量劃分好壞的標準，用信息增益度量不確定性：信息增益越大，不確定性越小

信息增益

其中P(x)表示事件x出現的概率

例如：一個盒子中分別有5個白球和5個紅球，隨機取出一個球，問，這個球是紅色還是白色？這個問題信息量多大呢？由於紅球和白球出現的概率都是1/2，那麼久可以得到其信息熵為：H(x)=-(1/2*log2(1/2)+1/2log2(1/2))=1，是的，這個信息量是1bit。

如果一個盒子裡有10個紅球，隨機取出一個，這個球什麼顏色？這個問題的信息量是多少？信息量是0，因為這是一個確定事件，概率P(x)=1

信息熵其實是一個隨機變量信息量的數學期望。

參考一個別人的例子：

1，計算總信息熵。數據記錄34條，銷量為高的有18條，為低的16條

總信息熵H(x)=-(18/34)*log2(18/34)-(16/34)*log2(16/34)=0.997503

2,計算各個屬性的信息熵

對於天氣，屬性值有好與壞，其中好天氣下，銷量為高的記錄11條，為低的記錄6條

在壞天氣下，銷量為高記錄7條，為低的記錄10條

H(天氣=好)= -(11/17)*log2(11/17)-(6/17)*log2(6/17)=0.936667

H(天氣=壞)= -(7/17)*log2(7/17)-(10/17)*log2(10/17)=0.977418

H(天氣)=(17/34)* H(天氣=好)+(17/34)* H(天氣=壞) = 0.957043

對於是否週末，屬性值有是與否，其中是週末下，銷量為高的記錄11條，為低的記錄3條

在否週末下，銷量為高記錄7條，為低的記錄13條

H(週末=是)= -(11/14)*log2(11/14)-(3/14)*log2(3/14)=0.749595

H(週末=否)= -(7/20)*log2(7/20)-(13/20)*log2(13/20)=0.934068

H(週末)=(14/34)* H(週末=是)+(10/34)* H(週末=否) = 0.858109

對於是否促銷，屬性值有是與否，其中促銷下，銷量為高的記錄15條，為低的記錄7條

在否促銷下，銷量為高記錄3條，為低的記錄9條

H(促銷=是)= -(15/22)*log2(15/22)-(7/22)*log2(7/22)=0.902393

H(促銷=否)= -(3/12)*log2(3/12)-(9/12)*log2(9/12)=0.811278

H(促銷)=(22/34)* H(促銷=是)+(12/34)* H(促銷=否) = 0.870235

3，計算天氣，是否週末，是否促銷的信息增益值

Gain(天氣)= H(x)- H(天氣)=0.04046

Gain(是否週末)= H(x)- H(週末)=0.139394

Gain(是否促銷)= H(x)- H(促銷) = 0.127268,4

4，由第三步可知，是否週末的信息增益最大，他的兩個屬性'是'，'否'作為跟結點的兩個分支，

然後從未被選擇的特徵中繼續進行一至三步，選擇最優數據劃分特徵來劃分子數據集，

何時停止？一是一直到所有的特徵都用完了，二是劃分後額信息增益足夠小，就可以停止了，最終構成一顆決策樹

信息熵與概率的關係圖如下：

可以看出，當概率P(x)越接近0或者1是，信息熵越小，其不確定性越小，即數據越純，我們在選擇特徵時，選擇信息增益最大的特徵，即，讓數據儘量往更純淨的方向上變換，因此，信息增益是用來衡量數據變得更有序、更純淨的指標。

1,數據離散化

如果一個特徵時連續值怎麼辦？此時需要進行離散化，對連續數據進行離散化處理，比如：

當成績大於90標識為優，當成績大於70小於90，標識為良，當成績大於60小於70，標識為及格，當成績小於60標識為不及格

經過離散化處理就可以構建決策樹了

2，正則項

信息增益的一個大問題就是容易造成偏向選擇分支多的屬性導致，那麼我們能想到的解決辦法就是加上一個與類別個數成正比的正則項來作為最終的信息熵，這樣當算法選擇的某個類別較多的特徵，是信息熵較小的時候，受到正則項的懲罰，最終導致信息熵也比較大，這樣通過合適的參數，可以是算法訓練得到平衡

另外一個解決辦法是使用信息增益比來作為特徵選擇的標準，就是特徵的增益值除以特徵熵，可以解決優先選取類別多的特徵的問題

3，基尼不純度

信息熵是衡量信息不確定性的指標，實際上是 衡量信息純度的指標，除此之外，基尼不純度也是衡量信息不純度的指標，公式如下：

P(x)是樣本屬於x類別的概率

如圖：

可以看出，其形狀和信息熵的幾乎一樣

解決過擬合問題

使用決策樹模型擬合數據時，容易過擬合，解決過擬合的方法一般是對決策樹進行剪枝，有兩種思路，前剪枝和後剪枝

1，前剪枝

前剪枝是在構建決策樹的同時進行剪枝，在構建過程中，如果無法進一步降低信息熵，就是停止創建分支，為了避免過擬合，可以設定一個閾值，當信息熵減小的數量小於這個閾值，計算還會降低熵，也要停止繼續創建分支。還可以限制葉子節點樣本個數，當樣本個數小於設定值，則不再繼續創建分支

2，後剪枝

後剪枝是在決策樹構建完成後進行剪枝。剪枝的過程就是對擁有同樣父節點的一組節點進行檢查，判斷其如果合併是否信息熵的增加量小於某一個閾值，如果小於閾值，這一組節點可以合併成一個節點。

閱讀更多 愛數據的小司機 的文章

關鍵字: 科普 技術 機器學習