決策樹之條件熵與信息增益

決策樹是一種用於分類和回歸的演算法。

決策樹的基本流程如下圖所示：

從這個流程圖中可以看出，決策樹演算法的核心是如何選擇最優屬性。所以諸如ID3、C4.5和CART這些決策樹演算法的主要區別之一就是最優屬性選擇方法。

在了解幾種決策樹演算法的演進之前，先了解一下幾個核心概念。

在決策樹演算法的學習過程中，信息增益是屬性選擇的一個重要指標，它定義為一個特徵能夠為分類系統帶來多少信息，帶來的信息越多，說明該特徵越重要，相應的信息增益也就越大。

信息增益= 信息熵 - 條件熵

這個問題就可以用信息增益來度量。如果選擇一個特徵後，信息增益最大（信息不確定性減少的程度最大），那麼我們就選取這個特徵。

熵。

資訊理論中熵的概念：熵度量了事物的不確定性，越不確定的事物，它的熵就越大。具體的，隨機變數X的熵的表達式如下：

其中n代表X的n種不同的離散取值。而 代表了X取值為i的概率，log為以2或者e為底的對數。

條件熵。

我們的條件熵的定義是：定義為X給定條件下，Y的條件概率分布的熵對X的數學期望 。

設有隨機變數(X,Y)，其聯合概率分布為

條件熵H(Y|X)表示在已知隨機變數X的條件下隨機變數Y的不確定性。

下面推導一下條件熵的公式：

注意，這個條件熵，不是指在給定某個數（某個變數為某個值）的情況下，另一個變數的熵是多少，變數的不確定性是多少？而是期望！

因為條件熵中X也是一個變數，意思是在一個變數X的條件下（變數X的每個值都會取），另一個變數Y熵對X的期望。

假如我們有上面數據：

設隨機變數

我們可以統計出，嫁的個數為6/12 = 1/2

不嫁的個數為6/12 = 1/2

那麼Y的熵，根據熵的公式來算，可以得到

為了引出條件熵，我們現在還有一個變數X，代表長相是帥還是帥，當長相是不帥的時候，統計如下紅色所示：

可以得出，當已知不帥的條件下，滿足條件的只有4個數據了，這四個數據中，不嫁的個數為1個，佔1/4

嫁的個數為3個，佔3/4

那麼此時的

同理我們可以得到：

當已知帥的條件下，滿足條件的有8個數據了，這八個數據中，不嫁的個數為5個，佔5/8

嫁的個數為3個，佔3/8

那麼此時的

有了上面的鋪墊之後，我們終於可以計算我們的條件熵了，我們現在需要求：

H(Y|X = 長相）

也就是說，我們想要求出當已知長相的條件下的條件熵。

根據公式我們可以知道，長相可以取帥與不帥倆種

條件熵是另一個變數Y熵對X（條件）的期望。

公式為：

然後將上面已經求得的答案帶入即可求出條件熵！

這裡比較容易錯誤就是忽略了X也是可以取多個值，然後對其求期望！

其實條件熵意思是按一個新的變數的每個值對原變數進行分類，比如上面這個題把嫁與不嫁按帥，不帥分成了倆類。

然後在每一個小類裡面，都計算一個小熵，然後每一個小熵乘以各個類別的概率，然後求和。

我們用另一個變數對原變數分類後，原變數的不確定性就會減小了，因為新增了Y的信息，可以感受一下。不確定程度減少了多少就是信息的增益。