經典的決策樹演算法

07-06

經典的決策樹演算法

來自專欄機器學習，深度學習，複雜網路，演算法

最近在整理基礎演算法和模型，從邏輯回歸，到樹，在到網路各種演算法，今天分享一篇感覺不錯的文章給大家

回歸與分類

我們在機器學習中一直會遇到兩種問題，一種是回歸問題，一種是分類問題。我們從字面上理解，很容易知道分類問題其實是將我們現有的數據分成若干類，然後對於新的數據，我們根據所分得類而進行劃分；而回歸問題是將現有數據擬合成一條函數，根據所擬合的函數來預測新的數據。

這兩者的區別就在於輸出變數的類型。回歸是定量輸出，或者說是預測連續變數；分類問題書定量輸出，預測離散變數。Po一張我在知乎上看到的一張圖片，解釋的很好：

如何區分分類與回歸，看的不是輸入，而是輸出。舉個例子，預測明天晴或是雨，是分類問題，而預測明天多少度，則是回歸問題。

回歸樹與分類樹

在決策樹中，也有回歸樹與分類樹的概念。

在二者的區別中，回歸樹是採用最大均方誤差來劃分節點，並且每個節點樣本的均值作為測試樣本的回歸預測值；而分類樹是採用信息增益或者是信息增益比來劃分節點，每個節點樣本的類別情況投票決定測試樣本的類別。我們可以看到，這兩者的區別主要在於劃分方式與工作模式。回歸樹採用最大均方誤差這種對數據精確處理的方式，輸出連續變數，可以更好地給我們的數據進行預測；而分類樹使用一個非常寬泛的信息增益這個變數，更好的從整體把握這個數據集的分類。

信息增益

這是信息增益的定義。可能理解起來非常之簡單，新加的一個節點與原來系統的互信息。也就是多考慮一個特徵值給我們整個決策環節多提供的信息量。但是我們一定要注意信息增益的計算過程，這裡我貼上《統計學習方法》中的例子，來給大家參考：

在《數學之美》這本書里，吳軍博士曾經告誡過:對於更好地判斷一件事物是正確還是錯誤，唯一方法是引入更多的信息量。那我們對於這個判決樹，當然傾向於選擇自身不確定性更大的特徵，因為自身不確定性越大，一旦被確定下來，引入的信息量就越多。這樣的話，對於整個系統判決更加有效。

信息增益比

信息增益比，有的書也叫信息增益率。資料比信息增益少很多。區別就是在信息增益的基礎上再除以一個總的熵。具體有什麼好處呢，我們在下面C4.5演算法中會提到。

不過同樣的，我們依舊最需要注意這個信息增益比的計算過程，信息增益我們都會計算了，這個總的熵我們與上面講的H(D)一致。再相除就得到了我們所想要的結果了。

ID3演算法

ID3演算法的核心實在決策樹上的各個節點上用信息增益選擇特徵。在ID3演算法生成樹的時候，是先計算所有備選特徵的信息增益，然後再選擇下一個節點是哪一個特徵。

在這個信息增益的定義及公式中，我們一定要注意這個H(D)的演算法。我們求解一整個集合的熵，一般是求解

信息增益直接影響了我們選擇什麼節點來作為下一個特徵的操作，並且設置一個閾值e，當信息增益小於這個閾值的時候停止循環。

為了不影響大家理解，我將這個演算法完整的寫在這：

ID3：

輸入：訓練數據集D,特徵集A，閾值e；

輸出 : 決策樹T

1、若D中國所有實例屬於同一類Ck，則T為單結點樹，並將Ck作為該結點的類標記，返回T；

2、若A=空集，則T為單結點樹，並將D中的實例數最大的類Ck作為該結點的類標記，返回T；

3、否則，計算A中各特徵對D的信息增益，（具體怎麼計算請看我前一條關於決策樹基礎的博客）選擇信息增益最大的特徵Ag；

4、如果Ag的信息增益小於閾值e，則置T為單結點樹，並將D中實例數最大的類Ck作為該結點的類標記，返回T；

5、否則，對Ag的每一個可能值ai；依Ag=ai將D分割為若干非空子集Di；將Di中實例數最大的類作為標記，構建子結點，由結點及其子結點構成樹T，返回T；

6、對第i個子結點，以Di為訓練集，以A-{Ag}為特徵集，遞歸調用（1）~（5），得到子樹Ti，返回Ti。

為了加深大家的理解，我貼上李航著的《統計學習方法》裡面的例子:

ID3演算法只有樹的生成，並沒有對於擬合程度的控制或者是削減分支，所以該演算法產生的樹容易產生過擬合。

C4.5演算法

C4.5演算法與ID3演算法非常相似，是對其的一種改進。唯一與ID3不同的是 C4.5採用信息增益比而不是信息增益來選擇特徵。

貼出C4.5演算法：

輸入：訓練數據集D,特徵集A，閾值e；輸出:決策樹T

若D中所有實例屬於同一類Ck，則T為單結點樹，並將Ck作為該結點的類標記，返回T；

若A=空集，則T為單結點樹，並將D中的實例數最大的類Ck作為該結點的類標記，返回T；

否則，計算A中各特徵對D的信息增益，（具體怎麼計算請看我前一條關於決策樹基礎的博客）選擇信息增益最大的特徵Ag；

如果Ag的信息增益小於閾值e，則置T為單結點樹，並將D中實例數最大的類Ck作為該結點的類標記，返回T；

否則，對Ag的每一個可能值ai；依Ag=ai將D分割為若干非空子集Di；將Di中實例數最大的類作為標記，構建子結點，由結點及其子結點構成樹T，返回T；

對第i個子結點，以Di為訓練集，以A-{Ag}為特徵集，遞歸調用（1）~（5），得到子樹Ti，返回Ti。

我們為什麼說C4.5是對ID3的一種改進呢？這個問題我們得從二者區別也就是信息增益與信息增益比說起。

我們再次貼上信息增益與信息增益比的定義：

通過對比我們可以看出，信息增益就是特徵與訓練集的互信息，或者說原來數據集的不確定性與確定其中一個特徵之後的不確定性之差，稱做信息增益。也就是確定這個特徵所引入的信息量。而信息增益比則是這一個互信息與D的不確定性的比值。

當我們遇到一個取值很多的屬性的時候，比如西瓜的品種這個屬性，會有好幾十種品種，也就是好幾十種取值。通過計算我們會發現，這類屬性的不確定性要比那些只有一兩個取值的屬性要大（因為取值很多使得整個數據集的混亂程度很大），所以計算機如果處理的時候優先選擇取值多的屬性。

所以C4.5在ID3的基礎上，採用了信息增益比這個判決方法，來懲罰取值很多的屬性。