下表给出判断目标人群是否购买电脑的训练数据，其中，第一列为序号不作 为划分依据，最后一列为分类标签，请利用信息增益（Information Gain）选 择每一次最优划分属性，生成决策树，请写出具体计算过程。（40’） Age Income Student Credit_rating Buys_computer (CLASS) 1 <=30 High No Fair No 2 <=30 High No Excellent No 3 31…40 High No Fair Yes 4 >40 Medium No Fair Yes 5 >40 Low Yes Fair Yes 6 >40 Low Yes Excellent No 7 31…40 Low Yes Excellent Yes 8 <=30 Medium No Fair No 9 <=30 Low Yes Fair Yes 10 >40 Medium Yes Fair Yes 11 <=30 Medium Yes Excellent Yes 12 31…40 Medium No Excellent Yes 13 31…40 High Yes Fair Yes 14 >40 Medium No Excellent No

首先，我们需要计算整个数据集的熵（entropy）：

$$
Ent(D) = - \sum_{k=1}^{2}{p_k\log_2p_k} = -\frac{9}{14}\log_2\frac{9}{14}-\frac{5}{14}\log_2\frac{5}{14} \approx 0.940
$$

其中，$p_k$表示样本中属于第$k$类的概率。

接下来，我们需要计算每个属性的信息增益（Information Gain），公式如下：

$$
Gain(D,a) = Ent(D) - \sum_{v=1}^{V}{\frac{|D^v|}{|D|}Ent(D^v)}
$$

其中，$a$表示属性，$v$表示属性$a$的一个可能取值，$D^v$表示在属性$a$上取值为$v$的样本子集，$V$表示属性$a$的可能取值数。

我们依次计算每个属性的信息增益：

1. 对于属性Age，我们需要计算两个子集的熵：年龄小于等于30岁的子集和年龄大于30岁的子集。

年龄小于等于30岁的子集包含5个样本，其中有2个不购买电脑，3个购买电脑。因此，其熵为：

$$
Ent(D^{<=30}) = -\frac{2}{5}\log_2\frac{2}{5}-\frac{3}{5}\log_2\frac{3}{5} \approx 0.971
$$

年龄大于30岁的子集包含9个样本，其中有3个不购买电脑，6个购买电脑。因此，其熵为：

$$
Ent(D^{>30}) = -\frac{3}{9}\log_2\frac{3}{9}-\frac{6}{9}\log_2\frac{6}{9} \approx 0.918
$$

因此，属性Age的信息增益为：

$$
Gain(D,Age) = Ent(D) - \frac{5}{14}Ent(D^{<=30}) - \frac{9}{14}Ent(D^{>30}) \approx 0.048
$$

2. 对于属性Income，我们需要计算三个子集的熵：收入高的子集、收入中等的子集和收入低的子集。

收入高的子集包含4个样本，其中有2个不购买电脑，2个购买电脑。因此，其熵为：

$$
Ent(D^{High}) = -\frac{2}{4}\log_2\frac{2}{4}-\frac{2}{4}\log_2\frac{2}{4} = 1
$$

收入中等的子集包含6个样本，其中有2个不购买电脑，4个购买电脑。因此，其熵为：

$$
Ent(D^{Medium}) = -\frac{2}{6}\log_2\frac{2}{6}-\frac{4}{6}\log_2\frac{4}{6} \approx 0.918
$$

收入低的子集包含4个样本，其中有5个购买电脑，1个不购买电脑。因此，其熵为：

$$
Ent(D^{Low}) = -\frac{1}{4}\log_2\frac{1}{4}-\frac{3}{4}\log_2\frac{3}{4} \approx 0.811
$$

因此，属性Income的信息增益为：

$$
Gain(D,Income) = Ent(D) - \frac{4}{14}Ent(D^{High}) - \frac{6}{14}Ent(D^{Medium}) - \frac{4}{14}Ent(D^{Low}) \approx 0.029
$$

3. 对于属性Student，我们需要计算两个子集的熵：是学生的子集和不是学生的子集。

是学生的子集包含6个样本，其中有2个不购买电脑，4个购买电脑。因此，其熵为：

$$
Ent(D^{Yes}) = -\frac{2}{6}\log_2\frac{2}{6}-\frac{4}{6}\log_2\frac{4}{6} \approx 0.918
$$

不是学生的子集包含8个样本，其中有3个不购买电脑，5个购买电脑。因此，其熵为：

$$
Ent(D^{No}) = -\frac{3}{8}\log_2\frac{3}{8}-\frac{5}{8}\log_2\frac{5}{8} \approx 0.954
$$

因此，属性Student的信息增益为：

$$
Gain(D,Student) = Ent(D) - \frac{6}{14}Ent(D^{Yes}) - \frac{8}{14}Ent(D^{No}) \approx 0.152
$$

4. 对于属性Credit\_rating，我们需要计算两个子集的熵：评级为fair的子集和评级为excellent的子集。

评级为fair的子集包含8个样本，其中有3个不购买电脑，5个购买电脑。因此，其熵为：

$$
Ent(D^{Fair}) = -\frac{3}{8}\log_2\frac{3}{8}-\frac{5}{8}\log_2\frac{5}{8} \approx 0.954
$$

评级为excellent的子集包含6个样本，其中有2个不购买电脑，4个购买电脑。因此，其熵为：

$$
Ent(D^{Excellent}) = -\frac{2}{6}\log_2\frac{2}{6}-\frac{4}{6}\log_2\frac{4}{6} \approx 0.918
$$

因此，属性Credit\_rating的信息增益为：

$$
Gain(D,Credit\_rating) = Ent(D) - \frac{8}{14}Ent(D^{Fair}) - \frac{6}{14}Ent(D^{Excellent}) \approx 0.083
$$

因此，我们选择属性Student作为第一次划分属性，生成如下决策树：

Student?
   Yes -> Buys_computer = Yes
   No -> Age?
           <=30 -> Buys_computer = No
           >30 -> Income?
                      High -> Buys_computer = No
                      Medium -> Buys_computer = Yes
                      Low -> Buys_computer = Yes