相关资料链接:

决策树-维基百科

深入浅出理解决策树算法（一）-核心思想

深入浅出理解决策树算法（二）-ID3算法与C4.5算法

深刻理解决策树-动手计算ID3算法

机器学习——使用ID3算法从原理到实际举例理解决策树

基于信息论的三种决策树算法

划分数据集的最大原则是：使无序的数据变的有序。 如果一个训练数据中有20个特征，那么选取哪个做划分依据？这就必须采用量化的方法来判断，量化划分方法有多重，其中一项就是“信息论度量信息分类”。基于信息论的决策树算法有ID3 、C4.5和 CART等算法，其中C4.5和CART两种算法从ID3算法中衍生而来。此处仅记录ID3算法。

ID3算法（Iterative Dichotomiser 3 迭代二叉树3代）是一个由 Ross Quinlan 发明的用于决策树的算法。

这个算法是建立在 奥卡姆剃刀 的基础上：越是小型的决策树越优于大的决策树（简单理论）。尽管如此，该算法也不是总是生成最小的树形结构。而是一个 启发式算法 。

这个ID3算法可以归纳为以下几点：

1. 使用所有没有使用的属性并计算与之相关的样本熵值
2. 选取其中熵值最小的属性
3. 生成包含该属性的节点

理论公式

某个分类的信息

$$ l(x_i) = -\log_2 P(x_i) $$

这里(p(x_i))是选择该分类的概率。

熵

在信息论与概率统计中，熵是表示随机变量不确定性的度量。熵定义为信息的期望值，因此熵的计算方法如下：

$$ H = -\sum_{i=1}^{n} P(x_i) \log_2 P(x_i) $$ 这里 ( n ) 是分类的数目。

经验熵

熵中的概率由数据估计（特别是最大似然估计）得到。在 ( |D| ) 样本容量（样本个数）下，设有 ( K ) 个类 ( C_k ), ( k = 1,2,3,…,K )，( |C_k| ) 为属于类 ( C_k ) 的样本个数，得到其表达式如下：

$$ H(D) = -\sum_{k=1}^{K} \frac{|C_k|}{|D|} \log_2 \frac{|C_k|}{|D|} $$

条件熵

在已知随机变量 ( X ) 的条件下随机变量 ( Y ) 的不确定性，即在随机变量 ( X ) 给定的条件下随机变量 ( Y ) 的条件熵 ( H(Y|X) )，定义为 ( X ) 给定条件下 ( Y ) 的条件概率分布的熵对 ( X ) 的数学期望：

$$ H(Y|X) = \sum_{i=1}^{n} p_i H(Y|X=x_i) $$

信息增益

集合 ( D ) 的经验熵 ( H(D) ) 与特征 ( A ) 给定条件下 ( D ) 的经验条件熵 ( H(D|A) ) 之差：

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

实战(第四次作业题)

算法步骤

• 计算数据集中决策属性“是否等待”的熵（Entropy）。
• 对每个特征计算其信息增益（Information Gain），选择信息增益最大的特征作为根节点。
• 对选中的特征划分子数据集，递归地对每个子数据集继续构造子树，直到每个子集中的样本都属于同一类别，或者没有更多特征可以用来分裂。
• 生成最终的决策树。

第一层计算实例

我们首先要计算整体数据集的熵，然后逐个计算每个特征的信息增益：

整体数据集经验熵计算：

有6个样例决策为是，6个样例决策为否。

$$ Entropy(S) = -\left(\frac{6}{12}\log_2\frac{6}{12}\right) - \left(\frac{6}{12}\log_2\frac{6}{12}\right) = 1 $$

经验熵计算完了，现在，我们要计算每个特征的条件熵，以及对应的信息增益，并对信息增益进行排序，选择增益最大的特征作为第一个分裂点进行分裂。

1.特征“是否有其他选择”的信息增益：

这个特征包含两个属性取值，是和否

$$ Entropy(S_{是}) = -\left(\frac{2}{6}\log_2\frac{2}{6}\right) - \left(\frac{4}{6}\log_2\frac{4}{6}\right) ≈ 0.918 $$

$$ Entropy(S_{否}) = -\left(\frac{4}{6}\log_2\frac{4}{6}\right) - \left(\frac{4}{6}\log_2\frac{4}{6}\right) ≈ 0.780 $$

信息增益计算： $$ Gain(Decision, 是否有其他选择) = 1 - \left(\frac{6}{12} \times 0.918 + \frac{6}{12} \times 0.780\right) ≈ 0.151 $$ “是否有其他选择”这个特征的信息增益计算结束了，现在，我们需要对其他特征应用相同的计算方法，计算出剩余每个特征的信息增益。

2.特征“饿否”的信息增益：

这个特征包含两个属性取值，是和否

$$ Entropy(S_{是}) = -\left(\frac{5}{7}\log_2\frac{5}{7}\right) - \left(\frac{2}{7}\log_2\frac{2}{7}\right) ≈ 0.863 $$

$$ Entropy(S_{否}) = -\left(\frac{1}{5}\log_2\frac{1}{5}\right) - \left(\frac{4}{5}\log_2\frac{4}{5}\right) ≈ 0.722 $$

信息增益计算： $$ Gain(Decision, 饿否) = 1 - \left(\frac{7}{12} \times 0.863 + \frac{5}{12} \times 0.722\right) ≈ 0.1958 $$

3.特征"价格”的信息增益：

这个特征包含三个属性取值，$和$$和$$$

$$ Entropy(S_{$}) = -\left(\frac{3}{7}\log_2\frac{3}{7}\right) - \left(\frac{4}{7}\log_2\frac{4}{7}\right) ≈ 0.985 $$

$$ Entropy(S_{$$}) = -\left(\frac{2}{2}\log_2\frac{2}{2}\right) - \left(\frac{0}{2}\log_2\frac{0}{2}\right) = 0 $$

如果类的实例数为0，而实例总数为n，则需要计算*-(0/n) .log2(0/n)，*定义0*log2*0=0，熵只依赖于X的分布，与X的取值无关。这里，log(0）将等于-∞, 我们不能计算0次∞。这是决策树应用程序中经常出现的一种特殊情况。 $$ Entropy(S_{$$$}) = -\left(\frac{1}{3}\log_2\frac{1}{3}\right) - \left(\frac{2}{3}\log_2\frac{2}{3}\right) ≈ 0.918 $$ 信息增益计算： $$ Gain(Decision, 价格) = 1 - \left(\frac{7}{12} \times 0.985 + \frac{2}{12} \times 0+\frac{3}{12} \times 0.918\right) ≈ 0.1959 $$

4.特征“餐馆类型”的信息增益：

这个特征包含四个属性取值，法式和中餐和快餐和意大利式。

$$ Entropy(S_{法}) = -\left(\frac{1}{2}\log_2\frac{1}{2}\right) - \left(\frac{1}{2}\log_2\frac{1}{2}\right) = 1 $$

$$ Entropy(S_{中}) = -\left(\frac{1}{4}\log_2\frac{1}{4}\right) - \left(\frac{3}{4}\log_2\frac{3}{4}\right) ≈ 0.811 $$

$$ Entropy(S_{快}) = -\left(\frac{2}{4}\log_2\frac{2}{4}\right) - \left(\frac{2}{4}\log_2\frac{2}{4}\right) = 1 $$

$$ Entropy(S_{意}) = -\left(\frac{1}{2}\log_2\frac{1}{2}\right) - \left(\frac{1}{2}\log_2\frac{1}{2}\right) = 1 $$

信息增益计算： $$ Gain(Decision, 是否有其他选择) = 1 - \left(\frac{2}{12} \times 1 + \frac{4}{12} \times 0.811 + \frac{4}{12} \times 1+ \frac{2}{12} \times 1\right) ≈ 0.063 $$

5.特征“餐馆顾客人数”的信息增益：

这个特征包含三个属性取值，无人和有人和客满。

$$ Entropy(S_{无人}) = -\left(\frac{0}{2}\log_2\frac{0}{2}\right) - \left(\frac{2}{2}\log_2\frac{2}{2}\right) = 0 $$

$$ Entropy(S_{有人}) = -\left(\frac{4}{4}\log_2\frac{4}{4}\right) - \left(\frac{0}{4}\log_2\frac{0}{4}\right) = 0 $$

$$ Entropy(S_{客满}) = -\left(\frac{2}{6}\log_2\frac{2}{6}\right) - \left(\frac{4}{6}\log_2\frac{4}{6}\right) ≈ 0.918 $$

信息增益计算： $$ Gain(Decision, 餐馆顾客人数) = 1 - \left(\frac{2}{12} \times 0 + \frac{4}{12} \times 0+\frac{6}{12} \times 0.918\right) ≈ 0.541 $$

6.特征“等待时间(分钟)”的信息增益：

这个特征包含四个属性取值，0-10和10-30和30-60和>60。

$$ Entropy(S_{0-10}) = -\left(\frac{4}{6}\log_2\frac{4}{6}\right) - \left(\frac{2}{6}\log_2\frac{2}{6}\right) ≈ 0.918 $$

$$ Entropy(S_{10-30}) = -\left(\frac{1}{2}\log_2\frac{1}{2}\right) - \left(\frac{1}{2}\log_2\frac{1}{2}\right) = 1 $$

$$ Entropy(S_{30-60}) = -\left(\frac{1}{2}\log_2\frac{1}{2}\right) - \left(\frac{1}{2}\log_2\frac{1}{2}\right) = 1 $$

$$ Entropy(S_{>60}) = -\left(\frac{0}{2}\log_2\frac{0}{2}\right) - \left(\frac{2}{2}\log_2\frac{2}{2}\right) = 0 $$

信息增益计算： $$ Gain(Decision, 等待时间) = 1 - \left(\frac{6}{12} \times 0.918 + \frac{2}{12} \times 1 + \frac{2}{12} \times 1+ \frac{2}{12} \times 0\right) ≈ 0.2077 $$

第二层分裂决策

第一层分裂的特征确定后就要根据分裂的结果，进行第二层的分裂，同第一层，也是需要计算每个子集的经验熵 + 条件熵。

数据集第一步被餐馆顾客人数这个特征分裂成三个节点，现在需要对每个节点计算下一步的分裂特征。

通过对所有特征的信息增益进行比较，选择信息增益最高的特征作为决策节点，继续对数据集进行划分，直到生成完整的决策树。

餐馆顾客人数-无人(有人) 分支

在无人这个分支上，标签全部是no，也就是已经彻底的完成了分裂了，这个就可以作为叶子节点，无需继续分裂。在有人这个分支上，标签全部是yes，这个也可以作为叶子节点，无需继续分裂。

餐馆顾客人数-客满 分支

这个分支包含以下数据集：

该子集中有 2 个样例决策为是，4 个样例决策为否。

1.整体数据集经验熵计算：

$$ Entropy(S) = -\left(\frac{2}{6}\log_2\frac{2}{6}\right) - \left(\frac{4}{6}\log_2\frac{4}{6}\right) ≈ 0.918 $$

现在我们对剩下的特征重新计算信息增益。

1. 特征“是否有其他选择”的信息增益

计算条件熵： $$ Entropy(S_{是}) = -\left(\frac{1}{4}\log_2\frac{1}{4}\right) - \left(\frac{3}{4}\log_2\frac{3}{4}\right) ≈ 0.811 $$

$$ Entropy(S_{否}) = -\left(\frac{1}{2}\log_2\frac{1}{2}\right) - \left(\frac{1}{2}\log_2\frac{1}{2}\right) = 1 $$

信息增益： $$ Gain(Decision, 是否有其他选择) = 0.918 - \left(\frac{4}{6} \times 0.811 + \frac{2}{6} \times 1\right) ≈ 0.0207 $$

2. 特征“饿否”的信息增益

计算条件熵： $$ Entropy(S_{是}) = -\left(\frac{2}{4}\log_2\frac{2}{4}\right) - \left(\frac{2}{4}\log_2\frac{2}{4}\right) = 1 $$

$$ Entropy(S_{否}) = -\left(\frac{0}{2}\log_2\frac{0}{2}\right) - \left(\frac{2}{2}\log_2\frac{2}{2}\right) = 0 $$

信息增益： $$ Gain(Decision, 饿否) = 0.918 - \left(\frac{4}{6} \times 1 + \frac{2}{6} \times 0\right) ≈ 0.2513 $$

3. 特征“价格”的信息增益

计算条件熵： $$ Entropy(S_{$}) = -\left(\frac{2}{4}\log_2\frac{2}{4}\right) - \left(\frac{2}{4}\log_2\frac{2}{4}\right) = 1 $$

$$ Entropy(S_{$$$}) = -\left(\frac{0}{2}\log_2\frac{0}{2}\right) - \left(\frac{2}{2}\log_2\frac{2}{2}\right) = 0 $$

信息增益： $$ Gain(Decision, 价格) = 0.918 - \left(\frac{4}{6} \times 1 + \frac{2}{6} \times 0\right) ≈ 0.2513 $$

4. 特征“餐馆类型”的信息增益

计算条件熵： $$ Entropy(S_{中餐}) = -\left(\frac{1}{2}\log_2\frac{1}{2}\right) - \left(\frac{1}{2}\log_2\frac{1}{2}\right) = 1 $$

$$ Entropy(S_{快餐}) = -\left(\frac{1}{2}\log_2\frac{1}{2}\right) - \left(\frac{1}{2}\log_2\frac{1}{2}\right) = 1 $$

$$ Entropy(S_{法式})=Entropy(S_{意大利式})=0 $$

信息增益： $$ Gain(Decision, 餐馆类型) = 0.918 - \left(\frac{2}{6} \times 1 + \frac{2}{6} \times 1 + \frac{1}{6} \times 0 + \frac{1}{6} \times 0\right)≈ 0.2511 $$

5. 特征“等待时间(分钟)”的信息增益

计算条件熵： $$ Entropy(S_{10-30}) = Entropy(S_{30-60}) = -\left(\frac{1}{2}\log_2\frac{1}{2}\right) - \left(\frac{1}{2}\log_2\frac{1}{2}\right) = 1 $$

$$ Entropy(S_{>60}) = 0 $$

信息增益： $$ Gain(Decision, 等待时间) = 0.918 - \left(\frac{2}{6} \times 1 + \frac{2}{6} \times 1 + \frac{2}{6} \times 0 \right) ≈ 0.2513 $$

第三层分裂决策

第三层也是需要计算每个子集的经验熵 + 条件熵。此时前三的信息增益一致，选任意一个即可。

数据集第一步被餐馆饿否这个特征分裂成三个节点，现在需要对每个节点计算下一步的分裂特征。

通过对所有特征的信息增益进行比较，选择信息增益最高的特征作为决策节点，继续对数据集进行划分，直到生成完整的决策树。

餐馆顾客人数-客满|饿否-否 分支

在否这个分支上，标签全部是no，也就是已经彻底的完成了分裂了，非常纯，这个就可以作为叶子节点，无需继续分裂。

餐馆顾客人数-客满|饿否-是 分支

这个分支包含以下数据集：

此子集中有 2 个样例决策为是，2 个样例决策为否。

1.整体数据集经验熵计算：

该子集的经验熵为： $$ Entropy(S) = -\left(\frac{2}{4}\log_2\frac{2}{4}\right) - \left(\frac{2}{4}\log_2\frac{2}{4}\right) = 1 $$ 现在我们对剩余特征重新计算信息增益。

2. 特征“是否有其他选择”的信息增益

计算条件熵： $$ Entropy(S_{是}) = -\left(\frac{1}{3}\log_2\frac{1}{3}\right) - \left(\frac{2}{3}\log_2\frac{2}{3}\right) ≈ 0.918 $$

$$ Entropy(S_{否}) = -\left(\frac{1}{1}\log_2\frac{1}{1}\right) = 0 $$

信息增益： $$ Gain(Decision, 是否有其他选择) = 1 - \left(\frac{3}{4} \times 0.918 + \frac{1}{4} \times 0\right) ≈ 0.311 $$

2. 特征“价格”的信息增益

计算条件熵： $$ Entropy(S_{$}) = -\left(\frac{2}{3}\log_2\frac{2}{3}\right) - \left(\frac{1}{3}\log_2\frac{1}{3}\right) ≈ 0.918 $$

$$ Entropy(S_{$$$}) = 0 $$

信息增益： $$ Gain(Decision, 价格) = 1 - \left(\frac{3}{4} \times 0.918 + \frac{1}{4} \times 0\right) ≈ 0.311 $$

3. 特征“餐馆类型”的信息增益

计算条件熵： $$ Entropy(S_{中餐}) = -\left(\frac{1}{2}\log_2\frac{1}{2}\right) - \left(\frac{1}{2}\log_2\frac{1}{2}\right) = 1 $$

$$ Entropy(S_{快餐}) = Entropy(S_{意大利式}) = 0 $$

信息增益： $$ Gain(Decision, 餐馆类型) = 1 - \left(\frac{2}{4} \times 1 + \frac{1}{4} \times 0 + \frac{1}{4} \times 0\right) = 0.5 $$

4. 特征“等待时间(分钟)”的信息增益

计算条件熵： $$ Entropy(S_{10-30}) = Entropy(S_{30-60}) = -\left(\frac{1}{2}\log_2\frac{1}{2}\right) - \left(\frac{1}{2}\log_2\frac{1}{2}\right) = 1 $$ 信息增益： $$ Gain(Decision, 等待时间) = 1 - 1 = 0 $$

第四层分裂决策

数据集第一步被餐馆餐馆类型这个特征分裂成三个节点，现在需要对每个节点计算下一步的分裂特征。继续对数据集进行划分，直到生成完整的决策树。

餐馆顾客人数-客满|饿否-是|餐馆类型-快餐(意大利式) 分支

在快餐个分支上，标签全部是yes，意大利式分支上全是no，非常纯，作为叶子节点，无需继续分裂。

餐馆顾客人数-客满|饿否-是|餐馆类型-中餐 分支

这个分支包含以下数据集：

此分支中有 1 个样例决策为是，1 个样例决策为否。

1. 整体数据集经验熵计算

该子集的经验熵为： $$ Entropy(S) = -\left(\frac{1}{2}\log_2\frac{1}{2}\right) - \left(\frac{1}{2}\log_2\frac{1}{2}\right) = 1 $$ 现在我们对剩余特征重新计算信息增益。

2. 特征“是否有其他选择”的信息增益

计算条件熵： $$ Entropy(S_{是}) = -\left(\frac{1}{2}\log_2\frac{1}{2}\right) - \left(\frac{1}{2}\log_2\frac{1}{2}\right) = 1 $$ 因为是否有其他选择没有有效的分裂，信息增益为0。

3. 特征“价格”的信息增益

计算条件熵： $$ Entropy(S_{$}) = -\left(\frac{1}{2}\log_2\frac{1}{2}\right) - \left(\frac{1}{2}\log_2\frac{1}{2}\right) = 1 $$ 价格也没有带来有效分裂，信息增益为0。

4. 特征“等待时间(分钟)”的信息增益

计算条件熵： $$ Entropy(S_{10-30}) = Entropy(S_{30-60}) = 0 $$ 信息增益： $$ Gain(Decision, 等待时间) = 1 - 0 = 1 $$

第五层分裂决策

数据集第一步被餐馆等待时间这个特征分裂成两个节点，现在需要对每个节点计算下一步的分裂特征。继续对数据集进行划分，直到生成完整的决策树。

餐馆顾客人数-客满|饿否-是|餐馆类型-中餐|等待时间-1030(3060) 分支

在10-30分支上，标签全部是yes，30-60分支上全是no，非常纯，无需继续分裂。

至此，最终决策树已构建。

最终决策树结构

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

.
└─顾客人数
    ├─客满
    │  └─饿否
    │      ├─否->no
    │      └─是
    │          └─餐馆类型
    │              ├─中餐
    │              │  └─等待时间
    │              │      ├─10~30->yes
    │              │      └─30~60->no
    │              ├─快餐->yes
    │              └─意大利式->no
    ├─无人->no
    └─有人->yes


仅供参考，可能有误