信息增益（ID3算法）——分类树，分类的标签是离散的，如 好/不好

信息熵

基本概念

信息熵（Information Entropy）是一个来自信息论的基本概念，由美国数学家克劳德·香农（Claude Shannon）在1948年引入，用于量化信息的不确定性和随机性。它是对一个信息系统无序程度或者信息的不确定性的一种度量。
在信息论中，熵描述了一条消息或一个信号所携带的信息量的期望值，即接收到该消息后所能消除的不确定性量。

$$具体来说，对于一个离散随机变量X，其可能取到的不同值为x_1,x_2,...,x_n，且每个值x_i出现的概率分别为p(x_i)，信息熵H(X)定义为：$$

$$H(X)=-\sum _{i=1}^{n}p(xi){\log }_2(p(xi))$$

其中，log是以2为底的对数，这个选择使得信息熵的单位是比特（bit）。如果使用其他底数的对数，信息熵的单位会相应改变，但其量值的相对大小不变，因为对数函数的换底公式保证了这一点。

信息熵的几个关键特性包括：

1. 非负性：信息熵总是非负的，当且仅当所有事件的发生概率相等时取得最大值（即系统完全无序时）。
2. 对称性：信息熵不依赖于事件的标签，只依赖于它们的概率分布。
3. 加性：如果有两个独立的随机变量X和Y，它们联合分布的信息熵等于各自熵的和。

例子

假设我们关心明天的天气预报，可能的结果有“晴天”、“雨天”、“阴天”三种，且已知历史数据显示：

• 晴天的概率为 P(晴天) = 0.4
• 雨天的概率为 P(雨天) = 0.3
• 阴天的概率为 P(阴天) = 0.3

我们要计算这种天气预报的不确定性，也就是信息熵。

计算步骤：

1. 确定随机变量及其可能取值：随机变量为“明天的天气”，取值为“晴天”、“雨天”、“阴天”。

2. 应用信息熵公式：

$$H(天气)=-\sum _i{p}_i{\log }_2{p}_i$$

$$其中，p_i是每种天气出现的概率。$$

• $$对于晴天：-0.4{\log }_{2}0.4$$
• $$对于雨天：-0.3{\log }_{2}0.3$$
• $$对于阴天：-0.3{\log }_{2}0.3$$

具体计算：

$$H(天气)=-(0.4{\log }_{2}0.4+0.3{\log }_{2}0.3+0.3{\log }_{2}0.3)$$

使用对数计算器进行计算（注意，这里的对数是以2为底的）：

• $$0.4{\log }_{2}0.4\approx 0.4\times (-2.0)=-0.8$$
• $$0.3{\log }_{2}0.3\approx 0.3\times (-1.5849)=-0.4755$$
• $$0.3{\log }_{2}0.3\approx 0.3\times (-1.5849)=-0.4755$$

所以，

$$H(天气)=-(-0.8-0.4755-0.4755)$$
$$H(天气)=1.751\text{ bits}$$

因此，在这个天气预报的例子中，明天天气的信息熵约为1.751比特。
这意味着，要准确地传达关于明天天气的信息，平均需要1.751比特的信息量。由于各种天气出现的概率较为均衡，不确定性较高，所以信息熵的值相对较大。

信息增益

基本概念

信息增益（Information Gain）是机器学习中特别是在决策树算法中用于特征选择的一个重要概念。它是基于信息论中的熵（Entropy）概念来衡量的，用于评估在给定一个特征的条件下，数据集的不确定性减少的程度。

具体来说，信息增益计算的是特征划分前数据集的熵与划分后各子集熵的加权平均之间的差值。
熵反映了数据集的纯度或不确定性，熵越高表示数据集中类别的分布越混杂，不确定性越大。而信息增益表达了使用某个特征划分数据集后，整体的不确定性减少了多少。

公式表示

假设数据集 D 的熵为 H(D)，在选择一个特征 A 进行划分后，数据集被划分为若干子集 $$(D_1,D_2,...,D_n)$$
每个子集的熵分别为$$H(D_1),H(D_2),...,H(D_n)$$
$$并且子集D_i中的数据占总数据的比例为p_i，则特征A的信息增益IG(A)定义为：$$

$$IG(A)=H(D)-\sum _{i=1}^n{p}_i\cdot H(D_i)$$

其中：

• $$H(D)表示原始数据集的熵。$$
• $$H(D_i)表示第i个子集的熵。$$
• $$p_i是子集D_i占原数据集的比例。$$

信息增益的意义

信息增益的值越大，说明使用这个特征进行划分后，数据集的不确定性减少得越多，即该特征对分类的贡献越大，有助于构建更纯净（即每个子集中的数据尽可能属于同一类别）的子集。在决策树构建过程中，通常会选择信息增益最大的特征作为当前节点的分裂特征，以达到最优的分类效果。

然而，信息增益方法倾向于选择具有大量值的特征，因为这类特征能够产生更多的子集，即使这些子集的纯度提升不大，也可能导致过拟合。为了解决这一问题，实践中经常使用信息增益比或基尼不纯度等替代方法。

例子

好的，让我们通过一个全新的例子来详细解释信息熵和信息增益的计算过程。假设我们有一个数据集，用于预测银行客户是否会购买一项保险产品。数据集中有两个特征：年龄（青年、中年、老年）和收入水平（低、中、高），以及目标变量“购买保险”（是、否）。

假设数据集如下：

年龄	收入水平	购买保险（是/否）	人数
青年	低	是	30人
青年	低	否	20人
青年	中	是	40人
青年	中	否	10人
青年	高	是	50人
青年	高	否	5人
中年	低	是	25人
中年	低	否	35人
中年	中	是	45人
中年	中	否	15人
中年	高	是	60人
中年	高	否	10人
老年	低	是	15人
老年	低	否	45人
老年	中	是	30人
老年	中	否	30人
老年	高	是	50人
老年	高	否	20人

计算整个数据集的熵 H(D)

• 总人数 = 30 + 20 + 40 + 10 + 50 + 5 + 25 + 35 + 45 + 15 + 60 + 10 + 15 + 45 + 30 + 30 + 50 + 20 = 535人
• 购买保险的人数 = 30 + 40 + 50 + 25 + 45 + 60 + 15 + 30 + 50 = 345人
• 不购买保险的人数 = 20 + 10 + 5 + 35 + 15 + 10 + 45 + 30 + 20 = 190人
• 购买的概率 $$P(是)=\frac{345}{535}$$
• 不购买的概率 $$P(否)=\frac{190}{535}$$

整个数据集的熵 H(D)：
$$H(D)=-P(是){\log }_{2}P(是)-P(否){\log }_{2}P(否)$$

计算特征“年龄”的信息增益 IG(年龄)

首先，分别计算按年龄划分后的子集熵。

青年子集

• 购买人数 = 30 + 40 + 50 = 120人
• 不购买人数 = 20 + 10 + 5 = 35人
• $$购买概率=\frac{120}{155}$$
• $$不购买概率=\frac{35}{155}$$

青年子集的熵：
$$H(青年)=-\frac{120}{155}{\log }_2\frac{120}{155}-\frac{35}{155}{\log }_2\frac{35}{155}$$

中年子集

• 购买人数 = 25 + 45 + 60 = 130人
• 不购买人数 = 35 + 15 + 10 = 60人
• $$购买概率=\frac{130}{190}$$
• $$不购买概率=\frac{60}{190}$$

中年子集的熵：
$$H(中年)=-\frac{130}{190}{\log }_2\frac{130}{190}-\frac{60}{190}{\log }_2\frac{60}{190}$$

老年子集

• 购买人数 = 15 + 30 + 50 = 95人
• 不购买人数 = 45 + 30 + 20 = 95人
• $$购买概率=\frac{95}{190}$$
• $$不购买概率=\frac{95}{190}$$

老年子集的熵：
$$H(老年)=-\frac{95}{190}{\log }_2\frac{95}{190}-\frac{95}{190}{\log }_2\frac{95}{190}$$

信息增益 (IG(年龄))

$$\begin{gathered} IG(A)=H(D)-\sum _{i=1}^n{p}_i\cdot H(D_i) \\ IG(年龄)=H(D)-\left(\frac{155}{535}H(青年)+\frac{190}{535}H(中年)+\frac{190}{535}H(老年)\right) \end{gathered}$$

通过以上步骤，可以计算出特征“年龄” 在决定是否购买保险方面的信息增益。这个值将告诉我们，根据年龄划分数据集能多大程度上减少不确定性。

ID3算法进行剪枝

假设数据集如下：

Outlook	Temperature	Humidity	Wind	Play
Sunny	Hot	High	Weak	No
Sunny	Hot	Normal	Strong	No
Overcast	Hot	High	Weak	Yes
Rain	Mild	High	Weak	Yes
Rain	Cool	Normal	Weak	Yes
Rain	Cool	Normal	Strong	No
Overcast	Cool	Normal	Strong	Yes
Sunny	Mild	High	Weak	No
Sunny	Cool	Normal	Weak	Yes
Rain	Mild	Normal	Weak	Yes
Sunny	Mild	Normal	Strong	Yes
Overcast	Mild	High	Strong	Yes
Overcast	Hot	Normal	Weak	Yes
Rain	Mild	High	Strong	No

目标：预测Play（是否适合户外活动，Yes/No）

ID3算法步骤及计算：

1. 计算整个数据集的信息熵 H(D)

首先，计算所有Play类别（Yes/No）的信息熵。假设有 (n) 个Yes，(m) 个No，则总样本数 (N = n + m)。

$$H(D)=-\left(\frac{n}{N}{\log }_2\frac{n}{N}+\frac{m}{N}{\log }_2\frac{m}{N}\right)$$

2. 计算各特征的信息增益

对于每个特征（Outlook, Temperature, Humidity, Wind），我们需要计算它对数据集划分后信息熵的减少量，即信息增益。

$$IG(Feature)=H(D)-\sum _{v\in Values}\frac{|D_v|}{|D|}H(D_v)$$

$$其中，Values是特征的所有可能取值，D_v是特征取值为v的子集，|D|和|D_v|分别是总样本数和子集的样本数。$$

3. 选择信息增益最大的特征作为根节点

根据计算出的各个特征的信息增益，选择信息增益最大的特征作为树的第一个分支节点。

4. 递归地为每个分支节点重复步骤1-3

继续在每个子集中选择信息增益最大的特征进行划分，直到满足停止条件（如子集中所有实例都属于同一类别，或达到预设的最大深度等）。

示例计算（简化示例，仅计算Outlook特征的信息增益）：

假设我们仅计算特征Outlook的信息增益，Outlook有三个取值：Sunny, Overcast, Rain。

• Sunny下的Play类别分布：2个No，3个Yes。
• Overcast下的Play类别分布：4个Yes，0个No。
• Rain下的Play类别分布：3个Yes，3个No。

首先，计算整个数据集的信息熵 H(D)。整个数据集中Yes有9个，No有5个，共14个样本。

$$H(D)=-\left(\frac{9}{14}{\log }_2\frac{9}{14}+\frac{5}{14}{\log }_2\frac{5}{14}\right)$$

接着，计算Outlook的信息增益：

• Sunny的信息熵 H(Sunny)。
  • $$H(Sunny)=-\left(\frac{2}{5}{\log }_2\frac{2}{5}+\frac{3}{5}{\log }_2\frac{3}{5}\right)$$
• Overcast的信息熵 H(Overcast)。
  • $$H(Overcast)=-\left(\frac{0}{4}{\log }_2\frac{0}{4}+\frac{4}{4}{\log }_2\frac{4}{4}\right)$$
• Rain的信息熵 H(Rain)。
  • $$H(Rain)=-\left(\frac{3}{6}{\log }_2\frac{3}{6}+\frac{3}{6}{\log }_2\frac{3}{6}\right)$$

$$IG(Outlook)=H(D)-\left(\frac{5}{14}H(Sunny)+\frac{4}{14}H(Overcast)+\frac{5}{14}H(Rain)\right)$$

完成所有特征的信息增益计算后，假设Outlook的信息增益最大，则我们选择Outlook作为根节点开始构建决策树，并在Sunny、Overcast、Rain的子集中继续递归应用ID3算法，直至满足停止条件。

最终，我们会得到一个决策树模型，该模型能够根据天气情况预测是否适合户外活动。