【機器學習】決策樹特征選擇準則 資訊增益、資訊增益率、基尼系數的計算及其python實作

索引

• 1.問題引入
• 2.資訊增益
• • 1.計算公式：
  • 2.執行個體計算：
• 3.資訊增益率
• • 1.計算公式：
  • 2.執行個體計算：
• 4.基尼系數
• • 1.計算公式：
  • 2.執行個體計算：
• 5.參考文獻
• 6.python代碼

1.問題引入

首先，我們引入需進行決策樹算法學習的資料集 D D D，如下，

特征 A = [ ′ 年 齡 ′ ， ′ 有 工 作 ′ , ′ 有 自 己 的 房 子 ′ , ′ 信 貸 情 況 ′ ] A = ['年齡'，'有工作', '有自己的房子', '信貸情況'] A=[′年齡′，′有工作′,′有自己的房子′,′信貸情況′]

類别 Y = [ ′ 類 别 ′ ] Y = ['類别'] Y=[′類别′]

接着擺在我們面前的是首先選擇哪個特征，其次選擇哪個特征，…，最後選擇哪個特征。（就是先選擇好的特征，再選擇壞的特征）

問題引入：  怎麼知道特征的好壞呢？
如果一個特征A能使得資料分出來的類别最好，那麼他就是最好的特征。
(就是提供的資訊最為準确），是以我們引入資訊增益來衡量提供的資訊準确度。
           

2.資訊增益

1.計算公式：

G ( D ， A ) = H ( D ) − H ( D ∣ A ) G(D，A) = H(D) - H(D|A) G(D，A)=H(D)−H(D∣A)

解釋: G ( D ， A ) G(D，A) G(D，A)指的是特征 A A A對資料集 D D D的資訊增益；

H ( D ) H(D) H(D)指資料集 D D D的(經驗)熵；

那麼問題來了，什麼是熵呢？
熵表示的是随機變量不确定性的度量。熵越大，表示這個系統越紊亂，越難确定一個東西。
           

H ( D ∣ A ) H(D|A) H(D∣A)指的是 A A A條件下，資料集 D D D的(經驗)條件熵。

經驗條件熵是什麼呢？
例如：H(D|A)指的是特征A條件下，資料集D的不确定性。
換句話說，就是隻知道特征A來确定資料D的類别，同樣的，熵越大，越紊亂，越難确定類别。
           

注：

1. H ( D ) = − ∑ i = 0 n p i l o g 2 p i H(D) = -\sum_{i=0}^{n}p_{i}log_{2}p_{i} H(D)=−i=0∑n​pi​log2​pi​

i = 1 ， . . . n ( n 為 類 别 Y 的 數 量 ) i=1，...n (n為類别Y的數量) i=1，...n(n為類别Y的數量)

p i 是 每 一 類 出 現 的 概 率 ， 例 如 p ′ 是 ′ = 是 出 現 的 次 數 總 數 = 9 15 p_{i}是每一類出現的機率，例如p_{'是'}= \frac{是出現的次數} {總數}= \frac{9} {15} pi​是每一類出現的機率，例如p′是′​=總數是出現的次數​=159​

2. H ( D ∣ A ) = ∑ i = 0 n p i H ( Y ∣ X = x i ) H(D|A) = \sum_{i=0}^{n}p_{i}H(Y|X = x_{i}) H(D∣A)=i=0∑n​pi​H(Y∣X=xi​)

i = 1 ， . . . n ( n 為 特 征 A 取 值 的 個 數 ) i=1，...n (n為特征A取值的個數) i=1，...n(n為特征A取值的個數)

2.執行個體計算：

我們拿上述資料集D的特征A='年齡’為例計算其資訊增益：

1.

H ( D ) = − ∑ i = 0 n p i l o g 2 p i = − 6 15 l o g 2 6 15 − 9 15 l o g 2 9 15 = 0.971 H(D) = -\sum_{i=0}^{n}p_{i}log_{2}p_{i}=-\frac{6}{15}log_{2}\frac{6}{15} -\frac{9}{15}log_{2}\frac{9}{15}=0.971 H(D)=−i=0∑n​pi​log2​pi​=−156​log2​156​−159​log2​159​=0.971

此處類别’否’為6個樣本，類别’是’為9個樣本；

2.

H ( D ∣ ′ 年 齡 ′ ) = ∑ i = 0 n p i H ( Y ∣ X = x i ) = p ′ 青 年 ′ H ( Y ∣ X = x ′ 青 年 ′ ) + p ′ 中 年 ′ H ( Y ∣ X = x ′ 中 年 ′ ) + p ′ 老 年 ′ H ( Y ∣ X = x ′ 老 年 ′ ) = 5 15 ∗ ( − 2 5 l o g 2 2 5 − 3 5 l o g 2 3 5 ) + 5 15 ∗ ( − 2 5 l o g 2 2 5 − 3 5 l o g 2 3 5 ) + 5 15 ∗ ( − 1 5 l o g 2 1 5 − 4 5 l o g 2 4 5 ) = 0.888 H(D|'年齡')=\sum_{i=0}^{n}p_{i}H(Y|X = x_{i})=p_{'青年'}H(Y|X = x_{'青年'})+p_{'中年'}H(Y|X = x_{'中年'})+ p_{'老年'}H(Y|X = x_{'老年'})=\frac{5}{15}*(-\frac{2}{5}log_{2}\frac{2}{5} -\frac{3}{5}log_{2}\frac{3}{5})+\frac{5}{15}*(-\frac{2}{5}log_{2}\frac{2}{5} -\frac{3}{5}log_{2}\frac{3}{5})+\frac{5}{15}*(-\frac{1} {5}log_{2}\frac{1}{5} -\frac{4}{5}log_{2}\frac{4}{5})=0.888 H(D∣′年齡′)=i=0∑n​pi​H(Y∣X=xi​)=p′青年′​H(Y∣X=x′青年′​)+p′中年′​H(Y∣X=x′中年′​)+p′老年′​H(Y∣X=x′老年′​)=155​∗(−52​log2​52​−53​log2​53​)+155​∗(−52​log2​52​−53​log2​53​)+155​∗(−51​log2​51​−54​log2​54​)=0.888

3.

G ( D ， ′ 年 齡 ′ ) = H ( D ) − H ( D ∣ ′ 年 齡 ′ ) = 0.971 − 0.888 = 0.083 G(D，'年齡') = H(D) - H(D|'年齡') =0.971-0.888=0.083 G(D，′年齡′)=H(D)−H(D∣′年齡′)=0.971−0.888=0.083

同理： G ( D ， ′ 有 工 作 ′ ) = 0.324 ， G ( D ， ′ 有 自 己 的 房 子 ′ ) = 0.420 ， G ( D ， ′ 信 貸 情 況 ′ ) = 0.363 G(D，'有工作')=0.324， G(D，'有自己的房子')=0.420，G(D，'信貸情況')=0.363 G(D，′有工作′)=0.324，G(D，′有自己的房子′)=0.420，G(D，′信貸情況′)=0.363

比較各個特征的資訊增益值，發現 G ( D ， ′ 有 自 己 的 房 子 ′ ) = 0.420 G(D，'有自己的房子')=0.420 G(D，′有自己的房子′)=0.420最大，即選擇特征’有自己的房子’作為最優特征。

資訊增益準則偏向選擇對數目較多的特征，是以引入資訊增益率準則

3.資訊增益率

1.計算公式：

g R ( D ， A ) = ( H ( D ) − H ( D ∣ A ) ) / H A ( D ) g_{R}(D，A) =(H(D) - H(D|A))/H_{A}(D) gR​(D，A)=(H(D)−H(D∣A))/HA​(D)

注： H A ( D ) = − ∑ i = 0 n p i l o g 2 p i ， i = 1 ， . . . n ( n 為 特 征 A 取 值 的 個 數 ) H_{A}(D)= -\sum_{i=0}^{n}p_{i}log_{2}p_{i}，i=1，...n (n為特征A取值的個數) HA​(D)=−i=0∑n​pi​log2​pi​，i=1，...n(n為特征A取值的個數)

2.執行個體計算：

我們還是拿上述資料集D的特征A='年齡’為例計算其資訊增益率：

1.

H ′ 年 齡 ′ ( D ) = ( − 5 15 l o g 2 5 15 − 5 15 l o g 2 5 15 − 5 15 l o g 2 5 15 ) = 1.58 H_{'年齡'}(D)=(-\frac{5} {15}log_{2}\frac{5}{15} -\frac{5} {15}log_{2}\frac{5}{15}-\frac{5} {15}log_{2}\frac{5}{15})=1.58 H′年齡′​(D)=(−155​log2​155​−155​log2​155​−155​log2​155​)=1.58

2.

g R ( D ， ′ 年 齡 ′ ) = ( H ( D ) − H ( D ∣ ′ 年 齡 ′ ) ) / H ′ 年 齡 ′ ( D ) = 0.083 / 1.585 = 0.052 g_{R}(D，'年齡') =(H(D) - H(D|'年齡'))/H_{'年齡'}(D)=0.083/1.585=0.052 gR​(D，′年齡′)=(H(D)−H(D∣′年齡′))/H′年齡′​(D)=0.083/1.585=0.052

同理： g R ( D ， ′ 有 工 作 ′ ) = 0.352 ， g R ( D ， ′ 有 自 己 的 房 子 ′ ) = 0.433 ， g R ( D ， ′ 信 貸 情 況 ′ ) = 0.232 g_{R}(D，'有工作') =0.352，g_{R}(D，'有自己的房子') =0.433，g_{R}(D，'信貸情況') =0.232 gR​(D，′有工作′)=0.352，gR​(D，′有自己的房子′)=0.433，gR​(D，′信貸情況′)=0.232

比較各個特征的資訊增益率值，發現 G ( D ， ′ 有 自 己 的 房 子 ′ ) = 0.433 G(D，'有自己的房子')=0.433 G(D，′有自己的房子′)=0.433最大，即選擇特征’有自己的房子’作為最優特征。

4.基尼系數

1.計算公式：

1.資料集D的純度：

G i n i ( D i ) = ∑ i = 1 n p i ( 1 − p i ) = 1 − ∑ i = 1 n p i 2 Gini(D^{i})=\sum_{i=1}^{n}p_{i}(1-p_{i})=1-\sum_{i=1}^{n}p_{i}^{2} Gini(Di)=i=1∑n​pi​(1−pi​)=1−i=1∑n​pi2​

n 為 樣 本 的 類 别 數 n為樣本的類别數 n為樣本的類别數

可以得出 G i n i ( p ) Gini(p) Gini(p)反應了在資料集中抽取兩個樣本，其類别不一樣的機率；

随機抽取兩個樣本，如果他們根據某個特征分類，其分類類别一樣，即該特征非常适合分類，(換句話說我們的目的是使同一個分支的類别一緻)，是以 G i n i ( p ) Gini(p) Gini(p)越小越好。

2.特征A的基尼系數：

G i n i ( D ， A ) = ∑ i = 1 n p i G i n i ( D i ) Gini(D， A)=\sum_{i=1}^{n}p_{i}Gini(D^{i}) Gini(D，A)=i=1∑n​pi​Gini(Di)

n 為 樣 本 的 類 别 數 n為樣本的類别數 n為樣本的類别數

2.執行個體計算：

我們還是拿上述資料集D的特征A='年齡’為例計算其基尼系數：

G i n i ( D ， ′ 年 齡 ′ ) = ∑ i = 1 n p i G i n i ( D i ) = p 青 年 ∗ ( 1 − ( 2 5 ) 2 − ( 3 5 ) 2 ) + p 中 年 ( 1 − ( 2 5 ) 2 − ( 3 5 ) 2 ) + p 老 年 ∗ ( 1 − ( 1 5 ) 2 − ( 4 5 ) 2 ) = 0.427 Gini(D， '年齡')=\sum_{i=1}^{n}p_{i}Gini(D^{i})=p_{青年}*(1-(\frac{2}{5})^{2}-(\frac{3}{5})^{2})+p_{中年}(1-(\frac{2}{5})^{2}-(\frac{3}{5})^{2})+p_{老年}*(1-(\frac{1}{5})^{2}-(\frac{4}{5})^{2})=0.427 Gini(D，′年齡′)=i=1∑n​pi​Gini(Di)=p青年​∗(1−(52​)2−(53​)2)+p中年​(1−(52​)2−(53​)2)+p老年​∗(1−(51​)2−(54​)2)=0.427

同理： G i n i ( D ， ′ 有 工 作 ′ ) = 0.320 ， G i n i ( D ， ′ 有 自 己 的 房 子 ′ ) = 0.267 ， G i n i ( D ， ′ 信 貸 情 況 ′ ) = 0.284 Gini(D，'有工作') =0.320，Gini(D，'有自己的房子') =0.267，Gini(D，'信貸情況') =0.284 Gini(D，′有工作′)=0.320，Gini(D，′有自己的房子′)=0.267，Gini(D，′信貸情況′)=0.284

5.參考文獻

[1]李航.統計學習方法（第二版）[M].清華大學出版社:北京,2019:67.

[2]周志華.機器學習[M].清華大學出版社:北京,2016:73.

6.python代碼

在這裡插入代碼片