决策树算法练习题：预测购买行为

给定如下表格：

| 年龄 | 收入 | 学历 | 是否购买 | | ---- | ---- | ---- | -------- | | 18 | 20K | 本科 | 否 | | 25 | 30K | 硕士 | 是 | | 35 | 50K | 博士 | 是 | | 28 | 45K | 本科 | 是 | | 20 | 25K | 大专 | 否 | | 32 | 60K | 硕士 | 是 | | 40 | 80K | 博士 | 是 | | 22 | 28K | 本科 | 否 |

请利用决策树算法进行分类，预测一名年龄为30岁，收入为50K，学历为本科的人是否会购买。

解答：首先选择一个最优的属性作为根节点，可以用信息增益或者基尼指数来计算，这里选择信息增益，计算公式如下：

$$\operatorname{Gain}(D, A)=\operatorname{Ent}(D)-\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \operatorname{Ent}\left(D^{v}\right)$$

其中，$D$表示数据集，$A$表示属性，$V$表示属性$A$的取值集合，$D^v$表示属性$A$取值为$v$的数据集，$\operatorname{Ent}(D)$表示数据集的熵。

对于年龄（$A_1$）、收入（$A_2$）、学历（$A_3$）三个属性，分别计算其信息增益：

$$\begin{aligned}\operatorname{Gain}(D, A_1) &= \operatorname{Ent}(D) - [\frac{3}{8}\operatorname{Ent}(D_1) + \frac{3}{8}\operatorname{Ent}(D_2) + \frac{2}{8}\operatorname{Ent}(D_3)] \&= 0.954 - [\frac{3}{8}(-\frac{2}{3}\log_2\frac{2}{3}-\frac{1}{3}\log_2\frac{1}{3}) + \frac{3}{8}(-\frac{1}{3}\log_2\frac{1}{3}-\frac{2}{3}\log_2\frac{2}{3}) + \frac{2}{8}(-\log_2\frac{1}{2})] \&= 0.048\end{aligned}$$

$$\begin{aligned}\operatorname{Gain}(D, A_2) &= \operatorname{Ent}(D) - [\frac{3}{8}\operatorname{Ent}(D_1) + \frac{2}{8}\operatorname{Ent}(D_2) + \frac{1}{8}\operatorname{Ent}(D_3) + \frac{2}{8}\operatorname{Ent}(D_4)] \&= 0.954 - [\frac{3}{8}(-\frac{1}{3}\log_2\frac{1}{3}-\frac{2}{3}\log_2\frac{2}{3}) + \frac{2}{8}(-\frac{1}{2}\log_2\frac{1}{2}-\frac{1}{2}\log_2\frac{1}{2}) \&\qquad + \frac{1}{8}(-\log_2\frac{1}{1}) + \frac{2}{8}(-\frac{1}{2}\log_2\frac{1}{2}-\frac{1}{2}\log_2\frac{1}{2})] \&= 0.232\end{aligned}$$

$$\begin{aligned}\operatorname{Gain}(D, A_3) &= \operatorname{Ent}(D) - [\frac{3}{8}\operatorname{Ent}(D_1) + \frac{1}{8}\operatorname{Ent}(D_2) + \frac{2}{8}\operatorname{Ent}(D_3) + \frac{2}{8}\operatorname{Ent}(D_4)] \&= 0.954 - [\frac{3}{8}(-\frac{2}{3}\log_2\frac{2}{3}-\frac{1}{3}\log_2\frac{1}{3}) + \frac{1}{8}(-\log_2\frac{1}{1}) \&\qquad + \frac{2}{8}(-\frac{1}{2}\log_2\frac{1}{2}-\frac{1}{2}\log_2\frac{1}{2}) + \frac{2}{8}(-\frac{1}{2}\log_2\frac{1}{2}-\frac{1}{2}\log_2\frac{1}{2})] \&= 0.048\end{aligned}$$

可以发现，收入的信息增益最大，因此选择它作为根节点。将数据集按照收入分成两部分，分别计算年龄和学历的信息增益：

$$\begin{aligned}\operatorname{Gain}(D_1, A_1) &= \operatorname{Ent}(D_1) - [\frac{2}{3}\operatorname{Ent}(D_{11}) + \frac{1}{3}\operatorname{Ent}(D_{12})] \&= 0.918 - [\frac{2}{3}(-\frac{1}{2}\log_2\frac{1}{2}-\frac{1}{2}\log_2\frac{1}{2}) + \frac{1}{3}(-\log_2\frac{1}{1})] \&= 0.251\end{aligned}$$

$$\begin{aligned}\operatorname{Gain}(D_1, A_3) &= \operatorname{Ent}(D_1) - [\frac{2}{3}\operatorname{Ent}(D_{11}) + \frac{1}{3}\operatorname{Ent}(D_{12})] \&= 0.918 - [\frac{2}{3}(-\frac{1}{2}\log_2\frac{1}{2}-\frac{1}{2}\log_2\frac{1}{2}) + \frac{1}{3}(-\log_2\frac{1}{1})] \&= 0.251\end{aligned}$$

$$\begin{aligned}\operatorname{Gain}(D_2, A_1) &= \operatorname{Ent}(D_2) - [\frac{1}{2}\operatorname{Ent}(D_{21}) + \frac{1}{2}\operatorname{Ent}(D_{22})] \&= 1 - [\frac{1}{2}(-\log_2\frac{1}{1}) + \frac{1}{2}(-\log_2\frac{1}{1})] \&= 0\end{aligned}$$

$$\begin{aligned}\operatorname{Gain}(D_2, A_3) &= \operatorname{Ent}(D_2) - [\frac{1}{2}\operatorname{Ent}(D_{21}) + \frac{1}{2}\operatorname{Ent}(D_{22})] \&= 1 - [\frac{1}{2}(-\log_2\frac{1}{1}) + \frac{1}{2}(-\log_2\frac{1}{1})] \&= 0\end{aligned}$$

可以发现，年龄和学历的信息增益相等，因此选择年龄作为下一层节点。将数据集按照年龄分成两部分，分别计算学历的信息增益：

$$\begin{aligned}\operatorname{Gain}(D_{11}, A_3) &= \operatorname{Ent}(D_{11}) - [\frac{1}{2}\operatorname{Ent}(D_{111}) + \frac{1}{2}\operatorname{Ent}(D_{112})] \&= 1 - [\frac{1}{2}(-\log_2\frac{1}{1}) + \frac{1}{2}(-\log_2\frac{1}{1})] \&= 0\end{aligned}$$

$$\begin{aligned}\operatorname{Gain}(D_{12}, A_3) &= \operatorname{Ent}(D_{12}) - [\frac{1}{2}\operatorname{Ent}(D_{121}) + \frac{1}{2}\operatorname{Ent}(D_{122})] \&= 1 - [\frac{1}{2}(-\log_2\frac{1}{1}) + \frac{1}{2}(-\log_2\frac{1}{1})] \&= 0\end{aligned}$$

因此，最终的决策树如下：

收入
  |
  |-> 30K以上：购买
  |-> 30K以下：
        |
        |-> 年龄30岁以上：购买
        |-> 年龄30岁以下：不购买

根据决策树，可以预测一名年龄为30岁，收入为50K，学历为本科的人会购买。