從熵概念到決策樹演算法

一、熵

熵可以認為是對無序的一種度量，熵越大越無序，熵越小越有序。

信息熵是將熵的理論應用於信息混亂度的描述，在隨機變數中可以描述隨機變數不確定性的程度，在機器學習的樣本集合中，可以用於描述樣本集合的純度。

假定樣本集合D中第k類樣本所包含的樣本數所佔總樣本數的比例為則D的信息熵可以定義為：

此文，可以以一個實際例子來做說明，該樣本集合較簡單，樣本如下：

從上述樣本集合中可以看出，該樣本共有四個屬性，分別為outlook、temperature、humidity、windy，最終分類結果只有兩個，yes和no，即建模的目的就是根據天氣情況來判斷當前是否適合出去運動。那麼，根據前面介紹的方法，就可以利用熵這個指標來描述一下當前樣本集合D的混亂程度，本文的計算將全部使用python語言來描述：

所以，訓練集合D在未進行分類的情況下，其樣本集合的熵為0.94。

了解了熵的概念以後，就可以引出今天我們主要的話題，決策樹演算法了，決策樹演算法是機器學習演算法中較常用的一種演算法，該演算法最常用於分類問題，比如根據西瓜的根蒂、紋理來判斷該瓜是熟瓜還是不熟瓜等，決策樹演算法較為簡單、易於理解，並且其結果最終又可以總結成規則，是一種應用十分廣泛的演算法。

首先，先介紹一下決策樹演算法，然後再展開具體講每個細節，決策樹演算法最終生成的結果是一顆樹，其中節點是屬性，節點間的分支是該屬性對應的值，從根到葉子結點就是一個判斷的流程。

決策樹學習的基本演算法如下：

輸入：訓練集D={(x1,y1),(x2,y2),(x3,y3),…,(xm,ym)}

屬性集A=

過程：函數TreeGenerate(D,A)

1、生成節點node

2、如果D中樣本全部屬於同一個類別C then將node標記為C類葉節點並返回

3、如果A=或者D中樣本在A上的取值均相同，則將node標記為葉節點，其類別標記為D中樣本最多的類

4、如果上面兩個條件不存在，在需要根據屬性來劃分，從A中選擇最優劃分屬性（如何找到最優劃分屬性後面講解），對於中的每一個屬性裡面的值都可以將樣本集合D生成一個分支，且可以用來表示在上取值為的樣本子集

5、如果為空，則將該分支節點標記為葉節點，其類別標記為D中樣本最多的類（因為為空，沒有類別，用父類別）

6、如果不為空，則繼續遞歸執行TreeGenerate(,A{})

根據上面的步驟就可以構造出一顆決策樹，不過，裡面有一點也是非常重要的一點就是如何去不斷找到最優屬性，也就是此時需要有一個衡量標準，能夠根據這個標準來衡量那個屬性可以作為最優屬性，此時就引入了信息增益的概念：

上面的公式就是決策樹演算法的信息增益。

其中D表示樣本集D，假定屬性a有v個可能的取值（離散或連續），在選擇最優劃分屬性的時候，比如先找到了a屬性，然後接著需要計算下並比較下a屬性是否是最優劃分屬性，也就是需要給屬性a一個打分，屬性a判斷完成後，接著再判斷下一個屬性，給每個屬性都一個打分，然後選擇得分最高的那個作為最優劃分屬性，於是，當拿到屬性a的時候，根據a的不同取值（1到v）就可以把樣本集D劃分成v個樣本子集，然後每個值對應的樣本子集又有一個或者多個類別，就可以計算出這個值的樣本子集所對應的熵，將所有值對應的樣本子集的熵相加就變成了這個屬性a的熵，即，又因為不同的取值所分成的樣本集合數量不同，越多的，說明此種情況更容易出現，所以可以給每個值對應的熵加上一個所佔比例的權重，用來表示，則屬性a劃分數據集D的熵就是，此時a的熵越小，說明劃分能力越強，然後此時可以用一個減少量去衡量，即使用上面公式來衡量，因為對於數據集D而言，Ent(D)是固定的，所以減去的數值越小就越大，即減少量就越大，即就可以用于衡量該屬性劃分能力的強弱，且該值越大，劃分能力越強，於是通過該值可以對所有屬性進行選擇了，不過這只是ID3演算法的標準，本文將以最簡單的ID3為例子講解。

好了，到這裡決策樹基本演算法的東西就講完了，這樣看來決策樹演算法還是很簡單易懂的，不過後面還有剪枝和調參數的很多東西，此時，可以先根據上面的理論得到前面天氣數據集的最優劃分屬性：