> For the complete documentation index, see [llms.txt](https://windmising.gitbook.io/lihang-tongjixuexifangfa/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://windmising.gitbook.io/lihang-tongjixuexifangfa/decisiontree/2.md).

# 信息增益的算法

## 信息增益的算法

输入：训练数据集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)
$$

## 代码

```python
# 特征和标签的可取值范围：
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
```