信息增益、信息增益比、基尼指數的比較

2020 年 6 月 6 日
筆記
決策樹, 機器學習, 特徵劃分

ID3、C4.5和CART三種經典的決策樹模型分別使用了信息增益、信息增益比和基尼指數作為選擇最優的劃分屬性的準則來構建決策樹。以分類樹來說，構建決策樹的過程就是從根節點(整個數據集)向下進行節點分裂(劃分數據子集)的過程，每次劃分需要讓分裂後的每個子集內部儘可能包含同一類樣本。信息增益和信息增益比都是和香農信息熵有關的衡量信息不確定度的量，因此下面首先介紹一下香農信息熵。

香農信息熵

說到信息熵和香農就想起了當年被《信息論》支配的恐懼，但是香農真的很帥哈哈！言歸正傳，信息熵是香農從熱力學的「熵」借鑒過來用來衡量信息不確定度的一個物理量。決策樹種將信息熵拿來衡量集合中樣本混亂程度，西瓜書中用的「純度」一詞，其實也就是集合中樣本類別數越少，樣本越屬於同一類別，集合的純度越高，混亂程度（信息熵）越低。
對於集合 \(D\)，包含的類別數為 \(K\)，則集合的信息熵這樣計算：

\[Ent(D)=-\sum_{k=1}^{K}p_{k}log_2p_k \tag{1}
\]

其中 \(|C_k|\) 表示 \(D\)中第 \(k\) 類樣本的數量，\(p_k = \frac{|C_k|}{|D|}\) 表示集合 \(D\)中第 \(k\) 類樣本的比例。\(Ent(D)\) 越小則集合 \(D\) 的純度越高，注意到\(Ent(D)\)總是大於等於0的。

信息增益

ID3使用信息增益來選擇最優劃分屬性，也就是選擇某個屬性，使得通過此屬性對數據集進行劃分後，信息增益最大。信息增益定義如下

\[Gain(D, a)=Ent(D)-\sum_{v=1}^{V}\frac{\left|D^v\right|}{|D|}Ent(D^v) \tag{2}
\]

式中 \(a\) 表示用來劃分數據集的屬性，有 \(V\) 個不同的離散值（注意：這裡包括後面信息增益率和基尼指數只討論離散特徵的情況，連續特徵最後面會講到）。上式表達的物理意義就是：對於屬性 \(a\)，按照不同的取值進行劃分，將數據集 \(D\) 分成 \(V\) 個不同的子集，用數據集 \(D\) 的信息熵減去劃分後所有子集信息熵的加權和(權重為每個子集樣本數佔總集合的比例)得到的差值。ID3決策樹想要找到使得式(2)信息增益最大的屬性 \(a\) 對數據集進行劃分。
怎麼理解呢？上面提到，信息熵用來衡量信息的純度，我們的目的是讓劃分後每個子集的純度儘可能大(也就是讓式(2)中減數項盡量小)，由於集合 \(D\) 的純度是確定的，那麼讓式(2)中減數項盡量小也就是讓 \(Gain(D, a)\) 盡量大。
這裡我其實一直有個疑問——既然集合 \(D\) 的純度是確定的，劃分的時候只需要讓 \(\sum_{v=1}^{V}\frac{\left|D^v\right|}{|D|}Ent(D^v)\)這一項盡量小就可以了，為什麼要多此一舉計算一下信息增益？可能「增益」這個詞更能表達我們做某個決策給我們帶來的收益？(胡亂猜想)
缺點：通過信息增益來選擇特徵會偏好取值較多的特徵，一個極端情況的例子就是如果對於某個特徵所有樣本在此特徵上的取值都不相同，這樣通過這個特徵計算得到的信息增益式最大的，可以計算一下 \(Ent(D^v)\) 是等於0的。

信息增益率

C4.5決策樹每次分裂的時候選擇信息增益率最大的特徵進行劃分。信息增益率提出就是為了解決上面所說的缺點，定義如下：

\[Gain\_ratio(D, a)=\frac{Gain(D, a)}{H(a)} \tag{3}
\]

其中

\[{H(a)}=-\sum_{v=1}^{V}\frac{\left|D^v\right|}{|D|}\log_2 \frac{\left|D^v\right|}{|D|} \tag{4}
\]

\({H(a)}\) 稱為數據集 \(D\) 關於 \(a\) 的取值熵或固有值。屬性 \(a\) 的取值數目越多 \({H(a)}\) 越大，因此將原有的信息增益除以 \({H(a)}\) 相當於對其進行了懲罰，避免了信息增益偏好取值較多特徵的問題。
缺點：信息增益率朝着信息增益相反的方向發展，偏好於取值較少的特徵。
關於C4.5使用信息增益比來選擇特徵知乎有個討論貼，有大佬數學證明了一下，還有大佬貼出來原作者的解釋了，鏈接放在文末了有興趣的可以去圍觀一波。

基尼指數(Gini index)

基尼指數的數學計算

基尼制數是衡量數據集純度的另一種方式，定義如下：

\[Gini(D)=\sum_{k=1}^{K} \sum_{k^{\prime} \neq k} p_{k} p_{k^{\prime}}=1-\sum_{k=1}^{K} p_{k}^{2} \tag{5}
\]

其中 \(p_k=\frac{|C_k|}{|D|}\) 表示數據集中 \(k\) 類樣本的比例，因此

\[Gini(D)=1-\sum_{k=1}^{K} \frac{|C_k|}{|D|} \tag{6}
\]

基尼指數的物理意義就是從數據集 \(D\) 中隨機抽取兩個樣本，他們類別不一樣的概率，因此基尼指數越小表明數據集 \(D\) 的中同一類樣本的數量越多，其純度越高。這樣，將數據集按屬性 \(a\)進行劃分後的基尼指數為

\[Gini(D,a)=\sum_{v=1}^{V} \frac{|D^v|}{|D|}Gini(D^v) \tag{7}
\]

CART樹的劃分方式

不同於ID3和C4.5，CART樹是一種二叉樹，也就是說每次分裂節點的時候，僅將當前節點的數據集合分成兩部分，分別進入左右子樹。那麼怎麼劃分呢？這裡先說離散特徵。
對於離散特徵 \(a\)，有 \(V\) 個不同的取值，當以取值 \(v\) 劃分時，基尼指數這樣計算：

\[Gini(D,a,v)=\frac{|D^v|}{|D|}Gini(D^v)+ \frac{|\widetilde{D}^v|}{|D|}Gini(\widetilde{D}^v)\tag{8}
\]

其中 \(\widetilde{D}^v\) 表示數據集 \(D\) 中特徵 \(a\) 取值不為 \(v\) 的樣本集合。這樣，遍歷所有的特徵和特徵的取值，選擇使得 \(Gini(D,a,v)\) 最小的 \(a\) 和 \(v\) 進行劃分，將數據集合劃分為在特徵 \(a\) 上等於 \(v\) 和不等於 \(v\) 的兩部分，進入左右子樹。

三種劃分方式的差異

適用情況

上面分別對三種劃分準則進行了梳理，其中信息增益和信息增益率通常用於離散型的特徵劃分，ID3和C4.5通常情況下都是多叉樹，也就是根據離散特徵的取值會將數據分到多個子樹中；而CART樹為二叉樹，使用基尼指數作為劃分準則，對於離散型特徵和連續行特徵都能很好的處理。

連續特徵的處理

《百面機器學習》一書中最後總結部分說ID3隻能處理離散型變量，而4.5和CART都可以處理連續型變量。我個人不太認同這個說法，CART可以處理連續變量是毋庸置疑的，只需要對所有特徵取值進行排序，然後取每兩個相鄰值的平均值作為切分點進行切分計算當前劃分方式下的基尼指數，最後取基尼指數最小的特徵和切分點進行劃分即可，和上面的離散特徵類似。那麼，採用信息增益和信息增益率的時候也可以這樣對連續特徵進行劃分得到最優分割特徵和最優劃分點。

參考資料

西瓜書
《百面機器學習》
c4.5為什麼使用信息增益比來選擇特徵？

Tags: 決策樹機器學習特徵劃分