信息增益的算法

信息增益的算法

输入：训练数据集D和特征A 输出：特征A对训练数据集D的信息增益g(D,A)

定义： K：样本标签有K种分类 $C_k$：样本标签为k的样本数 m：样本总数 $D_i$：样本中第A个特征为$a_i$的样本数 $D_{ik}$：样本中第A个特征为$a_i$且其标签分类为k的样本数

计算数据集D的经验熵H(D)

$$\begin{aligned} H(D) = -\sum_{k=1}^K P_k\log_2P_k \\ P_k = \frac{C_k}{m} \end{aligned}$$

计算特征A对数据集D的经验条件熵H(D|A)

$$\begin{aligned} H(D|A) = \sum_{i=1}^n p_iH(D_i) \\ = -\sum_{i=1}^n p_i\sum_{k=1}^K p_{ik}\log_2p_{ik} \\ p_i = \frac {D_i}{m} \\ p_{ik} = \frac {D_{ik}}{D_i} \end{aligned}$$

即通过特征A分出的每个子集的熵与子集比例乘积的和。

计算信息增益

$$g(D, A) = H(D) - H(D|A)$$

代码

# 特征和标签的可取值范围：
def H(y):
    sum = 0
    # 计算y可取到的值
    k = set(y)
    for ck in k:
        Pk = y[y==ck].shape[0] / y.shape[0]
        if Pk != 0:
            sum -= Pk * np.log2(Pk)
    return sum

def svm(X, y, feature):
    # 计算X的每个特征可取到的值
    a = set(X[:,feature])
    # 计算数据集的经验熵
    HD = H(y)
    # 计算特征A对数据集D的经验条件熵H(D|A)
    HDA = 0
    for value in a:
        yDi = y[X[:,feature]==value]
        HDA += yDi.shape[0]/y.shape[0] * H(yDi)
    return HD - HDA