決策樹2: 特徵選擇中的相關概念

2019 年 12 月 23 日
筆記

0x00 前言

決策樹學習演算法有三個步驟：

特徵選擇
決策樹生成
決策樹剪枝

特徵選擇，就是決策樹的構造過程。

為了找到最優的劃分特徵，我們需要先了解一些資訊理論的知識。

資訊熵(information entropy)
條件熵(conditional entropy)
資訊增益(information gain)
資訊增益率(information gain ratio)
基尼指數(Gini index)

0x01 資訊熵

1.1 什麼是資訊熵

熵是熱力學中的概念，表示混亂程度。熵越大，熱力系統中粒子無規則的運動越劇烈；熵越小，粒子越趨近於靜止的狀態。

引申到資訊理論和概率統計中，資訊熵表示隨機變數的不確定度。對於一組數據來說，越隨機、不確定性越高，資訊熵越大；不確定性越低，資訊熵越小。

為了計算熵，我們需要計算所有類別所有可能值所包含的資訊期望值，著名的香農公式：

在一個系統中，有k類的資訊，其中是選擇該分類的概率（n/k），再乘p的對數，求和後加上負號。這是因為概率是小於1的數，是小於0的數，我們要求得到的熵是大於0的。

下面構造三個例子：假設有三組，每組為三類的資訊，每組每類的概率為：

按照公式，分別計算資訊熵：

我們看到，資訊熵H值越小，說明數據的不確定性越小。第一個式子，每種分類情況都是均等的；第二個式子，數據有70%的概率是落在第三類中，因此要比第一個式子更穩定；第三個式子，乾脆只有一個類，因此熵最小為0（特別穩定）。

如果在二分類的情況下，資訊熵公式也可以寫為下面的形式：

1.2 計算二分類資訊熵並可視化

import numpy as npimport matplotlib.pyplot as plt  # p可以傳遞數值，也可以傳遞向量。因此使用np.logdef entropy(p):    return -p * np.log(p) - (1-p) * np.log(1-p)    # linspace生成向量x，從0到1均勻取值，繪製出x在不同值時對應的資訊熵x = np.linspace(0.01,0.99,100)  plt.plot(x,entropy(x))plt.show()

形似拋物線，以0.5為對稱軸。當x=0.5時，曲線取到最大值，也就是說對於資訊熵來說，只有兩個類別，其中一個類別是0.5，另一個類別是1-0.5時，此時資訊熵是最大的，也就是最不確定的。如果x偏向於某一類，確定性變高了，資訊熵變低了。

0x02 條件熵

2.1 條件熵的定義

設有隨機變數。條件熵表示在已知隨機變數的條件下隨機變數的不確定性。

隨機變數給定的條件下隨機變數的條件熵定義為給定條件下，的條件概率分布的熵對的數學期望:

其中，

注意，與資訊熵不同的是，條件熵是數學期望，而不是變數的不確定性。

2.2 資訊熵和條件熵的區別

下面通過一個例子來講一下資訊熵和條件熵的區別。

在上面這棵「相親決策樹」中，對於結果（葉子結點），有隨機變數Y={見,不見}。我們可以統計出，見的個數佔2/6=1/3；不見的個數佔4/6=2/3。那麼變數Y的熵，可以根據公式計算得到：。

對於條件熵來說，我們還需要增加一個變數X，假設是年齡這一特徵。那麼在年齡<=30的情況下，有五種結果，見的個數佔2/5；不見的個數佔3/5。在年齡大於30的情況下，只有一種結果，見為0，不見為1.

那麼此時，可以得到如下的式子：

然後我們終於可以計算條件熵：

隨機變數給定的條件下隨機變數的條件熵定義為給定條件下，的條件概率分布的熵對的數學期望:

其中，

現在計算已知年齡的條件下的條件熵，以30為界有兩種情況，然後將上述結果帶入公式中，求得期望。

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

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

所謂小類，就是不包含當前所選特徵的其他維度，即當前的特徵是給定的條件，在其他維度下求熵，是條件下的。各類別的概率，是當前這個小類別（年齡>30）下的樣本量除以總的樣本量。

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

0x03 資訊增益

3.1 什麼是資訊熵增益

在劃分數據集前後資訊發生的變化稱為資訊增益，獲得資訊增益最高的特徵就是最好的選擇。

資訊增益就是：

以某特徵劃分數據集前後的熵的差值

劃分前，樣本集合D的熵（也稱經驗熵）是為H(D)；使用某個特徵A劃分數據集D，計算劃分後的數據子集（給定特徵A的情況下，數據集D）的條件熵（經驗條件熵）H(D|A)。則公式為：

在計算過程中，使用所有特徵劃分數據集D，得到多個特徵劃分數據集D的資訊增益（列表）。從這些資訊增益中選擇最大的，因而當前結點的劃分特徵便是使資訊增益最大的劃分所使用的特徵。

3.2 資訊熵增益的使用

通過對資訊增益的進一步理解，我們發現：對於待劃分的數據集D，其經驗熵H(D)是不變的，但是劃分之後得到的條件熵H(D|A)是變化的（特徵A的選擇不同）。

條件熵H(D|A)越小，說明使用此特徵劃分得到的子集的不確定性越小（也就是純度越高），因為得到的資訊增益就越大。說明在決策樹構建的過程中我們總是希望集合往最快到達純度更高的子集合方向發展，因此我們總是選擇使得資訊增益最大的特徵來劃分當前數據集D。

資訊增益偏向取值較多的特徵。

原因：當特徵的取值較多時，根據此特徵劃分更容易得到純度更高的子集，因此劃分之後的熵更低，由於劃分前的熵是一定的，因此資訊增益更大，因此資訊增益比較偏向取值較多的特徵。

0x04 資訊增益率

4.1 為什麼需要資訊增益率

我們已經知道，選取資訊增益大的特徵，可以得到更好的劃分。那麼為什麼要用資訊增益比呢？資訊增益比優於資訊增益的地方在哪呢？

這是因為，資訊增益偏向於選擇取值較多的特徵，容易過擬合。

假設在信用卡逾期風險預測場景中，有如下數據：

信用級別	工資級別	是否逾期
1	1	是
2	1	否
3	2	是
4	2	否

那麼此時我們分別計算「信用級別」和「工資級別」條件下「預期」的條件熵。

B = H(是否逾期|工資級別)= p(工資級別=1)H(是否逾期|工資級別=1)+ p(工資級別=2)H(是否逾期|工資級別=2)

很顯然 B > A，也就是說，對於增益資訊：g(D|信用級別) > g(D|工資級別)。很明顯，資訊增益偏向於選擇取值較多的特徵，但是根據熵的公式可知，特徵越多，熵越大。

那麼有什麼辦法呢？是在資訊增益的基礎之上乘上一個懲罰參數，對樹分支過多的情況進行懲罰，抵消了特徵變數的複雜程度，避免了過擬合的存在。

4.2 資訊增益率的定義

特徵A對訓練數據集D的資訊增益比定義為：其資訊增益g(D,A)與訓練數據集D關於特徵A的值的熵HA(D)之比，即：

注意，其中的HA(D)是：對於樣本集合D，將當前特徵A作為隨機變數（取值是特徵A的各個特徵值），求得的經驗熵。（之前是把集合類別（年齡、長相）作為隨機變數，現在把某個特徵作為隨機變數，按照此特徵的特徵取值對集合D進行劃分，計算熵HA(D)）

其中，$H_A(D)=−sum_i=1}^n frac {D_i|D|logfracD_i|D|$，n是特徵AA取值的個數。注意區別H(D|A)和HA(D)。

資訊增益比本質：是在資訊增益的基礎之上乘上一個懲罰參數。特徵個數較多時，懲罰參數較小；特徵個數較少時，懲罰參數較大。

資訊增益比 = 懲罰參數 * 資訊增益

所謂懲罰參數，是數據集D以特徵A作為隨機變數的熵的倒數，即：將特徵A取值相同的樣本劃分到同一個子集中（之前所說數據集的熵是依據類別進行劃分的）。

資訊增益比的缺點是：偏向取值較少的特徵。原因：當特徵取值較少時HA(D)的值較小，因此其倒數較大，因而資訊增益比較大。因而偏向取值較少的特徵。

基於以上特點，在使用增益資訊比時，並不是直接選擇資訊增益率最大的特徵，而是現在候選特徵中找出資訊增益高於平均水平的特徵，然後在這些特徵中再選擇資訊增益率最高的特徵。

0x05 基尼係數

5.1 基尼係數的定義

基尼係數（Gini），也被稱為基尼不純度，表示在樣本集合中一個隨機選中的樣本被分錯的概率。

Gini係數越小表示集合中被選中的樣本被分錯的概率越小，也就是說集合的純度越高，反之，基尼指數集合越不純。

即：基尼指數（基尼不純度）= 樣本被選中的概率 * 樣本被分錯的概率

有如下公式：

對上述公式進行說明：

表示選中的樣本屬於k類別的概率，則這個樣本被分錯的概率是
因為樣本集合中有k個類別，一個隨機選中的樣本可以屬於這k個類別中的任意一個，因而累加所有的k個類別。
當二分類時，

樣本集合D的基尼係數：假設集合中有K個類別，每個類別的概率是，其中表示類別k的樣本個數，表示樣本總數，則：

5.2 特徵A劃分樣本集合D之後的基尼指數

一般來說，我們在使用中，用某個特徵劃分樣本集合只有兩個集合（CART）：

等於給定的特徵值的樣本集合D1
不等於給定的特徵值的樣本集合D2

這樣就可以對擁有多個取值的特徵的二值處理。

舉個例子：

假設現在有特徵「學歷」，此特徵有三個特徵取值：「本科」，「碩士」，「博士」，

當使用「學歷」這個特徵對樣本集合D進行劃分時，劃分值分別有三個，因而有三種劃分的可能集合，劃分後的子集如下：

劃分點：「本科」，劃分後的子集合：{本科}，{碩士，博士}
劃分點：「碩士」，劃分後的子集合：{碩士}，{本科，博士}
劃分點：「碩士」，劃分後的子集合：{博士}，{本科，碩士}

對於上述的每一種劃分，都可以計算出基於劃分特徵=某個特徵值將樣本集合D劃分為兩個子集的純度：

因而對於一個具有多個取值（超過2個）的特徵，需要計算以每一個取值作為劃分點，對樣本D劃分之後子集的純度Gini(D,Ai)，(其中Ai表示特徵A的可能取值)。然後從所有的可能劃分的Gini(D,Ai)中找出Gini指數最小的劃分，這個劃分的劃分點，便是使用特徵A對樣本集合D進行劃分的最佳劃分點。

0xFF 總結

本篇介紹了一系列的概念：資訊熵、條件熵、資訊增益、資訊增益率、基尼係數等。雖然沒怎麼介紹演算法，但是這些前置概念是必須的。

這篇文章的標題是《決策樹的特徵選擇》，特徵選擇也就是選擇最優劃分屬性，從當前數據的特徵中選擇一個特徵作為當前節點的劃分標準。我們希望在不斷劃分的過程中，決策樹的分支節點所包含的樣本儘可能屬於同一類，即節點的「純度」越來越高。

而選擇最優劃分特徵的標準（上面介紹的這些概念）不同，也導致了決策樹演算法的不同。