數學 · 決策樹（二）· 信息增益

01-27

從直觀來說，所謂信息增益，就是反映數據 A 能夠給我們帶來多少信息的一個度量。為了介紹信息增益，我們需要先弄明白什麼是條件熵 $H(Y | A)$

它是基於熵定義的。需要注意的是，此時我們要關心的就不僅僅是「因變數」 Y，也要關心「自變數」 A。我們的最終目的，是根據 A 來判斷 Y，這就有了條件熵的概念
先說直觀理解：所謂條件熵，就是根據 A 的不同取值把 Y 分成好幾份，對這些分開後的 Y 分別計算熵、再通過某種方式把這些熵合起來，得到總的條件熵。換句話說，就是將被 A 分開的各個部分的 Y 的混亂程度「加總」從而得到條件熵
所以，如果條件熵 $H(Y | A)$ 越小，就意味著 Y 被 A 分開後的總的混亂程度越小、從而意味著 A 更能夠幫助我們做出決策（感謝評論區 @小蟲子的提醒，這裡之前的概念敘述和信息增益混淆了）
接下來就是數學定義：

其中

它們的數學內涵我們會在下面具體應用時講到。需要指出的是，認為 $0log0 = 0$

定義完條件熵後，就可以來看信息增益了。由我上面說的直觀理解，可能不少童鞋已經猜到了它的數學定義

對於具體的問題、比如決策樹生成演算法而言，我們需要使用經驗熵來估計真正的熵：

其中：

$left| C_{k} right|$ 、 $left| Y right|$ 表示第 k 類的個數和總樣本數，從而 $frac{left| C_{k} right|}{left| Y right|}$ 是 $p_{k}$ 的估計（這裡其實就是頻率估計概率的思想。舉個栗子，如果你去抽了一百次獎、也就是說 $left| Y right| = 100$ ，用 $left| C_{0} right|$ 表示你中獎次數的話，假設中了一次獎、也就是說 $left| C_{0} right| = 1$ ，我們就估計這個抽獎）
n 是 A 的取值的個數，根據 A 的這 n 個取值可以將 Y 分成 n 份。把 $Y_{i}$ 當成 $Y$ ，結合前面 $H(Y)$ 的定義、可以得知定義中各個東西的數學內涵：

$Y_{i}$ 就是 $Y$ 的第 i 份， $left| Y_{ik} right|$ 代表著 $Y_{i}$ 中第 k 類的個數
$frac{left| Y_{i} right|}{left| Y right|}$ 是 $p_{i}$ 的估計， $frac{left| Y_{ik} right|}{left| Y_{i} right|}$ 是 $p_{ik}$ 的估計，思想同樣是頻率估計概率
所謂的

其實就是 $Y_{i}$ 的熵 $H(Y_{i})$ （也可以寫成 $H(Y | A = x_{i})$ ）
那麼 $H(Y_{i})$ 前面的係數 $frac{left| Y_{i} right|}{left| Y right|}$ 是什麼呢？它代表著 $Y_{i}$ 這一份樣本的重要程度。 $left| Y_{i} right|$ 越大、也就是說 $Y_{i}$ 中樣本越多，意味著 $Y_{i}$ 的混亂程度、也就是說 $H(Y_{i})$ 越應該得到重視

但如果簡單地以 $g(Y, A)$ 作為決策樹的生成演算法（也就是 ID3 演算法）的話、會存在偏向於選擇取值較多、也就是 n 比較大的特徵的問題。我們可以從直觀上去理解為什麼這是個問題：

我們希望得到的決策樹應該是比較深（又不會太深）的決策樹，從而它可以基於多個方面而不是片面地根據某些特徵來判斷
如果單純以 $g(Y, A)$ 作為標準，由於 $g(Y, A)$ 的直觀意義是 Y 被 A 劃分後混亂程度的減少量，可想而知，當 A 的取值很多時，Y 會被 A 劃分成很多份、從而其混亂程度自然會減少很多、從而 ID3 演算法會傾向於選擇 A 作為劃分依據。但如果這樣做的話、可以想像、我們最終得到的決策樹將會是一顆很胖很矮的決策樹（……）、這並不是我們想要的

為解決這個問題，我們需要給 n 一個懲罰，信息增益比的概念因而誕生了（對應於 C4.5 演算法）：

其中 $H_{A}{(Y)}$ 是 Y 關於 A 的熵，它的定義為：

由熵的內涵我們可以得知， $H_{A}Y$ 總體上而言會隨 n 的增大而增大

以上，我們大概講了一下信息增益相關的數學知識，它對應的是決策樹中的生成演算法。我們會在下一章介紹一下決策樹剪枝演算法一些相關的數學定義

希望觀眾老爺們能夠喜歡~

（猛戳我進入下一章！( σω)σ）