特征重要性算法

項目鏈接：https://github.com/Wchenguang/gglearn/blob/master/DecisionTree/李航機器學習講解/FeatureImportance.ipynb

信息增益法 公式

• 熵的定義：

  • 屬性 $y$ 的熵，表示特征的不確定性：
    $$P\left(Y=y_j\right)=p_j,i=1,2,?,n$$
    H ( Y ) = ? ∑ j = 1 n p j log ? p j H(Y)=-\sum_{j=1}^{n} p_{j} \log p_{j} H ( Y ) = ? j = 1 ∑ n ? p j ? lo g p j ?

• 條件熵的定義：

  • 在 $x$ 已知的情況下， $y$ 的不確定性
    $$P\left(X=x_i,Y=y_j\right)=p_{ij},i=1,2,?,n;j=1,2,?,m$$
    $$H(Y|X)=\sum _{i=1}^n{p}_{i}H\left(Y|X=x_i\right)$$

• 信息增益計算流程

  1. 計算特征A對數據集D的熵，即計算 $y$ 的熵
     H ( D ) = ? ∑ k = 1 K ∣ C k ∣ ∣ D ∣ log ? 2 ∣ C k ∣ ∣ D ∣ H(D)=-\sum_{k=1}^{K} \frac{\left|C_{k}\right|}{|D|} \log _{2} \frac{\left|C_{k}\right|}{|D|} H ( D ) = ? k = 1 ∑ K ? ∣ D ∣ ∣ C k ? ∣ ? lo g 2 ? ∣ D ∣ ∣ C k ? ∣ ?
  2. 計算$ x $不同取值的情況下，$ y $的熵
     H ( D ∣ A ) = ∑ i = 1 n ∣ D i ∣ ∣ D ∣ H ( D i ) = ? ∑ i = 1 n ∣ D i ∣ ∣ D ∣ ∑ k = 1 K ∣ D i k ∣ ∣ D i ∣ log ? 2 ∣ D i k ∣ ∣ D i ∣ H(D | A)=\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} H\left(D_{i}\right)=-\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} \sum_{k=1}^{K} \frac{\left|D_{i k}\right|}{\left|D_{i}\right|} \log _{2} \frac{\left|D_{i k}\right|}{\left|D_{i}\right|} H ( D ∣ A ) = i = 1 ∑ n ? ∣ D ∣ ∣ D i ? ∣ ? H ( D i ? ) = ? i = 1 ∑ n ? ∣ D ∣ ∣ D i ? ∣ ? k = 1 ∑ K ? ∣ D i ? ∣ ∣ D i k ? ∣ ? lo g 2 ? ∣ D i ? ∣ ∣ D i k ? ∣ ?
  3. 做差計算增益
     $$g(D,A)=H(D)?H(D|A)$$

            
              import numpy as np
import math
'''
熵的計算
'''
def entropy(y_values):
    e = 0
    unique_vals = np.unique(y_values)
    for val in unique_vals:
        p = np.sum(y_values == val)/len(y_values)
        e += (p * math.log(p, 2))
    return -1 * e

'''
條件熵的計算
'''
def entropy_condition(x_values, y_values):
    ey = entropy(y_values)
    ey_condition = 0
    xy = np.hstack((x_values, y_values))
    unique_x = np.unique(x_values)
    for x_val in unique_x:
        px = np.sum(x_values == x_val) / len(x_values)
        xy_condition_x = xy[np.where(xy[:, 0] == x_val)]
        ey_condition_x = entropy(xy_condition_x[:, 1])
        ey_condition += (px * ey_condition_x)
    return ey - ey_condition

'''
信息增益比：摒棄了選擇取值多的特征為重要特征的缺點
'''
def entropy_condition_ratio(x_values, y_values):
    return entropy_condition(x_values, y_values) / entropy(x_values)

            
          

• 以書中P62頁的例子作為測試，以下分別為A1， A2的信息增益

            
              xy = np.array([[0,0,0,0,0,1,1,1,1,1,2,2,2,2,2], [0,0,1,1,0,0,0,1,0,0,0,0,1,1,0], [0,0,0,1,0,0,0,1,1,1,1,1,0,0,0], 
             [0,1,1,0,0,0,1,1,2,2,2,1,1,2,0], [0,0,1,1,0,0,0,1,1,1,1,1,1,1,0]]).T
#A1
print(entropy_condition(xy[:, 0].reshape(-1, 1), 
                        xy[:, -1].reshape(-1, 1)))
#A2
print(entropy_condition(xy[:, 1].reshape(-1, 1), 
                        xy[:, -1].reshape(-1, 1)))

#A3
print(entropy_condition(xy[:, 2].reshape(-1, 1), 
                        xy[:, -1].reshape(-1, 1)))

#A4
print(entropy_condition(xy[:, 3].reshape(-1, 1), 
                        xy[:, -1].reshape(-1, 1)))


            
          

• 與書中結果相合

            
              xy = np.array([[0,0,0,0,0,1,1,1,1,1,2,2,2,2,2], [0,0,1,1,0,0,0,1,0,0,0,0,1,1,0], [0,0,0,1,0,0,0,1,1,1,1,1,0,0,0], 
             [0,1,1,0,0,0,1,1,2,2,2,1,1,2,0], [0,0,1,1,0,0,0,1,1,1,1,1,1,1,0]]).T
#A1
print(entropy_condition_ratio(xy[:, 0].reshape(-1, 1), 
                        xy[:, -1].reshape(-1, 1)))
#A2
print(entropy_condition_ratio(xy[:, 1].reshape(-1, 1), 
                        xy[:, -1].reshape(-1, 1)))

#A3
print(entropy_condition_ratio(xy[:, 2].reshape(-1, 1), 
                        xy[:, -1].reshape(-1, 1)))

#A4
print(entropy_condition_ratio(xy[:, 3].reshape(-1, 1), 
                        xy[:, -1].reshape(-1, 1)))


            
          

基尼指數 公式

$$\mathrm{G}\mathrm{i}\mathrm{n}\mathrm{i}(p)=\sum _{k=1}^K{p}_k\left(1?p_k\right)=1?\sum _{k=1}^K{p}_k^2$$
$$\mathrm{G}\mathrm{i}\mathrm{n}\mathrm{i}(D)=1?\sum _{k=1}^K{\left(\frac{\left|C_k\right|}{|D|}\right)}^2$$
$$\mathrm{G}\mathrm{i}\mathrm{n}\mathrm{i}(D,A)=\frac{\left|D_1\right|}{|D|}\mathrm{G}\mathrm{i}\mathrm{n}\mathrm{i}\left(D_1\right)+\frac{\left|D_2\right|}{|D|}\mathrm{G}\mathrm{i}\mathrm{n}\mathrm{i}\left(D_2\right)$$

            
              '''
基尼指數計算
'''
def gini(y_values):
    g = 0
    unique_vals = np.unique(y_values)
    for val in unique_vals:
        p = np.sum(y_values == val)/len(y_values)
        g += (p * p)
    return 1 - g

'''
按照x取值的基尼指數的計算
'''
def gini_condition(x_values, y_values):
    g_condition = {}
    xy = np.hstack((x_values, y_values))
    unique_x = np.unique(x_values)
    for x_val in unique_x:
        xy_condition_x = xy[np.where(xy[:, 0] == x_val)]
        xy_condition_notx = xy[np.where(xy[:, 0] != x_val)]
        g_condition[x_val] = len(xy_condition_x)/len(x_values) * gini(xy_condition_x[:, 1]) + len(xy_condition_notx)/len(x_values) * gini(xy_condition_notx[:, 1])
    return g_condition

            
          

            
              xy = np.array([[0,0,0,0,0,1,1,1,1,1,2,2,2,2,2], [0,0,1,1,0,0,0,1,0,0,0,0,1,1,0], [0,0,0,1,0,0,0,1,1,1,1,1,0,0,0], 
             [0,1,1,0,0,0,1,1,2,2,2,1,1,2,0], [0,0,1,1,0,0,0,1,1,1,1,1,1,1,0]]).T
#A1
print(gini_condition(xy[:, 0].reshape(-1, 1), 
                        xy[:, -1].reshape(-1, 1)))
#A2
print(gini_condition(xy[:, 1].reshape(-1, 1), 
                        xy[:, -1].reshape(-1, 1)))

#A3
print(gini_condition(xy[:, 2].reshape(-1, 1), 
                        xy[:, -1].reshape(-1, 1)))

#A4
print(gini_condition(xy[:, 3].reshape(-1, 1), 
                        xy[:, -1].reshape(-1, 1)))


            
          

• 與書中p71相符，選擇最小的特征及 $x$ 取值作為最優特征及分切點。
• 其實選取基尼指數最小，即選擇在哪個特征下以及該特征取哪個值的情況下， $y$ 的不確定性最小

特征重要性的對比

以隨機森林算法進行特征重要性計算，以書中數據為例

            
              from sklearn.ensemble import RandomForestClassifier

rf = RandomForestClassifier(random_state=42).fit(xy[:, :-1], xy[:, -1])

print(rf. feature_importances_)


            
          

• 總體上相符